-//===-- 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
//
//===----------------------------------------------------------------------===//
+#define DEBUG_TYPE "gcse"
#include "llvm/Transforms/Scalar.h"
-#include "llvm/BasicBlock.h"
-#include "llvm/Constant.h"
#include "llvm/Instructions.h"
+#include "llvm/Function.h"
#include "llvm/Type.h"
+#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/ValueNumbering.h"
-#include "llvm/Transforms/Utils/Local.h"
-#include "Support/DepthFirstIterator.h"
-#include "Support/Statistic.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Support/Compiler.h"
#include <algorithm>
using namespace llvm;
+STATISTIC(NumInstRemoved, "Number of instructions removed");
+STATISTIC(NumLoadRemoved, "Number of loads removed");
+STATISTIC(NumCallRemoved, "Number of calls removed");
+STATISTIC(NumNonInsts , "Number of instructions removed due "
+ "to non-instruction values");
+STATISTIC(NumArgsRepl , "Number of function arguments replaced "
+ "with constant values");
namespace {
- 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");
+ struct VISIBILITY_HIDDEN GCSE : public FunctionPass {
+ static char ID; // Pass identification, replacement for typeid
+ GCSE() : FunctionPass((intptr_t)&ID) {}
- struct GCSE : public FunctionPass {
virtual bool runOnFunction(Function &F);
private:
// This transformation requires dominator and immediate dominator info
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
- AU.addRequired<DominatorSet>();
AU.addRequired<DominatorTree>();
AU.addRequired<ValueNumbering>();
}
};
- RegisterOpt<GCSE> X("gcse", "Global Common Subexpression Elimination");
+ char GCSE::ID = 0;
+ RegisterPass<GCSE> X("gcse", "Global Common Subexpression Elimination");
}
// createGCSEPass - The public interface to this file...
bool Changed = false;
// Get pointers to the analysis results that we will be using...
- DominatorSet &DS = getAnalysis<DominatorSet>();
- ValueNumbering &VN = getAnalysis<ValueNumbering>();
DominatorTree &DT = getAnalysis<DominatorTree>();
+ ValueNumbering &VN = getAnalysis<ValueNumbering>();
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::arg_iterator AI = F.arg_begin(), E = F.arg_end(); 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()),
+ for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
E = df_end(DT.getRootNode()); DI != E; ++DI) {
BasicBlock *BB = DI->getBlock();
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) {
+ if (Constant *C = ConstantFoldInstruction(Inst)) {
+ ReplaceInstructionWith(Inst, C);
+ } else if (Inst->getType() != Type::VoidTy) {
+ // If this instruction computes a value, try to fold together common
+ // instructions that compute it.
+ //
VN.getEqualNumberNodes(Inst, EqualValues);
// If this instruction computes a value that is already computed
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.
if (OtherI->getParent() == BB)
Dominates = BlockInsts.count(OtherI);
else
- Dominates = DS.dominates(OtherI->getParent(), BB);
+ Dominates = DT.dominates(OtherI->getParent(), BB);
if (Dominates) {
// Okay, we found an instruction with the same value as this one
++NumCallRemoved; // Keep track of calls eliminated
++NumInstRemoved; // Keep track of number of insts eliminated
- // If we are not replacing the instruction with a constant, we cannot do
- // anything special.
- if (!isa<Constant>(V)) {
- I->replaceAllUsesWith(V);
-
- // Erase the instruction from the program.
- I->getParent()->getInstList().erase(I);
- return;
- }
+ // Update value numbering
+ getAnalysis<ValueNumbering>().deleteValue(I);
- Constant *C = cast<Constant>(V);
- std::vector<User*> Users(I->use_begin(), I->use_end());
+ I->replaceAllUsesWith(V);
- // Perform the replacement.
- I->replaceAllUsesWith(C);
+ 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());
+ }
// Erase the instruction from the program.
I->getParent()->getInstList().erase(I);
-
- // 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);
- }
- }
- }
}
projects / oota-llvm.git / blobdiff