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