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.
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.
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.
18 // let a = [ box 1,box 2, box 3];
25 // mir statement _10 = move _2[:-1]; replaced by:
27 // _12 = move _2[0 of 3];
29 // _13 = move _2[1 of 3];
30 // _10 = [move _12, move _13]
34 // and mir statement _11 = move _2[-1 of 1]; replaced by:
35 // _11 = move _2[2 of 3];
37 // FIXME: integrate this transformation to the mir build
40 use rustc::ty::TyCtxt;
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};
47 pub struct UniformArrayMoveOut;
49 impl MirPass for UniformArrayMoveOut {
50 fn run_pass<'a, 'tcx>(&self,
51 tcx: TyCtxt<'a, 'tcx, 'tcx>,
53 mir: &mut Mir<'tcx>) {
54 let mut patch = MirPatch::new(mir);
56 let mut visitor = UniformArrayMoveOutVisitor{mir, patch: &mut patch, tcx};
57 visitor.visit_mir(mir);
63 struct UniformArrayMoveOutVisitor<'a, 'tcx: 'a> {
65 patch: &'a mut MirPatch<'tcx>,
66 tcx: TyCtxt<'a, 'tcx, 'tcx>,
69 impl<'a, 'tcx> Visitor<'tcx> for UniformArrayMoveOutVisitor<'a, 'tcx> {
70 fn visit_assign(&mut self,
72 dst_place: &Place<'tcx>,
73 rvalue: &Rvalue<'tcx>,
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: _,
79 from_end: false} = proj.elem {
80 // no need to transformation
82 let place_ty = proj.base.ty(self.mir, self.tcx).to_ty(self.tcx);
83 if let ty::TyArray(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);
95 self.super_assign(block, dst_place, rvalue, location)
99 impl<'a, 'tcx> UniformArrayMoveOutVisitor<'a, 'tcx> {
100 fn uniform(&mut self,
102 dst_place: &Place<'tcx>,
103 proj: &PlaceProjection<'tcx>,
104 item_ty: &'tcx ty::TyS<'tcx>,
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,
117 Place::Projection(box PlaceProjection{
118 base: proj.base.clone(),
119 elem: ProjectionElem::ConstantIndex{
126 self.patch.add_assign(location,
128 Rvalue::Aggregate(box AggregateKind::Array(item_ty),
130 |x| Operand::Move(Place::Local(*x))).collect()
133 self.patch.add_statement(location, StatementKind::StorageDead(temp));
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,
143 Place::Projection(box PlaceProjection{
144 base: proj.base.clone(),
145 elem: ProjectionElem::ConstantIndex{
146 offset: size - offset,
148 from_end: false }}))));
155 // Restore Subslice move out after analysis
160 // _12 = move _2[0 of 3];
162 // _13 = move _2[1 of 3];
163 // _10 = [move _12, move _13]
167 // replaced by _10 = move _2[:-1];
169 pub struct RestoreSubsliceArrayMoveOut;
171 impl MirPass for RestoreSubsliceArrayMoveOut {
172 fn run_pass<'a, 'tcx>(&self,
173 tcx: TyCtxt<'a, 'tcx, 'tcx>,
175 mir: &mut Mir<'tcx>) {
176 let mut patch = MirPatch::new(mir);
178 let mut visitor = RestoreDataCollector {
179 locals_use: IndexVec::from_elem(LocalUse::new(), &mir.local_decls),
182 visitor.visit_mir(mir);
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 statments
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));
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::TyArray(_, ref size_o) = src_ty.sty {
206 size_o.assert_usize(tcx)
211 Self::check_and_patch(*candidate, &items, opt_size, &mut patch, dst_place);
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);
231 if opt_size.is_some() && items.iter().all(
232 |l| l.is_some() && l.unwrap().2 == opt_src_place.unwrap()) {
234 let indicies: Vec<_> = items.iter().map(|x| x.unwrap().1).collect();
235 for i in 1..indicies.len() {
236 if indicies[i - 1] + 1 != indicies[i] {
241 let min = *indicies.first().unwrap();
242 let max = *indicies.last().unwrap();
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());
250 patch.make_nop(candidate);
251 let size = opt_size.unwrap() as u32;
252 patch.add_assign(candidate,
256 Place::Projection(box PlaceProjection{
257 base: opt_src_place.unwrap().clone(),
258 elem: ProjectionElem::Subslice{
259 from: min, to: size - max - 1}}))));
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(
271 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))
282 #[derive(Copy, Clone, Debug)]
284 alive: Option<Location>,
285 dead: Option<Location>,
287 first_use: Option<Location>,
291 pub fn new() -> Self {
292 LocalUse{alive: None, dead: None, use_count: 0, first_use: None}
296 struct RestoreDataCollector {
297 locals_use: IndexVec<Local, LocalUse>,
298 candidates: Vec<Location>,
301 impl<'tcx> Visitor<'tcx> for RestoreDataCollector {
302 fn visit_assign(&mut self,
305 rvalue: &Rvalue<'tcx>,
306 location: Location) {
307 if let Rvalue::Aggregate(box AggregateKind::Array(_), _) = *rvalue {
308 self.candidates.push(location);
310 self.super_assign(block, place, rvalue, location)
313 fn visit_local(&mut self,
315 context: PlaceContext<'tcx>,
316 location: Location) {
317 let local_use = &mut self.locals_use[*local];
319 PlaceContext::StorageLive => local_use.alive = Some(location),
320 PlaceContext::StorageDead => local_use.dead = Some(location),
322 local_use.use_count += 1;
323 if local_use.first_use.is_none() {
324 local_use.first_use = Some(location);