Skip to content

Commit 7c78ef7

Browse files
preamespreames
committedMay 22, 2015
Extend EarlyCSE to handle basic cases from JumpThreading and CVP
This patch extends EarlyCSE to take advantage of the information that a controlling branch gives us about the value of a Value within this and dominated basic blocks. If the current block has a single predecessor with a controlling branch, we can infer what the branch condition must have been to execute this block. The actual change to support this is downright simple because EarlyCSE's existing scoped hash table logic deals with most of the complexity around merging. The patch actually implements two optimizations. 1) The first is analogous to JumpThreading in that it enables EarlyCSE's CSE handling to fold branches which are exactly redundant due to a previous branch to branches on constants. (It doesn't actually replace the branch or change the CFG.) This is pretty clearly a win since it enables substantial CFG simplification before we start trying to inline. 2) The second is analogous to CVP in that it exploits the knowledge gained to replace dominated *uses* of the original value. EarlyCSE does not otherwise reason about specific uses, so this is the more arguable one. It does enable further simplication and constant folding within the rest of the visit by EarlyCSE. In both cases, the added code only handles the easy dominance based case of each optimization. The general case is deferred to the existing passes. Differential Revision: http://reviews.llvm.org/D9763 llvm-svn: 238071
1 parent ecff11d commit 7c78ef7

File tree

6 files changed

+332
-21
lines changed

6 files changed

+332
-21
lines changed
 

‎llvm/include/llvm/Transforms/Utils/Local.h

+5
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,7 @@
1616
#define LLVM_TRANSFORMS_UTILS_LOCAL_H
1717

1818
#include "llvm/IR/DataLayout.h"
19+
#include "llvm/IR/Dominators.h"
1920
#include "llvm/IR/GetElementPtrTypeIterator.h"
2021
#include "llvm/IR/IRBuilder.h"
2122
#include "llvm/IR/Operator.h"
@@ -286,6 +287,10 @@ bool removeUnreachableBlocks(Function &F);
286287
/// Metadata not listed as known via KnownIDs is removed
287288
void combineMetadata(Instruction *K, const Instruction *J, ArrayRef<unsigned> KnownIDs);
288289

290+
/// \brief Replace each use of 'From' with 'To' if that use is dominated by
291+
/// the given edge. Returns the number of replacements made.
292+
unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT,
293+
const BasicBlockEdge &Edge);
289294
} // End llvm namespace
290295

291296
#endif

‎llvm/lib/Transforms/Scalar/EarlyCSE.cpp

+24
Original file line numberDiff line numberDiff line change
@@ -461,6 +461,30 @@ bool EarlyCSE::processNode(DomTreeNode *Node) {
461461
if (!BB->getSinglePredecessor())
462462
++CurrentGeneration;
463463

464+
// If this node has a single predecessor which ends in a conditional branch,
465+
// we can infer the value of the branch condition given that we took this
466+
// path. We need the single predeccesor to ensure there's not another path
467+
// which reaches this block where the condition might hold a different
468+
// value. Since we're adding this to the scoped hash table (like any other
469+
// def), it will have been popped if we encounter a future merge block.
470+
if (BasicBlock *Pred = BB->getSinglePredecessor())
471+
if (auto *BI = dyn_cast<BranchInst>(Pred->getTerminator()))
472+
if (BI->isConditional())
473+
if (auto *CondInst = dyn_cast<Instruction>(BI->getCondition()))
474+
if (SimpleValue::canHandle(CondInst)) {
475+
assert(BI->getSuccessor(0) == BB || BI->getSuccessor(1) == BB);
476+
auto *ConditionalConstant = (BI->getSuccessor(0) == BB) ?
477+
ConstantInt::getTrue(BB->getContext()) :
478+
ConstantInt::getFalse(BB->getContext());
479+
AvailableValues.insert(CondInst, ConditionalConstant);
480+
DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '"
481+
<< CondInst->getName() << "' as " << *ConditionalConstant
482+
<< " in " << BB->getName() << "\n");
483+
// Replace all dominated uses with the known value
484+
replaceDominatedUsesWith(CondInst, ConditionalConstant, DT,
485+
BasicBlockEdge(Pred, BB));
486+
}
487+
464488
/// LastStore - Keep track of the last non-volatile store that we saw... for
465489
/// as long as there in no instruction that reads memory. If we see a store
466490
/// to the same location, we delete the dead store. This zaps trivial dead

