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