-//===- ConstantProp.cpp - Code to perform Constant Propogation ------------===//
+//===- ConstantProp.cpp - Code to perform Simple Constant Propagation -----===//
//
-// This file implements constant propogation and merging:
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements constant propagation and merging:
//
// Specifically, this:
-// * Folds multiple identical constants in the constant pool together
-// Note that if one is named and the other is not, that the result gets the
-// original name.
-// * Converts instructions like "add int %1, %2" into a direct def of %3 in
-// the constant pool
-// * Converts conditional branches on a constant boolean value into direct
-// branches.
-// * Converts phi nodes with one incoming def to the incoming def directly
-// . Converts switch statements with one entry into a test & conditional
-// branch
-// . Converts switches on constant values into an unconditional branch.
+// * Converts instructions like "add int 1, 2" into 3
//
// Notice that:
// * This pass has a habit of making definitions be dead. It is a good idea
-// to to run a DCE pass sometime after running this pass.
+// to to run a DIE pass sometime after running this pass.
//
//===----------------------------------------------------------------------===//
-#include "llvm/Module.h"
-#include "llvm/Method.h"
-#include "llvm/BasicBlock.h"
-#include "llvm/iTerminators.h"
-#include "llvm/iOther.h"
-#include "llvm/ConstPoolVals.h"
-#include "llvm/ConstantPool.h"
-#include "llvm/Opt/AllOpts.h"
-#include "llvm/Opt/ConstantHandling.h"
-
-// Merge identical constant values in the constant pool.
-//
-// TODO: We can do better than this simplistic N^2 algorithm...
-//
-static bool MergeConstantPoolReferences(ConstantPool &CP) {
- bool Modified = false;
- for (ConstantPool::plane_iterator PI = CP.begin(); PI != CP.end(); ++PI) {
- for (ConstantPool::PlaneType::iterator I = (*PI)->begin();
- I != (*PI)->end(); I++) {
- ConstPoolVal *C = *I;
-
- ConstantPool::PlaneType::iterator J = I;
- for (++J; J != (*PI)->end(); J++) {
- if (C->equals(*J)) {
- Modified = true;
- // Okay we know that *I == *J. So now we need to make all uses of *I
- // point to *J.
- //
- C->replaceAllUsesWith(*J);
-
- (*PI)->remove(I); // Remove C from constant pool...
-
- if (C->hasName() && !(*J)->hasName()) // The merged constant inherits
- (*J)->setName(C->getName()); // the old name...
-
- delete C; // Delete the constant itself.
- break; // Break out of inner for loop
- }
- }
+#define DEBUG_TYPE "constprop"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Analysis/ConstantFolding.h"
+#include "llvm/Constant.h"
+#include "llvm/Instruction.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/Compiler.h"
+#include "llvm/Support/InstIterator.h"
+#include "llvm/ADT/Statistic.h"
+#include <set>
+using namespace llvm;
+
+STATISTIC(NumInstKilled, "Number of instructions killed");
+
+namespace {
+ struct VISIBILITY_HIDDEN ConstantPropagation : public FunctionPass {
+ static char ID; // Pass identification, replacement for typeid
+ ConstantPropagation() : FunctionPass((intptr_t)&ID) {}
+
+ bool runOnFunction(Function &F);
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesCFG();
}
- }
- return Modified;
-}
-
-inline static bool
-ConstantFoldUnaryInst(Method *M, Method::inst_iterator &DI,
- UnaryOperator *Op, ConstPoolVal *D) {
- ConstPoolVal *ReplaceWith = 0;
-
- switch (Op->getInstType()) {
- case Instruction::Not: ReplaceWith = !*D; break;
- case Instruction::Neg: ReplaceWith = -*D; break;
- }
-
- if (!ReplaceWith) return false; // Nothing new to change...
-
-
- // Add the new value to the constant pool...
- M->getConstantPool().insert(ReplaceWith);
-
- // Replaces all of the uses of a variable with uses of the constant.
- Op->replaceAllUsesWith(ReplaceWith);
-
- // Remove the operator from the list of definitions...
- Op->getParent()->getInstList().remove(DI.getInstructionIterator());
-
- // The new constant inherits the old name of the operator...
- if (Op->hasName()) ReplaceWith->setName(Op->getName());
-
- // Delete the operator now...
- delete Op;
- return true;
-}
-
-inline static bool
-ConstantFoldBinaryInst(Method *M, Method::inst_iterator &DI,
- BinaryOperator *Op,
- ConstPoolVal *D1, ConstPoolVal *D2) {
- ConstPoolVal *ReplaceWith = 0;
-
- switch (Op->getInstType()) {
- case Instruction::Add: ReplaceWith = *D1 + *D2; break;
- case Instruction::Sub: ReplaceWith = *D1 - *D2; break;
-
- case Instruction::SetEQ: ReplaceWith = *D1 == *D2; break;
- case Instruction::SetNE: ReplaceWith = *D1 != *D2; break;
- case Instruction::SetLE: ReplaceWith = *D1 <= *D2; break;
- case Instruction::SetGE: ReplaceWith = *D1 >= *D2; break;
- case Instruction::SetLT: ReplaceWith = *D1 < *D2; break;
- case Instruction::SetGT: ReplaceWith = *D1 > *D2; break;
- }
-
- if (!ReplaceWith) return false; // Nothing new to change...
-
- // Add the new value to the constant pool...
- M->getConstantPool().insert(ReplaceWith);
-
- // Replaces all of the uses of a variable with uses of the constant.
- Op->replaceAllUsesWith(ReplaceWith);
-
- // Remove the operator from the list of definitions...
- Op->getParent()->getInstList().remove(DI.getInstructionIterator());
-
- // The new constant inherits the old name of the operator...
- if (Op->hasName()) ReplaceWith->setName(Op->getName());
-
- // Delete the operator now...
- delete Op;
- return true;
+ };
}
-inline static bool ConstantFoldTerminator(TerminatorInst *T) {
- // Branch - See if we are conditional jumping on constant
- if (T->getInstType() == Instruction::Br) {
- BranchInst *BI = (BranchInst*)T;
- if (!BI->isUnconditional() && // Are we branching on constant?
- BI->getOperand(2)->getValueType() == Value::ConstantVal) {
- // YES. Change to unconditional branch...
- ConstPoolBool *Cond = (ConstPoolBool*)BI->getOperand(2);
- Value *Destination = BI->getOperand(Cond->getValue() ? 0 : 1);
+char ConstantPropagation::ID = 0;
+static RegisterPass<ConstantPropagation>
+X("constprop", "Simple constant propagation");
- BI->setOperand(0, Destination); // Set the unconditional destination
- BI->setOperand(1, 0); // Clear the conditional destination
- BI->setOperand(2, 0); // Clear the condition...
- return true;
- }
- }
- return false;
+FunctionPass *llvm::createConstantPropagationPass() {
+ return new ConstantPropagation();
}
-// ConstantFoldInstruction - If an instruction references constants, try to fold
-// them together...
-//
-inline static bool
-ConstantFoldInstruction(Method *M, Method::inst_iterator &II) {
- Instruction *Inst = *II;
- if (Inst->isBinaryOp()) {
- Value *D1, *D2;
- if (((D1 = Inst->getOperand(0))->getValueType() == Value::ConstantVal) &
- ((D2 = Inst->getOperand(1))->getValueType() == Value::ConstantVal))
- return ConstantFoldBinaryInst(M, II, (BinaryOperator*)Inst,
- (ConstPoolVal*)D1, (ConstPoolVal*)D2);
-
- } else if (Inst->isUnaryOp()) {
- Value *D;
- if ((D = Inst->getOperand(0))->getValueType() == Value::ConstantVal)
- return ConstantFoldUnaryInst(M, II, (UnaryOperator*)Inst,
- (ConstPoolVal*)D);
- } else if (Inst->isTerminator()) {
- return ConstantFoldTerminator((TerminatorInst*)Inst);
- } else if (Inst->getInstType() == Instruction::PHINode) {
- PHINode *PN = (PHINode*)Inst; // If it's a PHI node and only has one operand
- // Then replace it directly with that operand.
- assert(PN->getOperand(0) && "PHI Node must have at least one operand!");
- if (PN->getOperand(1) == 0) { // If the PHI Node has exactly 1 operand
- Value *V = PN->getOperand(0);
- PN->replaceAllUsesWith(V); // Replace all uses of this PHI
- // Unlink from basic block
- PN->getParent()->getInstList().remove(II.getInstructionIterator());
- if (PN->hasName()) V->setName(PN->getName()); // Inherit PHINode name
- delete PN; // Finally, delete the node...
- return true;
- }
+bool ConstantPropagation::runOnFunction(Function &F) {
+ // Initialize the worklist to all of the instructions ready to process...
+ std::set<Instruction*> WorkList;
+ for(inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) {
+ WorkList.insert(&*i);
}
- return false;
-}
-
-// DoConstPropPass - Propogate constants and do constant folding on instructions
-// this returns true if something was changed, false if nothing was changed.
-//
-static bool DoConstPropPass(Method *M) {
- bool SomethingChanged = false;
-
-#if 1
- Method::inst_iterator It = M->inst_begin();
- while (It != M->inst_end())
- if (ConstantFoldInstruction(M, It)) {
- SomethingChanged = true; // If returned true, iter is already incremented
-
- // Incrementing the iterator in an unchecked manner could mess up the
- // internals of 'It'. To make sure everything is happy, tell it we might
- // have broken it.
- It.resyncInstructionIterator();
- } else {
- ++It;
- }
-#else
- Method::BasicBlocksType::iterator BBIt = M->getBasicBlocks().begin();
- for (; BBIt != M->getBasicBlocks().end(); BBIt++) {
- BasicBlock *BB = *BBIt;
-
- BasicBlock::InstListType::iterator DI = BB->getInstList().begin();
- for (; DI != BB->getInstList().end(); DI++)
- SomethingChanged |= ConstantFoldInstruction(M, DI);
+ bool Changed = false;
+
+ while (!WorkList.empty()) {
+ Instruction *I = *WorkList.begin();
+ WorkList.erase(WorkList.begin()); // Get an element from the worklist...
+
+ if (!I->use_empty()) // Don't muck with dead instructions...
+ if (Constant *C = ConstantFoldInstruction(I)) {
+ // Add all of the users of this instruction to the worklist, they might
+ // be constant propagatable now...
+ for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
+ UI != UE; ++UI)
+ WorkList.insert(cast<Instruction>(*UI));
+
+ // Replace all of the uses of a variable with uses of the constant.
+ I->replaceAllUsesWith(C);
+
+ // Remove the dead instruction.
+ WorkList.erase(I);
+ I->getParent()->getInstList().erase(I);
+
+ // We made a change to the function...
+ Changed = true;
+ ++NumInstKilled;
+ }
}
-#endif
- return SomethingChanged;
-}
-
-
-// returns true on failure, false on success...
-//
-bool DoConstantPropogation(Method *M) {
- bool Modified = false;
-
- // Fold constants until we make no progress...
- while (DoConstPropPass(M)) Modified = true;
-
- // Merge identical constants last: this is important because we may have just
- // introduced constants that already exist!
- //
- Modified |= MergeConstantPoolReferences(M->getConstantPool());
-
- return Modified;
+ return Changed;
}