1 use crate::mir::interpret::Scalar;
2 use crate::ty::{self, Ty, TyCtxt};
3 use rustc_ast::{InlineAsmOptions, InlineAsmTemplatePiece};
4 use smallvec::{smallvec, SmallVec};
7 AssertMessage, BasicBlock, InlineAsmOperand, Operand, Place, SourceInfo, Successors,
10 pub use rustc_ast::Mutability;
11 use rustc_macros::HashStable;
14 use std::fmt::{self, Debug, Formatter, Write};
18 pub use super::query::*;
20 #[derive(Debug, Clone, TyEncodable, TyDecodable, Hash, HashStable, PartialEq, PartialOrd)]
21 pub struct SwitchTargets {
22 /// Possible values. The locations to branch to in each case
23 /// are found in the corresponding indices from the `targets` vector.
24 values: SmallVec<[u128; 1]>,
26 /// Possible branch sites. The last element of this vector is used
27 /// for the otherwise branch, so targets.len() == values.len() + 1
30 // This invariant is quite non-obvious and also could be improved.
31 // One way to make this invariant is to have something like this instead:
33 // branches: Vec<(ConstInt, BasicBlock)>,
34 // otherwise: Option<BasicBlock> // exhaustive if None
36 // However we’ve decided to keep this as-is until we figure a case
37 // where some other approach seems to be strictly better than other.
38 targets: SmallVec<[BasicBlock; 2]>,
42 /// Creates switch targets from an iterator of values and target blocks.
44 /// The iterator may be empty, in which case the `SwitchInt` instruction is equivalent to
45 /// `goto otherwise;`.
46 pub fn new(targets: impl Iterator<Item = (u128, BasicBlock)>, otherwise: BasicBlock) -> Self {
47 let (values, mut targets): (SmallVec<_>, SmallVec<_>) = targets.unzip();
48 targets.push(otherwise);
49 Self { values, targets }
52 /// Builds a switch targets definition that jumps to `then` if the tested value equals `value`,
53 /// and to `else_` if not.
54 pub fn static_if(value: u128, then: BasicBlock, else_: BasicBlock) -> Self {
55 Self { values: smallvec![value], targets: smallvec![then, else_] }
58 /// Returns the fallback target that is jumped to when none of the values match the operand.
59 pub fn otherwise(&self) -> BasicBlock {
60 *self.targets.last().unwrap()
63 /// Returns an iterator over the switch targets.
65 /// The iterator will yield tuples containing the value and corresponding target to jump to, not
66 /// including the `otherwise` fallback target.
68 /// Note that this may yield 0 elements. Only the `otherwise` branch is mandatory.
69 pub fn iter(&self) -> SwitchTargetsIter<'_> {
70 SwitchTargetsIter { inner: iter::zip(&self.values, &self.targets) }
73 /// Returns a slice with all possible jump targets (including the fallback target).
74 pub fn all_targets(&self) -> &[BasicBlock] {
78 pub fn all_targets_mut(&mut self) -> &mut [BasicBlock] {
82 /// Finds the `BasicBlock` to which this `SwitchInt` will branch given the
83 /// specific value. This cannot fail, as it'll return the `otherwise`
84 /// branch if there's not a specific match for the value.
85 pub fn target_for_value(&self, value: u128) -> BasicBlock {
86 self.iter().find_map(|(v, t)| (v == value).then_some(t)).unwrap_or_else(|| self.otherwise())
90 pub struct SwitchTargetsIter<'a> {
91 inner: iter::Zip<slice::Iter<'a, u128>, slice::Iter<'a, BasicBlock>>,
94 impl<'a> Iterator for SwitchTargetsIter<'a> {
95 type Item = (u128, BasicBlock);
97 fn next(&mut self) -> Option<Self::Item> {
98 self.inner.next().map(|(val, bb)| (*val, *bb))
101 fn size_hint(&self) -> (usize, Option<usize>) {
102 self.inner.size_hint()
106 impl<'a> ExactSizeIterator for SwitchTargetsIter<'a> {}
108 #[derive(Clone, TyEncodable, TyDecodable, Hash, HashStable, PartialEq, PartialOrd)]
109 pub enum TerminatorKind<'tcx> {
110 /// Block should have one successor in the graph; we jump there.
111 Goto { target: BasicBlock },
113 /// Operand evaluates to an integer; jump depending on its value
114 /// to one of the targets, and otherwise fallback to `otherwise`.
116 /// The discriminant value being tested.
117 discr: Operand<'tcx>,
119 /// The type of value being tested.
120 /// This is always the same as the type of `discr`.
121 /// FIXME: remove this redundant information. Currently, it is relied on by pretty-printing.
124 targets: SwitchTargets,
127 /// Indicates that the landing pad is finished and unwinding should
128 /// continue. Emitted by `build::scope::diverge_cleanup`.
131 /// Indicates that the landing pad is finished and that the process
132 /// should abort. Used to prevent unwinding for foreign items.
135 /// Indicates a normal return. The return place should have
136 /// been filled in before this executes. This can occur multiple times
137 /// in different basic blocks.
140 /// Indicates a terminator that can never be reached.
143 /// Drop the `Place`.
144 Drop { place: Place<'tcx>, target: BasicBlock, unwind: Option<BasicBlock> },
146 /// Drop the `Place` and assign the new value over it. This ensures
147 /// that the assignment to `P` occurs *even if* the destructor for
148 /// place unwinds. Its semantics are best explained by the
153 /// DropAndReplace(P <- V, goto BB1, unwind BB2)
161 /// Drop(P, goto BB1, unwind BB2)
164 /// // P is now uninitialized
168 /// // P is now uninitialized -- its dtor panicked
173 /// Note that DropAndReplace is eliminated as part of the `ElaborateDrops` pass.
176 value: Operand<'tcx>,
178 unwind: Option<BasicBlock>,
181 /// Block ends with a call of a function.
183 /// The function that’s being called.
185 /// Arguments the function is called with.
186 /// These are owned by the callee, which is free to modify them.
187 /// This allows the memory occupied by "by-value" arguments to be
188 /// reused across function calls without duplicating the contents.
189 args: Vec<Operand<'tcx>>,
190 /// Destination for the return value. If some, the call is converging.
191 destination: Option<(Place<'tcx>, BasicBlock)>,
192 /// Cleanups to be done if the call unwinds.
193 cleanup: Option<BasicBlock>,
194 /// `true` if this is from a call in HIR rather than from an overloaded
195 /// operator. True for overloaded function call.
197 /// This `Span` is the span of the function, without the dot and receiver
198 /// (e.g. `foo(a, b)` in `x.foo(a, b)`
202 /// Jump to the target if the condition has the expected value,
203 /// otherwise panic with a message and a cleanup target.
207 msg: AssertMessage<'tcx>,
209 cleanup: Option<BasicBlock>,
214 /// The value to return.
215 value: Operand<'tcx>,
216 /// Where to resume to.
218 /// The place to store the resume argument in.
219 resume_arg: Place<'tcx>,
220 /// Cleanup to be done if the generator is dropped at this suspend point.
221 drop: Option<BasicBlock>,
224 /// Indicates the end of the dropping of a generator.
227 /// A block where control flow only ever takes one real path, but borrowck
228 /// needs to be more conservative.
230 /// The target normal control flow will take.
231 real_target: BasicBlock,
232 /// A block control flow could conceptually jump to, but won't in
234 imaginary_target: BasicBlock,
236 /// A terminator for blocks that only take one path in reality, but where we
237 /// reserve the right to unwind in borrowck, even if it won't happen in practice.
238 /// This can arise in infinite loops with no function calls for example.
240 /// The target normal control flow will take.
241 real_target: BasicBlock,
242 /// The imaginary cleanup block link. This particular path will never be taken
243 /// in practice, but in order to avoid fragility we want to always
244 /// consider it in borrowck. We don't want to accept programs which
245 /// pass borrowck only when `panic=abort` or some assertions are disabled
246 /// due to release vs. debug mode builds. This needs to be an `Option` because
247 /// of the `remove_noop_landing_pads` and `abort_unwinding_calls` passes.
248 unwind: Option<BasicBlock>,
251 /// Block ends with an inline assembly block. This is a terminator since
252 /// inline assembly is allowed to diverge.
254 /// The template for the inline assembly, with placeholders.
255 template: &'tcx [InlineAsmTemplatePiece],
257 /// The operands for the inline assembly, as `Operand`s or `Place`s.
258 operands: Vec<InlineAsmOperand<'tcx>>,
260 /// Miscellaneous options for the inline assembly.
261 options: InlineAsmOptions,
263 /// Source spans for each line of the inline assembly code. These are
264 /// used to map assembler errors back to the line in the source code.
265 line_spans: &'tcx [Span],
267 /// Destination block after the inline assembly returns, unless it is
268 /// diverging (InlineAsmOptions::NORETURN).
269 destination: Option<BasicBlock>,
271 /// Cleanup to be done if the inline assembly unwinds. This is present
272 /// if and only if InlineAsmOptions::MAY_UNWIND is set.
273 cleanup: Option<BasicBlock>,
276 #[derive(Clone, Debug, TyEncodable, TyDecodable, HashStable)]
277 pub struct Terminator<'tcx> {
278 pub source_info: SourceInfo,
279 pub kind: TerminatorKind<'tcx>,
282 impl<'tcx> Terminator<'tcx> {
283 pub fn successors(&self) -> Successors<'_> {
284 self.kind.successors()
287 pub fn successors_mut(&mut self) -> SuccessorsMut<'_> {
288 self.kind.successors_mut()
291 pub fn unwind(&self) -> Option<&Option<BasicBlock>> {
295 pub fn unwind_mut(&mut self) -> Option<&mut Option<BasicBlock>> {
296 self.kind.unwind_mut()
300 impl<'tcx> TerminatorKind<'tcx> {
306 ) -> TerminatorKind<'tcx> {
307 TerminatorKind::SwitchInt {
309 switch_ty: tcx.types.bool,
310 targets: SwitchTargets::static_if(0, f, t),
314 pub fn successors(&self) -> Successors<'_> {
315 use self::TerminatorKind::*;
322 | Call { destination: None, cleanup: None, .. }
323 | InlineAsm { destination: None, cleanup: None, .. } => None.into_iter().chain(&[]),
324 Goto { target: ref t }
325 | Call { destination: None, cleanup: Some(ref t), .. }
326 | Call { destination: Some((_, ref t)), cleanup: None, .. }
327 | Yield { resume: ref t, drop: None, .. }
328 | DropAndReplace { target: ref t, unwind: None, .. }
329 | Drop { target: ref t, unwind: None, .. }
330 | Assert { target: ref t, cleanup: None, .. }
331 | FalseUnwind { real_target: ref t, unwind: None }
332 | InlineAsm { destination: Some(ref t), cleanup: None, .. }
333 | InlineAsm { destination: None, cleanup: Some(ref t), .. } => {
334 Some(t).into_iter().chain(&[])
336 Call { destination: Some((_, ref t)), cleanup: Some(ref u), .. }
337 | Yield { resume: ref t, drop: Some(ref u), .. }
338 | DropAndReplace { target: ref t, unwind: Some(ref u), .. }
339 | Drop { target: ref t, unwind: Some(ref u), .. }
340 | Assert { target: ref t, cleanup: Some(ref u), .. }
341 | FalseUnwind { real_target: ref t, unwind: Some(ref u) }
342 | InlineAsm { destination: Some(ref t), cleanup: Some(ref u), .. } => {
343 Some(t).into_iter().chain(slice::from_ref(u))
345 SwitchInt { ref targets, .. } => None.into_iter().chain(&targets.targets[..]),
346 FalseEdge { ref real_target, ref imaginary_target } => {
347 Some(real_target).into_iter().chain(slice::from_ref(imaginary_target))
352 pub fn successors_mut(&mut self) -> SuccessorsMut<'_> {
353 use self::TerminatorKind::*;
360 | Call { destination: None, cleanup: None, .. }
361 | InlineAsm { destination: None, cleanup: None, .. } => None.into_iter().chain(&mut []),
362 Goto { target: ref mut t }
363 | Call { destination: None, cleanup: Some(ref mut t), .. }
364 | Call { destination: Some((_, ref mut t)), cleanup: None, .. }
365 | Yield { resume: ref mut t, drop: None, .. }
366 | DropAndReplace { target: ref mut t, unwind: None, .. }
367 | Drop { target: ref mut t, unwind: None, .. }
368 | Assert { target: ref mut t, cleanup: None, .. }
369 | FalseUnwind { real_target: ref mut t, unwind: None }
370 | InlineAsm { destination: Some(ref mut t), cleanup: None, .. }
371 | InlineAsm { destination: None, cleanup: Some(ref mut t), .. } => {
372 Some(t).into_iter().chain(&mut [])
374 Call { destination: Some((_, ref mut t)), cleanup: Some(ref mut u), .. }
375 | Yield { resume: ref mut t, drop: Some(ref mut u), .. }
376 | DropAndReplace { target: ref mut t, unwind: Some(ref mut u), .. }
377 | Drop { target: ref mut t, unwind: Some(ref mut u), .. }
378 | Assert { target: ref mut t, cleanup: Some(ref mut u), .. }
379 | FalseUnwind { real_target: ref mut t, unwind: Some(ref mut u) }
380 | InlineAsm { destination: Some(ref mut t), cleanup: Some(ref mut u), .. } => {
381 Some(t).into_iter().chain(slice::from_mut(u))
383 SwitchInt { ref mut targets, .. } => None.into_iter().chain(&mut targets.targets[..]),
384 FalseEdge { ref mut real_target, ref mut imaginary_target } => {
385 Some(real_target).into_iter().chain(slice::from_mut(imaginary_target))
390 pub fn unwind(&self) -> Option<&Option<BasicBlock>> {
392 TerminatorKind::Goto { .. }
393 | TerminatorKind::Resume
394 | TerminatorKind::Abort
395 | TerminatorKind::Return
396 | TerminatorKind::Unreachable
397 | TerminatorKind::GeneratorDrop
398 | TerminatorKind::Yield { .. }
399 | TerminatorKind::SwitchInt { .. }
400 | TerminatorKind::FalseEdge { .. } => None,
401 TerminatorKind::Call { cleanup: ref unwind, .. }
402 | TerminatorKind::Assert { cleanup: ref unwind, .. }
403 | TerminatorKind::DropAndReplace { ref unwind, .. }
404 | TerminatorKind::Drop { ref unwind, .. }
405 | TerminatorKind::FalseUnwind { ref unwind, .. }
406 | TerminatorKind::InlineAsm { cleanup: ref unwind, .. } => Some(unwind),
410 pub fn unwind_mut(&mut self) -> Option<&mut Option<BasicBlock>> {
412 TerminatorKind::Goto { .. }
413 | TerminatorKind::Resume
414 | TerminatorKind::Abort
415 | TerminatorKind::Return
416 | TerminatorKind::Unreachable
417 | TerminatorKind::GeneratorDrop
418 | TerminatorKind::Yield { .. }
419 | TerminatorKind::SwitchInt { .. }
420 | TerminatorKind::FalseEdge { .. } => None,
421 TerminatorKind::Call { cleanup: ref mut unwind, .. }
422 | TerminatorKind::Assert { cleanup: ref mut unwind, .. }
423 | TerminatorKind::DropAndReplace { ref mut unwind, .. }
424 | TerminatorKind::Drop { ref mut unwind, .. }
425 | TerminatorKind::FalseUnwind { ref mut unwind, .. }
426 | TerminatorKind::InlineAsm { cleanup: ref mut unwind, .. } => Some(unwind),
430 pub fn as_switch(&self) -> Option<(&Operand<'tcx>, Ty<'tcx>, &SwitchTargets)> {
432 TerminatorKind::SwitchInt { discr, switch_ty, targets } => {
433 Some((discr, switch_ty, targets))
439 pub fn as_goto(&self) -> Option<BasicBlock> {
441 TerminatorKind::Goto { target } => Some(*target),
447 impl<'tcx> Debug for TerminatorKind<'tcx> {
448 fn fmt(&self, fmt: &mut Formatter<'_>) -> fmt::Result {
450 let successor_count = self.successors().count();
451 let labels = self.fmt_successor_labels();
452 assert_eq!(successor_count, labels.len());
454 match successor_count {
457 1 => write!(fmt, " -> {:?}", self.successors().next().unwrap()),
460 write!(fmt, " -> [")?;
461 for (i, target) in self.successors().enumerate() {
465 write!(fmt, "{}: {:?}", labels[i], target)?;
473 impl<'tcx> TerminatorKind<'tcx> {
474 /// Writes the "head" part of the terminator; that is, its name and the data it uses to pick the
475 /// successor basic block, if any. The only information not included is the list of possible
476 /// successors, which may be rendered differently between the text and the graphviz format.
477 pub fn fmt_head<W: Write>(&self, fmt: &mut W) -> fmt::Result {
478 use self::TerminatorKind::*;
480 Goto { .. } => write!(fmt, "goto"),
481 SwitchInt { discr, .. } => write!(fmt, "switchInt({:?})", discr),
482 Return => write!(fmt, "return"),
483 GeneratorDrop => write!(fmt, "generator_drop"),
484 Resume => write!(fmt, "resume"),
485 Abort => write!(fmt, "abort"),
486 Yield { value, resume_arg, .. } => write!(fmt, "{:?} = yield({:?})", resume_arg, value),
487 Unreachable => write!(fmt, "unreachable"),
488 Drop { place, .. } => write!(fmt, "drop({:?})", place),
489 DropAndReplace { place, value, .. } => {
490 write!(fmt, "replace({:?} <- {:?})", place, value)
492 Call { func, args, destination, .. } => {
493 if let Some((destination, _)) = destination {
494 write!(fmt, "{:?} = ", destination)?;
496 write!(fmt, "{:?}(", func)?;
497 for (index, arg) in args.iter().enumerate() {
501 write!(fmt, "{:?}", arg)?;
505 Assert { cond, expected, msg, .. } => {
506 write!(fmt, "assert(")?;
510 write!(fmt, "{:?}, ", cond)?;
511 msg.fmt_assert_args(fmt)?;
514 FalseEdge { .. } => write!(fmt, "falseEdge"),
515 FalseUnwind { .. } => write!(fmt, "falseUnwind"),
516 InlineAsm { template, ref operands, options, .. } => {
517 write!(fmt, "asm!(\"{}\"", InlineAsmTemplatePiece::to_string(template))?;
520 let print_late = |&late| if late { "late" } else { "" };
522 InlineAsmOperand::In { reg, value } => {
523 write!(fmt, "in({}) {:?}", reg, value)?;
525 InlineAsmOperand::Out { reg, late, place: Some(place) } => {
526 write!(fmt, "{}out({}) {:?}", print_late(late), reg, place)?;
528 InlineAsmOperand::Out { reg, late, place: None } => {
529 write!(fmt, "{}out({}) _", print_late(late), reg)?;
531 InlineAsmOperand::InOut {
535 out_place: Some(out_place),
539 "in{}out({}) {:?} => {:?}",
546 InlineAsmOperand::InOut { reg, late, in_value, out_place: None } => {
547 write!(fmt, "in{}out({}) {:?} => _", print_late(late), reg, in_value)?;
549 InlineAsmOperand::Const { value } => {
550 write!(fmt, "const {:?}", value)?;
552 InlineAsmOperand::SymFn { value } => {
553 write!(fmt, "sym_fn {:?}", value)?;
555 InlineAsmOperand::SymStatic { def_id } => {
556 write!(fmt, "sym_static {:?}", def_id)?;
560 write!(fmt, ", options({:?}))", options)
565 /// Returns the list of labels for the edges to the successor basic blocks.
566 pub fn fmt_successor_labels(&self) -> Vec<Cow<'static, str>> {
567 use self::TerminatorKind::*;
569 Return | Resume | Abort | Unreachable | GeneratorDrop => vec![],
570 Goto { .. } => vec!["".into()],
571 SwitchInt { ref targets, switch_ty, .. } => ty::tls::with(|tcx| {
572 let param_env = ty::ParamEnv::empty();
573 let switch_ty = tcx.lift(switch_ty).unwrap();
574 let size = tcx.layout_of(param_env.and(switch_ty)).unwrap().size;
579 ty::Const::from_scalar(tcx, Scalar::from_uint(u, size), switch_ty)
583 .chain(iter::once("otherwise".into()))
586 Call { destination: Some(_), cleanup: Some(_), .. } => {
587 vec!["return".into(), "unwind".into()]
589 Call { destination: Some(_), cleanup: None, .. } => vec!["return".into()],
590 Call { destination: None, cleanup: Some(_), .. } => vec!["unwind".into()],
591 Call { destination: None, cleanup: None, .. } => vec![],
592 Yield { drop: Some(_), .. } => vec!["resume".into(), "drop".into()],
593 Yield { drop: None, .. } => vec!["resume".into()],
594 DropAndReplace { unwind: None, .. } | Drop { unwind: None, .. } => {
595 vec!["return".into()]
597 DropAndReplace { unwind: Some(_), .. } | Drop { unwind: Some(_), .. } => {
598 vec!["return".into(), "unwind".into()]
600 Assert { cleanup: None, .. } => vec!["".into()],
601 Assert { .. } => vec!["success".into(), "unwind".into()],
602 FalseEdge { .. } => vec!["real".into(), "imaginary".into()],
603 FalseUnwind { unwind: Some(_), .. } => vec!["real".into(), "cleanup".into()],
604 FalseUnwind { unwind: None, .. } => vec!["real".into()],
605 InlineAsm { destination: Some(_), cleanup: Some(_), .. } => {
606 vec!["return".into(), "unwind".into()]
608 InlineAsm { destination: Some(_), cleanup: None, .. } => vec!["return".into()],
609 InlineAsm { destination: None, cleanup: Some(_), .. } => vec!["unwind".into()],
610 InlineAsm { destination: None, cleanup: None, .. } => vec![],