Chris Lattner | 36d1273 | 2005-04-15 19:28:32 +0000 | [diff] [blame] | 1 | //===-- CondPropagate.cpp - Propagate Conditional Expressions -------------===// |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 2 | // |
Chris Lattner | 36d1273 | 2005-04-15 19:28:32 +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 | // |
Chris Lattner | 36d1273 | 2005-04-15 19:28:32 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This pass propagates information about conditional expressions through the |
| 11 | // program, allowing it to eliminate conditional branches in some cases. |
| 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #define DEBUG_TYPE "condprop" |
| 16 | #include "llvm/Transforms/Scalar.h" |
| 17 | #include "llvm/Transforms/Utils/Local.h" |
| 18 | #include "llvm/Constants.h" |
| 19 | #include "llvm/Function.h" |
| 20 | #include "llvm/Instructions.h" |
| 21 | #include "llvm/Pass.h" |
| 22 | #include "llvm/Type.h" |
| 23 | #include "llvm/ADT/STLExtras.h" |
| 24 | #include "llvm/ADT/Statistic.h" |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 25 | #include "llvm/Support/Compiler.h" |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 26 | #include "llvm/Support/Streams.h" |
Chris Lattner | 36d1273 | 2005-04-15 19:28:32 +0000 | [diff] [blame] | 27 | using namespace llvm; |
| 28 | |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 29 | STATISTIC(NumBrThread, "Number of CFG edges threaded through branches"); |
| 30 | STATISTIC(NumSwThread, "Number of CFG edges threaded through switches"); |
Chris Lattner | 36d1273 | 2005-04-15 19:28:32 +0000 | [diff] [blame] | 31 | |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 32 | namespace { |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 33 | struct VISIBILITY_HIDDEN CondProp : public FunctionPass { |
Nick Lewycky | ecd94c8 | 2007-05-06 13:37:16 +0000 | [diff] [blame] | 34 | static char ID; // Pass identification, replacement for typeid |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 35 | CondProp() : FunctionPass((intptr_t)&ID) {} |
| 36 | |
Chris Lattner | 36d1273 | 2005-04-15 19:28:32 +0000 | [diff] [blame] | 37 | virtual bool runOnFunction(Function &F); |
| 38 | |
| 39 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| 40 | AU.addRequiredID(BreakCriticalEdgesID); |
| 41 | //AU.addRequired<DominanceFrontier>(); |
| 42 | } |
| 43 | |
| 44 | private: |
| 45 | bool MadeChange; |
| 46 | void SimplifyBlock(BasicBlock *BB); |
| 47 | void SimplifyPredecessors(BranchInst *BI); |
| 48 | void SimplifyPredecessors(SwitchInst *SI); |
| 49 | void RevectorBlockTo(BasicBlock *FromBB, BasicBlock *ToBB); |
| 50 | }; |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 51 | |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 52 | char CondProp::ID = 0; |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 53 | RegisterPass<CondProp> X("condprop", "Conditional Propagation"); |
Chris Lattner | 36d1273 | 2005-04-15 19:28:32 +0000 | [diff] [blame] | 54 | } |
| 55 | |
| 56 | FunctionPass *llvm::createCondPropagationPass() { |
| 57 | return new CondProp(); |
| 58 | } |
| 59 | |
| 60 | bool CondProp::runOnFunction(Function &F) { |
| 61 | bool EverMadeChange = false; |
| 62 | |
| 63 | // While we are simplifying blocks, keep iterating. |
| 64 | do { |
| 65 | MadeChange = false; |
| 66 | for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) |
| 67 | SimplifyBlock(BB); |
Devang Patel | 70b36d9 | 2007-07-26 20:21:42 +0000 | [diff] [blame] | 68 | EverMadeChange = EverMadeChange || MadeChange; |
Chris Lattner | 36d1273 | 2005-04-15 19:28:32 +0000 | [diff] [blame] | 69 | } while (MadeChange); |
| 70 | return EverMadeChange; |
| 71 | } |
| 72 | |
| 73 | void CondProp::SimplifyBlock(BasicBlock *BB) { |
| 74 | if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { |
| 75 | // If this is a conditional branch based on a phi node that is defined in |
| 76 | // this block, see if we can simplify predecessors of this block. |
| 77 | if (BI->isConditional() && isa<PHINode>(BI->getCondition()) && |
| 78 | cast<PHINode>(BI->getCondition())->getParent() == BB) |
| 79 | SimplifyPredecessors(BI); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 80 | |
Chris Lattner | 36d1273 | 2005-04-15 19:28:32 +0000 | [diff] [blame] | 81 | } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { |
| 82 | if (isa<PHINode>(SI->getCondition()) && |
| 83 | cast<PHINode>(SI->getCondition())->getParent() == BB) |
| 84 | SimplifyPredecessors(SI); |
| 85 | } |
| 86 | |
Chris Lattner | 36d1273 | 2005-04-15 19:28:32 +0000 | [diff] [blame] | 87 | // If possible, simplify the terminator of this block. |
| 88 | if (ConstantFoldTerminator(BB)) |
| 89 | MadeChange = true; |
| 90 | |
| 91 | // If this block ends with an unconditional branch and the only successor has |
| 92 | // only this block as a predecessor, merge the two blocks together. |
| 93 | if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) |
Chris Lattner | df32aac | 2006-08-14 21:38:05 +0000 | [diff] [blame] | 94 | if (BI->isUnconditional() && BI->getSuccessor(0)->getSinglePredecessor() && |
| 95 | BB != BI->getSuccessor(0)) { |
Chris Lattner | 36d1273 | 2005-04-15 19:28:32 +0000 | [diff] [blame] | 96 | BasicBlock *Succ = BI->getSuccessor(0); |
Chris Lattner | df32aac | 2006-08-14 21:38:05 +0000 | [diff] [blame] | 97 | |
| 98 | // If Succ has any PHI nodes, they are all single-entry PHI's. |
| 99 | while (PHINode *PN = dyn_cast<PHINode>(Succ->begin())) { |
| 100 | assert(PN->getNumIncomingValues() == 1 && |
| 101 | "PHI doesn't match parent block"); |
| 102 | PN->replaceAllUsesWith(PN->getIncomingValue(0)); |
| 103 | PN->eraseFromParent(); |
| 104 | } |
| 105 | |
Chris Lattner | 36d1273 | 2005-04-15 19:28:32 +0000 | [diff] [blame] | 106 | // Remove BI. |
| 107 | BI->eraseFromParent(); |
| 108 | |
| 109 | // Move over all of the instructions. |
| 110 | BB->getInstList().splice(BB->end(), Succ->getInstList()); |
| 111 | |
| 112 | // Any phi nodes that had entries for Succ now have entries from BB. |
| 113 | Succ->replaceAllUsesWith(BB); |
| 114 | |
| 115 | // Succ is now dead, but we cannot delete it without potentially |
| 116 | // invalidating iterators elsewhere. Just insert an unreachable |
| 117 | // instruction in it. |
| 118 | new UnreachableInst(Succ); |
| 119 | MadeChange = true; |
| 120 | } |
| 121 | } |
| 122 | |
| 123 | // SimplifyPredecessors(branches) - We know that BI is a conditional branch |
| 124 | // based on a PHI node defined in this block. If the phi node contains constant |
| 125 | // operands, then the blocks corresponding to those operands can be modified to |
| 126 | // jump directly to the destination instead of going through this block. |
| 127 | void CondProp::SimplifyPredecessors(BranchInst *BI) { |
| 128 | // TODO: We currently only handle the most trival case, where the PHI node has |
| 129 | // one use (the branch), and is the only instruction besides the branch in the |
| 130 | // block. |
| 131 | PHINode *PN = cast<PHINode>(BI->getCondition()); |
| 132 | if (!PN->hasOneUse()) return; |
| 133 | |
| 134 | BasicBlock *BB = BI->getParent(); |
| 135 | if (&*BB->begin() != PN || &*next(BB->begin()) != BI) |
| 136 | return; |
| 137 | |
| 138 | // Ok, we have this really simple case, walk the PHI operands, looking for |
| 139 | // constants. Walk from the end to remove operands from the end when |
| 140 | // possible, and to avoid invalidating "i". |
| 141 | for (unsigned i = PN->getNumIncomingValues(); i != 0; --i) |
Zhou Sheng | 6b6b6ef | 2007-01-11 12:24:14 +0000 | [diff] [blame] | 142 | if (ConstantInt *CB = dyn_cast<ConstantInt>(PN->getIncomingValue(i-1))) { |
Chris Lattner | 36d1273 | 2005-04-15 19:28:32 +0000 | [diff] [blame] | 143 | // If we have a constant, forward the edge from its current to its |
| 144 | // ultimate destination. |
Chris Lattner | 36d1273 | 2005-04-15 19:28:32 +0000 | [diff] [blame] | 145 | RevectorBlockTo(PN->getIncomingBlock(i-1), |
Reid Spencer | cae5754 | 2007-03-02 00:28:52 +0000 | [diff] [blame] | 146 | BI->getSuccessor(CB->isZero())); |
Chris Lattner | 36d1273 | 2005-04-15 19:28:32 +0000 | [diff] [blame] | 147 | ++NumBrThread; |
| 148 | |
Chris Lattner | 9dd7a51 | 2007-08-02 04:47:05 +0000 | [diff] [blame] | 149 | // If there were two predecessors before this simplification, or if the |
| 150 | // PHI node contained all the same value except for the one we just |
| 151 | // substituted, the PHI node may be deleted. Don't iterate through it the |
| 152 | // last time. |
| 153 | if (BI->getCondition() != PN) return; |
Chris Lattner | 36d1273 | 2005-04-15 19:28:32 +0000 | [diff] [blame] | 154 | } |
| 155 | } |
| 156 | |
| 157 | // SimplifyPredecessors(switch) - We know that SI is switch based on a PHI node |
| 158 | // defined in this block. If the phi node contains constant operands, then the |
| 159 | // blocks corresponding to those operands can be modified to jump directly to |
| 160 | // the destination instead of going through this block. |
| 161 | void CondProp::SimplifyPredecessors(SwitchInst *SI) { |
| 162 | // TODO: We currently only handle the most trival case, where the PHI node has |
| 163 | // one use (the branch), and is the only instruction besides the branch in the |
| 164 | // block. |
| 165 | PHINode *PN = cast<PHINode>(SI->getCondition()); |
| 166 | if (!PN->hasOneUse()) return; |
| 167 | |
| 168 | BasicBlock *BB = SI->getParent(); |
| 169 | if (&*BB->begin() != PN || &*next(BB->begin()) != SI) |
| 170 | return; |
| 171 | |
| 172 | bool RemovedPreds = false; |
| 173 | |
| 174 | // Ok, we have this really simple case, walk the PHI operands, looking for |
| 175 | // constants. Walk from the end to remove operands from the end when |
| 176 | // possible, and to avoid invalidating "i". |
| 177 | for (unsigned i = PN->getNumIncomingValues(); i != 0; --i) |
| 178 | if (ConstantInt *CI = dyn_cast<ConstantInt>(PN->getIncomingValue(i-1))) { |
| 179 | // If we have a constant, forward the edge from its current to its |
| 180 | // ultimate destination. |
Chris Lattner | 36d1273 | 2005-04-15 19:28:32 +0000 | [diff] [blame] | 181 | unsigned DestCase = SI->findCaseValue(CI); |
| 182 | RevectorBlockTo(PN->getIncomingBlock(i-1), |
| 183 | SI->getSuccessor(DestCase)); |
| 184 | ++NumSwThread; |
| 185 | RemovedPreds = true; |
| 186 | |
Chris Lattner | 9dd7a51 | 2007-08-02 04:47:05 +0000 | [diff] [blame] | 187 | // If there were two predecessors before this simplification, or if the |
| 188 | // PHI node contained all the same value except for the one we just |
| 189 | // substituted, the PHI node may be deleted. Don't iterate through it the |
| 190 | // last time. |
| 191 | if (SI->getCondition() != PN) return; |
Chris Lattner | 36d1273 | 2005-04-15 19:28:32 +0000 | [diff] [blame] | 192 | } |
| 193 | } |
| 194 | |
| 195 | |
| 196 | // RevectorBlockTo - Revector the unconditional branch at the end of FromBB to |
| 197 | // the ToBB block, which is one of the successors of its current successor. |
| 198 | void CondProp::RevectorBlockTo(BasicBlock *FromBB, BasicBlock *ToBB) { |
| 199 | BranchInst *FromBr = cast<BranchInst>(FromBB->getTerminator()); |
| 200 | assert(FromBr->isUnconditional() && "FromBB should end with uncond br!"); |
| 201 | |
| 202 | // Get the old block we are threading through. |
| 203 | BasicBlock *OldSucc = FromBr->getSuccessor(0); |
| 204 | |
Devang Patel | e0805a2 | 2006-11-01 23:04:45 +0000 | [diff] [blame] | 205 | // OldSucc had multiple successors. If ToBB has multiple predecessors, then |
| 206 | // the edge between them would be critical, which we already took care of. |
| 207 | // If ToBB has single operand PHI node then take care of it here. |
| 208 | while (PHINode *PN = dyn_cast<PHINode>(ToBB->begin())) { |
Devang Patel | 2c0565f | 2006-11-01 22:26:43 +0000 | [diff] [blame] | 209 | assert(PN->getNumIncomingValues() == 1 && "Critical Edge Found!"); |
| 210 | PN->replaceAllUsesWith(PN->getIncomingValue(0)); |
| 211 | PN->eraseFromParent(); |
| 212 | } |
Chris Lattner | 36d1273 | 2005-04-15 19:28:32 +0000 | [diff] [blame] | 213 | |
| 214 | // Update PHI nodes in OldSucc to know that FromBB no longer branches to it. |
| 215 | OldSucc->removePredecessor(FromBB); |
| 216 | |
| 217 | // Change FromBr to branch to the new destination. |
| 218 | FromBr->setSuccessor(0, ToBB); |
| 219 | |
| 220 | MadeChange = true; |
| 221 | } |