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/DataLayout.h"
12#include "llvm/IR/Function.h"
13#include "llvm/IR/Instructions.h"
14#include "llvm/Transforms/Utils/BasicBlockUtils.h"
15#include "llvm/Transforms/Utils/Local.h"
16using 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.
23AllocaInst *llvm::DemoteRegToStack(Instruction &I, bool VolatileLoads,
24 std::optional<BasicBlock::iterator> 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->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().begin());
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>(Val: &I)) {
47 if (!II->getNormalDest()->getSinglePredecessor()) {
48 unsigned SuccNum = GetSuccessorNumber(BB: II->getParent(), Succ: II->getNormalDest());
49 assert(isCriticalEdge(II, SuccNum) && "Expected a critical edge!");
50 BasicBlock *BB = SplitCriticalEdge(TI: II, SuccNum);
51 assert(BB && "Unable to split critical edge.");
52 (void)BB;
53 }
54 } else if (CallBrInst *CBI = dyn_cast<CallBrInst>(Val: &I)) {
55 for (unsigned i = 0; i < CBI->getNumSuccessors(); i++) {
56 auto *Succ = CBI->getSuccessor(i);
57 if (!Succ->getSinglePredecessor()) {
58 assert(isCriticalEdge(CBI, i) && "Expected a critical edge!");
59 [[maybe_unused]] BasicBlock *BB = SplitCriticalEdge(TI: CBI, SuccNum: i);
60 assert(BB && "Unable to split critical edge.");
61 }
62 }
63 }
64
65 // Change all of the users of the instruction to read from the stack slot.
66 while (!I.use_empty()) {
67 Instruction *U = cast<Instruction>(Val: I.user_back());
68 if (PHINode *PN = dyn_cast<PHINode>(Val: U)) {
69 // If this is a PHI node, we can't insert a load of the value before the
70 // use. Instead insert the load in the predecessor block corresponding
71 // to the incoming value.
72 //
73 // Note that if there are multiple edges from a basic block to this PHI
74 // node that we cannot have multiple loads. The problem is that the
75 // resulting PHI node will have multiple values (from each load) coming in
76 // from the same block, which is illegal SSA form. For this reason, we
77 // keep track of and reuse loads we insert.
78 DenseMap<BasicBlock*, Value*> Loads;
79 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
80 if (PN->getIncomingValue(i) == &I) {
81 Value *&V = Loads[PN->getIncomingBlock(i)];
82 if (!V) {
83 // Insert the load into the predecessor block
84 V = new LoadInst(I.getType(), Slot, I.getName() + ".reload",
85 VolatileLoads,
86 PN->getIncomingBlock(i)->getTerminator()->getIterator());
87 Loads[PN->getIncomingBlock(i)] = V;
88 }
89 PN->setIncomingValue(i, V);
90 }
91
92 } else {
93 // If this is a normal instruction, just insert a load.
94 Value *V = new LoadInst(I.getType(), Slot, I.getName() + ".reload",
95 VolatileLoads, U->getIterator());
96 U->replaceUsesOfWith(From: &I, To: V);
97 }
98 }
99
100 // Insert stores of the computed value into the stack slot. We have to be
101 // careful if I is an invoke instruction, because we can't insert the store
102 // AFTER the terminator instruction.
103 BasicBlock::iterator InsertPt;
104 if (!I.isTerminator()) {
105 InsertPt = ++I.getIterator();
106 // Don't insert before PHI nodes or landingpad instrs.
107 for (; isa<PHINode>(Val: InsertPt) || InsertPt->isEHPad(); ++InsertPt)
108 if (isa<CatchSwitchInst>(Val: InsertPt))
109 break;
110 if (isa<CatchSwitchInst>(Val: InsertPt)) {
111 for (BasicBlock *Handler : successors(I: &*InsertPt))
112 new StoreInst(&I, Slot, Handler->getFirstInsertionPt());
113 return Slot;
114 }
115 } else if (InvokeInst *II = dyn_cast<InvokeInst>(Val: &I)) {
116 InsertPt = II->getNormalDest()->getFirstInsertionPt();
117 } else if (CallBrInst *CBI = dyn_cast<CallBrInst>(Val: &I)) {
118 for (BasicBlock *Succ : successors(I: CBI))
119 new StoreInst(CBI, Slot, Succ->getFirstInsertionPt());
120 return Slot;
121 } else {
122 llvm_unreachable("Unsupported terminator for Reg2Mem");
123 }
124
125 new StoreInst(&I, Slot, InsertPt);
126 return Slot;
127}
128
129/// DemotePHIToStack - This function takes a virtual register computed by a PHI
130/// node and replaces it with a slot in the stack frame allocated via alloca.
131/// The PHI node is deleted. It returns the pointer to the alloca inserted.
132AllocaInst *llvm::DemotePHIToStack(PHINode *P, std::optional<BasicBlock::iterator> AllocaPoint) {
133 if (P->use_empty()) {
134 P->eraseFromParent();
135 return nullptr;
136 }
137
138 const DataLayout &DL = P->getDataLayout();
139
140 // Create a stack slot to hold the value.
141 AllocaInst *Slot;
142 if (AllocaPoint) {
143 Slot = new AllocaInst(P->getType(), DL.getAllocaAddrSpace(), nullptr,
144 P->getName()+".reg2mem", *AllocaPoint);
145 } else {
146 Function *F = P->getParent()->getParent();
147 Slot = new AllocaInst(P->getType(), DL.getAllocaAddrSpace(), nullptr,
148 P->getName() + ".reg2mem",
149 F->getEntryBlock().begin());
150 }
151
152 // Iterate over each operand inserting a store in each predecessor.
153 for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
154 if (InvokeInst *II = dyn_cast<InvokeInst>(Val: P->getIncomingValue(i))) {
155 assert(II->getParent() != P->getIncomingBlock(i) &&
156 "Invoke edge not supported yet"); (void)II;
157 }
158 new StoreInst(P->getIncomingValue(i), Slot,
159 P->getIncomingBlock(i)->getTerminator()->getIterator());
160 }
161
162 // Insert a load in place of the PHI and replace all uses.
163 BasicBlock::iterator InsertPt = P->getIterator();
164 // Don't insert before PHI nodes or landingpad instrs.
165 for (; isa<PHINode>(Val: InsertPt) || InsertPt->isEHPad(); ++InsertPt)
166 if (isa<CatchSwitchInst>(Val: InsertPt))
167 break;
168 if (isa<CatchSwitchInst>(Val: InsertPt)) {
169 // We need a separate load before each actual use of the PHI
170 SmallVector<Instruction *, 4> Users;
171 for (User *U : P->users()) {
172 Instruction *User = cast<Instruction>(Val: U);
173 Users.push_back(Elt: User);
174 }
175 for (Instruction *User : Users) {
176 Value *V =
177 new LoadInst(P->getType(), Slot, P->getName() + ".reload", User->getIterator());
178 User->replaceUsesOfWith(From: P, To: V);
179 }
180 } else {
181 Value *V =
182 new LoadInst(P->getType(), Slot, P->getName() + ".reload", InsertPt);
183 P->replaceAllUsesWith(V);
184 }
185 // Delete PHI.
186 P->eraseFromParent();
187 return Slot;
188}
189