diff options
| -rw-r--r-- | include/llvm/Transforms/Scalar/GCSE.h | 16 | ||||
| -rw-r--r-- | lib/Transforms/Scalar/GCSE.cpp | 272 |
2 files changed, 288 insertions, 0 deletions
diff --git a/include/llvm/Transforms/Scalar/GCSE.h b/include/llvm/Transforms/Scalar/GCSE.h new file mode 100644 index 0000000..f3b005f --- /dev/null +++ b/include/llvm/Transforms/Scalar/GCSE.h @@ -0,0 +1,16 @@ +//===-- GCSE.h - SSA based Global Common Subexpr Elimination -----*- C++ -*--=// +// +// This pass is designed to be a very quick global transformation that +// eliminates global common subexpressions from a function. It does this by +// examining the SSA value graph of the function, instead of doing slow +// bit-vector computations. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_GCSE_H +#define LLVM_TRANSFORMS_SCALAR_GCSE_H + +class Pass; +Pass *createGCSEPass(); + +#endif diff --git a/lib/Transforms/Scalar/GCSE.cpp b/lib/Transforms/Scalar/GCSE.cpp new file mode 100644 index 0000000..d3f893f --- /dev/null +++ b/lib/Transforms/Scalar/GCSE.cpp @@ -0,0 +1,272 @@ +//===-- GCSE.cpp - SSA based Global Common Subexpr Elimination ------------===// +// +// This pass is designed to be a very quick global transformation that +// eliminates global common subexpressions from a function. It does this by +// examining the SSA value graph of the function, instead of doing slow, dense, +// bit-vector computations. +// +// This pass works best if it is proceeded with a simple constant propogation +// pass and an instruction combination pass because this pass does not do any +// value numbering (in order to be speedy). +// +// This pass does not attempt to CSE load instructions, because it does not use +// pointer analysis to determine when it is safe. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Scalar/GCSE.h" +#include "llvm/Pass.h" +#include "llvm/InstrTypes.h" +#include "llvm/iMemory.h" +#include "llvm/Analysis/Dominators.h" +#include "llvm/Support/InstVisitor.h" +#include "llvm/Support/InstIterator.h" +#include <set> +#include <algorithm> +using namespace cfg; + +namespace { + class GCSE : public FunctionPass, public InstVisitor<GCSE, bool> { + set<Instruction*> WorkList; + DominatorSet *DomSetInfo; + ImmediateDominators *ImmDominator; + public: + virtual bool runOnFunction(Function *F); + + // Visitation methods, these are invoked depending on the type of + // instruction being checked. They should return true if a common + // subexpression was folded. + // + bool visitUnaryOperator(Instruction *I); + bool visitBinaryOperator(Instruction *I); + bool visitGetElementPtrInst(GetElementPtrInst *I); + bool visitCastInst(CastInst *I){return visitUnaryOperator((Instruction*)I);} + bool visitShiftInst(ShiftInst *I) { + return visitBinaryOperator((Instruction*)I); + } + bool visitInstruction(Instruction *) { return false; } + + private: + void ReplaceInstWithInst(Instruction *First, BasicBlock::iterator SI); + void CommonSubExpressionFound(Instruction *I, Instruction *Other); + + // This transformation requires dominator and immediate dominator info + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + //preservesCFG(AU); + AU.addRequired(DominatorSet::ID); + AU.addRequired(ImmediateDominators::ID); + } + }; +} + +// createGCSEPass - The public interface to this file... +Pass *createGCSEPass() { return new GCSE(); } + + +// GCSE::runOnFunction - This is the main transformation entry point for a +// function. +// +bool GCSE::runOnFunction(Function *F) { + bool Changed = false; + + DomSetInfo = &getAnalysis<DominatorSet>(); + ImmDominator = &getAnalysis<ImmediateDominators>(); + + // Step #1: Add all instructions in the function to the worklist for + // processing. All of the instructions are considered to be our + // subexpressions to eliminate if possible. + // + WorkList.insert(inst_begin(F), inst_end(F)); + + // Step #2: WorkList processing. Iterate through all of the instructions, + // checking to see if there are any additionally defined subexpressions in the + // program. If so, eliminate them! + // + while (!WorkList.empty()) { + Instruction *I = *WorkList.begin(); // Get an instruction from the worklist + WorkList.erase(WorkList.begin()); + + // Visit the instruction, dispatching to the correct visit function based on + // the instruction type. This does the checking. + // + Changed |= visit(I); + } + + // When the worklist is empty, return whether or not we changed anything... + return Changed; +} + + +// ReplaceInstWithInst - Destroy the instruction pointed to by SI, making all +// uses of the instruction use First now instead. +// +void GCSE::ReplaceInstWithInst(Instruction *First, BasicBlock::iterator SI) { + Instruction *Second = *SI; + + // Add the first instruction back to the worklist + WorkList.insert(First); + + // Add all uses of the second instruction to the worklist + for (Value::use_iterator UI = Second->use_begin(), UE = Second->use_end(); + UI != UE; ++UI) + WorkList.insert(cast<Instruction>(*UI)); + + // Make all users of 'Second' now use 'First' + Second->replaceAllUsesWith(First); + + // Erase the second instruction from the program + delete Second->getParent()->getInstList().remove(SI); +} + +// CommonSubExpressionFound - The two instruction I & Other have been found to +// be common subexpressions. This function is responsible for eliminating one +// of them, and for fixing the worklist to be correct. +// +void GCSE::CommonSubExpressionFound(Instruction *I, Instruction *Other) { + // I has already been removed from the worklist, Other needs to be. + assert(WorkList.count(I) == 0 && WorkList.count(Other) && + "I in worklist or Other not!"); + WorkList.erase(Other); + + // Handle the easy case, where both instructions are in the same basic block + BasicBlock *BB1 = I->getParent(), *BB2 = Other->getParent(); + if (BB1 == BB2) { + // Eliminate the second occuring instruction. Add all uses of the second + // instruction to the worklist. + // + // Scan the basic block looking for the "first" instruction + BasicBlock::iterator BI = BB1->begin(); + while (*BI != I && *BI != Other) { + ++BI; + assert(BI != BB1->end() && "Instructions not found in parent BB!"); + } + + // Keep track of which instructions occurred first & second + Instruction *First = *BI; + Instruction *Second = I != First ? I : Other; // Get iterator to second inst + BI = find(BI, BB1->end(), Second); + assert(BI != BB1->end() && "Second instruction not found in parent block!"); + + // Destroy Second, using First instead. + ReplaceInstWithInst(First, BI); + + // Otherwise, the two instructions are in different basic blocks. If one + // dominates the other instruction, we can simply use it + // + } else if (DomSetInfo->dominates(BB1, BB2)) { // I dom Other? + BasicBlock::iterator BI = find(BB2->begin(), BB2->end(), Other); + assert(BI != BB2->end() && "Other not in parent basic block!"); + ReplaceInstWithInst(I, BI); + } else if (DomSetInfo->dominates(BB2, BB1)) { // Other dom I? + BasicBlock::iterator BI = find(BB1->begin(), BB1->end(), I); + assert(BI != BB1->end() && "I not in parent basic block!"); + ReplaceInstWithInst(Other, BI); + } else { + // Handle the most general case now. In this case, neither I dom Other nor + // Other dom I. Because we are in SSA form, we are guaranteed that the + // operands of the two instructions both dominate the uses, so we _know_ + // that there must exist a block that dominates both instructions (if the + // operands of the instructions are globals or constants, worst case we + // would get the entry node of the function). Search for this block now. + // + + // Search up the immediate dominator chain of BB1 for the shared dominator + BasicBlock *SharedDom = (*ImmDominator)[BB1]; + while (!DomSetInfo->dominates(SharedDom, BB2)) + SharedDom = (*ImmDominator)[SharedDom]; + + // At this point, shared dom must dominate BOTH BB1 and BB2... + assert(SharedDom && DomSetInfo->dominates(SharedDom, BB1) && + DomSetInfo->dominates(SharedDom, BB2) && "Dominators broken!"); + + // Rip 'I' out of BB1, and move it to the end of SharedDom. + BB1->getInstList().remove(I); + SharedDom->getInstList().insert(SharedDom->end()-1, I); + + // Eliminate 'Other' now. + BasicBlock::iterator BI = find(BB2->begin(), BB2->end(), Other); + assert(BI != BB2->end() && "I not in parent basic block!"); + ReplaceInstWithInst(I, BI); + } +} + +//===----------------------------------------------------------------------===// +// +// Visitation methods, these are invoked depending on the type of instruction +// being checked. They should return true if a common subexpression was folded. +// +//===----------------------------------------------------------------------===// + +bool GCSE::visitUnaryOperator(Instruction *I) { + Value *Op = I->getOperand(0); + Function *F = I->getParent()->getParent(); + + for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end(); + UI != UE; ++UI) + if (Instruction *Other = dyn_cast<Instruction>(*UI)) + // Check to see if this new binary operator is not I, but same operand... + if (Other != I && Other->getOpcode() == I->getOpcode() && + Other->getOperand(0) == Op && // Is the operand the same? + // Is it embeded in the same function? (This could be false if LHS + // is a constant or global!) + Other->getParent()->getParent() == F && + + // Check that the types are the same, since this code handles casts... + Other->getType() == I->getType()) { + + // These instructions are identical. Handle the situation. + CommonSubExpressionFound(I, Other); + return true; // One instruction eliminated! + } + + return false; +} + +bool GCSE::visitBinaryOperator(Instruction *I) { + Value *LHS = I->getOperand(0), *RHS = I->getOperand(1); + Function *F = I->getParent()->getParent(); + + for (Value::use_iterator UI = LHS->use_begin(), UE = LHS->use_end(); + UI != UE; ++UI) + if (Instruction *Other = dyn_cast<Instruction>(*UI)) + // Check to see if this new binary operator is not I, but same operand... + if (Other != I && Other->getOpcode() == I->getOpcode() && + // Are the LHS and RHS the same? + Other->getOperand(0) == LHS && Other->getOperand(1) == RHS && + // Is it embeded in the same function? (This could be false if LHS + // is a constant or global!) + Other->getParent()->getParent() == F) { + + // These instructions are identical. Handle the situation. + CommonSubExpressionFound(I, Other); + return true; // One instruction eliminated! + } + + return false; +} + +bool GCSE::visitGetElementPtrInst(GetElementPtrInst *I) { + Value *Op = I->getOperand(0); + Function *F = I->getParent()->getParent(); + + for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end(); + UI != UE; ++UI) + if (GetElementPtrInst *Other = dyn_cast<GetElementPtrInst>(*UI)) + // Check to see if this new binary operator is not I, but same operand... + if (Other != I && Other->getParent()->getParent() == F && + Other->getType() == I->getType()) { + + // Check to see that all operators past the 0th are the same... + unsigned i = 1, e = I->getNumOperands(); + for (; i != e; ++i) + if (I->getOperand(i) != Other->getOperand(i)) break; + + if (i == e) { + // These instructions are identical. Handle the situation. + CommonSubExpressionFound(I, Other); + return true; // One instruction eliminated! + } + } + + return false; +} |