From daa02ab70c7619cc22131c75c62390cf3f5f8891 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Mon, 13 Dec 2010 07:00:06 +0000 Subject: [PATCH] Make simplifycfg reprocess newly formed "br (cond1 | cond2)" conditions when simplifying, allowing them to be eagerly turned into switches. This is the last step required to get "Example 7" from this blog post: http://blog.regehr.org/archives/320 On X86, we now generate this machine code, which (to my eye) seems better than the ICC generated code: _crud: ## @crud ## BB#0: ## %entry cmpb $33, %dil jb LBB0_4 ## BB#1: ## %switch.early.test addb $-34, %dil cmpb $58, %dil ja LBB0_3 ## BB#2: ## %switch.early.test movzbl %dil, %eax movabsq $288230376537592865, %rcx ## imm = 0x400000017001421 btq %rax, %rcx jb LBB0_4 LBB0_3: ## %lor.rhs xorl %eax, %eax ret LBB0_4: ## %lor.end movl $1, %eax ret git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121690 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Utils/SimplifyCFG.cpp | 17 +++-- test/Transforms/SimplifyCFG/switch_create.ll | 65 ++++++++++++++++++++ 2 files changed, 77 insertions(+), 5 deletions(-) diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp index 503e5bcb23f..18c2905a546 100644 --- a/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/lib/Transforms/Utils/SimplifyCFG.cpp @@ -1357,7 +1357,7 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI) { // must be at the front of the block. BasicBlock::iterator FrontIt = BB->front(); // Ignore dbg intrinsics. - while(isa(FrontIt)) + while (isa(FrontIt)) ++FrontIt; // Allow a single instruction to be hoisted in addition to the compare @@ -1441,7 +1441,7 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI) { UsedValues.erase(Pair.first); if (UsedValues.empty()) break; - if (Instruction* I = dyn_cast(Pair.first)) { + if (Instruction *I = dyn_cast(Pair.first)) { for (Instruction::op_iterator OI = I->op_begin(), OE = I->op_end(); OI != OE; ++OI) Worklist.push_back(std::make_pair(OI->get(), Pair.second+1)); @@ -1469,9 +1469,16 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI) { // If we need to invert the condition in the pred block to match, do so now. if (InvertPredCond) { - Value *NewCond = - BinaryOperator::CreateNot(PBI->getCondition(), + Value *NewCond = PBI->getCondition(); + + if (NewCond->hasOneUse() && isa(NewCond)) { + CmpInst *CI = cast(NewCond); + CI->setPredicate(CI->getInversePredicate()); + } else { + NewCond = BinaryOperator::CreateNot(NewCond, PBI->getCondition()->getName()+".not", PBI); + } + PBI->setCondition(NewCond); BasicBlock *OldTrue = PBI->getSuccessor(0); BasicBlock *OldFalse = PBI->getSuccessor(1); @@ -1507,7 +1514,7 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI) { AddPredecessorToBlock(FalseDest, PredBlock, BB); PBI->setSuccessor(1, FalseDest); } - return true; + return SimplifyCFG(PBI->getParent()) | true; } return false; } diff --git a/test/Transforms/SimplifyCFG/switch_create.ll b/test/Transforms/SimplifyCFG/switch_create.ll index d5347e8afff..ce82936c31f 100644 --- a/test/Transforms/SimplifyCFG/switch_create.ll +++ b/test/Transforms/SimplifyCFG/switch_create.ll @@ -203,5 +203,70 @@ if.end: ; preds = %entry ; CHECK: i8 97, label %if.then ; CHECK: ] ; CHECK: %A = phi i32 [ 0, %entry ], [ 42, %switch.early.test ], [ 42, %N ], [ 42, %switch.early.test ] +} + +define i32 @test9(i8 zeroext %c) nounwind ssp noredzone { +entry: + %cmp = icmp ult i8 %c, 33 + br i1 %cmp, label %lor.end, label %lor.lhs.false + +lor.lhs.false: ; preds = %entry + %cmp4 = icmp eq i8 %c, 46 + br i1 %cmp4, label %lor.end, label %lor.lhs.false6 + +lor.lhs.false6: ; preds = %lor.lhs.false + %cmp9 = icmp eq i8 %c, 44 + br i1 %cmp9, label %lor.end, label %lor.lhs.false11 + +lor.lhs.false11: ; preds = %lor.lhs.false6 + %cmp14 = icmp eq i8 %c, 58 + br i1 %cmp14, label %lor.end, label %lor.lhs.false16 + +lor.lhs.false16: ; preds = %lor.lhs.false11 + %cmp19 = icmp eq i8 %c, 59 + br i1 %cmp19, label %lor.end, label %lor.lhs.false21 + +lor.lhs.false21: ; preds = %lor.lhs.false16 + %cmp24 = icmp eq i8 %c, 60 + br i1 %cmp24, label %lor.end, label %lor.lhs.false26 + +lor.lhs.false26: ; preds = %lor.lhs.false21 + %cmp29 = icmp eq i8 %c, 62 + br i1 %cmp29, label %lor.end, label %lor.lhs.false31 +lor.lhs.false31: ; preds = %lor.lhs.false26 + %cmp34 = icmp eq i8 %c, 34 + br i1 %cmp34, label %lor.end, label %lor.lhs.false36 + +lor.lhs.false36: ; preds = %lor.lhs.false31 + %cmp39 = icmp eq i8 %c, 92 + br i1 %cmp39, label %lor.end, label %lor.rhs + +lor.rhs: ; preds = %lor.lhs.false36 + %cmp43 = icmp eq i8 %c, 39 + br label %lor.end + +lor.end: ; preds = %lor.rhs, %lor.lhs.false36, %lor.lhs.false31, %lor.lhs.false26, %lor.lhs.false21, %lor.lhs.false16, %lor.lhs.false11, %lor.lhs.false6, %lor.lhs.false, %entry + %0 = phi i1 [ true, %lor.lhs.false36 ], [ true, %lor.lhs.false31 ], [ true, %lor.lhs.false26 ], [ true, %lor.lhs.false21 ], [ true, %lor.lhs.false16 ], [ true, %lor.lhs.false11 ], [ true, %lor.lhs.false6 ], [ true, %lor.lhs.false ], [ true, %entry ], [ %cmp43, %lor.rhs ] + %conv46 = zext i1 %0 to i32 + ret i32 %conv46 + +; CHECK: @test9 +; CHECK: %cmp = icmp ult i8 %c, 33 +; CHECK: br i1 %cmp, label %lor.end, label %switch.early.test + +; CHECK: switch.early.test: +; CHECK: switch i8 %c, label %lor.rhs [ +; CHECK: i8 46, label %lor.end +; CHECK: i8 44, label %lor.end +; CHECK: i8 58, label %lor.end +; CHECK: i8 59, label %lor.end +; CHECK: i8 60, label %lor.end +; CHECK: i8 62, label %lor.end +; CHECK: i8 34, label %lor.end +; CHECK: i8 92, label %lor.end +; CHECK: i8 39, label %lor.end +; CHECK: ] } + + -- 2.34.1