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 } 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. 109 AllocaInst *llvm::DemotePHIToStack(PHINode *P, Instruction *AllocaPoint) { 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 } 153