10c7e8e17ff602d473d9ea0f91b246365dcc6fe30Chris Lattner//===- DemoteRegToStack.cpp - Move a virtual register to the stack --------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 983e3b6503d775e98cc85fb881419d1c23b75cde2Vikram S. Adve 10a2dc727ac4d3cd6d6826140e33eb7b54f074b9d7Chris Lattner#include "llvm/Transforms/Utils/Local.h" 1183e3b6503d775e98cc85fb881419d1c23b75cde2Vikram S. Adve#include "llvm/Function.h" 12c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner#include "llvm/Instructions.h" 135b3a4553c1da7e417a240379e2f510c77532c5c1Chris Lattner#include "llvm/Type.h" 143106b8b18b6fbeb77ac3f76b7179e2569bbffef9Bill Wendling#include "llvm/ADT/DenseMap.h" 15f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 16d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 17c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner/// DemoteRegToStack - This function takes a virtual register computed by an 18c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner/// Instruction and replaces it with a slot in the stack frame, allocated via 19c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner/// alloca. This allows the CFG to be changed around without fear of 20c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner/// invalidating the SSA information for the value. It returns the pointer to 21c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner/// the alloca inserted to create a stack slot for I. 223106b8b18b6fbeb77ac3f76b7179e2569bbffef9Bill WendlingAllocaInst *llvm::DemoteRegToStack(Instruction &I, bool VolatileLoads, 23a024e8cedab928403818ac79e899cdae2a356c56Anton Korobeynikov Instruction *AllocaPoint) { 24a024e8cedab928403818ac79e899cdae2a356c56Anton Korobeynikov if (I.use_empty()) { 25a024e8cedab928403818ac79e899cdae2a356c56Anton Korobeynikov I.eraseFromParent(); 26a024e8cedab928403818ac79e899cdae2a356c56Anton Korobeynikov return 0; 27a024e8cedab928403818ac79e899cdae2a356c56Anton Korobeynikov } 28d0e8469ba65c54b593df15b7249d7fe12097c4cfJim Grosbach 29c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // Create a stack slot to hold the value. 30a024e8cedab928403818ac79e899cdae2a356c56Anton Korobeynikov AllocaInst *Slot; 31a024e8cedab928403818ac79e899cdae2a356c56Anton Korobeynikov if (AllocaPoint) { 3250dead06ffc107edb7e84857baaeeb09039c631cOwen Anderson Slot = new AllocaInst(I.getType(), 0, 339adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson I.getName()+".reg2mem", AllocaPoint); 34a024e8cedab928403818ac79e899cdae2a356c56Anton Korobeynikov } else { 35a024e8cedab928403818ac79e899cdae2a356c56Anton Korobeynikov Function *F = I.getParent()->getParent(); 3650dead06ffc107edb7e84857baaeeb09039c631cOwen Anderson Slot = new AllocaInst(I.getType(), 0, I.getName()+".reg2mem", 37a024e8cedab928403818ac79e899cdae2a356c56Anton Korobeynikov F->getEntryBlock().begin()); 38a024e8cedab928403818ac79e899cdae2a356c56Anton Korobeynikov } 39d0e8469ba65c54b593df15b7249d7fe12097c4cfJim Grosbach 401bc147b892b4b881a020a3fb706c5415ef244730Bill Wendling // Change all of the users of the instruction to read from the stack slot. 41c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner while (!I.use_empty()) { 42c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner Instruction *U = cast<Instruction>(I.use_back()); 43c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner if (PHINode *PN = dyn_cast<PHINode>(U)) { 44c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // If this is a PHI node, we can't insert a load of the value before the 451bc147b892b4b881a020a3fb706c5415ef244730Bill Wendling // use. Instead insert the load in the predecessor block corresponding 46c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // to the incoming value. 47c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // 48c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // Note that if there are multiple edges from a basic block to this PHI 491bc147b892b4b881a020a3fb706c5415ef244730Bill Wendling // node that we cannot have multiple loads. The problem is that the 501bc147b892b4b881a020a3fb706c5415ef244730Bill Wendling // resulting PHI node will have multiple values (from each load) coming in 511bc147b892b4b881a020a3fb706c5415ef244730Bill Wendling // from the same block, which is illegal SSA form. For this reason, we 521bc147b892b4b881a020a3fb706c5415ef244730Bill Wendling // keep track of and reuse loads we insert. 533106b8b18b6fbeb77ac3f76b7179e2569bbffef9Bill Wendling DenseMap<BasicBlock*, Value*> Loads; 54c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 55c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner if (PN->getIncomingValue(i) == &I) { 56c68bace452dbad23794d4b3c47eeebc00d489cefChris Lattner Value *&V = Loads[PN->getIncomingBlock(i)]; 57c68bace452dbad23794d4b3c47eeebc00d489cefChris Lattner if (V == 0) { 58c68bace452dbad23794d4b3c47eeebc00d489cefChris Lattner // Insert the load into the predecessor block 59d0e8469ba65c54b593df15b7249d7fe12097c4cfJim Grosbach V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads, 60c68bace452dbad23794d4b3c47eeebc00d489cefChris Lattner PN->getIncomingBlock(i)->getTerminator()); 61c68bace452dbad23794d4b3c47eeebc00d489cefChris Lattner } 62c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner PN->setIncomingValue(i, V); 63ab4536e3536fd46863a89fb4cecae9cb8ee21c68Chris Lattner } 64ab4536e3536fd46863a89fb4cecae9cb8ee21c68Chris Lattner 65c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner } else { 66c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // If this is a normal instruction, just insert a load. 676d7277b3b4c4847a39841cdac3e3fd29bd54fa85Chris Lattner Value *V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads, U); 68c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner U->replaceUsesOfWith(&I, V); 6983e3b6503d775e98cc85fb881419d1c23b75cde2Vikram S. Adve } 70ab4536e3536fd46863a89fb4cecae9cb8ee21c68Chris Lattner } 7183e3b6503d775e98cc85fb881419d1c23b75cde2Vikram S. Adve 7283e3b6503d775e98cc85fb881419d1c23b75cde2Vikram S. Adve 731bc147b892b4b881a020a3fb706c5415ef244730Bill Wendling // Insert stores of the computed value into the stack slot. We have to be 741bc147b892b4b881a020a3fb706c5415ef244730Bill Wendling // careful if I is an invoke instruction, because we can't insert the store 751bc147b892b4b881a020a3fb706c5415ef244730Bill Wendling // AFTER the terminator instruction. 766d7277b3b4c4847a39841cdac3e3fd29bd54fa85Chris Lattner BasicBlock::iterator InsertPt; 77c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner if (!isa<TerminatorInst>(I)) { 786d7277b3b4c4847a39841cdac3e3fd29bd54fa85Chris Lattner InsertPt = &I; 79ab55698349cd87aabc2f2af16f58e2408362f6eaChris Lattner ++InsertPt; 80c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner } else { 816d7277b3b4c4847a39841cdac3e3fd29bd54fa85Chris Lattner // We cannot demote invoke instructions to the stack if their normal edge 826d7277b3b4c4847a39841cdac3e3fd29bd54fa85Chris Lattner // is critical. 836d7277b3b4c4847a39841cdac3e3fd29bd54fa85Chris Lattner InvokeInst &II = cast<InvokeInst>(I); 846d7277b3b4c4847a39841cdac3e3fd29bd54fa85Chris Lattner assert(II.getNormalDest()->getSinglePredecessor() && 856d7277b3b4c4847a39841cdac3e3fd29bd54fa85Chris Lattner "Cannot demote invoke with a critical successor!"); 866d7277b3b4c4847a39841cdac3e3fd29bd54fa85Chris Lattner InsertPt = II.getNormalDest()->begin(); 87c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner } 880c7e8e17ff602d473d9ea0f91b246365dcc6fe30Chris Lattner 89ac101e584873d72715b4fc4d2e35e3ba0ec8217bBill Wendling for (; isa<PHINode>(InsertPt) || isa<LandingPadInst>(InsertPt); ++InsertPt) 901bc147b892b4b881a020a3fb706c5415ef244730Bill Wendling /* empty */; // Don't insert before PHI nodes or landingpad instrs. 916d7277b3b4c4847a39841cdac3e3fd29bd54fa85Chris Lattner 921bc147b892b4b881a020a3fb706c5415ef244730Bill Wendling new StoreInst(&I, Slot, InsertPt); 93c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner return Slot; 9483e3b6503d775e98cc85fb881419d1c23b75cde2Vikram S. Adve} 9508d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner 961bc147b892b4b881a020a3fb706c5415ef244730Bill Wendling/// DemotePHIToStack - This function takes a virtual register computed by a PHI 971bc147b892b4b881a020a3fb706c5415ef244730Bill Wendling/// node and replaces it with a slot in the stack frame allocated via alloca. 981bc147b892b4b881a020a3fb706c5415ef244730Bill Wendling/// The PHI node is deleted. It returns the pointer to the alloca inserted. 993106b8b18b6fbeb77ac3f76b7179e2569bbffef9Bill WendlingAllocaInst *llvm::DemotePHIToStack(PHINode *P, Instruction *AllocaPoint) { 10008d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner if (P->use_empty()) { 101d0e8469ba65c54b593df15b7249d7fe12097c4cfJim Grosbach P->eraseFromParent(); 102d0e8469ba65c54b593df15b7249d7fe12097c4cfJim Grosbach return 0; 10308d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner } 104a024e8cedab928403818ac79e899cdae2a356c56Anton Korobeynikov 10508d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner // Create a stack slot to hold the value. 106a024e8cedab928403818ac79e899cdae2a356c56Anton Korobeynikov AllocaInst *Slot; 107a024e8cedab928403818ac79e899cdae2a356c56Anton Korobeynikov if (AllocaPoint) { 10850dead06ffc107edb7e84857baaeeb09039c631cOwen Anderson Slot = new AllocaInst(P->getType(), 0, 1099adc0abad3c3ed40a268ccbcee0c74cb9e1359feOwen Anderson P->getName()+".reg2mem", AllocaPoint); 110a024e8cedab928403818ac79e899cdae2a356c56Anton Korobeynikov } else { 111a024e8cedab928403818ac79e899cdae2a356c56Anton Korobeynikov Function *F = P->getParent()->getParent(); 11250dead06ffc107edb7e84857baaeeb09039c631cOwen Anderson Slot = new AllocaInst(P->getType(), 0, P->getName()+".reg2mem", 113a024e8cedab928403818ac79e899cdae2a356c56Anton Korobeynikov F->getEntryBlock().begin()); 114a024e8cedab928403818ac79e899cdae2a356c56Anton Korobeynikov } 115d0e8469ba65c54b593df15b7249d7fe12097c4cfJim Grosbach 1161bc147b892b4b881a020a3fb706c5415ef244730Bill Wendling // Iterate over each operand inserting a store in each predecessor. 11708d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) { 11808d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(P->getIncomingValue(i))) { 119d0e8469ba65c54b593df15b7249d7fe12097c4cfJim Grosbach assert(II->getParent() != P->getIncomingBlock(i) && 1208e68c3873549ca31533e2e3e40dda3a43cb79566Jeffrey Yasskin "Invoke edge not supported yet"); (void)II; 12108d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner } 122d0e8469ba65c54b593df15b7249d7fe12097c4cfJim Grosbach new StoreInst(P->getIncomingValue(i), Slot, 12308d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner P->getIncomingBlock(i)->getTerminator()); 12408d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner } 125d0e8469ba65c54b593df15b7249d7fe12097c4cfJim Grosbach 1261bc147b892b4b881a020a3fb706c5415ef244730Bill Wendling // Insert a load in place of the PHI and replace all uses. 12708d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner Value *V = new LoadInst(Slot, P->getName()+".reload", P); 12808d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner P->replaceAllUsesWith(V); 129d0e8469ba65c54b593df15b7249d7fe12097c4cfJim Grosbach 1301bc147b892b4b881a020a3fb706c5415ef244730Bill Wendling // Delete PHI. 13108d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner P->eraseFromParent(); 13208d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner return Slot; 13308d14d2469c4f0465f610a204353220ee2ccde9cTanya Lattner} 134