compiler/rustc_mir_dataflow/src/value_analysis.rs

   1 //! This module provides a framework on top of the normal MIR dataflow framework to simplify the
   2 //! implementation of analyses that track the values stored in places of interest.
   3 //!
   4 //! The default methods of [`ValueAnalysis`] (prefixed with `super_` instead of `handle_`)
   5 //! provide some behavior that should be valid for all abstract domains that are based only on the
   6 //! value stored in a certain place. On top of these default rules, an implementation should
   7 //! override some of the `handle_` methods. For an example, see `ConstAnalysis`.
   8 //!
   9 //! An implementation must also provide a [`Map`]. Before the anaylsis begins, all places that
  10 //! should be tracked during the analysis must be registered. The set of tracked places cannot be
  11 //! changed during the analysis.
  12
  13 use std::fmt::{Debug, Formatter};
  14
  15 use rustc_data_structures::fx::FxHashMap;
  16 use rustc_index::vec::IndexVec;
  17 use rustc_middle::mir::*;
  18 use rustc_middle::ty::{self, Ty, TyCtxt};
  19 use rustc_target::abi::VariantIdx;
  20
  21 use crate::{
  22     fmt::DebugWithContext, lattice::FlatSet, Analysis, AnalysisDomain, CallReturnPlaces,
  23     JoinSemiLattice, SwitchIntEdgeEffects,
  24 };
  25
  26 pub trait ValueAnalysis<'tcx> {
  27     /// For each place of interest, the analysis tracks a value of the given type.
  28     type Value: Clone + JoinSemiLattice + HasBottom + HasTop;
  29
  30     const NAME: &'static str;
  31
  32     fn map(&self) -> &Map;
  33
  34     fn handle_statement(&self, statement: &Statement<'tcx>, state: &mut State<Self::Value>) {
  35         self.super_statement(statement, state)
  36     }
  37
  38     fn super_statement(&self, statement: &Statement<'tcx>, state: &mut State<Self::Value>) {
  39         match &statement.kind {
  40             StatementKind::Assign(box (place, rvalue)) => {
  41                 self.handle_assign(*place, rvalue, state);
  42             }
  43             StatementKind::SetDiscriminant { .. } => {
  44                 // Could tread this as writing a constant to a pseudo-place.
  45             }
  46             StatementKind::CopyNonOverlapping(..) => {
  47                 // FIXME: What to do here?
  48             }
  49             StatementKind::StorageLive(..)
  50             | StatementKind::StorageDead(..)
  51             | StatementKind::Deinit(_) => {
  52                 // Could perhaps use these.
  53             }
  54             StatementKind::Nop
  55             | StatementKind::Retag(..)
  56             | StatementKind::FakeRead(..)
  57             | StatementKind::Coverage(..)
  58             | StatementKind::AscribeUserType(..) => (),
  59         }
  60     }
  61
  62     fn handle_assign(
  63         &self,
  64         target: Place<'tcx>,
  65         rvalue: &Rvalue<'tcx>,
  66         state: &mut State<Self::Value>,
  67     ) {
  68         self.super_assign(target, rvalue, state)
  69     }
  70
  71     fn super_assign(
  72         &self,
  73         target: Place<'tcx>,
  74         rvalue: &Rvalue<'tcx>,
  75         state: &mut State<Self::Value>,
  76     ) {
  77         match rvalue {
  78             Rvalue::Ref(_, BorrowKind::Shared, place) => {
  79                 let target_deref = self
  80                     .map()
  81                     .find(target.as_ref())
  82                     .and_then(|target| self.map().apply_elem(target, ProjElem::Deref));
  83                 let place = self.map().find(place.as_ref());
  84                 match (target_deref, place) {
  85                     (Some(target_deref), Some(place)) => {
  86                         state.assign_idx(target_deref, ValueOrPlace::Place(place), self.map())
  87                     }
  88                     _ => (),
  89                 }
  90             }
  91             Rvalue::Ref(_, _, place) | Rvalue::AddressOf(_, place) => {
  92                 state.flood(place.as_ref(), self.map(), Self::Value::top());
  93             }
  94             _ => {
  95                 let result = self.handle_rvalue(rvalue, state);
  96                 state.assign(target.as_ref(), result, self.map());
  97             }
  98         }
  99     }
 100
 101     fn handle_rvalue(
 102         &self,
 103         rvalue: &Rvalue<'tcx>,
 104         state: &mut State<Self::Value>,
 105     ) -> ValueOrPlace<Self::Value> {
 106         self.super_rvalue(rvalue, state)
 107     }
 108
 109     fn super_rvalue(
 110         &self,
 111         rvalue: &Rvalue<'tcx>,
 112         state: &mut State<Self::Value>,
 113     ) -> ValueOrPlace<Self::Value> {
 114         match rvalue {
 115             Rvalue::Use(operand) => self.handle_operand(operand, state),
 116             Rvalue::CopyForDeref(place) => self.handle_operand(&Operand::Copy(*place), state),
 117             Rvalue::Ref(..) | Rvalue::AddressOf(..) => {
 118                 bug!("this rvalue must be handled by handle_assign() or super_assign()")
 119             }
 120             _ => {
 121                 // FIXME: Check that other Rvalues really have no side-effect.
 122                 ValueOrPlace::Unknown
 123             }
 124         }
 125     }
 126
 127     fn handle_operand(
 128         &self,
 129         operand: &Operand<'tcx>,
 130         state: &mut State<Self::Value>,
 131     ) -> ValueOrPlace<Self::Value> {
 132         self.super_operand(operand, state)
 133     }
 134
 135     fn super_operand(
 136         &self,
 137         operand: &Operand<'tcx>,
 138         state: &mut State<Self::Value>,
 139     ) -> ValueOrPlace<Self::Value> {
 140         match operand {
 141             Operand::Constant(box constant) => {
 142                 ValueOrPlace::Value(self.handle_constant(constant, state))
 143             }
 144             Operand::Copy(place) | Operand::Move(place) => {
 145                 // Do want want to handle moves different? Could flood place with bottom.
 146                 self.map()
 147                     .find(place.as_ref())
 148                     .map(ValueOrPlace::Place)
 149                     .unwrap_or(ValueOrPlace::Unknown)
 150             }
 151         }
 152     }
 153
 154     fn handle_constant(
 155         &self,
 156         constant: &Constant<'tcx>,
 157         state: &mut State<Self::Value>,
 158     ) -> Self::Value {
 159         self.super_constant(constant, state)
 160     }
 161
 162     fn super_constant(
 163         &self,
 164         _constant: &Constant<'tcx>,
 165         _state: &mut State<Self::Value>,
 166     ) -> Self::Value {
 167         Self::Value::top()
 168     }
 169
 170     fn handle_terminator(&self, terminator: &Terminator<'tcx>, state: &mut State<Self::Value>) {
 171         self.super_terminator(terminator, state)
 172     }
 173
 174     fn super_terminator(&self, _terminator: &Terminator<'tcx>, _state: &mut State<Self::Value>) {}
 175
 176     fn handle_call_return(
 177         &self,
 178         return_places: CallReturnPlaces<'_, 'tcx>,
 179         state: &mut State<Self::Value>,
 180     ) {
 181         self.super_call_return(return_places, state)
 182     }
 183
 184     fn super_call_return(
 185         &self,
 186         return_places: CallReturnPlaces<'_, 'tcx>,
 187         state: &mut State<Self::Value>,
 188     ) {
 189         return_places.for_each(|place| {
 190             state.flood(place.as_ref(), self.map(), Self::Value::top());
 191         })
 192     }
 193
 194     fn handle_switch_int(
 195         &self,
 196         discr: &Operand<'tcx>,
 197         apply_edge_effects: &mut impl SwitchIntEdgeEffects<State<Self::Value>>,
 198     ) {
 199         self.super_switch_int(discr, apply_edge_effects)
 200     }
 201
 202     fn super_switch_int(
 203         &self,
 204         _discr: &Operand<'tcx>,
 205         _apply_edge_effects: &mut impl SwitchIntEdgeEffects<State<Self::Value>>,
 206     ) {
 207     }
 208
 209     fn wrap(self) -> ValueAnalysisWrapper<Self>
 210     where
 211         Self: Sized,
 212     {
 213         ValueAnalysisWrapper(self)
 214     }
 215 }
 216
 217 pub struct ValueAnalysisWrapper<T>(pub T);
 218
 219 impl<'tcx, T: ValueAnalysis<'tcx>> AnalysisDomain<'tcx> for ValueAnalysisWrapper<T> {
 220     type Domain = State<T::Value>;
 221
 222     type Direction = crate::Forward;
 223
 224     const NAME: &'static str = T::NAME;
 225
 226     fn bottom_value(&self, _body: &Body<'tcx>) -> Self::Domain {
 227         State(IndexVec::from_elem_n(T::Value::bottom(), self.0.map().value_count))
 228     }
 229
 230     fn initialize_start_block(&self, body: &Body<'tcx>, state: &mut Self::Domain) {
 231         for arg in body.args_iter() {
 232             state.flood(PlaceRef { local: arg, projection: &[] }, self.0.map(), T::Value::top());
 233         }
 234     }
 235 }
 236
 237 impl<'tcx, T> Analysis<'tcx> for ValueAnalysisWrapper<T>
 238 where
 239     T: ValueAnalysis<'tcx>,
 240 {
 241     fn apply_statement_effect(
 242         &self,
 243         state: &mut Self::Domain,
 244         statement: &Statement<'tcx>,
 245         _location: Location,
 246     ) {
 247         self.0.handle_statement(statement, state);
 248     }
 249
 250     fn apply_terminator_effect(
 251         &self,
 252         state: &mut Self::Domain,
 253         terminator: &Terminator<'tcx>,
 254         _location: Location,
 255     ) {
 256         self.0.handle_terminator(terminator, state);
 257     }
 258
 259     fn apply_call_return_effect(
 260         &self,
 261         state: &mut Self::Domain,
 262         _block: BasicBlock,
 263         return_places: crate::CallReturnPlaces<'_, 'tcx>,
 264     ) {
 265         self.0.handle_call_return(return_places, state)
 266     }
 267
 268     fn apply_switch_int_edge_effects(
 269         &self,
 270         _block: BasicBlock,
 271         discr: &Operand<'tcx>,
 272         apply_edge_effects: &mut impl SwitchIntEdgeEffects<Self::Domain>,
 273     ) {
 274         self.0.handle_switch_int(discr, apply_edge_effects)
 275     }
 276 }
 277
 278 rustc_index::newtype_index!(
 279     pub struct PlaceIndex {}
 280 );
 281
 282 rustc_index::newtype_index!(
 283     struct ValueIndex {}
 284 );
 285
 286 #[derive(PartialEq, Eq, Clone, Debug)]
 287 pub struct State<V>(IndexVec<ValueIndex, V>);
 288
 289 impl<V: Clone + HasTop> State<V> {
 290     pub fn flood_all(&mut self, value: V) {
 291         self.0.raw.fill(value);
 292     }
 293
 294     pub fn flood(&mut self, place: PlaceRef<'_>, map: &Map, value: V) {
 295         if let Some(root) = map.find(place) {
 296             self.flood_idx(root, map, value);
 297         }
 298     }
 299
 300     pub fn flood_idx(&mut self, place: PlaceIndex, map: &Map, value: V) {
 301         map.preorder_invoke(place, &mut |place| {
 302             if let Some(vi) = map.places[place].value_index {
 303                 self.0[vi] = value.clone();
 304             }
 305         });
 306     }
 307
 308     pub fn assign_place_idx(&mut self, target: PlaceIndex, source: PlaceIndex, map: &Map) {
 309         if let Some(target_value) = map.places[target].value_index {
 310             if let Some(source_value) = map.places[source].value_index {
 311                 self.0[target_value] = self.0[source_value].clone();
 312             } else {
 313                 self.0[target_value] = V::top();
 314             }
 315         }
 316         for target_child in map.children(target) {
 317             // Try to find corresponding child in source.
 318             let projection = map.places[target_child].proj_elem.unwrap();
 319             if let Some(source_child) = map.projections.get(&(source, projection)) {
 320                 self.assign_place_idx(target_child, *source_child, map);
 321             } else {
 322                 self.flood_idx(target_child, map, V::top());
 323             }
 324         }
 325     }
 326
 327     pub fn assign(&mut self, target: PlaceRef<'_>, result: ValueOrPlace<V>, map: &Map) {
 328         if let Some(target) = map.find(target) {
 329             self.assign_idx(target, result, map);
 330         }
 331     }
 332
 333     pub fn assign_idx(&mut self, target: PlaceIndex, result: ValueOrPlace<V>, map: &Map) {
 334         match result {
 335             ValueOrPlace::Value(value) => {
 336                 // FIXME: What if not all tracked projections are overwritten? Can this happen?
 337                 if let Some(value_index) = map.places[target].value_index {
 338                     self.0[value_index] = value;
 339                 }
 340             }
 341             ValueOrPlace::Place(source) => self.assign_place_idx(target, source, map),
 342             ValueOrPlace::Unknown => {
 343                 self.flood_idx(target, map, V::top());
 344             }
 345         }
 346     }
 347
 348     pub fn get(&self, place: PlaceRef<'_>, map: &Map) -> V {
 349         map.find(place).map(|place| self.get_idx(place, map)).unwrap_or(V::top())
 350     }
 351
 352     pub fn get_idx(&self, place: PlaceIndex, map: &Map) -> V {
 353         map.places[place].value_index.map(|v| self.0[v].clone()).unwrap_or(V::top())
 354     }
 355 }
 356
 357 impl<V: JoinSemiLattice> JoinSemiLattice for State<V> {
 358     fn join(&mut self, other: &Self) -> bool {
 359         self.0.join(&other.0)
 360     }
 361 }
 362
 363 #[derive(Debug)]
 364 pub struct Map {
 365     locals: IndexVec<Local, Option<PlaceIndex>>,
 366     projections: FxHashMap<(PlaceIndex, ProjElem), PlaceIndex>,
 367     places: IndexVec<PlaceIndex, PlaceInfo>,
 368     value_count: usize,
 369 }
 370
 371 impl Map {
 372     pub fn new() -> Self {
 373         Self {
 374             locals: IndexVec::new(),
 375             projections: FxHashMap::default(),
 376             places: IndexVec::new(),
 377             value_count: 0,
 378         }
 379     }
 380
 381     /// Register all places with suitable types up to a certain derefence depth (to prevent cycles).
 382     pub fn register_with_filter<'tcx>(
 383         &mut self,
 384         tcx: TyCtxt<'tcx>,
 385         source: &impl HasLocalDecls<'tcx>,
 386         max_derefs: u32,
 387         mut filter: impl FnMut(Ty<'tcx>) -> bool,
 388     ) {
 389         let mut projection = Vec::new();
 390         for (local, decl) in source.local_decls().iter_enumerated() {
 391             self.register_with_filter_rec(
 392                 tcx,
 393                 max_derefs,
 394                 local,
 395                 &mut projection,
 396                 decl.ty,
 397                 &mut filter,
 398             );
 399         }
 400     }
 401
 402     fn register_with_filter_rec<'tcx>(
 403         &mut self,
 404         tcx: TyCtxt<'tcx>,
 405         max_derefs: u32,
 406         local: Local,
 407         projection: &mut Vec<PlaceElem<'tcx>>,
 408         ty: Ty<'tcx>,
 409         filter: &mut impl FnMut(Ty<'tcx>) -> bool,
 410     ) {
 411         if filter(ty) {
 412             self.register(local, projection)
 413                 .expect("projection should only contain convertible elements");
 414         }
 415         if max_derefs > 0 {
 416             if let Some(ty::TypeAndMut { ty, .. }) = ty.builtin_deref(false) {
 417                 projection.push(PlaceElem::Deref);
 418                 self.register_with_filter_rec(tcx, max_derefs - 1, local, projection, ty, filter);
 419                 projection.pop();
 420             }
 421         }
 422         iter_fields(ty, tcx, |variant, field, ty| {
 423             if let Some(variant) = variant {
 424                 projection.push(PlaceElem::Downcast(None, variant));
 425             }
 426             projection.push(PlaceElem::Field(field, ty));
 427             self.register_with_filter_rec(tcx, max_derefs, local, projection, ty, filter);
 428             projection.pop();
 429             if variant.is_some() {
 430                 projection.pop();
 431             }
 432         });
 433     }
 434
 435     pub fn register<'tcx>(
 436         &mut self,
 437         local: Local,
 438         projection: &[PlaceElem<'tcx>],
 439     ) -> Result<(), ()> {
 440         // Get the base index of the local.
 441         let mut index =
 442             *self.locals.get_or_insert_with(local, || self.places.push(PlaceInfo::new(None)));
 443
 444         // Apply the projection.
 445         for &elem in projection {
 446             let elem = elem.try_into()?;
 447             index = *self.projections.entry((index, elem)).or_insert_with(|| {
 448                 // Prepend new child to the linked list.
 449                 let next = self.places.push(PlaceInfo::new(Some(elem)));
 450                 self.places[next].next_sibling = self.places[index].first_child;
 451                 self.places[index].first_child = Some(next);
 452                 next
 453             });
 454         }
 455
 456         // Allocate a value slot if it doesn't have one.
 457         if self.places[index].value_index.is_none() {
 458             self.places[index].value_index = Some(self.value_count.into());
 459             self.value_count += 1;
 460         }
 461
 462         Ok(())
 463     }
 464
 465     pub fn apply_elem(&self, place: PlaceIndex, elem: ProjElem) -> Option<PlaceIndex> {
 466         self.projections.get(&(place, elem)).copied()
 467     }
 468
 469     pub fn find(&self, place: PlaceRef<'_>) -> Option<PlaceIndex> {
 470         let mut index = *self.locals.get(place.local)?.as_ref()?;
 471
 472         for &elem in place.projection {
 473             index = self.apply_elem(index, elem.try_into().ok()?)?;
 474         }
 475
 476         Some(index)
 477     }
 478
 479     pub fn children(&self, parent: PlaceIndex) -> impl Iterator<Item = PlaceIndex> + '_ {
 480         Children::new(self, parent)
 481     }
 482
 483     pub fn preorder_invoke(&self, root: PlaceIndex, f: &mut impl FnMut(PlaceIndex)) {
 484         f(root);
 485         for child in self.children(root) {
 486             self.preorder_invoke(child, f);
 487         }
 488     }
 489 }
 490
 491 #[derive(Debug)]
 492 struct PlaceInfo {
 493     next_sibling: Option<PlaceIndex>,
 494     first_child: Option<PlaceIndex>,
 495     /// The projection used to go from parent to this node (only None for root).
 496     proj_elem: Option<ProjElem>,
 497     value_index: Option<ValueIndex>,
 498 }
 499
 500 impl PlaceInfo {
 501     fn new(proj_elem: Option<ProjElem>) -> Self {
 502         Self { next_sibling: None, first_child: None, proj_elem, value_index: None }
 503     }
 504 }
 505
 506 struct Children<'a> {
 507     map: &'a Map,
 508     next: Option<PlaceIndex>,
 509 }
 510
 511 impl<'a> Children<'a> {
 512     fn new(map: &'a Map, parent: PlaceIndex) -> Self {
 513         Self { map, next: map.places[parent].first_child }
 514     }
 515 }
 516
 517 impl<'a> Iterator for Children<'a> {
 518     type Item = PlaceIndex;
 519
 520     fn next(&mut self) -> Option<Self::Item> {
 521         match self.next {
 522             Some(child) => {
 523                 self.next = self.map.places[child].next_sibling;
 524                 Some(child)
 525             }
 526             None => None,
 527         }
 528     }
 529 }
 530
 531 // FIXME: See if we can get rid of `Unknown`.
 532 pub enum ValueOrPlace<V> {
 533     Value(V),
 534     Place(PlaceIndex),
 535     Unknown,
 536 }
 537
 538 pub trait HasBottom {
 539     fn bottom() -> Self;
 540 }
 541
 542 pub trait HasTop {
 543     fn top() -> Self;
 544 }
 545
 546 impl<V> HasBottom for FlatSet<V> {
 547     fn bottom() -> Self {
 548         Self::Bottom
 549     }
 550 }
 551
 552 impl<V> HasTop for FlatSet<V> {
 553     fn top() -> Self {
 554         Self::Top
 555     }
 556 }
 557
 558 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
 559 pub enum ProjElem {
 560     Deref,
 561     Field(Field),
 562     Downcast(VariantIdx),
 563 }
 564
 565 impl<V, T> TryFrom<ProjectionElem<V, T>> for ProjElem {
 566     type Error = ();
 567
 568     fn try_from(value: ProjectionElem<V, T>) -> Result<Self, Self::Error> {
 569         match value {
 570             ProjectionElem::Deref => Ok(ProjElem::Deref),
 571             ProjectionElem::Field(field, _) => Ok(ProjElem::Field(field)),
 572             ProjectionElem::Downcast(_, variant) => Ok(ProjElem::Downcast(variant)),
 573             _ => Err(()),
 574         }
 575     }
 576 }
 577
 578 fn iter_fields<'tcx>(
 579     ty: Ty<'tcx>,
 580     tcx: TyCtxt<'tcx>,
 581     mut f: impl FnMut(Option<VariantIdx>, Field, Ty<'tcx>),
 582 ) {
 583     match ty.kind() {
 584         ty::Tuple(list) => {
 585             for (field, ty) in list.iter().enumerate() {
 586                 f(None, field.into(), ty);
 587             }
 588         }
 589         ty::Adt(def, substs) => {
 590             for (v_index, v_def) in def.variants().iter_enumerated() {
 591                 for (f_index, f_def) in v_def.fields.iter().enumerate() {
 592                     let field_ty = tcx.normalize_erasing_regions(
 593                         ty::ParamEnv::reveal_all(),
 594                         f_def.ty(tcx, substs),
 595                     );
 596                     f(Some(v_index), f_index.into(), field_ty);
 597                 }
 598             }
 599         }
 600         ty::Closure(_, substs) => {
 601             iter_fields(substs.as_closure().tupled_upvars_ty(), tcx, f);
 602         }
 603         _ => (),
 604     }
 605 }
 606
 607 fn debug_with_context_rec<V: Debug + Eq>(
 608     place: PlaceIndex,
 609     place_str: &str,
 610     new: &State<V>,
 611     old: Option<&State<V>>,
 612     map: &Map,
 613     f: &mut Formatter<'_>,
 614 ) -> std::fmt::Result {
 615     if let Some(value) = map.places[place].value_index {
 616         match old {
 617             None => writeln!(f, "{}: {:?}", place_str, new.0[value])?,
 618             Some(old) => {
 619                 if new.0[value] != old.0[value] {
 620                     writeln!(f, "\u{001f}-{}: {:?}", place_str, old.0[value])?;
 621                     writeln!(f, "\u{001f}+{}: {:?}", place_str, new.0[value])?;
 622                 }
 623             }
 624         }
 625     }
 626
 627     for child in map.children(place) {
 628         let info_elem = map.places[child].proj_elem.unwrap();
 629         let child_place_str = match info_elem {
 630             ProjElem::Deref => format!("*{}", place_str),
 631             ProjElem::Field(field) => {
 632                 if place_str.starts_with("*") {
 633                     format!("({}).{}", place_str, field.index())
 634                 } else {
 635                     format!("{}.{}", place_str, field.index())
 636                 }
 637             }
 638             ProjElem::Downcast(variant) => format!("({} as #{})", place_str, variant.index()),
 639         };
 640         debug_with_context_rec(child, &child_place_str, new, old, map, f)?;
 641     }
 642
 643     Ok(())
 644 }
 645
 646 fn debug_with_context<V: Debug + Eq>(
 647     new: &State<V>,
 648     old: Option<&State<V>>,
 649     map: &Map,
 650     f: &mut Formatter<'_>,
 651 ) -> std::fmt::Result {
 652     for (local, place) in map.locals.iter_enumerated() {
 653         if let Some(place) = place {
 654             debug_with_context_rec(*place, &format!("{:?}", local), new, old, map, f)?;
 655         }
 656     }
 657     Ok(())
 658 }
 659
 660 impl<'tcx, T> DebugWithContext<ValueAnalysisWrapper<T>> for State<T::Value>
 661 where
 662     T: ValueAnalysis<'tcx>,
 663     T::Value: Debug,
 664 {
 665     fn fmt_with(&self, ctxt: &ValueAnalysisWrapper<T>, f: &mut Formatter<'_>) -> std::fmt::Result {
 666         debug_with_context(self, None, ctxt.0.map(), f)
 667     }
 668
 669     fn fmt_diff_with(
 670         &self,
 671         old: &Self,
 672         ctxt: &ValueAnalysisWrapper<T>,
 673         f: &mut Formatter<'_>,
 674     ) -> std::fmt::Result {
 675         debug_with_context(self, Some(old), ctxt.0.map(), f)
 676     }
 677 }