aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/Analysis/MemoryDependenceAnalysis.h7
-rw-r--r--lib/Analysis/MemoryDependenceAnalysis.cpp72
-rw-r--r--lib/Transforms/Scalar/GVN.cpp44
-rw-r--r--test/Transforms/GVN/pre-load.ll34
4 files changed, 134 insertions, 23 deletions
diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h
index cbb27a5218..042c7fc73f 100644
--- a/include/llvm/Analysis/MemoryDependenceAnalysis.h
+++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h
@@ -250,6 +250,13 @@ namespace llvm {
Value *PHITranslatePointer(Value *V,
BasicBlock *CurBB, BasicBlock *PredBB,
const TargetData *TD) const;
+
+ /// InsertPHITranslatedPointer - Insert a computation of the PHI translated
+ /// version of 'V' for the edge PredBB->CurBB into the end of the PredBB
+ /// block.
+ Value *InsertPHITranslatedPointer(Value *V,
+ BasicBlock *CurBB, BasicBlock *PredBB,
+ const TargetData *TD) const;
/// removeInstruction - Remove an instruction from the dependence analysis,
/// updating the dependence of instructions that previously depended on it.
diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp
index bb5b76cef9..95e9437339 100644
--- a/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -752,19 +752,35 @@ PHITranslatePointer(Value *InVal, BasicBlock *CurBB, BasicBlock *Pred,
// Handle getelementptr with at least one PHI operand.
if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
SmallVector<Value*, 8> GEPOps;
- Value *APHIOp = 0;
BasicBlock *CurBB = GEP->getParent();
for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) {
- GEPOps.push_back(GEP->getOperand(i)->DoPHITranslation(CurBB, Pred));
- if (!isa<Constant>(GEPOps.back()))
- APHIOp = GEPOps.back();
+ Value *GEPOp = GEP->getOperand(i);
+ // No PHI translation is needed of operands whose values are live in to
+ // the predecessor block.
+ if (!isa<Instruction>(GEPOp) ||
+ cast<Instruction>(GEPOp)->getParent() != CurBB) {
+ GEPOps.push_back(GEPOp);
+ continue;
+ }
+
+ // If the operand is a phi node, do phi translation.
+ if (PHINode *PN = dyn_cast<PHINode>(GEPOp)) {
+ GEPOps.push_back(PN->getIncomingValueForBlock(Pred));
+ continue;
+ }
+
+ // Otherwise, we can't PHI translate this random value defined in this
+ // block.
+ return 0;
}
// Simplify the GEP to handle 'gep x, 0' -> x etc.
if (Value *V = SimplifyGEPInst(&GEPOps[0], GEPOps.size(), TD))
return V;
-
+
+
// Scan to see if we have this GEP available.
+ Value *APHIOp = GEPOps[0];
for (Value::use_iterator UI = APHIOp->use_begin(), E = APHIOp->use_end();
UI != E; ++UI) {
if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI))
@@ -787,6 +803,52 @@ PHITranslatePointer(Value *InVal, BasicBlock *CurBB, BasicBlock *Pred,
return 0;
}
+/// InsertPHITranslatedPointer - Insert a computation of the PHI translated
+/// version of 'V' for the edge PredBB->CurBB into the end of the PredBB
+/// block.
+///
+/// This is only called when PHITranslatePointer returns a value that doesn't
+/// dominate the block, so we don't need to handle the trivial cases here.
+Value *MemoryDependenceAnalysis::
+InsertPHITranslatedPointer(Value *InVal, BasicBlock *CurBB,
+ BasicBlock *PredBB, const TargetData *TD) const {
+ // If the input value isn't an instruction in CurBB, it doesn't need phi
+ // translation.
+ Instruction *Inst = cast<Instruction>(InVal);
+ assert(Inst->getParent() == CurBB && "Doesn't need phi trans");
+
+ // Handle bitcast of PHI.
+ if (BitCastInst *BC = dyn_cast<BitCastInst>(Inst)) {
+ PHINode *BCPN = cast<PHINode>(BC->getOperand(0));
+ Value *PHIIn = BCPN->getIncomingValueForBlock(PredBB);
+
+ // Otherwise insert a bitcast at the end of PredBB.
+ return new BitCastInst(PHIIn, InVal->getType(),
+ InVal->getName()+".phi.trans.insert",
+ PredBB->getTerminator());
+ }
+
+ // Handle getelementptr with at least one PHI operand.
+ if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
+ SmallVector<Value*, 8> GEPOps;
+ Value *APHIOp = 0;
+ BasicBlock *CurBB = GEP->getParent();
+ for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) {
+ GEPOps.push_back(GEP->getOperand(i)->DoPHITranslation(CurBB, PredBB));
+ if (!isa<Constant>(GEPOps.back()))
+ APHIOp = GEPOps.back();
+ }
+
+ GetElementPtrInst *Result =
+ GetElementPtrInst::Create(GEPOps[0], GEPOps.begin()+1, GEPOps.end(),
+ InVal->getName()+".phi.trans.insert",
+ PredBB->getTerminator());
+ Result->setIsInBounds(GEP->isInBounds());
+ return Result;
+ }
+
+ return 0;
+}
/// getNonLocalPointerDepFromBB - Perform a dependency query based on
/// pointer/pointeesize starting at the end of StartBB. Add any clobber/def
diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index e878050364..72eb9002ce 100644
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -1425,32 +1425,40 @@ bool GVN::processNonLocalLoad(LoadInst *LI,
assert(UnavailablePred != 0 &&
"Fully available value should be eliminated above!");
+ // We don't currently handle critical edges :(
+ if (UnavailablePred->getTerminator()->getNumSuccessors() != 1) {
+ DEBUG(errs() << "COULD NOT PRE LOAD BECAUSE OF CRITICAL EDGE '"
+ << UnavailablePred->getName() << "': " << *LI << '\n');
+ return false;
+ }
+
// If the loaded pointer is PHI node defined in this block, do PHI translation
// to get its value in the predecessor.
Value *LoadPtr = MD->PHITranslatePointer(LI->getOperand(0),
LoadBB, UnavailablePred, TD);
+ // Make sure the value is live in the predecessor. MemDep found a computation
+ // of LPInst with the right value, but that does not dominate UnavailablePred,
+ // then we can't use it.
+ if (Instruction *LPInst = dyn_cast_or_null<Instruction>(LoadPtr))
+ if (!DT->dominates(LPInst->getParent(), UnavailablePred))
+ LoadPtr = 0;
+
+ // If we don't have a computation of this phi translated value, try to insert
+ // one.
if (LoadPtr == 0) {
- DEBUG(errs() << "COULDN'T PRE LOAD BECAUSE PTR CAN'T BE PHI TRANSLATED: "
- << *LI->getOperand(0) << '\n' << *LI << "\n");
- return false;
- }
-
- // Make sure the value is live in the predecessor. If it was defined by a
- // non-PHI instruction in this block, we don't know how to recompute it above.
- if (Instruction *LPInst = dyn_cast<Instruction>(LoadPtr))
- if (!DT->dominates(LPInst->getParent(), UnavailablePred)) {
- DEBUG(errs() << "COULDN'T PRE LOAD BECAUSE PTR DOES NOT DOMINATE PRED: "
- << *LPInst << '\n' << *LI << "\n");
+ LoadPtr = MD->InsertPHITranslatedPointer(LI->getOperand(0),
+ LoadBB, UnavailablePred, TD);
+ if (LoadPtr == 0) {
+ DEBUG(errs() << "COULDN'T INSERT PHI TRANSLATED VALUE OF: "
+ << *LI->getOperand(0) << "\n");
return false;
}
-
- // We don't currently handle critical edges :(
- if (UnavailablePred->getTerminator()->getNumSuccessors() != 1) {
- DEBUG(errs() << "COULD NOT PRE LOAD BECAUSE OF CRITICAL EDGE '"
- << UnavailablePred->getName() << "': " << *LI << '\n');
- return false;
+
+ // FIXME: This inserts a computation, but we don't tell scalar GVN
+ // optimization stuff about it. How do we do this?
+ DEBUG(errs() << "INSERTED PHI TRANSLATED VALUE: " << *LoadPtr << "\n");
}
-
+
// Make sure it is valid to move this load here. We have to watch out for:
// @1 = getelementptr (i8* p, ...
// test p and branch if == 0
diff --git a/test/Transforms/GVN/pre-load.ll b/test/Transforms/GVN/pre-load.ll
index 637a6d26c8..3cb67135ac 100644
--- a/test/Transforms/GVN/pre-load.ll
+++ b/test/Transforms/GVN/pre-load.ll
@@ -22,6 +22,7 @@ block4:
; CHECK-NEXT: ret i32
}
+; This is a simple phi translation case.
define i32 @test2(i32* %p, i32* %q, i1 %C) {
; CHECK: @test2
block1:
@@ -46,6 +47,7 @@ block4:
; CHECK: ret i32
}
+; This is a PRE case that requires phi translation through a GEP.
define i32 @test3(i32* %p, i32* %q, i32** %Hack, i1 %C) {
; CHECK: @test3
block1:
@@ -73,3 +75,35 @@ block4:
; CHECK-NOT: load
; CHECK: ret i32
}
+
+;; Here the loaded address is available, but the computation is in 'block3'
+;; which does not dominate 'block2'.
+define i32 @test4(i32* %p, i32* %q, i32** %Hack, i1 %C) {
+; CHECK: @test4
+block1:
+ br i1 %C, label %block2, label %block3
+
+block2:
+ br label %block4
+; CHECK: block2:
+; CHECK: load i32*
+; CHECK: br label %block4
+
+block3:
+ %B = getelementptr i32* %q, i32 1
+ store i32* %B, i32** %Hack
+
+ %A = getelementptr i32* %p, i32 1
+ store i32 0, i32* %A
+ br label %block4
+
+block4:
+ %P2 = phi i32* [%p, %block3], [%q, %block2]
+ %P3 = getelementptr i32* %P2, i32 1
+ %PRE = load i32* %P3
+ ret i32 %PRE
+; CHECK: block4:
+; CHECK-NEXT: phi i32 [
+; CHECK-NOT: load
+; CHECK: ret i32
+}
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-07-05 15:44:17 +0000