-//===-- GCSE.cpp - SSA based Global Common Subexpr Elimination ------------===//
+//===-- GCSE.cpp - SSA-based Global Common Subexpression Elimination ------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
//
// 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.
+// 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/BasicBlock.h"
+#include "llvm/Constant.h"
+#include "llvm/Instructions.h"
+#include "llvm/Type.h"
#include "llvm/Analysis/Dominators.h"
-#include "llvm/Analysis/AliasAnalysis.h"
-#include "llvm/Support/InstVisitor.h"
-#include "llvm/Support/InstIterator.h"
-#include "llvm/Support/CFG.h"
-#include "Support/StatisticReporter.h"
+#include "llvm/Analysis/ValueNumbering.h"
+#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/Statistic.h"
#include <algorithm>
-using std::set;
-using std::map;
-
-
-static Statistic<> NumInstRemoved("gcse\t\t- Number of instructions removed");
-static Statistic<> NumLoadRemoved("gcse\t\t- Number of loads removed");
+using namespace llvm;
namespace {
- class GCSE : public FunctionPass, public InstVisitor<GCSE, bool> {
- set<Instruction*> WorkList;
- DominatorSet *DomSetInfo;
- ImmediateDominators *ImmDominator;
- AliasAnalysis *AA;
-
- public:
+ Statistic<> NumInstRemoved("gcse", "Number of instructions removed");
+ Statistic<> NumLoadRemoved("gcse", "Number of loads removed");
+ Statistic<> NumCallRemoved("gcse", "Number of calls removed");
+ Statistic<> NumNonInsts ("gcse", "Number of instructions removed due "
+ "to non-instruction values");
+ Statistic<> NumArgsRepl ("gcse", "Number of function arguments replaced "
+ "with constant values");
+
+ struct GCSE : public FunctionPass {
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 visitBinaryOperator(Instruction &I);
- bool visitGetElementPtrInst(GetElementPtrInst &I);
- bool visitCastInst(CastInst &I);
- bool visitShiftInst(ShiftInst &I) {
- return visitBinaryOperator((Instruction&)I);
- }
- bool visitLoadInst(LoadInst &LI);
- bool visitInstruction(Instruction &) { return false; }
-
private:
- void ReplaceInstWithInst(Instruction *First, BasicBlock::iterator SI);
- bool CommonSubExpressionFound(Instruction *I, Instruction *Other);
-
- // TryToRemoveALoad - Try to remove one of L1 or L2. The problem with
- // removing loads is that intervening stores might make otherwise identical
- // load's yield different values. To ensure that this is not the case, we
- // check that there are no intervening stores or calls between the
- // instructions.
- //
- bool TryToRemoveALoad(LoadInst *L1, LoadInst *L2);
-
- // CheckForInvalidatingInst - Return true if BB or any of the predecessors
- // of BB (until DestBB) contain an instruction that might invalidate Ptr.
- //
- bool CheckForInvalidatingInst(BasicBlock *BB, BasicBlock *DestBB,
- Value *Ptr, set<BasicBlock*> &VisitedSet);
+ void ReplaceInstructionWith(Instruction *I, Value *V);
// This transformation requires dominator and immediate dominator info
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- AU.preservesCFG();
+ AU.setPreservesCFG();
AU.addRequired<DominatorSet>();
- AU.addRequired<ImmediateDominators>();
- AU.addRequired<AliasAnalysis>();
+ AU.addRequired<DominatorTree>();
+ AU.addRequired<ValueNumbering>();
}
};
}
// createGCSEPass - The public interface to this file...
-Pass *createGCSEPass() { return new GCSE(); }
-
+FunctionPass *llvm::createGCSEPass() { return new GCSE(); }
// GCSE::runOnFunction - This is the main transformation entry point for a
// function.
bool Changed = false;
// Get pointers to the analysis results that we will be using...
- DomSetInfo = &getAnalysis<DominatorSet>();
- ImmDominator = &getAnalysis<ImmediateDominators>();
- AA = &getAnalysis<AliasAnalysis>();
-
- // 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);
+ DominatorSet &DS = getAnalysis<DominatorSet>();
+ ValueNumbering &VN = getAnalysis<ValueNumbering>();
+ DominatorTree &DT = getAnalysis<DominatorTree>();
+
+ std::vector<Value*> EqualValues;
+
+ // Check for value numbers of arguments. If the value numbering
+ // implementation can prove that an incoming argument is a constant or global
+ // value address, substitute it, making the argument dead.
+ for (Function::aiterator AI = F.abegin(), E = F.aend(); AI != E; ++AI)
+ if (!AI->use_empty()) {
+ VN.getEqualNumberNodes(AI, EqualValues);
+ if (!EqualValues.empty()) {
+ for (unsigned i = 0, e = EqualValues.size(); i != e; ++i)
+ if (isa<Constant>(EqualValues[i])) {
+ AI->replaceAllUsesWith(EqualValues[i]);
+ ++NumArgsRepl;
+ Changed = true;
+ break;
+ }
+ EqualValues.clear();
+ }
+ }
+
+ // Traverse the CFG of the function in dominator order, so that we see each
+ // instruction after we see its operands.
+ for (df_iterator<DominatorTree::Node*> DI = df_begin(DT.getRootNode()),
+ E = df_end(DT.getRootNode()); DI != E; ++DI) {
+ BasicBlock *BB = DI->getBlock();
+
+ // Remember which instructions we've seen in this basic block as we scan.
+ std::set<Instruction*> BlockInsts;
+
+ for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
+ Instruction *Inst = I++;
+
+ // If this instruction computes a value, try to fold together common
+ // instructions that compute it.
+ //
+ if (Inst->getType() != Type::VoidTy) {
+ VN.getEqualNumberNodes(Inst, EqualValues);
+
+ // If this instruction computes a value that is already computed
+ // elsewhere, try to recycle the old value.
+ if (!EqualValues.empty()) {
+ if (Inst == &*BB->begin())
+ I = BB->end();
+ else {
+ I = Inst; --I;
+ }
+
+ // First check to see if we were able to value number this instruction
+ // to a non-instruction value. If so, prefer that value over other
+ // instructions which may compute the same thing.
+ for (unsigned i = 0, e = EqualValues.size(); i != e; ++i)
+ if (!isa<Instruction>(EqualValues[i])) {
+ ++NumNonInsts; // Keep track of # of insts repl with values
+
+ // Change all users of Inst to use the replacement and remove it
+ // from the program.
+ ReplaceInstructionWith(Inst, EqualValues[i]);
+ Inst = 0;
+ EqualValues.clear(); // don't enter the next loop
+ break;
+ }
+
+ // If there were no non-instruction values that this instruction
+ // produces, find a dominating instruction that produces the same
+ // value. If we find one, use it's value instead of ours.
+ for (unsigned i = 0, e = EqualValues.size(); i != e; ++i) {
+ Instruction *OtherI = cast<Instruction>(EqualValues[i]);
+ bool Dominates = false;
+ if (OtherI->getParent() == BB)
+ Dominates = BlockInsts.count(OtherI);
+ else
+ Dominates = DS.dominates(OtherI->getParent(), BB);
+
+ if (Dominates) {
+ // Okay, we found an instruction with the same value as this one
+ // and that dominates this one. Replace this instruction with the
+ // specified one.
+ ReplaceInstructionWith(Inst, OtherI);
+ Inst = 0;
+ break;
+ }
+ }
+
+ EqualValues.clear();
+
+ if (Inst) {
+ I = Inst; ++I; // Deleted no instructions
+ } else if (I == BB->end()) { // Deleted first instruction
+ I = BB->begin();
+ } else { // Deleted inst in middle of block.
+ ++I;
+ }
+ }
+
+ if (Inst)
+ BlockInsts.insert(Inst);
+ }
+ }
}
// When the worklist is empty, return whether or not we changed anything...
}
-// 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;
-
- //cerr << "DEL " << (void*)Second << Second;
-
- // Add the first instruction back to the worklist
- WorkList.insert(First);
+void GCSE::ReplaceInstructionWith(Instruction *I, Value *V) {
+ if (isa<LoadInst>(I))
+ ++NumLoadRemoved; // Keep track of loads eliminated
+ if (isa<CallInst>(I))
+ ++NumCallRemoved; // Keep track of calls eliminated
+ ++NumInstRemoved; // Keep track of number of insts eliminated
- // 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);
+ // Update value numbering
+ getAnalysis<ValueNumbering>().deleteValue(I);
- // Erase the second instruction from the program
- Second.getParent()->getInstList().erase(SI);
-}
+ // If we are not replacing the instruction with a constant, we cannot do
+ // anything special.
+ if (!isa<Constant>(V)) {
+ I->replaceAllUsesWith(V);
-// 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.
-//
-bool GCSE::CommonSubExpressionFound(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();
- 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!");
+ if (InvokeInst *II = dyn_cast<InvokeInst>(I)) {
+ // Removing an invoke instruction requires adding a branch to the normal
+ // destination and removing PHI node entries in the exception destination.
+ new BranchInst(II->getNormalDest(), II);
+ II->getUnwindDest()->removePredecessor(II->getParent());
}
-
- // Keep track of which instructions occurred first & second
- Instruction *First = BI;
- Instruction *Second = I != First ? I : Other; // Get iterator to second inst
- BI = Second;
-
- // 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?
- ReplaceInstWithInst(I, Other);
- } else if (DomSetInfo->dominates(BB2, BB1)) { // Other dom I?
- ReplaceInstWithInst(Other, I);
- } 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 false;
-
-#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_
- // 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(), I);
-
- // Eliminate 'Other' now.
- ReplaceInstWithInst(I, Other);
-#endif
+
+ // Erase the instruction from the program.
+ I->getParent()->getInstList().erase(I);
+ return;
}
- return true;
-}
-
-//===----------------------------------------------------------------------===//
-//
-// 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::visitCastInst(CastInst &CI) {
- Instruction &I = (Instruction&)CI;
- 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 cast is not I, but has the 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.
- if (CommonSubExpressionFound(&I, Other))
- return true; // One instruction eliminated!
- }
-
- return false;
-}
-// isIdenticalBinaryInst - Return true if the two binary instructions are
-// identical.
-//
-static inline bool isIdenticalBinaryInst(const Instruction &I1,
- const Instruction *I2) {
- // Is it embeded in the same function? (This could be false if LHS
- // is a constant or global!)
- if (I1.getOpcode() != I2->getOpcode() ||
- I1.getParent()->getParent() != I2->getParent()->getParent())
- return false;
-
- // They are identical if both operands are the same!
- if (I1.getOperand(0) == I2->getOperand(0) &&
- I1.getOperand(1) == I2->getOperand(1))
- return true;
-
- // If the instruction is commutative and associative, the instruction can
- // match if the operands are swapped!
- //
- if ((I1.getOperand(0) == I2->getOperand(1) &&
- I1.getOperand(1) == I2->getOperand(0)) &&
- (I1.getOpcode() == Instruction::Add ||
- I1.getOpcode() == Instruction::Mul ||
- I1.getOpcode() == Instruction::And ||
- I1.getOpcode() == Instruction::Or ||
- I1.getOpcode() == Instruction::Xor))
- return true;
-
- return false;
-}
+ Constant *C = cast<Constant>(V);
+ std::vector<User*> Users(I->use_begin(), I->use_end());
-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 && isIdenticalBinaryInst(I, Other)) {
- // These instructions are identical. Handle the situation.
- if (CommonSubExpressionFound(&I, Other))
- return true; // One instruction eliminated!
- }
-
- return false;
-}
+ // Perform the replacement.
+ I->replaceAllUsesWith(C);
-// IdenticalComplexInst - Return true if the two instructions are the same, by
-// using a brute force comparison.
-//
-static bool IdenticalComplexInst(const Instruction *I1, const Instruction *I2) {
- assert(I1->getOpcode() == I2->getOpcode());
- // Equal if they are in the same function...
- return I1->getParent()->getParent() == I2->getParent()->getParent() &&
- // And return the same type...
- I1->getType() == I2->getType() &&
- // And have the same number of operands...
- I1->getNumOperands() == I2->getNumOperands() &&
- // And all of the operands are equal.
- std::equal(I1->op_begin(), I1->op_end(), I2->op_begin());
-}
+ if (InvokeInst *II = dyn_cast<InvokeInst>(I)) {
+ // Removing an invoke instruction requires adding a branch to the normal
+ // destination and removing PHI node entries in the exception destination.
+ new BranchInst(II->getNormalDest(), II);
+ II->getUnwindDest()->removePredecessor(II->getParent());
+ }
-bool GCSE::visitGetElementPtrInst(GetElementPtrInst &I) {
- Value *Op = I.getOperand(0);
- Function *F = I.getParent()->getParent();
+ // Erase the instruction from the program.
+ I->getParent()->getInstList().erase(I);
- 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 getelementptr is not I, but same operand...
- if (Other != &I && IdenticalComplexInst(&I, Other)) {
- // These instructions are identical. Handle the situation.
- if (CommonSubExpressionFound(&I, Other))
- return true; // One instruction eliminated!
+ // Check each user to see if we can constant fold it.
+ while (!Users.empty()) {
+ Instruction *U = cast<Instruction>(Users.back());
+ Users.pop_back();
+
+ if (Constant *C = ConstantFoldInstruction(U)) {
+ ReplaceInstructionWith(U, C);
+
+ // If the instruction used I more than once, it could be on the user list
+ // multiple times. Make sure we don't reprocess it.
+ std::vector<User*>::iterator It = std::find(Users.begin(), Users.end(),U);
+ while (It != Users.end()) {
+ Users.erase(It);
+ It = std::find(Users.begin(), Users.end(), U);
}
-
- return false;
-}
-
-bool GCSE::visitLoadInst(LoadInst &LI) {
- Value *Op = LI.getOperand(0);
- Function *F = LI.getParent()->getParent();
-
- for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
- UI != UE; ++UI)
- if (LoadInst *Other = dyn_cast<LoadInst>(*UI))
- // Check to see if this new load is not LI, but has the same operands...
- if (Other != &LI && IdenticalComplexInst(&LI, Other) &&
- TryToRemoveALoad(&LI, Other))
- return true; // An instruction was eliminated!
-
- return false;
-}
-
-// TryToRemoveALoad - Try to remove one of L1 or L2. The problem with removing
-// loads is that intervening stores might make otherwise identical load's yield
-// different values. To ensure that this is not the case, we check that there
-// are no intervening stores or calls between the instructions.
-//
-bool GCSE::TryToRemoveALoad(LoadInst *L1, LoadInst *L2) {
- // Figure out which load dominates the other one. If neither dominates the
- // other we cannot eliminate one...
- //
- if (DomSetInfo->dominates(L2, L1))
- std::swap(L1, L2); // Make L1 dominate L2
- else if (!DomSetInfo->dominates(L1, L2))
- return false; // Neither instruction dominates the other one...
-
- BasicBlock *BB1 = L1->getParent(), *BB2 = L2->getParent();
-
- assert(!L1->hasIndices());
- Value *LoadAddress = L1->getOperand(0);
-
- // L1 now dominates L2. Check to see if the intervening instructions between
- // the two loads include a store or call...
- //
- if (BB1 == BB2) { // In same basic block?
- // In this degenerate case, no checking of global basic blocks has to occur
- // just check the instructions BETWEEN L1 & L2...
- //
- if (AA->canInstructionRangeModify(*L1, *L2, LoadAddress))
- return false; // Cannot eliminate load
-
- ++NumLoadRemoved;
- if (CommonSubExpressionFound(L1, L2))
- return true;
- } else {
- // Make sure that there are no store instructions between L1 and the end of
- // it's basic block...
- //
- if (AA->canInstructionRangeModify(*L1, *BB1->getTerminator(), LoadAddress))
- return false; // Cannot eliminate load
-
- // Make sure that there are no store instructions between the start of BB2
- // and the second load instruction...
- //
- if (AA->canInstructionRangeModify(BB2->front(), *L2, LoadAddress))
- return false; // Cannot eliminate load
-
- // Do a depth first traversal of the inverse CFG starting at L2's block,
- // looking for L1's block. The inverse CFG is made up of the predecessor
- // nodes of a block... so all of the edges in the graph are "backward".
- //
- set<BasicBlock*> VisitedSet;
- for (pred_iterator PI = pred_begin(BB2), PE = pred_end(BB2); PI != PE; ++PI)
- if (CheckForInvalidatingInst(*PI, BB1, LoadAddress, VisitedSet))
- return false;
-
- ++NumLoadRemoved;
- return CommonSubExpressionFound(L1, L2);
+ }
}
- return false;
-}
-
-// CheckForInvalidatingInst - Return true if BB or any of the predecessors of BB
-// (until DestBB) contain an instruction that might invalidate Ptr.
-//
-bool GCSE::CheckForInvalidatingInst(BasicBlock *BB, BasicBlock *DestBB,
- Value *Ptr, set<BasicBlock*> &VisitedSet) {
- // Found the termination point!
- if (BB == DestBB || VisitedSet.count(BB)) return false;
-
- // Avoid infinite recursion!
- VisitedSet.insert(BB);
-
- // Can this basic block modify Ptr?
- if (AA->canBasicBlockModify(*BB, Ptr))
- return true;
-
- // Check all of our predecessor blocks...
- for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
- if (CheckForInvalidatingInst(*PI, DestBB, Ptr, VisitedSet))
- return true;
-
- // None of our predecessor blocks contain a store, and we don't either!
- return false;
}
projects / oota-llvm.git / blobdiff