src/librustc_middle/mir/terminator/mod.rs

   1 use crate::mir::interpret::Scalar;
   2 use crate::ty::{self, Ty, TyCtxt};
   3 use rustc_ast::ast::{InlineAsmOptions, InlineAsmTemplatePiece};
   4
   5 use super::{
   6     AssertMessage, BasicBlock, InlineAsmOperand, Operand, Place, SourceInfo, Successors,
   7     SuccessorsMut,
   8 };
   9 pub use rustc_ast::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, RustcEncodable, RustcDecodable, 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     DropAndReplace {
 100         place: Place<'tcx>,
 101         value: Operand<'tcx>,
 102         target: BasicBlock,
 103         unwind: Option<BasicBlock>,
 104     },
 105
 106     /// Block ends with a call of a converging function.
 107     Call {
 108         /// The function that’s being called.
 109         func: Operand<'tcx>,
 110         /// Arguments the function is called with.
 111         /// These are owned by the callee, which is free to modify them.
 112         /// This allows the memory occupied by "by-value" arguments to be
 113         /// reused across function calls without duplicating the contents.
 114         args: Vec<Operand<'tcx>>,
 115         /// Destination for the return value. If some, the call is converging.
 116         destination: Option<(Place<'tcx>, BasicBlock)>,
 117         /// Cleanups to be done if the call unwinds.
 118         cleanup: Option<BasicBlock>,
 119         /// `true` if this is from a call in HIR rather than from an overloaded
 120         /// operator. True for overloaded function call.
 121         from_hir_call: bool,
 122         /// This `Span` is the span of the function, without the dot and receiver
 123         /// (e.g. `foo(a, b)` in `x.foo(a, b)`
 124         fn_span: Span,
 125     },
 126
 127     /// Jump to the target if the condition has the expected value,
 128     /// otherwise panic with a message and a cleanup target.
 129     Assert {
 130         cond: Operand<'tcx>,
 131         expected: bool,
 132         msg: AssertMessage<'tcx>,
 133         target: BasicBlock,
 134         cleanup: Option<BasicBlock>,
 135     },
 136
 137     /// A suspend point.
 138     Yield {
 139         /// The value to return.
 140         value: Operand<'tcx>,
 141         /// Where to resume to.
 142         resume: BasicBlock,
 143         /// The place to store the resume argument in.
 144         resume_arg: Place<'tcx>,
 145         /// Cleanup to be done if the generator is dropped at this suspend point.
 146         drop: Option<BasicBlock>,
 147     },
 148
 149     /// Indicates the end of the dropping of a generator.
 150     GeneratorDrop,
 151
 152     /// A block where control flow only ever takes one real path, but borrowck
 153     /// needs to be more conservative.
 154     FalseEdge {
 155         /// The target normal control flow will take.
 156         real_target: BasicBlock,
 157         /// A block control flow could conceptually jump to, but won't in
 158         /// practice.
 159         imaginary_target: BasicBlock,
 160     },
 161     /// A terminator for blocks that only take one path in reality, but where we
 162     /// reserve the right to unwind in borrowck, even if it won't happen in practice.
 163     /// This can arise in infinite loops with no function calls for example.
 164     FalseUnwind {
 165         /// The target normal control flow will take.
 166         real_target: BasicBlock,
 167         /// The imaginary cleanup block link. This particular path will never be taken
 168         /// in practice, but in order to avoid fragility we want to always
 169         /// consider it in borrowck. We don't want to accept programs which
 170         /// pass borrowck only when `panic=abort` or some assertions are disabled
 171         /// due to release vs. debug mode builds. This needs to be an `Option` because
 172         /// of the `remove_noop_landing_pads` and `no_landing_pads` passes.
 173         unwind: Option<BasicBlock>,
 174     },
 175
 176     /// Block ends with an inline assembly block. This is a terminator since
 177     /// inline assembly is allowed to diverge.
 178     InlineAsm {
 179         /// The template for the inline assembly, with placeholders.
 180         template: &'tcx [InlineAsmTemplatePiece],
 181
 182         /// The operands for the inline assembly, as `Operand`s or `Place`s.
 183         operands: Vec<InlineAsmOperand<'tcx>>,
 184
 185         /// Miscellaneous options for the inline assembly.
 186         options: InlineAsmOptions,
 187
 188         /// Source spans for each line of the inline assembly code. These are
 189         /// used to map assembler errors back to the line in the source code.
 190         line_spans: &'tcx [Span],
 191
 192         /// Destination block after the inline assembly returns, unless it is
 193         /// diverging (InlineAsmOptions::NORETURN).
 194         destination: Option<BasicBlock>,
 195     },
 196 }
 197 #[derive(Clone, Debug, RustcEncodable, RustcDecodable, HashStable)]
 198 pub struct Terminator<'tcx> {
 199     pub source_info: SourceInfo,
 200     pub kind: TerminatorKind<'tcx>,
 201 }
 202
 203 impl<'tcx> Terminator<'tcx> {
 204     pub fn successors(&self) -> Successors<'_> {
 205         self.kind.successors()
 206     }
 207
 208     pub fn successors_mut(&mut self) -> SuccessorsMut<'_> {
 209         self.kind.successors_mut()
 210     }
 211
 212     pub fn unwind(&self) -> Option<&Option<BasicBlock>> {
 213         self.kind.unwind()
 214     }
 215
 216     pub fn unwind_mut(&mut self) -> Option<&mut Option<BasicBlock>> {
 217         self.kind.unwind_mut()
 218     }
 219 }
 220
 221 impl<'tcx> TerminatorKind<'tcx> {
 222     pub fn if_(
 223         tcx: TyCtxt<'tcx>,
 224         cond: Operand<'tcx>,
 225         t: BasicBlock,
 226         f: BasicBlock,
 227     ) -> TerminatorKind<'tcx> {
 228         static BOOL_SWITCH_FALSE: &[u128] = &[0];
 229         TerminatorKind::SwitchInt {
 230             discr: cond,
 231             switch_ty: tcx.types.bool,
 232             values: From::from(BOOL_SWITCH_FALSE),
 233             targets: vec![f, t],
 234         }
 235     }
 236
 237     pub fn successors(&self) -> Successors<'_> {
 238         use self::TerminatorKind::*;
 239         match *self {
 240             Resume
 241             | Abort
 242             | GeneratorDrop
 243             | Return
 244             | Unreachable
 245             | Call { destination: None, cleanup: None, .. }
 246             | InlineAsm { destination: None, .. } => None.into_iter().chain(&[]),
 247             Goto { target: ref t }
 248             | Call { destination: None, cleanup: Some(ref t), .. }
 249             | Call { destination: Some((_, ref t)), cleanup: None, .. }
 250             | Yield { resume: ref t, drop: None, .. }
 251             | DropAndReplace { target: ref t, unwind: None, .. }
 252             | Drop { target: ref t, unwind: None, .. }
 253             | Assert { target: ref t, cleanup: None, .. }
 254             | FalseUnwind { real_target: ref t, unwind: None }
 255             | InlineAsm { destination: Some(ref t), .. } => Some(t).into_iter().chain(&[]),
 256             Call { destination: Some((_, ref t)), cleanup: Some(ref u), .. }
 257             | Yield { resume: ref t, drop: Some(ref u), .. }
 258             | DropAndReplace { target: ref t, unwind: Some(ref u), .. }
 259             | Drop { target: ref t, unwind: Some(ref u), .. }
 260             | Assert { target: ref t, cleanup: Some(ref u), .. }
 261             | FalseUnwind { real_target: ref t, unwind: Some(ref u) } => {
 262                 Some(t).into_iter().chain(slice::from_ref(u))
 263             }
 264             SwitchInt { ref targets, .. } => None.into_iter().chain(&targets[..]),
 265             FalseEdge { ref real_target, ref imaginary_target } => {
 266                 Some(real_target).into_iter().chain(slice::from_ref(imaginary_target))
 267             }
 268         }
 269     }
 270
 271     pub fn successors_mut(&mut self) -> SuccessorsMut<'_> {
 272         use self::TerminatorKind::*;
 273         match *self {
 274             Resume
 275             | Abort
 276             | GeneratorDrop
 277             | Return
 278             | Unreachable
 279             | Call { destination: None, cleanup: None, .. }
 280             | InlineAsm { destination: None, .. } => None.into_iter().chain(&mut []),
 281             Goto { target: ref mut t }
 282             | Call { destination: None, cleanup: Some(ref mut t), .. }
 283             | Call { destination: Some((_, ref mut t)), cleanup: None, .. }
 284             | Yield { resume: ref mut t, drop: None, .. }
 285             | DropAndReplace { target: ref mut t, unwind: None, .. }
 286             | Drop { target: ref mut t, unwind: None, .. }
 287             | Assert { target: ref mut t, cleanup: None, .. }
 288             | FalseUnwind { real_target: ref mut t, unwind: None }
 289             | InlineAsm { destination: Some(ref mut t), .. } => Some(t).into_iter().chain(&mut []),
 290             Call { destination: Some((_, ref mut t)), cleanup: Some(ref mut u), .. }
 291             | Yield { resume: ref mut t, drop: Some(ref mut u), .. }
 292             | DropAndReplace { target: ref mut t, unwind: Some(ref mut u), .. }
 293             | Drop { target: ref mut t, unwind: Some(ref mut u), .. }
 294             | Assert { target: ref mut t, cleanup: Some(ref mut u), .. }
 295             | FalseUnwind { real_target: ref mut t, unwind: Some(ref mut u) } => {
 296                 Some(t).into_iter().chain(slice::from_mut(u))
 297             }
 298             SwitchInt { ref mut targets, .. } => None.into_iter().chain(&mut targets[..]),
 299             FalseEdge { ref mut real_target, ref mut imaginary_target } => {
 300                 Some(real_target).into_iter().chain(slice::from_mut(imaginary_target))
 301             }
 302         }
 303     }
 304
 305     pub fn unwind(&self) -> Option<&Option<BasicBlock>> {
 306         match *self {
 307             TerminatorKind::Goto { .. }
 308             | TerminatorKind::Resume
 309             | TerminatorKind::Abort
 310             | TerminatorKind::Return
 311             | TerminatorKind::Unreachable
 312             | TerminatorKind::GeneratorDrop
 313             | TerminatorKind::Yield { .. }
 314             | TerminatorKind::SwitchInt { .. }
 315             | TerminatorKind::FalseEdge { .. }
 316             | TerminatorKind::InlineAsm { .. } => None,
 317             TerminatorKind::Call { cleanup: ref unwind, .. }
 318             | TerminatorKind::Assert { cleanup: ref unwind, .. }
 319             | TerminatorKind::DropAndReplace { ref unwind, .. }
 320             | TerminatorKind::Drop { ref unwind, .. }
 321             | TerminatorKind::FalseUnwind { ref unwind, .. } => Some(unwind),
 322         }
 323     }
 324
 325     pub fn unwind_mut(&mut self) -> Option<&mut Option<BasicBlock>> {
 326         match *self {
 327             TerminatorKind::Goto { .. }
 328             | TerminatorKind::Resume
 329             | TerminatorKind::Abort
 330             | TerminatorKind::Return
 331             | TerminatorKind::Unreachable
 332             | TerminatorKind::GeneratorDrop
 333             | TerminatorKind::Yield { .. }
 334             | TerminatorKind::SwitchInt { .. }
 335             | TerminatorKind::FalseEdge { .. }
 336             | TerminatorKind::InlineAsm { .. } => None,
 337             TerminatorKind::Call { cleanup: ref mut unwind, .. }
 338             | TerminatorKind::Assert { cleanup: ref mut unwind, .. }
 339             | TerminatorKind::DropAndReplace { ref mut unwind, .. }
 340             | TerminatorKind::Drop { ref mut unwind, .. }
 341             | TerminatorKind::FalseUnwind { ref mut unwind, .. } => Some(unwind),
 342         }
 343     }
 344 }
 345
 346 impl<'tcx> Debug for TerminatorKind<'tcx> {
 347     fn fmt(&self, fmt: &mut Formatter<'_>) -> fmt::Result {
 348         self.fmt_head(fmt)?;
 349         let successor_count = self.successors().count();
 350         let labels = self.fmt_successor_labels();
 351         assert_eq!(successor_count, labels.len());
 352
 353         match successor_count {
 354             0 => Ok(()),
 355
 356             1 => write!(fmt, " -> {:?}", self.successors().next().unwrap()),
 357
 358             _ => {
 359                 write!(fmt, " -> [")?;
 360                 for (i, target) in self.successors().enumerate() {
 361                     if i > 0 {
 362                         write!(fmt, ", ")?;
 363                     }
 364                     write!(fmt, "{}: {:?}", labels[i], target)?;
 365                 }
 366                 write!(fmt, "]")
 367             }
 368         }
 369     }
 370 }
 371
 372 impl<'tcx> TerminatorKind<'tcx> {
 373     /// Writes the "head" part of the terminator; that is, its name and the data it uses to pick the
 374     /// successor basic block, if any. The only information not included is the list of possible
 375     /// successors, which may be rendered differently between the text and the graphviz format.
 376     pub fn fmt_head<W: Write>(&self, fmt: &mut W) -> fmt::Result {
 377         use self::TerminatorKind::*;
 378         match self {
 379             Goto { .. } => write!(fmt, "goto"),
 380             SwitchInt { discr, .. } => write!(fmt, "switchInt({:?})", discr),
 381             Return => write!(fmt, "return"),
 382             GeneratorDrop => write!(fmt, "generator_drop"),
 383             Resume => write!(fmt, "resume"),
 384             Abort => write!(fmt, "abort"),
 385             Yield { value, resume_arg, .. } => write!(fmt, "{:?} = yield({:?})", resume_arg, value),
 386             Unreachable => write!(fmt, "unreachable"),
 387             Drop { place, .. } => write!(fmt, "drop({:?})", place),
 388             DropAndReplace { place, value, .. } => {
 389                 write!(fmt, "replace({:?} <- {:?})", place, value)
 390             }
 391             Call { func, args, destination, .. } => {
 392                 if let Some((destination, _)) = destination {
 393                     write!(fmt, "{:?} = ", destination)?;
 394                 }
 395                 write!(fmt, "{:?}(", func)?;
 396                 for (index, arg) in args.iter().enumerate() {
 397                     if index > 0 {
 398                         write!(fmt, ", ")?;
 399                     }
 400                     write!(fmt, "{:?}", arg)?;
 401                 }
 402                 write!(fmt, ")")
 403             }
 404             Assert { cond, expected, msg, .. } => {
 405                 write!(fmt, "assert(")?;
 406                 if !expected {
 407                     write!(fmt, "!")?;
 408                 }
 409                 write!(fmt, "{:?}, ", cond)?;
 410                 msg.fmt_assert_args(fmt)?;
 411                 write!(fmt, ")")
 412             }
 413             FalseEdge { .. } => write!(fmt, "falseEdge"),
 414             FalseUnwind { .. } => write!(fmt, "falseUnwind"),
 415             InlineAsm { template, ref operands, options, .. } => {
 416                 write!(fmt, "asm!(\"{}\"", InlineAsmTemplatePiece::to_string(template))?;
 417                 for op in operands {
 418                     write!(fmt, ", ")?;
 419                     let print_late = |&late| if late { "late" } else { "" };
 420                     match op {
 421                         InlineAsmOperand::In { reg, value } => {
 422                             write!(fmt, "in({}) {:?}", reg, value)?;
 423                         }
 424                         InlineAsmOperand::Out { reg, late, place: Some(place) } => {
 425                             write!(fmt, "{}out({}) {:?}", print_late(late), reg, place)?;
 426                         }
 427                         InlineAsmOperand::Out { reg, late, place: None } => {
 428                             write!(fmt, "{}out({}) _", print_late(late), reg)?;
 429                         }
 430                         InlineAsmOperand::InOut {
 431                             reg,
 432                             late,
 433                             in_value,
 434                             out_place: Some(out_place),
 435                         } => {
 436                             write!(
 437                                 fmt,
 438                                 "in{}out({}) {:?} => {:?}",
 439                                 print_late(late),
 440                                 reg,
 441                                 in_value,
 442                                 out_place
 443                             )?;
 444                         }
 445                         InlineAsmOperand::InOut { reg, late, in_value, out_place: None } => {
 446                             write!(fmt, "in{}out({}) {:?} => _", print_late(late), reg, in_value)?;
 447                         }
 448                         InlineAsmOperand::Const { value } => {
 449                             write!(fmt, "const {:?}", value)?;
 450                         }
 451                         InlineAsmOperand::SymFn { value } => {
 452                             write!(fmt, "sym_fn {:?}", value)?;
 453                         }
 454                         InlineAsmOperand::SymStatic { def_id } => {
 455                             write!(fmt, "sym_static {:?}", def_id)?;
 456                         }
 457                     }
 458                 }
 459                 write!(fmt, ", options({:?}))", options)
 460             }
 461         }
 462     }
 463
 464     /// Returns the list of labels for the edges to the successor basic blocks.
 465     pub fn fmt_successor_labels(&self) -> Vec<Cow<'static, str>> {
 466         use self::TerminatorKind::*;
 467         match *self {
 468             Return | Resume | Abort | Unreachable | GeneratorDrop => vec![],
 469             Goto { .. } => vec!["".into()],
 470             SwitchInt { ref values, switch_ty, .. } => ty::tls::with(|tcx| {
 471                 let param_env = ty::ParamEnv::empty();
 472                 let switch_ty = tcx.lift(&switch_ty).unwrap();
 473                 let size = tcx.layout_of(param_env.and(switch_ty)).unwrap().size;
 474                 values
 475                     .iter()
 476                     .map(|&u| {
 477                         ty::Const::from_scalar(tcx, Scalar::from_uint(u, size), switch_ty)
 478                             .to_string()
 479                             .into()
 480                     })
 481                     .chain(iter::once("otherwise".into()))
 482                     .collect()
 483             }),
 484             Call { destination: Some(_), cleanup: Some(_), .. } => {
 485                 vec!["return".into(), "unwind".into()]
 486             }
 487             Call { destination: Some(_), cleanup: None, .. } => vec!["return".into()],
 488             Call { destination: None, cleanup: Some(_), .. } => vec!["unwind".into()],
 489             Call { destination: None, cleanup: None, .. } => vec![],
 490             Yield { drop: Some(_), .. } => vec!["resume".into(), "drop".into()],
 491             Yield { drop: None, .. } => vec!["resume".into()],
 492             DropAndReplace { unwind: None, .. } | Drop { unwind: None, .. } => {
 493                 vec!["return".into()]
 494             }
 495             DropAndReplace { unwind: Some(_), .. } | Drop { unwind: Some(_), .. } => {
 496                 vec!["return".into(), "unwind".into()]
 497             }
 498             Assert { cleanup: None, .. } => vec!["".into()],
 499             Assert { .. } => vec!["success".into(), "unwind".into()],
 500             FalseEdge { .. } => vec!["real".into(), "imaginary".into()],
 501             FalseUnwind { unwind: Some(_), .. } => vec!["real".into(), "cleanup".into()],
 502             FalseUnwind { unwind: None, .. } => vec!["real".into()],
 503             InlineAsm { destination: Some(_), .. } => vec!["".into()],
 504             InlineAsm { destination: None, .. } => vec![],
 505         }
 506     }
 507 }