LLVM  14.0.0git
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,
137  P->getIncomingBlock(i)->getTerminator());
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 }
i
i
Definition: README.txt:29
llvm::InvokeInst::getNormalDest
BasicBlock * getNormalDest() const
Definition: Instructions.h:3881
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
llvm::Function
Definition: Function.h:62
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Local.h
DenseMap.h
llvm::SplitCriticalEdge
BasicBlock * SplitCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
If this edge is a critical edge, insert a new node to split the critical edge.
Definition: BreakCriticalEdges.cpp:103
llvm::isCriticalEdge
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
Definition: CFG.cpp:95
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::DemotePHIToStack
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...
Definition: DemoteRegToStack.cpp:110
llvm::BasicBlock::getFirstInsertionPt
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:253
llvm::Instruction
Definition: Instruction.h:45
Type.h
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3749
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:304
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::User::replaceUsesOfWith
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:21
llvm::GetSuccessorNumber
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:79
CFG.h
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::DemoteRegToStack
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 ...
Definition: DemoteRegToStack.cpp:23
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:175
Function.h
Instructions.h
llvm::PHINode
Definition: Instructions.h:2633
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:62
BasicBlockUtils.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75