‎llvm/lib/Transforms/Scalar/GVN.cpp

+2-21
Original file line numberDiff line numberDiff line change
@@ -716,8 +716,6 @@ namespace {
716716
void verifyRemoved(const Instruction *I) const;
717717
bool splitCriticalEdges();
718718
BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
719-
unsigned replaceAllDominatedUsesWith(Value *From, Value *To,
720-
const BasicBlockEdge &Root);
721719
bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root);
722720
bool processFoldableCondBr(BranchInst *BI);
723721
void addDeadBlock(BasicBlock *BB);
@@ -2033,23 +2031,6 @@ Value *GVN::findLeader(const BasicBlock *BB, uint32_t num) {
20332031
return Val;
20342032
}
20352033

2036-
/// Replace all uses of 'From' with 'To' if the use is dominated by the given
2037-
/// basic block. Returns the number of uses that were replaced.
2038-
unsigned GVN::replaceAllDominatedUsesWith(Value *From, Value *To,
2039-
const BasicBlockEdge &Root) {
2040-
unsigned Count = 0;
2041-
for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
2042-
UI != UE; ) {
2043-
Use &U = *UI++;
2044-
2045-
if (DT->dominates(Root, U)) {
2046-
U.set(To);
2047-
++Count;
2048-
}
2049-
}
2050-
return Count;
2051-
}
2052-
20532034
/// There is an edge from 'Src' to 'Dst'. Return
20542035
/// true if every path from the entry block to 'Dst' passes via this edge. In
20552036
/// particular 'Dst' must not be reachable via another edge from 'Src'.
@@ -2126,7 +2107,7 @@ bool GVN::propagateEquality(Value *LHS, Value *RHS,
21262107
// LHS always has at least one use that is not dominated by Root, this will
21272108
// never do anything if LHS has only one use.
21282109
if (!LHS->hasOneUse()) {
2129-
unsigned NumReplacements = replaceAllDominatedUsesWith(LHS, RHS, Root);
2110+
unsigned NumReplacements = replaceDominatedUsesWith(LHS, RHS, *DT, Root);
21302111
Changed |= NumReplacements > 0;
21312112
NumGVNEqProp += NumReplacements;
21322113
}
@@ -2198,7 +2179,7 @@ bool GVN::propagateEquality(Value *LHS, Value *RHS,
21982179
Value *NotCmp = findLeader(Root.getEnd(), Num);
21992180
if (NotCmp && isa<Instruction>(NotCmp)) {
22002181
unsigned NumReplacements =
2201-
replaceAllDominatedUsesWith(NotCmp, NotVal, Root);
2182+
replaceDominatedUsesWith(NotCmp, NotVal, *DT, Root);
22022183
Changed |= NumReplacements > 0;
22032184
NumGVNEqProp += NumReplacements;
22042185
}

‎llvm/lib/Transforms/Utils/Local.cpp

+20
Original file line numberDiff line numberDiff line change
@@ -1343,3 +1343,23 @@ void llvm::combineMetadata(Instruction *K, const Instruction *J, ArrayRef<unsign
13431343
}
13441344
}
13451345
}
1346+
1347+
unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
1348+
DominatorTree &DT,
1349+
const BasicBlockEdge &Root) {
1350+
assert(From->getType() == To->getType());
1351+
1352+
unsigned Count = 0;
1353+
for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
1354+
UI != UE; ) {
1355+
Use &U = *UI++;
1356+
if (DT.dominates(Root, U)) {
1357+
U.set(To);
1358+
DEBUG(dbgs() << "Replace dominated use of '"
1359+
<< From->getName() << "' as "
1360+
<< *To << " in " << *U << "\n");
1361+
++Count;
1362+
}
1363+
}
1364+
return Count;
1365+
}

