DemoteRegToStack.cpp revision c1a0623e8618e6903eca756dcfc0c0df700816c2
10c7e8e17ff602d473d9ea0f91b246365dcc6fe30Chris Lattner//===- DemoteRegToStack.cpp - Move a virtual register to the stack --------===// 283e3b6503d775e98cc85fb881419d1c23b75cde2Vikram S. Adve// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 7b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 10ab2b328c78cd59d663358c550d7b951b55059c3dChris Lattner// This file provide the function DemoteRegToStack(). This function takes a 11c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner// virtual register computed by an Instruction and replaces it with a slot in 12ab2b328c78cd59d663358c550d7b951b55059c3dChris Lattner// the stack frame, allocated via alloca. It returns the pointer to the 13c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner// AllocaInst inserted. After this function is called on an instruction, we are 14c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner// guaranteed that the only user of the instruction is a store that is 15c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner// immediately after it. 16ab2b328c78cd59d663358c550d7b951b55059c3dChris Lattner// 1783e3b6503d775e98cc85fb881419d1c23b75cde2Vikram S. Adve//===----------------------------------------------------------------------===// 1883e3b6503d775e98cc85fb881419d1c23b75cde2Vikram S. Adve 19a2dc727ac4d3cd6d6826140e33eb7b54f074b9d7Chris Lattner#include "llvm/Transforms/Utils/Local.h" 2083e3b6503d775e98cc85fb881419d1c23b75cde2Vikram S. Adve#include "llvm/Function.h" 21c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner#include "llvm/Instructions.h" 22f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 23d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 24c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner/// DemoteRegToStack - This function takes a virtual register computed by an 25c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner/// Instruction and replaces it with a slot in the stack frame, allocated via 26c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner/// alloca. This allows the CFG to be changed around without fear of 27c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner/// invalidating the SSA information for the value. It returns the pointer to 28c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner/// the alloca inserted to create a stack slot for I. 29c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner/// 30c1a0623e8618e6903eca756dcfc0c0df700816c2Chris LattnerAllocaInst* llvm::DemoteRegToStack(Instruction &I) { 31c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner if (I.use_empty()) return 0; // nothing to do! 32c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner 33c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // Create a stack slot to hold the value. 34c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner Function *F = I.getParent()->getParent(); 35c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner AllocaInst *Slot = new AllocaInst(I.getType(), 0, I.getName(), 36c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner F->getEntryBlock().begin()); 37c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner 38c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // Change all of the users of the instruction to read from the stack slot 39c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // instead. 40c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner while (!I.use_empty()) { 41c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner Instruction *U = cast<Instruction>(I.use_back()); 42c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner if (PHINode *PN = dyn_cast<PHINode>(U)) { 43c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // If this is a PHI node, we can't insert a load of the value before the 44c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // use. Instead, insert the load in the predecessor block corresponding 45c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // to the incoming value. 46c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // 47c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // Note that if there are multiple edges from a basic block to this PHI 48c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // node that we'll insert multiple loads. Since DemoteRegToStack requires 49c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // a mem2reg pass after it (to produce reasonable code), we don't care. 50c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 51c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner if (PN->getIncomingValue(i) == &I) { 52c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // Insert the load into the predecessor block 53c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner Value *V = new LoadInst(Slot, I.getName()+".reload", 54c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner PN->getIncomingBlock(i)->getTerminator()); 55c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner PN->setIncomingValue(i, V); 56ab4536e3536fd46863a89fb4cecae9cb8ee21c68Chris Lattner } 57ab4536e3536fd46863a89fb4cecae9cb8ee21c68Chris Lattner 58c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner } else { 59c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // If this is a normal instruction, just insert a load. 60c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner Value *V = new LoadInst(Slot, I.getName()+".reload", U); 61c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner U->replaceUsesOfWith(&I, V); 6283e3b6503d775e98cc85fb881419d1c23b75cde2Vikram S. Adve } 63ab4536e3536fd46863a89fb4cecae9cb8ee21c68Chris Lattner } 6483e3b6503d775e98cc85fb881419d1c23b75cde2Vikram S. Adve 6583e3b6503d775e98cc85fb881419d1c23b75cde2Vikram S. Adve 66c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // Insert stores of the computed value into the stack slot. We have to be 67c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // careful is I is an invoke instruction though, because we can't insert the 68c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // store AFTER the terminator instruction. 69c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner if (!isa<TerminatorInst>(I)) { 70c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner BasicBlock::iterator InsertPt = &I; 71c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner for (++InsertPt; isa<PHINode>(InsertPt); ++InsertPt) 72c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner /* empty */; // Don't insert before any PHI nodes. 73c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner new StoreInst(&I, Slot, InsertPt); 74c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner } else { 75c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // FIXME: We cannot yet demote invoke instructions to the stack, because 76c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // doing so would require breaking critical edges. This should be fixed 77c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // eventually. 78c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner assert(0 && 79c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner "Cannot demote the value computed by an invoke instruction yet!"); 80c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner } 810c7e8e17ff602d473d9ea0f91b246365dcc6fe30Chris Lattner 82c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner return Slot; 8383e3b6503d775e98cc85fb881419d1c23b75cde2Vikram S. Adve} 84