From 432535da2b5144d467056efcfa6864d35ba2de0f Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Sat, 10 Oct 2020 17:36:04 +0200 Subject: [PATCH] Refactor how SwitchInt stores jump targets --- compiler/rustc_codegen_ssa/src/mir/block.rs | 45 +++---- .../rustc_middle/src/mir/terminator/mod.rs | 112 ++++++++++++++---- .../rustc_middle/src/mir/type_foldable.rs | 3 +- compiler/rustc_middle/src/mir/visit.rs | 1 - .../src/borrow_check/invalidation.rs | 2 +- compiler/rustc_mir/src/borrow_check/mod.rs | 2 +- .../src/borrow_check/type_check/mod.rs | 2 +- .../src/dataflow/framework/direction.rs | 18 ++- .../rustc_mir/src/interpret/terminator.rs | 10 +- .../src/transform/early_otherwise_branch.rs | 35 +++--- compiler/rustc_mir/src/transform/generator.rs | 6 +- compiler/rustc_mir/src/transform/inline.rs | 2 +- .../rustc_mir/src/transform/match_branches.rs | 9 +- .../src/transform/simplify_branches.rs | 9 +- .../transform/simplify_comparison_integral.rs | 48 ++++---- .../rustc_mir/src/transform/simplify_try.rs | 14 +-- .../transform/uninhabited_enum_branching.rs | 23 ++-- .../src/transform/unreachable_prop.rs | 20 ++-- compiler/rustc_mir/src/transform/validate.rs | 17 +-- .../rustc_mir/src/util/elaborate_drops.rs | 14 ++- .../rustc_mir_build/src/build/matches/test.rs | 60 +++++----- .../src/utils/qualify_min_const_fn.rs | 1 - 22 files changed, 247 insertions(+), 206 deletions(-) diff --git a/compiler/rustc_codegen_ssa/src/mir/block.rs b/compiler/rustc_codegen_ssa/src/mir/block.rs index 703a17b200a..8d57ccdba6d 100644 --- a/compiler/rustc_codegen_ssa/src/mir/block.rs +++ b/compiler/rustc_codegen_ssa/src/mir/block.rs @@ -12,9 +12,9 @@ use rustc_ast as ast; use rustc_hir::lang_items::LangItem; use rustc_index::vec::Idx; -use rustc_middle::mir; use rustc_middle::mir::interpret::ConstValue; use rustc_middle::mir::AssertKind; +use rustc_middle::mir::{self, SwitchTargets}; use rustc_middle::ty::layout::{FnAbiExt, HasTyCtxt}; use rustc_middle::ty::print::with_no_trimmed_paths; use rustc_middle::ty::{self, Instance, Ty, TypeFoldable}; @@ -24,8 +24,6 @@ use rustc_target::abi::{self, LayoutOf}; use rustc_target::spec::abi::Abi; -use std::borrow::Cow; - /// Used by `FunctionCx::codegen_terminator` for emitting common patterns /// e.g., creating a basic block, calling a function, etc. struct TerminatorCodegenHelper<'tcx> { @@ -198,42 +196,37 @@ fn codegen_switchint_terminator( mut bx: Bx, discr: &mir::Operand<'tcx>, switch_ty: Ty<'tcx>, - values: &Cow<'tcx, [u128]>, - targets: &Vec, + targets: &SwitchTargets<'tcx>, ) { let discr = self.codegen_operand(&mut bx, &discr); // `switch_ty` is redundant, sanity-check that. assert_eq!(discr.layout.ty, switch_ty); - if targets.len() == 2 { - // If there are two targets, emit br instead of switch - let lltrue = helper.llblock(self, targets[0]); - let llfalse = helper.llblock(self, targets[1]); + helper.maybe_sideeffect(self.mir, &mut bx, targets.all_targets()); + + let mut target_iter = targets.iter(); + if target_iter.len() == 1 { + // If there are two targets (one conditional, one fallback), emit br instead of switch + let (test_value, target) = target_iter.next().unwrap(); + let lltrue = helper.llblock(self, target); + let llfalse = helper.llblock(self, targets.otherwise()); if switch_ty == bx.tcx().types.bool { - helper.maybe_sideeffect(self.mir, &mut bx, targets.as_slice()); // Don't generate trivial icmps when switching on bool - if let [0] = values[..] { - bx.cond_br(discr.immediate(), llfalse, lltrue); - } else { - assert_eq!(&values[..], &[1]); - bx.cond_br(discr.immediate(), lltrue, llfalse); + match test_value { + 0 => bx.cond_br(discr.immediate(), llfalse, lltrue), + 1 => bx.cond_br(discr.immediate(), lltrue, llfalse), + _ => bug!(), } } else { let switch_llty = bx.immediate_backend_type(bx.layout_of(switch_ty)); - let llval = bx.const_uint_big(switch_llty, values[0]); + let llval = bx.const_uint_big(switch_llty, test_value); let cmp = bx.icmp(IntPredicate::IntEQ, discr.immediate(), llval); - helper.maybe_sideeffect(self.mir, &mut bx, targets.as_slice()); bx.cond_br(cmp, lltrue, llfalse); } } else { - helper.maybe_sideeffect(self.mir, &mut bx, targets.as_slice()); - let (otherwise, targets) = targets.split_last().unwrap(); bx.switch( discr.immediate(), - helper.llblock(self, *otherwise), - values - .iter() - .zip(targets) - .map(|(&value, target)| (value, helper.llblock(self, *target))), + helper.llblock(self, targets.otherwise()), + target_iter.map(|(value, target)| (value, helper.llblock(self, target))), ); } } @@ -975,8 +968,8 @@ fn codegen_terminator( helper.funclet_br(self, &mut bx, target); } - mir::TerminatorKind::SwitchInt { ref discr, switch_ty, ref values, ref targets } => { - self.codegen_switchint_terminator(helper, bx, discr, switch_ty, values, targets); + mir::TerminatorKind::SwitchInt { ref discr, switch_ty, ref targets } => { + self.codegen_switchint_terminator(helper, bx, discr, switch_ty, targets); } mir::TerminatorKind::Return => { diff --git a/compiler/rustc_middle/src/mir/terminator/mod.rs b/compiler/rustc_middle/src/mir/terminator/mod.rs index 8909f02270c..677776106f5 100644 --- a/compiler/rustc_middle/src/mir/terminator/mod.rs +++ b/compiler/rustc_middle/src/mir/terminator/mod.rs @@ -16,6 +16,87 @@ pub use super::query::*; +#[derive(Debug, Clone, TyEncodable, TyDecodable, HashStable, PartialEq)] +pub struct SwitchTargets<'tcx> { + /// Possible values. The locations to branch to in each case + /// are found in the corresponding indices from the `targets` vector. + values: Cow<'tcx, [u128]>, + + /// Possible branch sites. The last element of this vector is used + /// for the otherwise branch, so targets.len() == values.len() + 1 + /// should hold. + // + // This invariant is quite non-obvious and also could be improved. + // One way to make this invariant is to have something like this instead: + // + // branches: Vec<(ConstInt, BasicBlock)>, + // otherwise: Option // exhaustive if None + // + // However we’ve decided to keep this as-is until we figure a case + // where some other approach seems to be strictly better than other. + targets: Vec, +} + +impl<'tcx> SwitchTargets<'tcx> { + /// Creates switch targets from an iterator of values and target blocks. + /// + /// The iterator may be empty, in which case the `SwitchInt` instruction is equivalent to + /// `goto otherwise;`. + pub fn new(targets: impl Iterator, otherwise: BasicBlock) -> Self { + let (values, mut targets): (Vec<_>, Vec<_>) = targets.unzip(); + targets.push(otherwise); + Self { values: values.into(), targets } + } + + /// Builds a switch targets definition that jumps to `then` if the tested value equals `value`, + /// and to `else_` if not. + pub fn static_if(value: &'static [u128; 1], then: BasicBlock, else_: BasicBlock) -> Self { + Self { values: Cow::Borrowed(value), targets: vec![then, else_] } + } + + /// Returns the fallback target that is jumped to when none of the values match the operand. + pub fn otherwise(&self) -> BasicBlock { + *self.targets.last().unwrap() + } + + /// Returns an iterator over the switch targets. + /// + /// The iterator will yield tuples containing the value and corresponding target to jump to, not + /// including the `otherwise` fallback target. + /// + /// Note that this may yield 0 elements. Only the `otherwise` branch is mandatory. + pub fn iter(&self) -> SwitchTargetsIter<'_> { + SwitchTargetsIter { inner: self.values.iter().zip(self.targets.iter()) } + } + + /// Returns a slice with all possible jump targets (including the fallback target). + pub fn all_targets(&self) -> &[BasicBlock] { + &self.targets + } + + pub fn all_targets_mut(&mut self) -> &mut [BasicBlock] { + &mut self.targets + } +} + +pub struct SwitchTargetsIter<'a> { + inner: iter::Zip, slice::Iter<'a, BasicBlock>>, +} + +impl<'a> Iterator for SwitchTargetsIter<'a> { + type Item = (u128, BasicBlock); + + fn next(&mut self) -> Option { + self.inner.next().map(|(val, bb)| (*val, *bb)) + } + + fn size_hint(&self) -> (usize, Option) { + self.inner.size_hint() + } +} + +impl<'a> ExactSizeIterator for SwitchTargetsIter<'a> {} + #[derive(Clone, TyEncodable, TyDecodable, HashStable, PartialEq)] pub enum TerminatorKind<'tcx> { /// Block should have one successor in the graph; we jump there. @@ -32,23 +113,7 @@ pub enum TerminatorKind<'tcx> { /// FIXME: remove this redundant information. Currently, it is relied on by pretty-printing. switch_ty: Ty<'tcx>, - /// Possible values. The locations to branch to in each case - /// are found in the corresponding indices from the `targets` vector. - values: Cow<'tcx, [u128]>, - - /// Possible branch sites. The last element of this vector is used - /// for the otherwise branch, so targets.len() == values.len() + 1 - /// should hold. - // - // This invariant is quite non-obvious and also could be improved. - // One way to make this invariant is to have something like this instead: - // - // branches: Vec<(ConstInt, BasicBlock)>, - // otherwise: Option // exhaustive if None - // - // However we’ve decided to keep this as-is until we figure a case - // where some other approach seems to be strictly better than other. - targets: Vec, + targets: SwitchTargets<'tcx>, }, /// Indicates that the landing pad is finished and unwinding should @@ -227,12 +292,10 @@ pub fn if_( t: BasicBlock, f: BasicBlock, ) -> TerminatorKind<'tcx> { - static BOOL_SWITCH_FALSE: &[u128] = &[0]; TerminatorKind::SwitchInt { discr: cond, switch_ty: tcx.types.bool, - values: From::from(BOOL_SWITCH_FALSE), - targets: vec![f, t], + targets: SwitchTargets::static_if(&[0], f, t), } } @@ -263,7 +326,7 @@ pub fn successors(&self) -> Successors<'_> { | FalseUnwind { real_target: ref t, unwind: Some(ref u) } => { Some(t).into_iter().chain(slice::from_ref(u)) } - SwitchInt { ref targets, .. } => None.into_iter().chain(&targets[..]), + SwitchInt { ref targets, .. } => None.into_iter().chain(&targets.targets[..]), FalseEdge { ref real_target, ref imaginary_target } => { Some(real_target).into_iter().chain(slice::from_ref(imaginary_target)) } @@ -297,7 +360,7 @@ pub fn successors_mut(&mut self) -> SuccessorsMut<'_> { | FalseUnwind { real_target: ref mut t, unwind: Some(ref mut u) } => { Some(t).into_iter().chain(slice::from_mut(u)) } - SwitchInt { ref mut targets, .. } => None.into_iter().chain(&mut targets[..]), + SwitchInt { ref mut targets, .. } => None.into_iter().chain(&mut targets.targets[..]), FalseEdge { ref mut real_target, ref mut imaginary_target } => { Some(real_target).into_iter().chain(slice::from_mut(imaginary_target)) } @@ -469,11 +532,12 @@ pub fn fmt_successor_labels(&self) -> Vec> { match *self { Return | Resume | Abort | Unreachable | GeneratorDrop => vec![], Goto { .. } => vec!["".into()], - SwitchInt { ref values, switch_ty, .. } => ty::tls::with(|tcx| { + SwitchInt { ref targets, switch_ty, .. } => ty::tls::with(|tcx| { let param_env = ty::ParamEnv::empty(); let switch_ty = tcx.lift(&switch_ty).unwrap(); let size = tcx.layout_of(param_env.and(switch_ty)).unwrap().size; - values + targets + .values .iter() .map(|&u| { ty::Const::from_scalar(tcx, Scalar::from_uint(u, size), switch_ty) diff --git a/compiler/rustc_middle/src/mir/type_foldable.rs b/compiler/rustc_middle/src/mir/type_foldable.rs index ad2eae0298c..9297aed66a4 100644 --- a/compiler/rustc_middle/src/mir/type_foldable.rs +++ b/compiler/rustc_middle/src/mir/type_foldable.rs @@ -21,10 +21,9 @@ fn super_fold_with>(&self, folder: &mut F) -> Self { let kind = match self.kind { Goto { target } => Goto { target }, - SwitchInt { ref discr, switch_ty, ref values, ref targets } => SwitchInt { + SwitchInt { ref discr, switch_ty, ref targets } => SwitchInt { discr: discr.fold_with(folder), switch_ty: switch_ty.fold_with(folder), - values: values.clone(), targets: targets.clone(), }, Drop { ref place, target, unwind } => { diff --git a/compiler/rustc_middle/src/mir/visit.rs b/compiler/rustc_middle/src/mir/visit.rs index 9a6bfa10189..1adebe30b5e 100644 --- a/compiler/rustc_middle/src/mir/visit.rs +++ b/compiler/rustc_middle/src/mir/visit.rs @@ -453,7 +453,6 @@ fn super_terminator(&mut self, TerminatorKind::SwitchInt { discr, switch_ty, - values: _, targets: _ } => { self.visit_operand(discr, location); diff --git a/compiler/rustc_mir/src/borrow_check/invalidation.rs b/compiler/rustc_mir/src/borrow_check/invalidation.rs index c84ccafaff5..8c05e6fd5d0 100644 --- a/compiler/rustc_mir/src/borrow_check/invalidation.rs +++ b/compiler/rustc_mir/src/borrow_check/invalidation.rs @@ -117,7 +117,7 @@ fn visit_terminator(&mut self, terminator: &Terminator<'tcx>, location: Location self.check_activations(location); match &terminator.kind { - TerminatorKind::SwitchInt { ref discr, switch_ty: _, values: _, targets: _ } => { + TerminatorKind::SwitchInt { ref discr, switch_ty: _, targets: _ } => { self.consume_operand(location, discr); } TerminatorKind::Drop { place: drop_place, target: _, unwind: _ } => { diff --git a/compiler/rustc_mir/src/borrow_check/mod.rs b/compiler/rustc_mir/src/borrow_check/mod.rs index 9b34db1de40..4b7af271bae 100644 --- a/compiler/rustc_mir/src/borrow_check/mod.rs +++ b/compiler/rustc_mir/src/borrow_check/mod.rs @@ -671,7 +671,7 @@ fn visit_terminator_before_primary_effect( self.check_activations(loc, span, flow_state); match term.kind { - TerminatorKind::SwitchInt { ref discr, switch_ty: _, values: _, targets: _ } => { + TerminatorKind::SwitchInt { ref discr, switch_ty: _, targets: _ } => { self.consume_operand(loc, (discr, span), flow_state); } TerminatorKind::Drop { place: ref drop_place, target: _, unwind: _ } => { diff --git a/compiler/rustc_mir/src/borrow_check/type_check/mod.rs b/compiler/rustc_mir/src/borrow_check/type_check/mod.rs index f8a8801595a..4fc1c570e46 100644 --- a/compiler/rustc_mir/src/borrow_check/type_check/mod.rs +++ b/compiler/rustc_mir/src/borrow_check/type_check/mod.rs @@ -1777,7 +1777,7 @@ fn check_iscleanup(&mut self, body: &Body<'tcx>, block_data: &BasicBlockData<'tc self.assert_iscleanup(body, block_data, target, is_cleanup) } TerminatorKind::SwitchInt { ref targets, .. } => { - for target in targets { + for target in targets.all_targets() { self.assert_iscleanup(body, block_data, *target, is_cleanup); } } diff --git a/compiler/rustc_mir/src/dataflow/framework/direction.rs b/compiler/rustc_mir/src/dataflow/framework/direction.rs index ca2bb6e0bf7..72e3a876254 100644 --- a/compiler/rustc_mir/src/dataflow/framework/direction.rs +++ b/compiler/rustc_mir/src/dataflow/framework/direction.rs @@ -1,5 +1,5 @@ use rustc_index::bit_set::BitSet; -use rustc_middle::mir::{self, BasicBlock, Location}; +use rustc_middle::mir::{self, BasicBlock, Location, SwitchTargets}; use rustc_middle::ty::TyCtxt; use std::ops::RangeInclusive; @@ -488,11 +488,10 @@ fn join_state_into_successors_of( } } - SwitchInt { ref targets, ref values, ref discr, switch_ty: _ } => { + SwitchInt { ref targets, ref discr, switch_ty: _ } => { let mut applier = SwitchIntEdgeEffectApplier { exit_state, - targets: targets.as_ref(), - values: values.as_ref(), + targets, propagate, effects_applied: false, }; @@ -504,8 +503,8 @@ fn join_state_into_successors_of( } = applier; if !effects_applied { - for &target in targets.iter() { - propagate(target, exit_state); + for target in targets.all_targets() { + propagate(*target, exit_state); } } } @@ -515,8 +514,7 @@ fn join_state_into_successors_of( struct SwitchIntEdgeEffectApplier<'a, D, F> { exit_state: &'a mut D, - values: &'a [u128], - targets: &'a [BasicBlock], + targets: &'a SwitchTargets<'a>, propagate: F, effects_applied: bool, @@ -531,7 +529,7 @@ fn apply(&mut self, mut apply_edge_effect: impl FnMut(&mut D, SwitchIntTarget)) assert!(!self.effects_applied); let mut tmp = None; - for (&value, &target) in self.values.iter().zip(self.targets.iter()) { + for (value, target) in self.targets.iter() { let tmp = opt_clone_from_or_clone(&mut tmp, self.exit_state); apply_edge_effect(tmp, SwitchIntTarget { value: Some(value), target }); (self.propagate)(target, tmp); @@ -539,7 +537,7 @@ fn apply(&mut self, mut apply_edge_effect: impl FnMut(&mut D, SwitchIntTarget)) // Once we get to the final, "otherwise" branch, there is no need to preserve `exit_state`, // so pass it directly to `apply_edge_effect` to save a clone of the dataflow state. - let otherwise = self.targets.last().copied().unwrap(); + let otherwise = self.targets.otherwise(); apply_edge_effect(self.exit_state, SwitchIntTarget { value: None, target: otherwise }); (self.propagate)(otherwise, self.exit_state); diff --git a/compiler/rustc_mir/src/interpret/terminator.rs b/compiler/rustc_mir/src/interpret/terminator.rs index 9f200ca62b8..bb11c2a23bd 100644 --- a/compiler/rustc_mir/src/interpret/terminator.rs +++ b/compiler/rustc_mir/src/interpret/terminator.rs @@ -24,16 +24,16 @@ pub(super) fn eval_terminator( Goto { target } => self.go_to_block(target), - SwitchInt { ref discr, ref values, ref targets, switch_ty } => { + SwitchInt { ref discr, ref targets, switch_ty } => { let discr = self.read_immediate(self.eval_operand(discr, None)?)?; trace!("SwitchInt({:?})", *discr); assert_eq!(discr.layout.ty, switch_ty); // Branch to the `otherwise` case by default, if no match is found. - assert!(!targets.is_empty()); - let mut target_block = targets[targets.len() - 1]; + assert!(!targets.iter().is_empty()); + let mut target_block = targets.otherwise(); - for (index, &const_int) in values.iter().enumerate() { + for (const_int, target) in targets.iter() { // Compare using binary_op, to also support pointer values let res = self .overflowing_binary_op( @@ -43,7 +43,7 @@ pub(super) fn eval_terminator( )? .0; if res.to_bool()? { - target_block = targets[index]; + target_block = target; break; } } diff --git a/compiler/rustc_mir/src/transform/early_otherwise_branch.rs b/compiler/rustc_mir/src/transform/early_otherwise_branch.rs index 237a5c7864b..f97dcf4852d 100644 --- a/compiler/rustc_mir/src/transform/early_otherwise_branch.rs +++ b/compiler/rustc_mir/src/transform/early_otherwise_branch.rs @@ -1,7 +1,7 @@ use crate::{transform::MirPass, util::patch::MirPatch}; use rustc_middle::mir::*; use rustc_middle::ty::{Ty, TyCtxt}; -use std::{borrow::Cow, fmt::Debug}; +use std::fmt::Debug; use super::simplify::simplify_cfg; @@ -95,15 +95,17 @@ fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) { StatementKind::Assign(box (Place::from(not_equal_temp), not_equal_rvalue)), ); - let (mut targets_to_jump_to, values_to_jump_to): (Vec<_>, Vec<_>) = opt_to_apply + let new_targets = opt_to_apply .infos .iter() .flat_map(|x| x.second_switch_info.targets_with_values.iter()) - .cloned() - .unzip(); + .cloned(); + + let targets = SwitchTargets::new( + new_targets, + opt_to_apply.infos[0].first_switch_info.otherwise_bb, + ); - // add otherwise case in the end - targets_to_jump_to.push(opt_to_apply.infos[0].first_switch_info.otherwise_bb); // new block that jumps to the correct discriminant case. This block is switched to if the discriminants are equal let new_switch_data = BasicBlockData::new(Some(Terminator { source_info: opt_to_apply.infos[0].second_switch_info.discr_source_info, @@ -111,8 +113,7 @@ fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) { // the first and second discriminants are equal, so just pick one discr: Operand::Copy(first_descriminant_place), switch_ty: discr_type, - values: Cow::from(values_to_jump_to), - targets: targets_to_jump_to, + targets, }, })); @@ -176,7 +177,7 @@ struct SwitchDiscriminantInfo<'tcx> { /// The basic block that the otherwise branch points to otherwise_bb: BasicBlock, /// Target along with the value being branched from. Otherwise is not included - targets_with_values: Vec<(BasicBlock, u128)>, + targets_with_values: Vec<(u128, BasicBlock)>, discr_source_info: SourceInfo, /// The place of the discriminant used in the switch discr_used_in_switch: Place<'tcx>, @@ -211,7 +212,7 @@ pub fn go( let discr = self.find_switch_discriminant_info(bb, switch)?; // go through each target, finding a discriminant read, and a switch - let results = discr.targets_with_values.iter().map(|(target, value)| { + let results = discr.targets_with_values.iter().map(|(value, target)| { self.find_discriminant_switch_pairing(&discr, target.clone(), value.clone()) }); @@ -253,7 +254,7 @@ fn find_discriminant_switch_pairing( } // check that the value being matched on is the same. The - if this_bb_discr_info.targets_with_values.iter().find(|x| x.1 == value).is_none() { + if this_bb_discr_info.targets_with_values.iter().find(|x| x.0 == value).is_none() { trace!("NO: values being matched on are not the same"); return None; } @@ -270,7 +271,7 @@ fn find_discriminant_switch_pairing( // ``` // We check this by seeing that the value of the first discriminant is the only other discriminant value being used as a target in the second switch if !(this_bb_discr_info.targets_with_values.len() == 1 - && this_bb_discr_info.targets_with_values[0].1 == value) + && this_bb_discr_info.targets_with_values[0].0 == value) { trace!( "NO: The second switch did not have only 1 target (besides otherwise) that had the same value as the value from the first switch that got us here" @@ -296,18 +297,14 @@ fn find_switch_discriminant_info( switch: &Terminator<'tcx>, ) -> Option> { match &switch.kind { - TerminatorKind::SwitchInt { discr, targets, values, .. } => { + TerminatorKind::SwitchInt { discr, targets, .. } => { let discr_local = discr.place()?.as_local()?; // the declaration of the discriminant read. Place of this read is being used in the switch let discr_decl = &self.body.local_decls()[discr_local]; let discr_ty = discr_decl.ty; // the otherwise target lies as the last element - let otherwise_bb = targets.get(values.len())?.clone(); - let targets_with_values = targets - .iter() - .zip(values.iter()) - .map(|(t, v)| (t.clone(), v.clone())) - .collect(); + let otherwise_bb = targets.otherwise(); + let targets_with_values = targets.iter().collect(); // find the place of the adt where the discriminant is being read from // assume this is the last statement of the block diff --git a/compiler/rustc_mir/src/transform/generator.rs b/compiler/rustc_mir/src/transform/generator.rs index 924bb4996fc..039d4753a8c 100644 --- a/compiler/rustc_mir/src/transform/generator.rs +++ b/compiler/rustc_mir/src/transform/generator.rs @@ -71,7 +71,6 @@ use rustc_middle::ty::{self, AdtDef, Ty, TyCtxt}; use rustc_target::abi::VariantIdx; use rustc_target::spec::PanicStrategy; -use std::borrow::Cow; use std::{iter, ops}; pub struct StateTransform; @@ -839,11 +838,12 @@ fn insert_switch<'tcx>( ) { let default_block = insert_term_block(body, default); let (assign, discr) = transform.get_discr(body); + let switch_targets = + SwitchTargets::new(cases.iter().map(|(i, bb)| ((*i) as u128, *bb)), default_block); let switch = TerminatorKind::SwitchInt { discr: Operand::Move(discr), switch_ty: transform.discr_ty, - values: Cow::from(cases.iter().map(|&(i, _)| i as u128).collect::>()), - targets: cases.iter().map(|&(_, d)| d).chain(iter::once(default_block)).collect(), + targets: switch_targets, }; let source_info = SourceInfo::outermost(body.span); diff --git a/compiler/rustc_mir/src/transform/inline.rs b/compiler/rustc_mir/src/transform/inline.rs index bec1eb79047..34aaefdcbea 100644 --- a/compiler/rustc_mir/src/transform/inline.rs +++ b/compiler/rustc_mir/src/transform/inline.rs @@ -771,7 +771,7 @@ fn visit_terminator(&mut self, terminator: &mut Terminator<'tcx>, loc: Location) *target = self.update_target(*target); } TerminatorKind::SwitchInt { ref mut targets, .. } => { - for tgt in targets { + for tgt in targets.all_targets_mut() { *tgt = self.update_target(*tgt); } } diff --git a/compiler/rustc_mir/src/transform/match_branches.rs b/compiler/rustc_mir/src/transform/match_branches.rs index dad3812c5cd..8b2d6b09aa8 100644 --- a/compiler/rustc_mir/src/transform/match_branches.rs +++ b/compiler/rustc_mir/src/transform/match_branches.rs @@ -46,10 +46,13 @@ fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) { discr: Operand::Copy(ref place) | Operand::Move(ref place), switch_ty, ref targets, - ref values, .. - } if targets.len() == 2 && values.len() == 1 && targets[0] != targets[1] => { - (place, values[0], switch_ty, targets[0], targets[1]) + } if targets.iter().len() == 1 => { + let (value, target) = targets.iter().next().unwrap(); + if target == targets.otherwise() { + continue; + } + (place, value, switch_ty, target, targets.otherwise()) } // Only optimize switch int statements _ => continue, diff --git a/compiler/rustc_mir/src/transform/simplify_branches.rs b/compiler/rustc_mir/src/transform/simplify_branches.rs index 161856a38ee..5f63c03993d 100644 --- a/compiler/rustc_mir/src/transform/simplify_branches.rs +++ b/compiler/rustc_mir/src/transform/simplify_branches.rs @@ -29,17 +29,16 @@ fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) { TerminatorKind::SwitchInt { discr: Operand::Constant(ref c), switch_ty, - ref values, ref targets, .. } => { let constant = c.literal.try_eval_bits(tcx, param_env, switch_ty); if let Some(constant) = constant { - let (otherwise, targets) = targets.split_last().unwrap(); - let mut ret = TerminatorKind::Goto { target: *otherwise }; - for (&v, t) in values.iter().zip(targets.iter()) { + let otherwise = targets.otherwise(); + let mut ret = TerminatorKind::Goto { target: otherwise }; + for (v, t) in targets.iter() { if v == constant { - ret = TerminatorKind::Goto { target: *t }; + ret = TerminatorKind::Goto { target: t }; break; } } diff --git a/compiler/rustc_mir/src/transform/simplify_comparison_integral.rs b/compiler/rustc_mir/src/transform/simplify_comparison_integral.rs index 9f837cf78a6..50f5fbb3bc2 100644 --- a/compiler/rustc_mir/src/transform/simplify_comparison_integral.rs +++ b/compiler/rustc_mir/src/transform/simplify_comparison_integral.rs @@ -1,8 +1,10 @@ +use std::iter; + use super::MirPass; use rustc_middle::{ mir::{ interpret::Scalar, BasicBlock, BinOp, Body, Operand, Place, Rvalue, Statement, - StatementKind, TerminatorKind, + StatementKind, SwitchTargets, TerminatorKind, }, ty::{Ty, TyCtxt}, }; @@ -43,19 +45,21 @@ fn run_pass(&self, _: TyCtxt<'tcx>, body: &mut Body<'tcx>) { Scalar::Ptr(_) => continue, }; const FALSE: u128 = 0; - let mut new_targets = opt.targets.clone(); - let first_is_false_target = opt.values[0] == FALSE; + + let mut new_targets = opt.targets; + let first_value = new_targets.iter().next().unwrap().0; + let first_is_false_target = first_value == FALSE; match opt.op { BinOp::Eq => { // if the assignment was Eq we want the true case to be first if first_is_false_target { - new_targets.swap(0, 1); + new_targets.all_targets_mut().swap(0, 1); } } BinOp::Ne => { // if the assignment was Ne we want the false case to be first if !first_is_false_target { - new_targets.swap(0, 1); + new_targets.all_targets_mut().swap(0, 1); } } _ => unreachable!(), @@ -96,7 +100,7 @@ fn run_pass(&self, _: TyCtxt<'tcx>, body: &mut Body<'tcx>) { } storage_deads_to_remove.push((stmt_idx, opt.bb_idx)); // if we have StorageDeads to remove then make sure to insert them at the top of each target - for bb_idx in new_targets.iter() { + for bb_idx in new_targets.all_targets() { storage_deads_to_insert.push(( *bb_idx, Statement { @@ -107,13 +111,18 @@ fn run_pass(&self, _: TyCtxt<'tcx>, body: &mut Body<'tcx>) { } } - let terminator = bb.terminator_mut(); + let [bb_cond, bb_otherwise] = match new_targets.all_targets() { + [a, b] => [*a, *b], + e => bug!("expected 2 switch targets, got: {:?}", e), + }; + + let targets = SwitchTargets::new(iter::once((new_value, bb_cond)), bb_otherwise); + let terminator = bb.terminator_mut(); terminator.kind = TerminatorKind::SwitchInt { discr: Operand::Move(opt.to_switch_on), switch_ty: opt.branch_value_ty, - values: vec![new_value].into(), - targets: new_targets, + targets, }; } @@ -138,15 +147,13 @@ fn find_optimizations(&self) -> Vec> { .iter_enumerated() .filter_map(|(bb_idx, bb)| { // find switch - let (place_switched_on, values, targets, place_switched_on_moved) = match &bb - .terminator() - .kind - { - rustc_middle::mir::TerminatorKind::SwitchInt { - discr, values, targets, .. - } => Some((discr.place()?, values, targets, discr.is_move())), - _ => None, - }?; + let (place_switched_on, targets, place_switched_on_moved) = + match &bb.terminator().kind { + rustc_middle::mir::TerminatorKind::SwitchInt { discr, targets, .. } => { + Some((discr.place()?, targets, discr.is_move())) + } + _ => None, + }?; // find the statement that assigns the place being switched on bb.statements.iter().enumerate().rev().find_map(|(stmt_idx, stmt)| { @@ -167,7 +174,6 @@ fn find_optimizations(&self) -> Vec> { branch_value_scalar, branch_value_ty, op: *op, - values: values.clone().into_owned(), targets: targets.clone(), }) } @@ -220,8 +226,6 @@ struct OptimizationInfo<'tcx> { branch_value_ty: Ty<'tcx>, /// Either Eq or Ne op: BinOp, - /// Current values used in the switch target. This needs to be replaced with the branch_value - values: Vec, /// Current targets used in the switch - targets: Vec, + targets: SwitchTargets<'tcx>, } diff --git a/compiler/rustc_mir/src/transform/simplify_try.rs b/compiler/rustc_mir/src/transform/simplify_try.rs index a4e7a5a9453..27bb1def726 100644 --- a/compiler/rustc_mir/src/transform/simplify_try.rs +++ b/compiler/rustc_mir/src/transform/simplify_try.rs @@ -576,15 +576,13 @@ fn find(&self) -> Vec { .iter_enumerated() .filter_map(|(bb_idx, bb)| { let (discr_switched_on, targets_and_values) = match &bb.terminator().kind { - TerminatorKind::SwitchInt { targets, discr, values, .. } => { - // if values.len() == targets.len() - 1, we need to include None where no value is present - // such that the zip does not throw away targets. If no `otherwise` case is in targets, the zip will simply throw away the added None - let values_extended = values.iter().map(|x|Some(*x)).chain(once(None)); - let targets_and_values:Vec<_> = targets.iter().zip(values_extended) - .map(|(target, value)| SwitchTargetAndValue{target:*target, value}) + TerminatorKind::SwitchInt { targets, discr, .. } => { + let targets_and_values: Vec<_> = targets.iter() + .map(|(val, target)| SwitchTargetAndValue { target, value: Some(val) }) + .chain(once(SwitchTargetAndValue { target: targets.otherwise(), value: None })) .collect(); - assert_eq!(targets.len(), targets_and_values.len()); - (discr, targets_and_values)}, + (discr, targets_and_values) + }, _ => return None, }; diff --git a/compiler/rustc_mir/src/transform/uninhabited_enum_branching.rs b/compiler/rustc_mir/src/transform/uninhabited_enum_branching.rs index 87906e83ed5..465832c89fd 100644 --- a/compiler/rustc_mir/src/transform/uninhabited_enum_branching.rs +++ b/compiler/rustc_mir/src/transform/uninhabited_enum_branching.rs @@ -3,7 +3,8 @@ use crate::transform::MirPass; use rustc_data_structures::stable_set::FxHashSet; use rustc_middle::mir::{ - BasicBlock, BasicBlockData, Body, Local, Operand, Rvalue, StatementKind, TerminatorKind, + BasicBlock, BasicBlockData, Body, Local, Operand, Rvalue, StatementKind, SwitchTargets, + TerminatorKind, }; use rustc_middle::ty::layout::TyAndLayout; use rustc_middle::ty::{Ty, TyCtxt}; @@ -101,21 +102,15 @@ fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) { trace!("allowed_variants = {:?}", allowed_variants); - if let TerminatorKind::SwitchInt { values, targets, .. } = + if let TerminatorKind::SwitchInt { targets, .. } = &mut body.basic_blocks_mut()[bb].terminator_mut().kind { - // take otherwise out early - let otherwise = targets.pop().unwrap(); - assert_eq!(targets.len(), values.len()); - let mut i = 0; - targets.retain(|_| { - let keep = allowed_variants.contains(&values[i]); - i += 1; - keep - }); - targets.push(otherwise); - - values.to_mut().retain(|var| allowed_variants.contains(var)); + let new_targets = SwitchTargets::new( + targets.iter().filter(|(val, _)| allowed_variants.contains(val)), + targets.otherwise(), + ); + + *targets = new_targets; } else { unreachable!() } diff --git a/compiler/rustc_mir/src/transform/unreachable_prop.rs b/compiler/rustc_mir/src/transform/unreachable_prop.rs index c6426a06ea1..f6d39dae342 100644 --- a/compiler/rustc_mir/src/transform/unreachable_prop.rs +++ b/compiler/rustc_mir/src/transform/unreachable_prop.rs @@ -7,7 +7,6 @@ use rustc_data_structures::fx::{FxHashMap, FxHashSet}; use rustc_middle::mir::*; use rustc_middle::ty::TyCtxt; -use std::borrow::Cow; pub struct UnreachablePropagation; @@ -69,14 +68,15 @@ fn remove_successors( { let terminator = match *terminator_kind { TerminatorKind::Goto { target } if predicate(target) => TerminatorKind::Unreachable, - TerminatorKind::SwitchInt { ref discr, switch_ty, ref values, ref targets } => { - let original_targets_len = targets.len(); - let (otherwise, targets) = targets.split_last().unwrap(); + TerminatorKind::SwitchInt { ref discr, switch_ty, ref targets } => { + let otherwise = targets.otherwise(); + + let original_targets_len = targets.iter().len() + 1; let (mut values, mut targets): (Vec<_>, Vec<_>) = - values.iter().zip(targets.iter()).filter(|(_, &t)| !predicate(t)).unzip(); + targets.iter().filter(|(_, bb)| !predicate(*bb)).unzip(); - if !predicate(*otherwise) { - targets.push(*otherwise); + if !predicate(otherwise) { + targets.push(otherwise); } else { values.pop(); } @@ -91,8 +91,10 @@ fn remove_successors( TerminatorKind::SwitchInt { discr: discr.clone(), switch_ty, - values: Cow::from(values), - targets, + targets: SwitchTargets::new( + values.iter().copied().zip(targets.iter().copied()), + *targets.last().unwrap(), + ), } } else { return None; diff --git a/compiler/rustc_mir/src/transform/validate.rs b/compiler/rustc_mir/src/transform/validate.rs index cf51e86c5bc..48477f60ef7 100644 --- a/compiler/rustc_mir/src/transform/validate.rs +++ b/compiler/rustc_mir/src/transform/validate.rs @@ -334,7 +334,7 @@ fn visit_terminator(&mut self, terminator: &Terminator<'tcx>, location: Location TerminatorKind::Goto { target } => { self.check_edge(location, *target, EdgeKind::Normal); } - TerminatorKind::SwitchInt { targets, values, switch_ty, discr } => { + TerminatorKind::SwitchInt { targets, switch_ty, discr } => { let ty = discr.ty(&self.body.local_decls, self.tcx); if ty != *switch_ty { self.fail( @@ -345,19 +345,10 @@ fn visit_terminator(&mut self, terminator: &Terminator<'tcx>, location: Location ), ); } - if targets.len() != values.len() + 1 { - self.fail( - location, - format!( - "encountered `SwitchInt` terminator with {} values, but {} targets (should be values+1)", - values.len(), - targets.len(), - ), - ); - } - for target in targets { - self.check_edge(location, *target, EdgeKind::Normal); + for (_, target) in targets.iter() { + self.check_edge(location, target, EdgeKind::Normal); } + self.check_edge(location, targets.otherwise(), EdgeKind::Normal); } TerminatorKind::Drop { target, unwind, .. } => { self.check_edge(location, *target, EdgeKind::Normal); diff --git a/compiler/rustc_mir/src/util/elaborate_drops.rs b/compiler/rustc_mir/src/util/elaborate_drops.rs index 43fa15d7e49..4a48b335ce9 100644 --- a/compiler/rustc_mir/src/util/elaborate_drops.rs +++ b/compiler/rustc_mir/src/util/elaborate_drops.rs @@ -588,8 +588,10 @@ fn adt_switch_block( kind: TerminatorKind::SwitchInt { discr: Operand::Move(discr), switch_ty: discr_ty, - values: From::from(values.to_owned()), - targets: blocks, + targets: SwitchTargets::new( + values.iter().copied().zip(blocks.iter().copied()), + *blocks.last().unwrap(), + ), }, }), is_cleanup: unwind.is_cleanup(), @@ -758,7 +760,7 @@ fn open_drop_for_array(&mut self, ety: Ty<'tcx>, opt_size: Option) -> Basic let elem_size = Place::from(self.new_temp(tcx.types.usize)); let len = Place::from(self.new_temp(tcx.types.usize)); - static USIZE_SWITCH_ZERO: &[u128] = &[0]; + static USIZE_SWITCH_ZERO: &[u128; 1] = &[0]; let base_block = BasicBlockData { statements: vec![ @@ -771,11 +773,11 @@ fn open_drop_for_array(&mut self, ety: Ty<'tcx>, opt_size: Option) -> Basic kind: TerminatorKind::SwitchInt { discr: move_(elem_size), switch_ty: tcx.types.usize, - values: From::from(USIZE_SWITCH_ZERO), - targets: vec![ + targets: SwitchTargets::static_if( + USIZE_SWITCH_ZERO, self.drop_loop_pair(ety, false, len), self.drop_loop_pair(ety, true, len), - ], + ), }, }), }; diff --git a/compiler/rustc_mir_build/src/build/matches/test.rs b/compiler/rustc_mir_build/src/build/matches/test.rs index 02dcf0394f6..c4191900147 100644 --- a/compiler/rustc_mir_build/src/build/matches/test.rs +++ b/compiler/rustc_mir_build/src/build/matches/test.rs @@ -167,48 +167,42 @@ pub(super) fn perform_test( let target_blocks = make_target_blocks(self); // Variants is a BitVec of indexes into adt_def.variants. let num_enum_variants = adt_def.variants.len(); - let used_variants = variants.count(); debug_assert_eq!(target_blocks.len(), num_enum_variants + 1); let otherwise_block = *target_blocks.last().unwrap(); - let mut targets = Vec::with_capacity(used_variants + 1); - let mut values = Vec::with_capacity(used_variants); let tcx = self.hir.tcx(); - for (idx, discr) in adt_def.discriminants(tcx) { - if variants.contains(idx) { - debug_assert_ne!( - target_blocks[idx.index()], - otherwise_block, - "no canididates for tested discriminant: {:?}", - discr, - ); - values.push(discr.val); - targets.push(target_blocks[idx.index()]); - } else { - debug_assert_eq!( - target_blocks[idx.index()], - otherwise_block, - "found canididates for untested discriminant: {:?}", - discr, - ); - } - } - targets.push(otherwise_block); - debug!( - "num_enum_variants: {}, tested variants: {:?}, variants: {:?}", - num_enum_variants, values, variants + let switch_targets = SwitchTargets::new( + adt_def.discriminants(tcx).filter_map(|(idx, discr)| { + if variants.contains(idx) { + debug_assert_ne!( + target_blocks[idx.index()], + otherwise_block, + "no canididates for tested discriminant: {:?}", + discr, + ); + Some((discr.val, target_blocks[idx.index()])) + } else { + debug_assert_eq!( + target_blocks[idx.index()], + otherwise_block, + "found canididates for untested discriminant: {:?}", + discr, + ); + None + } + }), + otherwise_block, ); + debug!("num_enum_variants: {}, variants: {:?}", num_enum_variants, variants); let discr_ty = adt_def.repr.discr_type().to_ty(tcx); let discr = self.temp(discr_ty, test.span); self.cfg.push_assign(block, source_info, discr, Rvalue::Discriminant(place)); - assert_eq!(values.len() + 1, targets.len()); self.cfg.terminate( block, source_info, TerminatorKind::SwitchInt { discr: Operand::Move(discr), switch_ty: discr_ty, - values: From::from(values), - targets, + targets: switch_targets, }, ); } @@ -230,11 +224,15 @@ pub(super) fn perform_test( } else { // The switch may be inexhaustive so we have a catch all block debug_assert_eq!(options.len() + 1, target_blocks.len()); + let otherwise_block = *target_blocks.last().unwrap(); + let switch_targets = SwitchTargets::new( + options.values().copied().zip(target_blocks), + otherwise_block, + ); TerminatorKind::SwitchInt { discr: Operand::Copy(place), switch_ty, - values: options.values().copied().collect(), - targets: target_blocks, + targets: switch_targets, } }; self.cfg.terminate(block, source_info, terminator); diff --git a/src/tools/clippy/clippy_lints/src/utils/qualify_min_const_fn.rs b/src/tools/clippy/clippy_lints/src/utils/qualify_min_const_fn.rs index 1b4f2034272..7cb7d0a26b6 100644 --- a/src/tools/clippy/clippy_lints/src/utils/qualify_min_const_fn.rs +++ b/src/tools/clippy/clippy_lints/src/utils/qualify_min_const_fn.rs @@ -282,7 +282,6 @@ fn check_terminator(tcx: TyCtxt<'tcx>, body: &'a Body<'tcx>, terminator: &Termin TerminatorKind::SwitchInt { discr, switch_ty: _, - values: _, targets: _, } => check_operand(tcx, discr, span, body), -- 2.44.0