//
// 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.
+// using an existing value numbering implementation to identify the common
+// subexpressions, eliminating them when possible.
//
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/Scalar.h"
-#include "llvm/InstrTypes.h"
#include "llvm/iMemory.h"
+#include "llvm/Type.h"
#include "llvm/Analysis/Dominators.h"
-#include "llvm/Support/InstVisitor.h"
+#include "llvm/Analysis/ValueNumbering.h"
#include "llvm/Support/InstIterator.h"
-#include "Support/StatisticReporter.h"
+#include "Support/Statistic.h"
#include <algorithm>
-static Statistic<> NumInstRemoved("gcse\t\t- Number of instructions removed");
-
namespace {
- class GCSE : public FunctionPass, public InstVisitor<GCSE, bool> {
- set<Instruction*> WorkList;
- DominatorSet *DomSetInfo;
- ImmediateDominators *ImmDominator;
+ Statistic<> NumInstRemoved("gcse", "Number of instructions removed");
+ Statistic<> NumLoadRemoved("gcse", "Number of loads removed");
+ Statistic<> NumNonInsts ("gcse", "Number of instructions removed due "
+ "to non-instruction values");
+
+ class GCSE : public FunctionPass {
+ std::set<Instruction*> WorkList;
+ DominatorSet *DomSetInfo;
+#if 0
+ ImmediateDominators *ImmDominator;
+#endif
+ ValueNumbering *VN;
public:
- const char *getPassName() const {
- return "Global Common Subexpression Elimination";
- }
-
- 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; }
+ virtual bool runOnFunction(Function &F);
private:
+ bool EliminateRedundancies(Instruction *I,std::vector<Value*> &EqualValues);
+ Instruction *EliminateCSE(Instruction *I, Instruction *Other);
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 {
- AU.preservesCFG();
- AU.addRequired(DominatorSet::ID);
- AU.addRequired(ImmediateDominators::ID);
+ AU.setPreservesCFG();
+ AU.addRequired<DominatorSet>();
+ AU.addRequired<ImmediateDominators>();
+ AU.addRequired<ValueNumbering>();
}
};
+
+ RegisterOpt<GCSE> X("gcse", "Global Common Subexpression Elimination");
}
// createGCSEPass - The public interface to this file...
// GCSE::runOnFunction - This is the main transformation entry point for a
// function.
//
-bool GCSE::runOnFunction(Function *F) {
+bool GCSE::runOnFunction(Function &F) {
bool Changed = false;
+ // Get pointers to the analysis results that we will be using...
DomSetInfo = &getAnalysis<DominatorSet>();
+#if 0
ImmDominator = &getAnalysis<ImmediateDominators>();
+#endif
+ VN = &getAnalysis<ValueNumbering>();
// Step #1: Add all instructions in the function to the worklist for
// processing. All of the instructions are considered to be our
// program. If so, eliminate them!
//
while (!WorkList.empty()) {
- Instruction *I = *WorkList.begin(); // Get an instruction from the worklist
+ 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.
+ // If this instruction computes a value, try to fold together common
+ // instructions that compute it.
//
- Changed |= visit(I);
+ if (I.getType() != Type::VoidTy) {
+ std::vector<Value*> EqualValues;
+ VN->getEqualNumberNodes(&I, EqualValues);
+
+ if (!EqualValues.empty())
+ Changed |= EliminateRedundancies(&I, EqualValues);
+ }
}
-
+
// When the worklist is empty, return whether or not we changed anything...
return Changed;
}
+bool GCSE::EliminateRedundancies(Instruction *I,
+ std::vector<Value*> &EqualValues) {
+ // If the EqualValues set contains any non-instruction values, then we know
+ // that all of the instructions can be replaced with the non-instruction value
+ // because it is guaranteed to dominate all of the instructions in the
+ // function. We only have to do hard work if all we have are instructions.
+ //
+ for (unsigned i = 0, e = EqualValues.size(); i != e; ++i)
+ if (!isa<Instruction>(EqualValues[i])) {
+ // Found a non-instruction. Replace all instructions with the
+ // non-instruction.
+ //
+ Value *Replacement = EqualValues[i];
+
+ // Make sure we get I as well...
+ EqualValues[i] = I;
+
+ // Replace all instructions with the Replacement value.
+ for (i = 0; i != e; ++i)
+ if (Instruction *I = dyn_cast<Instruction>(EqualValues[i])) {
+ // Change all users of I to use Replacement.
+ I->replaceAllUsesWith(Replacement);
+
+ if (isa<LoadInst>(I))
+ ++NumLoadRemoved; // Keep track of loads eliminated
+ ++NumInstRemoved; // Keep track of number of instructions eliminated
+ ++NumNonInsts; // Keep track of number of insts repl with values
+
+ // Erase the instruction from the program.
+ I->getParent()->getInstList().erase(I);
+ }
+
+ return true;
+ }
+
+ // Remove duplicate entries from EqualValues...
+ std::sort(EqualValues.begin(), EqualValues.end());
+ EqualValues.erase(std::unique(EqualValues.begin(), EqualValues.end()),
+ EqualValues.end());
+
+ // From this point on, EqualValues is logically a vector of instructions.
+ //
+ bool Changed = false;
+ EqualValues.push_back(I); // Make sure I is included...
+ while (EqualValues.size() > 1) {
+ // FIXME, this could be done better than simple iteration!
+ Instruction *Test = cast<Instruction>(EqualValues.back());
+ EqualValues.pop_back();
+
+ for (unsigned i = 0, e = EqualValues.size(); i != e; ++i)
+ if (Instruction *Ret = EliminateCSE(Test,
+ cast<Instruction>(EqualValues[i]))) {
+ if (Ret == Test) // Eliminated EqualValues[i]
+ EqualValues[i] = Test; // Make sure that we reprocess I at some point
+ Changed = true;
+ break;
+ }
+ }
+ 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;
+ Instruction &Second = *SI;
//cerr << "DEL " << (void*)Second << Second;
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();
+ 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);
+ Second.replaceAllUsesWith(First);
// Erase the second instruction from the program
- delete Second->getParent()->getInstList().remove(SI);
+ Second.getParent()->getInstList().erase(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.
+// EliminateCSE - 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. The instruction that is preserved
+// is returned from the function if the other is eliminated, otherwise null is
+// returned.
//
-void GCSE::CommonSubExpressionFound(Instruction *I, Instruction *Other) {
- // I has already been removed from the worklist, Other needs to be.
- assert(I != Other && WorkList.count(I) == 0 && "I shouldn't be on worklist!");
+Instruction *GCSE::EliminateCSE(Instruction *I, Instruction *Other) {
+ assert(I != Other);
+ WorkList.erase(I);
WorkList.erase(Other); // Other may not actually be on the worklist anymore...
- ++NumInstRemoved; // Keep track of number of instructions eliminated
-
// Handle the easy case, where both instructions are in the same basic block
BasicBlock *BB1 = I->getParent(), *BB2 = Other->getParent();
+ Instruction *Ret = 0;
+
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) {
+ 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 *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!");
+ BI = Second;
// Destroy Second, using First instead.
- ReplaceInstWithInst(First, BI);
+ ReplaceInstWithInst(First, BI);
+ Ret = First;
// 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);
+ ReplaceInstWithInst(I, Other);
+ Ret = I;
} 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);
+ ReplaceInstWithInst(Other, I);
+ Ret = Other;
} else {
+ // This code is disabled because it has several problems:
+ // One, the actual assumption is wrong, as shown by this code:
+ // int "test"(int %X, int %Y) {
+ // %Z = add int %X, %Y
+ // ret int %Z
+ // Unreachable:
+ // %Q = add int %X, %Y
+ // ret int %Q
+ // }
+ //
+ // Here there are no shared dominators. Additionally, this had the habit of
+ // moving computations where they were not always computed. For example, in
+ // a cast like this:
+ // if (c) {
+ // if (d) ...
+ // else ... X+Y ...
+ // } else {
+ // ... X+Y ...
+ // }
+ //
+ // In thiscase, the expression would be hoisted to outside the 'if' stmt,
+ // causing the expression to be evaluated, even for the if (d) path, which
+ // could cause problems, if, for example, it caused a divide by zero. In
+ // general the problem this case is trying to solve is better addressed with
+ // PRE than GCSE.
+ //
+ return 0;
+
+#if 0
// 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_
// Rip 'I' out of BB1, and move it to the end of SharedDom.
BB1->getInstList().remove(I);
- SharedDom->getInstList().insert(SharedDom->end()-1, I);
+ SharedDom->getInstList().insert(--SharedDom->end(), 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);
+ ReplaceInstWithInst(I, Other);
+#endif
}
-}
-
-//===----------------------------------------------------------------------===//
-//
-// 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;
-}
+ if (isa<LoadInst>(Ret))
+ ++NumLoadRemoved; // Keep track of loads eliminated
+ ++NumInstRemoved; // Keep track of number of instructions eliminated
-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;
-}
+ // Add all users of Ret to the worklist...
+ for (Value::use_iterator I = Ret->use_begin(), E = Ret->use_end(); I != E;++I)
+ if (Instruction *Inst = dyn_cast<Instruction>(*I))
+ WorkList.insert(Inst);
-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;
+ return Ret;
}
projects / oota-llvm.git / blobdiff