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 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. 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()); 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); 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 // Don't insert before PHI nodes or landingpad instrs. 97 for (; isa<PHINode>(InsertPt) || InsertPt->isEHPad(); ++InsertPt) 98 if (isa<CatchSwitchInst>(InsertPt)) 99 break; 100 if (isa<CatchSwitchInst>(InsertPt)) { 101 for (BasicBlock *Handler : successors(&*InsertPt)) 102 new StoreInst(&I, Slot, &*Handler->getFirstInsertionPt()); 103 return Slot; 104 } 105 } else { 106 InvokeInst &II = cast<InvokeInst>(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, Instruction *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().front()); 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>(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()); 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>(InsertPt) || InsertPt->isEHPad(); ++InsertPt) 151 if (isa<CatchSwitchInst>(InsertPt)) 152 break; 153 if (isa<CatchSwitchInst>(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>(U); 158 Users.push_back(User); 159 } 160 for (Instruction *User : Users) { 161 Value *V = 162 new LoadInst(P->getType(), Slot, P->getName() + ".reload", User); 163 User->replaceUsesOfWith(P, 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