From: Benjamin Kramer Date: Mon, 7 Feb 2011 22:37:28 +0000 (+0000) Subject: SimplifyCFG: Track the number of used icmps when turning a icmp chain into a switch... X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=commitdiff_plain;h=33828bcb24176aae72afac0e4953e4b7f9560ef1 SimplifyCFG: Track the number of used icmps when turning a icmp chain into a switch. If we used only one icmp, don't turn it into a switch. Also prevent the switch-to-icmp transform from creating identity adds, noticed by Marius Wachtler. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125056 91177308-0d34-0410-b5e6-96231b3b80d8 --- diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp index 93d81435760..fb660dbfac1 100644 --- a/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/lib/Transforms/Utils/SimplifyCFG.cpp @@ -305,7 +305,7 @@ static ConstantInt *GetConstantInt(Value *V, const TargetData *TD) { /// Values vector. static Value * GatherConstantCompares(Value *V, std::vector &Vals, Value *&Extra, - const TargetData *TD, bool isEQ) { + const TargetData *TD, bool isEQ, unsigned &UsedICmps) { Instruction *I = dyn_cast(V); if (I == 0) return 0; @@ -313,6 +313,7 @@ GatherConstantCompares(Value *V, std::vector &Vals, Value *&Extra, if (ICmpInst *ICI = dyn_cast(I)) { if (ConstantInt *C = GetConstantInt(I->getOperand(1), TD)) { if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ:ICmpInst::ICMP_NE)) { + UsedICmps++; Vals.push_back(C); return I->getOperand(0); } @@ -335,6 +336,7 @@ GatherConstantCompares(Value *V, std::vector &Vals, Value *&Extra, for (APInt Tmp = Span.getLower(); Tmp != Span.getUpper(); ++Tmp) Vals.push_back(ConstantInt::get(V->getContext(), Tmp)); + UsedICmps++; return I->getOperand(0); } return 0; @@ -345,14 +347,17 @@ GatherConstantCompares(Value *V, std::vector &Vals, Value *&Extra, return 0; unsigned NumValsBeforeLHS = Vals.size(); + unsigned UsedICmpsBeforeLHS = UsedICmps; if (Value *LHS = GatherConstantCompares(I->getOperand(0), Vals, Extra, TD, - isEQ)) { + isEQ, UsedICmps)) { unsigned NumVals = Vals.size(); + unsigned UsedICmpsBeforeRHS = UsedICmps; if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, TD, - isEQ)) { + isEQ, UsedICmps)) { if (LHS == RHS) return LHS; Vals.resize(NumVals); + UsedICmps = UsedICmpsBeforeRHS; } // The RHS of the or/and can't be folded in and we haven't used "Extra" yet, @@ -363,6 +368,7 @@ GatherConstantCompares(Value *V, std::vector &Vals, Value *&Extra, } Vals.resize(NumValsBeforeLHS); + UsedICmps = UsedICmpsBeforeLHS; return 0; } @@ -372,7 +378,7 @@ GatherConstantCompares(Value *V, std::vector &Vals, Value *&Extra, Value *OldExtra = Extra; Extra = I->getOperand(0); if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, TD, - isEQ)) + isEQ, UsedICmps)) return RHS; assert(Vals.size() == NumValsBeforeLHS); Extra = OldExtra; @@ -1926,17 +1932,24 @@ static bool SimplifyBranchOnICmpChain(BranchInst *BI, const TargetData *TD) { std::vector Values; bool TrueWhenEqual = true; Value *ExtraCase = 0; + unsigned UsedICmps = 0; if (Cond->getOpcode() == Instruction::Or) { - CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, true); + CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, true, + UsedICmps); } else if (Cond->getOpcode() == Instruction::And) { - CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, false); + CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, false, + UsedICmps); TrueWhenEqual = false; } // If we didn't have a multiply compared value, fail. if (CompVal == 0) return false; + // Avoid turning single icmps into a switch. + if (UsedICmps <= 1) + return false; + // There might be duplicate constants in the list, which the switch // instruction can't handle, remove them now. array_pod_sort(Values.begin(), Values.end(), ConstantIntSortPredicate); @@ -2262,7 +2275,9 @@ static bool TurnSwitchRangeIntoICmp(SwitchInst *SI) { Constant *Offset = ConstantExpr::getNeg(Cases.back()); Constant *NumCases = ConstantInt::get(Offset->getType(), SI->getNumCases()-1); - Value *Sub = BinaryOperator::CreateAdd(SI->getCondition(), Offset, "off", SI); + Value *Sub = SI->getCondition(); + if (!Offset->isNullValue()) + Sub = BinaryOperator::CreateAdd(Sub, Offset, Sub->getName()+".off", SI); Value *Cmp = new ICmpInst(SI, ICmpInst::ICMP_ULT, Sub, NumCases, "switch"); BranchInst::Create(SI->getSuccessor(1), SI->getDefaultDest(), Cmp, SI); diff --git a/test/Transforms/SimplifyCFG/switch-to-icmp.ll b/test/Transforms/SimplifyCFG/switch-to-icmp.ll index 2499cdbcd69..414f8475bc2 100644 --- a/test/Transforms/SimplifyCFG/switch-to-icmp.ll +++ b/test/Transforms/SimplifyCFG/switch-to-icmp.ll @@ -16,8 +16,8 @@ lor.end: ret i1 %0 ; CHECK: @test1 -; CHECK: %off = add i32 %x, -1 -; CHECK: %switch = icmp ult i32 %off, 3 +; CHECK: %x.off = add i32 %x, -1 +; CHECK: %switch = icmp ult i32 %x.off, 3 } define zeroext i1 @test2(i32 %x) nounwind readnone ssp noredzone { @@ -35,6 +35,5 @@ lor.end: ret i1 %0 ; CHECK: @test2 -; CHECK: %off = add i32 %x, 0 -; CHECK: %switch = icmp ult i32 %off, 2 +; CHECK: %switch = icmp ult i32 %x, 2 } diff --git a/test/Transforms/SimplifyCFG/switch_create.ll b/test/Transforms/SimplifyCFG/switch_create.ll index 7c153e86822..546cc75f297 100644 --- a/test/Transforms/SimplifyCFG/switch_create.ll +++ b/test/Transforms/SimplifyCFG/switch_create.ll @@ -141,8 +141,8 @@ UnifiedReturnBlock: ; preds = %shortcirc_done.4, %shortcirc_next.4 ret i1 %UnifiedRetVal ; CHECK: @test6 -; CHECK: %off = add i32 %tmp.2.i, -14 -; CHECK: %switch = icmp ult i32 %off, 6 +; CHECK: %tmp.2.i.off = add i32 %tmp.2.i, -14 +; CHECK: %switch = icmp ult i32 %tmp.2.i.off, 6 } define void @test7(i8 zeroext %c, i32 %x) nounwind ssp noredzone { @@ -441,8 +441,8 @@ if.end: define zeroext i1 @test16(i32 %x) nounwind { entry: ; CHECK: @test16 -; CHECK: %off = add i32 %x, -1 -; CHECK: %switch = icmp ult i32 %off, 3 +; CHECK: %x.off = add i32 %x, -1 +; CHECK: %switch = icmp ult i32 %x.off, 3 %cmp.i = icmp eq i32 %x, 1 br i1 %cmp.i, label %lor.end, label %lor.lhs.false @@ -458,3 +458,24 @@ lor.end: %0 = phi i1 [ true, %lor.lhs.false ], [ true, %entry ], [ %cmp.i1, %lor.rhs ] ret i1 %0 } + +; Check that we don't turn an icmp into a switch where it's not useful. +define void @test17(i32 %x, i32 %y) { + %cmp = icmp ult i32 %x, 3 + %switch = icmp ult i32 %y, 2 + %or.cond775 = or i1 %cmp, %switch + br i1 %or.cond775, label %lor.lhs.false8, label %return + +lor.lhs.false8: + tail call void @foo1() + ret void + +return: + ret void + +; CHECK: @test17 +; CHECK-NOT: switch.early.test +; CHECK-NOT: switch i32 +; CHECK: ret void +} + diff --git a/test/Transforms/SimplifyCFG/switch_formation.dbg.ll b/test/Transforms/SimplifyCFG/switch_formation.dbg.ll index 09bef648ab0..2723ec608e1 100644 --- a/test/Transforms/SimplifyCFG/switch_formation.dbg.ll +++ b/test/Transforms/SimplifyCFG/switch_formation.dbg.ll @@ -14,8 +14,8 @@ declare void @llvm.dbg.stoppoint(i32, i32, { }*) nounwind define i1 @t({ i32, i32 }* %I) { ; CHECK: @t -; CHECK: %off = add i32 %tmp.2.i, -14 -; CHECK: %switch = icmp ult i32 %off, 6 +; CHECK: %tmp.2.i.off = add i32 %tmp.2.i, -14 +; CHECK: %switch = icmp ult i32 %tmp.2.i.off, 6 entry: %tmp.1.i = getelementptr { i32, i32 }* %I, i64 0, i32 1 ; [#uses=1] %tmp.2.i = load i32* %tmp.1.i ; [#uses=6]