Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 1 | //===-- Local.cpp - Functions to perform local transformations ------------===// |
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 | //===----------------------------------------------------------------------===// |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 9 | // |
| 10 | // This family of functions perform various local transformations to the |
| 11 | // program. |
| 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #include "llvm/Transforms/Utils/Local.h" |
Chris Lattner | 81ebc30 | 2004-01-12 18:35:03 +0000 | [diff] [blame] | 16 | #include "llvm/Constants.h" |
Chris Lattner | c5f52e6 | 2005-09-26 05:27:10 +0000 | [diff] [blame] | 17 | #include "llvm/DerivedTypes.h" |
Chris Lattner | 7822c2a | 2004-01-12 19:56:36 +0000 | [diff] [blame] | 18 | #include "llvm/Instructions.h" |
Chris Lattner | cf11035 | 2004-06-11 06:16:23 +0000 | [diff] [blame] | 19 | #include "llvm/Intrinsics.h" |
Chris Lattner | 741c0ae | 2007-12-29 00:59:12 +0000 | [diff] [blame] | 20 | #include "llvm/IntrinsicInst.h" |
Chris Lattner | cbbc6b7 | 2005-10-27 16:34:00 +0000 | [diff] [blame] | 21 | #include "llvm/Analysis/ConstantFolding.h" |
Chris Lattner | 9fa038d | 2007-01-30 23:13:49 +0000 | [diff] [blame] | 22 | #include "llvm/Target/TargetData.h" |
Chris Lattner | c5f52e6 | 2005-09-26 05:27:10 +0000 | [diff] [blame] | 23 | #include "llvm/Support/GetElementPtrTypeIterator.h" |
| 24 | #include "llvm/Support/MathExtras.h" |
Alkis Evlogimenos | 09233fb | 2004-04-21 16:11:40 +0000 | [diff] [blame] | 25 | #include <cerrno> |
Chris Lattner | abbc2dd | 2003-12-19 05:56:28 +0000 | [diff] [blame] | 26 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 27 | |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 28 | //===----------------------------------------------------------------------===// |
Misha Brukman | 82c89b9 | 2003-05-20 21:01:22 +0000 | [diff] [blame] | 29 | // Local constant propagation... |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 30 | // |
| 31 | |
Chris Lattner | abbc2dd | 2003-12-19 05:56:28 +0000 | [diff] [blame] | 32 | /// doConstantPropagation - If an instruction references constants, try to fold |
| 33 | /// them together... |
| 34 | /// |
Chris Lattner | 9fa038d | 2007-01-30 23:13:49 +0000 | [diff] [blame] | 35 | bool llvm::doConstantPropagation(BasicBlock::iterator &II, |
| 36 | const TargetData *TD) { |
| 37 | if (Constant *C = ConstantFoldInstruction(II, TD)) { |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 38 | // Replaces all of the uses of a variable with uses of the constant. |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 39 | II->replaceAllUsesWith(C); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 40 | |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 41 | // Remove the instruction from the basic block... |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 42 | II = II->getParent()->getInstList().erase(II); |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 43 | return true; |
| 44 | } |
| 45 | |
| 46 | return false; |
| 47 | } |
| 48 | |
| 49 | // ConstantFoldTerminator - If a terminator instruction is predicated on a |
| 50 | // constant value, convert it into an unconditional branch to the constant |
| 51 | // destination. |
| 52 | // |
Chris Lattner | abbc2dd | 2003-12-19 05:56:28 +0000 | [diff] [blame] | 53 | bool llvm::ConstantFoldTerminator(BasicBlock *BB) { |
Chris Lattner | 76ae344 | 2002-05-21 20:04:50 +0000 | [diff] [blame] | 54 | TerminatorInst *T = BB->getTerminator(); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 55 | |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 56 | // Branch - See if we are conditional jumping on constant |
| 57 | if (BranchInst *BI = dyn_cast<BranchInst>(T)) { |
| 58 | if (BI->isUnconditional()) return false; // Can't optimize uncond branch |
| 59 | BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0)); |
| 60 | BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1)); |
| 61 | |
Zhou Sheng | 6b6b6ef | 2007-01-11 12:24:14 +0000 | [diff] [blame] | 62 | if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) { |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 63 | // Are we branching on constant? |
| 64 | // YES. Change to unconditional branch... |
Reid Spencer | 579dca1 | 2007-01-12 04:24:46 +0000 | [diff] [blame] | 65 | BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2; |
| 66 | BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1; |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 67 | |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 68 | //cerr << "Function: " << T->getParent()->getParent() |
| 69 | // << "\nRemoving branch from " << T->getParent() |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 70 | // << "\n\nTo: " << OldDest << endl; |
| 71 | |
| 72 | // Let the basic block know that we are letting go of it. Based on this, |
| 73 | // it will adjust it's PHI nodes. |
| 74 | assert(BI->getParent() && "Terminator not inserted in block!"); |
| 75 | OldDest->removePredecessor(BI->getParent()); |
| 76 | |
| 77 | // Set the unconditional destination, and change the insn to be an |
| 78 | // unconditional branch. |
| 79 | BI->setUnconditionalDest(Destination); |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 80 | return true; |
Chris Lattner | 342a9d1 | 2003-08-17 19:34:55 +0000 | [diff] [blame] | 81 | } else if (Dest2 == Dest1) { // Conditional branch to same location? |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 82 | // This branch matches something like this: |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 83 | // br bool %cond, label %Dest, label %Dest |
| 84 | // and changes it into: br label %Dest |
| 85 | |
| 86 | // Let the basic block know that we are letting go of one copy of it. |
| 87 | assert(BI->getParent() && "Terminator not inserted in block!"); |
| 88 | Dest1->removePredecessor(BI->getParent()); |
| 89 | |
| 90 | // Change a conditional branch to unconditional. |
| 91 | BI->setUnconditionalDest(Dest1); |
| 92 | return true; |
| 93 | } |
Chris Lattner | 10b1f5a | 2003-08-17 20:21:14 +0000 | [diff] [blame] | 94 | } else if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { |
| 95 | // If we are switching on a constant, we can convert the switch into a |
| 96 | // single branch instruction! |
| 97 | ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); |
| 98 | BasicBlock *TheOnlyDest = SI->getSuccessor(0); // The default dest |
Chris Lattner | 7d6c24c | 2003-08-23 23:18:19 +0000 | [diff] [blame] | 99 | BasicBlock *DefaultDest = TheOnlyDest; |
| 100 | assert(TheOnlyDest == SI->getDefaultDest() && |
| 101 | "Default destination is not successor #0?"); |
Chris Lattner | 694e37f | 2003-08-17 19:41:53 +0000 | [diff] [blame] | 102 | |
Chris Lattner | 10b1f5a | 2003-08-17 20:21:14 +0000 | [diff] [blame] | 103 | // Figure out which case it goes to... |
| 104 | for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) { |
| 105 | // Found case matching a constant operand? |
| 106 | if (SI->getSuccessorValue(i) == CI) { |
| 107 | TheOnlyDest = SI->getSuccessor(i); |
| 108 | break; |
| 109 | } |
Chris Lattner | 694e37f | 2003-08-17 19:41:53 +0000 | [diff] [blame] | 110 | |
Chris Lattner | 7d6c24c | 2003-08-23 23:18:19 +0000 | [diff] [blame] | 111 | // Check to see if this branch is going to the same place as the default |
| 112 | // dest. If so, eliminate it as an explicit compare. |
| 113 | if (SI->getSuccessor(i) == DefaultDest) { |
| 114 | // Remove this entry... |
| 115 | DefaultDest->removePredecessor(SI->getParent()); |
| 116 | SI->removeCase(i); |
| 117 | --i; --e; // Don't skip an entry... |
| 118 | continue; |
| 119 | } |
| 120 | |
Chris Lattner | 10b1f5a | 2003-08-17 20:21:14 +0000 | [diff] [blame] | 121 | // Otherwise, check to see if the switch only branches to one destination. |
| 122 | // We do this by reseting "TheOnlyDest" to null when we find two non-equal |
| 123 | // destinations. |
| 124 | if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0; |
Chris Lattner | 694e37f | 2003-08-17 19:41:53 +0000 | [diff] [blame] | 125 | } |
| 126 | |
Chris Lattner | 10b1f5a | 2003-08-17 20:21:14 +0000 | [diff] [blame] | 127 | if (CI && !TheOnlyDest) { |
| 128 | // Branching on a constant, but not any of the cases, go to the default |
| 129 | // successor. |
| 130 | TheOnlyDest = SI->getDefaultDest(); |
| 131 | } |
| 132 | |
| 133 | // If we found a single destination that we can fold the switch into, do so |
| 134 | // now. |
| 135 | if (TheOnlyDest) { |
| 136 | // Insert the new branch.. |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame^] | 137 | BranchInst::Create(TheOnlyDest, SI); |
Chris Lattner | 10b1f5a | 2003-08-17 20:21:14 +0000 | [diff] [blame] | 138 | BasicBlock *BB = SI->getParent(); |
| 139 | |
| 140 | // Remove entries from PHI nodes which we no longer branch to... |
| 141 | for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { |
| 142 | // Found case matching a constant operand? |
| 143 | BasicBlock *Succ = SI->getSuccessor(i); |
| 144 | if (Succ == TheOnlyDest) |
| 145 | TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest |
| 146 | else |
| 147 | Succ->removePredecessor(BB); |
| 148 | } |
| 149 | |
| 150 | // Delete the old switch... |
| 151 | BB->getInstList().erase(SI); |
| 152 | return true; |
| 153 | } else if (SI->getNumSuccessors() == 2) { |
| 154 | // Otherwise, we can fold this switch into a conditional branch |
| 155 | // instruction if it has only one non-default destination. |
Reid Spencer | e4d87aa | 2006-12-23 06:05:41 +0000 | [diff] [blame] | 156 | Value *Cond = new ICmpInst(ICmpInst::ICMP_EQ, SI->getCondition(), |
| 157 | SI->getSuccessorValue(1), "cond", SI); |
Chris Lattner | 10b1f5a | 2003-08-17 20:21:14 +0000 | [diff] [blame] | 158 | // Insert the new branch... |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame^] | 159 | BranchInst::Create(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI); |
Chris Lattner | 10b1f5a | 2003-08-17 20:21:14 +0000 | [diff] [blame] | 160 | |
| 161 | // Delete the old switch... |
| 162 | SI->getParent()->getInstList().erase(SI); |
| 163 | return true; |
| 164 | } |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 165 | } |
| 166 | return false; |
| 167 | } |
| 168 | |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 169 | |
| 170 | //===----------------------------------------------------------------------===// |
| 171 | // Local dead code elimination... |
| 172 | // |
| 173 | |
Chris Lattner | abbc2dd | 2003-12-19 05:56:28 +0000 | [diff] [blame] | 174 | bool llvm::isInstructionTriviallyDead(Instruction *I) { |
Chris Lattner | ec710c5 | 2005-05-06 05:27:34 +0000 | [diff] [blame] | 175 | if (!I->use_empty() || isa<TerminatorInst>(I)) return false; |
Jeff Cohen | 00b16889 | 2005-07-27 06:12:32 +0000 | [diff] [blame] | 176 | |
Chris Lattner | 741c0ae | 2007-12-29 00:59:12 +0000 | [diff] [blame] | 177 | if (!I->mayWriteToMemory()) |
| 178 | return true; |
Chris Lattner | ec710c5 | 2005-05-06 05:27:34 +0000 | [diff] [blame] | 179 | |
Chris Lattner | 741c0ae | 2007-12-29 00:59:12 +0000 | [diff] [blame] | 180 | // Special case intrinsics that "may write to memory" but can be deleted when |
| 181 | // dead. |
| 182 | if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) |
| 183 | // Safe to delete llvm.stacksave if dead. |
| 184 | if (II->getIntrinsicID() == Intrinsic::stacksave) |
| 185 | return true; |
| 186 | |
Chris Lattner | ec710c5 | 2005-05-06 05:27:34 +0000 | [diff] [blame] | 187 | return false; |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 188 | } |
| 189 | |
| 190 | // dceInstruction - Inspect the instruction at *BBI and figure out if it's |
| 191 | // [trivially] dead. If so, remove the instruction and update the iterator |
| 192 | // to point to the instruction that immediately succeeded the original |
| 193 | // instruction. |
| 194 | // |
Chris Lattner | abbc2dd | 2003-12-19 05:56:28 +0000 | [diff] [blame] | 195 | bool llvm::dceInstruction(BasicBlock::iterator &BBI) { |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 196 | // Look for un"used" definitions... |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 197 | if (isInstructionTriviallyDead(BBI)) { |
| 198 | BBI = BBI->getParent()->getInstList().erase(BBI); // Bye bye |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 199 | return true; |
| 200 | } |
| 201 | return false; |
| 202 | } |