LLVM  9.0.0svn
DemoteRegToStack.cpp
Go to the documentation of this file.
1 //===- DemoteRegToStack.cpp - Move a virtual register to the stack --------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "llvm/ADT/DenseMap.h"
10 #include "llvm/Analysis/CFG.h"
12 #include "llvm/IR/Function.h"
13 #include "llvm/IR/Instructions.h"
14 #include "llvm/IR/Type.h"
16 using namespace llvm;
17 
18 /// DemoteRegToStack - This function takes a virtual register computed by an
19 /// Instruction and replaces it with a slot in the stack frame, allocated via
20 /// alloca. This allows the CFG to be changed around without fear of
21 /// invalidating the SSA information for the value. It returns the pointer to
22 /// the alloca inserted to create a stack slot for I.
24  Instruction *AllocaPoint) {
25  if (I.use_empty()) {
26  I.eraseFromParent();
27  return nullptr;
28  }
29 
30  Function *F = I.getParent()->getParent();
31  const DataLayout &DL = F->getParent()->getDataLayout();
32 
33  // Create a stack slot to hold the value.
34  AllocaInst *Slot;
35  if (AllocaPoint) {
36  Slot = new AllocaInst(I.getType(), DL.getAllocaAddrSpace(), nullptr,
37  I.getName()+".reg2mem", AllocaPoint);
38  } else {
39  Slot = new AllocaInst(I.getType(), DL.getAllocaAddrSpace(), nullptr,
40  I.getName() + ".reg2mem", &F->getEntryBlock().front());
41  }
42 
43  // We cannot demote invoke instructions to the stack if their normal edge
44  // is critical. Therefore, split the critical edge and create a basic block
45  // into which the store can be inserted.
46  if (InvokeInst *II = dyn_cast<InvokeInst>(&I)) {
47  if (!II->getNormalDest()->getSinglePredecessor()) {
48  unsigned SuccNum = GetSuccessorNumber(II->getParent(), II->getNormalDest());
49  assert(isCriticalEdge(II, SuccNum) && "Expected a critical edge!");
50  BasicBlock *BB = SplitCriticalEdge(II, SuccNum);
51  assert(BB && "Unable to split critical edge.");
52  (void)BB;
53  }
54  }
55 
56  // Change all of the users of the instruction to read from the stack slot.
57  while (!I.use_empty()) {
58  Instruction *U = cast<Instruction>(I.user_back());
59  if (PHINode *PN = dyn_cast<PHINode>(U)) {
60  // If this is a PHI node, we can't insert a load of the value before the
61  // use. Instead insert the load in the predecessor block corresponding
62  // to the incoming value.
63  //
64  // Note that if there are multiple edges from a basic block to this PHI
65  // node that we cannot have multiple loads. The problem is that the
66  // resulting PHI node will have multiple values (from each load) coming in
67  // from the same block, which is illegal SSA form. For this reason, we
68  // keep track of and reuse loads we insert.
70  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
71  if (PN->getIncomingValue(i) == &I) {
72  Value *&V = Loads[PN->getIncomingBlock(i)];
73  if (!V) {
74  // Insert the load into the predecessor block
75  V = new LoadInst(I.getType(), Slot, I.getName() + ".reload",
76  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(I.getType(), Slot, I.getName() + ".reload",
85  VolatileLoads, U);
86  U->replaceUsesOfWith(&I, V);
87  }
88  }
89 
90  // Insert stores of the computed value into the stack slot. We have to be
91  // careful if I is an invoke instruction, because we can't insert the store
92  // AFTER the terminator instruction.
93  BasicBlock::iterator InsertPt;
94  if (!I.isTerminator()) {
95  InsertPt = ++I.getIterator();
96  for (; isa<PHINode>(InsertPt) || InsertPt->isEHPad(); ++InsertPt)
97  /* empty */; // Don't insert before PHI nodes or landingpad instrs.
98  } else {
99  InvokeInst &II = cast<InvokeInst>(I);
100  InsertPt = II.getNormalDest()->getFirstInsertionPt();
101  }
102 
103  new StoreInst(&I, Slot, &*InsertPt);
104  return Slot;
105 }
106 
107 /// DemotePHIToStack - This function takes a virtual register computed by a PHI
108 /// node and replaces it with a slot in the stack frame allocated via alloca.
109 /// The PHI node is deleted. It returns the pointer to the alloca inserted.
111  if (P->use_empty()) {
112  P->eraseFromParent();
113  return nullptr;
114  }
115 
116  const DataLayout &DL = P->getModule()->getDataLayout();
117 
118  // Create a stack slot to hold the value.
119  AllocaInst *Slot;
120  if (AllocaPoint) {
121  Slot = new AllocaInst(P->getType(), DL.getAllocaAddrSpace(), nullptr,
122  P->getName()+".reg2mem", AllocaPoint);
123  } else {
124  Function *F = P->getParent()->getParent();
125  Slot = new AllocaInst(P->getType(), DL.getAllocaAddrSpace(), nullptr,
126  P->getName() + ".reg2mem",
127  &F->getEntryBlock().front());
128  }
129 
130  // Iterate over each operand inserting a store in each predecessor.
131  for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
132  if (InvokeInst *II = dyn_cast<InvokeInst>(P->getIncomingValue(i))) {
133  assert(II->getParent() != P->getIncomingBlock(i) &&
134  "Invoke edge not supported yet"); (void)II;
135  }
136  new StoreInst(P->getIncomingValue(i), Slot,
138  }
139 
140  // Insert a load in place of the PHI and replace all uses.
141  BasicBlock::iterator InsertPt = P->getIterator();
142 
143  for (; isa<PHINode>(InsertPt) || InsertPt->isEHPad(); ++InsertPt)
144  /* empty */; // Don't insert before PHI nodes or landingpad instrs.
145 
146  Value *V =
147  new LoadInst(P->getType(), Slot, P->getName() + ".reload", &*InsertPt);
148  P->replaceAllUsesWith(V);
149 
150  // Delete PHI.
151  P->eraseFromParent();
152  return Slot;
153 }
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
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 ...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool isTerminator() const
Definition: Instruction.h:128
F(f)
An instruction for reading from memory.
Definition: Instructions.h:167
const Instruction * 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:137
unsigned getAllocaAddrSpace() const
Definition: DataLayout.h:269
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
BasicBlock * SplitCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
If this edge is a critical edge, insert a new node to split the critical edge.
An instruction for storing to memory.
Definition: Instructions.h:320
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:20
const BasicBlock & getEntryBlock() const
Definition: Function.h:639
#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:216
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
const Instruction & front() const
Definition: BasicBlock.h:280
self_iterator getIterator()
Definition: ilist_node.h:81
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
Definition: CFG.cpp:87
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:55
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:71
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
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:106
#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:565
LLVM Value Representation.
Definition: Value.h:72
Invoke instruction.
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:59