lib/Transforms/Scalar/ConstantProp.cpp - platform/external/llvm - Git at Google

 //===- ConstantProp.cpp - Code to perform Constant Propogation ------------===//
 //
 // This file implements constant propogation 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.
 //
 // 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.
 //
 //===----------------------------------------------------------------------===//

 #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
 	}
       }
     }
   }
   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);

       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;
 }

 // 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;
     }
   }
   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);
   }
 #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;
 }
	//===- ConstantProp.cpp - Code to perform Constant Propogation ------------===//
	//
	// This file implements constant propogation 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.
	//
	// 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.
	//
	//===----------------------------------------------------------------------===//

	#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
	}
	}
	}
	}
	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);

	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;
	}

	// 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;
	}
	}
	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);
	}
	#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;
	}