src/librustc_mir/def_use.rs

   1 // Copyright 2016 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 //! Def-use analysis.
  12
  13 use rustc::mir::repr::{Local, Location, Lvalue, Mir};
  14 use rustc::mir::visit::{LvalueContext, MutVisitor, Visitor};
  15 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
  16 use std::marker::PhantomData;
  17 use std::mem;
  18
  19 pub struct DefUseAnalysis<'tcx> {
  20     info: IndexVec<Local, Info<'tcx>>,
  21     mir_summary: MirSummary,
  22 }
  23
  24 #[derive(Clone)]
  25 pub struct Info<'tcx> {
  26     pub defs_and_uses: Vec<Use<'tcx>>,
  27 }
  28
  29 #[derive(Clone)]
  30 pub struct Use<'tcx> {
  31     pub context: LvalueContext<'tcx>,
  32     pub location: Location,
  33 }
  34
  35 impl<'tcx> DefUseAnalysis<'tcx> {
  36     pub fn new(mir: &Mir<'tcx>) -> DefUseAnalysis<'tcx> {
  37         DefUseAnalysis {
  38             info: IndexVec::from_elem_n(Info::new(), mir.count_locals()),
  39             mir_summary: MirSummary::new(mir),
  40         }
  41     }
  42
  43     pub fn analyze(&mut self, mir: &Mir<'tcx>) {
  44         let mut finder = DefUseFinder {
  45             info: mem::replace(&mut self.info, IndexVec::new()),
  46             mir_summary: self.mir_summary,
  47         };
  48         finder.visit_mir(mir);
  49         self.info = finder.info
  50     }
  51
  52     pub fn local_info(&self, local: Local) -> &Info<'tcx> {
  53         &self.info[local]
  54     }
  55
  56     pub fn local_info_mut(&mut self, local: Local) -> &mut Info<'tcx> {
  57         &mut self.info[local]
  58     }
  59
  60     fn mutate_defs_and_uses<F>(&self, local: Local, mir: &mut Mir<'tcx>, mut callback: F)
  61                                where F: for<'a> FnMut(&'a mut Lvalue<'tcx>,
  62                                                       LvalueContext<'tcx>,
  63                                                       Location) {
  64         for lvalue_use in &self.info[local].defs_and_uses {
  65             MutateUseVisitor::new(local,
  66                                   &mut callback,
  67                                   self.mir_summary,
  68                                   mir).visit_location(mir, lvalue_use.location)
  69         }
  70     }
  71
  72     /// FIXME(pcwalton): This should update the def-use chains.
  73     pub fn replace_all_defs_and_uses_with(&self,
  74                                           local: Local,
  75                                           mir: &mut Mir<'tcx>,
  76                                           new_lvalue: Lvalue<'tcx>) {
  77         self.mutate_defs_and_uses(local, mir, |lvalue, _, _| *lvalue = new_lvalue.clone())
  78     }
  79 }
  80
  81 struct DefUseFinder<'tcx> {
  82     info: IndexVec<Local, Info<'tcx>>,
  83     mir_summary: MirSummary,
  84 }
  85
  86 impl<'tcx> DefUseFinder<'tcx> {
  87     fn lvalue_mut_info(&mut self, lvalue: &Lvalue<'tcx>) -> Option<&mut Info<'tcx>> {
  88         let info = &mut self.info;
  89         self.mir_summary.local_index(lvalue).map(move |local| &mut info[local])
  90     }
  91 }
  92
  93 impl<'tcx> Visitor<'tcx> for DefUseFinder<'tcx> {
  94     fn visit_lvalue(&mut self,
  95                     lvalue: &Lvalue<'tcx>,
  96                     context: LvalueContext<'tcx>,
  97                     location: Location) {
  98         if let Some(ref mut info) = self.lvalue_mut_info(lvalue) {
  99             info.defs_and_uses.push(Use {
 100                 context: context,
 101                 location: location,
 102             })
 103         }
 104         self.super_lvalue(lvalue, context, location)
 105     }
 106 }
 107
 108 impl<'tcx> Info<'tcx> {
 109     fn new() -> Info<'tcx> {
 110         Info {
 111             defs_and_uses: vec![],
 112         }
 113     }
 114
 115     pub fn def_count(&self) -> usize {
 116         self.defs_and_uses.iter().filter(|lvalue_use| lvalue_use.context.is_mutating_use()).count()
 117     }
 118
 119     pub fn def_count_not_including_drop(&self) -> usize {
 120         self.defs_and_uses.iter().filter(|lvalue_use| {
 121             lvalue_use.context.is_mutating_use() && !lvalue_use.context.is_drop()
 122         }).count()
 123     }
 124
 125     pub fn use_count(&self) -> usize {
 126         self.defs_and_uses.iter().filter(|lvalue_use| {
 127             lvalue_use.context.is_nonmutating_use()
 128         }).count()
 129     }
 130 }
 131
 132 struct MutateUseVisitor<'tcx, F> {
 133     query: Local,
 134     callback: F,
 135     mir_summary: MirSummary,
 136     phantom: PhantomData<&'tcx ()>,
 137 }
 138
 139 impl<'tcx, F> MutateUseVisitor<'tcx, F> {
 140     fn new(query: Local, callback: F, mir_summary: MirSummary, _: &Mir<'tcx>)
 141            -> MutateUseVisitor<'tcx, F>
 142            where F: for<'a> FnMut(&'a mut Lvalue<'tcx>, LvalueContext<'tcx>, Location) {
 143         MutateUseVisitor {
 144             query: query,
 145             callback: callback,
 146             mir_summary: mir_summary,
 147             phantom: PhantomData,
 148         }
 149     }
 150 }
 151
 152 impl<'tcx, F> MutVisitor<'tcx> for MutateUseVisitor<'tcx, F>
 153               where F: for<'a> FnMut(&'a mut Lvalue<'tcx>, LvalueContext<'tcx>, Location) {
 154     fn visit_lvalue(&mut self,
 155                     lvalue: &mut Lvalue<'tcx>,
 156                     context: LvalueContext<'tcx>,
 157                     location: Location) {
 158         if self.mir_summary.local_index(lvalue) == Some(self.query) {
 159             (self.callback)(lvalue, context, location)
 160         }
 161         self.super_lvalue(lvalue, context, location)
 162     }
 163 }
 164
 165 /// A small structure that enables various metadata of the MIR to be queried
 166 /// without a reference to the MIR itself.
 167 #[derive(Clone, Copy)]
 168 pub struct MirSummary {
 169     arg_count: usize,
 170     var_count: usize,
 171     temp_count: usize,
 172 }
 173
 174 impl MirSummary {
 175     pub fn new(mir: &Mir) -> MirSummary {
 176         MirSummary {
 177             arg_count: mir.arg_decls.len(),
 178             var_count: mir.var_decls.len(),
 179             temp_count: mir.temp_decls.len(),
 180         }
 181     }
 182
 183     pub fn local_index<'tcx>(&self, lvalue: &Lvalue<'tcx>) -> Option<Local> {
 184         match *lvalue {
 185             Lvalue::Arg(arg) => Some(Local::new(arg.index())),
 186             Lvalue::Var(var) => Some(Local::new(var.index() + self.arg_count)),
 187             Lvalue::Temp(temp) => {
 188                 Some(Local::new(temp.index() + self.arg_count + self.var_count))
 189             }
 190             Lvalue::ReturnPointer => {
 191                 Some(Local::new(self.arg_count + self.var_count + self.temp_count))
 192             }
 193             _ => None,
 194         }
 195     }
 196 }
 197