1 //===- DemoteRegToStack.cpp - Move a virtual reg. to stack ------*- C++ -*-===//
2 //
3 // This file provide the function DemoteRegToStack().  This function takes a
4 // virtual register computed by an Instruction& X and replaces it with a slot in
5 // the stack frame, allocated via alloca. It returns the pointer to the
6 // AllocaInst inserted.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "llvm/Transforms/Utils/DemoteRegToStack.h"
11 #include "llvm/Function.h"
12 #include "llvm/iMemory.h"
13 #include "llvm/iPHINode.h"
14 #include "llvm/iTerminators.h"
15 #include "llvm/Type.h"
16 #include "Support/hash_set"
17 #include <stack>
18 
19 //----------------------------------------------------------------------------
20 // function DemoteRegToStack()
21 //
22 //----------------------------------------------------------------------------
23 
24 typedef hash_set<PHINode*>           PhiSet;
25 typedef hash_set<PHINode*>::iterator PhiSetIterator;
26 
27 // Helper function to push a phi *and* all its operands to the worklist!
28 // Do not push an instruction if it is already in the result set of Phis to go.
29 inline void PushOperandsOnWorkList(std::stack<Instruction*>& workList,
30                                    PhiSet& phisToGo, PHINode* phiN) {
31   for (User::op_iterator OI = phiN->op_begin(), OE = phiN->op_end();
32        OI != OE; ++OI)
33     if (Instruction* opI = dyn_cast<Instruction>(OI))
34       if (!isa<PHINode>(opI) ||
35           phisToGo.find(cast<PHINode>(opI)) == phisToGo.end())
36         workList.push(opI);
37 }
38 
39 void FindPhis(Instruction& X, PhiSet& phisToGo)
40 {
41   std::stack<Instruction*> workList;
42   workList.push(&X);
43 
44   // Handle the case that X itself is a Phi!
45   if (PHINode* phiX = dyn_cast<PHINode>(&X))
46     {
47       phisToGo.insert(phiX);
48       PushOperandsOnWorkList(workList, phisToGo, phiX);
49     }
50 
51   // Now use a worklist to find all phis reachable from X, and
52   // (recursively) all phis reachable from operands of such phis.
53   for (Instruction* workI; !workList.empty(); workList.pop())
54     {
55       workI = workList.top();
56       for (Value::use_iterator UI=workI->use_begin(), UE=workI->use_end();
57            UI != UE; ++UI)
58         if (PHINode* phiN = dyn_cast<PHINode>(*UI))
59           if (phisToGo.find(phiN) == phisToGo.end())
60             { // Seeing this phi for the first time: it must go!
61               phisToGo.insert(phiN);
62               workList.push(phiN);
63               PushOperandsOnWorkList(workList, phisToGo, phiN);
64             }
65     }
66 }
67 
68 
69 // Create the Alloca for X
70 AllocaInst* CreateAllocaForX(Instruction& X)
71 {
72   Function* parentFunc = X.getParent()->getParent();
73   Instruction* entryInst = parentFunc->getEntryNode().begin();
74   return new AllocaInst(X.getType(), /*arraySize*/ NULL,
75                         X.hasName()? X.getName()+std::string("OnStack")
76                                    : "DemotedTmp",
77                         entryInst);
78 }
79 
80 // Insert loads before all uses of I, except uses in Phis
81 // since all such Phis *must* be deleted.
82 void LoadBeforeUses(Instruction* def, AllocaInst* XSlot)
83 {
84   for (unsigned nPhis = 0; def->use_size() - nPhis > 0; )
85     {
86       Instruction* useI = cast<Instruction>(def->use_back());
87       if (!isa<PHINode>(useI))
88         {
89           LoadInst* loadI =
90             new LoadInst(XSlot, std::string("Load")+XSlot->getName(), useI);
91           useI->replaceUsesOfWith(def, loadI);
92         }
93       else
94         ++nPhis;
95     }
96 }
97 
98 void AddLoadsAndStores(AllocaInst* XSlot, Instruction& X, PhiSet& phisToGo)
99 {
100   for (PhiSetIterator PI=phisToGo.begin(), PE=phisToGo.end(); PI != PE; ++PI)
101     {
102       PHINode* pn = *PI;
103 
104       // First, insert loads before all uses except uses in Phis.
105       // Do this first because new stores will appear as uses also!
106       LoadBeforeUses(pn, XSlot);
107 
108       // For every incoming operand of the Phi, insert a store either
109       // just after the instruction defining the value or just before the
110       // predecessor of the Phi if the value is a formal, not an instruction.
111       //
112       for (unsigned i=0, N=pn->getNumIncomingValues(); i < N; ++i)
113         {
114           Value* phiOp = pn->getIncomingValue(i);
115           if (phiOp != &X &&
116               (!isa<PHINode>(phiOp) ||
117                phisToGo.find(cast<PHINode>(phiOp)) == phisToGo.end()))
118             { // This operand is not a phi that will be deleted: need to store.
119               assert(!isa<TerminatorInst>(phiOp));
120 
121               Instruction* storeBefore;
122               if (Instruction* I = dyn_cast<Instruction>(phiOp))
123                 { // phiOp is an instruction, store its result right after it.
124                   assert(I->getNext() && "Non-terminator without successor?");
125                   storeBefore = I->getNext();
126                 }
127               else
128                 { // If not, it must be a formal: store it at the end of the
129                   // predecessor block of the Phi (*not* at function entry!).
130                   storeBefore = pn->getIncomingBlock(i)->getTerminator();
131                 }
132 
133               // Create instr. to store the value of phiOp before `insertBefore'
134               StoreInst* storeI = new StoreInst(phiOp, XSlot, storeBefore);
135             }
136         }
137     }
138 }
139 
140 void DeletePhis(PhiSet& phisToGo)
141 {
142   for (PhiSetIterator PI=phisToGo.begin(), PE=phisToGo.end(); PI != PE; ++PI)
143     {
144       assert((*PI)->use_size() == 0 && "This PHI should be DEAD!");
145       (*PI)->getParent()->getInstList().remove(*PI);
146       delete *PI;
147     }
148   phisToGo.clear();
149 }
150 
151 //----------------------------------------------------------------------------
152 // function DemoteRegToStack()
153 //
154 // This function takes a virtual register computed by an
155 // Instruction& X and replaces it with a slot in the stack frame,
156 // allocated via alloca.  It has to:
157 // (1) Identify all Phi operations that have X as an operand and
158 //     transitively other Phis that use such Phis;
159 // (2) Store all values merged with X via Phi operations to the stack slot;
160 // (3) Load the value from the stack slot just before any use of X or any
161 //     of the Phis that were eliminated; and
162 // (4) Delete all the Phis, which should all now be dead.
163 //
164 // Returns the pointer to the alloca inserted to create a stack slot for X.
165 //----------------------------------------------------------------------------
166 
167 AllocaInst* DemoteRegToStack(Instruction& X)
168 {
169   if (X.getType() == Type::VoidTy)
170     return NULL;                             // nothing to do!
171 
172   // Find all Phis involving X or recursively using such Phis or Phis
173   // involving operands of such Phis (essentially all Phis in the "web" of X)
174   PhiSet phisToGo;
175   FindPhis(X, phisToGo);
176 
177   // Create a stack slot to hold X
178   AllocaInst* XSlot = CreateAllocaForX(X);
179 
180   // Insert loads before all uses of X and (*only then*) insert store after X
181   assert(X.getNext() && "Non-terminator (since non-void) with no successor?");
182   LoadBeforeUses(&X, XSlot);
183   StoreInst* storeI = new StoreInst(&X, XSlot, X.getNext());
184 
185   // Do the same for all the phis that will be deleted
186   AddLoadsAndStores(XSlot, X, phisToGo);
187 
188   // Delete the phis and return the alloca instruction
189   DeletePhis(phisToGo);
190   return XSlot;
191 }
192