Index: llvm/trunk/include/llvm/Transforms/Utils/Local.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Utils/Local.h +++ llvm/trunk/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); +/// \brief 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: llvm/trunk/lib/Transforms/Scalar/EarlyCSE.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/EarlyCSE.cpp +++ llvm/trunk/lib/Transforms/Scalar/EarlyCSE.cpp @@ -461,6 +461,30 @@ 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()) + 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)); + } + /// 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: llvm/trunk/lib/Transforms/Scalar/GVN.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/GVN.cpp +++ llvm/trunk/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: llvm/trunk/lib/Transforms/Utils/Local.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/Local.cpp +++ llvm/trunk/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: llvm/trunk/test/Transforms/EarlyCSE/conditional.ll =================================================================== --- llvm/trunk/test/Transforms/EarlyCSE/conditional.ll +++ llvm/trunk/test/Transforms/EarlyCSE/conditional.ll @@ -0,0 +1,107 @@ +; RUN: opt -early-cse -S < %s | FileCheck %s + +; Can we CSE a known condition to a constant? +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 +} + +; We can CSE the condition, but we *don't* know it's value after the merge +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 +} + +; Check specifically for a case where we have a unique predecessor, but +; not a single predecessor. We can not know the value of the condition here. +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 +} + +; Not legal to replace use given it's not dominated by edge +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 +} + +; Another single predecessor test, but for dominated use +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 +} + Index: llvm/trunk/test/Transforms/EarlyCSE/edge.ll =================================================================== --- llvm/trunk/test/Transforms/EarlyCSE/edge.ll +++ llvm/trunk/test/Transforms/EarlyCSE/edge.ll @@ -0,0 +1,174 @@ +; RUN: opt -early-cse -S < %s | FileCheck %s +; Same as GVN/edge.ll, but updated to reflect EarlyCSE's less powerful +; implementation. EarlyCSE doesn't yet handle uses on edges where the +; source is dominated, but the dest is not. Nor does it reason about +; fcmps. This file can basically be seen as a list of TODOs. + +define i32 @f1(i32 %x) { + ; CHECK-LABEL: define i32 @f1( +bb0: + %cmp = icmp eq i32 %x, 0 + br i1 %cmp, label %bb2, label %bb1 +bb1: + br label %bb2 +bb2: + %cond = phi i32 [ %x, %bb0 ], [ 0, %bb1 ] + %foo = add i32 %cond, %x + ret i32 %foo + ; CHECK: bb2: + ; CHECK: %cond = phi i32 [ %x, %bb0 ], [ 0, %bb1 ] +} + +define i32 @f2(i32 %x) { + ; CHECK-LABEL: define i32 @f2( +bb0: + %cmp = icmp ne i32 %x, 0 + br i1 %cmp, label %bb1, label %bb2 +bb1: + br label %bb2 +bb2: + %cond = phi i32 [ %x, %bb0 ], [ 0, %bb1 ] + %foo = add i32 %cond, %x + ret i32 %foo + ; CHECK: bb2: + ; CHECK: %cond = phi i32 [ %x, %bb0 ], [ 0, %bb1 ] +} + +define i32 @f3(i32 %x) { + ; CHECK-LABEL: define i32 @f3( +bb0: + switch i32 %x, label %bb1 [ i32 0, label %bb2] +bb1: + br label %bb2 +bb2: + %cond = phi i32 [ %x, %bb0 ], [ 0, %bb1 ] + %foo = add i32 %cond, %x + ret i32 %foo + ; CHECK: bb2: + ; CHECK: %cond = phi i32 [ %x, %bb0 ], [ 0, %bb1 ] +} + +declare void @g(i1) +define void @f4(i8 * %x) { +; CHECK-LABEL: define void @f4( +bb0: + %y = icmp eq i8* null, %x + br i1 %y, label %bb2, label %bb1 +bb1: + br label %bb2 +bb2: + %zed = icmp eq i8* null, %x + call void @g(i1 %zed) +; CHECK: call void @g(i1 %y) + ret void +} + +define double @fcmp_oeq_not_zero(double %x, double %y) { +entry: + %cmp = fcmp oeq double %y, 2.0 + br i1 %cmp, label %if, label %return + +if: + %div = fdiv double %x, %y + br label %return + +return: + %retval = phi double [ %div, %if ], [ %x, %entry ] + ret double %retval + +; CHECK-LABEL: define double @fcmp_oeq_not_zero( +; CHECK: %div = fdiv double %x, %y +} + +define double @fcmp_une_not_zero(double %x, double %y) { +entry: + %cmp = fcmp une double %y, 2.0 + br i1 %cmp, label %return, label %else + +else: + %div = fdiv double %x, %y + br label %return + +return: + %retval = phi double [ %div, %else ], [ %x, %entry ] + ret double %retval + +; CHECK-LABEL: define double @fcmp_une_not_zero( +; CHECK: %div = fdiv double %x, %y +} + +; PR22376 - We can't propagate zero constants because -0.0 +; compares equal to 0.0. If %y is -0.0 in this test case, +; we would produce the wrong sign on the infinity return value. +define double @fcmp_oeq_zero(double %x, double %y) { +entry: + %cmp = fcmp oeq double %y, 0.0 + br i1 %cmp, label %if, label %return + +if: + %div = fdiv double %x, %y + br label %return + +return: + %retval = phi double [ %div, %if ], [ %x, %entry ] + ret double %retval + +; CHECK-LABEL: define double @fcmp_oeq_zero( +; CHECK: %div = fdiv double %x, %y +} + +define double @fcmp_une_zero(double %x, double %y) { +entry: + %cmp = fcmp une double %y, -0.0 + br i1 %cmp, label %return, label %else + +else: + %div = fdiv double %x, %y + br label %return + +return: + %retval = phi double [ %div, %else ], [ %x, %entry ] + ret double %retval + +; CHECK-LABEL: define double @fcmp_une_zero( +; CHECK: %div = fdiv double %x, %y +} + +; We also cannot propagate a value if it's not a constant. +; This is because the value could be 0.0 or -0.0. + +define double @fcmp_oeq_maybe_zero(double %x, double %y, double %z1, double %z2) { +entry: + %z = fadd double %z1, %z2 + %cmp = fcmp oeq double %y, %z + br i1 %cmp, label %if, label %return + +if: + %div = fdiv double %x, %z + br label %return + +return: + %retval = phi double [ %div, %if ], [ %x, %entry ] + ret double %retval + +; CHECK-LABEL: define double @fcmp_oeq_maybe_zero( +; CHECK: %div = fdiv double %x, %z +} + +define double @fcmp_une_maybe_zero(double %x, double %y, double %z1, double %z2) { +entry: + %z = fadd double %z1, %z2 + %cmp = fcmp une double %y, %z + br i1 %cmp, label %return, label %else + +else: + %div = fdiv double %x, %z + br label %return + +return: + %retval = phi double [ %div, %else ], [ %x, %entry ] + ret double %retval + +; CHECK-LABEL: define double @fcmp_une_maybe_zero( +; CHECK: %div = fdiv double %x, %z +}