compiler/rustc_middle/src/mir/terminator/mod.rs

   1 use crate::mir::interpret::Scalar;
   2 use crate::ty::{self, Ty, TyCtxt};
   3 use rustc_ast::{InlineAsmOptions, InlineAsmTemplatePiece};
   4
   5 use super::{
   6     AssertMessage, BasicBlock, InlineAsmOperand, Operand, Place, SourceInfo, Successors,
   7     SuccessorsMut,
   8 };
   9 pub use rustc_ast::Mutability;
  10 use rustc_macros::HashStable;
  11 use rustc_span::Span;
  12 use std::borrow::Cow;
  13 use std::fmt::{self, Debug, Formatter, Write};
  14 use std::iter;
  15 use std::slice;
  16
  17 pub use super::query::*;
  18
  19 #[derive(Clone, TyEncodable, TyDecodable, HashStable, PartialEq)]
  20 pub enum TerminatorKind<'tcx> {
  21     /// Block should have one successor in the graph; we jump there.
  22     Goto { target: BasicBlock },
  23
  24     /// Operand evaluates to an integer; jump depending on its value
  25     /// to one of the targets, and otherwise fallback to `otherwise`.
  26     SwitchInt {
  27         /// The discriminant value being tested.
  28         discr: Operand<'tcx>,
  29
  30         /// The type of value being tested.
  31         /// This is always the same as the type of `discr`.
  32         /// FIXME: remove this redundant information. Currently, it is relied on by pretty-printing.
  33         switch_ty: Ty<'tcx>,
  34
  35         /// Possible values. The locations to branch to in each case
  36         /// are found in the corresponding indices from the `targets` vector.
  37         values: Cow<'tcx, [u128]>,
  38
  39         /// Possible branch sites. The last element of this vector is used
  40         /// for the otherwise branch, so targets.len() == values.len() + 1
  41         /// should hold.
  42         //
  43         // This invariant is quite non-obvious and also could be improved.
  44         // One way to make this invariant is to have something like this instead:
  45         //
  46         // branches: Vec<(ConstInt, BasicBlock)>,
  47         // otherwise: Option<BasicBlock> // exhaustive if None
  48         //
  49         // However we’ve decided to keep this as-is until we figure a case
  50         // where some other approach seems to be strictly better than other.
  51         targets: Vec<BasicBlock>,
  52     },
  53
  54     /// Indicates that the landing pad is finished and unwinding should
  55     /// continue. Emitted by `build::scope::diverge_cleanup`.
  56     Resume,
  57
  58     /// Indicates that the landing pad is finished and that the process
  59     /// should abort. Used to prevent unwinding for foreign items.
  60     Abort,
  61
  62     /// Indicates a normal return. The return place should have
  63     /// been filled in before this executes. This can occur multiple times
  64     /// in different basic blocks.
  65     Return,
  66
  67     /// Indicates a terminator that can never be reached.
  68     Unreachable,
  69
  70     /// Drop the `Place`.
  71     Drop { place: Place<'tcx>, target: BasicBlock, unwind: Option<BasicBlock> },
  72
  73     /// Drop the `Place` and assign the new value over it. This ensures
  74     /// that the assignment to `P` occurs *even if* the destructor for
  75     /// place unwinds. Its semantics are best explained by the
  76     /// elaboration:
  77     ///
  78     /// ```
  79     /// BB0 {
  80     ///   DropAndReplace(P <- V, goto BB1, unwind BB2)
  81     /// }
  82     /// ```
  83     ///
  84     /// becomes
  85     ///
  86     /// ```
  87     /// BB0 {
  88     ///   Drop(P, goto BB1, unwind BB2)
  89     /// }
  90     /// BB1 {
  91     ///   // P is now uninitialized
  92     ///   P <- V
  93     /// }
  94     /// BB2 {
  95     ///   // P is now uninitialized -- its dtor panicked
  96     ///   P <- V
  97     /// }
  98     /// ```
  99     ///
 100     /// Note that DropAndReplace is eliminated as part of the `ElaborateDrops` pass.
 101     DropAndReplace {
 102         place: Place<'tcx>,
 103         value: Operand<'tcx>,
 104         target: BasicBlock,
 105         unwind: Option<BasicBlock>,
 106     },
 107
 108     /// Block ends with a call of a function.
 109     Call {
 110         /// The function that’s being called.
 111         func: Operand<'tcx>,
 112         /// Arguments the function is called with.
 113         /// These are owned by the callee, which is free to modify them.
 114         /// This allows the memory occupied by "by-value" arguments to be
 115         /// reused across function calls without duplicating the contents.
 116         args: Vec<Operand<'tcx>>,
 117         /// Destination for the return value. If some, the call is converging.
 118         destination: Option<(Place<'tcx>, BasicBlock)>,
 119         /// Cleanups to be done if the call unwinds.
 120         cleanup: Option<BasicBlock>,
 121         /// `true` if this is from a call in HIR rather than from an overloaded
 122         /// operator. True for overloaded function call.
 123         from_hir_call: bool,
 124         /// This `Span` is the span of the function, without the dot and receiver
 125         /// (e.g. `foo(a, b)` in `x.foo(a, b)`
 126         fn_span: Span,
 127     },
 128
 129     /// Jump to the target if the condition has the expected value,
 130     /// otherwise panic with a message and a cleanup target.
 131     Assert {
 132         cond: Operand<'tcx>,
 133         expected: bool,
 134         msg: AssertMessage<'tcx>,
 135         target: BasicBlock,
 136         cleanup: Option<BasicBlock>,
 137     },
 138
 139     /// A suspend point.
 140     Yield {
 141         /// The value to return.
 142         value: Operand<'tcx>,
 143         /// Where to resume to.
 144         resume: BasicBlock,
 145         /// The place to store the resume argument in.
 146         resume_arg: Place<'tcx>,
 147         /// Cleanup to be done if the generator is dropped at this suspend point.
 148         drop: Option<BasicBlock>,
 149     },
 150
 151     /// Indicates the end of the dropping of a generator.
 152     GeneratorDrop,
 153
 154     /// A block where control flow only ever takes one real path, but borrowck
 155     /// needs to be more conservative.
 156     FalseEdge {
 157         /// The target normal control flow will take.
 158         real_target: BasicBlock,
 159         /// A block control flow could conceptually jump to, but won't in
 160         /// practice.
 161         imaginary_target: BasicBlock,
 162     },
 163     /// A terminator for blocks that only take one path in reality, but where we
 164     /// reserve the right to unwind in borrowck, even if it won't happen in practice.
 165     /// This can arise in infinite loops with no function calls for example.
 166     FalseUnwind {
 167         /// The target normal control flow will take.
 168         real_target: BasicBlock,
 169         /// The imaginary cleanup block link. This particular path will never be taken
 170         /// in practice, but in order to avoid fragility we want to always
 171         /// consider it in borrowck. We don't want to accept programs which
 172         /// pass borrowck only when `panic=abort` or some assertions are disabled
 173         /// due to release vs. debug mode builds. This needs to be an `Option` because
 174         /// of the `remove_noop_landing_pads` and `no_landing_pads` passes.
 175         unwind: Option<BasicBlock>,
 176     },
 177
 178     /// Block ends with an inline assembly block. This is a terminator since
 179     /// inline assembly is allowed to diverge.
 180     InlineAsm {
 181         /// The template for the inline assembly, with placeholders.
 182         template: &'tcx [InlineAsmTemplatePiece],
 183
 184         /// The operands for the inline assembly, as `Operand`s or `Place`s.
 185         operands: Vec<InlineAsmOperand<'tcx>>,
 186
 187         /// Miscellaneous options for the inline assembly.
 188         options: InlineAsmOptions,
 189
 190         /// Source spans for each line of the inline assembly code. These are
 191         /// used to map assembler errors back to the line in the source code.
 192         line_spans: &'tcx [Span],
 193
 194         /// Destination block after the inline assembly returns, unless it is
 195         /// diverging (InlineAsmOptions::NORETURN).
 196         destination: Option<BasicBlock>,
 197     },
 198 }
 199 #[derive(Clone, Debug, TyEncodable, TyDecodable, HashStable)]
 200 pub struct Terminator<'tcx> {
 201     pub source_info: SourceInfo,
 202     pub kind: TerminatorKind<'tcx>,
 203 }
 204
 205 impl<'tcx> Terminator<'tcx> {
 206     pub fn successors(&self) -> Successors<'_> {
 207         self.kind.successors()
 208     }
 209
 210     pub fn successors_mut(&mut self) -> SuccessorsMut<'_> {
 211         self.kind.successors_mut()
 212     }
 213
 214     pub fn unwind(&self) -> Option<&Option<BasicBlock>> {
 215         self.kind.unwind()
 216     }
 217
 218     pub fn unwind_mut(&mut self) -> Option<&mut Option<BasicBlock>> {
 219         self.kind.unwind_mut()
 220     }
 221 }
 222
 223 impl<'tcx> TerminatorKind<'tcx> {
 224     pub fn if_(
 225         tcx: TyCtxt<'tcx>,
 226         cond: Operand<'tcx>,
 227         t: BasicBlock,
 228         f: BasicBlock,
 229     ) -> TerminatorKind<'tcx> {
 230         static BOOL_SWITCH_FALSE: &[u128] = &[0];
 231         TerminatorKind::SwitchInt {
 232             discr: cond,
 233             switch_ty: tcx.types.bool,
 234             values: From::from(BOOL_SWITCH_FALSE),
 235             targets: vec![f, t],
 236         }
 237     }
 238
 239     pub fn successors(&self) -> Successors<'_> {
 240         use self::TerminatorKind::*;
 241         match *self {
 242             Resume
 243             | Abort
 244             | GeneratorDrop
 245             | Return
 246             | Unreachable
 247             | Call { destination: None, cleanup: None, .. }
 248             | InlineAsm { destination: None, .. } => None.into_iter().chain(&[]),
 249             Goto { target: ref t }
 250             | Call { destination: None, cleanup: Some(ref t), .. }
 251             | Call { destination: Some((_, ref t)), cleanup: None, .. }
 252             | Yield { resume: ref t, drop: None, .. }
 253             | DropAndReplace { target: ref t, unwind: None, .. }
 254             | Drop { target: ref t, unwind: None, .. }
 255             | Assert { target: ref t, cleanup: None, .. }
 256             | FalseUnwind { real_target: ref t, unwind: None }
 257             | InlineAsm { destination: Some(ref t), .. } => Some(t).into_iter().chain(&[]),
 258             Call { destination: Some((_, ref t)), cleanup: Some(ref u), .. }
 259             | Yield { resume: ref t, drop: Some(ref u), .. }
 260             | DropAndReplace { target: ref t, unwind: Some(ref u), .. }
 261             | Drop { target: ref t, unwind: Some(ref u), .. }
 262             | Assert { target: ref t, cleanup: Some(ref u), .. }
 263             | FalseUnwind { real_target: ref t, unwind: Some(ref u) } => {
 264                 Some(t).into_iter().chain(slice::from_ref(u))
 265             }
 266             SwitchInt { ref targets, .. } => None.into_iter().chain(&targets[..]),
 267             FalseEdge { ref real_target, ref imaginary_target } => {
 268                 Some(real_target).into_iter().chain(slice::from_ref(imaginary_target))
 269             }
 270         }
 271     }
 272
 273     pub fn successors_mut(&mut self) -> SuccessorsMut<'_> {
 274         use self::TerminatorKind::*;
 275         match *self {
 276             Resume
 277             | Abort
 278             | GeneratorDrop
 279             | Return
 280             | Unreachable
 281             | Call { destination: None, cleanup: None, .. }
 282             | InlineAsm { destination: None, .. } => None.into_iter().chain(&mut []),
 283             Goto { target: ref mut t }
 284             | Call { destination: None, cleanup: Some(ref mut t), .. }
 285             | Call { destination: Some((_, ref mut t)), cleanup: None, .. }
 286             | Yield { resume: ref mut t, drop: None, .. }
 287             | DropAndReplace { target: ref mut t, unwind: None, .. }
 288             | Drop { target: ref mut t, unwind: None, .. }
 289             | Assert { target: ref mut t, cleanup: None, .. }
 290             | FalseUnwind { real_target: ref mut t, unwind: None }
 291             | InlineAsm { destination: Some(ref mut t), .. } => Some(t).into_iter().chain(&mut []),
 292             Call { destination: Some((_, ref mut t)), cleanup: Some(ref mut u), .. }
 293             | Yield { resume: ref mut t, drop: Some(ref mut u), .. }
 294             | DropAndReplace { target: ref mut t, unwind: Some(ref mut u), .. }
 295             | Drop { target: ref mut t, unwind: Some(ref mut u), .. }
 296             | Assert { target: ref mut t, cleanup: Some(ref mut u), .. }
 297             | FalseUnwind { real_target: ref mut t, unwind: Some(ref mut u) } => {
 298                 Some(t).into_iter().chain(slice::from_mut(u))
 299             }
 300             SwitchInt { ref mut targets, .. } => None.into_iter().chain(&mut targets[..]),
 301             FalseEdge { ref mut real_target, ref mut imaginary_target } => {
 302                 Some(real_target).into_iter().chain(slice::from_mut(imaginary_target))
 303             }
 304         }
 305     }
 306
 307     pub fn unwind(&self) -> Option<&Option<BasicBlock>> {
 308         match *self {
 309             TerminatorKind::Goto { .. }
 310             | TerminatorKind::Resume
 311             | TerminatorKind::Abort
 312             | TerminatorKind::Return
 313             | TerminatorKind::Unreachable
 314             | TerminatorKind::GeneratorDrop
 315             | TerminatorKind::Yield { .. }
 316             | TerminatorKind::SwitchInt { .. }
 317             | TerminatorKind::FalseEdge { .. }
 318             | TerminatorKind::InlineAsm { .. } => None,
 319             TerminatorKind::Call { cleanup: ref unwind, .. }
 320             | TerminatorKind::Assert { cleanup: ref unwind, .. }
 321             | TerminatorKind::DropAndReplace { ref unwind, .. }
 322             | TerminatorKind::Drop { ref unwind, .. }
 323             | TerminatorKind::FalseUnwind { ref unwind, .. } => Some(unwind),
 324         }
 325     }
 326
 327     pub fn unwind_mut(&mut self) -> Option<&mut Option<BasicBlock>> {
 328         match *self {
 329             TerminatorKind::Goto { .. }
 330             | TerminatorKind::Resume
 331             | TerminatorKind::Abort
 332             | TerminatorKind::Return
 333             | TerminatorKind::Unreachable
 334             | TerminatorKind::GeneratorDrop
 335             | TerminatorKind::Yield { .. }
 336             | TerminatorKind::SwitchInt { .. }
 337             | TerminatorKind::FalseEdge { .. }
 338             | TerminatorKind::InlineAsm { .. } => None,
 339             TerminatorKind::Call { cleanup: ref mut unwind, .. }
 340             | TerminatorKind::Assert { cleanup: ref mut unwind, .. }
 341             | TerminatorKind::DropAndReplace { ref mut unwind, .. }
 342             | TerminatorKind::Drop { ref mut unwind, .. }
 343             | TerminatorKind::FalseUnwind { ref mut unwind, .. } => Some(unwind),
 344         }
 345     }
 346 }
 347
 348 impl<'tcx> Debug for TerminatorKind<'tcx> {
 349     fn fmt(&self, fmt: &mut Formatter<'_>) -> fmt::Result {
 350         self.fmt_head(fmt)?;
 351         let successor_count = self.successors().count();
 352         let labels = self.fmt_successor_labels();
 353         assert_eq!(successor_count, labels.len());
 354
 355         match successor_count {
 356             0 => Ok(()),
 357
 358             1 => write!(fmt, " -> {:?}", self.successors().next().unwrap()),
 359
 360             _ => {
 361                 write!(fmt, " -> [")?;
 362                 for (i, target) in self.successors().enumerate() {
 363                     if i > 0 {
 364                         write!(fmt, ", ")?;
 365                     }
 366                     write!(fmt, "{}: {:?}", labels[i], target)?;
 367                 }
 368                 write!(fmt, "]")
 369             }
 370         }
 371     }
 372 }
 373
 374 impl<'tcx> TerminatorKind<'tcx> {
 375     /// Writes the "head" part of the terminator; that is, its name and the data it uses to pick the
 376     /// successor basic block, if any. The only information not included is the list of possible
 377     /// successors, which may be rendered differently between the text and the graphviz format.
 378     pub fn fmt_head<W: Write>(&self, fmt: &mut W) -> fmt::Result {
 379         use self::TerminatorKind::*;
 380         match self {
 381             Goto { .. } => write!(fmt, "goto"),
 382             SwitchInt { discr, .. } => write!(fmt, "switchInt({:?})", discr),
 383             Return => write!(fmt, "return"),
 384             GeneratorDrop => write!(fmt, "generator_drop"),
 385             Resume => write!(fmt, "resume"),
 386             Abort => write!(fmt, "abort"),
 387             Yield { value, resume_arg, .. } => write!(fmt, "{:?} = yield({:?})", resume_arg, value),
 388             Unreachable => write!(fmt, "unreachable"),
 389             Drop { place, .. } => write!(fmt, "drop({:?})", place),
 390             DropAndReplace { place, value, .. } => {
 391                 write!(fmt, "replace({:?} <- {:?})", place, value)
 392             }
 393             Call { func, args, destination, .. } => {
 394                 if let Some((destination, _)) = destination {
 395                     write!(fmt, "{:?} = ", destination)?;
 396                 }
 397                 write!(fmt, "{:?}(", func)?;
 398                 for (index, arg) in args.iter().enumerate() {
 399                     if index > 0 {
 400                         write!(fmt, ", ")?;
 401                     }
 402                     write!(fmt, "{:?}", arg)?;
 403                 }
 404                 write!(fmt, ")")
 405             }
 406             Assert { cond, expected, msg, .. } => {
 407                 write!(fmt, "assert(")?;
 408                 if !expected {
 409                     write!(fmt, "!")?;
 410                 }
 411                 write!(fmt, "{:?}, ", cond)?;
 412                 msg.fmt_assert_args(fmt)?;
 413                 write!(fmt, ")")
 414             }
 415             FalseEdge { .. } => write!(fmt, "falseEdge"),
 416             FalseUnwind { .. } => write!(fmt, "falseUnwind"),
 417             InlineAsm { template, ref operands, options, .. } => {
 418                 write!(fmt, "asm!(\"{}\"", InlineAsmTemplatePiece::to_string(template))?;
 419                 for op in operands {
 420                     write!(fmt, ", ")?;
 421                     let print_late = |&late| if late { "late" } else { "" };
 422                     match op {
 423                         InlineAsmOperand::In { reg, value } => {
 424                             write!(fmt, "in({}) {:?}", reg, value)?;
 425                         }
 426                         InlineAsmOperand::Out { reg, late, place: Some(place) } => {
 427                             write!(fmt, "{}out({}) {:?}", print_late(late), reg, place)?;
 428                         }
 429                         InlineAsmOperand::Out { reg, late, place: None } => {
 430                             write!(fmt, "{}out({}) _", print_late(late), reg)?;
 431                         }
 432                         InlineAsmOperand::InOut {
 433                             reg,
 434                             late,
 435                             in_value,
 436                             out_place: Some(out_place),
 437                         } => {
 438                             write!(
 439                                 fmt,
 440                                 "in{}out({}) {:?} => {:?}",
 441                                 print_late(late),
 442                                 reg,
 443                                 in_value,
 444                                 out_place
 445                             )?;
 446                         }
 447                         InlineAsmOperand::InOut { reg, late, in_value, out_place: None } => {
 448                             write!(fmt, "in{}out({}) {:?} => _", print_late(late), reg, in_value)?;
 449                         }
 450                         InlineAsmOperand::Const { value } => {
 451                             write!(fmt, "const {:?}", value)?;
 452                         }
 453                         InlineAsmOperand::SymFn { value } => {
 454                             write!(fmt, "sym_fn {:?}", value)?;
 455                         }
 456                         InlineAsmOperand::SymStatic { def_id } => {
 457                             write!(fmt, "sym_static {:?}", def_id)?;
 458                         }
 459                     }
 460                 }
 461                 write!(fmt, ", options({:?}))", options)
 462             }
 463         }
 464     }
 465
 466     /// Returns the list of labels for the edges to the successor basic blocks.
 467     pub fn fmt_successor_labels(&self) -> Vec<Cow<'static, str>> {
 468         use self::TerminatorKind::*;
 469         match *self {
 470             Return | Resume | Abort | Unreachable | GeneratorDrop => vec![],
 471             Goto { .. } => vec!["".into()],
 472             SwitchInt { ref values, switch_ty, .. } => ty::tls::with(|tcx| {
 473                 let param_env = ty::ParamEnv::empty();
 474                 let switch_ty = tcx.lift(&switch_ty).unwrap();
 475                 let size = tcx.layout_of(param_env.and(switch_ty)).unwrap().size;
 476                 values
 477                     .iter()
 478                     .map(|&u| {
 479                         ty::Const::from_scalar(tcx, Scalar::from_uint(u, size), switch_ty)
 480                             .to_string()
 481                             .into()
 482                     })
 483                     .chain(iter::once("otherwise".into()))
 484                     .collect()
 485             }),
 486             Call { destination: Some(_), cleanup: Some(_), .. } => {
 487                 vec!["return".into(), "unwind".into()]
 488             }
 489             Call { destination: Some(_), cleanup: None, .. } => vec!["return".into()],
 490             Call { destination: None, cleanup: Some(_), .. } => vec!["unwind".into()],
 491             Call { destination: None, cleanup: None, .. } => vec![],
 492             Yield { drop: Some(_), .. } => vec!["resume".into(), "drop".into()],
 493             Yield { drop: None, .. } => vec!["resume".into()],
 494             DropAndReplace { unwind: None, .. } | Drop { unwind: None, .. } => {
 495                 vec!["return".into()]
 496             }
 497             DropAndReplace { unwind: Some(_), .. } | Drop { unwind: Some(_), .. } => {
 498                 vec!["return".into(), "unwind".into()]
 499             }
 500             Assert { cleanup: None, .. } => vec!["".into()],
 501             Assert { .. } => vec!["success".into(), "unwind".into()],
 502             FalseEdge { .. } => vec!["real".into(), "imaginary".into()],
 503             FalseUnwind { unwind: Some(_), .. } => vec!["real".into(), "cleanup".into()],
 504             FalseUnwind { unwind: None, .. } => vec!["real".into()],
 505             InlineAsm { destination: Some(_), .. } => vec!["".into()],
 506             InlineAsm { destination: None, .. } => vec![],
 507         }
 508     }
 509 }