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