#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"
/// Metadata not listed as known via KnownIDs is removed
void combineMetadata(Instruction *K, const Instruction *J, ArrayRef<unsigned> 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
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<BranchInst>(Pred->getTerminator()))
+ if (BI->isConditional())
+ if (auto *CondInst = dyn_cast<Instruction>(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
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);
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'.
// 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;
}
Value *NotCmp = findLeader(Root.getEnd(), Num);
if (NotCmp && isa<Instruction>(NotCmp)) {
unsigned NumReplacements =
- replaceAllDominatedUsesWith(NotCmp, NotVal, Root);
+ replaceDominatedUsesWith(NotCmp, NotVal, *DT, Root);
Changed |= NumReplacements > 0;
NumGVNEqProp += NumReplacements;
}
}
}
}
+
+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;
+}
--- /dev/null
+; 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
+}
+
--- /dev/null
+; 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
+}
projects / oota-llvm.git / commitdiff