Chris Lattner | 0c7e8e1 | 2003-11-06 19:46:29 +0000 | [diff] [blame] | 1 | //===- DemoteRegToStack.cpp - Move a virtual register to the stack --------===// |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 2 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame^] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 7 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 9 | // |
Chris Lattner | ab2b328 | 2003-05-29 15:12:27 +0000 | [diff] [blame] | 10 | // This file provide the function DemoteRegToStack(). This function takes a |
Chris Lattner | c1a0623 | 2004-03-16 23:23:11 +0000 | [diff] [blame] | 11 | // virtual register computed by an Instruction and replaces it with a slot in |
Chris Lattner | ab2b328 | 2003-05-29 15:12:27 +0000 | [diff] [blame] | 12 | // the stack frame, allocated via alloca. It returns the pointer to the |
Chris Lattner | c1a0623 | 2004-03-16 23:23:11 +0000 | [diff] [blame] | 13 | // AllocaInst inserted. After this function is called on an instruction, we are |
| 14 | // guaranteed that the only user of the instruction is a store that is |
| 15 | // immediately after it. |
Chris Lattner | ab2b328 | 2003-05-29 15:12:27 +0000 | [diff] [blame] | 16 | // |
Vikram S. Adve | 83e3b65 | 2002-12-10 13:07:58 +0000 | [diff] [blame] | 17 | //===----------------------------------------------------------------------===// |
| 18 | |
Chris Lattner | a2dc727 | 2004-03-14 02:13:38 +0000 | [diff] [blame] | 19 | #include "llvm/Transforms/Utils/Local.h" |
Vikram S. Adve | 83e3b65 | 2002-12-10 13:07:58 +0000 | [diff] [blame] | 20 | #include "llvm/Function.h" |
Chris Lattner | c1a0623 | 2004-03-16 23:23:11 +0000 | [diff] [blame] | 21 | #include "llvm/Instructions.h" |
Chris Lattner | 5b3a455 | 2005-03-17 15:38:16 +0000 | [diff] [blame] | 22 | #include "llvm/Type.h" |
Chris Lattner | c68bace | 2004-04-01 20:28:45 +0000 | [diff] [blame] | 23 | #include <map> |
Chris Lattner | f7703df | 2004-01-09 06:12:26 +0000 | [diff] [blame] | 24 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 25 | |
Chris Lattner | c1a0623 | 2004-03-16 23:23:11 +0000 | [diff] [blame] | 26 | /// DemoteRegToStack - This function takes a virtual register computed by an |
| 27 | /// Instruction and replaces it with a slot in the stack frame, allocated via |
| 28 | /// alloca. This allows the CFG to be changed around without fear of |
| 29 | /// invalidating the SSA information for the value. It returns the pointer to |
| 30 | /// the alloca inserted to create a stack slot for I. |
| 31 | /// |
Anton Korobeynikov | a024e8c | 2007-10-21 23:05:16 +0000 | [diff] [blame] | 32 | AllocaInst* llvm::DemoteRegToStack(Instruction &I, bool VolatileLoads, |
| 33 | Instruction *AllocaPoint) { |
| 34 | if (I.use_empty()) { |
| 35 | I.eraseFromParent(); |
| 36 | return 0; |
| 37 | } |
| 38 | |
Chris Lattner | c1a0623 | 2004-03-16 23:23:11 +0000 | [diff] [blame] | 39 | // Create a stack slot to hold the value. |
Anton Korobeynikov | a024e8c | 2007-10-21 23:05:16 +0000 | [diff] [blame] | 40 | AllocaInst *Slot; |
| 41 | if (AllocaPoint) { |
| 42 | Slot = new AllocaInst(I.getType(), 0, I.getName()+".reg2mem", AllocaPoint); |
| 43 | } else { |
| 44 | Function *F = I.getParent()->getParent(); |
| 45 | Slot = new AllocaInst(I.getType(), 0, I.getName()+".reg2mem", |
| 46 | F->getEntryBlock().begin()); |
| 47 | } |
| 48 | |
Chris Lattner | c1a0623 | 2004-03-16 23:23:11 +0000 | [diff] [blame] | 49 | // Change all of the users of the instruction to read from the stack slot |
| 50 | // instead. |
| 51 | while (!I.use_empty()) { |
| 52 | Instruction *U = cast<Instruction>(I.use_back()); |
| 53 | if (PHINode *PN = dyn_cast<PHINode>(U)) { |
| 54 | // If this is a PHI node, we can't insert a load of the value before the |
| 55 | // use. Instead, insert the load in the predecessor block corresponding |
| 56 | // to the incoming value. |
| 57 | // |
| 58 | // Note that if there are multiple edges from a basic block to this PHI |
Chris Lattner | c68bace | 2004-04-01 20:28:45 +0000 | [diff] [blame] | 59 | // node that we cannot multiple loads. The problem is that the resultant |
| 60 | // PHI node will have multiple values (from each load) coming in from the |
| 61 | // same block, which is illegal SSA form. For this reason, we keep track |
| 62 | // and reuse loads we insert. |
| 63 | std::map<BasicBlock*, Value*> Loads; |
Chris Lattner | c1a0623 | 2004-03-16 23:23:11 +0000 | [diff] [blame] | 64 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) |
| 65 | if (PN->getIncomingValue(i) == &I) { |
Chris Lattner | c68bace | 2004-04-01 20:28:45 +0000 | [diff] [blame] | 66 | Value *&V = Loads[PN->getIncomingBlock(i)]; |
| 67 | if (V == 0) { |
| 68 | // Insert the load into the predecessor block |
Chris Lattner | 6d7277b | 2005-09-27 19:39:00 +0000 | [diff] [blame] | 69 | V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads, |
Chris Lattner | c68bace | 2004-04-01 20:28:45 +0000 | [diff] [blame] | 70 | PN->getIncomingBlock(i)->getTerminator()); |
| 71 | } |
Chris Lattner | c1a0623 | 2004-03-16 23:23:11 +0000 | [diff] [blame] | 72 | PN->setIncomingValue(i, V); |
Chris Lattner | ab4536e | 2003-09-20 14:36:23 +0000 | [diff] [blame] | 73 | } |
Vikram S. Adve | 83e3b65 | 2002-12-10 13:07:58 +0000 | [diff] [blame] | 74 | |
Chris Lattner | c1a0623 | 2004-03-16 23:23:11 +0000 | [diff] [blame] | 75 | } else { |
| 76 | // If this is a normal instruction, just insert a load. |
Chris Lattner | 6d7277b | 2005-09-27 19:39:00 +0000 | [diff] [blame] | 77 | Value *V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads, U); |
Chris Lattner | c1a0623 | 2004-03-16 23:23:11 +0000 | [diff] [blame] | 78 | U->replaceUsesOfWith(&I, V); |
Vikram S. Adve | 83e3b65 | 2002-12-10 13:07:58 +0000 | [diff] [blame] | 79 | } |
Chris Lattner | ab4536e | 2003-09-20 14:36:23 +0000 | [diff] [blame] | 80 | } |
Chris Lattner | 0c7e8e1 | 2003-11-06 19:46:29 +0000 | [diff] [blame] | 81 | |
Vikram S. Adve | 83e3b65 | 2002-12-10 13:07:58 +0000 | [diff] [blame] | 82 | |
Chris Lattner | c1a0623 | 2004-03-16 23:23:11 +0000 | [diff] [blame] | 83 | // Insert stores of the computed value into the stack slot. We have to be |
| 84 | // careful is I is an invoke instruction though, because we can't insert the |
| 85 | // store AFTER the terminator instruction. |
Chris Lattner | 6d7277b | 2005-09-27 19:39:00 +0000 | [diff] [blame] | 86 | BasicBlock::iterator InsertPt; |
Chris Lattner | c1a0623 | 2004-03-16 23:23:11 +0000 | [diff] [blame] | 87 | if (!isa<TerminatorInst>(I)) { |
Chris Lattner | 6d7277b | 2005-09-27 19:39:00 +0000 | [diff] [blame] | 88 | InsertPt = &I; |
Chris Lattner | ab55698 | 2005-10-04 00:44:01 +0000 | [diff] [blame] | 89 | ++InsertPt; |
Chris Lattner | c1a0623 | 2004-03-16 23:23:11 +0000 | [diff] [blame] | 90 | } else { |
Chris Lattner | 6d7277b | 2005-09-27 19:39:00 +0000 | [diff] [blame] | 91 | // We cannot demote invoke instructions to the stack if their normal edge |
| 92 | // is critical. |
| 93 | InvokeInst &II = cast<InvokeInst>(I); |
| 94 | assert(II.getNormalDest()->getSinglePredecessor() && |
| 95 | "Cannot demote invoke with a critical successor!"); |
| 96 | InsertPt = II.getNormalDest()->begin(); |
Chris Lattner | c1a0623 | 2004-03-16 23:23:11 +0000 | [diff] [blame] | 97 | } |
Vikram S. Adve | 83e3b65 | 2002-12-10 13:07:58 +0000 | [diff] [blame] | 98 | |
Chris Lattner | ab55698 | 2005-10-04 00:44:01 +0000 | [diff] [blame] | 99 | for (; isa<PHINode>(InsertPt); ++InsertPt) |
Chris Lattner | 6d7277b | 2005-09-27 19:39:00 +0000 | [diff] [blame] | 100 | /* empty */; // Don't insert before any PHI nodes. |
| 101 | new StoreInst(&I, Slot, InsertPt); |
| 102 | |
Chris Lattner | c1a0623 | 2004-03-16 23:23:11 +0000 | [diff] [blame] | 103 | return Slot; |
Vikram S. Adve | 83e3b65 | 2002-12-10 13:07:58 +0000 | [diff] [blame] | 104 | } |
Tanya Lattner | 08d14d2 | 2007-07-11 18:41:34 +0000 | [diff] [blame] | 105 | |
| 106 | |
| 107 | /// DemotePHIToStack - This function takes a virtual register computed by a phi |
| 108 | /// node and replaces it with a slot in the stack frame, allocated via alloca. |
| 109 | /// The phi node is deleted and it returns the pointer to the alloca inserted. |
Anton Korobeynikov | a024e8c | 2007-10-21 23:05:16 +0000 | [diff] [blame] | 110 | AllocaInst* llvm::DemotePHIToStack(PHINode *P, Instruction *AllocaPoint) { |
Tanya Lattner | 08d14d2 | 2007-07-11 18:41:34 +0000 | [diff] [blame] | 111 | if (P->use_empty()) { |
| 112 | P->eraseFromParent(); |
| 113 | return 0; |
| 114 | } |
Anton Korobeynikov | a024e8c | 2007-10-21 23:05:16 +0000 | [diff] [blame] | 115 | |
Tanya Lattner | 08d14d2 | 2007-07-11 18:41:34 +0000 | [diff] [blame] | 116 | // Create a stack slot to hold the value. |
Anton Korobeynikov | a024e8c | 2007-10-21 23:05:16 +0000 | [diff] [blame] | 117 | AllocaInst *Slot; |
| 118 | if (AllocaPoint) { |
| 119 | Slot = new AllocaInst(P->getType(), 0, P->getName()+".reg2mem", AllocaPoint); |
| 120 | } else { |
| 121 | Function *F = P->getParent()->getParent(); |
| 122 | Slot = new AllocaInst(P->getType(), 0, P->getName()+".reg2mem", |
| 123 | F->getEntryBlock().begin()); |
| 124 | } |
Tanya Lattner | 08d14d2 | 2007-07-11 18:41:34 +0000 | [diff] [blame] | 125 | |
| 126 | // Iterate over each operand, insert store in each predecessor. |
| 127 | for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) { |
| 128 | if (InvokeInst *II = dyn_cast<InvokeInst>(P->getIncomingValue(i))) { |
| 129 | assert(II->getParent() != P->getIncomingBlock(i) && |
| 130 | "Invoke edge not supported yet"); |
| 131 | } |
| 132 | new StoreInst(P->getIncomingValue(i), Slot, |
| 133 | P->getIncomingBlock(i)->getTerminator()); |
| 134 | } |
| 135 | |
| 136 | // Insert load in place of the phi and replace all uses. |
| 137 | BasicBlock::iterator InsertPt; |
| 138 | for (InsertPt = P->getParent()->getInstList().begin(); |
Anton Korobeynikov | 406452d | 2007-09-02 22:11:14 +0000 | [diff] [blame] | 139 | isa<PHINode>(InsertPt); ++InsertPt) |
| 140 | ; /*noop */ |
Tanya Lattner | 08d14d2 | 2007-07-11 18:41:34 +0000 | [diff] [blame] | 141 | Value *V = new LoadInst(Slot, P->getName()+".reload", P); |
| 142 | P->replaceAllUsesWith(V); |
| 143 | |
| 144 | // Delete phi. |
| 145 | P->eraseFromParent(); |
| 146 | |
| 147 | return Slot; |
| 148 | } |