LLVM  15.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"
11 #include "llvm/IR/Function.h"
12 #include "llvm/IR/Instructions.h"
15 using 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.
23  Instruction *AllocaPoint) {
24  if (I.use_empty()) {
25  I.eraseFromParent();
26  return nullptr;
27  }
28 
29  Function *F = I.getParent()->getParent();
30  const DataLayout &DL = F->getParent()->getDataLayout();
31 
32  // Create a stack slot to hold the value.
33  AllocaInst *Slot;
34  if (AllocaPoint) {
35  Slot = new AllocaInst(I.getType(), DL.getAllocaAddrSpace(), nullptr,
36  I.getName()+".reg2mem", AllocaPoint);
37  } else {
38  Slot = new AllocaInst(I.getType(), DL.getAllocaAddrSpace(), nullptr,
39  I.getName() + ".reg2mem", &F->getEntryBlock().front());
40  }
41 
42  // We cannot demote invoke instructions to the stack if their normal edge
43  // is critical. Therefore, split the critical edge and create a basic block
44  // into which the store can be inserted.
45  if (InvokeInst *II = dyn_cast<InvokeInst>(&I)) {
46  if (!II->getNormalDest()->getSinglePredecessor()) {
47  unsigned SuccNum = GetSuccessorNumber(II->getParent(), II->getNormalDest());
48  assert(isCriticalEdge(II, SuccNum) && "Expected a critical edge!");
49  BasicBlock *BB = SplitCriticalEdge(II, SuccNum);
50  assert(BB && "Unable to split critical edge.");
51  (void)BB;
52  }
53  }
54 
55  // Change all of the users of the instruction to read from the stack slot.
56  while (!I.use_empty()) {
57  Instruction *U = cast<Instruction>(I.user_back());
58  if (PHINode *PN = dyn_cast<PHINode>(U)) {
59  // If this is a PHI node, we can't insert a load of the value before the
60  // use. Instead insert the load in the predecessor block corresponding
61  // to the incoming value.
62  //
63  // Note that if there are multiple edges from a basic block to this PHI
64  // node that we cannot have multiple loads. The problem is that the
65  // resulting PHI node will have multiple values (from each load) coming in
66  // from the same block, which is illegal SSA form. For this reason, we
67  // keep track of and reuse loads we insert.
69  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
70  if (PN->getIncomingValue(i) == &I) {
71  Value *&V = Loads[PN->getIncomingBlock(i)];
72  if (!V) {
73  // Insert the load into the predecessor block
74  V = new LoadInst(I.getType(), Slot, I.getName() + ".reload",
75  VolatileLoads,
76  PN->getIncomingBlock(i)->getTerminator());
77  }
78  PN->setIncomingValue(i, V);
79  }
80 
81  } else {
82  // If this is a normal instruction, just insert a load.
83  Value *V = new LoadInst(I.getType(), Slot, I.getName() + ".reload",
84  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 (!I.isTerminator()) {
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,
136  P->getIncomingBlock(i)->getTerminator());
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 =
146  new LoadInst(P->getType(), Slot, P->getName() + ".reload", &*InsertPt);
147  P->replaceAllUsesWith(V);
148 
149  // Delete PHI.
150  P->eraseFromParent();
151  return Slot;
152 }
i
i
Definition: README.txt:29
llvm::InvokeInst::getNormalDest
BasicBlock * getNormalDest() const
Definition: Instructions.h:3895
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:87
llvm::Function
Definition: Function.h:60
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:101
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:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
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:109
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:246
llvm::Instruction
Definition: Instruction.h:42
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3763
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:297
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:716
I
#define I(x, y, z)
Definition: MD5.cpp:58
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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:22
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:173
llvm::User::replaceUsesOfWith
bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:21
Function.h
Instructions.h
llvm::PHINode
Definition: Instructions.h:2651
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:58
BasicBlockUtils.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74