-//===-- 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
#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 <algorithm>
using namespace llvm;
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);
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 (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.
++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);
+ // Update value numbering
+ getAnalysis<ValueNumbering>().deleteValue(I);
- // Erase the instruction from the program.
- I->getParent()->getInstList().erase(I);
- return;
- }
-
- 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);
- }
- }
- }
}