src/librustc_mir/transform/uniform_array_move_out.rs

   1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 // This pass converts move out from array by Subslice and
  12 // ConstIndex{.., from_end: true} to ConstIndex move out(s) from begin
  13 // of array. It allows detect error by mir borrowck and elaborate
  14 // drops for array without additional work.
  15 //
  16 // Example:
  17 //
  18 // let a = [ box 1,box 2, box 3];
  19 // if b {
  20 //  let [_a.., _] = a;
  21 // } else {
  22 //  let [.., _b] = a;
  23 // }
  24 //
  25 //  mir statement _10 = move _2[:-1]; replaced by:
  26 //  StorageLive(_12);
  27 //  _12 = move _2[0 of 3];
  28 //  StorageLive(_13);
  29 //  _13 = move _2[1 of 3];
  30 //  _10 = [move _12, move _13]
  31 //  StorageDead(_12);
  32 //  StorageDead(_13);
  33 //
  34 //  and mir statement _11 = move _2[-1 of 1]; replaced by:
  35 //  _11 = move _2[2 of 3];
  36 //
  37 // FIXME: integrate this transformation to the mir build
  38
  39 use rustc::ty;
  40 use rustc::ty::TyCtxt;
  41 use rustc::mir::*;
  42 use rustc::mir::visit::{Visitor, PlaceContext};
  43 use transform::{MirPass, MirSource};
  44 use util::patch::MirPatch;
  45 use rustc_data_structures::indexed_vec::{IndexVec};
  46
  47 pub struct UniformArrayMoveOut;
  48
  49 impl MirPass for UniformArrayMoveOut {
  50     fn run_pass<'a, 'tcx>(&self,
  51                           tcx: TyCtxt<'a, 'tcx, 'tcx>,
  52                           _src: MirSource,
  53                           mir: &mut Mir<'tcx>) {
  54         let mut patch = MirPatch::new(mir);
  55         {
  56             let mut visitor = UniformArrayMoveOutVisitor{mir, patch: &mut patch, tcx};
  57             visitor.visit_mir(mir);
  58         }
  59         patch.apply(mir);
  60     }
  61 }
  62
  63 struct UniformArrayMoveOutVisitor<'a, 'tcx: 'a> {
  64     mir: &'a Mir<'tcx>,
  65     patch: &'a mut MirPatch<'tcx>,
  66     tcx: TyCtxt<'a, 'tcx, 'tcx>,
  67 }
  68
  69 impl<'a, 'tcx> Visitor<'tcx> for UniformArrayMoveOutVisitor<'a, 'tcx> {
  70     fn visit_assign(&mut self,
  71                     block: BasicBlock,
  72                     dst_place: &Place<'tcx>,
  73                     rvalue: &Rvalue<'tcx>,
  74                     location: Location) {
  75         if let Rvalue::Use(Operand::Move(ref src_place)) = rvalue {
  76             if let Place::Projection(ref proj) = *src_place {
  77                 if let ProjectionElem::ConstantIndex{offset: _,
  78                                                      min_length: _,
  79                                                      from_end: false} = proj.elem {
  80                     // no need to transformation
  81                 } else {
  82                     let place_ty = proj.base.ty(self.mir, self.tcx).to_ty(self.tcx);
  83                     if let ty::Array(item_ty, const_size) = place_ty.sty {
  84                         if let Some(size) = const_size.assert_usize(self.tcx) {
  85                             assert!(size <= u32::max_value() as u64,
  86                                     "uniform array move out doesn't supported
  87                                      for array bigger then u32");
  88                             self.uniform(location, dst_place, proj, item_ty, size as u32);
  89                         }
  90                     }
  91
  92                 }
  93             }
  94         }
  95         self.super_assign(block, dst_place, rvalue, location)
  96     }
  97 }
  98
  99 impl<'a, 'tcx> UniformArrayMoveOutVisitor<'a, 'tcx> {
 100     fn uniform(&mut self,
 101                location: Location,
 102                dst_place: &Place<'tcx>,
 103                proj: &PlaceProjection<'tcx>,
 104                item_ty: &'tcx ty::TyS<'tcx>,
 105                size: u32) {
 106         match proj.elem {
 107             // uniforms statements like_10 = move _2[:-1];
 108             ProjectionElem::Subslice{from, to} => {
 109                 self.patch.make_nop(location);
 110                 let temps : Vec<_> = (from..(size-to)).map(|i| {
 111                     let temp = self.patch.new_temp(item_ty, self.mir.source_info(location).span);
 112                     self.patch.add_statement(location, StatementKind::StorageLive(temp));
 113                     self.patch.add_assign(location,
 114                                           Place::Local(temp),
 115                                           Rvalue::Use(
 116                                               Operand::Move(
 117                                                   Place::Projection(box PlaceProjection{
 118                                                       base: proj.base.clone(),
 119                                                       elem: ProjectionElem::ConstantIndex{
 120                                                           offset: i,
 121                                                           min_length: size,
 122                                                           from_end: false}
 123                                                   }))));
 124                     temp
 125                 }).collect();
 126                 self.patch.add_assign(location,
 127                                       dst_place.clone(),
 128                                       Rvalue::Aggregate(box AggregateKind::Array(item_ty),
 129                                       temps.iter().map(
 130                                           |x| Operand::Move(Place::Local(*x))).collect()
 131                                       ));
 132                 for temp in temps {
 133                     self.patch.add_statement(location, StatementKind::StorageDead(temp));
 134                 }
 135             }
 136             // uniforms statements like _11 = move _2[-1 of 1];
 137             ProjectionElem::ConstantIndex{offset, min_length: _, from_end: true} => {
 138                 self.patch.make_nop(location);
 139                 self.patch.add_assign(location,
 140                                       dst_place.clone(),
 141                                       Rvalue::Use(
 142                                           Operand::Move(
 143                                               Place::Projection(box PlaceProjection{
 144                                                   base: proj.base.clone(),
 145                                                   elem: ProjectionElem::ConstantIndex{
 146                                                       offset: size - offset,
 147                                                       min_length: size,
 148                                                       from_end: false }}))));
 149             }
 150             _ => {}
 151         }
 152     }
 153 }
 154
 155 // Restore Subslice move out after analysis
 156 // Example:
 157 //
 158 //  next statements:
 159 //   StorageLive(_12);
 160 //   _12 = move _2[0 of 3];
 161 //   StorageLive(_13);
 162 //   _13 = move _2[1 of 3];
 163 //   _10 = [move _12, move _13]
 164 //   StorageDead(_12);
 165 //   StorageDead(_13);
 166 //
 167 // replaced by _10 = move _2[:-1];
 168
 169 pub struct RestoreSubsliceArrayMoveOut;
 170
 171 impl MirPass for RestoreSubsliceArrayMoveOut {
 172     fn run_pass<'a, 'tcx>(&self,
 173                           tcx: TyCtxt<'a, 'tcx, 'tcx>,
 174                           _src: MirSource,
 175                           mir: &mut Mir<'tcx>) {
 176         let mut patch = MirPatch::new(mir);
 177         {
 178             let mut visitor = RestoreDataCollector {
 179                 locals_use: IndexVec::from_elem(LocalUse::new(), &mir.local_decls),
 180                 candidates: vec![],
 181             };
 182             visitor.visit_mir(mir);
 183
 184             for candidate in &visitor.candidates {
 185                 let statement = &mir[candidate.block].statements[candidate.statement_index];
 186                 if let StatementKind::Assign(ref dst_place, ref rval) = statement.kind {
 187                     if let Rvalue::Aggregate(box AggregateKind::Array(_), ref items) = **rval {
 188                         let items : Vec<_> = items.iter().map(|item| {
 189                             if let Operand::Move(Place::Local(local)) = item {
 190                                 let local_use = &visitor.locals_use[*local];
 191                                 let opt_index_and_place = Self::try_get_item_source(local_use, mir);
 192                                 // each local should be used twice:
 193                                 //  in assign and in aggregate statements
 194                                 if local_use.use_count == 2 && opt_index_and_place.is_some() {
 195                                     let (index, src_place) = opt_index_and_place.unwrap();
 196                                     return Some((local_use, index, src_place));
 197                                 }
 198                             }
 199                             None
 200                         }).collect();
 201
 202                         let opt_src_place = items.first().and_then(|x| *x).map(|x| x.2);
 203                         let opt_size = opt_src_place.and_then(|src_place| {
 204                             let src_ty = src_place.ty(mir, tcx).to_ty(tcx);
 205                             if let ty::Array(_, ref size_o) = src_ty.sty {
 206                                 size_o.assert_usize(tcx)
 207                             } else {
 208                                 None
 209                             }
 210                         });
 211                         Self::check_and_patch(*candidate, &items, opt_size, &mut patch, dst_place);
 212                     }
 213                 }
 214             }
 215         }
 216         patch.apply(mir);
 217     }
 218 }
 219
 220 impl RestoreSubsliceArrayMoveOut {
 221     // Checks that source has size, all locals are inited from same source place and
 222     // indices is an integer interval. If all checks pass do the replacent.
 223     // items are Vec<Option<LocalUse, index in source array, source place for init local>>
 224     fn check_and_patch<'tcx>(candidate: Location,
 225                              items: &[Option<(&LocalUse, u32, &Place<'tcx>)>],
 226                              opt_size: Option<u64>,
 227                              patch: &mut MirPatch<'tcx>,
 228                              dst_place: &Place<'tcx>) {
 229         let opt_src_place = items.first().and_then(|x| *x).map(|x| x.2);
 230
 231         if opt_size.is_some() && items.iter().all(
 232             |l| l.is_some() && l.unwrap().2 == opt_src_place.unwrap()) {
 233
 234             let indices: Vec<_> = items.iter().map(|x| x.unwrap().1).collect();
 235             for i in 1..indices.len() {
 236                 if indices[i - 1] + 1 != indices[i] {
 237                     return;
 238                 }
 239             }
 240
 241             let min = *indices.first().unwrap();
 242             let max = *indices.last().unwrap();
 243
 244             for item in items {
 245                 let locals_use = item.unwrap().0;
 246                 patch.make_nop(locals_use.alive.unwrap());
 247                 patch.make_nop(locals_use.dead.unwrap());
 248                 patch.make_nop(locals_use.first_use.unwrap());
 249             }
 250             patch.make_nop(candidate);
 251             let size = opt_size.unwrap() as u32;
 252             patch.add_assign(candidate,
 253                              dst_place.clone(),
 254                              Rvalue::Use(
 255                                  Operand::Move(
 256                                      Place::Projection(box PlaceProjection{
 257                                          base: opt_src_place.unwrap().clone(),
 258                                          elem: ProjectionElem::Subslice{
 259                                              from: min, to: size - max - 1}}))));
 260         }
 261     }
 262
 263     fn try_get_item_source<'a, 'tcx>(local_use: &LocalUse,
 264                                      mir: &'a Mir<'tcx>) -> Option<(u32, &'a Place<'tcx>)> {
 265         if let Some(location) = local_use.first_use {
 266             let block = &mir[location.block];
 267             if block.statements.len() > location.statement_index {
 268                 let statement = &block.statements[location.statement_index];
 269                 if let StatementKind::Assign(
 270                     Place::Local(_),
 271                     box Rvalue::Use(Operand::Move(Place::Projection(box PlaceProjection{
 272                         ref base, elem: ProjectionElem::ConstantIndex{
 273                             offset, min_length: _, from_end: false}})))) = statement.kind {
 274                     return Some((offset, base))
 275                 }
 276             }
 277         }
 278         None
 279     }
 280 }
 281
 282 #[derive(Copy, Clone, Debug)]
 283 struct LocalUse {
 284     alive: Option<Location>,
 285     dead: Option<Location>,
 286     use_count: u32,
 287     first_use: Option<Location>,
 288 }
 289
 290 impl LocalUse {
 291     pub fn new() -> Self {
 292         LocalUse{alive: None, dead: None, use_count: 0, first_use: None}
 293     }
 294 }
 295
 296 struct RestoreDataCollector {
 297     locals_use: IndexVec<Local, LocalUse>,
 298     candidates: Vec<Location>,
 299 }
 300
 301 impl<'tcx> Visitor<'tcx> for RestoreDataCollector {
 302     fn visit_assign(&mut self,
 303                     block: BasicBlock,
 304                     place: &Place<'tcx>,
 305                     rvalue: &Rvalue<'tcx>,
 306                     location: Location) {
 307         if let Rvalue::Aggregate(box AggregateKind::Array(_), _) = *rvalue {
 308             self.candidates.push(location);
 309         }
 310         self.super_assign(block, place, rvalue, location)
 311     }
 312
 313     fn visit_local(&mut self,
 314                    local: &Local,
 315                    context: PlaceContext<'tcx>,
 316                    location: Location) {
 317         let local_use = &mut self.locals_use[*local];
 318         match context {
 319             PlaceContext::StorageLive => local_use.alive = Some(location),
 320             PlaceContext::StorageDead => local_use.dead = Some(location),
 321             _ => {
 322                 local_use.use_count += 1;
 323                 if local_use.first_use.is_none() {
 324                     local_use.first_use = Some(location);
 325                 }
 326             }
 327         }
 328     }
 329 }