X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FDemoteRegToStack.cpp;h=9972b22a07e400fdd0b1ffeaa8038e8f99df6464;hb=7478e275730f5b9fc0651b5600761c8e707e1897;hp=32c1f19127a8540c2bef20dbab96503c8edceffc;hpb=a024e8cedab928403818ac79e899cdae2a356c56;p=oota-llvm.git diff --git a/lib/Transforms/Utils/DemoteRegToStack.cpp b/lib/Transforms/Utils/DemoteRegToStack.cpp index 32c1f19127a..9972b22a07e 100644 --- a/lib/Transforms/Utils/DemoteRegToStack.cpp +++ b/lib/Transforms/Utils/DemoteRegToStack.cpp @@ -2,25 +2,18 @@ // // 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 file provide the function DemoteRegToStack(). This function takes a -// virtual register computed by an Instruction and replaces it with a slot in -// the stack frame, allocated via alloca. It returns the pointer to the -// AllocaInst inserted. After this function is called on an instruction, we are -// guaranteed that the only user of the instruction is a store that is -// immediately after it. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// +#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" -#include "llvm/Function.h" -#include "llvm/Instructions.h" -#include "llvm/Type.h" -#include using namespace llvm; /// DemoteRegToStack - This function takes a virtual register computed by an @@ -28,45 +21,44 @@ using namespace llvm; /// 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, +AllocaInst *llvm::DemoteRegToStack(Instruction &I, bool VolatileLoads, Instruction *AllocaPoint) { if (I.use_empty()) { I.eraseFromParent(); - return 0; + return nullptr; } - + // Create a stack slot to hold the value. AllocaInst *Slot; if (AllocaPoint) { - Slot = new AllocaInst(I.getType(), 0, I.getName()+".reg2mem", AllocaPoint); + Slot = new AllocaInst(I.getType(), nullptr, + I.getName()+".reg2mem", AllocaPoint); } else { Function *F = I.getParent()->getParent(); - Slot = new AllocaInst(I.getType(), 0, I.getName()+".reg2mem", + Slot = new AllocaInst(I.getType(), nullptr, I.getName()+".reg2mem", F->getEntryBlock().begin()); } - - // Change all of the users of the instruction to read from the stack slot - // instead. + + // Change all of the users of the instruction to read from the stack slot. while (!I.use_empty()) { - Instruction *U = cast(I.use_back()); + Instruction *U = cast(I.user_back()); if (PHINode *PN = dyn_cast(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 + // 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 multiple loads. The problem is that the resultant - // 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 - // and reuse loads we insert. - std::map Loads; + // 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 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) { + if (!V) { // Insert the load into the predecessor block - V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads, + V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads, PN->getIncomingBlock(i)->getTerminator()); } PN->setIncomingValue(i, V); @@ -80,69 +72,78 @@ AllocaInst* llvm::DemoteRegToStack(Instruction &I, bool VolatileLoads, } - // Insert stores of the computed value into the stack slot. We have to be - // careful is I is an invoke instruction though, because we can't insert the - // store AFTER the terminator instruction. + // 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(I)) { InsertPt = &I; ++InsertPt; } else { - // We cannot demote invoke instructions to the stack if their normal edge - // is critical. InvokeInst &II = cast(I); - assert(II.getNormalDest()->getSinglePredecessor() && - "Cannot demote invoke with a critical successor!"); - InsertPt = II.getNormalDest()->begin(); + 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(I); + assert (isCriticalEdge(TI, SuccNum) && + "Expected a critical edge!"); + BasicBlock *BB = SplitCriticalEdge(TI, SuccNum); + assert (BB && "Unable to split critical edge."); + InsertPt = BB->getFirstInsertionPt(); + } } - for (; isa(InsertPt); ++InsertPt) - /* empty */; // Don't insert before any PHI nodes. - new StoreInst(&I, Slot, InsertPt); + for (; isa(InsertPt) || isa(InsertPt); ++InsertPt) + /* empty */; // Don't insert before PHI nodes or landingpad instrs. + new StoreInst(&I, Slot, InsertPt); return Slot; } - -/// 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 and it returns the pointer to the alloca inserted. -AllocaInst* llvm::DemotePHIToStack(PHINode *P, Instruction *AllocaPoint) { +/// 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; + P->eraseFromParent(); + return nullptr; } // Create a stack slot to hold the value. AllocaInst *Slot; if (AllocaPoint) { - Slot = new AllocaInst(P->getType(), 0, P->getName()+".reg2mem", AllocaPoint); + Slot = new AllocaInst(P->getType(), nullptr, + P->getName()+".reg2mem", AllocaPoint); } else { Function *F = P->getParent()->getParent(); - Slot = new AllocaInst(P->getType(), 0, P->getName()+".reg2mem", + Slot = new AllocaInst(P->getType(), nullptr, P->getName()+".reg2mem", F->getEntryBlock().begin()); } - - // Iterate over each operand, insert store in each predecessor. + + // 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(P->getIncomingValue(i))) { - assert(II->getParent() != P->getIncomingBlock(i) && - "Invoke edge not supported yet"); + assert(II->getParent() != P->getIncomingBlock(i) && + "Invoke edge not supported yet"); (void)II; } - new StoreInst(P->getIncomingValue(i), Slot, + new StoreInst(P->getIncomingValue(i), Slot, P->getIncomingBlock(i)->getTerminator()); } - - // Insert load in place of the phi and replace all uses. - BasicBlock::iterator InsertPt; - for (InsertPt = P->getParent()->getInstList().begin(); - isa(InsertPt); ++InsertPt) - ; /*noop */ - Value *V = new LoadInst(Slot, P->getName()+".reload", P); + + // Insert a load in place of the PHI and replace all uses. + BasicBlock::iterator InsertPt = P; + + for (; isa(InsertPt) || isa(InsertPt); ++InsertPt) + /* empty */; // Don't insert before PHI nodes or landingpad instrs. + + Value *V = new LoadInst(Slot, P->getName()+".reload", InsertPt); P->replaceAllUsesWith(V); - - // Delete phi. + + // Delete PHI. P->eraseFromParent(); - return Slot; }