LLVM  6.0.0svn
DemoteRegToStack.cpp
Go to the documentation of this file.
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/ADT/DenseMap.h"
11 #include "llvm/Analysis/CFG.h"
12 #include "llvm/IR/Function.h"
13 #include "llvm/IR/Instructions.h"
14 #include "llvm/IR/Type.h"
17 using namespace llvm;
18 
19 /// DemoteRegToStack - This function takes a virtual register computed by an
20 /// Instruction and replaces it with a slot in the stack frame, allocated via
21 /// alloca. This allows the CFG to be changed around without fear of
22 /// invalidating the SSA information for the value. It returns the pointer to
23 /// the alloca inserted to create a stack slot for I.
25  Instruction *AllocaPoint) {
26  if (I.use_empty()) {
27  I.eraseFromParent();
28  return nullptr;
29  }
30 
31  Function *F = I.getParent()->getParent();
32  const DataLayout &DL = F->getParent()->getDataLayout();
33 
34  // Create a stack slot to hold the value.
35  AllocaInst *Slot;
36  if (AllocaPoint) {
37  Slot = new AllocaInst(I.getType(), DL.getAllocaAddrSpace(), nullptr,
38  I.getName()+".reg2mem", AllocaPoint);
39  } else {
40  Slot = new AllocaInst(I.getType(), DL.getAllocaAddrSpace(), nullptr,
41  I.getName() + ".reg2mem", &F->getEntryBlock().front());
42  }
43 
44  // We cannot demote invoke instructions to the stack if their normal edge
45  // is critical. Therefore, split the critical edge and create a basic block
46  // into which the store can be inserted.
47  if (InvokeInst *II = dyn_cast<InvokeInst>(&I)) {
48  if (!II->getNormalDest()->getSinglePredecessor()) {
49  unsigned SuccNum = GetSuccessorNumber(II->getParent(), II->getNormalDest());
50  assert(isCriticalEdge(II, SuccNum) && "Expected a critical edge!");
51  BasicBlock *BB = SplitCriticalEdge(II, SuccNum);
52  assert(BB && "Unable to split critical edge.");
53  (void)BB;
54  }
55  }
56 
57  // Change all of the users of the instruction to read from the stack slot.
58  while (!I.use_empty()) {
59  Instruction *U = cast<Instruction>(I.user_back());
60  if (PHINode *PN = dyn_cast<PHINode>(U)) {
61  // If this is a PHI node, we can't insert a load of the value before the
62  // use. Instead insert the load in the predecessor block corresponding
63  // to the incoming value.
64  //
65  // Note that if there are multiple edges from a basic block to this PHI
66  // node that we cannot have multiple loads. The problem is that the
67  // resulting PHI node will have multiple values (from each load) coming in
68  // from the same block, which is illegal SSA form. For this reason, we
69  // keep track of and reuse loads we insert.
71  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
72  if (PN->getIncomingValue(i) == &I) {
73  Value *&V = Loads[PN->getIncomingBlock(i)];
74  if (!V) {
75  // Insert the load into the predecessor block
76  V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads,
77  PN->getIncomingBlock(i)->getTerminator());
78  }
79  PN->setIncomingValue(i, V);
80  }
81 
82  } else {
83  // If this is a normal instruction, just insert a load.
84  Value *V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads, U);
85  U->replaceUsesOfWith(&I, V);
86  }
87  }
88 
89  // Insert stores of the computed value into the stack slot. We have to be
90  // careful if I is an invoke instruction, because we can't insert the store
91  // AFTER the terminator instruction.
92  BasicBlock::iterator InsertPt;
93  if (!isa<TerminatorInst>(I)) {
94  InsertPt = ++I.getIterator();
95  for (; isa<PHINode>(InsertPt) || InsertPt->isEHPad(); ++InsertPt)
96  /* empty */; // Don't insert before PHI nodes or landingpad instrs.
97  } else {
98  InvokeInst &II = cast<InvokeInst>(I);
99  InsertPt = II.getNormalDest()->getFirstInsertionPt();
100  }
101 
102  new StoreInst(&I, Slot, &*InsertPt);
103  return Slot;
104 }
105 
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.
110  if (P->use_empty()) {
111  P->eraseFromParent();
112  return nullptr;
113  }
114 
115  const DataLayout &DL = P->getModule()->getDataLayout();
116 
117  // Create a stack slot to hold the value.
118  AllocaInst *Slot;
119  if (AllocaPoint) {
120  Slot = new AllocaInst(P->getType(), DL.getAllocaAddrSpace(), nullptr,
121  P->getName()+".reg2mem", AllocaPoint);
122  } else {
123  Function *F = P->getParent()->getParent();
124  Slot = new AllocaInst(P->getType(), DL.getAllocaAddrSpace(), nullptr,
125  P->getName() + ".reg2mem",
126  &F->getEntryBlock().front());
127  }
128 
129  // Iterate over each operand inserting a store in each predecessor.
130  for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
131  if (InvokeInst *II = dyn_cast<InvokeInst>(P->getIncomingValue(i))) {
132  assert(II->getParent() != P->getIncomingBlock(i) &&
133  "Invoke edge not supported yet"); (void)II;
134  }
135  new StoreInst(P->getIncomingValue(i), Slot,
137  }
138 
139  // Insert a load in place of the PHI and replace all uses.
140  BasicBlock::iterator InsertPt = P->getIterator();
141 
142  for (; isa<PHINode>(InsertPt) || InsertPt->isEHPad(); ++InsertPt)
143  /* empty */; // Don't insert before PHI nodes or landingpad instrs.
144 
145  Value *V = new LoadInst(Slot, P->getName() + ".reload", &*InsertPt);
146  P->replaceAllUsesWith(V);
147 
148  // Delete PHI.
149  P->eraseFromParent();
150  return Slot;
151 }
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:69
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
AllocaInst * DemoteRegToStack(Instruction &X, bool VolatileLoads=false, Instruction *AllocaPoint=nullptr)
This function takes a virtual register computed by an Instruction and replaces it with a slot in the ...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
An instruction for reading from memory.
Definition: Instructions.h:164
unsigned getAllocaAddrSpace() const
Definition: DataLayout.h:253
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
#define F(x, y, z)
Definition: MD5.cpp:55
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
An instruction for storing to memory.
Definition: Instructions.h:306
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:428
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:22
const BasicBlock & getEntryBlock() const
Definition: Function.h:564
BasicBlock * SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
If this edge is a critical edge, insert a new node to split the critical edge.
#define P(N)
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:200
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
const Instruction & front() const
Definition: BasicBlock.h:264
self_iterator getIterator()
Definition: ilist_node.h:82
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
BasicBlock * getNormalDest() const
Iterator for intrusive lists based on ilist_node.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
Definition: Instruction.h:63
unsigned getNumIncomingValues() const
Return the number of incoming edges.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:57
unsigned GetSuccessorNumber(const BasicBlock *BB, const BasicBlock *Succ)
Search for the specified successor of basic block BB and return its position in the terminator instru...
Definition: CFG.cpp:72
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:218
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
AllocaInst * DemotePHIToStack(PHINode *P, Instruction *AllocaPoint=nullptr)
This function takes a virtual register computed by a phi node and replaces it with a slot in the stac...
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:545
LLVM Value Representation.
Definition: Value.h:73
Invoke instruction.
const TerminatorInst * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:120
bool use_empty() const
Definition: Value.h:322
const BasicBlock * getParent() const
Definition: Instruction.h:66
an instruction to allocate memory on the stack
Definition: Instructions.h:60
bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
Definition: CFG.cpp:88