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" |
13 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
14 | #include "llvm/Transforms/Utils/Local.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. |
22 | AllocaInst *llvm::DemoteRegToStack(Instruction &I, bool VolatileLoads, |
23 | std::optional<BasicBlock::iterator> 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().begin()); |
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>(Val: &I)) { |
46 | if (!II->getNormalDest()->getSinglePredecessor()) { |
47 | unsigned SuccNum = GetSuccessorNumber(BB: II->getParent(), Succ: II->getNormalDest()); |
48 | assert(isCriticalEdge(II, SuccNum) && "Expected a critical edge!" ); |
49 | BasicBlock *BB = SplitCriticalEdge(TI: 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>(Val: I.user_back()); |
58 | if (PHINode *PN = dyn_cast<PHINode>(Val: 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. |
68 | DenseMap<BasicBlock*, Value*> Loads; |
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()->getIterator()); |
77 | Loads[PN->getIncomingBlock(i)] = V; |
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->getIterator()); |
86 | U->replaceUsesOfWith(From: &I, To: 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 | // Don't insert before PHI nodes or landingpad instrs. |
97 | for (; isa<PHINode>(Val: InsertPt) || InsertPt->isEHPad(); ++InsertPt) |
98 | if (isa<CatchSwitchInst>(Val: InsertPt)) |
99 | break; |
100 | if (isa<CatchSwitchInst>(Val: InsertPt)) { |
101 | for (BasicBlock *Handler : successors(I: &*InsertPt)) |
102 | new StoreInst(&I, Slot, Handler->getFirstInsertionPt()); |
103 | return Slot; |
104 | } |
105 | } else { |
106 | InvokeInst &II = cast<InvokeInst>(Val&: I); |
107 | InsertPt = II.getNormalDest()->getFirstInsertionPt(); |
108 | } |
109 | |
110 | new StoreInst(&I, Slot, InsertPt); |
111 | return Slot; |
112 | } |
113 | |
114 | /// DemotePHIToStack - This function takes a virtual register computed by a PHI |
115 | /// node and replaces it with a slot in the stack frame allocated via alloca. |
116 | /// The PHI node is deleted. It returns the pointer to the alloca inserted. |
117 | AllocaInst *llvm::DemotePHIToStack(PHINode *P, std::optional<BasicBlock::iterator> AllocaPoint) { |
118 | if (P->use_empty()) { |
119 | P->eraseFromParent(); |
120 | return nullptr; |
121 | } |
122 | |
123 | const DataLayout &DL = P->getModule()->getDataLayout(); |
124 | |
125 | // Create a stack slot to hold the value. |
126 | AllocaInst *Slot; |
127 | if (AllocaPoint) { |
128 | Slot = new AllocaInst(P->getType(), DL.getAllocaAddrSpace(), nullptr, |
129 | P->getName()+".reg2mem" , *AllocaPoint); |
130 | } else { |
131 | Function *F = P->getParent()->getParent(); |
132 | Slot = new AllocaInst(P->getType(), DL.getAllocaAddrSpace(), nullptr, |
133 | P->getName() + ".reg2mem" , |
134 | F->getEntryBlock().begin()); |
135 | } |
136 | |
137 | // Iterate over each operand inserting a store in each predecessor. |
138 | for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) { |
139 | if (InvokeInst *II = dyn_cast<InvokeInst>(Val: P->getIncomingValue(i))) { |
140 | assert(II->getParent() != P->getIncomingBlock(i) && |
141 | "Invoke edge not supported yet" ); (void)II; |
142 | } |
143 | new StoreInst(P->getIncomingValue(i), Slot, |
144 | P->getIncomingBlock(i)->getTerminator()->getIterator()); |
145 | } |
146 | |
147 | // Insert a load in place of the PHI and replace all uses. |
148 | BasicBlock::iterator InsertPt = P->getIterator(); |
149 | // Don't insert before PHI nodes or landingpad instrs. |
150 | for (; isa<PHINode>(Val: InsertPt) || InsertPt->isEHPad(); ++InsertPt) |
151 | if (isa<CatchSwitchInst>(Val: InsertPt)) |
152 | break; |
153 | if (isa<CatchSwitchInst>(Val: InsertPt)) { |
154 | // We need a separate load before each actual use of the PHI |
155 | SmallVector<Instruction *, 4> Users; |
156 | for (User *U : P->users()) { |
157 | Instruction *User = cast<Instruction>(Val: U); |
158 | Users.push_back(Elt: User); |
159 | } |
160 | for (Instruction *User : Users) { |
161 | Value *V = |
162 | new LoadInst(P->getType(), Slot, P->getName() + ".reload" , User->getIterator()); |
163 | User->replaceUsesOfWith(From: P, To: V); |
164 | } |
165 | } else { |
166 | Value *V = |
167 | new LoadInst(P->getType(), Slot, P->getName() + ".reload" , InsertPt); |
168 | P->replaceAllUsesWith(V); |
169 | } |
170 | // Delete PHI. |
171 | P->eraseFromParent(); |
172 | return Slot; |
173 | } |
174 | |