1 //===- DemoteRegToStack.cpp - Move a virtual register to the stack --------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file provide the function DemoteRegToStack(). This function takes a
11 // virtual register computed by an Instruction& X and replaces it with a slot in
12 // the stack frame, allocated via alloca. It returns the pointer to the
13 // AllocaInst inserted.
15 //===----------------------------------------------------------------------===//
17 #include "llvm/Transforms/Utils/DemoteRegToStack.h"
18 #include "llvm/Function.h"
19 #include "llvm/iMemory.h"
20 #include "llvm/iPHINode.h"
21 #include "llvm/iTerminators.h"
22 #include "llvm/Type.h"
23 #include "Support/hash_set"
27 typedef hash_set<PHINode*> PhiSet;
28 typedef hash_set<PHINode*>::iterator PhiSetIterator;
30 // Helper function to push a phi *and* all its operands to the worklist!
31 // Do not push an instruction if it is already in the result set of Phis to go.
32 inline void PushOperandsOnWorkList(std::vector<Instruction*>& workList,
33 PhiSet& phisToGo, PHINode* phiN) {
34 for (User::op_iterator OI = phiN->op_begin(), OE = phiN->op_end();
36 Instruction* opI = cast<Instruction>(OI);
37 if (!isa<PHINode>(opI) || !phisToGo.count(cast<PHINode>(opI)))
38 workList.push_back(opI);
42 static void FindPhis(Instruction& X, PhiSet& phisToGo) {
43 std::vector<Instruction*> workList;
44 workList.push_back(&X);
46 // Handle the case that X itself is a Phi!
47 if (PHINode* phiX = dyn_cast<PHINode>(&X)) {
48 phisToGo.insert(phiX);
49 PushOperandsOnWorkList(workList, phisToGo, phiX);
52 // Now use a worklist to find all phis reachable from X, and
53 // (recursively) all phis reachable from operands of such phis.
54 while (!workList.empty()) {
55 Instruction *I = workList.back();
57 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI!=E; ++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_back(phiN);
63 PushOperandsOnWorkList(workList, phisToGo, phiN);
69 // Insert loads before all uses of I, except uses in Phis
70 // since all such Phis *must* be deleted.
71 static void LoadBeforeUses(Instruction* def, AllocaInst* XSlot) {
72 for (unsigned nPhis = 0; def->use_size() - nPhis > 0; ) {
73 Instruction* useI = cast<Instruction>(def->use_back());
74 if (!isa<PHINode>(useI)) {
76 new LoadInst(XSlot, std::string("Load")+XSlot->getName(), useI);
77 useI->replaceUsesOfWith(def, loadI);
83 static void AddLoadsAndStores(AllocaInst* XSlot, Instruction& X,
85 for (PhiSetIterator PI=phisToGo.begin(), PE=phisToGo.end(); PI != PE; ++PI) {
88 // First, insert loads before all uses except uses in Phis.
89 // Do this first because new stores will appear as uses also!
90 LoadBeforeUses(pn, XSlot);
92 // For every incoming operand of the Phi, insert a store either
93 // just after the instruction defining the value or just before the
94 // predecessor of the Phi if the value is a formal, not an instruction.
96 for (unsigned i=0, N=pn->getNumIncomingValues(); i < N; ++i) {
97 Value* phiOp = pn->getIncomingValue(i);
99 (!isa<PHINode>(phiOp) || !phisToGo.count(cast<PHINode>(phiOp)))) {
100 // This operand is not a phi that will be deleted: need to store.
101 assert(!isa<TerminatorInst>(phiOp));
103 Instruction* storeBefore;
104 if (Instruction* I = dyn_cast<Instruction>(phiOp)) {
105 // phiOp is an instruction, store its result right after it.
106 assert(I->getNext() && "Non-terminator without successor?");
107 storeBefore = I->getNext();
109 // If not, it must be a formal: store it at the end of the
110 // predecessor block of the Phi (*not* at function entry!).
111 storeBefore = pn->getIncomingBlock(i)->getTerminator();
114 // Create instr. to store the value of phiOp before `insertBefore'
115 StoreInst* storeI = new StoreInst(phiOp, XSlot, storeBefore);
121 //----------------------------------------------------------------------------
122 // function DemoteRegToStack()
124 // This function takes a virtual register computed by an
125 // Instruction& X and replaces it with a slot in the stack frame,
126 // allocated via alloca. It has to:
127 // (1) Identify all Phi operations that have X as an operand and
128 // transitively other Phis that use such Phis;
129 // (2) Store all values merged with X via Phi operations to the stack slot;
130 // (3) Load the value from the stack slot just before any use of X or any
131 // of the Phis that were eliminated; and
132 // (4) Delete all the Phis, which should all now be dead.
134 // Returns the pointer to the alloca inserted to create a stack slot for X.
136 AllocaInst* DemoteRegToStack(Instruction& X) {
137 if (X.getType() == Type::VoidTy)
138 return 0; // nothing to do!
140 // Find all Phis involving X or recursively using such Phis or Phis
141 // involving operands of such Phis (essentially all Phis in the "web" of X)
143 FindPhis(X, phisToGo);
145 // Create a stack slot to hold X
146 Function* parentFunc = X.getParent()->getParent();
147 AllocaInst *XSlot = new AllocaInst(X.getType(), 0, X.getName(),
148 parentFunc->getEntryBlock().begin());
151 // Insert loads before all uses of X and (*only then*) insert store after X
152 assert(X.getNext() && "Non-terminator (since non-void) with no successor?");
153 LoadBeforeUses(&X, XSlot);
154 StoreInst* storeI = new StoreInst(&X, XSlot, X.getNext());
156 // Do the same for all the phis that will be deleted
157 AddLoadsAndStores(XSlot, X, phisToGo);
159 // Delete the phis and return the alloca instruction
160 for (PhiSetIterator PI = phisToGo.begin(), E = phisToGo.end(); PI != E; ++PI)
161 (*PI)->getParent()->getInstList().erase(*PI);
166 } // End llvm namespace