DemoteRegToStack.cpp revision dce4a407a24b04eebc6a376f8e62b41aaa7b071f
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===- DemoteRegToStack.cpp - Move a virtual register to the stack --------===// 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The LLVM Compiler Infrastructure 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file is distributed under the University of Illinois Open Source 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// License. See LICENSE.TXT for details. 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Transforms/Utils/BasicBlockUtils.h" 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/ADT/DenseMap.h" 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Analysis/CFG.h" 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/IR/Function.h" 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/IR/Instructions.h" 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/IR/Type.h" 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/Transforms/Utils/Local.h" 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using namespace llvm; 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// DemoteRegToStack - This function takes a virtual register computed by an 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// Instruction and replaces it with a slot in the stack frame, allocated via 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// alloca. This allows the CFG to be changed around without fear of 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// invalidating the SSA information for the value. It returns the pointer to 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// the alloca inserted to create a stack slot for I. 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)AllocaInst *llvm::DemoteRegToStack(Instruction &I, bool VolatileLoads, 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *AllocaPoint) { 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (I.use_empty()) { 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) I.eraseFromParent(); 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return nullptr; 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Create a stack slot to hold the value. 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AllocaInst *Slot; 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (AllocaPoint) { 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Slot = new AllocaInst(I.getType(), nullptr, 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) I.getName()+".reg2mem", AllocaPoint); 362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } else { 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Function *F = I.getParent()->getParent(); 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Slot = new AllocaInst(I.getType(), nullptr, I.getName()+".reg2mem", 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) F->getEntryBlock().begin()); 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Change all of the users of the instruction to read from the stack slot. 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (!I.use_empty()) { 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Instruction *U = cast<Instruction>(I.user_back()); 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (PHINode *PN = dyn_cast<PHINode>(U)) { 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If this is a PHI node, we can't insert a load of the value before the 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // use. Instead insert the load in the predecessor block corresponding 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // to the incoming value. 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Note that if there are multiple edges from a basic block to this PHI 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // node that we cannot have multiple loads. The problem is that the 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // resulting PHI node will have multiple values (from each load) coming in 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // from the same block, which is illegal SSA form. For this reason, we 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // keep track of and reuse loads we insert. 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DenseMap<BasicBlock*, Value*> Loads; 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (PN->getIncomingValue(i) == &I) { 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Value *&V = Loads[PN->getIncomingBlock(i)]; 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!V) { 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Insert the load into the predecessor block 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads, 6290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) PN->getIncomingBlock(i)->getTerminator()); 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PN->setIncomingValue(i, V); 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If this is a normal instruction, just insert a load. 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Value *V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads, U); 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) U->replaceUsesOfWith(&I, V); 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Insert stores of the computed value into the stack slot. We have to be 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // careful if I is an invoke instruction, because we can't insert the store 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // AFTER the terminator instruction. 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BasicBlock::iterator InsertPt; 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!isa<TerminatorInst>(I)) { 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) InsertPt = &I; 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++InsertPt; 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) InvokeInst &II = cast<InvokeInst>(I); 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (II.getNormalDest()->getSinglePredecessor()) 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) InsertPt = II.getNormalDest()->getFirstInsertionPt(); 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else { 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We cannot demote invoke instructions to the stack if their normal edge 8890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // is critical. Therefore, split the critical edge and insert the store 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // in the newly created basic block. 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned SuccNum = GetSuccessorNumber(I.getParent(), II.getNormalDest()); 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TerminatorInst *TI = &cast<TerminatorInst>(I); 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert (isCriticalEdge(TI, SuccNum) && 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "Expected a critical edge!"); 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BasicBlock *BB = SplitCriticalEdge(TI, SuccNum); 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert (BB && "Unable to split critical edge."); 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) InsertPt = BB->getFirstInsertionPt(); 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (; isa<PHINode>(InsertPt) || isa<LandingPadInst>(InsertPt); ++InsertPt) 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* empty */; // Don't insert before PHI nodes or landingpad instrs. 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new StoreInst(&I, Slot, InsertPt); 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Slot; 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// DemotePHIToStack - This function takes a virtual register computed by a PHI 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// node and replaces it with a slot in the stack frame allocated via alloca. 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// The PHI node is deleted. It returns the pointer to the alloca inserted. 11090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)AllocaInst *llvm::DemotePHIToStack(PHINode *P, Instruction *AllocaPoint) { 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (P->use_empty()) { 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) P->eraseFromParent(); 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return nullptr; 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Create a stack slot to hold the value. 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AllocaInst *Slot; 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (AllocaPoint) { 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Slot = new AllocaInst(P->getType(), nullptr, 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) P->getName()+".reg2mem", AllocaPoint); 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Function *F = P->getParent()->getParent(); 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Slot = new AllocaInst(P->getType(), nullptr, P->getName()+".reg2mem", 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) F->getEntryBlock().begin()); 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Iterate over each operand inserting a store in each predecessor. 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) { 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (InvokeInst *II = dyn_cast<InvokeInst>(P->getIncomingValue(i))) { 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(II->getParent() != P->getIncomingBlock(i) && 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "Invoke edge not supported yet"); (void)II; 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new StoreInst(P->getIncomingValue(i), Slot, 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) P->getIncomingBlock(i)->getTerminator()); 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Insert a load in place of the PHI and replace all uses. 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BasicBlock::iterator InsertPt = P; 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (; isa<PHINode>(InsertPt) || isa<LandingPadInst>(InsertPt); ++InsertPt) 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* empty */; // Don't insert before PHI nodes or landingpad instrs. 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Value *V = new LoadInst(Slot, P->getName()+".reload", InsertPt); 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) P->replaceAllUsesWith(V); 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Delete PHI. 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) P->eraseFromParent(); 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Slot; 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)