From 45537917eec15e5c3ef75c0ee2bf8963b02f3a54 Mon Sep 17 00:00:00 2001 From: Owen Anderson Date: Thu, 26 Jul 2007 18:26:51 +0000 Subject: [PATCH] Fix a couple more bugs in the phi construction by pulling in code that does almost the same things from LCSSA. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40540 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/MemoryDependenceAnalysis.cpp | 3 - lib/Transforms/Scalar/GVN.cpp | 93 +++++++------------ .../GVN/2007-07-26-InterlockingLoops.ll | 30 ++++++ test/Transforms/GVN/2007-07-26-PhiErasure.ll | 28 ++++++ 4 files changed, 93 insertions(+), 61 deletions(-) create mode 100644 test/Transforms/GVN/2007-07-26-InterlockingLoops.ll create mode 100644 test/Transforms/GVN/2007-07-26-PhiErasure.ll diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp index e260b271641..064a0872bb0 100644 --- a/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -124,9 +124,6 @@ bool MemoryDependenceAnalysis::nonLocalHelper(Instruction* query, visited.erase(block); - if (!inserted) - resp.insert(std::make_pair(block, None)); - return inserted; } diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp index d7e622857ae..119a9e4a841 100644 --- a/lib/Transforms/Scalar/GVN.cpp +++ b/lib/Transforms/Scalar/GVN.cpp @@ -13,12 +13,14 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "gvn" -#include "llvm/Value.h" + #include "llvm/Transforms/Scalar.h" #include "llvm/BasicBlock.h" -#include "llvm/Instructions.h" -#include "llvm/Function.h" +#include "llvm/Constants.h" #include "llvm/DerivedTypes.h" +#include "llvm/Function.h" +#include "llvm/Instructions.h" +#include "llvm/Value.h" #include "llvm/Analysis/Dominators.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseMap.h" @@ -650,9 +652,8 @@ namespace { DenseMap& lastSeenLoad, SmallVector& toErase); bool processNonLocalLoad(LoadInst* L, SmallVector& toErase); - Value *performPHIConstruction(BasicBlock *BB, LoadInst* orig, - DenseMap &Phis, - SmallPtrSet& visited); + Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig, + DenseMap &Phis); void dump(DenseMap& d); }; @@ -706,59 +707,35 @@ void GVN::dump(DenseMap& d) { } -Value *GVN::performPHIConstruction(BasicBlock *BB, LoadInst* orig, - DenseMap &Phis, - SmallPtrSet& visited) { - DenseMap::iterator DI = Phis.find(BB); - if (DI != Phis.end()) - return DI->second; +/// GetValueForBlock - Get the value to use within the specified basic block. +/// available values are in Phis. +Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig, + DenseMap &Phis) { + DominatorTree &DT = getAnalysis(); + + // If we have already computed this value, return the previously computed val. + Value *&V = Phis[BB]; + if (V) return V; + + DomTreeNode *IDom = DT.getNode(BB)->getIDom(); + + if (IDom && Phis.count(IDom->getBlock())) { + return V = GetValueForBlock(IDom->getBlock(), orig, Phis); + } - unsigned numPreds = std::distance(pred_begin(BB), pred_end(BB)); - if (numPreds == 1) { - DenseMap::iterator DI = Phis.find(BB); - if (DI != Phis.end()) { - Phis.insert(std::make_pair(BB, DI->second)); - return DI->second; - } else { - visited.insert(BB); - Value* domV = performPHIConstruction(*pred_begin(BB), orig, Phis, visited); - visited.erase(BB); - - Phis.insert(std::make_pair(BB, domV)); - return domV; - } - } else { - PHINode *PN = new PHINode(orig->getType(), orig->getName()+".rle", BB->begin()); - PN->reserveOperandSpace(numPreds); - Phis[BB] = PN; - - visited.insert(BB); - // Fill in the incoming values for the block. - for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) - if (!visited.count(*PI)) - PN->addIncoming(performPHIConstruction(*PI, orig, Phis, visited), *PI); - else { - if (Phis[*PI]) - PN->addIncoming(Phis[*PI], *PI); - else - PN->addIncoming(PN, *PI); - } - visited.erase(BB); - - bool all_same = PN->getNumIncomingValues() != 1; - Value* first = PN->getIncomingValue(0); - for (unsigned i = 1; i < PN->getNumIncomingValues(); ++i) - all_same &= (PN->getIncomingValue(i) == first); - - if (all_same) { - PN->eraseFromParent(); - Phis[BB] = first; - return first; - } else { - return PN; - } - } + + // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so + // now, then get values to fill in the incoming values for the PHI. + PHINode *PN = new PHINode(orig->getType(), orig->getName()+".rle", + BB->begin()); + PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB))); + V = PN; + + // Fill in the incoming values for the block. + for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) + PN->addIncoming(GetValueForBlock(DT.getNode(*PI)->getBlock(), orig, Phis), *PI); + return PN; } bool GVN::processNonLocalLoad(LoadInst* L, SmallVector& toErase) { @@ -789,7 +766,7 @@ bool GVN::processNonLocalLoad(LoadInst* L, SmallVector& toErase } SmallPtrSet visited; - Value* v = performPHIConstruction(L->getParent(), L, repl, visited); + Value* v = GetValueForBlock(L->getParent(), L, repl); MD.removeInstruction(L); L->replaceAllUsesWith(v); diff --git a/test/Transforms/GVN/2007-07-26-InterlockingLoops.ll b/test/Transforms/GVN/2007-07-26-InterlockingLoops.ll new file mode 100644 index 00000000000..1dd1479b482 --- /dev/null +++ b/test/Transforms/GVN/2007-07-26-InterlockingLoops.ll @@ -0,0 +1,30 @@ +; RUN: llvm-as < %s | opt -gvn | llvm-dis | not grep {tmp17625 =} +; RUN: llvm-as < %s | opt -gvn | llvm-dis | not grep {tmp17631 =} + +@last = external global [65 x i32*] ; <[65 x i32*]*> [#uses=1] + +define i32 @NextRootMove(i32 %wtm) { +cond_next95: ; preds = %cond_true85, %cond_true79, %cond_true73, %bb68 + %tmp17618 = load i32** getelementptr ([65 x i32*]* @last, i32 0, i32 1), align 4 ; [#uses=0] + br label %cond_true116 + +cond_true116: ; preds = %cond_true111 + br i1 false, label %cond_true128, label %cond_true145 + +cond_true128: ; preds = %cond_true121 + %tmp17625 = load i32** getelementptr ([65 x i32*]* @last, i32 0, i32 1), align 4 ; [#uses=0] + br i1 false, label %bb98.backedge, label %return.loopexit + +bb98.backedge: ; preds = %bb171, %cond_true145, %cond_true128 + br label %cond_true116 + +cond_true145: ; preds = %cond_false + %tmp17631 = load i32** getelementptr ([65 x i32*]* @last, i32 0, i32 1), align 4 ; [#uses=0] + br i1 false, label %bb98.backedge, label %return.loopexit + +return.loopexit: ; preds = %bb171, %cond_true145, %cond_true128 + br label %return + +return: ; preds = %return.loopexit, %cond_next95, %cond_true85 + ret i32 0 +} diff --git a/test/Transforms/GVN/2007-07-26-PhiErasure.ll b/test/Transforms/GVN/2007-07-26-PhiErasure.ll new file mode 100644 index 00000000000..52c5b8e7ec8 --- /dev/null +++ b/test/Transforms/GVN/2007-07-26-PhiErasure.ll @@ -0,0 +1,28 @@ +; RUN: llvm-as < %s | opt -gvn | llvm-dis | not grep {tmp298316 =} + + %struct..0anon = type { i32 } + %struct.FILE = type { i8*, i32, i32, i16, i16, %struct.__sbuf, i32, i8*, i32 (i8*)*, i32 (i8*, i8*, i32)*, i64 (i8*, i64, i32)*, i32 (i8*, i8*, i32)*, %struct.__sbuf, %struct.__sFILEX*, i32, [3 x i8], [1 x i8], %struct.__sbuf, i32, i64 } + %struct.__sFILEX = type opaque + %struct.__sbuf = type { i8*, i32 } + %struct.rtx_def = type { i16, i8, i8, [1 x %struct..0anon] } +@n_spills = external global i32 ; [#uses=2] + +define i32 @reload(%struct.rtx_def* %first, i32 %global, %struct.FILE* %dumpfile) { +cond_next2835.1: ; preds = %cond_next2861 + %tmp2922 = load i32* @n_spills, align 4 ; [#uses=0] + br label %bb2928 + +bb2928: ; preds = %cond_next2835.1, %cond_next2943 + br i1 false, label %cond_next2943, label %cond_true2935 + +cond_true2935: ; preds = %bb2928 + br label %cond_next2943 + +cond_next2943: ; preds = %cond_true2935, %bb2928 + br i1 false, label %bb2982.preheader, label %bb2928 + +bb2982.preheader: ; preds = %cond_next2943 + %tmp298316 = load i32* @n_spills, align 4 ; [#uses=0] + ret i32 0 + +} -- 2.34.1