1//===- DemoteRegToStack.cpp - Move a virtual register to the stack --------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file provide the function DemoteRegToStack().  This function takes a
11// virtual register computed by an Instruction and replaces it with a slot in
12// the stack frame, allocated via alloca. It returns the pointer to the
13// AllocaInst inserted.  After this function is called on an instruction, we are
14// guaranteed that the only user of the instruction is a store that is
15// immediately after it.
16//
17//===----------------------------------------------------------------------===//
18
19#include "llvm/Transforms/Utils/Local.h"
20#include "llvm/Function.h"
21#include "llvm/Instructions.h"
22#include "llvm/Type.h"
23#include <map>
24using namespace llvm;
25
26/// DemoteRegToStack - This function takes a virtual register computed by an
27/// Instruction and replaces it with a slot in the stack frame, allocated via
28/// alloca.  This allows the CFG to be changed around without fear of
29/// invalidating the SSA information for the value.  It returns the pointer to
30/// the alloca inserted to create a stack slot for I.
31///
32AllocaInst* llvm::DemoteRegToStack(Instruction &I, bool VolatileLoads,
33                                   Instruction *AllocaPoint) {
34  if (I.use_empty()) {
35    I.eraseFromParent();
36    return 0;
37  }
38
39  // Create a stack slot to hold the value.
40  AllocaInst *Slot;
41  if (AllocaPoint) {
42    Slot = new AllocaInst(I.getType(), 0,
43                          I.getName()+".reg2mem", AllocaPoint);
44  } else {
45    Function *F = I.getParent()->getParent();
46    Slot = new AllocaInst(I.getType(), 0, I.getName()+".reg2mem",
47                          F->getEntryBlock().begin());
48  }
49
50  // Change all of the users of the instruction to read from the stack slot
51  // instead.
52  while (!I.use_empty()) {
53    Instruction *U = cast<Instruction>(I.use_back());
54    if (PHINode *PN = dyn_cast<PHINode>(U)) {
55      // If this is a PHI node, we can't insert a load of the value before the
56      // use.  Instead, insert the load in the predecessor block corresponding
57      // to the incoming value.
58      //
59      // Note that if there are multiple edges from a basic block to this PHI
60      // node that we cannot multiple loads.  The problem is that the resultant
61      // PHI node will have multiple values (from each load) coming in from the
62      // same block, which is illegal SSA form.  For this reason, we keep track
63      // and reuse loads we insert.
64      std::map<BasicBlock*, Value*> Loads;
65      for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
66        if (PN->getIncomingValue(i) == &I) {
67          Value *&V = Loads[PN->getIncomingBlock(i)];
68          if (V == 0) {
69            // Insert the load into the predecessor block
70            V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads,
71                             PN->getIncomingBlock(i)->getTerminator());
72          }
73          PN->setIncomingValue(i, V);
74        }
75
76    } else {
77      // If this is a normal instruction, just insert a load.
78      Value *V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads, U);
79      U->replaceUsesOfWith(&I, V);
80    }
81  }
82
83
84  // Insert stores of the computed value into the stack slot.  We have to be
85  // careful is I is an invoke instruction though, because we can't insert the
86  // store AFTER the terminator instruction.
87  BasicBlock::iterator InsertPt;
88  if (!isa<TerminatorInst>(I)) {
89    InsertPt = &I;
90    ++InsertPt;
91  } else {
92    // We cannot demote invoke instructions to the stack if their normal edge
93    // is critical.
94    InvokeInst &II = cast<InvokeInst>(I);
95    assert(II.getNormalDest()->getSinglePredecessor() &&
96           "Cannot demote invoke with a critical successor!");
97    InsertPt = II.getNormalDest()->begin();
98  }
99
100  for (; isa<PHINode>(InsertPt); ++InsertPt)
101  /* empty */;   // Don't insert before any PHI nodes.
102  new StoreInst(&I, Slot, InsertPt);
103
104  return Slot;
105}
106
107
108/// DemotePHIToStack - This function takes a virtual register computed by a phi
109/// node and replaces it with a slot in the stack frame, allocated via alloca.
110/// The phi node is deleted and it returns the pointer to the alloca inserted.
111AllocaInst* llvm::DemotePHIToStack(PHINode *P, Instruction *AllocaPoint) {
112  if (P->use_empty()) {
113    P->eraseFromParent();
114    return 0;
115  }
116
117  // Create a stack slot to hold the value.
118  AllocaInst *Slot;
119  if (AllocaPoint) {
120    Slot = new AllocaInst(P->getType(), 0,
121                          P->getName()+".reg2mem", AllocaPoint);
122  } else {
123    Function *F = P->getParent()->getParent();
124    Slot = new AllocaInst(P->getType(), 0, P->getName()+".reg2mem",
125                          F->getEntryBlock().begin());
126  }
127
128  // Iterate over each operand, insert store in each predecessor.
129  for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
130    if (InvokeInst *II = dyn_cast<InvokeInst>(P->getIncomingValue(i))) {
131      assert(II->getParent() != P->getIncomingBlock(i) &&
132             "Invoke edge not supported yet"); (void)II;
133    }
134    new StoreInst(P->getIncomingValue(i), Slot,
135                  P->getIncomingBlock(i)->getTerminator());
136  }
137
138  // Insert load in place of the phi and replace all uses.
139  Value *V = new LoadInst(Slot, P->getName()+".reload", P);
140  P->replaceAllUsesWith(V);
141
142  // Delete phi.
143  P->eraseFromParent();
144
145  return Slot;
146}
147