aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/Analysis/Dominators.h14
-rw-r--r--lib/Analysis/ScalarEvolutionExpander.cpp11
-rw-r--r--lib/VMCore/Dominators.cpp104
-rw-r--r--test/Analysis/Dominators/invoke.ll19
-rw-r--r--test/Transforms/LoopStrengthReduce/dominate-assert.ll40
5 files changed, 156 insertions, 32 deletions
diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index 5873073147..c384925e70 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -749,15 +749,11 @@ public:
return DT->dominates(A, B);
}
- // dominates - Return true if A dominates B. This performs the
- // special checks necessary if A and B are in the same basic block.
- bool dominates(const Instruction *A, const Instruction *B) const;
-
- /// properlyDominates - Use this instead of dominates() to determine whether a
- /// user of A can be hoisted above B.
- bool properlyDominates(const Instruction *A, const Instruction *B) const {
- return A != B && dominates(A, B);
- }
+ // dominates - Return true if Def dominates a use in User. This performs
+ // the special checks necessary if Def and User are in the same basic block.
+ // Note that Def doesn't dominate a use in Def itself!
+ bool dominates(const Instruction *Def, const Instruction *User) const;
+ bool dominates(const Instruction *Def, const BasicBlock *BB) const;
bool properlyDominates(const DomTreeNode *A, const DomTreeNode *B) const {
return DT->properlyDominates(A, B);
diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp
index a03e371daa..c83abd2e72 100644
--- a/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -515,8 +515,7 @@ Value *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin,
Type::getInt8PtrTy(Ty->getContext(), PTy->getAddressSpace()));
assert(!isa<Instruction>(V) ||
- SE.DT->properlyDominates(cast<Instruction>(V),
- Builder.GetInsertPoint()));
+ SE.DT->dominates(cast<Instruction>(V), Builder.GetInsertPoint()));
// Expand the operands for a plain byte offset.
Value *Idx = expandCodeFor(SE.getAddExpr(Ops), Ty);
@@ -908,7 +907,7 @@ Instruction *SCEVExpander::getIVIncOperand(Instruction *IncV,
case Instruction::Add:
case Instruction::Sub: {
Instruction *OInst = dyn_cast<Instruction>(IncV->getOperand(1));
- if (!OInst || SE.DT->properlyDominates(OInst, InsertPos))
+ if (!OInst || SE.DT->dominates(OInst, InsertPos))
return dyn_cast<Instruction>(IncV->getOperand(0));
return NULL;
}
@@ -920,7 +919,7 @@ Instruction *SCEVExpander::getIVIncOperand(Instruction *IncV,
if (isa<Constant>(*I))
continue;
if (Instruction *OInst = dyn_cast<Instruction>(*I)) {
- if (!SE.DT->properlyDominates(OInst, InsertPos))
+ if (!SE.DT->dominates(OInst, InsertPos))
return NULL;
}
if (allowScale) {
@@ -947,7 +946,7 @@ Instruction *SCEVExpander::getIVIncOperand(Instruction *IncV,
/// it available to other uses in this loop. Recursively hoist any operands,
/// until we reach a value that dominates InsertPos.
bool SCEVExpander::hoistIVInc(Instruction *IncV, Instruction *InsertPos) {
- if (SE.DT->properlyDominates(IncV, InsertPos))
+ if (SE.DT->dominates(IncV, InsertPos))
return true;
// InsertPos must itself dominate IncV so that IncV's new position satisfies
@@ -964,7 +963,7 @@ bool SCEVExpander::hoistIVInc(Instruction *IncV, Instruction *InsertPos) {
// IncV is safe to hoist.
IVIncs.push_back(IncV);
IncV = Oper;
- if (SE.DT->properlyDominates(IncV, InsertPos))
+ if (SE.DT->dominates(IncV, InsertPos))
break;
}
for (SmallVectorImpl<Instruction*>::reverse_iterator I = IVIncs.rbegin(),
diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index d052f2455d..af51a05c8b 100644
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -80,27 +80,97 @@ void DominatorTree::print(raw_ostream &OS, const Module *) const {
DT->print(OS);
}
-// dominates - Return true if A dominates a use in B. This performs the
-// special checks necessary if A and B are in the same basic block.
-bool DominatorTree::dominates(const Instruction *A, const Instruction *B) const{
- const BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
+// dominates - Return true if Def dominates a use in User. This performs
+// the special checks necessary if Def and User are in the same basic block.
+// Note that Def doesn't dominate a use in Def itself!
+bool DominatorTree::dominates(const Instruction *Def,
+ const Instruction *User) const {
+ const BasicBlock *UseBB = User->getParent();
+ const BasicBlock *DefBB = Def->getParent();
+
+ assert(isReachableFromEntry(DefBB) && isReachableFromEntry(UseBB) &&
+ "We only handle reachable blocks");
+
+ // An instruction doesn't dominate a use in itself.
+ if (Def == User)
+ return false;
+
+ // The value defined by an invoke dominates an instruction only if
+ // it dominates every instruction in UseBB.
+ // A PHI is dominated only if the instruction dominates every possible use
+ // in the UseBB.
+ if (isa<InvokeInst>(Def) || isa<PHINode>(User))
+ return dominates(Def, UseBB);
+
+ if (DefBB != UseBB)
+ return dominates(DefBB, UseBB);
- // If A is an invoke instruction, its value is only available in this normal
- // successor block.
- if (const InvokeInst *II = dyn_cast<InvokeInst>(A))
- BBA = II->getNormalDest();
+ // Loop through the basic block until we find Def or User.
+ BasicBlock::const_iterator I = DefBB->begin();
+ for (; &*I != Def && &*I != User; ++I)
+ /*empty*/;
+
+ return &*I == Def;
+}
- if (BBA != BBB) return dominates(BBA, BBB);
+// true if Def would dominate a use in any instruction in UseBB.
+// note that dominates(Def, Def->getParent()) is false.
+bool DominatorTree::dominates(const Instruction *Def,
+ const BasicBlock *UseBB) const {
+ const BasicBlock *DefBB = Def->getParent();
- // It is not possible to determine dominance between two PHI nodes
- // based on their ordering.
- if (isa<PHINode>(A) && isa<PHINode>(B))
+ assert(isReachableFromEntry(DefBB) && isReachableFromEntry(UseBB) &&
+ "We only handle reachable blocks");
+
+ if (DefBB == UseBB)
return false;
- // Loop through the basic block until we find A or B.
- BasicBlock::const_iterator I = BBA->begin();
- for (; &*I != A && &*I != B; ++I)
- /*empty*/;
+ const InvokeInst *II = dyn_cast<InvokeInst>(Def);
+ if (!II)
+ return dominates(DefBB, UseBB);
- return &*I == A;
+ // Invoke results are only usable in the normal destination, not in the
+ // exceptional destination.
+ BasicBlock *NormalDest = II->getNormalDest();
+ if (!dominates(NormalDest, UseBB))
+ return false;
+
+ // Simple case: if the normal destination has a single predecessor, the
+ // fact that it dominates the use block implies that we also do.
+ if (NormalDest->getSinglePredecessor())
+ return true;
+
+ // The normal edge from the invoke is critical. Conceptually, what we would
+ // like to do is split it and check if the new block dominates the use.
+ // With X being the new block, the graph would look like:
+ //
+ // DefBB
+ // /\ . .
+ // / \ . .
+ // / \ . .
+ // / \ | |
+ // A X B C
+ // | \ | /
+ // . \|/
+ // . NormalDest
+ // .
+ //
+ // Given the definition of dominance, NormalDest is dominated by X iff X
+ // dominates all of NormalDest's predecessors (X, B, C in the example). X
+ // trivially dominates itself, so we only have to find if it dominates the
+ // other predecessors. Since the only way out of X is via NormalDest, X can
+ // only properly dominate a node if NormalDest dominates that node too.
+ for (pred_iterator PI = pred_begin(NormalDest),
+ E = pred_end(NormalDest); PI != E; ++PI) {
+ const BasicBlock *BB = *PI;
+ if (BB == DefBB)
+ continue;
+
+ if (!DT->isReachableFromEntry(BB))
+ continue;
+
+ if (!dominates(NormalDest, BB))
+ return false;
+ }
+ return true;
}
diff --git a/test/Analysis/Dominators/invoke.ll b/test/Analysis/Dominators/invoke.ll
new file mode 100644
index 0000000000..f935750c98
--- /dev/null
+++ b/test/Analysis/Dominators/invoke.ll
@@ -0,0 +1,19 @@
+; RUN: opt -verify -disable-output %s
+; This tests that we handle unreachable blocks correctly
+
+define void @f() {
+ %v1 = invoke i32* @g()
+ to label %bb1 unwind label %bb2
+ invoke void @__dynamic_cast()
+ to label %bb1 unwind label %bb2
+bb1:
+ %Hidden = getelementptr inbounds i32* %v1, i64 1
+ ret void
+bb2:
+ %lpad.loopexit80 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*)
+ cleanup
+ ret void
+}
+declare i32 @__gxx_personality_v0(...)
+declare void @__dynamic_cast()
+declare i32* @g()
diff --git a/test/Transforms/LoopStrengthReduce/dominate-assert.ll b/test/Transforms/LoopStrengthReduce/dominate-assert.ll
new file mode 100644
index 0000000000..89f2f60334
--- /dev/null
+++ b/test/Transforms/LoopStrengthReduce/dominate-assert.ll
@@ -0,0 +1,40 @@
+; RUN: opt -loop-reduce %s
+; we used to crash on this one
+
+declare i8* @_Znwm()
+declare i32 @__gxx_personality_v0(...)
+declare void @g()
+define void @f() {
+bb0:
+ br label %bb1
+bb1:
+ %v0 = phi i64 [ 0, %bb0 ], [ %v1, %bb1 ]
+ %v1 = add nsw i64 %v0, 1
+ br i1 undef, label %bb2, label %bb1
+bb2:
+ %v2 = icmp eq i64 %v0, 0
+ br i1 %v2, label %bb6, label %bb3
+bb3:
+ %v3 = invoke noalias i8* @_Znwm()
+ to label %bb5 unwind label %bb4
+bb4:
+ %v4 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*)
+ cleanup
+ br label %bb9
+bb5:
+ %v5 = bitcast i8* %v3 to i32**
+ %add.ptr.i = getelementptr inbounds i32** %v5, i64 %v0
+ br label %bb6
+bb6:
+ %v6 = phi i32** [ null, %bb2 ], [ %add.ptr.i, %bb5 ]
+ invoke void @g()
+ to label %bb7 unwind label %bb8
+bb7:
+ unreachable
+bb8:
+ %v7 = landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*)
+ cleanup
+ br label %bb9
+bb9:
+ resume { i8*, i32 } zeroinitializer
+}
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-27 07:40:00 +0000