Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -4895,13 +4895,14 @@ /// Create a lookup table to use as a switch replacement with the contents /// of Values, using DefaultValue to fill any holes in the table. SwitchLookupTable( - Module &M, uint64_t TableSize, ConstantInt *Offset, + Module &M, uint64_t TableSize, ConstantInt *Offset, Type *MinTy, + IRBuilder<> &Builder, const SmallVectorImpl> &Values, Constant *DefaultValue, const DataLayout &DL, const StringRef &FuncName); /// Build instructions with Builder to retrieve the value at /// the position given by Index in the lookup table. - Value *BuildLookup(Value *Index, IRBuilder<> &Builder); + Value *BuildLookup(Value *Index, Type *MinTy, IRBuilder<> &Builder); /// Return true if a table with TableSize elements of /// type ElementType would fit in a target-legal register. @@ -4949,7 +4950,8 @@ } // end anonymous namespace SwitchLookupTable::SwitchLookupTable( - Module &M, uint64_t TableSize, ConstantInt *Offset, + Module &M, uint64_t TableSize, ConstantInt *Offset, Type *ValueType, + IRBuilder<> &Builder, const SmallVectorImpl> &Values, Constant *DefaultValue, const DataLayout &DL, const StringRef &FuncName) { assert(Values.size() && "Can't build lookup table without values!"); @@ -4958,17 +4960,31 @@ // If all values in the table are equal, this is that value. SingleValue = Values.begin()->second; - Type *ValueType = Values.begin()->second->getType(); - // Build up the table contents. SmallVector TableContents(TableSize); + uint64_t MinBitWidth; + bool DoTruncate = true; + IntegerType *ITy = nullptr; + if (ValueType) + ITy = dyn_cast(ValueType); + if (ITy) + MinBitWidth = ITy->getBitWidth(); + else + DoTruncate = false; for (size_t I = 0, E = Values.size(); I != E; ++I) { ConstantInt *CaseVal = Values[I].first; Constant *CaseRes = Values[I].second; - assert(CaseRes->getType() == ValueType); uint64_t Idx = (CaseVal->getValue() - Offset->getValue()).getLimitedValue(); - TableContents[Idx] = CaseRes; + ConstantInt *CaseResCst; + if (DoTruncate && (CaseResCst = dyn_cast(CaseRes))) + TableContents[Idx] = + ConstantInt::get(ValueType->getContext(), + CaseResCst->getValue().zextOrTrunc(MinBitWidth)); + else { + assert(CaseRes->getType() == ValueType); + TableContents[Idx] = CaseRes; + } if (CaseRes != SingleValue) SingleValue = nullptr; @@ -4978,10 +4994,18 @@ if (Values.size() < TableSize) { assert(DefaultValue && "Need a default value to fill the lookup table holes."); - assert(DefaultValue->getType() == ValueType); + Constant *DefaultValueTrunc; + ConstantInt *DV; + if (DoTruncate && (DV = dyn_cast(DefaultValue))) + DefaultValueTrunc = ConstantInt::get( + ValueType->getContext(), DV->getValue().zextOrTrunc(MinBitWidth)); + else { + assert(DefaultValue->getType() == Values[0].second->getType()); + DefaultValueTrunc = DefaultValue; + } for (uint64_t I = 0; I < TableSize; ++I) { if (!TableContents[I]) - TableContents[I] = DefaultValue; + TableContents[I] = DefaultValueTrunc; } if (DefaultValue != SingleValue) @@ -5024,8 +5048,14 @@ PrevVal = Val; } if (LinearMappingPossible) { - LinearOffset = cast(TableContents[0]); - LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev); + uint64_t OrigBitWidth = + Values.begin()->second->getType()->getIntegerBitWidth(); + LinearOffset = + ConstantInt::get(M.getContext(), cast(TableContents[0]) + ->getValue() + .zextOrSelf(OrigBitWidth)); + LinearMultiplier = + ConstantInt::get(M.getContext(), DistToPrev.zextOrSelf(OrigBitWidth)); Kind = LinearMapKind; ++NumLinearMaps; return; @@ -5065,11 +5095,14 @@ Kind = ArrayKind; } -Value *SwitchLookupTable::BuildLookup(Value *Index, IRBuilder<> &Builder) { +Value *SwitchLookupTable::BuildLookup(Value *Index, Type *OrigTy, + IRBuilder<> &Builder) { switch (Kind) { case SingleValueKind: + assert(SingleValue->getType() == OrigTy); return SingleValue; case LinearMapKind: { + assert(LinearMultiplier->getType() == OrigTy); // Derive the result value from the input value. Value *Result = Builder.CreateIntCast(Index, LinearMultiplier->getType(), false, "switch.idx.cast"); @@ -5097,7 +5130,9 @@ Value *DownShifted = Builder.CreateLShr(BitMap, ShiftAmt, "switch.downshift"); // Mask off. - return Builder.CreateTrunc(DownShifted, BitMapElementTy, "switch.masked"); + Value *WrongWidth = + Builder.CreateTrunc(DownShifted, BitMapElementTy, "switch.masked"); + return Builder.CreateZExtOrBitCast(WrongWidth, OrigTy, "switch.zext"); } case ArrayKind: { // Make sure the table index will not overflow when treated as signed. @@ -5112,9 +5147,10 @@ Value *GEPIndices[] = {Builder.getInt32(0), Index}; Value *GEP = Builder.CreateInBoundsGEP(Array->getValueType(), Array, GEPIndices, "switch.gep"); - return Builder.CreateLoad( + Value *WrongWidth = Builder.CreateLoad( cast(Array->getValueType())->getElementType(), GEP, "switch.load"); + return Builder.CreateZExtOrBitCast(WrongWidth, OrigTy, "switch.zext"); } } llvm_unreachable("Unknown lookup table kind!"); @@ -5137,21 +5173,16 @@ /// Determine whether a lookup table should be built for this switch, based on /// the number of cases, size of the table, and the types of the results. -static bool -ShouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize, - const TargetTransformInfo &TTI, const DataLayout &DL, - const SmallDenseMap &ResultTypes) { +static bool ShouldBuildLookupTable( + SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI, + const DataLayout &DL, + const SmallDenseMap> &ResultTypes) { if (SI->getNumCases() > TableSize || TableSize >= UINT64_MAX / 10) return false; // TableSize overflowed, or mul below might overflow. bool AllTablesFitInRegister = true; - bool HasIllegalType = false; for (const auto &I : ResultTypes) { - Type *Ty = I.second; - - // Saturate this flag to true. - HasIllegalType = HasIllegalType || !TTI.isTypeLegal(Ty); - + Type *Ty = I.second.second; // Saturate this flag to false. AllTablesFitInRegister = AllTablesFitInRegister && @@ -5160,7 +5191,7 @@ // If both flags saturate, we're done. NOTE: This *only* works with // saturating flags, and all flags have to saturate first due to the // non-deterministic behavior of iterating over a dense map. - if (HasIllegalType && !AllTablesFitInRegister) + if (!AllTablesFitInRegister) break; } @@ -5168,10 +5199,6 @@ if (AllTablesFitInRegister) return true; - // Don't build a table that doesn't fit in-register if it has illegal types. - if (HasIllegalType) - return false; - // The table density should be at least 40%. This is the same criterion as for // jump tables, see SelectionDAGBuilder::handleJTSwitchCase. // FIXME: Find the best cut-off. @@ -5301,7 +5328,8 @@ SmallDenseMap ResultLists; SmallDenseMap DefaultResults; - SmallDenseMap ResultTypes; + // Extend-to type (original type), type in table + SmallDenseMap> ResultTypes; SmallVector PHIs; for (SwitchInst::CaseIt E = SI->case_end(); CI != E; ++CI) { @@ -5328,9 +5356,31 @@ } } - // Keep track of the result types. + // Keep track of the result types, and calculate the smallest type we can use. for (PHINode *PHI : PHIs) { - ResultTypes[PHI] = ResultLists[PHI][0].second->getType(); + ResultTypes[PHI].first = ResultLists[PHI][0].second->getType(); + + uint64_t MaxVal = 0; + for (auto &Res : ResultLists[PHI]) { + ConstantInt *CstI = dyn_cast(Res.second); + if (!CstI) + continue; // This is an undef + MaxVal = std::max(MaxVal, CstI->getValue().getLimitedValue()); + } + if (MaxVal == UINT64_MAX || MaxVal == 0) { + // Compiler Explorer show that if the PHI is always 0 (or undef), it is + // pruned, so let's not worry about it. + ResultTypes[PHI].second = ResultTypes[PHI].first; + continue; + } + unsigned NewBitWidth = 64 - countLeadingZeros(MaxVal); + IntegerType *NewType = IntegerType::get(SI->getContext(), NewBitWidth); + ResultTypes[PHI].second = NewType; + if (ResultTypes[PHI].first->getIntegerBitWidth() <= NewBitWidth) { + // Can't truncate this type + assert(ResultTypes[PHI].first->getIntegerBitWidth() == NewBitWidth); + continue; + } } uint64_t NumResults = ResultLists[PHIs[0]].size(); @@ -5460,9 +5510,11 @@ ConstantInt *Base = NeedMask ? MinCaseVal : ConstantInt::get(Mod.getContext(), APInt(CaseSize, 0)); - SwitchLookupTable Table(Mod, TableSize, Base, ResultList, DV, DL, FuncName); + SwitchLookupTable Table(Mod, TableSize, Base, ResultTypes[PHI].second, + Builder, ResultList, DV, DL, FuncName); - Value *Result = Table.BuildLookup(TableIndex, Builder); + Value *Result = + Table.BuildLookup(TableIndex, ResultTypes[PHI].first, Builder); // If the result is used to return immediately from the function, we want to // do that right here. Index: test/Transforms/SimplifyCFG/ARM/switch-to-lookup-table.ll =================================================================== --- test/Transforms/SimplifyCFG/ARM/switch-to-lookup-table.ll +++ test/Transforms/SimplifyCFG/ARM/switch-to-lookup-table.ll @@ -28,9 +28,10 @@ ; CHECK-NEXT: [[TMP0:%.*]] = icmp ult i32 [[N:%.*]], 3 ; CHECK-NEXT: br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]] ; CHECK: switch.lookup: -; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i32], [3 x i32]* @switch.table.test1, i32 0, i32 [[N]] -; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]] -; CHECK-NEXT: ret i32 [[SWITCH_LOAD]] +; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i14], [3 x i14]* @switch.table.test1, i32 0, i32 [[N]] +; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load i14, i14* [[SWITCH_GEP]] +; CHECK-NEXT: [[SWITCH_ZEXT:%.*]] = zext i14 [[SWITCH_LOAD]] to i32 +; CHECK-NEXT: ret i32 [[SWITCH_ZEXT]] ; CHECK: return: ; CHECK-NEXT: ret i32 15498 ; @@ -65,33 +66,16 @@ define i32* @test2(i32 %n) { -; ENABLE-LABEL: @test2( -; ENABLE-NEXT: entry: -; ENABLE-NEXT: [[TMP0:%.*]] = icmp ult i32 [[N:%.*]], 3 -; ENABLE-NEXT: br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]] -; ENABLE: switch.lookup: -; ENABLE-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i32*], [3 x i32*]* @switch.table.test2, i32 0, i32 [[N]] -; ENABLE-NEXT: [[SWITCH_LOAD:%.*]] = load i32*, i32** [[SWITCH_GEP]] -; ENABLE-NEXT: ret i32* [[SWITCH_LOAD]] -; ENABLE: return: -; ENABLE-NEXT: ret i32* @c4 -; -; DISABLE-LABEL: @test2( -; DISABLE-NEXT: entry: -; DISABLE-NEXT: switch i32 [[N:%.*]], label [[SW_DEFAULT:%.*]] [ -; DISABLE-NEXT: i32 0, label [[RETURN:%.*]] -; DISABLE-NEXT: i32 1, label [[SW_BB1:%.*]] -; DISABLE-NEXT: i32 2, label [[SW_BB2:%.*]] -; DISABLE-NEXT: ] -; DISABLE: sw.bb1: -; DISABLE-NEXT: br label [[RETURN]] -; DISABLE: sw.bb2: -; DISABLE-NEXT: br label [[RETURN]] -; DISABLE: sw.default: -; DISABLE-NEXT: br label [[RETURN]] -; DISABLE: return: -; DISABLE-NEXT: [[RETVAL_0:%.*]] = phi i32* [ @c4, [[SW_DEFAULT]] ], [ @c3, [[SW_BB2]] ], [ @c2, [[SW_BB1]] ], [ @c1, [[ENTRY:%.*]] ] -; DISABLE-NEXT: ret i32* [[RETVAL_0]] +; CHECK-LABEL: @test2( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[TMP0:%.*]] = icmp ult i32 [[N:%.*]], 3 +; CHECK-NEXT: br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]] +; CHECK: switch.lookup: +; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i32*], [3 x i32*]* @switch.table.test2, i32 0, i32 [[N]] +; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load i32*, i32** [[SWITCH_GEP]] +; CHECK-NEXT: ret i32* [[SWITCH_LOAD]] +; CHECK: return: +; CHECK-NEXT: ret i32* @c4 ; entry: switch i32 %n, label %sw.default [ @@ -123,33 +107,16 @@ @g4 = external global i32, align 4 define i32* @test3(i32 %n) { -; ENABLE-LABEL: @test3( -; ENABLE-NEXT: entry: -; ENABLE-NEXT: [[TMP0:%.*]] = icmp ult i32 [[N:%.*]], 3 -; ENABLE-NEXT: br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]] -; ENABLE: switch.lookup: -; ENABLE-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i32*], [3 x i32*]* @switch.table.test3, i32 0, i32 [[N]] -; ENABLE-NEXT: [[SWITCH_LOAD:%.*]] = load i32*, i32** [[SWITCH_GEP]] -; ENABLE-NEXT: ret i32* [[SWITCH_LOAD]] -; ENABLE: return: -; ENABLE-NEXT: ret i32* @g4 -; -; DISABLE-LABEL: @test3( -; DISABLE-NEXT: entry: -; DISABLE-NEXT: switch i32 [[N:%.*]], label [[SW_DEFAULT:%.*]] [ -; DISABLE-NEXT: i32 0, label [[RETURN:%.*]] -; DISABLE-NEXT: i32 1, label [[SW_BB1:%.*]] -; DISABLE-NEXT: i32 2, label [[SW_BB2:%.*]] -; DISABLE-NEXT: ] -; DISABLE: sw.bb1: -; DISABLE-NEXT: br label [[RETURN]] -; DISABLE: sw.bb2: -; DISABLE-NEXT: br label [[RETURN]] -; DISABLE: sw.default: -; DISABLE-NEXT: br label [[RETURN]] -; DISABLE: return: -; DISABLE-NEXT: [[RETVAL_0:%.*]] = phi i32* [ @g4, [[SW_DEFAULT]] ], [ @g3, [[SW_BB2]] ], [ @g2, [[SW_BB1]] ], [ @g1, [[ENTRY:%.*]] ] -; DISABLE-NEXT: ret i32* [[RETVAL_0]] +; CHECK-LABEL: @test3( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[TMP0:%.*]] = icmp ult i32 [[N:%.*]], 3 +; CHECK-NEXT: br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]] +; CHECK: switch.lookup: +; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i32*], [3 x i32*]* @switch.table.test3, i32 0, i32 [[N]] +; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load i32*, i32** [[SWITCH_GEP]] +; CHECK-NEXT: ret i32* [[SWITCH_LOAD]] +; CHECK: return: +; CHECK-NEXT: ret i32* @g4 ; entry: switch i32 %n, label %sw.default [ @@ -182,43 +149,25 @@ declare i32 @f5(i32, i32) define i32 @test4(i32 %a, i32 %b, i32 %c) { -; ENABLE-LABEL: @test4( -; ENABLE-NEXT: entry: -; ENABLE-NEXT: [[SWITCH_TABLEIDX:%.*]] = sub i32 [[A:%.*]], 1 -; ENABLE-NEXT: [[TMP0:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 3 -; ENABLE-NEXT: br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[COND_FALSE6:%.*]] -; ENABLE: cond.false6: -; ENABLE-NEXT: [[CMP7:%.*]] = icmp eq i32 [[A]], 4 -; ENABLE-NEXT: [[COND:%.*]] = select i1 [[CMP7]], i32 (i32, i32)* @f4, i32 (i32, i32)* @f5 -; ENABLE-NEXT: br label [[COND_END11:%.*]] -; ENABLE: switch.lookup: -; ENABLE-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i32 (i32, i32)*], [3 x i32 (i32, i32)*]* @switch.table.test4, i32 0, i32 [[SWITCH_TABLEIDX]] -; ENABLE-NEXT: [[SWITCH_LOAD:%.*]] = load i32 (i32, i32)*, i32 (i32, i32)** [[SWITCH_GEP]] -; ENABLE-NEXT: br label [[COND_END11]] -; ENABLE: cond.end11: -; ENABLE-NEXT: [[COND12:%.*]] = phi i32 (i32, i32)* [ [[COND]], [[COND_FALSE6]] ], [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ] -; ENABLE-NEXT: [[CALL:%.*]] = call i32 [[COND12]](i32 [[B:%.*]], i32 [[C:%.*]]) -; ENABLE-NEXT: ret i32 [[CALL]] -; -; DISABLE-LABEL: @test4( -; DISABLE-NEXT: entry: -; DISABLE-NEXT: switch i32 [[A:%.*]], label [[COND_FALSE6:%.*]] [ -; DISABLE-NEXT: i32 1, label [[COND_END11:%.*]] -; DISABLE-NEXT: i32 2, label [[COND_END11_FOLD_SPLIT:%.*]] -; DISABLE-NEXT: i32 3, label [[COND_END11_FOLD_SPLIT1:%.*]] -; DISABLE-NEXT: ] -; DISABLE: cond.false6: -; DISABLE-NEXT: [[CMP7:%.*]] = icmp eq i32 [[A]], 4 -; DISABLE-NEXT: [[COND:%.*]] = select i1 [[CMP7]], i32 (i32, i32)* @f4, i32 (i32, i32)* @f5 -; DISABLE-NEXT: br label [[COND_END11]] -; DISABLE: cond.end11.fold.split: -; DISABLE-NEXT: br label [[COND_END11]] -; DISABLE: cond.end11.fold.split1: -; DISABLE-NEXT: br label [[COND_END11]] -; DISABLE: cond.end11: -; DISABLE-NEXT: [[COND12:%.*]] = phi i32 (i32, i32)* [ @f1, [[ENTRY:%.*]] ], [ [[COND]], [[COND_FALSE6]] ], [ @f2, [[COND_END11_FOLD_SPLIT]] ], [ @f3, [[COND_END11_FOLD_SPLIT1]] ] -; DISABLE-NEXT: [[CALL:%.*]] = call i32 [[COND12]](i32 [[B:%.*]], i32 [[C:%.*]]) -; DISABLE-NEXT: ret i32 [[CALL]] +; CHECK-LABEL: @test4( +; CHECK-NEXT: entry: +; CHECK-NEXT: switch i32 [[A:%.*]], label [[COND_FALSE6:%.*]] [ +; CHECK-NEXT: i32 1, label [[COND_END11:%.*]] +; CHECK-NEXT: i32 2, label [[COND_END11_FOLD_SPLIT:%.*]] +; CHECK-NEXT: i32 3, label [[COND_END11_FOLD_SPLIT1:%.*]] +; CHECK-NEXT: ] +; CHECK: cond.false6: +; CHECK-NEXT: [[CMP7:%.*]] = icmp eq i32 [[A]], 4 +; CHECK-NEXT: [[COND:%.*]] = select i1 [[CMP7]], i32 (i32, i32)* @f4, i32 (i32, i32)* @f5 +; CHECK-NEXT: br label [[COND_END11]] +; CHECK: cond.end11.fold.split: +; CHECK-NEXT: br label [[COND_END11]] +; CHECK: cond.end11.fold.split1: +; CHECK-NEXT: br label [[COND_END11]] +; CHECK: cond.end11: +; CHECK-NEXT: [[COND12:%.*]] = phi i32 (i32, i32)* [ @f1, [[ENTRY:%.*]] ], [ [[COND]], [[COND_FALSE6]] ], [ @f2, [[COND_END11_FOLD_SPLIT]] ], [ @f3, [[COND_END11_FOLD_SPLIT1]] ] +; CHECK-NEXT: [[CALL:%.*]] = call i32 [[COND12]](i32 [[B:%.*]], i32 [[C:%.*]]) +; CHECK-NEXT: ret i32 [[CALL]] ; entry: %cmp = icmp eq i32 %a, 1 Index: test/Transforms/SimplifyCFG/X86/switch-covered-bug.ll =================================================================== --- test/Transforms/SimplifyCFG/X86/switch-covered-bug.ll +++ test/Transforms/SimplifyCFG/X86/switch-covered-bug.ll @@ -12,12 +12,14 @@ ; CHECK-NEXT: [[TMP0:%.*]] = icmp ult i3 [[ARG:%.*]], -1 ; CHECK-NEXT: br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[DEFAULT:%.*]] ; CHECK: switch.lookup: -; CHECK-NEXT: [[SWITCH_TABLEIDX_ZEXT:%.*]] = zext i3 [[ARG]] to i4 -; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [7 x i64], [7 x i64]* @switch.table.test, i32 0, i4 [[SWITCH_TABLEIDX_ZEXT]] -; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load i64, i64* [[SWITCH_GEP]] +; CHECK-NEXT: [[SWITCH_CAST:%.*]] = zext i3 [[ARG]] to i28 +; CHECK-NEXT: [[SWITCH_SHIFTAMT:%.*]] = mul i28 [[SWITCH_CAST]], 4 +; CHECK-NEXT: [[SWITCH_DOWNSHIFT:%.*]] = lshr i28 129423864, [[SWITCH_SHIFTAMT]] +; CHECK-NEXT: [[SWITCH_MASKED:%.*]] = trunc i28 [[SWITCH_DOWNSHIFT]] to i4 +; CHECK-NEXT: [[SWITCH_ZEXT:%.*]] = zext i4 [[SWITCH_MASKED]] to i64 ; CHECK-NEXT: br label [[DEFAULT]] ; CHECK: Default: -; CHECK-NEXT: [[V1:%.*]] = phi i64 [ 8, [[ENTRY:%.*]] ], [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ] +; CHECK-NEXT: [[V1:%.*]] = phi i64 [ 8, [[ENTRY:%.*]] ], [ [[SWITCH_ZEXT]], [[SWITCH_LOOKUP]] ] ; CHECK-NEXT: [[V3:%.*]] = add i64 [[V1]], 0 ; CHECK-NEXT: ret i64 [[V3]] ; Index: test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll =================================================================== --- test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll +++ test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll @@ -122,14 +122,16 @@ ; CHECK-NEXT: [[TMP0:%.*]] = icmp ult i32 [[X:%.*]], 4 ; CHECK-NEXT: br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[SW_EPILOG:%.*]] ; CHECK: switch.lookup: -; CHECK-NEXT: [[SWITCH_SHIFTAMT:%.*]] = mul i32 [[X]], 8 -; CHECK-NEXT: [[SWITCH_DOWNSHIFT:%.*]] = lshr i32 89655594, [[SWITCH_SHIFTAMT]] -; CHECK-NEXT: [[SWITCH_MASKED:%.*]] = trunc i32 [[SWITCH_DOWNSHIFT]] to i8 +; CHECK-NEXT: [[SWITCH_CAST:%.*]] = trunc i32 [[X]] to i28 +; CHECK-NEXT: [[SWITCH_SHIFTAMT:%.*]] = mul i28 [[SWITCH_CAST]], 7 +; CHECK-NEXT: [[SWITCH_DOWNSHIFT:%.*]] = lshr i28 11928746, [[SWITCH_SHIFTAMT]] +; CHECK-NEXT: [[SWITCH_MASKED:%.*]] = trunc i28 [[SWITCH_DOWNSHIFT]] to i7 +; CHECK-NEXT: [[SWITCH_ZEXT:%.*]] = zext i7 [[SWITCH_MASKED]] to i8 ; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x float], [4 x float]* @switch.table.h, i32 0, i32 [[X]] ; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load float, float* [[SWITCH_GEP]] ; CHECK-NEXT: br label [[SW_EPILOG]] ; CHECK: sw.epilog: -; CHECK-NEXT: [[A_0:%.*]] = phi i8 [ [[SWITCH_MASKED]], [[SWITCH_LOOKUP]] ], [ 7, [[ENTRY:%.*]] ] +; CHECK-NEXT: [[A_0:%.*]] = phi i8 [ [[SWITCH_ZEXT]], [[SWITCH_LOOKUP]] ], [ 7, [[ENTRY:%.*]] ] ; CHECK-NEXT: [[B_0:%.*]] = phi float [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 0x4023FAE140000000, [[ENTRY]] ] ; CHECK-NEXT: call void @dummy(i8 signext [[A_0]], float [[B_0]]) ; CHECK-NEXT: ret void @@ -208,9 +210,12 @@ ; CHECK-NEXT: [[TMP0:%.*]] = icmp ult i32 [[X:%.*]], 4 ; CHECK-NEXT: br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[SW_EPILOG:%.*]] ; CHECK: switch.lookup: -; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i32], [4 x i32]* @switch.table.earlyreturncrash, i32 0, i32 [[X]] -; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]] -; CHECK-NEXT: ret i32 [[SWITCH_LOAD]] +; CHECK-NEXT: [[SWITCH_CAST:%.*]] = trunc i32 [[X]] to i28 +; CHECK-NEXT: [[SWITCH_SHIFTAMT:%.*]] = mul i28 [[SWITCH_CAST]], 7 +; CHECK-NEXT: [[SWITCH_DOWNSHIFT:%.*]] = lshr i28 11928746, [[SWITCH_SHIFTAMT]] +; CHECK-NEXT: [[SWITCH_MASKED:%.*]] = trunc i28 [[SWITCH_DOWNSHIFT]] to i7 +; CHECK-NEXT: [[SWITCH_ZEXT:%.*]] = zext i7 [[SWITCH_MASKED]] to i32 +; CHECK-NEXT: ret i32 [[SWITCH_ZEXT]] ; CHECK: sw.epilog: ; CHECK-NEXT: ret i32 7 ; @@ -382,9 +387,10 @@ ; CHECK-NEXT: [[TMP0:%.*]] = icmp ult i32 [[SPEC_SELECT]], 200 ; CHECK-NEXT: br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]] ; CHECK: switch.lookup: -; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [200 x i32], [200 x i32]* @switch.table.large, i32 0, i32 [[SPEC_SELECT]] -; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]] -; CHECK-NEXT: ret i32 [[SWITCH_LOAD]] +; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [200 x i16], [200 x i16]* @switch.table.large, i32 0, i32 [[SPEC_SELECT]] +; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load i16, i16* [[SWITCH_GEP]] +; CHECK-NEXT: [[SWITCH_ZEXT:%.*]] = zext i16 [[SWITCH_LOAD]] to i32 +; CHECK-NEXT: ret i32 [[SWITCH_ZEXT]] ; CHECK: return: ; CHECK-NEXT: ret i32 0 ; @@ -894,9 +900,12 @@ define i32 @unreachable_default(i32 %x) { ; CHECK-LABEL: @unreachable_default( ; CHECK-NEXT: entry: -; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i32], [4 x i32]* @switch.table.unreachable_default, i32 0, i32 [[X:%.*]] -; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]] -; CHECK-NEXT: ret i32 [[SWITCH_LOAD]] +; CHECK-NEXT: [[SWITCH_CAST:%.*]] = trunc i32 [[X:%.*]] to i24 +; CHECK-NEXT: [[SWITCH_SHIFTAMT:%.*]] = mul i24 [[SWITCH_CAST]], 6 +; CHECK-NEXT: [[SWITCH_DOWNSHIFT:%.*]] = lshr i24 531754, [[SWITCH_SHIFTAMT]] +; CHECK-NEXT: [[SWITCH_MASKED:%.*]] = trunc i24 [[SWITCH_DOWNSHIFT]] to i6 +; CHECK-NEXT: [[SWITCH_ZEXT:%.*]] = zext i6 [[SWITCH_MASKED]] to i32 +; CHECK-NEXT: ret i32 [[SWITCH_ZEXT]] ; entry: switch i32 %x, label %default [ @@ -923,26 +932,14 @@ ; CHECK-LABEL: @illegaltype( ; CHECK-NEXT: entry: ; CHECK-NEXT: [[TMP0:%.*]] = sub i32 [[C:%.*]], 42 -; CHECK-NEXT: switch i32 [[TMP0]], label [[SW_DEFAULT:%.*]] [ -; CHECK-NEXT: i32 0, label [[RETURN:%.*]] -; CHECK-NEXT: i32 1, label [[SW_BB1:%.*]] -; CHECK-NEXT: i32 2, label [[SW_BB2:%.*]] -; CHECK-NEXT: i32 3, label [[SW_BB3:%.*]] -; CHECK-NEXT: i32 4, label [[SW_BB4:%.*]] -; CHECK-NEXT: ] -; CHECK: sw.bb1: -; CHECK-NEXT: br label [[RETURN]] -; CHECK: sw.bb2: -; CHECK-NEXT: br label [[RETURN]] -; CHECK: sw.bb3: -; CHECK-NEXT: br label [[RETURN]] -; CHECK: sw.bb4: -; CHECK-NEXT: br label [[RETURN]] -; CHECK: sw.default: -; CHECK-NEXT: br label [[RETURN]] +; CHECK-NEXT: [[TMP1:%.*]] = icmp ult i32 [[TMP0]], 5 +; CHECK-NEXT: br i1 [[TMP1]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]] +; CHECK: switch.lookup: +; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [5 x i96], [5 x i96]* @switch.table.illegaltype, i32 0, i32 [[TMP0]] +; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load i96, i96* [[SWITCH_GEP]] +; CHECK-NEXT: ret i96 [[SWITCH_LOAD]] ; CHECK: return: -; CHECK-NEXT: [[RETVAL_0:%.*]] = phi i96 [ 15, [[SW_DEFAULT]] ], [ 27, [[SW_BB4]] ], [ -1, [[SW_BB3]] ], [ 0, [[SW_BB2]] ], [ 123, [[SW_BB1]] ], [ 55, [[ENTRY:%.*]] ] -; CHECK-NEXT: ret i96 [[RETVAL_0]] +; CHECK-NEXT: ret i96 15 ; entry: switch i32 %c, label %sw.default [ @@ -1079,9 +1076,12 @@ ; CHECK-NEXT: [[TMP0:%.*]] = icmp ult i32 [[C:%.*]], 3 ; CHECK-NEXT: br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]] ; CHECK: switch.lookup: -; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i32], [3 x i32]* @switch.table.threecases, i32 0, i32 [[C]] -; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]] -; CHECK-NEXT: ret i32 [[SWITCH_LOAD]] +; CHECK-NEXT: [[SWITCH_CAST:%.*]] = trunc i32 [[C]] to i12 +; CHECK-NEXT: [[SWITCH_SHIFTAMT:%.*]] = mul i12 [[SWITCH_CAST]], 4 +; CHECK-NEXT: [[SWITCH_DOWNSHIFT:%.*]] = lshr i12 1402, [[SWITCH_SHIFTAMT]] +; CHECK-NEXT: [[SWITCH_MASKED:%.*]] = trunc i12 [[SWITCH_DOWNSHIFT]] to i4 +; CHECK-NEXT: [[SWITCH_ZEXT:%.*]] = zext i4 [[SWITCH_MASKED]] to i32 +; CHECK-NEXT: ret i32 [[SWITCH_ZEXT]] ; CHECK: return: ; CHECK-NEXT: ret i32 3 ; @@ -1218,7 +1218,7 @@ ; CHECK-NEXT: br i1 [[TMP1]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]] ; CHECK: switch.lookup: ; CHECK-NEXT: [[SWITCH_IDX_CAST:%.*]] = trunc i32 [[TMP0]] to i8 -; CHECK-NEXT: [[SWITCH_IDX_MULT:%.*]] = mul i8 [[SWITCH_IDX_CAST]], -5 +; CHECK-NEXT: [[SWITCH_IDX_MULT:%.*]] = mul i8 [[SWITCH_IDX_CAST]], 27 ; CHECK-NEXT: [[SWITCH_OFFSET:%.*]] = add i8 [[SWITCH_IDX_MULT]], 18 ; CHECK-NEXT: ret i8 [[SWITCH_OFFSET]] ; CHECK: return: @@ -1556,12 +1556,14 @@ ; CHECK-NEXT: [[SWITCH_LOBIT:%.*]] = trunc i8 [[SWITCH_SHIFTED]] to i1 ; CHECK-NEXT: br i1 [[SWITCH_LOBIT]], label [[SWITCH_LOOKUP:%.*]], label [[L6]] ; CHECK: switch.lookup: -; CHECK-NEXT: [[SWITCH_TABLEIDX_ZEXT:%.*]] = zext i3 [[TMP2]] to i4 -; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [6 x i32], [6 x i32]* @switch.table.covered_switch_with_bit_tests, i32 0, i4 [[SWITCH_TABLEIDX_ZEXT]] -; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]] +; CHECK-NEXT: [[SWITCH_CAST:%.*]] = zext i3 [[TMP2]] to i12 +; CHECK-NEXT: [[SWITCH_SHIFTAMT:%.*]] = mul i12 [[SWITCH_CAST]], 2 +; CHECK-NEXT: [[SWITCH_DOWNSHIFT:%.*]] = lshr i12 -1371, [[SWITCH_SHIFTAMT]] +; CHECK-NEXT: [[SWITCH_MASKED:%.*]] = trunc i12 [[SWITCH_DOWNSHIFT]] to i2 +; CHECK-NEXT: [[SWITCH_ZEXT:%.*]] = zext i2 [[SWITCH_MASKED]] to i32 ; CHECK-NEXT: br label [[L6]] ; CHECK: l6: -; CHECK-NEXT: [[R:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 0, [[SWITCH_HOLE_CHECK]] ], [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ] +; CHECK-NEXT: [[R:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 0, [[SWITCH_HOLE_CHECK]] ], [ [[SWITCH_ZEXT]], [[SWITCH_LOOKUP]] ] ; CHECK-NEXT: ret i32 [[R]] ; entry: Index: test/Transforms/SimplifyCFG/rangereduce.ll =================================================================== --- test/Transforms/SimplifyCFG/rangereduce.ll +++ test/Transforms/SimplifyCFG/rangereduce.ll @@ -10,21 +10,15 @@ ; CHECK-NEXT: [[TMP2:%.*]] = lshr i32 [[TMP1]], 2 ; CHECK-NEXT: [[TMP3:%.*]] = shl i32 [[TMP1]], 30 ; CHECK-NEXT: [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]] -; CHECK-NEXT: switch i32 [[TMP4]], label [[DEF:%.*]] [ -; CHECK-NEXT: i32 0, label [[ONE:%.*]] -; CHECK-NEXT: i32 1, label [[TWO:%.*]] -; CHECK-NEXT: i32 2, label [[THREE:%.*]] -; CHECK-NEXT: i32 3, label [[THREE]] -; CHECK-NEXT: ] +; CHECK-NEXT: [[TMP5:%.*]] = icmp ult i32 [[TMP4]], 4 +; CHECK-NEXT: br i1 [[TMP5]], label [[SWITCH_LOOKUP:%.*]], label [[DEF:%.*]] +; CHECK: switch.lookup: +; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i17], [4 x i17]* @switch.table.test1, i32 0, i32 [[TMP4]] +; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load i17, i17* [[SWITCH_GEP]] +; CHECK-NEXT: [[SWITCH_ZEXT:%.*]] = zext i17 [[SWITCH_LOAD]] to i32 +; CHECK-NEXT: ret i32 [[SWITCH_ZEXT]] ; CHECK: def: -; CHECK-NEXT: [[MERGE:%.*]] = phi i32 [ 8867, [[TMP0:%.*]] ], [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ] -; CHECK-NEXT: ret i32 [[MERGE]] -; CHECK: one: -; CHECK-NEXT: br label [[DEF]] -; CHECK: two: -; CHECK-NEXT: br label [[DEF]] -; CHECK: three: -; CHECK-NEXT: br label [[DEF]] +; CHECK-NEXT: ret i32 8867 ; switch i32 %a, label %def [ i32 97, label %one @@ -198,21 +192,15 @@ ; CHECK-NEXT: [[TMP2:%.*]] = lshr i32 [[TMP1]], 2 ; CHECK-NEXT: [[TMP3:%.*]] = shl i32 [[TMP1]], 30 ; CHECK-NEXT: [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]] -; CHECK-NEXT: switch i32 [[TMP4]], label [[DEF:%.*]] [ -; CHECK-NEXT: i32 3, label [[ONE:%.*]] -; CHECK-NEXT: i32 2, label [[TWO:%.*]] -; CHECK-NEXT: i32 1, label [[THREE:%.*]] -; CHECK-NEXT: i32 0, label [[THREE]] -; CHECK-NEXT: ] +; CHECK-NEXT: [[TMP5:%.*]] = icmp ult i32 [[TMP4]], 4 +; CHECK-NEXT: br i1 [[TMP5]], label [[SWITCH_LOOKUP:%.*]], label [[DEF:%.*]] +; CHECK: switch.lookup: +; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i17], [4 x i17]* @switch.table.test6, i32 0, i32 [[TMP4]] +; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load i17, i17* [[SWITCH_GEP]] +; CHECK-NEXT: [[SWITCH_ZEXT:%.*]] = zext i17 [[SWITCH_LOAD]] to i32 +; CHECK-NEXT: ret i32 [[SWITCH_ZEXT]] ; CHECK: def: -; CHECK-NEXT: [[MERGE:%.*]] = phi i32 [ 8867, [[TMP0:%.*]] ], [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ] -; CHECK-NEXT: ret i32 [[MERGE]] -; CHECK: one: -; CHECK-NEXT: br label [[DEF]] -; CHECK: two: -; CHECK-NEXT: br label [[DEF]] -; CHECK: three: -; CHECK-NEXT: br label [[DEF]] +; CHECK-NEXT: ret i32 8867 ; switch i32 %a, label %def [ i32 -97, label %one @@ -273,21 +261,15 @@ ; CHECK-NEXT: [[TMP2:%.*]] = lshr i32 [[TMP1]], 2 ; CHECK-NEXT: [[TMP3:%.*]] = shl i32 [[TMP1]], 30 ; CHECK-NEXT: [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]] -; CHECK-NEXT: switch i32 [[TMP4]], label [[DEF:%.*]] [ -; CHECK-NEXT: i32 0, label [[ONE:%.*]] -; CHECK-NEXT: i32 1, label [[TWO:%.*]] -; CHECK-NEXT: i32 2, label [[THREE:%.*]] -; CHECK-NEXT: i32 4, label [[THREE]] -; CHECK-NEXT: ] +; CHECK-NEXT: [[TMP5:%.*]] = icmp ult i32 [[TMP4]], 5 +; CHECK-NEXT: br i1 [[TMP5]], label [[SWITCH_LOOKUP:%.*]], label [[DEF:%.*]] +; CHECK: switch.lookup: +; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [5 x i17], [5 x i17]* @switch.table.test8, i32 0, i32 [[TMP4]] +; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load i17, i17* [[SWITCH_GEP]] +; CHECK-NEXT: [[SWITCH_ZEXT:%.*]] = zext i17 [[SWITCH_LOAD]] to i32 +; CHECK-NEXT: ret i32 [[SWITCH_ZEXT]] ; CHECK: def: -; CHECK-NEXT: [[MERGE:%.*]] = phi i32 [ 8867, [[TMP0:%.*]] ], [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ] -; CHECK-NEXT: ret i32 [[MERGE]] -; CHECK: one: -; CHECK-NEXT: br label [[DEF]] -; CHECK: two: -; CHECK-NEXT: br label [[DEF]] -; CHECK: three: -; CHECK-NEXT: br label [[DEF]] +; CHECK-NEXT: ret i32 8867 ; switch i32 %a, label %def [ i32 97, label %one