DemoteRegToStack.cpp revision fd93908ae8b9684fe71c239e3c6cfe13ff6a2663
10c7e8e17ff602d473d9ea0f91b246365dcc6fe30Chris Lattner//===- DemoteRegToStack.cpp - Move a virtual register to the stack --------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 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. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 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" 225b3a4553c1da7e417a240379e2f510c77532c5c1Chris Lattner#include "llvm/Type.h" 23c68bace452dbad23794d4b3c47eeebc00d489cefChris Lattner#include <map> 24f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 25d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 26c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner/// DemoteRegToStack - This function takes a virtual register computed by an 27c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner/// Instruction and replaces it with a slot in the stack frame, allocated via 28c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner/// alloca. This allows the CFG to be changed around without fear of 29c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner/// invalidating the SSA information for the value. It returns the pointer to 30c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner/// the alloca inserted to create a stack slot for I. 31c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner/// 32c1a0623e8618e6903eca756dcfc0c0df700816c2Chris LattnerAllocaInst* llvm::DemoteRegToStack(Instruction &I) { 33c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner if (I.use_empty()) return 0; // nothing to do! 34c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner 35c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // Create a stack slot to hold the value. 36c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner Function *F = I.getParent()->getParent(); 37c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner AllocaInst *Slot = new AllocaInst(I.getType(), 0, I.getName(), 38c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner F->getEntryBlock().begin()); 39c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner 40c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // Change all of the users of the instruction to read from the stack slot 41c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // instead. 42c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner while (!I.use_empty()) { 43c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner Instruction *U = cast<Instruction>(I.use_back()); 44c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner if (PHINode *PN = dyn_cast<PHINode>(U)) { 45c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // If this is a PHI node, we can't insert a load of the value before the 46c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // use. Instead, insert the load in the predecessor block corresponding 47c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // to the incoming value. 48c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // 49c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // Note that if there are multiple edges from a basic block to this PHI 50c68bace452dbad23794d4b3c47eeebc00d489cefChris Lattner // node that we cannot multiple loads. The problem is that the resultant 51c68bace452dbad23794d4b3c47eeebc00d489cefChris Lattner // PHI node will have multiple values (from each load) coming in from the 52c68bace452dbad23794d4b3c47eeebc00d489cefChris Lattner // same block, which is illegal SSA form. For this reason, we keep track 53c68bace452dbad23794d4b3c47eeebc00d489cefChris Lattner // and reuse loads we insert. 54c68bace452dbad23794d4b3c47eeebc00d489cefChris Lattner std::map<BasicBlock*, Value*> Loads; 55c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 56c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner if (PN->getIncomingValue(i) == &I) { 57c68bace452dbad23794d4b3c47eeebc00d489cefChris Lattner Value *&V = Loads[PN->getIncomingBlock(i)]; 58c68bace452dbad23794d4b3c47eeebc00d489cefChris Lattner if (V == 0) { 59c68bace452dbad23794d4b3c47eeebc00d489cefChris Lattner // Insert the load into the predecessor block 60c68bace452dbad23794d4b3c47eeebc00d489cefChris Lattner V = new LoadInst(Slot, I.getName()+".reload", 61c68bace452dbad23794d4b3c47eeebc00d489cefChris Lattner PN->getIncomingBlock(i)->getTerminator()); 62c68bace452dbad23794d4b3c47eeebc00d489cefChris Lattner } 63c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner PN->setIncomingValue(i, V); 64ab4536e3536fd46863a89fb4cecae9cb8ee21c68Chris Lattner } 65ab4536e3536fd46863a89fb4cecae9cb8ee21c68Chris Lattner 66c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner } else { 67c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // If this is a normal instruction, just insert a load. 68c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner Value *V = new LoadInst(Slot, I.getName()+".reload", U); 69c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner U->replaceUsesOfWith(&I, V); 7083e3b6503d775e98cc85fb881419d1c23b75cde2Vikram S. Adve } 71ab4536e3536fd46863a89fb4cecae9cb8ee21c68Chris Lattner } 7283e3b6503d775e98cc85fb881419d1c23b75cde2Vikram S. Adve 7383e3b6503d775e98cc85fb881419d1c23b75cde2Vikram S. Adve 74c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // Insert stores of the computed value into the stack slot. We have to be 75c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // careful is I is an invoke instruction though, because we can't insert the 76c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // store AFTER the terminator instruction. 77c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner if (!isa<TerminatorInst>(I)) { 78c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner BasicBlock::iterator InsertPt = &I; 79c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner for (++InsertPt; isa<PHINode>(InsertPt); ++InsertPt) 80c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner /* empty */; // Don't insert before any PHI nodes. 81c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner new StoreInst(&I, Slot, InsertPt); 82c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner } else { 83c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // FIXME: We cannot yet demote invoke instructions to the stack, because 84c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // doing so would require breaking critical edges. This should be fixed 85c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner // eventually. 86c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner assert(0 && 87c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner "Cannot demote the value computed by an invoke instruction yet!"); 88c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner } 890c7e8e17ff602d473d9ea0f91b246365dcc6fe30Chris Lattner 90c1a0623e8618e6903eca756dcfc0c0df700816c2Chris Lattner return Slot; 9183e3b6503d775e98cc85fb881419d1c23b75cde2Vikram S. Adve} 92