Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 1 | //===-- Local.cpp - Functions to perform local transformations ------------===// |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file was developed by the LLVM research group and is distributed under |
| 6 | // the University of Illinois Open Source License. See LICENSE.TXT for details. |
| 7 | // |
| 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 | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 17 | #include "llvm/iTerminators.h" |
Chris Lattner | 10b1f5a | 2003-08-17 20:21:14 +0000 | [diff] [blame] | 18 | #include "llvm/iOperators.h" |
Chris Lattner | abbc2dd | 2003-12-19 05:56:28 +0000 | [diff] [blame] | 19 | #include "llvm/iPHINode.h" |
Chris Lattner | abbc2dd | 2003-12-19 05:56:28 +0000 | [diff] [blame] | 20 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 21 | |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 22 | //===----------------------------------------------------------------------===// |
Misha Brukman | 82c89b9 | 2003-05-20 21:01:22 +0000 | [diff] [blame] | 23 | // Local constant propagation... |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 24 | // |
| 25 | |
Chris Lattner | abbc2dd | 2003-12-19 05:56:28 +0000 | [diff] [blame] | 26 | /// doConstantPropagation - If an instruction references constants, try to fold |
| 27 | /// them together... |
| 28 | /// |
| 29 | bool llvm::doConstantPropagation(BasicBlock::iterator &II) { |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 30 | if (Constant *C = ConstantFoldInstruction(II)) { |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 31 | // 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] | 32 | II->replaceAllUsesWith(C); |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 33 | |
| 34 | // Remove the instruction from the basic block... |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 35 | II = II->getParent()->getInstList().erase(II); |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 36 | return true; |
| 37 | } |
| 38 | |
| 39 | return false; |
| 40 | } |
| 41 | |
Chris Lattner | 8f90b00 | 2004-01-12 18:25:22 +0000 | [diff] [blame] | 42 | /// ConstantFoldInstruction - Attempt to constant fold the specified |
| 43 | /// instruction. If successful, the constant result is returned, if not, null |
| 44 | /// is returned. Note that this function can only fail when attempting to fold |
| 45 | /// instructions like loads and stores, which have no constant expression form. |
| 46 | /// |
| 47 | Constant *llvm::ConstantFoldInstruction(Instruction *I) { |
| 48 | if (PHINode *PN = dyn_cast<PHINode>(I)) { |
| 49 | if (PN->getNumIncomingValues() == 0) |
| 50 | return Constant::getNullValue(PN->getType()); |
| 51 | |
| 52 | Constant *Result = dyn_cast<Constant>(PN->getIncomingValue(0)); |
| 53 | if (Result == 0) return 0; |
| 54 | |
| 55 | // Handle PHI nodes specially here... |
| 56 | for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) |
| 57 | if (PN->getIncomingValue(i) != Result && PN->getIncomingValue(i) != PN) |
| 58 | return 0; // Not all the same incoming constants... |
| 59 | |
| 60 | // If we reach here, all incoming values are the same constant. |
| 61 | return Result; |
| 62 | } |
| 63 | |
| 64 | Constant *Op0 = 0, *Op1 = 0; |
| 65 | switch (I->getNumOperands()) { |
| 66 | default: |
| 67 | case 2: |
| 68 | Op1 = dyn_cast<Constant>(I->getOperand(1)); |
| 69 | if (Op1 == 0) return 0; // Not a constant?, can't fold |
| 70 | case 1: |
| 71 | Op0 = dyn_cast<Constant>(I->getOperand(0)); |
| 72 | if (Op0 == 0) return 0; // Not a constant?, can't fold |
| 73 | break; |
| 74 | case 0: return 0; |
| 75 | } |
| 76 | |
| 77 | if (isa<BinaryOperator>(I)) |
| 78 | return ConstantExpr::get(I->getOpcode(), Op0, Op1); |
| 79 | |
| 80 | switch (I->getOpcode()) { |
| 81 | default: return 0; |
| 82 | case Instruction::Cast: |
| 83 | return ConstantExpr::getCast(Op0, I->getType()); |
| 84 | case Instruction::Shl: |
| 85 | case Instruction::Shr: |
| 86 | return ConstantExpr::getShift(I->getOpcode(), Op0, Op1); |
| 87 | case Instruction::GetElementPtr: |
| 88 | std::vector<Constant*> IdxList; |
| 89 | IdxList.reserve(I->getNumOperands()-1); |
| 90 | if (Op1) IdxList.push_back(Op1); |
| 91 | for (unsigned i = 2, e = I->getNumOperands(); i != e; ++i) |
| 92 | if (Constant *C = dyn_cast<Constant>(I->getOperand(i))) |
| 93 | IdxList.push_back(C); |
| 94 | else |
| 95 | return 0; // Non-constant operand |
| 96 | return ConstantExpr::getGetElementPtr(Op0, IdxList); |
| 97 | } |
| 98 | } |
| 99 | |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 100 | // ConstantFoldTerminator - If a terminator instruction is predicated on a |
| 101 | // constant value, convert it into an unconditional branch to the constant |
| 102 | // destination. |
| 103 | // |
Chris Lattner | abbc2dd | 2003-12-19 05:56:28 +0000 | [diff] [blame] | 104 | bool llvm::ConstantFoldTerminator(BasicBlock *BB) { |
Chris Lattner | 76ae344 | 2002-05-21 20:04:50 +0000 | [diff] [blame] | 105 | TerminatorInst *T = BB->getTerminator(); |
| 106 | |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 107 | // Branch - See if we are conditional jumping on constant |
| 108 | if (BranchInst *BI = dyn_cast<BranchInst>(T)) { |
| 109 | if (BI->isUnconditional()) return false; // Can't optimize uncond branch |
| 110 | BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0)); |
| 111 | BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1)); |
| 112 | |
| 113 | if (ConstantBool *Cond = dyn_cast<ConstantBool>(BI->getCondition())) { |
| 114 | // Are we branching on constant? |
| 115 | // YES. Change to unconditional branch... |
| 116 | BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2; |
| 117 | BasicBlock *OldDest = Cond->getValue() ? Dest2 : Dest1; |
| 118 | |
| 119 | //cerr << "Function: " << T->getParent()->getParent() |
| 120 | // << "\nRemoving branch from " << T->getParent() |
| 121 | // << "\n\nTo: " << OldDest << endl; |
| 122 | |
| 123 | // Let the basic block know that we are letting go of it. Based on this, |
| 124 | // it will adjust it's PHI nodes. |
| 125 | assert(BI->getParent() && "Terminator not inserted in block!"); |
| 126 | OldDest->removePredecessor(BI->getParent()); |
| 127 | |
| 128 | // Set the unconditional destination, and change the insn to be an |
| 129 | // unconditional branch. |
| 130 | BI->setUnconditionalDest(Destination); |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 131 | return true; |
Chris Lattner | 342a9d1 | 2003-08-17 19:34:55 +0000 | [diff] [blame] | 132 | } else if (Dest2 == Dest1) { // Conditional branch to same location? |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 133 | // This branch matches something like this: |
| 134 | // br bool %cond, label %Dest, label %Dest |
| 135 | // and changes it into: br label %Dest |
| 136 | |
| 137 | // Let the basic block know that we are letting go of one copy of it. |
| 138 | assert(BI->getParent() && "Terminator not inserted in block!"); |
| 139 | Dest1->removePredecessor(BI->getParent()); |
| 140 | |
| 141 | // Change a conditional branch to unconditional. |
| 142 | BI->setUnconditionalDest(Dest1); |
| 143 | return true; |
| 144 | } |
Chris Lattner | 10b1f5a | 2003-08-17 20:21:14 +0000 | [diff] [blame] | 145 | } else if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { |
| 146 | // If we are switching on a constant, we can convert the switch into a |
| 147 | // single branch instruction! |
| 148 | ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); |
| 149 | BasicBlock *TheOnlyDest = SI->getSuccessor(0); // The default dest |
Chris Lattner | 7d6c24c | 2003-08-23 23:18:19 +0000 | [diff] [blame] | 150 | BasicBlock *DefaultDest = TheOnlyDest; |
| 151 | assert(TheOnlyDest == SI->getDefaultDest() && |
| 152 | "Default destination is not successor #0?"); |
Chris Lattner | 694e37f | 2003-08-17 19:41:53 +0000 | [diff] [blame] | 153 | |
Chris Lattner | 10b1f5a | 2003-08-17 20:21:14 +0000 | [diff] [blame] | 154 | // Figure out which case it goes to... |
| 155 | for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) { |
| 156 | // Found case matching a constant operand? |
| 157 | if (SI->getSuccessorValue(i) == CI) { |
| 158 | TheOnlyDest = SI->getSuccessor(i); |
| 159 | break; |
| 160 | } |
Chris Lattner | 694e37f | 2003-08-17 19:41:53 +0000 | [diff] [blame] | 161 | |
Chris Lattner | 7d6c24c | 2003-08-23 23:18:19 +0000 | [diff] [blame] | 162 | // Check to see if this branch is going to the same place as the default |
| 163 | // dest. If so, eliminate it as an explicit compare. |
| 164 | if (SI->getSuccessor(i) == DefaultDest) { |
| 165 | // Remove this entry... |
| 166 | DefaultDest->removePredecessor(SI->getParent()); |
| 167 | SI->removeCase(i); |
| 168 | --i; --e; // Don't skip an entry... |
| 169 | continue; |
| 170 | } |
| 171 | |
Chris Lattner | 10b1f5a | 2003-08-17 20:21:14 +0000 | [diff] [blame] | 172 | // Otherwise, check to see if the switch only branches to one destination. |
| 173 | // We do this by reseting "TheOnlyDest" to null when we find two non-equal |
| 174 | // destinations. |
| 175 | if (SI->getSuccessor(i) != TheOnlyDest) TheOnlyDest = 0; |
Chris Lattner | 694e37f | 2003-08-17 19:41:53 +0000 | [diff] [blame] | 176 | } |
| 177 | |
Chris Lattner | 10b1f5a | 2003-08-17 20:21:14 +0000 | [diff] [blame] | 178 | if (CI && !TheOnlyDest) { |
| 179 | // Branching on a constant, but not any of the cases, go to the default |
| 180 | // successor. |
| 181 | TheOnlyDest = SI->getDefaultDest(); |
| 182 | } |
| 183 | |
| 184 | // If we found a single destination that we can fold the switch into, do so |
| 185 | // now. |
| 186 | if (TheOnlyDest) { |
| 187 | // Insert the new branch.. |
| 188 | new BranchInst(TheOnlyDest, SI); |
| 189 | BasicBlock *BB = SI->getParent(); |
| 190 | |
| 191 | // Remove entries from PHI nodes which we no longer branch to... |
| 192 | for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { |
| 193 | // Found case matching a constant operand? |
| 194 | BasicBlock *Succ = SI->getSuccessor(i); |
| 195 | if (Succ == TheOnlyDest) |
| 196 | TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest |
| 197 | else |
| 198 | Succ->removePredecessor(BB); |
| 199 | } |
| 200 | |
| 201 | // Delete the old switch... |
| 202 | BB->getInstList().erase(SI); |
| 203 | return true; |
| 204 | } else if (SI->getNumSuccessors() == 2) { |
| 205 | // Otherwise, we can fold this switch into a conditional branch |
| 206 | // instruction if it has only one non-default destination. |
| 207 | Value *Cond = new SetCondInst(Instruction::SetEQ, SI->getCondition(), |
| 208 | SI->getSuccessorValue(1), "cond", SI); |
| 209 | // Insert the new branch... |
| 210 | new BranchInst(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI); |
| 211 | |
| 212 | // Delete the old switch... |
| 213 | SI->getParent()->getInstList().erase(SI); |
| 214 | return true; |
| 215 | } |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 216 | } |
| 217 | return false; |
| 218 | } |
| 219 | |
| 220 | |
| 221 | |
| 222 | //===----------------------------------------------------------------------===// |
| 223 | // Local dead code elimination... |
| 224 | // |
| 225 | |
Chris Lattner | abbc2dd | 2003-12-19 05:56:28 +0000 | [diff] [blame] | 226 | bool llvm::isInstructionTriviallyDead(Instruction *I) { |
Chris Lattner | f0a93ed | 2003-02-24 20:48:32 +0000 | [diff] [blame] | 227 | return I->use_empty() && !I->mayWriteToMemory() && !isa<TerminatorInst>(I); |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 228 | } |
| 229 | |
| 230 | // dceInstruction - Inspect the instruction at *BBI and figure out if it's |
| 231 | // [trivially] dead. If so, remove the instruction and update the iterator |
| 232 | // to point to the instruction that immediately succeeded the original |
| 233 | // instruction. |
| 234 | // |
Chris Lattner | abbc2dd | 2003-12-19 05:56:28 +0000 | [diff] [blame] | 235 | bool llvm::dceInstruction(BasicBlock::iterator &BBI) { |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 236 | // Look for un"used" definitions... |
Chris Lattner | 1896150 | 2002-06-25 16:12:52 +0000 | [diff] [blame] | 237 | if (isInstructionTriviallyDead(BBI)) { |
| 238 | BBI = BBI->getParent()->getInstList().erase(BBI); // Bye bye |
Chris Lattner | 4d1e46e | 2002-05-07 18:07:59 +0000 | [diff] [blame] | 239 | return true; |
| 240 | } |
| 241 | return false; |
| 242 | } |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 243 | |
Chris Lattner | abbc2dd | 2003-12-19 05:56:28 +0000 | [diff] [blame] | 244 | //===----------------------------------------------------------------------===// |
| 245 | // PHI Instruction Simplification |
| 246 | // |
| 247 | |
| 248 | /// hasConstantValue - If the specified PHI node always merges together the same |
| 249 | /// value, return the value, otherwise return null. |
| 250 | /// |
| 251 | Value *llvm::hasConstantValue(PHINode *PN) { |
| 252 | // If the PHI node only has one incoming value, eliminate the PHI node... |
| 253 | if (PN->getNumIncomingValues() == 1) |
| 254 | return PN->getIncomingValue(0); |
| 255 | |
| 256 | // Otherwise if all of the incoming values are the same for the PHI, replace |
| 257 | // the PHI node with the incoming value. |
| 258 | // |
| 259 | Value *InVal = 0; |
| 260 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) |
| 261 | if (PN->getIncomingValue(i) != PN) // Not the PHI node itself... |
| 262 | if (InVal && PN->getIncomingValue(i) != InVal) |
| 263 | return 0; // Not the same, bail out. |
| 264 | else |
| 265 | InVal = PN->getIncomingValue(i); |
| 266 | |
| 267 | // The only case that could cause InVal to be null is if we have a PHI node |
| 268 | // that only has entries for itself. In this case, there is no entry into the |
| 269 | // loop, so kill the PHI. |
| 270 | // |
| 271 | if (InVal == 0) InVal = Constant::getNullValue(PN->getType()); |
| 272 | |
| 273 | // All of the incoming values are the same, return the value now. |
| 274 | return InVal; |
| 275 | } |