Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 1 | //===- CodeGenPrepare.cpp - Prepare a function for code generation --------===// |
| 2 | // |
| 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. |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This pass munges the code in the input function to better prepare it for |
| 11 | // SelectionDAG-based code generation. This works around limitations in it's |
| 12 | // basic-block-at-a-time approach. It should eventually be removed. |
| 13 | // |
| 14 | //===----------------------------------------------------------------------===// |
| 15 | |
| 16 | #define DEBUG_TYPE "codegenprepare" |
| 17 | #include "llvm/Transforms/Scalar.h" |
| 18 | #include "llvm/Constants.h" |
| 19 | #include "llvm/DerivedTypes.h" |
| 20 | #include "llvm/Function.h" |
| 21 | #include "llvm/Instructions.h" |
| 22 | #include "llvm/Pass.h" |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 23 | #include "llvm/Target/TargetAsmInfo.h" |
| 24 | #include "llvm/Target/TargetData.h" |
| 25 | #include "llvm/Target/TargetLowering.h" |
| 26 | #include "llvm/Target/TargetMachine.h" |
| 27 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
Chris Lattner | dd77df3 | 2007-04-13 20:30:56 +0000 | [diff] [blame] | 28 | #include "llvm/Transforms/Utils/Local.h" |
| 29 | #include "llvm/ADT/DenseMap.h" |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 30 | #include "llvm/ADT/SmallSet.h" |
Evan Cheng | bdcb726 | 2007-12-05 23:58:20 +0000 | [diff] [blame] | 31 | #include "llvm/Support/CommandLine.h" |
Chris Lattner | d9c3a0d | 2007-04-02 01:35:34 +0000 | [diff] [blame] | 32 | #include "llvm/Support/Compiler.h" |
Evan Cheng | bdcb726 | 2007-12-05 23:58:20 +0000 | [diff] [blame] | 33 | #include "llvm/Support/Debug.h" |
Chris Lattner | dd77df3 | 2007-04-13 20:30:56 +0000 | [diff] [blame] | 34 | #include "llvm/Support/GetElementPtrTypeIterator.h" |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 35 | using namespace llvm; |
| 36 | |
Evan Cheng | bdcb726 | 2007-12-05 23:58:20 +0000 | [diff] [blame] | 37 | namespace { |
| 38 | cl::opt<bool> OptExtUses("optimize-ext-uses", |
Evan Cheng | f9785f9 | 2007-12-13 03:32:53 +0000 | [diff] [blame] | 39 | cl::init(true), cl::Hidden); |
Evan Cheng | bdcb726 | 2007-12-05 23:58:20 +0000 | [diff] [blame] | 40 | } |
| 41 | |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 42 | namespace { |
| 43 | class VISIBILITY_HIDDEN CodeGenPrepare : public FunctionPass { |
| 44 | /// TLI - Keep a pointer of a TargetLowering to consult for determining |
| 45 | /// transformation profitability. |
| 46 | const TargetLowering *TLI; |
| 47 | public: |
Nick Lewycky | ecd94c8 | 2007-05-06 13:37:16 +0000 | [diff] [blame] | 48 | static char ID; // Pass identification, replacement for typeid |
Dan Gohman | c2bbfc1 | 2007-08-01 15:32:29 +0000 | [diff] [blame] | 49 | explicit CodeGenPrepare(const TargetLowering *tli = 0) |
| 50 | : FunctionPass((intptr_t)&ID), TLI(tli) {} |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 51 | bool runOnFunction(Function &F); |
| 52 | |
| 53 | private: |
Chris Lattner | d9c3a0d | 2007-04-02 01:35:34 +0000 | [diff] [blame] | 54 | bool EliminateMostlyEmptyBlocks(Function &F); |
| 55 | bool CanMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const; |
| 56 | void EliminateMostlyEmptyBlock(BasicBlock *BB); |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 57 | bool OptimizeBlock(BasicBlock &BB); |
Chris Lattner | dd77df3 | 2007-04-13 20:30:56 +0000 | [diff] [blame] | 58 | bool OptimizeLoadStoreInst(Instruction *I, Value *Addr, |
| 59 | const Type *AccessTy, |
| 60 | DenseMap<Value*,Value*> &SunkAddrs); |
Evan Cheng | bdcb726 | 2007-12-05 23:58:20 +0000 | [diff] [blame] | 61 | bool OptimizeExtUses(Instruction *I); |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 62 | }; |
| 63 | } |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 64 | |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 65 | char CodeGenPrepare::ID = 0; |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 66 | static RegisterPass<CodeGenPrepare> X("codegenprepare", |
| 67 | "Optimize for code generation"); |
| 68 | |
| 69 | FunctionPass *llvm::createCodeGenPreparePass(const TargetLowering *TLI) { |
| 70 | return new CodeGenPrepare(TLI); |
| 71 | } |
| 72 | |
| 73 | |
| 74 | bool CodeGenPrepare::runOnFunction(Function &F) { |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 75 | bool EverMadeChange = false; |
Chris Lattner | d9c3a0d | 2007-04-02 01:35:34 +0000 | [diff] [blame] | 76 | |
| 77 | // First pass, eliminate blocks that contain only PHI nodes and an |
| 78 | // unconditional branch. |
| 79 | EverMadeChange |= EliminateMostlyEmptyBlocks(F); |
| 80 | |
| 81 | bool MadeChange = true; |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 82 | while (MadeChange) { |
| 83 | MadeChange = false; |
| 84 | for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) |
| 85 | MadeChange |= OptimizeBlock(*BB); |
| 86 | EverMadeChange |= MadeChange; |
| 87 | } |
| 88 | return EverMadeChange; |
| 89 | } |
| 90 | |
Chris Lattner | d9c3a0d | 2007-04-02 01:35:34 +0000 | [diff] [blame] | 91 | /// EliminateMostlyEmptyBlocks - eliminate blocks that contain only PHI nodes |
| 92 | /// and an unconditional branch. Passes before isel (e.g. LSR/loopsimplify) |
| 93 | /// often split edges in ways that are non-optimal for isel. Start by |
| 94 | /// eliminating these blocks so we can split them the way we want them. |
| 95 | bool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) { |
| 96 | bool MadeChange = false; |
| 97 | // Note that this intentionally skips the entry block. |
| 98 | for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) { |
| 99 | BasicBlock *BB = I++; |
| 100 | |
| 101 | // If this block doesn't end with an uncond branch, ignore it. |
| 102 | BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); |
| 103 | if (!BI || !BI->isUnconditional()) |
| 104 | continue; |
| 105 | |
| 106 | // If the instruction before the branch isn't a phi node, then other stuff |
| 107 | // is happening here. |
| 108 | BasicBlock::iterator BBI = BI; |
| 109 | if (BBI != BB->begin()) { |
| 110 | --BBI; |
| 111 | if (!isa<PHINode>(BBI)) continue; |
| 112 | } |
| 113 | |
| 114 | // Do not break infinite loops. |
| 115 | BasicBlock *DestBB = BI->getSuccessor(0); |
| 116 | if (DestBB == BB) |
| 117 | continue; |
| 118 | |
| 119 | if (!CanMergeBlocks(BB, DestBB)) |
| 120 | continue; |
| 121 | |
| 122 | EliminateMostlyEmptyBlock(BB); |
| 123 | MadeChange = true; |
| 124 | } |
| 125 | return MadeChange; |
| 126 | } |
| 127 | |
| 128 | /// CanMergeBlocks - Return true if we can merge BB into DestBB if there is a |
| 129 | /// single uncond branch between them, and BB contains no other non-phi |
| 130 | /// instructions. |
| 131 | bool CodeGenPrepare::CanMergeBlocks(const BasicBlock *BB, |
| 132 | const BasicBlock *DestBB) const { |
| 133 | // We only want to eliminate blocks whose phi nodes are used by phi nodes in |
| 134 | // the successor. If there are more complex condition (e.g. preheaders), |
| 135 | // don't mess around with them. |
| 136 | BasicBlock::const_iterator BBI = BB->begin(); |
| 137 | while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { |
| 138 | for (Value::use_const_iterator UI = PN->use_begin(), E = PN->use_end(); |
| 139 | UI != E; ++UI) { |
| 140 | const Instruction *User = cast<Instruction>(*UI); |
| 141 | if (User->getParent() != DestBB || !isa<PHINode>(User)) |
| 142 | return false; |
Devang Patel | 75abc1e | 2007-04-25 00:37:04 +0000 | [diff] [blame] | 143 | // If User is inside DestBB block and it is a PHINode then check |
| 144 | // incoming value. If incoming value is not from BB then this is |
| 145 | // a complex condition (e.g. preheaders) we want to avoid here. |
| 146 | if (User->getParent() == DestBB) { |
| 147 | if (const PHINode *UPN = dyn_cast<PHINode>(User)) |
| 148 | for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) { |
| 149 | Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I)); |
| 150 | if (Insn && Insn->getParent() == BB && |
| 151 | Insn->getParent() != UPN->getIncomingBlock(I)) |
| 152 | return false; |
| 153 | } |
| 154 | } |
Chris Lattner | d9c3a0d | 2007-04-02 01:35:34 +0000 | [diff] [blame] | 155 | } |
| 156 | } |
| 157 | |
| 158 | // If BB and DestBB contain any common predecessors, then the phi nodes in BB |
| 159 | // and DestBB may have conflicting incoming values for the block. If so, we |
| 160 | // can't merge the block. |
| 161 | const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin()); |
| 162 | if (!DestBBPN) return true; // no conflict. |
| 163 | |
| 164 | // Collect the preds of BB. |
Chris Lattner | f67f73a | 2007-11-06 22:07:40 +0000 | [diff] [blame] | 165 | SmallPtrSet<const BasicBlock*, 16> BBPreds; |
Chris Lattner | d9c3a0d | 2007-04-02 01:35:34 +0000 | [diff] [blame] | 166 | if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { |
| 167 | // It is faster to get preds from a PHI than with pred_iterator. |
| 168 | for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) |
| 169 | BBPreds.insert(BBPN->getIncomingBlock(i)); |
| 170 | } else { |
| 171 | BBPreds.insert(pred_begin(BB), pred_end(BB)); |
| 172 | } |
| 173 | |
| 174 | // Walk the preds of DestBB. |
| 175 | for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) { |
| 176 | BasicBlock *Pred = DestBBPN->getIncomingBlock(i); |
| 177 | if (BBPreds.count(Pred)) { // Common predecessor? |
| 178 | BBI = DestBB->begin(); |
| 179 | while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { |
| 180 | const Value *V1 = PN->getIncomingValueForBlock(Pred); |
| 181 | const Value *V2 = PN->getIncomingValueForBlock(BB); |
| 182 | |
| 183 | // If V2 is a phi node in BB, look up what the mapped value will be. |
| 184 | if (const PHINode *V2PN = dyn_cast<PHINode>(V2)) |
| 185 | if (V2PN->getParent() == BB) |
| 186 | V2 = V2PN->getIncomingValueForBlock(Pred); |
| 187 | |
| 188 | // If there is a conflict, bail out. |
| 189 | if (V1 != V2) return false; |
| 190 | } |
| 191 | } |
| 192 | } |
| 193 | |
| 194 | return true; |
| 195 | } |
| 196 | |
| 197 | |
| 198 | /// EliminateMostlyEmptyBlock - Eliminate a basic block that have only phi's and |
| 199 | /// an unconditional branch in it. |
| 200 | void CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) { |
| 201 | BranchInst *BI = cast<BranchInst>(BB->getTerminator()); |
| 202 | BasicBlock *DestBB = BI->getSuccessor(0); |
| 203 | |
| 204 | DOUT << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB; |
| 205 | |
| 206 | // If the destination block has a single pred, then this is a trivial edge, |
| 207 | // just collapse it. |
| 208 | if (DestBB->getSinglePredecessor()) { |
| 209 | // If DestBB has single-entry PHI nodes, fold them. |
| 210 | while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) { |
| 211 | PN->replaceAllUsesWith(PN->getIncomingValue(0)); |
| 212 | PN->eraseFromParent(); |
| 213 | } |
| 214 | |
| 215 | // Splice all the PHI nodes from BB over to DestBB. |
| 216 | DestBB->getInstList().splice(DestBB->begin(), BB->getInstList(), |
| 217 | BB->begin(), BI); |
| 218 | |
| 219 | // Anything that branched to BB now branches to DestBB. |
| 220 | BB->replaceAllUsesWith(DestBB); |
| 221 | |
| 222 | // Nuke BB. |
| 223 | BB->eraseFromParent(); |
| 224 | |
| 225 | DOUT << "AFTER:\n" << *DestBB << "\n\n\n"; |
| 226 | return; |
| 227 | } |
| 228 | |
| 229 | // Otherwise, we have multiple predecessors of BB. Update the PHIs in DestBB |
| 230 | // to handle the new incoming edges it is about to have. |
| 231 | PHINode *PN; |
| 232 | for (BasicBlock::iterator BBI = DestBB->begin(); |
| 233 | (PN = dyn_cast<PHINode>(BBI)); ++BBI) { |
| 234 | // Remove the incoming value for BB, and remember it. |
| 235 | Value *InVal = PN->removeIncomingValue(BB, false); |
| 236 | |
| 237 | // Two options: either the InVal is a phi node defined in BB or it is some |
| 238 | // value that dominates BB. |
| 239 | PHINode *InValPhi = dyn_cast<PHINode>(InVal); |
| 240 | if (InValPhi && InValPhi->getParent() == BB) { |
| 241 | // Add all of the input values of the input PHI as inputs of this phi. |
| 242 | for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i) |
| 243 | PN->addIncoming(InValPhi->getIncomingValue(i), |
| 244 | InValPhi->getIncomingBlock(i)); |
| 245 | } else { |
| 246 | // Otherwise, add one instance of the dominating value for each edge that |
| 247 | // we will be adding. |
| 248 | if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { |
| 249 | for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) |
| 250 | PN->addIncoming(InVal, BBPN->getIncomingBlock(i)); |
| 251 | } else { |
| 252 | for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) |
| 253 | PN->addIncoming(InVal, *PI); |
| 254 | } |
| 255 | } |
| 256 | } |
| 257 | |
| 258 | // The PHIs are now updated, change everything that refers to BB to use |
| 259 | // DestBB and remove BB. |
| 260 | BB->replaceAllUsesWith(DestBB); |
| 261 | BB->eraseFromParent(); |
| 262 | |
| 263 | DOUT << "AFTER:\n" << *DestBB << "\n\n\n"; |
| 264 | } |
| 265 | |
| 266 | |
Chris Lattner | ebe8075 | 2007-12-24 19:32:55 +0000 | [diff] [blame] | 267 | /// SplitEdgeNicely - Split the critical edge from TI to its specified |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 268 | /// successor if it will improve codegen. We only do this if the successor has |
| 269 | /// phi nodes (otherwise critical edges are ok). If there is already another |
| 270 | /// predecessor of the succ that is empty (and thus has no phi nodes), use it |
| 271 | /// instead of introducing a new block. |
| 272 | static void SplitEdgeNicely(TerminatorInst *TI, unsigned SuccNum, Pass *P) { |
| 273 | BasicBlock *TIBB = TI->getParent(); |
| 274 | BasicBlock *Dest = TI->getSuccessor(SuccNum); |
| 275 | assert(isa<PHINode>(Dest->begin()) && |
| 276 | "This should only be called if Dest has a PHI!"); |
| 277 | |
Chris Lattner | ebe8075 | 2007-12-24 19:32:55 +0000 | [diff] [blame] | 278 | // As a hack, never split backedges of loops. Even though the copy for any |
| 279 | // PHIs inserted on the backedge would be dead for exits from the loop, we |
| 280 | // assume that the cost of *splitting* the backedge would be too high. |
Chris Lattner | ff26ab2 | 2007-12-25 19:06:45 +0000 | [diff] [blame] | 281 | if (Dest == TIBB) |
Chris Lattner | ebe8075 | 2007-12-24 19:32:55 +0000 | [diff] [blame] | 282 | return; |
| 283 | |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 284 | /// TIPHIValues - This array is lazily computed to determine the values of |
| 285 | /// PHIs in Dest that TI would provide. |
Chris Lattner | ebe8075 | 2007-12-24 19:32:55 +0000 | [diff] [blame] | 286 | SmallVector<Value*, 32> TIPHIValues; |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 287 | |
| 288 | // Check to see if Dest has any blocks that can be used as a split edge for |
| 289 | // this terminator. |
| 290 | for (pred_iterator PI = pred_begin(Dest), E = pred_end(Dest); PI != E; ++PI) { |
| 291 | BasicBlock *Pred = *PI; |
| 292 | // To be usable, the pred has to end with an uncond branch to the dest. |
| 293 | BranchInst *PredBr = dyn_cast<BranchInst>(Pred->getTerminator()); |
| 294 | if (!PredBr || !PredBr->isUnconditional() || |
| 295 | // Must be empty other than the branch. |
Dale Johannesen | 6603a1b | 2007-05-08 01:01:04 +0000 | [diff] [blame] | 296 | &Pred->front() != PredBr || |
| 297 | // Cannot be the entry block; its label does not get emitted. |
| 298 | Pred == &(Dest->getParent()->getEntryBlock())) |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 299 | continue; |
| 300 | |
| 301 | // Finally, since we know that Dest has phi nodes in it, we have to make |
| 302 | // sure that jumping to Pred will have the same affect as going to Dest in |
| 303 | // terms of PHI values. |
| 304 | PHINode *PN; |
| 305 | unsigned PHINo = 0; |
| 306 | bool FoundMatch = true; |
| 307 | for (BasicBlock::iterator I = Dest->begin(); |
| 308 | (PN = dyn_cast<PHINode>(I)); ++I, ++PHINo) { |
| 309 | if (PHINo == TIPHIValues.size()) |
| 310 | TIPHIValues.push_back(PN->getIncomingValueForBlock(TIBB)); |
| 311 | |
| 312 | // If the PHI entry doesn't work, we can't use this pred. |
| 313 | if (TIPHIValues[PHINo] != PN->getIncomingValueForBlock(Pred)) { |
| 314 | FoundMatch = false; |
| 315 | break; |
| 316 | } |
| 317 | } |
| 318 | |
| 319 | // If we found a workable predecessor, change TI to branch to Succ. |
| 320 | if (FoundMatch) { |
| 321 | Dest->removePredecessor(TIBB); |
| 322 | TI->setSuccessor(SuccNum, Pred); |
| 323 | return; |
| 324 | } |
| 325 | } |
| 326 | |
| 327 | SplitCriticalEdge(TI, SuccNum, P, true); |
| 328 | } |
| 329 | |
Chris Lattner | dd77df3 | 2007-04-13 20:30:56 +0000 | [diff] [blame] | 330 | /// OptimizeNoopCopyExpression - If the specified cast instruction is a noop |
| 331 | /// copy (e.g. it's casting from one pointer type to another, int->uint, or |
| 332 | /// int->sbyte on PPC), sink it into user blocks to reduce the number of virtual |
Dale Johannesen | ce0b237 | 2007-06-12 16:50:17 +0000 | [diff] [blame] | 333 | /// registers that must be created and coalesced. |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 334 | /// |
| 335 | /// Return true if any changes are made. |
Chris Lattner | dd77df3 | 2007-04-13 20:30:56 +0000 | [diff] [blame] | 336 | static bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI){ |
| 337 | // If this is a noop copy, |
| 338 | MVT::ValueType SrcVT = TLI.getValueType(CI->getOperand(0)->getType()); |
| 339 | MVT::ValueType DstVT = TLI.getValueType(CI->getType()); |
| 340 | |
| 341 | // This is an fp<->int conversion? |
| 342 | if (MVT::isInteger(SrcVT) != MVT::isInteger(DstVT)) |
| 343 | return false; |
| 344 | |
| 345 | // If this is an extension, it will be a zero or sign extension, which |
| 346 | // isn't a noop. |
| 347 | if (SrcVT < DstVT) return false; |
| 348 | |
| 349 | // If these values will be promoted, find out what they will be promoted |
| 350 | // to. This helps us consider truncates on PPC as noop copies when they |
| 351 | // are. |
| 352 | if (TLI.getTypeAction(SrcVT) == TargetLowering::Promote) |
| 353 | SrcVT = TLI.getTypeToTransformTo(SrcVT); |
| 354 | if (TLI.getTypeAction(DstVT) == TargetLowering::Promote) |
| 355 | DstVT = TLI.getTypeToTransformTo(DstVT); |
| 356 | |
| 357 | // If, after promotion, these are the same types, this is a noop copy. |
| 358 | if (SrcVT != DstVT) |
| 359 | return false; |
| 360 | |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 361 | BasicBlock *DefBB = CI->getParent(); |
| 362 | |
| 363 | /// InsertedCasts - Only insert a cast in each block once. |
Dale Johannesen | ce0b237 | 2007-06-12 16:50:17 +0000 | [diff] [blame] | 364 | DenseMap<BasicBlock*, CastInst*> InsertedCasts; |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 365 | |
| 366 | bool MadeChange = false; |
| 367 | for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); |
| 368 | UI != E; ) { |
| 369 | Use &TheUse = UI.getUse(); |
| 370 | Instruction *User = cast<Instruction>(*UI); |
| 371 | |
| 372 | // Figure out which BB this cast is used in. For PHI's this is the |
| 373 | // appropriate predecessor block. |
| 374 | BasicBlock *UserBB = User->getParent(); |
| 375 | if (PHINode *PN = dyn_cast<PHINode>(User)) { |
| 376 | unsigned OpVal = UI.getOperandNo()/2; |
| 377 | UserBB = PN->getIncomingBlock(OpVal); |
| 378 | } |
| 379 | |
| 380 | // Preincrement use iterator so we don't invalidate it. |
| 381 | ++UI; |
| 382 | |
| 383 | // If this user is in the same block as the cast, don't change the cast. |
| 384 | if (UserBB == DefBB) continue; |
| 385 | |
| 386 | // If we have already inserted a cast into this block, use it. |
| 387 | CastInst *&InsertedCast = InsertedCasts[UserBB]; |
| 388 | |
| 389 | if (!InsertedCast) { |
| 390 | BasicBlock::iterator InsertPt = UserBB->begin(); |
| 391 | while (isa<PHINode>(InsertPt)) ++InsertPt; |
| 392 | |
| 393 | InsertedCast = |
| 394 | CastInst::create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "", |
| 395 | InsertPt); |
| 396 | MadeChange = true; |
| 397 | } |
| 398 | |
Dale Johannesen | ce0b237 | 2007-06-12 16:50:17 +0000 | [diff] [blame] | 399 | // Replace a use of the cast with a use of the new cast. |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 400 | TheUse = InsertedCast; |
| 401 | } |
| 402 | |
| 403 | // If we removed all uses, nuke the cast. |
| 404 | if (CI->use_empty()) |
| 405 | CI->eraseFromParent(); |
| 406 | |
| 407 | return MadeChange; |
| 408 | } |
| 409 | |
Dale Johannesen | ce0b237 | 2007-06-12 16:50:17 +0000 | [diff] [blame] | 410 | /// OptimizeCmpExpression - sink the given CmpInst into user blocks to reduce |
| 411 | /// the number of virtual registers that must be created and coalesced. This is |
Chris Lattner | 684b22d | 2007-08-02 16:53:43 +0000 | [diff] [blame] | 412 | /// a clear win except on targets with multiple condition code registers |
| 413 | /// (PowerPC), where it might lose; some adjustment may be wanted there. |
Dale Johannesen | ce0b237 | 2007-06-12 16:50:17 +0000 | [diff] [blame] | 414 | /// |
| 415 | /// Return true if any changes are made. |
| 416 | static bool OptimizeCmpExpression(CmpInst *CI){ |
| 417 | |
| 418 | BasicBlock *DefBB = CI->getParent(); |
| 419 | |
| 420 | /// InsertedCmp - Only insert a cmp in each block once. |
| 421 | DenseMap<BasicBlock*, CmpInst*> InsertedCmps; |
| 422 | |
| 423 | bool MadeChange = false; |
| 424 | for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); |
| 425 | UI != E; ) { |
| 426 | Use &TheUse = UI.getUse(); |
| 427 | Instruction *User = cast<Instruction>(*UI); |
| 428 | |
| 429 | // Preincrement use iterator so we don't invalidate it. |
| 430 | ++UI; |
| 431 | |
| 432 | // Don't bother for PHI nodes. |
| 433 | if (isa<PHINode>(User)) |
| 434 | continue; |
| 435 | |
| 436 | // Figure out which BB this cmp is used in. |
| 437 | BasicBlock *UserBB = User->getParent(); |
| 438 | |
| 439 | // If this user is in the same block as the cmp, don't change the cmp. |
| 440 | if (UserBB == DefBB) continue; |
| 441 | |
| 442 | // If we have already inserted a cmp into this block, use it. |
| 443 | CmpInst *&InsertedCmp = InsertedCmps[UserBB]; |
| 444 | |
| 445 | if (!InsertedCmp) { |
| 446 | BasicBlock::iterator InsertPt = UserBB->begin(); |
| 447 | while (isa<PHINode>(InsertPt)) ++InsertPt; |
| 448 | |
| 449 | InsertedCmp = |
| 450 | CmpInst::create(CI->getOpcode(), CI->getPredicate(), CI->getOperand(0), |
| 451 | CI->getOperand(1), "", InsertPt); |
| 452 | MadeChange = true; |
| 453 | } |
| 454 | |
| 455 | // Replace a use of the cmp with a use of the new cmp. |
| 456 | TheUse = InsertedCmp; |
| 457 | } |
| 458 | |
| 459 | // If we removed all uses, nuke the cmp. |
| 460 | if (CI->use_empty()) |
| 461 | CI->eraseFromParent(); |
| 462 | |
| 463 | return MadeChange; |
| 464 | } |
| 465 | |
Chris Lattner | dd77df3 | 2007-04-13 20:30:56 +0000 | [diff] [blame] | 466 | /// EraseDeadInstructions - Erase any dead instructions |
| 467 | static void EraseDeadInstructions(Value *V) { |
| 468 | Instruction *I = dyn_cast<Instruction>(V); |
| 469 | if (!I || !I->use_empty()) return; |
| 470 | |
| 471 | SmallPtrSet<Instruction*, 16> Insts; |
| 472 | Insts.insert(I); |
| 473 | |
| 474 | while (!Insts.empty()) { |
| 475 | I = *Insts.begin(); |
| 476 | Insts.erase(I); |
| 477 | if (isInstructionTriviallyDead(I)) { |
| 478 | for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) |
| 479 | if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i))) |
| 480 | Insts.insert(U); |
| 481 | I->eraseFromParent(); |
| 482 | } |
| 483 | } |
| 484 | } |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 485 | |
| 486 | |
Chris Lattner | dd77df3 | 2007-04-13 20:30:56 +0000 | [diff] [blame] | 487 | /// ExtAddrMode - This is an extended version of TargetLowering::AddrMode which |
| 488 | /// holds actual Value*'s for register values. |
| 489 | struct ExtAddrMode : public TargetLowering::AddrMode { |
| 490 | Value *BaseReg; |
| 491 | Value *ScaledReg; |
| 492 | ExtAddrMode() : BaseReg(0), ScaledReg(0) {} |
| 493 | void dump() const; |
| 494 | }; |
| 495 | |
| 496 | static std::ostream &operator<<(std::ostream &OS, const ExtAddrMode &AM) { |
| 497 | bool NeedPlus = false; |
| 498 | OS << "["; |
| 499 | if (AM.BaseGV) |
| 500 | OS << (NeedPlus ? " + " : "") |
| 501 | << "GV:%" << AM.BaseGV->getName(), NeedPlus = true; |
| 502 | |
| 503 | if (AM.BaseOffs) |
| 504 | OS << (NeedPlus ? " + " : "") << AM.BaseOffs, NeedPlus = true; |
| 505 | |
| 506 | if (AM.BaseReg) |
| 507 | OS << (NeedPlus ? " + " : "") |
| 508 | << "Base:%" << AM.BaseReg->getName(), NeedPlus = true; |
| 509 | if (AM.Scale) |
| 510 | OS << (NeedPlus ? " + " : "") |
| 511 | << AM.Scale << "*%" << AM.ScaledReg->getName(), NeedPlus = true; |
| 512 | |
| 513 | return OS << "]"; |
| 514 | } |
| 515 | |
| 516 | void ExtAddrMode::dump() const { |
| 517 | cerr << *this << "\n"; |
| 518 | } |
| 519 | |
| 520 | static bool TryMatchingScaledValue(Value *ScaleReg, int64_t Scale, |
| 521 | const Type *AccessTy, ExtAddrMode &AddrMode, |
| 522 | SmallVector<Instruction*, 16> &AddrModeInsts, |
| 523 | const TargetLowering &TLI, unsigned Depth); |
| 524 | |
| 525 | /// FindMaximalLegalAddressingMode - If we can, try to merge the computation of |
| 526 | /// Addr into the specified addressing mode. If Addr can't be added to AddrMode |
| 527 | /// this returns false. This assumes that Addr is either a pointer type or |
| 528 | /// intptr_t for the target. |
| 529 | static bool FindMaximalLegalAddressingMode(Value *Addr, const Type *AccessTy, |
| 530 | ExtAddrMode &AddrMode, |
| 531 | SmallVector<Instruction*, 16> &AddrModeInsts, |
| 532 | const TargetLowering &TLI, |
| 533 | unsigned Depth) { |
| 534 | |
| 535 | // If this is a global variable, fold it into the addressing mode if possible. |
| 536 | if (GlobalValue *GV = dyn_cast<GlobalValue>(Addr)) { |
| 537 | if (AddrMode.BaseGV == 0) { |
| 538 | AddrMode.BaseGV = GV; |
| 539 | if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) |
| 540 | return true; |
| 541 | AddrMode.BaseGV = 0; |
| 542 | } |
| 543 | } else if (ConstantInt *CI = dyn_cast<ConstantInt>(Addr)) { |
| 544 | AddrMode.BaseOffs += CI->getSExtValue(); |
| 545 | if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) |
| 546 | return true; |
| 547 | AddrMode.BaseOffs -= CI->getSExtValue(); |
| 548 | } else if (isa<ConstantPointerNull>(Addr)) { |
| 549 | return true; |
| 550 | } |
| 551 | |
| 552 | // Look through constant exprs and instructions. |
| 553 | unsigned Opcode = ~0U; |
| 554 | User *AddrInst = 0; |
| 555 | if (Instruction *I = dyn_cast<Instruction>(Addr)) { |
| 556 | Opcode = I->getOpcode(); |
| 557 | AddrInst = I; |
| 558 | } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Addr)) { |
| 559 | Opcode = CE->getOpcode(); |
| 560 | AddrInst = CE; |
| 561 | } |
| 562 | |
| 563 | // Limit recursion to avoid exponential behavior. |
| 564 | if (Depth == 5) { AddrInst = 0; Opcode = ~0U; } |
| 565 | |
| 566 | // If this is really an instruction, add it to our list of related |
| 567 | // instructions. |
| 568 | if (Instruction *I = dyn_cast_or_null<Instruction>(AddrInst)) |
| 569 | AddrModeInsts.push_back(I); |
| 570 | |
| 571 | switch (Opcode) { |
| 572 | case Instruction::PtrToInt: |
| 573 | // PtrToInt is always a noop, as we know that the int type is pointer sized. |
| 574 | if (FindMaximalLegalAddressingMode(AddrInst->getOperand(0), AccessTy, |
| 575 | AddrMode, AddrModeInsts, TLI, Depth)) |
| 576 | return true; |
| 577 | break; |
| 578 | case Instruction::IntToPtr: |
| 579 | // This inttoptr is a no-op if the integer type is pointer sized. |
| 580 | if (TLI.getValueType(AddrInst->getOperand(0)->getType()) == |
| 581 | TLI.getPointerTy()) { |
| 582 | if (FindMaximalLegalAddressingMode(AddrInst->getOperand(0), AccessTy, |
| 583 | AddrMode, AddrModeInsts, TLI, Depth)) |
| 584 | return true; |
| 585 | } |
| 586 | break; |
| 587 | case Instruction::Add: { |
| 588 | // Check to see if we can merge in the RHS then the LHS. If so, we win. |
| 589 | ExtAddrMode BackupAddrMode = AddrMode; |
| 590 | unsigned OldSize = AddrModeInsts.size(); |
| 591 | if (FindMaximalLegalAddressingMode(AddrInst->getOperand(1), AccessTy, |
| 592 | AddrMode, AddrModeInsts, TLI, Depth+1) && |
| 593 | FindMaximalLegalAddressingMode(AddrInst->getOperand(0), AccessTy, |
| 594 | AddrMode, AddrModeInsts, TLI, Depth+1)) |
| 595 | return true; |
| 596 | |
| 597 | // Restore the old addr mode info. |
| 598 | AddrMode = BackupAddrMode; |
| 599 | AddrModeInsts.resize(OldSize); |
| 600 | |
| 601 | // Otherwise this was over-aggressive. Try merging in the LHS then the RHS. |
| 602 | if (FindMaximalLegalAddressingMode(AddrInst->getOperand(0), AccessTy, |
| 603 | AddrMode, AddrModeInsts, TLI, Depth+1) && |
| 604 | FindMaximalLegalAddressingMode(AddrInst->getOperand(1), AccessTy, |
| 605 | AddrMode, AddrModeInsts, TLI, Depth+1)) |
| 606 | return true; |
| 607 | |
| 608 | // Otherwise we definitely can't merge the ADD in. |
| 609 | AddrMode = BackupAddrMode; |
| 610 | AddrModeInsts.resize(OldSize); |
| 611 | break; |
| 612 | } |
| 613 | case Instruction::Or: { |
| 614 | ConstantInt *RHS = dyn_cast<ConstantInt>(AddrInst->getOperand(1)); |
| 615 | if (!RHS) break; |
| 616 | // TODO: We can handle "Or Val, Imm" iff this OR is equivalent to an ADD. |
| 617 | break; |
| 618 | } |
| 619 | case Instruction::Mul: |
| 620 | case Instruction::Shl: { |
| 621 | // Can only handle X*C and X << C, and can only handle this when the scale |
| 622 | // field is available. |
| 623 | ConstantInt *RHS = dyn_cast<ConstantInt>(AddrInst->getOperand(1)); |
| 624 | if (!RHS) break; |
| 625 | int64_t Scale = RHS->getSExtValue(); |
| 626 | if (Opcode == Instruction::Shl) |
| 627 | Scale = 1 << Scale; |
| 628 | |
| 629 | if (TryMatchingScaledValue(AddrInst->getOperand(0), Scale, AccessTy, |
| 630 | AddrMode, AddrModeInsts, TLI, Depth)) |
| 631 | return true; |
| 632 | break; |
| 633 | } |
| 634 | case Instruction::GetElementPtr: { |
| 635 | // Scan the GEP. We check it if it contains constant offsets and at most |
| 636 | // one variable offset. |
| 637 | int VariableOperand = -1; |
| 638 | unsigned VariableScale = 0; |
| 639 | |
| 640 | int64_t ConstantOffset = 0; |
| 641 | const TargetData *TD = TLI.getTargetData(); |
| 642 | gep_type_iterator GTI = gep_type_begin(AddrInst); |
| 643 | for (unsigned i = 1, e = AddrInst->getNumOperands(); i != e; ++i, ++GTI) { |
| 644 | if (const StructType *STy = dyn_cast<StructType>(*GTI)) { |
| 645 | const StructLayout *SL = TD->getStructLayout(STy); |
| 646 | unsigned Idx = |
| 647 | cast<ConstantInt>(AddrInst->getOperand(i))->getZExtValue(); |
| 648 | ConstantOffset += SL->getElementOffset(Idx); |
| 649 | } else { |
Duncan Sands | 514ab34 | 2007-11-01 20:53:16 +0000 | [diff] [blame] | 650 | uint64_t TypeSize = TD->getABITypeSize(GTI.getIndexedType()); |
Chris Lattner | dd77df3 | 2007-04-13 20:30:56 +0000 | [diff] [blame] | 651 | if (ConstantInt *CI = dyn_cast<ConstantInt>(AddrInst->getOperand(i))) { |
| 652 | ConstantOffset += CI->getSExtValue()*TypeSize; |
| 653 | } else if (TypeSize) { // Scales of zero don't do anything. |
| 654 | // We only allow one variable index at the moment. |
| 655 | if (VariableOperand != -1) { |
| 656 | VariableOperand = -2; |
| 657 | break; |
| 658 | } |
| 659 | |
| 660 | // Remember the variable index. |
| 661 | VariableOperand = i; |
| 662 | VariableScale = TypeSize; |
| 663 | } |
| 664 | } |
| 665 | } |
| 666 | |
| 667 | // If the GEP had multiple variable indices, punt. |
| 668 | if (VariableOperand == -2) |
| 669 | break; |
| 670 | |
| 671 | // A common case is for the GEP to only do a constant offset. In this case, |
| 672 | // just add it to the disp field and check validity. |
| 673 | if (VariableOperand == -1) { |
| 674 | AddrMode.BaseOffs += ConstantOffset; |
| 675 | if (ConstantOffset == 0 || TLI.isLegalAddressingMode(AddrMode, AccessTy)){ |
| 676 | // Check to see if we can fold the base pointer in too. |
| 677 | if (FindMaximalLegalAddressingMode(AddrInst->getOperand(0), AccessTy, |
| 678 | AddrMode, AddrModeInsts, TLI, |
| 679 | Depth+1)) |
| 680 | return true; |
| 681 | } |
| 682 | AddrMode.BaseOffs -= ConstantOffset; |
| 683 | } else { |
| 684 | // Check that this has no base reg yet. If so, we won't have a place to |
| 685 | // put the base of the GEP (assuming it is not a null ptr). |
| 686 | bool SetBaseReg = false; |
| 687 | if (AddrMode.HasBaseReg) { |
| 688 | if (!isa<ConstantPointerNull>(AddrInst->getOperand(0))) |
| 689 | break; |
| 690 | } else { |
| 691 | AddrMode.HasBaseReg = true; |
| 692 | AddrMode.BaseReg = AddrInst->getOperand(0); |
| 693 | SetBaseReg = true; |
| 694 | } |
| 695 | |
| 696 | // See if the scale amount is valid for this target. |
| 697 | AddrMode.BaseOffs += ConstantOffset; |
| 698 | if (TryMatchingScaledValue(AddrInst->getOperand(VariableOperand), |
| 699 | VariableScale, AccessTy, AddrMode, |
| 700 | AddrModeInsts, TLI, Depth)) { |
| 701 | if (!SetBaseReg) return true; |
| 702 | |
| 703 | // If this match succeeded, we know that we can form an address with the |
| 704 | // GepBase as the basereg. See if we can match *more*. |
| 705 | AddrMode.HasBaseReg = false; |
| 706 | AddrMode.BaseReg = 0; |
| 707 | if (FindMaximalLegalAddressingMode(AddrInst->getOperand(0), AccessTy, |
| 708 | AddrMode, AddrModeInsts, TLI, |
| 709 | Depth+1)) |
| 710 | return true; |
| 711 | // Strange, shouldn't happen. Restore the base reg and succeed the easy |
| 712 | // way. |
| 713 | AddrMode.HasBaseReg = true; |
| 714 | AddrMode.BaseReg = AddrInst->getOperand(0); |
| 715 | return true; |
| 716 | } |
| 717 | |
| 718 | AddrMode.BaseOffs -= ConstantOffset; |
| 719 | if (SetBaseReg) { |
| 720 | AddrMode.HasBaseReg = false; |
| 721 | AddrMode.BaseReg = 0; |
| 722 | } |
| 723 | } |
| 724 | break; |
| 725 | } |
| 726 | } |
| 727 | |
| 728 | if (Instruction *I = dyn_cast_or_null<Instruction>(AddrInst)) { |
| 729 | assert(AddrModeInsts.back() == I && "Stack imbalance"); |
| 730 | AddrModeInsts.pop_back(); |
| 731 | } |
| 732 | |
| 733 | // Worse case, the target should support [reg] addressing modes. :) |
| 734 | if (!AddrMode.HasBaseReg) { |
| 735 | AddrMode.HasBaseReg = true; |
| 736 | // Still check for legality in case the target supports [imm] but not [i+r]. |
| 737 | if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) { |
| 738 | AddrMode.BaseReg = Addr; |
| 739 | return true; |
| 740 | } |
| 741 | AddrMode.HasBaseReg = false; |
| 742 | } |
| 743 | |
| 744 | // If the base register is already taken, see if we can do [r+r]. |
| 745 | if (AddrMode.Scale == 0) { |
| 746 | AddrMode.Scale = 1; |
| 747 | if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) { |
| 748 | AddrMode.ScaledReg = Addr; |
| 749 | return true; |
| 750 | } |
| 751 | AddrMode.Scale = 0; |
| 752 | } |
| 753 | // Couldn't match. |
| 754 | return false; |
| 755 | } |
| 756 | |
| 757 | /// TryMatchingScaledValue - Try adding ScaleReg*Scale to the specified |
| 758 | /// addressing mode. Return true if this addr mode is legal for the target, |
| 759 | /// false if not. |
| 760 | static bool TryMatchingScaledValue(Value *ScaleReg, int64_t Scale, |
| 761 | const Type *AccessTy, ExtAddrMode &AddrMode, |
| 762 | SmallVector<Instruction*, 16> &AddrModeInsts, |
| 763 | const TargetLowering &TLI, unsigned Depth) { |
| 764 | // If we already have a scale of this value, we can add to it, otherwise, we |
| 765 | // need an available scale field. |
| 766 | if (AddrMode.Scale != 0 && AddrMode.ScaledReg != ScaleReg) |
| 767 | return false; |
| 768 | |
| 769 | ExtAddrMode InputAddrMode = AddrMode; |
| 770 | |
| 771 | // Add scale to turn X*4+X*3 -> X*7. This could also do things like |
| 772 | // [A+B + A*7] -> [B+A*8]. |
| 773 | AddrMode.Scale += Scale; |
| 774 | AddrMode.ScaledReg = ScaleReg; |
| 775 | |
| 776 | if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) { |
| 777 | // Okay, we decided that we can add ScaleReg+Scale to AddrMode. Check now |
| 778 | // to see if ScaleReg is actually X+C. If so, we can turn this into adding |
| 779 | // X*Scale + C*Scale to addr mode. |
| 780 | BinaryOperator *BinOp = dyn_cast<BinaryOperator>(ScaleReg); |
| 781 | if (BinOp && BinOp->getOpcode() == Instruction::Add && |
| 782 | isa<ConstantInt>(BinOp->getOperand(1)) && InputAddrMode.ScaledReg ==0) { |
| 783 | |
| 784 | InputAddrMode.Scale = Scale; |
| 785 | InputAddrMode.ScaledReg = BinOp->getOperand(0); |
| 786 | InputAddrMode.BaseOffs += |
| 787 | cast<ConstantInt>(BinOp->getOperand(1))->getSExtValue()*Scale; |
| 788 | if (TLI.isLegalAddressingMode(InputAddrMode, AccessTy)) { |
| 789 | AddrModeInsts.push_back(BinOp); |
| 790 | AddrMode = InputAddrMode; |
| 791 | return true; |
| 792 | } |
| 793 | } |
| 794 | |
| 795 | // Otherwise, not (x+c)*scale, just return what we have. |
| 796 | return true; |
| 797 | } |
| 798 | |
| 799 | // Otherwise, back this attempt out. |
| 800 | AddrMode.Scale -= Scale; |
| 801 | if (AddrMode.Scale == 0) AddrMode.ScaledReg = 0; |
| 802 | |
| 803 | return false; |
| 804 | } |
| 805 | |
| 806 | |
| 807 | /// IsNonLocalValue - Return true if the specified values are defined in a |
| 808 | /// different basic block than BB. |
| 809 | static bool IsNonLocalValue(Value *V, BasicBlock *BB) { |
| 810 | if (Instruction *I = dyn_cast<Instruction>(V)) |
| 811 | return I->getParent() != BB; |
| 812 | return false; |
| 813 | } |
| 814 | |
| 815 | /// OptimizeLoadStoreInst - Load and Store Instructions have often have |
| 816 | /// addressing modes that can do significant amounts of computation. As such, |
| 817 | /// instruction selection will try to get the load or store to do as much |
| 818 | /// computation as possible for the program. The problem is that isel can only |
| 819 | /// see within a single block. As such, we sink as much legal addressing mode |
| 820 | /// stuff into the block as possible. |
| 821 | bool CodeGenPrepare::OptimizeLoadStoreInst(Instruction *LdStInst, Value *Addr, |
| 822 | const Type *AccessTy, |
| 823 | DenseMap<Value*,Value*> &SunkAddrs) { |
| 824 | // Figure out what addressing mode will be built up for this operation. |
| 825 | SmallVector<Instruction*, 16> AddrModeInsts; |
| 826 | ExtAddrMode AddrMode; |
| 827 | bool Success = FindMaximalLegalAddressingMode(Addr, AccessTy, AddrMode, |
| 828 | AddrModeInsts, *TLI, 0); |
| 829 | Success = Success; assert(Success && "Couldn't select *anything*?"); |
| 830 | |
| 831 | // Check to see if any of the instructions supersumed by this addr mode are |
| 832 | // non-local to I's BB. |
| 833 | bool AnyNonLocal = false; |
| 834 | for (unsigned i = 0, e = AddrModeInsts.size(); i != e; ++i) { |
| 835 | if (IsNonLocalValue(AddrModeInsts[i], LdStInst->getParent())) { |
| 836 | AnyNonLocal = true; |
| 837 | break; |
| 838 | } |
| 839 | } |
| 840 | |
| 841 | // If all the instructions matched are already in this BB, don't do anything. |
| 842 | if (!AnyNonLocal) { |
| 843 | DEBUG(cerr << "CGP: Found local addrmode: " << AddrMode << "\n"); |
| 844 | return false; |
| 845 | } |
| 846 | |
| 847 | // Insert this computation right after this user. Since our caller is |
| 848 | // scanning from the top of the BB to the bottom, reuse of the expr are |
| 849 | // guaranteed to happen later. |
| 850 | BasicBlock::iterator InsertPt = LdStInst; |
| 851 | |
| 852 | // Now that we determined the addressing expression we want to use and know |
| 853 | // that we have to sink it into this block. Check to see if we have already |
| 854 | // done this for some other load/store instr in this block. If so, reuse the |
| 855 | // computation. |
| 856 | Value *&SunkAddr = SunkAddrs[Addr]; |
| 857 | if (SunkAddr) { |
| 858 | DEBUG(cerr << "CGP: Reusing nonlocal addrmode: " << AddrMode << "\n"); |
| 859 | if (SunkAddr->getType() != Addr->getType()) |
| 860 | SunkAddr = new BitCastInst(SunkAddr, Addr->getType(), "tmp", InsertPt); |
| 861 | } else { |
| 862 | DEBUG(cerr << "CGP: SINKING nonlocal addrmode: " << AddrMode << "\n"); |
| 863 | const Type *IntPtrTy = TLI->getTargetData()->getIntPtrType(); |
| 864 | |
| 865 | Value *Result = 0; |
| 866 | // Start with the scale value. |
| 867 | if (AddrMode.Scale) { |
| 868 | Value *V = AddrMode.ScaledReg; |
| 869 | if (V->getType() == IntPtrTy) { |
| 870 | // done. |
| 871 | } else if (isa<PointerType>(V->getType())) { |
| 872 | V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt); |
| 873 | } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() < |
| 874 | cast<IntegerType>(V->getType())->getBitWidth()) { |
| 875 | V = new TruncInst(V, IntPtrTy, "sunkaddr", InsertPt); |
| 876 | } else { |
| 877 | V = new SExtInst(V, IntPtrTy, "sunkaddr", InsertPt); |
| 878 | } |
| 879 | if (AddrMode.Scale != 1) |
| 880 | V = BinaryOperator::createMul(V, ConstantInt::get(IntPtrTy, |
| 881 | AddrMode.Scale), |
| 882 | "sunkaddr", InsertPt); |
| 883 | Result = V; |
| 884 | } |
| 885 | |
| 886 | // Add in the base register. |
| 887 | if (AddrMode.BaseReg) { |
| 888 | Value *V = AddrMode.BaseReg; |
| 889 | if (V->getType() != IntPtrTy) |
| 890 | V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt); |
| 891 | if (Result) |
| 892 | Result = BinaryOperator::createAdd(Result, V, "sunkaddr", InsertPt); |
| 893 | else |
| 894 | Result = V; |
| 895 | } |
| 896 | |
| 897 | // Add in the BaseGV if present. |
| 898 | if (AddrMode.BaseGV) { |
| 899 | Value *V = new PtrToIntInst(AddrMode.BaseGV, IntPtrTy, "sunkaddr", |
| 900 | InsertPt); |
| 901 | if (Result) |
| 902 | Result = BinaryOperator::createAdd(Result, V, "sunkaddr", InsertPt); |
| 903 | else |
| 904 | Result = V; |
| 905 | } |
| 906 | |
| 907 | // Add in the Base Offset if present. |
| 908 | if (AddrMode.BaseOffs) { |
| 909 | Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs); |
| 910 | if (Result) |
| 911 | Result = BinaryOperator::createAdd(Result, V, "sunkaddr", InsertPt); |
| 912 | else |
| 913 | Result = V; |
| 914 | } |
| 915 | |
| 916 | if (Result == 0) |
| 917 | SunkAddr = Constant::getNullValue(Addr->getType()); |
| 918 | else |
| 919 | SunkAddr = new IntToPtrInst(Result, Addr->getType(), "sunkaddr",InsertPt); |
| 920 | } |
| 921 | |
| 922 | LdStInst->replaceUsesOfWith(Addr, SunkAddr); |
| 923 | |
| 924 | if (Addr->use_empty()) |
| 925 | EraseDeadInstructions(Addr); |
| 926 | return true; |
| 927 | } |
| 928 | |
Evan Cheng | bdcb726 | 2007-12-05 23:58:20 +0000 | [diff] [blame] | 929 | bool CodeGenPrepare::OptimizeExtUses(Instruction *I) { |
| 930 | BasicBlock *DefBB = I->getParent(); |
| 931 | |
| 932 | // If both result of the {s|z}xt and its source are live out, rewrite all |
| 933 | // other uses of the source with result of extension. |
| 934 | Value *Src = I->getOperand(0); |
| 935 | if (Src->hasOneUse()) |
| 936 | return false; |
| 937 | |
Evan Cheng | 696e5c0 | 2007-12-13 07:50:36 +0000 | [diff] [blame] | 938 | // Only do this xform if truncating is free. |
Evan Cheng | f9785f9 | 2007-12-13 03:32:53 +0000 | [diff] [blame] | 939 | if (!TLI->isTruncateFree(I->getType(), Src->getType())) |
| 940 | return false; |
| 941 | |
Evan Cheng | 772de51 | 2007-12-12 00:51:06 +0000 | [diff] [blame] | 942 | // Only safe to perform the optimization if the source is also defined in |
Evan Cheng | 765dff2 | 2007-12-12 02:53:41 +0000 | [diff] [blame] | 943 | // this block. |
| 944 | if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->getParent()) |
Evan Cheng | 772de51 | 2007-12-12 00:51:06 +0000 | [diff] [blame] | 945 | return false; |
| 946 | |
Evan Cheng | bdcb726 | 2007-12-05 23:58:20 +0000 | [diff] [blame] | 947 | bool DefIsLiveOut = false; |
| 948 | for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); |
| 949 | UI != E; ++UI) { |
| 950 | Instruction *User = cast<Instruction>(*UI); |
| 951 | |
| 952 | // Figure out which BB this ext is used in. |
| 953 | BasicBlock *UserBB = User->getParent(); |
| 954 | if (UserBB == DefBB) continue; |
| 955 | DefIsLiveOut = true; |
| 956 | break; |
| 957 | } |
| 958 | if (!DefIsLiveOut) |
| 959 | return false; |
| 960 | |
Evan Cheng | 765dff2 | 2007-12-12 02:53:41 +0000 | [diff] [blame] | 961 | // Make sure non of the uses are PHI nodes. |
| 962 | for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); |
| 963 | UI != E; ++UI) { |
| 964 | Instruction *User = cast<Instruction>(*UI); |
Evan Cheng | f9785f9 | 2007-12-13 03:32:53 +0000 | [diff] [blame] | 965 | BasicBlock *UserBB = User->getParent(); |
| 966 | if (UserBB == DefBB) continue; |
| 967 | // Be conservative. We don't want this xform to end up introducing |
| 968 | // reloads just before load / store instructions. |
| 969 | if (isa<PHINode>(User) || isa<LoadInst>(User) || isa<StoreInst>(User)) |
Evan Cheng | 765dff2 | 2007-12-12 02:53:41 +0000 | [diff] [blame] | 970 | return false; |
| 971 | } |
| 972 | |
Evan Cheng | bdcb726 | 2007-12-05 23:58:20 +0000 | [diff] [blame] | 973 | // InsertedTruncs - Only insert one trunc in each block once. |
| 974 | DenseMap<BasicBlock*, Instruction*> InsertedTruncs; |
| 975 | |
| 976 | bool MadeChange = false; |
| 977 | for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); |
| 978 | UI != E; ++UI) { |
| 979 | Use &TheUse = UI.getUse(); |
| 980 | Instruction *User = cast<Instruction>(*UI); |
| 981 | |
| 982 | // Figure out which BB this ext is used in. |
| 983 | BasicBlock *UserBB = User->getParent(); |
| 984 | if (UserBB == DefBB) continue; |
| 985 | |
| 986 | // Both src and def are live in this block. Rewrite the use. |
| 987 | Instruction *&InsertedTrunc = InsertedTruncs[UserBB]; |
| 988 | |
| 989 | if (!InsertedTrunc) { |
| 990 | BasicBlock::iterator InsertPt = UserBB->begin(); |
| 991 | while (isa<PHINode>(InsertPt)) ++InsertPt; |
| 992 | |
| 993 | InsertedTrunc = new TruncInst(I, Src->getType(), "", InsertPt); |
| 994 | } |
| 995 | |
| 996 | // Replace a use of the {s|z}ext source with a use of the result. |
| 997 | TheUse = InsertedTrunc; |
| 998 | |
| 999 | MadeChange = true; |
| 1000 | } |
| 1001 | |
| 1002 | return MadeChange; |
| 1003 | } |
| 1004 | |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 1005 | // In this pass we look for GEP and cast instructions that are used |
| 1006 | // across basic blocks and rewrite them to improve basic-block-at-a-time |
| 1007 | // selection. |
| 1008 | bool CodeGenPrepare::OptimizeBlock(BasicBlock &BB) { |
| 1009 | bool MadeChange = false; |
| 1010 | |
| 1011 | // Split all critical edges where the dest block has a PHI and where the phi |
| 1012 | // has shared immediate operands. |
| 1013 | TerminatorInst *BBTI = BB.getTerminator(); |
| 1014 | if (BBTI->getNumSuccessors() > 1) { |
| 1015 | for (unsigned i = 0, e = BBTI->getNumSuccessors(); i != e; ++i) |
| 1016 | if (isa<PHINode>(BBTI->getSuccessor(i)->begin()) && |
| 1017 | isCriticalEdge(BBTI, i, true)) |
| 1018 | SplitEdgeNicely(BBTI, i, this); |
| 1019 | } |
| 1020 | |
| 1021 | |
Chris Lattner | dd77df3 | 2007-04-13 20:30:56 +0000 | [diff] [blame] | 1022 | // Keep track of non-local addresses that have been sunk into this block. |
| 1023 | // This allows us to avoid inserting duplicate code for blocks with multiple |
| 1024 | // load/stores of the same address. |
| 1025 | DenseMap<Value*, Value*> SunkAddrs; |
| 1026 | |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 1027 | for (BasicBlock::iterator BBI = BB.begin(), E = BB.end(); BBI != E; ) { |
| 1028 | Instruction *I = BBI++; |
| 1029 | |
Chris Lattner | dd77df3 | 2007-04-13 20:30:56 +0000 | [diff] [blame] | 1030 | if (CastInst *CI = dyn_cast<CastInst>(I)) { |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 1031 | // If the source of the cast is a constant, then this should have |
| 1032 | // already been constant folded. The only reason NOT to constant fold |
| 1033 | // it is if something (e.g. LSR) was careful to place the constant |
| 1034 | // evaluation in a block other than then one that uses it (e.g. to hoist |
| 1035 | // the address of globals out of a loop). If this is the case, we don't |
| 1036 | // want to forward-subst the cast. |
| 1037 | if (isa<Constant>(CI->getOperand(0))) |
| 1038 | continue; |
| 1039 | |
Evan Cheng | bdcb726 | 2007-12-05 23:58:20 +0000 | [diff] [blame] | 1040 | bool Change = false; |
| 1041 | if (TLI) { |
| 1042 | Change = OptimizeNoopCopyExpression(CI, *TLI); |
| 1043 | MadeChange |= Change; |
| 1044 | } |
| 1045 | |
| 1046 | if (OptExtUses && !Change && (isa<ZExtInst>(I) || isa<SExtInst>(I))) |
| 1047 | MadeChange |= OptimizeExtUses(I); |
Dale Johannesen | ce0b237 | 2007-06-12 16:50:17 +0000 | [diff] [blame] | 1048 | } else if (CmpInst *CI = dyn_cast<CmpInst>(I)) { |
| 1049 | MadeChange |= OptimizeCmpExpression(CI); |
Chris Lattner | dd77df3 | 2007-04-13 20:30:56 +0000 | [diff] [blame] | 1050 | } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { |
| 1051 | if (TLI) |
| 1052 | MadeChange |= OptimizeLoadStoreInst(I, I->getOperand(0), LI->getType(), |
| 1053 | SunkAddrs); |
| 1054 | } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { |
| 1055 | if (TLI) |
| 1056 | MadeChange |= OptimizeLoadStoreInst(I, SI->getOperand(1), |
| 1057 | SI->getOperand(0)->getType(), |
| 1058 | SunkAddrs); |
| 1059 | } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { |
Chris Lattner | f25646b | 2007-04-14 00:17:39 +0000 | [diff] [blame] | 1060 | if (GEPI->hasAllZeroIndices()) { |
Chris Lattner | dd77df3 | 2007-04-13 20:30:56 +0000 | [diff] [blame] | 1061 | /// The GEP operand must be a pointer, so must its result -> BitCast |
| 1062 | Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(), |
| 1063 | GEPI->getName(), GEPI); |
| 1064 | GEPI->replaceAllUsesWith(NC); |
| 1065 | GEPI->eraseFromParent(); |
| 1066 | MadeChange = true; |
| 1067 | BBI = NC; |
| 1068 | } |
| 1069 | } else if (CallInst *CI = dyn_cast<CallInst>(I)) { |
| 1070 | // If we found an inline asm expession, and if the target knows how to |
| 1071 | // lower it to normal LLVM code, do so now. |
| 1072 | if (TLI && isa<InlineAsm>(CI->getCalledValue())) |
| 1073 | if (const TargetAsmInfo *TAI = |
| 1074 | TLI->getTargetMachine().getTargetAsmInfo()) { |
| 1075 | if (TAI->ExpandInlineAsm(CI)) |
| 1076 | BBI = BB.begin(); |
| 1077 | } |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 1078 | } |
| 1079 | } |
Chris Lattner | dd77df3 | 2007-04-13 20:30:56 +0000 | [diff] [blame] | 1080 | |
Chris Lattner | dbe0dec | 2007-03-31 04:06:36 +0000 | [diff] [blame] | 1081 | return MadeChange; |
| 1082 | } |
| 1083 | |