-//===- DemoteRegToStack.cpp - Move a virtual reg. to stack ------*- C++ -*-===//
-//
-// This file provide the function DemoteRegToStack().
-// This function takes a virtual register computed by an
-// Instruction& X and replaces it with a slot in the stack frame,
-// allocated via alloca. It returns the pointer to the AllocaInst inserted.
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Transforms/Utils/DemoteRegToStack.h"
-#include "llvm/Function.h"
-#include "llvm/BasicBlock.h"
-#include "llvm/iMemory.h"
-#include "llvm/iPHINode.h"
-#include "llvm/iTerminators.h"
-#include "llvm/Type.h"
-#include "Support/hash_set"
-#include <stack>
-
-
-//----------------------------------------------------------------------------
-// function DemoteRegToStack()
+//===- DemoteRegToStack.cpp - Move a virtual register to the stack --------===//
//
-//----------------------------------------------------------------------------
-
-typedef hash_set<PHINode*> PhiSet;
-typedef hash_set<PHINode*>::iterator PhiSetIterator;
-
-// Helper function to push a phi *and* all its operands to the worklist!
-// Do not push an instruction if it is already in the result set of Phis to go.
-inline void PushOperandsOnWorkList(std::stack<Instruction*>& workList,
- PhiSet& phisToGo, PHINode* phiN)
-{
- for (User::op_iterator OI=phiN->op_begin(), OE=phiN->op_end();
- OI != OE; ++OI)
- if (Instruction* opI = dyn_cast<Instruction>(OI->get()))
- if (!isa<PHINode>(opI) ||
- phisToGo.find(cast<PHINode>(opI)) == phisToGo.end())
- workList.push(opI);
-}
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
-void FindPhis(Instruction& X, PhiSet& phisToGo)
-{
- std::stack<Instruction*> workList;
- workList.push(&X);
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Analysis/CFG.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Type.h"
+#include "llvm/Transforms/Utils/Local.h"
+using namespace llvm;
+
+/// DemoteRegToStack - This function takes a virtual register computed by an
+/// Instruction and replaces it with a slot in the stack frame, allocated via
+/// alloca. This allows the CFG to be changed around without fear of
+/// invalidating the SSA information for the value. It returns the pointer to
+/// the alloca inserted to create a stack slot for I.
+AllocaInst *llvm::DemoteRegToStack(Instruction &I, bool VolatileLoads,
+ Instruction *AllocaPoint) {
+ if (I.use_empty()) {
+ I.eraseFromParent();
+ return 0;
+ }
+
+ // Create a stack slot to hold the value.
+ AllocaInst *Slot;
+ if (AllocaPoint) {
+ Slot = new AllocaInst(I.getType(), 0,
+ I.getName()+".reg2mem", AllocaPoint);
+ } else {
+ Function *F = I.getParent()->getParent();
+ Slot = new AllocaInst(I.getType(), 0, I.getName()+".reg2mem",
+ F->getEntryBlock().begin());
+ }
+
+ // Change all of the users of the instruction to read from the stack slot.
+ while (!I.use_empty()) {
+ Instruction *U = cast<Instruction>(I.use_back());
+ if (PHINode *PN = dyn_cast<PHINode>(U)) {
+ // If this is a PHI node, we can't insert a load of the value before the
+ // use. Instead insert the load in the predecessor block corresponding
+ // to the incoming value.
+ //
+ // Note that if there are multiple edges from a basic block to this PHI
+ // node that we cannot have multiple loads. The problem is that the
+ // resulting PHI node will have multiple values (from each load) coming in
+ // from the same block, which is illegal SSA form. For this reason, we
+ // keep track of and reuse loads we insert.
+ DenseMap<BasicBlock*, Value*> Loads;
+ for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
+ if (PN->getIncomingValue(i) == &I) {
+ Value *&V = Loads[PN->getIncomingBlock(i)];
+ if (V == 0) {
+ // Insert the load into the predecessor block
+ V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads,
+ PN->getIncomingBlock(i)->getTerminator());
+ }
+ PN->setIncomingValue(i, V);
+ }
- // Handle the case that X itself is a Phi!
- if (PHINode* phiX = dyn_cast<PHINode>(&X))
- {
- phisToGo.insert(phiX);
- PushOperandsOnWorkList(workList, phisToGo, phiX);
+ } else {
+ // If this is a normal instruction, just insert a load.
+ Value *V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads, U);
+ U->replaceUsesOfWith(&I, V);
}
-
- // Now use a worklist to find all phis reachable from X, and
- // (recursively) all phis reachable from operands of such phis.
- for (Instruction* workI; !workList.empty(); workList.pop())
- {
- workI = workList.top();
- for (Value::use_iterator UI=workI->use_begin(), UE=workI->use_end();
- UI != UE; ++UI)
- if (PHINode* phiN = dyn_cast<PHINode>(*UI))
- if (phisToGo.find(phiN) == phisToGo.end())
- { // Seeing this phi for the first time: it must go!
- phisToGo.insert(phiN);
- workList.push(phiN);
- PushOperandsOnWorkList(workList, phisToGo, phiN);
- }
+ }
+
+
+ // Insert stores of the computed value into the stack slot. We have to be
+ // careful if I is an invoke instruction, because we can't insert the store
+ // AFTER the terminator instruction.
+ BasicBlock::iterator InsertPt;
+ if (!isa<TerminatorInst>(I)) {
+ InsertPt = &I;
+ ++InsertPt;
+ } else {
+ InvokeInst &II = cast<InvokeInst>(I);
+ if (II.getNormalDest()->getSinglePredecessor())
+ InsertPt = II.getNormalDest()->getFirstInsertionPt();
+ else {
+ // We cannot demote invoke instructions to the stack if their normal edge
+ // is critical. Therefore, split the critical edge and insert the store
+ // in the newly created basic block.
+ unsigned SuccNum = GetSuccessorNumber(I.getParent(), II.getNormalDest());
+ TerminatorInst *TI = &cast<TerminatorInst>(I);
+ assert (isCriticalEdge(TI, SuccNum) &&
+ "Expected a critical edge!");
+ BasicBlock *BB = SplitCriticalEdge(TI, SuccNum);
+ assert (BB && "Unable to split critical edge.");
+ InsertPt = BB->getFirstInsertionPt();
}
-}
-
+ }
-// Create the Alloca for X
-AllocaInst* CreateAllocaForX(Instruction& X)
-{
- Function* parentFunc = X.getParent()->getParent();
- Instruction* entryInst = parentFunc->getEntryNode().begin();
- return new AllocaInst(X.getType(), /*arraySize*/ NULL,
- X.hasName()? X.getName()+std::string("OnStack")
- : "DemotedTmp",
- entryInst);
-}
-
-// Insert loads before all uses of I, except uses in Phis
-// since all such Phis *must* be deleted.
-void LoadBeforeUses(Instruction* def, AllocaInst* XSlot)
-{
- for (unsigned nPhis = 0; def->use_size() - nPhis > 0; )
- {
- Instruction* useI = cast<Instruction>(def->use_back());
- if (!isa<PHINode>(useI))
- {
- LoadInst* loadI =
- new LoadInst(XSlot, std::string("Load")+XSlot->getName(), useI);
- useI->replaceUsesOfWith(def, loadI);
- }
- else
- ++nPhis;
- }
-}
+ for (; isa<PHINode>(InsertPt) || isa<LandingPadInst>(InsertPt); ++InsertPt)
+ /* empty */; // Don't insert before PHI nodes or landingpad instrs.
-void AddLoadsAndStores(AllocaInst* XSlot, Instruction& X, PhiSet& phisToGo)
-{
- for (PhiSetIterator PI=phisToGo.begin(), PE=phisToGo.end(); PI != PE; ++PI)
- {
- PHINode* pn = *PI;
-
- // First, insert loads before all uses except uses in Phis.
- // Do this first because new stores will appear as uses also!
- LoadBeforeUses(pn, XSlot);
-
- // For every incoming operand of the Phi, insert a store either
- // just after the instruction defining the value or just before the
- // predecessor of the Phi if the value is a formal, not an instruction.
- //
- for (unsigned i=0, N=pn->getNumIncomingValues(); i < N; ++i)
- {
- Value* phiOp = pn->getIncomingValue(i);
- if (phiOp != &X &&
- (!isa<PHINode>(phiOp) ||
- phisToGo.find(cast<PHINode>(phiOp)) == phisToGo.end()))
- { // This operand is not a phi that will be deleted: need to store.
- assert(!isa<TerminatorInst>(phiOp));
-
- Instruction* storeBefore;
- if (Instruction* I = dyn_cast<Instruction>(phiOp))
- { // phiOp is an instruction, store its result right after it.
- assert(I->getNext() && "Non-terminator without successor?");
- storeBefore = I->getNext();
- }
- else
- { // If not, it must be a formal: store it at the end of the
- // predecessor block of the Phi (*not* at function entry!).
- storeBefore = pn->getIncomingBlock(i)->getTerminator();
- }
-
- // Create instr. to store the value of phiOp before `insertBefore'
- StoreInst* storeI = new StoreInst(phiOp, XSlot, storeBefore);
- }
- }
- }
+ new StoreInst(&I, Slot, InsertPt);
+ return Slot;
}
-void DeletePhis(PhiSet& phisToGo)
-{
- for (PhiSetIterator PI=phisToGo.begin(), PE=phisToGo.end(); PI != PE; ++PI)
- {
- assert((*PI)->use_size() == 0 && "This PHI should be DEAD!");
- (*PI)->getParent()->getInstList().remove(*PI);
- delete *PI;
+/// DemotePHIToStack - This function takes a virtual register computed by a PHI
+/// node and replaces it with a slot in the stack frame allocated via alloca.
+/// The PHI node is deleted. It returns the pointer to the alloca inserted.
+AllocaInst *llvm::DemotePHIToStack(PHINode *P, Instruction *AllocaPoint) {
+ if (P->use_empty()) {
+ P->eraseFromParent();
+ return 0;
+ }
+
+ // Create a stack slot to hold the value.
+ AllocaInst *Slot;
+ if (AllocaPoint) {
+ Slot = new AllocaInst(P->getType(), 0,
+ P->getName()+".reg2mem", AllocaPoint);
+ } else {
+ Function *F = P->getParent()->getParent();
+ Slot = new AllocaInst(P->getType(), 0, P->getName()+".reg2mem",
+ F->getEntryBlock().begin());
+ }
+
+ // Iterate over each operand inserting a store in each predecessor.
+ for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
+ if (InvokeInst *II = dyn_cast<InvokeInst>(P->getIncomingValue(i))) {
+ assert(II->getParent() != P->getIncomingBlock(i) &&
+ "Invoke edge not supported yet"); (void)II;
}
- phisToGo.clear();
-}
-
-//----------------------------------------------------------------------------
-// function DemoteRegToStack()
-//
-// This function takes a virtual register computed by an
-// Instruction& X and replaces it with a slot in the stack frame,
-// allocated via alloca. It has to:
-// (1) Identify all Phi operations that have X as an operand and
-// transitively other Phis that use such Phis;
-// (2) Store all values merged with X via Phi operations to the stack slot;
-// (3) Load the value from the stack slot just before any use of X or any
-// of the Phis that were eliminated; and
-// (4) Delete all the Phis, which should all now be dead.
-//
-// Returns the pointer to the alloca inserted to create a stack slot for X.
-//----------------------------------------------------------------------------
-
-AllocaInst* DemoteRegToStack(Instruction& X)
-{
- if (X.getType() == Type::VoidTy)
- return NULL; // nothing to do!
-
- // Find all Phis involving X or recursively using such Phis or Phis
- // involving operands of such Phis (essentially all Phis in the "web" of X)
- PhiSet phisToGo;
- FindPhis(X, phisToGo);
+ new StoreInst(P->getIncomingValue(i), Slot,
+ P->getIncomingBlock(i)->getTerminator());
+ }
- // Create a stack slot to hold X
- AllocaInst* XSlot = CreateAllocaForX(X);
+ // Insert a load in place of the PHI and replace all uses.
+ BasicBlock::iterator InsertPt = P;
- // Insert loads before all uses of X and (*only then*) insert store after X
- assert(X.getNext() && "Non-terminator (since non-void) with no successor?");
- LoadBeforeUses(&X, XSlot);
- StoreInst* storeI = new StoreInst(&X, XSlot, X.getNext());
+ for (; isa<PHINode>(InsertPt) || isa<LandingPadInst>(InsertPt); ++InsertPt)
+ /* empty */; // Don't insert before PHI nodes or landingpad instrs.
- // Do the same for all the phis that will be deleted
- AddLoadsAndStores(XSlot, X, phisToGo);
+ Value *V = new LoadInst(Slot, P->getName()+".reload", InsertPt);
+ P->replaceAllUsesWith(V);
- // Delete the phis and return the alloca instruction
- DeletePhis(phisToGo);
- return XSlot;
+ // Delete PHI.
+ P->eraseFromParent();
+ return Slot;
}
projects / oota-llvm.git / blobdiff