diff options
| -rw-r--r-- | lib/Transforms/Scalar/EarlyCSE.cpp | 145 | ||||
| -rw-r--r-- | test/Transforms/EarlyCSE/basic.ll | 21 | ||||
| -rw-r--r-- | test/Transforms/EarlyCSE/dg.exp | 3 |
3 files changed, 165 insertions, 4 deletions
diff --git a/lib/Transforms/Scalar/EarlyCSE.cpp b/lib/Transforms/Scalar/EarlyCSE.cpp index 4445404..a43d425 100644 --- a/lib/Transforms/Scalar/EarlyCSE.cpp +++ b/lib/Transforms/Scalar/EarlyCSE.cpp @@ -14,11 +14,84 @@ #define DEBUG_TYPE "early-cse" #include "llvm/Transforms/Scalar.h" -#include "llvm/Analysis/Dominators.h" #include "llvm/Pass.h" +#include "llvm/Analysis/Dominators.h" +#include "llvm/Analysis/InstructionSimplify.h" +#include "llvm/Analysis/InstructionSimplify.h" +#include "llvm/Target/TargetData.h" +#include "llvm/Transforms/Utils/Local.h" +#include "llvm/ADT/ScopedHashTable.h" using namespace llvm; namespace { + /// InstValue - Instances of this struct represent available values in the + /// scoped hash table. + struct InstValue { + Instruction *Inst; + + bool isSentinel() const { + return Inst == DenseMapInfo<Instruction*>::getEmptyKey() || + Inst == DenseMapInfo<Instruction*>::getTombstoneKey(); + } + + static bool canHandle(Instruction *Inst) { + return isa<CastInst>(Inst); + } + + static InstValue get(Instruction *I) { + InstValue X; X.Inst = I; + assert((X.isSentinel() || canHandle(I)) && "Inst can't be handled!"); + return X; + } + }; +} + +namespace llvm { +// InstValue is POD. +template<> struct isPodLike<InstValue> { + static const bool value = true; +}; + +template<> struct DenseMapInfo<InstValue> { + static inline InstValue getEmptyKey() { + return InstValue::get(DenseMapInfo<Instruction*>::getEmptyKey()); + } + static inline InstValue getTombstoneKey() { + return InstValue::get(DenseMapInfo<Instruction*>::getTombstoneKey()); + } + static unsigned getHashValue(InstValue Val); + static bool isEqual(InstValue LHS, InstValue RHS); +}; +} + +unsigned getHash(const void *V) { + return DenseMapInfo<const void*>::getHashValue(V); +} + +unsigned DenseMapInfo<InstValue>::getHashValue(InstValue Val) { + Instruction *Inst = Val.Inst; + unsigned Res = 0; + if (CastInst *CI = dyn_cast<CastInst>(Inst)) + Res = getHash(CI->getOperand(0)) ^ getHash(CI->getType()); + else + assert(0 && "Unhandled instruction kind"); + + return (Res << 1) ^ Inst->getOpcode(); +} + +bool DenseMapInfo<InstValue>::isEqual(InstValue LHS, InstValue RHS) { + Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst; + + if (LHS.isSentinel() || RHS.isSentinel()) + return LHSI == RHSI; + + if (LHSI->getOpcode() != RHSI->getOpcode()) return false; + return LHSI->isIdenticalTo(RHSI); +} + + +namespace { + /// EarlyCSE - This pass does a simple depth-first walk over the dominator /// tree, eliminating trivially redundant instructions and using instsimplify /// to canonicalize things as it goes. It is intended to be fast and catch @@ -27,6 +100,10 @@ namespace { /// cases. class EarlyCSE : public FunctionPass { public: + const TargetData *TD; + DominatorTree *DT; + ScopedHashTable<InstValue, Instruction*> *AvailableValues; + static char ID; explicit EarlyCSE() : FunctionPass(ID) { @@ -36,6 +113,9 @@ public: bool runOnFunction(Function &F); private: + + bool processNode(DomTreeNode *Node); + // This transformation requires dominator postdominator info virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired<DominatorTree>(); @@ -55,8 +135,65 @@ INITIALIZE_PASS_BEGIN(EarlyCSE, "early-cse", "Early CSE", false, false) INITIALIZE_PASS_DEPENDENCY(DominatorTree) INITIALIZE_PASS_END(EarlyCSE, "early-cse", "Early CSE", false, false) +// FIXME: Should bump pointer allocate entries in scoped hash table. + +bool EarlyCSE::processNode(DomTreeNode *Node) { + // Define a scope in the scoped hash table. + ScopedHashTableScope<InstValue, Instruction*> Scope(*AvailableValues); + + BasicBlock *BB = Node->getBlock(); + + bool Changed = false; + + // See if any instructions in the block can be eliminated. If so, do it. If + // not, add them to AvailableValues. + for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { + Instruction *Inst = I++; + + // Dead instructions should just be removed. + if (isInstructionTriviallyDead(Inst)) { + Inst->eraseFromParent(); + Changed = true; + continue; + } + + // If the instruction can be simplified (e.g. X+0 = X) then replace it with + // its simpler value. + if (Value *V = SimplifyInstruction(Inst, TD, DT)) { + Inst->replaceAllUsesWith(V); + Inst->eraseFromParent(); + Changed = true; + continue; + } + + // If this instruction is something that we can't value number, ignore it. + if (!InstValue::canHandle(Inst)) + continue; + + // See if the instruction has an available value. If so, use it. + if (Instruction *V = AvailableValues->lookup(InstValue::get(Inst))) { + Inst->replaceAllUsesWith(V); + Inst->eraseFromParent(); + Changed = true; + continue; + } + + // Otherwise, just remember that this value is available. + AvailableValues->insert(InstValue::get(Inst), Inst); + } + + + for (DomTreeNode::iterator I = Node->begin(), E = Node->end(); I != E; ++I) + Changed |= processNode(*I); + return Changed; +} + + bool EarlyCSE::runOnFunction(Function &F) { - DominatorTree &DT = getAnalysis<DominatorTree>(); - (void)DT; - return false; + TD = getAnalysisIfAvailable<TargetData>(); + DT = &getAnalysis<DominatorTree>(); + ScopedHashTable<InstValue, Instruction*> AVTable; + AvailableValues = &AVTable; + return processNode(DT->getRootNode()); } + diff --git a/test/Transforms/EarlyCSE/basic.ll b/test/Transforms/EarlyCSE/basic.ll new file mode 100644 index 0000000..d42f503 --- /dev/null +++ b/test/Transforms/EarlyCSE/basic.ll @@ -0,0 +1,21 @@ +; RUN: opt < %s -S -early-cse | FileCheck %s + + +; CHECK: @test1 +define void @test1(i8 %V, i32 *%P) { + %A = bitcast i64 42 to double ;; dead + %B = add i32 4, 19 ;; constant folds + store i32 %B, i32* %P + + ; CHECK-NEXT: store i32 23, i32* %P + + %C = zext i8 %V to i32 + %D = zext i8 %V to i32 ;; CSE + volatile store i32 %C, i32* %P + volatile store i32 %D, i32* %P + + ; CHECK-NEXT: %C = zext i8 %V to i32 + ; CHECK-NEXT: volatile store i32 %C + ; CHECK-NEXT: volatile store i32 %C + ret void +} diff --git a/test/Transforms/EarlyCSE/dg.exp b/test/Transforms/EarlyCSE/dg.exp new file mode 100644 index 0000000..de42dad --- /dev/null +++ b/test/Transforms/EarlyCSE/dg.exp @@ -0,0 +1,3 @@ +load_lib llvm.exp + +RunLLVMTests [lsort [glob -nocomplain $srcdir/$subdir/*.ll]] |