From 4d1e46e7b06534cde262d32fad038135f406b6b7 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Tue, 7 May 2002 18:07:59 +0000 Subject: [PATCH] Add code pulled out of TransformInternals.cpp, ConstProp.cpp, and DCE.cpp git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2513 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Utils/BasicBlockUtils.cpp | 79 ++++++++++++++++ lib/Transforms/Utils/Local.cpp | 111 +++++++++++++++++++++++ lib/Transforms/Utils/Makefile | 6 ++ 3 files changed, 196 insertions(+) create mode 100644 lib/Transforms/Utils/BasicBlockUtils.cpp create mode 100644 lib/Transforms/Utils/Local.cpp create mode 100644 lib/Transforms/Utils/Makefile diff --git a/lib/Transforms/Utils/BasicBlockUtils.cpp b/lib/Transforms/Utils/BasicBlockUtils.cpp new file mode 100644 index 00000000000..89078a12e95 --- /dev/null +++ b/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -0,0 +1,79 @@ +//===-- BasicBlockUtils.cpp - BasicBlock Utilities -------------------------==// +// +// This family of functions perform manipulations on basic blocks, and +// instructions contained within basic blocks. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Function.h" +#include "llvm/Instruction.h" +#include + +// ReplaceInstWithValue - Replace all uses of an instruction (specified by BI) +// with a value, then remove and delete the original instruction. +// +void ReplaceInstWithValue(BasicBlock::InstListType &BIL, + BasicBlock::iterator &BI, Value *V) { + Instruction *I = *BI; + // Replaces all of the uses of the instruction with uses of the value + I->replaceAllUsesWith(V); + + // Remove the unneccesary instruction now... + BIL.remove(BI); + + // Make sure to propogate a name if there is one already... + if (I->hasName() && !V->hasName()) + V->setName(I->getName(), BIL.getParent()->getSymbolTable()); + + // Remove the dead instruction now... + delete I; +} + + +// ReplaceInstWithInst - Replace the instruction specified by BI with the +// instruction specified by I. The original instruction is deleted and BI is +// updated to point to the new instruction. +// +void ReplaceInstWithInst(BasicBlock::InstListType &BIL, + BasicBlock::iterator &BI, Instruction *I) { + assert(I->getParent() == 0 && + "ReplaceInstWithInst: Instruction already inserted into basic block!"); + + // Insert the new instruction into the basic block... + BI = BIL.insert(BI, I)+1; // Increment BI to point to instruction to delete + + // Replace all uses of the old instruction, and delete it. + ReplaceInstWithValue(BIL, BI, I); + + // Move BI back to point to the newly inserted instruction + --BI; +} + +// ReplaceInstWithInst - Replace the instruction specified by From with the +// instruction specified by To. Note that this is slower than providing an +// iterator directly, because the basic block containing From must be searched +// for the instruction. +// +void ReplaceInstWithInst(Instruction *From, Instruction *To) { + BasicBlock *BB = From->getParent(); + BasicBlock::InstListType &BIL = BB->getInstList(); + BasicBlock::iterator BI = find(BIL.begin(), BIL.end(), From); + assert(BI != BIL.end() && "Inst not in it's parents BB!"); + ReplaceInstWithInst(BIL, BI, To); +} + +// InsertInstBeforeInst - Insert 'NewInst' into the basic block that 'Existing' +// is already in, and put it right before 'Existing'. This instruction should +// only be used when there is no iterator to Existing already around. The +// returned iterator points to the new instruction. +// +BasicBlock::iterator InsertInstBeforeInst(Instruction *NewInst, + Instruction *Existing) { + BasicBlock *BB = Existing->getParent(); + BasicBlock::InstListType &BIL = BB->getInstList(); + BasicBlock::iterator BI = find(BIL.begin(), BIL.end(), Existing); + assert(BI != BIL.end() && "Inst not in it's parents BB!"); + return BIL.insert(BI, NewInst); +} + diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp new file mode 100644 index 00000000000..36622642bfa --- /dev/null +++ b/lib/Transforms/Utils/Local.cpp @@ -0,0 +1,111 @@ +//===-- Local.cpp - Functions to perform local transformations ------------===// +// +// This family of functions perform various local transformations to the +// program. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Utils/Local.h" +#include "llvm/iTerminators.h" +#include "llvm/ConstantHandling.h" + +//===----------------------------------------------------------------------===// +// Local constant propogation... +// + +// ConstantFoldInstruction - If an instruction references constants, try to fold +// them together... +// +bool doConstantPropogation(BasicBlock *BB, BasicBlock::iterator &II) { + Instruction *Inst = *II; + if (Constant *C = ConstantFoldInstruction(Inst)) { + // Replaces all of the uses of a variable with uses of the constant. + Inst->replaceAllUsesWith(C); + + // Remove the instruction from the basic block... + delete BB->getInstList().remove(II); + return true; + } + + return false; +} + +// ConstantFoldTerminator - If a terminator instruction is predicated on a +// constant value, convert it into an unconditional branch to the constant +// destination. +// +bool ConstantFoldTerminator(BasicBlock *BB, BasicBlock::iterator &II, + TerminatorInst *T) { + // Branch - See if we are conditional jumping on constant + if (BranchInst *BI = dyn_cast(T)) { + if (BI->isUnconditional()) return false; // Can't optimize uncond branch + BasicBlock *Dest1 = cast(BI->getOperand(0)); + BasicBlock *Dest2 = cast(BI->getOperand(1)); + + if (ConstantBool *Cond = dyn_cast(BI->getCondition())) { + // Are we branching on constant? + // YES. Change to unconditional branch... + BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2; + BasicBlock *OldDest = Cond->getValue() ? Dest2 : Dest1; + + //cerr << "Function: " << T->getParent()->getParent() + // << "\nRemoving branch from " << T->getParent() + // << "\n\nTo: " << OldDest << endl; + + // Let the basic block know that we are letting go of it. Based on this, + // it will adjust it's PHI nodes. + assert(BI->getParent() && "Terminator not inserted in block!"); + OldDest->removePredecessor(BI->getParent()); + + // Set the unconditional destination, and change the insn to be an + // unconditional branch. + BI->setUnconditionalDest(Destination); + II = BB->end()-1; // Update instruction iterator! + return true; + } +#if 0 + // FIXME: TODO: This doesn't work if the destination has PHI nodes with + // different incoming values on each branch! + // + else if (Dest2 == Dest1) { // Conditional branch to same location? + // This branch matches something like this: + // br bool %cond, label %Dest, label %Dest + // and changes it into: br label %Dest + + // Let the basic block know that we are letting go of one copy of it. + assert(BI->getParent() && "Terminator not inserted in block!"); + Dest1->removePredecessor(BI->getParent()); + + // Change a conditional branch to unconditional. + BI->setUnconditionalDest(Dest1); + return true; + } +#endif + } + return false; +} + + + +//===----------------------------------------------------------------------===// +// Local dead code elimination... +// + +bool isInstructionTriviallyDead(Instruction *I) { + return I->use_empty() && !I->hasSideEffects() && !isa(I); +} + +// dceInstruction - Inspect the instruction at *BBI and figure out if it's +// [trivially] dead. If so, remove the instruction and update the iterator +// to point to the instruction that immediately succeeded the original +// instruction. +// +bool dceInstruction(BasicBlock::InstListType &BBIL, + BasicBlock::iterator &BBI) { + // Look for un"used" definitions... + if (isInstructionTriviallyDead(*BBI)) { + delete BBIL.remove(BBI); // Bye bye + return true; + } + return false; +} diff --git a/lib/Transforms/Utils/Makefile b/lib/Transforms/Utils/Makefile new file mode 100644 index 00000000000..f451df2d5c2 --- /dev/null +++ b/lib/Transforms/Utils/Makefile @@ -0,0 +1,6 @@ +LEVEL = ../../.. + +LIBRARYNAME = transformutils + +include $(LEVEL)/Makefile.common + -- 2.34.1