1193323Sed//===- DemoteRegToStack.cpp - Move a virtual register to the stack --------===// 2193323Sed// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6193323Sed// 7193323Sed//===----------------------------------------------------------------------===// 8193323Sed 9234353Sdim#include "llvm/ADT/DenseMap.h" 10261991Sdim#include "llvm/Analysis/CFG.h" 11341825Sdim#include "llvm/Transforms/Utils/Local.h" 12249423Sdim#include "llvm/IR/Function.h" 13249423Sdim#include "llvm/IR/Instructions.h" 14249423Sdim#include "llvm/IR/Type.h" 15321369Sdim#include "llvm/Transforms/Utils/BasicBlockUtils.h" 16193323Sedusing namespace llvm; 17193323Sed 18193323Sed/// DemoteRegToStack - This function takes a virtual register computed by an 19193323Sed/// Instruction and replaces it with a slot in the stack frame, allocated via 20193323Sed/// alloca. This allows the CFG to be changed around without fear of 21193323Sed/// invalidating the SSA information for the value. It returns the pointer to 22193323Sed/// the alloca inserted to create a stack slot for I. 23234353SdimAllocaInst *llvm::DemoteRegToStack(Instruction &I, bool VolatileLoads, 24193323Sed Instruction *AllocaPoint) { 25193323Sed if (I.use_empty()) { 26193323Sed I.eraseFromParent(); 27276479Sdim return nullptr; 28193323Sed } 29210299Sed 30321369Sdim Function *F = I.getParent()->getParent(); 31321369Sdim const DataLayout &DL = F->getParent()->getDataLayout(); 32321369Sdim 33193323Sed // Create a stack slot to hold the value. 34193323Sed AllocaInst *Slot; 35193323Sed if (AllocaPoint) { 36321369Sdim Slot = new AllocaInst(I.getType(), DL.getAllocaAddrSpace(), nullptr, 37198090Srdivacky I.getName()+".reg2mem", AllocaPoint); 38193323Sed } else { 39321369Sdim Slot = new AllocaInst(I.getType(), DL.getAllocaAddrSpace(), nullptr, 40321369Sdim I.getName() + ".reg2mem", &F->getEntryBlock().front()); 41193323Sed } 42210299Sed 43288943Sdim // We cannot demote invoke instructions to the stack if their normal edge 44288943Sdim // is critical. Therefore, split the critical edge and create a basic block 45288943Sdim // into which the store can be inserted. 46288943Sdim if (InvokeInst *II = dyn_cast<InvokeInst>(&I)) { 47288943Sdim if (!II->getNormalDest()->getSinglePredecessor()) { 48288943Sdim unsigned SuccNum = GetSuccessorNumber(II->getParent(), II->getNormalDest()); 49288943Sdim assert(isCriticalEdge(II, SuccNum) && "Expected a critical edge!"); 50288943Sdim BasicBlock *BB = SplitCriticalEdge(II, SuccNum); 51288943Sdim assert(BB && "Unable to split critical edge."); 52288943Sdim (void)BB; 53288943Sdim } 54288943Sdim } 55288943Sdim 56234353Sdim // Change all of the users of the instruction to read from the stack slot. 57193323Sed while (!I.use_empty()) { 58276479Sdim Instruction *U = cast<Instruction>(I.user_back()); 59193323Sed if (PHINode *PN = dyn_cast<PHINode>(U)) { 60193323Sed // If this is a PHI node, we can't insert a load of the value before the 61234353Sdim // use. Instead insert the load in the predecessor block corresponding 62193323Sed // to the incoming value. 63193323Sed // 64193323Sed // Note that if there are multiple edges from a basic block to this PHI 65234353Sdim // node that we cannot have multiple loads. The problem is that the 66234353Sdim // resulting PHI node will have multiple values (from each load) coming in 67234353Sdim // from the same block, which is illegal SSA form. For this reason, we 68234353Sdim // keep track of and reuse loads we insert. 69234353Sdim DenseMap<BasicBlock*, Value*> Loads; 70193323Sed for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 71193323Sed if (PN->getIncomingValue(i) == &I) { 72193323Sed Value *&V = Loads[PN->getIncomingBlock(i)]; 73276479Sdim if (!V) { 74193323Sed // Insert the load into the predecessor block 75353358Sdim V = new LoadInst(I.getType(), Slot, I.getName() + ".reload", 76353358Sdim VolatileLoads, 77193323Sed PN->getIncomingBlock(i)->getTerminator()); 78193323Sed } 79193323Sed PN->setIncomingValue(i, V); 80193323Sed } 81193323Sed 82193323Sed } else { 83193323Sed // If this is a normal instruction, just insert a load. 84353358Sdim Value *V = new LoadInst(I.getType(), Slot, I.getName() + ".reload", 85353358Sdim VolatileLoads, U); 86193323Sed U->replaceUsesOfWith(&I, V); 87193323Sed } 88193323Sed } 89193323Sed 90234353Sdim // Insert stores of the computed value into the stack slot. We have to be 91234353Sdim // careful if I is an invoke instruction, because we can't insert the store 92234353Sdim // AFTER the terminator instruction. 93193323Sed BasicBlock::iterator InsertPt; 94344779Sdim if (!I.isTerminator()) { 95296417Sdim InsertPt = ++I.getIterator(); 96296417Sdim for (; isa<PHINode>(InsertPt) || InsertPt->isEHPad(); ++InsertPt) 97288943Sdim /* empty */; // Don't insert before PHI nodes or landingpad instrs. 98193323Sed } else { 99193323Sed InvokeInst &II = cast<InvokeInst>(I); 100288943Sdim InsertPt = II.getNormalDest()->getFirstInsertionPt(); 101193323Sed } 102193323Sed 103296417Sdim new StoreInst(&I, Slot, &*InsertPt); 104193323Sed return Slot; 105193323Sed} 106193323Sed 107234353Sdim/// DemotePHIToStack - This function takes a virtual register computed by a PHI 108234353Sdim/// node and replaces it with a slot in the stack frame allocated via alloca. 109234353Sdim/// The PHI node is deleted. It returns the pointer to the alloca inserted. 110234353SdimAllocaInst *llvm::DemotePHIToStack(PHINode *P, Instruction *AllocaPoint) { 111193323Sed if (P->use_empty()) { 112210299Sed P->eraseFromParent(); 113276479Sdim return nullptr; 114193323Sed } 115193323Sed 116321369Sdim const DataLayout &DL = P->getModule()->getDataLayout(); 117321369Sdim 118193323Sed // Create a stack slot to hold the value. 119193323Sed AllocaInst *Slot; 120193323Sed if (AllocaPoint) { 121321369Sdim Slot = new AllocaInst(P->getType(), DL.getAllocaAddrSpace(), nullptr, 122198090Srdivacky P->getName()+".reg2mem", AllocaPoint); 123193323Sed } else { 124193323Sed Function *F = P->getParent()->getParent(); 125321369Sdim Slot = new AllocaInst(P->getType(), DL.getAllocaAddrSpace(), nullptr, 126321369Sdim P->getName() + ".reg2mem", 127296417Sdim &F->getEntryBlock().front()); 128193323Sed } 129210299Sed 130234353Sdim // Iterate over each operand inserting a store in each predecessor. 131193323Sed for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) { 132193323Sed if (InvokeInst *II = dyn_cast<InvokeInst>(P->getIncomingValue(i))) { 133210299Sed assert(II->getParent() != P->getIncomingBlock(i) && 134218893Sdim "Invoke edge not supported yet"); (void)II; 135193323Sed } 136210299Sed new StoreInst(P->getIncomingValue(i), Slot, 137193323Sed P->getIncomingBlock(i)->getTerminator()); 138193323Sed } 139210299Sed 140234353Sdim // Insert a load in place of the PHI and replace all uses. 141296417Sdim BasicBlock::iterator InsertPt = P->getIterator(); 142249423Sdim 143296417Sdim for (; isa<PHINode>(InsertPt) || InsertPt->isEHPad(); ++InsertPt) 144249423Sdim /* empty */; // Don't insert before PHI nodes or landingpad instrs. 145249423Sdim 146353358Sdim Value *V = 147353358Sdim new LoadInst(P->getType(), Slot, P->getName() + ".reload", &*InsertPt); 148193323Sed P->replaceAllUsesWith(V); 149210299Sed 150234353Sdim // Delete PHI. 151193323Sed P->eraseFromParent(); 152193323Sed return Slot; 153193323Sed} 154