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.
8 // let a = [ box 1,box 2, box 3];
15 // mir statement _10 = move _2[:-1]; replaced by:
17 // _12 = move _2[0 of 3];
19 // _13 = move _2[1 of 3];
20 // _10 = [move _12, move _13]
24 // and mir statement _11 = move _2[-1 of 1]; replaced by:
25 // _11 = move _2[2 of 3];
27 // FIXME: integrate this transformation to the mir build
30 use rustc::ty::TyCtxt;
32 use rustc::mir::visit::{Visitor, PlaceContext, NonUseContext};
33 use transform::{MirPass, MirSource};
34 use util::patch::MirPatch;
35 use rustc_data_structures::indexed_vec::{IndexVec};
37 pub struct UniformArrayMoveOut;
39 impl MirPass for UniformArrayMoveOut {
40 fn run_pass<'a, 'tcx>(&self,
41 tcx: TyCtxt<'a, 'tcx, 'tcx>,
43 mir: &mut Mir<'tcx>) {
44 let mut patch = MirPatch::new(mir);
46 let mut visitor = UniformArrayMoveOutVisitor{mir, patch: &mut patch, tcx};
47 visitor.visit_mir(mir);
53 struct UniformArrayMoveOutVisitor<'a, 'tcx: 'a> {
55 patch: &'a mut MirPatch<'tcx>,
56 tcx: TyCtxt<'a, 'tcx, 'tcx>,
59 impl<'a, 'tcx> Visitor<'tcx> for UniformArrayMoveOutVisitor<'a, 'tcx> {
60 fn visit_assign(&mut self,
62 dst_place: &Place<'tcx>,
63 rvalue: &Rvalue<'tcx>,
65 if let Rvalue::Use(Operand::Move(ref src_place)) = rvalue {
66 if let Place::Projection(ref proj) = *src_place {
67 if let ProjectionElem::ConstantIndex{offset: _,
69 from_end: false} = proj.elem {
70 // no need to transformation
72 let place_ty = proj.base.ty(self.mir, self.tcx).to_ty(self.tcx);
73 if let ty::Array(item_ty, const_size) = place_ty.sty {
74 if let Some(size) = const_size.assert_usize(self.tcx) {
75 assert!(size <= u32::max_value() as u64,
76 "uniform array move out doesn't supported
77 for array bigger then u32");
78 self.uniform(location, dst_place, proj, item_ty, size as u32);
85 self.super_assign(block, dst_place, rvalue, location)
89 impl<'a, 'tcx> UniformArrayMoveOutVisitor<'a, 'tcx> {
92 dst_place: &Place<'tcx>,
93 proj: &PlaceProjection<'tcx>,
94 item_ty: &'tcx ty::TyS<'tcx>,
97 // uniforms statements like_10 = move _2[:-1];
98 ProjectionElem::Subslice{from, to} => {
99 self.patch.make_nop(location);
100 let temps : Vec<_> = (from..(size-to)).map(|i| {
101 let temp = self.patch.new_temp(item_ty, self.mir.source_info(location).span);
102 self.patch.add_statement(location, StatementKind::StorageLive(temp));
103 self.patch.add_assign(location,
107 Place::Projection(box PlaceProjection{
108 base: proj.base.clone(),
109 elem: ProjectionElem::ConstantIndex{
116 self.patch.add_assign(location,
118 Rvalue::Aggregate(box AggregateKind::Array(item_ty),
120 |x| Operand::Move(Place::Local(*x))).collect()
123 self.patch.add_statement(location, StatementKind::StorageDead(temp));
126 // uniforms statements like _11 = move _2[-1 of 1];
127 ProjectionElem::ConstantIndex{offset, min_length: _, from_end: true} => {
128 self.patch.make_nop(location);
129 self.patch.add_assign(location,
133 Place::Projection(box PlaceProjection{
134 base: proj.base.clone(),
135 elem: ProjectionElem::ConstantIndex{
136 offset: size - offset,
138 from_end: false }}))));
145 // Restore Subslice move out after analysis
150 // _12 = move _2[0 of 3];
152 // _13 = move _2[1 of 3];
153 // _10 = [move _12, move _13]
157 // replaced by _10 = move _2[:-1];
159 pub struct RestoreSubsliceArrayMoveOut;
161 impl MirPass for RestoreSubsliceArrayMoveOut {
162 fn run_pass<'a, 'tcx>(&self,
163 tcx: TyCtxt<'a, 'tcx, 'tcx>,
165 mir: &mut Mir<'tcx>) {
166 let mut patch = MirPatch::new(mir);
168 let mut visitor = RestoreDataCollector {
169 locals_use: IndexVec::from_elem(LocalUse::new(), &mir.local_decls),
172 visitor.visit_mir(mir);
174 for candidate in &visitor.candidates {
175 let statement = &mir[candidate.block].statements[candidate.statement_index];
176 if let StatementKind::Assign(ref dst_place, ref rval) = statement.kind {
177 if let Rvalue::Aggregate(box AggregateKind::Array(_), ref items) = **rval {
178 let items : Vec<_> = items.iter().map(|item| {
179 if let Operand::Move(Place::Local(local)) = item {
180 let local_use = &visitor.locals_use[*local];
181 let opt_index_and_place = Self::try_get_item_source(local_use, mir);
182 // each local should be used twice:
183 // in assign and in aggregate statements
184 if local_use.use_count == 2 && opt_index_and_place.is_some() {
185 let (index, src_place) = opt_index_and_place.unwrap();
186 return Some((local_use, index, src_place));
192 let opt_src_place = items.first().and_then(|x| *x).map(|x| x.2);
193 let opt_size = opt_src_place.and_then(|src_place| {
194 let src_ty = src_place.ty(mir, tcx).to_ty(tcx);
195 if let ty::Array(_, ref size_o) = src_ty.sty {
196 size_o.assert_usize(tcx)
201 Self::check_and_patch(*candidate, &items, opt_size, &mut patch, dst_place);
210 impl RestoreSubsliceArrayMoveOut {
211 // Checks that source has size, all locals are inited from same source place and
212 // indices is an integer interval. If all checks pass do the replacent.
213 // items are Vec<Option<LocalUse, index in source array, source place for init local>>
214 fn check_and_patch<'tcx>(candidate: Location,
215 items: &[Option<(&LocalUse, u32, &Place<'tcx>)>],
216 opt_size: Option<u64>,
217 patch: &mut MirPatch<'tcx>,
218 dst_place: &Place<'tcx>) {
219 let opt_src_place = items.first().and_then(|x| *x).map(|x| x.2);
221 if opt_size.is_some() && items.iter().all(
222 |l| l.is_some() && l.unwrap().2 == opt_src_place.unwrap()) {
224 let indices: Vec<_> = items.iter().map(|x| x.unwrap().1).collect();
225 for i in 1..indices.len() {
226 if indices[i - 1] + 1 != indices[i] {
231 let min = *indices.first().unwrap();
232 let max = *indices.last().unwrap();
235 let locals_use = item.unwrap().0;
236 patch.make_nop(locals_use.alive.unwrap());
237 patch.make_nop(locals_use.dead.unwrap());
238 patch.make_nop(locals_use.first_use.unwrap());
240 patch.make_nop(candidate);
241 let size = opt_size.unwrap() as u32;
242 patch.add_assign(candidate,
246 Place::Projection(box PlaceProjection{
247 base: opt_src_place.unwrap().clone(),
248 elem: ProjectionElem::Subslice{
249 from: min, to: size - max - 1}}))));
253 fn try_get_item_source<'a, 'tcx>(local_use: &LocalUse,
254 mir: &'a Mir<'tcx>) -> Option<(u32, &'a Place<'tcx>)> {
255 if let Some(location) = local_use.first_use {
256 let block = &mir[location.block];
257 if block.statements.len() > location.statement_index {
258 let statement = &block.statements[location.statement_index];
259 if let StatementKind::Assign(
261 box Rvalue::Use(Operand::Move(Place::Projection(box PlaceProjection{
262 ref base, elem: ProjectionElem::ConstantIndex{
263 offset, min_length: _, from_end: false}})))) = statement.kind {
264 return Some((offset, base))
272 #[derive(Copy, Clone, Debug)]
274 alive: Option<Location>,
275 dead: Option<Location>,
277 first_use: Option<Location>,
281 pub fn new() -> Self {
282 LocalUse{alive: None, dead: None, use_count: 0, first_use: None}
286 struct RestoreDataCollector {
287 locals_use: IndexVec<Local, LocalUse>,
288 candidates: Vec<Location>,
291 impl<'tcx> Visitor<'tcx> for RestoreDataCollector {
292 fn visit_assign(&mut self,
295 rvalue: &Rvalue<'tcx>,
296 location: Location) {
297 if let Rvalue::Aggregate(box AggregateKind::Array(_), _) = *rvalue {
298 self.candidates.push(location);
300 self.super_assign(block, place, rvalue, location)
303 fn visit_local(&mut self,
305 context: PlaceContext<'tcx>,
306 location: Location) {
307 let local_use = &mut self.locals_use[*local];
309 PlaceContext::NonUse(NonUseContext::StorageLive) => local_use.alive = Some(location),
310 PlaceContext::NonUse(NonUseContext::StorageDead) => local_use.dead = Some(location),
312 local_use.use_count += 1;
313 if local_use.first_use.is_none() {
314 local_use.first_use = Some(location);