src/librustc_mir/transform/uniform_array_move_out.rs

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