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