‎llvm/test/Transforms/EarlyCSE/conditional.ll

+107
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,107 @@
1+
; RUN: opt -early-cse -S < %s | FileCheck %s
2+
3+
; Can we CSE a known condition to a constant?
4+
define i1 @test(i8* %p) {
5+
; CHECK-LABEL: @test
6+
entry:
7+
%cnd1 = icmp eq i8* %p, null
8+
br i1 %cnd1, label %taken, label %untaken
9+
10+
taken:
11+
; CHECK-LABEL: taken:
12+
; CHECK-NEXT: ret i1 true
13+
%cnd2 = icmp eq i8* %p, null
14+
ret i1 %cnd2
15+
16+
untaken:
17+
; CHECK-LABEL: untaken:
18+
; CHECK-NEXT: ret i1 false
19+
%cnd3 = icmp eq i8* %p, null
20+
ret i1 %cnd3
21+
}
22+
23+
; We can CSE the condition, but we *don't* know it's value after the merge
24+
define i1 @test_neg1(i8* %p) {
25+
; CHECK-LABEL: @test_neg1
26+
entry:
27+
%cnd1 = icmp eq i8* %p, null
28+
br i1 %cnd1, label %taken, label %untaken
29+
30+
taken:
31+
br label %merge
32+
33+
untaken:
34+
br label %merge
35+
36+
merge:
37+
; CHECK-LABEL: merge:
38+
; CHECK-NEXT: ret i1 %cnd1
39+
%cnd3 = icmp eq i8* %p, null
40+
ret i1 %cnd3
41+
}
42+
43+
; Check specifically for a case where we have a unique predecessor, but
44+
; not a single predecessor. We can not know the value of the condition here.
45+
define i1 @test_neg2(i8* %p) {
46+
; CHECK-LABEL: @test_neg2
47+
entry:
48+
%cnd1 = icmp eq i8* %p, null
49+
br i1 %cnd1, label %merge, label %merge
50+
51+
merge:
52+
; CHECK-LABEL: merge:
53+
; CHECK-NEXT: ret i1 %cnd1
54+
%cnd3 = icmp eq i8* %p, null
55+
ret i1 %cnd3
56+
}
57+
58+
; Replace a use rather than CSE
59+
define i1 @test2(i8* %p) {
60+
; CHECK-LABEL: @test2
61+
entry:
62+
%cnd = icmp eq i8* %p, null
63+
br i1 %cnd, label %taken, label %untaken
64+
65+
taken:
66+
; CHECK-LABEL: taken:
67+
; CHECK-NEXT: ret i1 true
68+
ret i1 %cnd
69+
70+
untaken:
71+
; CHECK-LABEL: untaken:
72+
; CHECK-NEXT: ret i1 false
73+
ret i1 %cnd
74+
}
75+
76+
; Not legal to replace use given it's not dominated by edge
77+
define i1 @test2_neg1(i8* %p) {
78+
; CHECK-LABEL: @test2_neg1
79+
entry:
80+
%cnd1 = icmp eq i8* %p, null
81+
br i1 %cnd1, label %taken, label %untaken
82+
83+
taken:
84+
br label %merge
85+
86+
untaken:
87+
br label %merge
88+
89+
merge:
90+
; CHECK-LABEL: merge:
91+
; CHECK-NEXT: ret i1 %cnd1
92+
ret i1 %cnd1
93+
}
94+
95+
; Another single predecessor test, but for dominated use
96+
define i1 @test2_neg2(i8* %p) {
97+
; CHECK-LABEL: @test2_neg2
98+
entry:
99+
%cnd1 = icmp eq i8* %p, null
100+
br i1 %cnd1, label %merge, label %merge
101+
102+
merge:
103+
; CHECK-LABEL: merge:
104+
; CHECK-NEXT: ret i1 %cnd1
105+
ret i1 %cnd1
106+
}
107+

0 commit comments

Comments
 (0)