1 //===- DemoteRegToStack.cpp - Move a virtual register to the stack --------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
11 #include "llvm/Transforms/Utils/Local.h"
12 #include "llvm/ADT/DenseMap.h"
13 #include "llvm/IR/Function.h"
14 #include "llvm/IR/Instructions.h"
15 #include "llvm/IR/Type.h"
18 /// DemoteRegToStack - This function takes a virtual register computed by an
19 /// Instruction and replaces it with a slot in the stack frame, allocated via
20 /// alloca. This allows the CFG to be changed around without fear of
21 /// invalidating the SSA information for the value. It returns the pointer to
22 /// the alloca inserted to create a stack slot for I.
23 AllocaInst *llvm::DemoteRegToStack(Instruction &I, bool VolatileLoads,
24 Instruction *AllocaPoint) {
30 // Create a stack slot to hold the value.
33 Slot = new AllocaInst(I.getType(), 0,
34 I.getName()+".reg2mem", AllocaPoint);
36 Function *F = I.getParent()->getParent();
37 Slot = new AllocaInst(I.getType(), 0, I.getName()+".reg2mem",
38 F->getEntryBlock().begin());
41 // Change all of the users of the instruction to read from the stack slot.
42 while (!I.use_empty()) {
43 Instruction *U = cast<Instruction>(I.use_back());
44 if (PHINode *PN = dyn_cast<PHINode>(U)) {
45 // If this is a PHI node, we can't insert a load of the value before the
46 // use. Instead insert the load in the predecessor block corresponding
47 // to the incoming value.
49 // Note that if there are multiple edges from a basic block to this PHI
50 // node that we cannot have multiple loads. The problem is that the
51 // resulting PHI node will have multiple values (from each load) coming in
52 // from the same block, which is illegal SSA form. For this reason, we
53 // keep track of and reuse loads we insert.
54 DenseMap<BasicBlock*, Value*> Loads;
55 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
56 if (PN->getIncomingValue(i) == &I) {
57 Value *&V = Loads[PN->getIncomingBlock(i)];
59 // Insert the load into the predecessor block
60 V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads,
61 PN->getIncomingBlock(i)->getTerminator());
63 PN->setIncomingValue(i, V);
67 // If this is a normal instruction, just insert a load.
68 Value *V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads, U);
69 U->replaceUsesOfWith(&I, V);
74 // Insert stores of the computed value into the stack slot. We have to be
75 // careful if I is an invoke instruction, because we can't insert the store
76 // AFTER the terminator instruction.
77 BasicBlock::iterator InsertPt;
78 if (!isa<TerminatorInst>(I)) {
82 InvokeInst &II = cast<InvokeInst>(I);
83 if (II.getNormalDest()->getSinglePredecessor())
84 InsertPt = II.getNormalDest()->getFirstInsertionPt();
86 // We cannot demote invoke instructions to the stack if their normal edge
87 // is critical. Therefore, split the critical edge and insert the store
88 // in the newly created basic block.
89 unsigned SuccNum = GetSuccessorNumber(I.getParent(), II.getNormalDest());
90 TerminatorInst *TI = &cast<TerminatorInst>(I);
91 assert (isCriticalEdge(TI, SuccNum) &&
92 "Expected a critical edge!");
93 BasicBlock *BB = SplitCriticalEdge(TI, SuccNum);
94 assert (BB && "Unable to split critical edge.");
95 InsertPt = BB->getFirstInsertionPt();
99 for (; isa<PHINode>(InsertPt) || isa<LandingPadInst>(InsertPt); ++InsertPt)
100 /* empty */; // Don't insert before PHI nodes or landingpad instrs.
102 new StoreInst(&I, Slot, InsertPt);
106 /// DemotePHIToStack - This function takes a virtual register computed by a PHI
107 /// node and replaces it with a slot in the stack frame allocated via alloca.
108 /// The PHI node is deleted. It returns the pointer to the alloca inserted.
109 AllocaInst *llvm::DemotePHIToStack(PHINode *P, Instruction *AllocaPoint) {
110 if (P->use_empty()) {
111 P->eraseFromParent();
115 // Create a stack slot to hold the value.
118 Slot = new AllocaInst(P->getType(), 0,
119 P->getName()+".reg2mem", AllocaPoint);
121 Function *F = P->getParent()->getParent();
122 Slot = new AllocaInst(P->getType(), 0, P->getName()+".reg2mem",
123 F->getEntryBlock().begin());
126 // Iterate over each operand inserting a store in each predecessor.
127 for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
128 if (InvokeInst *II = dyn_cast<InvokeInst>(P->getIncomingValue(i))) {
129 assert(II->getParent() != P->getIncomingBlock(i) &&
130 "Invoke edge not supported yet"); (void)II;
132 new StoreInst(P->getIncomingValue(i), Slot,
133 P->getIncomingBlock(i)->getTerminator());
136 // Insert a load in place of the PHI and replace all uses.
137 BasicBlock::iterator InsertPt = P;
139 for (; isa<PHINode>(InsertPt) || isa<LandingPadInst>(InsertPt); ++InsertPt)
140 /* empty */; // Don't insert before PHI nodes or landingpad instrs.
142 Value *V = new LoadInst(Slot, P->getName()+".reload", InsertPt);
143 P->replaceAllUsesWith(V);
146 P->eraseFromParent();