Index: include/llvm/Transforms/Utils/Local.h =================================================================== --- include/llvm/Transforms/Utils/Local.h +++ include/llvm/Transforms/Utils/Local.h @@ -16,6 +16,7 @@ #define LLVM_TRANSFORMS_UTILS_LOCAL_H #include "llvm/IR/DataLayout.h" +#include "llvm/IR/Dominators.h" #include "llvm/IR/GetElementPtrTypeIterator.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/Operator.h" @@ -286,6 +287,10 @@ /// Metadata not listed as known via KnownIDs is removed void combineMetadata(Instruction *K, const Instruction *J, ArrayRef KnownIDs); +/// Replace each use of 'From' with 'To' if that use is dominated by the given +/// edge. Returns the number of replacements made. +unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, + const BasicBlockEdge &Edge); } // End llvm namespace #endif Index: lib/Transforms/Scalar/EarlyCSE.cpp =================================================================== --- lib/Transforms/Scalar/EarlyCSE.cpp +++ lib/Transforms/Scalar/EarlyCSE.cpp @@ -461,6 +461,33 @@ if (!BB->getSinglePredecessor()) ++CurrentGeneration; + // If this node has a single predecessor which ends in a conditional branch, + // we can infer the value of the branch condition given that we took this + // path. We need the single predeccesor to ensure there's not another path + // which reaches this block where the condition might hold a different + // value. Since we're adding this to the scoped hash table (like any other + // def), it will have been popped if we encounter a future merge block. + if (BasicBlock *Pred = BB->getSinglePredecessor()) + // TODO: handle switch with case value as well + if (auto *BI = dyn_cast(Pred->getTerminator())) + if (BI->isConditional()) + if (auto *CondInst = dyn_cast(BI->getCondition())) + if (SimpleValue::canHandle(CondInst)) { + assert(BI->getSuccessor(0) == BB || BI->getSuccessor(1) == BB); + auto *ConditionalConstant = (BI->getSuccessor(0) == BB) ? + ConstantInt::getTrue(BB->getContext()) : + ConstantInt::getFalse(BB->getContext()); + AvailableValues.insert(CondInst, ConditionalConstant); + DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '" + << CondInst->getName() << "' as " << *ConditionalConstant + << " in " << BB->getName() << "\n"); + // Replace all dominated uses with the known value + replaceDominatedUsesWith(CondInst, ConditionalConstant, DT, + BasicBlockEdge(Pred, BB)); + // TODO: Exploit icmp eq %v, C to get value for C + // TODO: Look through and/or sequences to get more known conditions + } + /// LastStore - Keep track of the last non-volatile store that we saw... for /// as long as there in no instruction that reads memory. If we see a store /// to the same location, we delete the dead store. This zaps trivial dead Index: lib/Transforms/Scalar/GVN.cpp =================================================================== --- lib/Transforms/Scalar/GVN.cpp +++ lib/Transforms/Scalar/GVN.cpp @@ -716,8 +716,6 @@ void verifyRemoved(const Instruction *I) const; bool splitCriticalEdges(); BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ); - unsigned replaceAllDominatedUsesWith(Value *From, Value *To, - const BasicBlockEdge &Root); bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root); bool processFoldableCondBr(BranchInst *BI); void addDeadBlock(BasicBlock *BB); @@ -2033,23 +2031,6 @@ return Val; } -/// Replace all uses of 'From' with 'To' if the use is dominated by the given -/// basic block. Returns the number of uses that were replaced. -unsigned GVN::replaceAllDominatedUsesWith(Value *From, Value *To, - const BasicBlockEdge &Root) { - unsigned Count = 0; - for (Value::use_iterator UI = From->use_begin(), UE = From->use_end(); - UI != UE; ) { - Use &U = *UI++; - - if (DT->dominates(Root, U)) { - U.set(To); - ++Count; - } - } - return Count; -} - /// There is an edge from 'Src' to 'Dst'. Return /// true if every path from the entry block to 'Dst' passes via this edge. In /// particular 'Dst' must not be reachable via another edge from 'Src'. @@ -2126,7 +2107,7 @@ // LHS always has at least one use that is not dominated by Root, this will // never do anything if LHS has only one use. if (!LHS->hasOneUse()) { - unsigned NumReplacements = replaceAllDominatedUsesWith(LHS, RHS, Root); + unsigned NumReplacements = replaceDominatedUsesWith(LHS, RHS, *DT, Root); Changed |= NumReplacements > 0; NumGVNEqProp += NumReplacements; } @@ -2198,7 +2179,7 @@ Value *NotCmp = findLeader(Root.getEnd(), Num); if (NotCmp && isa(NotCmp)) { unsigned NumReplacements = - replaceAllDominatedUsesWith(NotCmp, NotVal, Root); + replaceDominatedUsesWith(NotCmp, NotVal, *DT, Root); Changed |= NumReplacements > 0; NumGVNEqProp += NumReplacements; } Index: lib/Transforms/Utils/Local.cpp =================================================================== --- lib/Transforms/Utils/Local.cpp +++ lib/Transforms/Utils/Local.cpp @@ -1343,3 +1343,23 @@ } } } + +unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To, + DominatorTree &DT, + const BasicBlockEdge &Root) { + assert(From->getType() == To->getType()); + + unsigned Count = 0; + for (Value::use_iterator UI = From->use_begin(), UE = From->use_end(); + UI != UE; ) { + Use &U = *UI++; + if (DT.dominates(Root, U)) { + U.set(To); + DEBUG(dbgs() << "Replace dominated use of '" + << From->getName() << "' as " + << *To << " in " << *U << "\n"); + ++Count; + } + } + return Count; +} Index: test/Transforms/EarlyCSE/conditional.ll =================================================================== --- /dev/null +++ test/Transforms/EarlyCSE/conditional.ll @@ -0,0 +1,101 @@ +; RUN: opt -early-cse -S < %s | FileCheck %s + +define i1 @test(i8* %p) { +; CHECK-LABEL: @test +entry: + %cnd1 = icmp eq i8* %p, null + br i1 %cnd1, label %taken, label %untaken + +taken: +; CHECK-LABEL: taken: +; CHECK-NEXT: ret i1 true + %cnd2 = icmp eq i8* %p, null + ret i1 %cnd2 + +untaken: +; CHECK-LABEL: untaken: +; CHECK-NEXT: ret i1 false + %cnd3 = icmp eq i8* %p, null + ret i1 %cnd3 +} + +define i1 @test_neg1(i8* %p) { +; CHECK-LABEL: @test_neg1 +entry: + %cnd1 = icmp eq i8* %p, null + br i1 %cnd1, label %taken, label %untaken + +taken: + br label %merge + +untaken: + br label %merge + +merge: +; CHECK-LABEL: merge: +; CHECK-NEXT: ret i1 %cnd1 + %cnd3 = icmp eq i8* %p, null + ret i1 %cnd3 +} + +define i1 @test_neg2(i8* %p) { +; CHECK-LABEL: @test_neg2 +entry: + %cnd1 = icmp eq i8* %p, null + br i1 %cnd1, label %merge, label %merge + +merge: +; CHECK-LABEL: merge: +; CHECK-NEXT: ret i1 %cnd1 + %cnd3 = icmp eq i8* %p, null + ret i1 %cnd3 +} + +; Replace a use rather than CSE +define i1 @test2(i8* %p) { +; CHECK-LABEL: @test2 +entry: + %cnd = icmp eq i8* %p, null + br i1 %cnd, label %taken, label %untaken + +taken: +; CHECK-LABEL: taken: +; CHECK-NEXT: ret i1 true + ret i1 %cnd + +untaken: +; CHECK-LABEL: untaken: +; CHECK-NEXT: ret i1 false + ret i1 %cnd +} + +define i1 @test2_neg1(i8* %p) { +; CHECK-LABEL: @test2_neg1 +entry: + %cnd1 = icmp eq i8* %p, null + br i1 %cnd1, label %taken, label %untaken + +taken: + br label %merge + +untaken: + br label %merge + +merge: +; CHECK-LABEL: merge: +; CHECK-NEXT: ret i1 %cnd1 + ret i1 %cnd1 +} + +define i1 @test2_neg2(i8* %p) { +; CHECK-LABEL: @test2_neg2 +entry: + %cnd1 = icmp eq i8* %p, null + br i1 %cnd1, label %merge, label %merge + +merge: +; CHECK-LABEL: merge: +; CHECK-NEXT: ret i1 %cnd1 + ret i1 %cnd1 +} +