compiler/rustc_middle/src/mir/terminator.rs

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