compiler/rustc_middle/src/mir/terminator.rs

   1 use crate::mir;
   2 use crate::mir::interpret::Scalar;
   3 use crate::ty::{self, Ty, TyCtxt};
   4 use smallvec::{smallvec, SmallVec};
   5
   6 use super::{BasicBlock, InlineAsmOperand, Operand, SourceInfo, TerminatorKind};
   7 use rustc_ast::InlineAsmTemplatePiece;
   8 pub use rustc_ast::Mutability;
   9 use rustc_macros::HashStable;
  10 use std::borrow::Cow;
  11 use std::fmt::{self, Debug, Formatter, Write};
  12 use std::iter;
  13 use std::slice;
  14
  15 pub use super::query::*;
  16
  17 #[derive(Debug, Clone, TyEncodable, TyDecodable, Hash, HashStable, PartialEq)]
  18 pub struct SwitchTargets {
  19     /// Possible values. The locations to branch to in each case
  20     /// are found in the corresponding indices from the `targets` vector.
  21     values: SmallVec<[u128; 1]>,
  22
  23     /// Possible branch sites. The last element of this vector is used
  24     /// for the otherwise branch, so targets.len() == values.len() + 1
  25     /// should hold.
  26     //
  27     // This invariant is quite non-obvious and also could be improved.
  28     // One way to make this invariant is to have something like this instead:
  29     //
  30     // branches: Vec<(ConstInt, BasicBlock)>,
  31     // otherwise: Option<BasicBlock> // exhaustive if None
  32     //
  33     // However we’ve decided to keep this as-is until we figure a case
  34     // where some other approach seems to be strictly better than other.
  35     targets: SmallVec<[BasicBlock; 2]>,
  36 }
  37
  38 impl SwitchTargets {
  39     /// Creates switch targets from an iterator of values and target blocks.
  40     ///
  41     /// The iterator may be empty, in which case the `SwitchInt` instruction is equivalent to
  42     /// `goto otherwise;`.
  43     pub fn new(targets: impl Iterator<Item = (u128, BasicBlock)>, otherwise: BasicBlock) -> Self {
  44         let (values, mut targets): (SmallVec<_>, SmallVec<_>) = targets.unzip();
  45         targets.push(otherwise);
  46         Self { values, targets }
  47     }
  48
  49     /// Builds a switch targets definition that jumps to `then` if the tested value equals `value`,
  50     /// and to `else_` if not.
  51     pub fn static_if(value: u128, then: BasicBlock, else_: BasicBlock) -> Self {
  52         Self { values: smallvec![value], targets: smallvec![then, else_] }
  53     }
  54
  55     /// Returns the fallback target that is jumped to when none of the values match the operand.
  56     pub fn otherwise(&self) -> BasicBlock {
  57         *self.targets.last().unwrap()
  58     }
  59
  60     /// Returns an iterator over the switch targets.
  61     ///
  62     /// The iterator will yield tuples containing the value and corresponding target to jump to, not
  63     /// including the `otherwise` fallback target.
  64     ///
  65     /// Note that this may yield 0 elements. Only the `otherwise` branch is mandatory.
  66     pub fn iter(&self) -> SwitchTargetsIter<'_> {
  67         SwitchTargetsIter { inner: iter::zip(&self.values, &self.targets) }
  68     }
  69
  70     /// Returns a slice with all possible jump targets (including the fallback target).
  71     pub fn all_targets(&self) -> &[BasicBlock] {
  72         &self.targets
  73     }
  74
  75     pub fn all_targets_mut(&mut self) -> &mut [BasicBlock] {
  76         &mut self.targets
  77     }
  78
  79     /// Finds the `BasicBlock` to which this `SwitchInt` will branch given the
  80     /// specific value.  This cannot fail, as it'll return the `otherwise`
  81     /// branch if there's not a specific match for the value.
  82     pub fn target_for_value(&self, value: u128) -> BasicBlock {
  83         self.iter().find_map(|(v, t)| (v == value).then_some(t)).unwrap_or_else(|| self.otherwise())
  84     }
  85 }
  86
  87 pub struct SwitchTargetsIter<'a> {
  88     inner: iter::Zip<slice::Iter<'a, u128>, slice::Iter<'a, BasicBlock>>,
  89 }
  90
  91 impl<'a> Iterator for SwitchTargetsIter<'a> {
  92     type Item = (u128, BasicBlock);
  93
  94     fn next(&mut self) -> Option<Self::Item> {
  95         self.inner.next().map(|(val, bb)| (*val, *bb))
  96     }
  97
  98     fn size_hint(&self) -> (usize, Option<usize>) {
  99         self.inner.size_hint()
 100     }
 101 }
 102
 103 impl<'a> ExactSizeIterator for SwitchTargetsIter<'a> {}
 104
 105 #[derive(Clone, Debug, TyEncodable, TyDecodable, HashStable, TypeFoldable, TypeVisitable)]
 106 pub struct Terminator<'tcx> {
 107     pub source_info: SourceInfo,
 108     pub kind: TerminatorKind<'tcx>,
 109 }
 110
 111 pub type Successors<'a> = impl Iterator<Item = BasicBlock> + 'a;
 112 pub type SuccessorsMut<'a> =
 113     iter::Chain<std::option::IntoIter<&'a mut BasicBlock>, slice::IterMut<'a, BasicBlock>>;
 114
 115 impl<'tcx> Terminator<'tcx> {
 116     pub fn successors(&self) -> Successors<'_> {
 117         self.kind.successors()
 118     }
 119
 120     pub fn successors_mut(&mut self) -> SuccessorsMut<'_> {
 121         self.kind.successors_mut()
 122     }
 123
 124     pub fn unwind(&self) -> Option<&Option<BasicBlock>> {
 125         self.kind.unwind()
 126     }
 127
 128     pub fn unwind_mut(&mut self) -> Option<&mut Option<BasicBlock>> {
 129         self.kind.unwind_mut()
 130     }
 131 }
 132
 133 impl<'tcx> TerminatorKind<'tcx> {
 134     pub fn if_(
 135         tcx: TyCtxt<'tcx>,
 136         cond: Operand<'tcx>,
 137         t: BasicBlock,
 138         f: BasicBlock,
 139     ) -> TerminatorKind<'tcx> {
 140         TerminatorKind::SwitchInt {
 141             discr: cond,
 142             switch_ty: tcx.types.bool,
 143             targets: SwitchTargets::static_if(0, f, t),
 144         }
 145     }
 146
 147     pub fn successors(&self) -> Successors<'_> {
 148         use self::TerminatorKind::*;
 149         match *self {
 150             Resume
 151             | Abort
 152             | GeneratorDrop
 153             | Return
 154             | Unreachable
 155             | Call { target: None, cleanup: None, .. }
 156             | InlineAsm { destination: None, cleanup: None, .. } => {
 157                 None.into_iter().chain((&[]).into_iter().copied())
 158             }
 159             Goto { target: t }
 160             | Call { target: None, cleanup: Some(t), .. }
 161             | Call { target: Some(t), cleanup: None, .. }
 162             | Yield { resume: t, drop: None, .. }
 163             | DropAndReplace { target: t, unwind: None, .. }
 164             | Drop { target: t, unwind: None, .. }
 165             | Assert { target: t, cleanup: None, .. }
 166             | FalseUnwind { real_target: t, unwind: None }
 167             | InlineAsm { destination: Some(t), cleanup: None, .. }
 168             | InlineAsm { destination: None, cleanup: Some(t), .. } => {
 169                 Some(t).into_iter().chain((&[]).into_iter().copied())
 170             }
 171             Call { target: Some(t), cleanup: Some(ref u), .. }
 172             | Yield { resume: t, drop: Some(ref u), .. }
 173             | DropAndReplace { target: t, unwind: Some(ref u), .. }
 174             | Drop { target: t, unwind: Some(ref u), .. }
 175             | Assert { target: t, cleanup: Some(ref u), .. }
 176             | FalseUnwind { real_target: t, unwind: Some(ref u) }
 177             | InlineAsm { destination: Some(t), cleanup: Some(ref u), .. } => {
 178                 Some(t).into_iter().chain(slice::from_ref(u).into_iter().copied())
 179             }
 180             SwitchInt { ref targets, .. } => {
 181                 None.into_iter().chain(targets.targets.iter().copied())
 182             }
 183             FalseEdge { real_target, ref imaginary_target } => Some(real_target)
 184                 .into_iter()
 185                 .chain(slice::from_ref(imaginary_target).into_iter().copied()),
 186         }
 187     }
 188
 189     pub fn successors_mut(&mut self) -> SuccessorsMut<'_> {
 190         use self::TerminatorKind::*;
 191         match *self {
 192             Resume
 193             | Abort
 194             | GeneratorDrop
 195             | Return
 196             | Unreachable
 197             | Call { target: None, cleanup: None, .. }
 198             | InlineAsm { destination: None, cleanup: None, .. } => None.into_iter().chain(&mut []),
 199             Goto { target: ref mut t }
 200             | Call { target: None, cleanup: Some(ref mut t), .. }
 201             | Call { target: Some(ref mut t), cleanup: None, .. }
 202             | Yield { resume: ref mut t, drop: None, .. }
 203             | DropAndReplace { target: ref mut t, unwind: None, .. }
 204             | Drop { target: ref mut t, unwind: None, .. }
 205             | Assert { target: ref mut t, cleanup: None, .. }
 206             | FalseUnwind { real_target: ref mut t, unwind: None }
 207             | InlineAsm { destination: Some(ref mut t), cleanup: None, .. }
 208             | InlineAsm { destination: None, cleanup: Some(ref mut t), .. } => {
 209                 Some(t).into_iter().chain(&mut [])
 210             }
 211             Call { target: Some(ref mut t), cleanup: Some(ref mut u), .. }
 212             | Yield { resume: ref mut t, drop: Some(ref mut u), .. }
 213             | DropAndReplace { target: ref mut t, unwind: Some(ref mut u), .. }
 214             | Drop { target: ref mut t, unwind: Some(ref mut u), .. }
 215             | Assert { target: ref mut t, cleanup: Some(ref mut u), .. }
 216             | FalseUnwind { real_target: ref mut t, unwind: Some(ref mut u) }
 217             | InlineAsm { destination: Some(ref mut t), cleanup: Some(ref mut u), .. } => {
 218                 Some(t).into_iter().chain(slice::from_mut(u))
 219             }
 220             SwitchInt { ref mut targets, .. } => None.into_iter().chain(&mut targets.targets),
 221             FalseEdge { ref mut real_target, ref mut imaginary_target } => {
 222                 Some(real_target).into_iter().chain(slice::from_mut(imaginary_target))
 223             }
 224         }
 225     }
 226
 227     pub fn unwind(&self) -> Option<&Option<BasicBlock>> {
 228         match *self {
 229             TerminatorKind::Goto { .. }
 230             | TerminatorKind::Resume
 231             | TerminatorKind::Abort
 232             | TerminatorKind::Return
 233             | TerminatorKind::Unreachable
 234             | TerminatorKind::GeneratorDrop
 235             | TerminatorKind::Yield { .. }
 236             | TerminatorKind::SwitchInt { .. }
 237             | TerminatorKind::FalseEdge { .. } => None,
 238             TerminatorKind::Call { cleanup: ref unwind, .. }
 239             | TerminatorKind::Assert { cleanup: ref unwind, .. }
 240             | TerminatorKind::DropAndReplace { ref unwind, .. }
 241             | TerminatorKind::Drop { ref unwind, .. }
 242             | TerminatorKind::FalseUnwind { ref unwind, .. }
 243             | TerminatorKind::InlineAsm { cleanup: ref unwind, .. } => Some(unwind),
 244         }
 245     }
 246
 247     pub fn unwind_mut(&mut self) -> Option<&mut Option<BasicBlock>> {
 248         match *self {
 249             TerminatorKind::Goto { .. }
 250             | TerminatorKind::Resume
 251             | TerminatorKind::Abort
 252             | TerminatorKind::Return
 253             | TerminatorKind::Unreachable
 254             | TerminatorKind::GeneratorDrop
 255             | TerminatorKind::Yield { .. }
 256             | TerminatorKind::SwitchInt { .. }
 257             | TerminatorKind::FalseEdge { .. } => None,
 258             TerminatorKind::Call { cleanup: ref mut unwind, .. }
 259             | TerminatorKind::Assert { cleanup: ref mut unwind, .. }
 260             | TerminatorKind::DropAndReplace { ref mut unwind, .. }
 261             | TerminatorKind::Drop { ref mut unwind, .. }
 262             | TerminatorKind::FalseUnwind { ref mut unwind, .. }
 263             | TerminatorKind::InlineAsm { cleanup: ref mut unwind, .. } => Some(unwind),
 264         }
 265     }
 266
 267     pub fn as_switch(&self) -> Option<(&Operand<'tcx>, Ty<'tcx>, &SwitchTargets)> {
 268         match self {
 269             TerminatorKind::SwitchInt { discr, switch_ty, targets } => {
 270                 Some((discr, *switch_ty, targets))
 271             }
 272             _ => None,
 273         }
 274     }
 275
 276     pub fn as_goto(&self) -> Option<BasicBlock> {
 277         match self {
 278             TerminatorKind::Goto { target } => Some(*target),
 279             _ => None,
 280         }
 281     }
 282 }
 283
 284 impl<'tcx> Debug for TerminatorKind<'tcx> {
 285     fn fmt(&self, fmt: &mut Formatter<'_>) -> fmt::Result {
 286         self.fmt_head(fmt)?;
 287         let successor_count = self.successors().count();
 288         let labels = self.fmt_successor_labels();
 289         assert_eq!(successor_count, labels.len());
 290
 291         match successor_count {
 292             0 => Ok(()),
 293
 294             1 => write!(fmt, " -> {:?}", self.successors().next().unwrap()),
 295
 296             _ => {
 297                 write!(fmt, " -> [")?;
 298                 for (i, target) in self.successors().enumerate() {
 299                     if i > 0 {
 300                         write!(fmt, ", ")?;
 301                     }
 302                     write!(fmt, "{}: {:?}", labels[i], target)?;
 303                 }
 304                 write!(fmt, "]")
 305             }
 306         }
 307     }
 308 }
 309
 310 impl<'tcx> TerminatorKind<'tcx> {
 311     /// Writes the "head" part of the terminator; that is, its name and the data it uses to pick the
 312     /// successor basic block, if any. The only information not included is the list of possible
 313     /// successors, which may be rendered differently between the text and the graphviz format.
 314     pub fn fmt_head<W: Write>(&self, fmt: &mut W) -> fmt::Result {
 315         use self::TerminatorKind::*;
 316         match self {
 317             Goto { .. } => write!(fmt, "goto"),
 318             SwitchInt { discr, .. } => write!(fmt, "switchInt({:?})", discr),
 319             Return => write!(fmt, "return"),
 320             GeneratorDrop => write!(fmt, "generator_drop"),
 321             Resume => write!(fmt, "resume"),
 322             Abort => write!(fmt, "abort"),
 323             Yield { value, resume_arg, .. } => write!(fmt, "{:?} = yield({:?})", resume_arg, value),
 324             Unreachable => write!(fmt, "unreachable"),
 325             Drop { place, .. } => write!(fmt, "drop({:?})", place),
 326             DropAndReplace { place, value, .. } => {
 327                 write!(fmt, "replace({:?} <- {:?})", place, value)
 328             }
 329             Call { func, args, destination, .. } => {
 330                 write!(fmt, "{:?} = ", destination)?;
 331                 write!(fmt, "{:?}(", func)?;
 332                 for (index, arg) in args.iter().enumerate() {
 333                     if index > 0 {
 334                         write!(fmt, ", ")?;
 335                     }
 336                     write!(fmt, "{:?}", arg)?;
 337                 }
 338                 write!(fmt, ")")
 339             }
 340             Assert { cond, expected, msg, .. } => {
 341                 write!(fmt, "assert(")?;
 342                 if !expected {
 343                     write!(fmt, "!")?;
 344                 }
 345                 write!(fmt, "{:?}, ", cond)?;
 346                 msg.fmt_assert_args(fmt)?;
 347                 write!(fmt, ")")
 348             }
 349             FalseEdge { .. } => write!(fmt, "falseEdge"),
 350             FalseUnwind { .. } => write!(fmt, "falseUnwind"),
 351             InlineAsm { template, ref operands, options, .. } => {
 352                 write!(fmt, "asm!(\"{}\"", InlineAsmTemplatePiece::to_string(template))?;
 353                 for op in operands {
 354                     write!(fmt, ", ")?;
 355                     let print_late = |&late| if late { "late" } else { "" };
 356                     match op {
 357                         InlineAsmOperand::In { reg, value } => {
 358                             write!(fmt, "in({}) {:?}", reg, value)?;
 359                         }
 360                         InlineAsmOperand::Out { reg, late, place: Some(place) } => {
 361                             write!(fmt, "{}out({}) {:?}", print_late(late), reg, place)?;
 362                         }
 363                         InlineAsmOperand::Out { reg, late, place: None } => {
 364                             write!(fmt, "{}out({}) _", print_late(late), reg)?;
 365                         }
 366                         InlineAsmOperand::InOut {
 367                             reg,
 368                             late,
 369                             in_value,
 370                             out_place: Some(out_place),
 371                         } => {
 372                             write!(
 373                                 fmt,
 374                                 "in{}out({}) {:?} => {:?}",
 375                                 print_late(late),
 376                                 reg,
 377                                 in_value,
 378                                 out_place
 379                             )?;
 380                         }
 381                         InlineAsmOperand::InOut { reg, late, in_value, out_place: None } => {
 382                             write!(fmt, "in{}out({}) {:?} => _", print_late(late), reg, in_value)?;
 383                         }
 384                         InlineAsmOperand::Const { value } => {
 385                             write!(fmt, "const {:?}", value)?;
 386                         }
 387                         InlineAsmOperand::SymFn { value } => {
 388                             write!(fmt, "sym_fn {:?}", value)?;
 389                         }
 390                         InlineAsmOperand::SymStatic { def_id } => {
 391                             write!(fmt, "sym_static {:?}", def_id)?;
 392                         }
 393                     }
 394                 }
 395                 write!(fmt, ", options({:?}))", options)
 396             }
 397         }
 398     }
 399
 400     /// Returns the list of labels for the edges to the successor basic blocks.
 401     pub fn fmt_successor_labels(&self) -> Vec<Cow<'static, str>> {
 402         use self::TerminatorKind::*;
 403         match *self {
 404             Return | Resume | Abort | Unreachable | GeneratorDrop => vec![],
 405             Goto { .. } => vec!["".into()],
 406             SwitchInt { ref targets, switch_ty, .. } => ty::tls::with(|tcx| {
 407                 let param_env = ty::ParamEnv::empty();
 408                 let switch_ty = tcx.lift(switch_ty).unwrap();
 409                 let size = tcx.layout_of(param_env.and(switch_ty)).unwrap().size;
 410                 targets
 411                     .values
 412                     .iter()
 413                     .map(|&u| {
 414                         mir::ConstantKind::from_scalar(tcx, Scalar::from_uint(u, size), switch_ty)
 415                             .to_string()
 416                             .into()
 417                     })
 418                     .chain(iter::once("otherwise".into()))
 419                     .collect()
 420             }),
 421             Call { target: Some(_), cleanup: Some(_), .. } => {
 422                 vec!["return".into(), "unwind".into()]
 423             }
 424             Call { target: Some(_), cleanup: None, .. } => vec!["return".into()],
 425             Call { target: None, cleanup: Some(_), .. } => vec!["unwind".into()],
 426             Call { target: None, cleanup: None, .. } => vec![],
 427             Yield { drop: Some(_), .. } => vec!["resume".into(), "drop".into()],
 428             Yield { drop: None, .. } => vec!["resume".into()],
 429             DropAndReplace { unwind: None, .. } | Drop { unwind: None, .. } => {
 430                 vec!["return".into()]
 431             }
 432             DropAndReplace { unwind: Some(_), .. } | Drop { unwind: Some(_), .. } => {
 433                 vec!["return".into(), "unwind".into()]
 434             }
 435             Assert { cleanup: None, .. } => vec!["".into()],
 436             Assert { .. } => vec!["success".into(), "unwind".into()],
 437             FalseEdge { .. } => vec!["real".into(), "imaginary".into()],
 438             FalseUnwind { unwind: Some(_), .. } => vec!["real".into(), "cleanup".into()],
 439             FalseUnwind { unwind: None, .. } => vec!["real".into()],
 440             InlineAsm { destination: Some(_), cleanup: Some(_), .. } => {
 441                 vec!["return".into(), "unwind".into()]
 442             }
 443             InlineAsm { destination: Some(_), cleanup: None, .. } => vec!["return".into()],
 444             InlineAsm { destination: None, cleanup: Some(_), .. } => vec!["unwind".into()],
 445             InlineAsm { destination: None, cleanup: None, .. } => vec![],
 446         }
 447     }
 448 }