CodeGenPrepare.cpp revision 44ab89eb376af838d1123293a79975aede501464
1//===- CodeGenPrepare.cpp - Prepare a function for code generation --------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// 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/InlineAsm.h" 22#include "llvm/Instructions.h" 23#include "llvm/IntrinsicInst.h" 24#include "llvm/Pass.h" 25#include "llvm/Analysis/ProfileInfo.h" 26#include "llvm/Target/TargetData.h" 27#include "llvm/Target/TargetLowering.h" 28#include "llvm/Transforms/Utils/AddrModeMatcher.h" 29#include "llvm/Transforms/Utils/BasicBlockUtils.h" 30#include "llvm/Transforms/Utils/Local.h" 31#include "llvm/Transforms/Utils/BuildLibCalls.h" 32#include "llvm/ADT/DenseMap.h" 33#include "llvm/ADT/SmallSet.h" 34#include "llvm/ADT/Statistic.h" 35#include "llvm/Assembly/Writer.h" 36#include "llvm/Support/CallSite.h" 37#include "llvm/Support/CommandLine.h" 38#include "llvm/Support/Debug.h" 39#include "llvm/Support/GetElementPtrTypeIterator.h" 40#include "llvm/Support/PatternMatch.h" 41#include "llvm/Support/raw_ostream.h" 42#include "llvm/Support/IRBuilder.h" 43using namespace llvm; 44using namespace llvm::PatternMatch; 45 46STATISTIC(NumElim, "Number of blocks eliminated"); 47 48static cl::opt<bool> 49CriticalEdgeSplit("cgp-critical-edge-splitting", 50 cl::desc("Split critical edges during codegen prepare"), 51 cl::init(false), cl::Hidden); 52 53namespace { 54 class CodeGenPrepare : public FunctionPass { 55 /// TLI - Keep a pointer of a TargetLowering to consult for determining 56 /// transformation profitability. 57 const TargetLowering *TLI; 58 ProfileInfo *PFI; 59 60 /// BackEdges - Keep a set of all the loop back edges. 61 /// 62 SmallSet<std::pair<const BasicBlock*, const BasicBlock*>, 8> BackEdges; 63 public: 64 static char ID; // Pass identification, replacement for typeid 65 explicit CodeGenPrepare(const TargetLowering *tli = 0) 66 : FunctionPass(ID), TLI(tli) { 67 initializeCodeGenPreparePass(*PassRegistry::getPassRegistry()); 68 } 69 bool runOnFunction(Function &F); 70 71 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 72 AU.addPreserved<ProfileInfo>(); 73 } 74 75 virtual void releaseMemory() { 76 BackEdges.clear(); 77 } 78 79 private: 80 bool EliminateMostlyEmptyBlocks(Function &F); 81 bool CanMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const; 82 void EliminateMostlyEmptyBlock(BasicBlock *BB); 83 bool OptimizeBlock(BasicBlock &BB); 84 bool OptimizeMemoryInst(Instruction *I, Value *Addr, const Type *AccessTy, 85 DenseMap<Value*,Value*> &SunkAddrs); 86 bool OptimizeInlineAsmInst(Instruction *I, CallSite CS, 87 DenseMap<Value*,Value*> &SunkAddrs); 88 bool OptimizeCallInst(CallInst *CI); 89 bool MoveExtToFormExtLoad(Instruction *I); 90 bool OptimizeExtUses(Instruction *I); 91 void findLoopBackEdges(const Function &F); 92 }; 93} 94 95char CodeGenPrepare::ID = 0; 96INITIALIZE_PASS(CodeGenPrepare, "codegenprepare", 97 "Optimize for code generation", false, false) 98 99FunctionPass *llvm::createCodeGenPreparePass(const TargetLowering *TLI) { 100 return new CodeGenPrepare(TLI); 101} 102 103/// findLoopBackEdges - Do a DFS walk to find loop back edges. 104/// 105void CodeGenPrepare::findLoopBackEdges(const Function &F) { 106 SmallVector<std::pair<const BasicBlock*,const BasicBlock*>, 32> Edges; 107 FindFunctionBackedges(F, Edges); 108 109 BackEdges.insert(Edges.begin(), Edges.end()); 110} 111 112 113bool CodeGenPrepare::runOnFunction(Function &F) { 114 bool EverMadeChange = false; 115 116 PFI = getAnalysisIfAvailable<ProfileInfo>(); 117 // First pass, eliminate blocks that contain only PHI nodes and an 118 // unconditional branch. 119 EverMadeChange |= EliminateMostlyEmptyBlocks(F); 120 121 // Now find loop back edges. 122 findLoopBackEdges(F); 123 124 bool MadeChange = true; 125 while (MadeChange) { 126 MadeChange = false; 127 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 128 MadeChange |= OptimizeBlock(*BB); 129 EverMadeChange |= MadeChange; 130 } 131 return EverMadeChange; 132} 133 134/// EliminateMostlyEmptyBlocks - eliminate blocks that contain only PHI nodes, 135/// debug info directives, and an unconditional branch. Passes before isel 136/// (e.g. LSR/loopsimplify) often split edges in ways that are non-optimal for 137/// isel. Start by eliminating these blocks so we can split them the way we 138/// want them. 139bool CodeGenPrepare::EliminateMostlyEmptyBlocks(Function &F) { 140 bool MadeChange = false; 141 // Note that this intentionally skips the entry block. 142 for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ) { 143 BasicBlock *BB = I++; 144 145 // If this block doesn't end with an uncond branch, ignore it. 146 BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 147 if (!BI || !BI->isUnconditional()) 148 continue; 149 150 // If the instruction before the branch (skipping debug info) isn't a phi 151 // node, then other stuff is happening here. 152 BasicBlock::iterator BBI = BI; 153 if (BBI != BB->begin()) { 154 --BBI; 155 while (isa<DbgInfoIntrinsic>(BBI)) { 156 if (BBI == BB->begin()) 157 break; 158 --BBI; 159 } 160 if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI)) 161 continue; 162 } 163 164 // Do not break infinite loops. 165 BasicBlock *DestBB = BI->getSuccessor(0); 166 if (DestBB == BB) 167 continue; 168 169 if (!CanMergeBlocks(BB, DestBB)) 170 continue; 171 172 EliminateMostlyEmptyBlock(BB); 173 MadeChange = true; 174 } 175 return MadeChange; 176} 177 178/// CanMergeBlocks - Return true if we can merge BB into DestBB if there is a 179/// single uncond branch between them, and BB contains no other non-phi 180/// instructions. 181bool CodeGenPrepare::CanMergeBlocks(const BasicBlock *BB, 182 const BasicBlock *DestBB) const { 183 // We only want to eliminate blocks whose phi nodes are used by phi nodes in 184 // the successor. If there are more complex condition (e.g. preheaders), 185 // don't mess around with them. 186 BasicBlock::const_iterator BBI = BB->begin(); 187 while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 188 for (Value::const_use_iterator UI = PN->use_begin(), E = PN->use_end(); 189 UI != E; ++UI) { 190 const Instruction *User = cast<Instruction>(*UI); 191 if (User->getParent() != DestBB || !isa<PHINode>(User)) 192 return false; 193 // If User is inside DestBB block and it is a PHINode then check 194 // incoming value. If incoming value is not from BB then this is 195 // a complex condition (e.g. preheaders) we want to avoid here. 196 if (User->getParent() == DestBB) { 197 if (const PHINode *UPN = dyn_cast<PHINode>(User)) 198 for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) { 199 Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I)); 200 if (Insn && Insn->getParent() == BB && 201 Insn->getParent() != UPN->getIncomingBlock(I)) 202 return false; 203 } 204 } 205 } 206 } 207 208 // If BB and DestBB contain any common predecessors, then the phi nodes in BB 209 // and DestBB may have conflicting incoming values for the block. If so, we 210 // can't merge the block. 211 const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin()); 212 if (!DestBBPN) return true; // no conflict. 213 214 // Collect the preds of BB. 215 SmallPtrSet<const BasicBlock*, 16> BBPreds; 216 if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 217 // It is faster to get preds from a PHI than with pred_iterator. 218 for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 219 BBPreds.insert(BBPN->getIncomingBlock(i)); 220 } else { 221 BBPreds.insert(pred_begin(BB), pred_end(BB)); 222 } 223 224 // Walk the preds of DestBB. 225 for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) { 226 BasicBlock *Pred = DestBBPN->getIncomingBlock(i); 227 if (BBPreds.count(Pred)) { // Common predecessor? 228 BBI = DestBB->begin(); 229 while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 230 const Value *V1 = PN->getIncomingValueForBlock(Pred); 231 const Value *V2 = PN->getIncomingValueForBlock(BB); 232 233 // If V2 is a phi node in BB, look up what the mapped value will be. 234 if (const PHINode *V2PN = dyn_cast<PHINode>(V2)) 235 if (V2PN->getParent() == BB) 236 V2 = V2PN->getIncomingValueForBlock(Pred); 237 238 // If there is a conflict, bail out. 239 if (V1 != V2) return false; 240 } 241 } 242 } 243 244 return true; 245} 246 247 248/// EliminateMostlyEmptyBlock - Eliminate a basic block that have only phi's and 249/// an unconditional branch in it. 250void CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) { 251 BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 252 BasicBlock *DestBB = BI->getSuccessor(0); 253 254 DEBUG(dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB); 255 256 // If the destination block has a single pred, then this is a trivial edge, 257 // just collapse it. 258 if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) { 259 if (SinglePred != DestBB) { 260 // Remember if SinglePred was the entry block of the function. If so, we 261 // will need to move BB back to the entry position. 262 bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock(); 263 MergeBasicBlockIntoOnlyPred(DestBB, this); 264 265 if (isEntry && BB != &BB->getParent()->getEntryBlock()) 266 BB->moveBefore(&BB->getParent()->getEntryBlock()); 267 268 DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n"); 269 return; 270 } 271 } 272 273 // Otherwise, we have multiple predecessors of BB. Update the PHIs in DestBB 274 // to handle the new incoming edges it is about to have. 275 PHINode *PN; 276 for (BasicBlock::iterator BBI = DestBB->begin(); 277 (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 278 // Remove the incoming value for BB, and remember it. 279 Value *InVal = PN->removeIncomingValue(BB, false); 280 281 // Two options: either the InVal is a phi node defined in BB or it is some 282 // value that dominates BB. 283 PHINode *InValPhi = dyn_cast<PHINode>(InVal); 284 if (InValPhi && InValPhi->getParent() == BB) { 285 // Add all of the input values of the input PHI as inputs of this phi. 286 for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i) 287 PN->addIncoming(InValPhi->getIncomingValue(i), 288 InValPhi->getIncomingBlock(i)); 289 } else { 290 // Otherwise, add one instance of the dominating value for each edge that 291 // we will be adding. 292 if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 293 for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 294 PN->addIncoming(InVal, BBPN->getIncomingBlock(i)); 295 } else { 296 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 297 PN->addIncoming(InVal, *PI); 298 } 299 } 300 } 301 302 // The PHIs are now updated, change everything that refers to BB to use 303 // DestBB and remove BB. 304 BB->replaceAllUsesWith(DestBB); 305 if (PFI) { 306 PFI->replaceAllUses(BB, DestBB); 307 PFI->removeEdge(ProfileInfo::getEdge(BB, DestBB)); 308 } 309 BB->eraseFromParent(); 310 ++NumElim; 311 312 DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n"); 313} 314 315/// FindReusablePredBB - Check all of the predecessors of the block DestPHI 316/// lives in to see if there is a block that we can reuse as a critical edge 317/// from TIBB. 318static BasicBlock *FindReusablePredBB(PHINode *DestPHI, BasicBlock *TIBB) { 319 BasicBlock *Dest = DestPHI->getParent(); 320 321 /// TIPHIValues - This array is lazily computed to determine the values of 322 /// PHIs in Dest that TI would provide. 323 SmallVector<Value*, 32> TIPHIValues; 324 325 /// TIBBEntryNo - This is a cache to speed up pred queries for TIBB. 326 unsigned TIBBEntryNo = 0; 327 328 // Check to see if Dest has any blocks that can be used as a split edge for 329 // this terminator. 330 for (unsigned pi = 0, e = DestPHI->getNumIncomingValues(); pi != e; ++pi) { 331 BasicBlock *Pred = DestPHI->getIncomingBlock(pi); 332 // To be usable, the pred has to end with an uncond branch to the dest. 333 BranchInst *PredBr = dyn_cast<BranchInst>(Pred->getTerminator()); 334 if (!PredBr || !PredBr->isUnconditional()) 335 continue; 336 // Must be empty other than the branch and debug info. 337 BasicBlock::iterator I = Pred->begin(); 338 while (isa<DbgInfoIntrinsic>(I)) 339 I++; 340 if (&*I != PredBr) 341 continue; 342 // Cannot be the entry block; its label does not get emitted. 343 if (Pred == &Dest->getParent()->getEntryBlock()) 344 continue; 345 346 // Finally, since we know that Dest has phi nodes in it, we have to make 347 // sure that jumping to Pred will have the same effect as going to Dest in 348 // terms of PHI values. 349 PHINode *PN; 350 unsigned PHINo = 0; 351 unsigned PredEntryNo = pi; 352 353 bool FoundMatch = true; 354 for (BasicBlock::iterator I = Dest->begin(); 355 (PN = dyn_cast<PHINode>(I)); ++I, ++PHINo) { 356 if (PHINo == TIPHIValues.size()) { 357 if (PN->getIncomingBlock(TIBBEntryNo) != TIBB) 358 TIBBEntryNo = PN->getBasicBlockIndex(TIBB); 359 TIPHIValues.push_back(PN->getIncomingValue(TIBBEntryNo)); 360 } 361 362 // If the PHI entry doesn't work, we can't use this pred. 363 if (PN->getIncomingBlock(PredEntryNo) != Pred) 364 PredEntryNo = PN->getBasicBlockIndex(Pred); 365 366 if (TIPHIValues[PHINo] != PN->getIncomingValue(PredEntryNo)) { 367 FoundMatch = false; 368 break; 369 } 370 } 371 372 // If we found a workable predecessor, change TI to branch to Succ. 373 if (FoundMatch) 374 return Pred; 375 } 376 return 0; 377} 378 379 380/// SplitEdgeNicely - Split the critical edge from TI to its specified 381/// successor if it will improve codegen. We only do this if the successor has 382/// phi nodes (otherwise critical edges are ok). If there is already another 383/// predecessor of the succ that is empty (and thus has no phi nodes), use it 384/// instead of introducing a new block. 385static void SplitEdgeNicely(TerminatorInst *TI, unsigned SuccNum, 386 SmallSet<std::pair<const BasicBlock*, 387 const BasicBlock*>, 8> &BackEdges, 388 Pass *P) { 389 BasicBlock *TIBB = TI->getParent(); 390 BasicBlock *Dest = TI->getSuccessor(SuccNum); 391 assert(isa<PHINode>(Dest->begin()) && 392 "This should only be called if Dest has a PHI!"); 393 PHINode *DestPHI = cast<PHINode>(Dest->begin()); 394 395 // Do not split edges to EH landing pads. 396 if (InvokeInst *Invoke = dyn_cast<InvokeInst>(TI)) 397 if (Invoke->getSuccessor(1) == Dest) 398 return; 399 400 // As a hack, never split backedges of loops. Even though the copy for any 401 // PHIs inserted on the backedge would be dead for exits from the loop, we 402 // assume that the cost of *splitting* the backedge would be too high. 403 if (BackEdges.count(std::make_pair(TIBB, Dest))) 404 return; 405 406 if (BasicBlock *ReuseBB = FindReusablePredBB(DestPHI, TIBB)) { 407 ProfileInfo *PFI = P->getAnalysisIfAvailable<ProfileInfo>(); 408 if (PFI) 409 PFI->splitEdge(TIBB, Dest, ReuseBB); 410 Dest->removePredecessor(TIBB); 411 TI->setSuccessor(SuccNum, ReuseBB); 412 return; 413 } 414 415 SplitCriticalEdge(TI, SuccNum, P, true); 416} 417 418 419/// OptimizeNoopCopyExpression - If the specified cast instruction is a noop 420/// copy (e.g. it's casting from one pointer type to another, i32->i8 on PPC), 421/// sink it into user blocks to reduce the number of virtual 422/// registers that must be created and coalesced. 423/// 424/// Return true if any changes are made. 425/// 426static bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI){ 427 // If this is a noop copy, 428 EVT SrcVT = TLI.getValueType(CI->getOperand(0)->getType()); 429 EVT DstVT = TLI.getValueType(CI->getType()); 430 431 // This is an fp<->int conversion? 432 if (SrcVT.isInteger() != DstVT.isInteger()) 433 return false; 434 435 // If this is an extension, it will be a zero or sign extension, which 436 // isn't a noop. 437 if (SrcVT.bitsLT(DstVT)) return false; 438 439 // If these values will be promoted, find out what they will be promoted 440 // to. This helps us consider truncates on PPC as noop copies when they 441 // are. 442 if (TLI.getTypeAction(SrcVT) == TargetLowering::Promote) 443 SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT); 444 if (TLI.getTypeAction(DstVT) == TargetLowering::Promote) 445 DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT); 446 447 // If, after promotion, these are the same types, this is a noop copy. 448 if (SrcVT != DstVT) 449 return false; 450 451 BasicBlock *DefBB = CI->getParent(); 452 453 /// InsertedCasts - Only insert a cast in each block once. 454 DenseMap<BasicBlock*, CastInst*> InsertedCasts; 455 456 bool MadeChange = false; 457 for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 458 UI != E; ) { 459 Use &TheUse = UI.getUse(); 460 Instruction *User = cast<Instruction>(*UI); 461 462 // Figure out which BB this cast is used in. For PHI's this is the 463 // appropriate predecessor block. 464 BasicBlock *UserBB = User->getParent(); 465 if (PHINode *PN = dyn_cast<PHINode>(User)) { 466 UserBB = PN->getIncomingBlock(UI); 467 } 468 469 // Preincrement use iterator so we don't invalidate it. 470 ++UI; 471 472 // If this user is in the same block as the cast, don't change the cast. 473 if (UserBB == DefBB) continue; 474 475 // If we have already inserted a cast into this block, use it. 476 CastInst *&InsertedCast = InsertedCasts[UserBB]; 477 478 if (!InsertedCast) { 479 BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 480 481 InsertedCast = 482 CastInst::Create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "", 483 InsertPt); 484 MadeChange = true; 485 } 486 487 // Replace a use of the cast with a use of the new cast. 488 TheUse = InsertedCast; 489 } 490 491 // If we removed all uses, nuke the cast. 492 if (CI->use_empty()) { 493 CI->eraseFromParent(); 494 MadeChange = true; 495 } 496 497 return MadeChange; 498} 499 500/// OptimizeCmpExpression - sink the given CmpInst into user blocks to reduce 501/// the number of virtual registers that must be created and coalesced. This is 502/// a clear win except on targets with multiple condition code registers 503/// (PowerPC), where it might lose; some adjustment may be wanted there. 504/// 505/// Return true if any changes are made. 506static bool OptimizeCmpExpression(CmpInst *CI) { 507 BasicBlock *DefBB = CI->getParent(); 508 509 /// InsertedCmp - Only insert a cmp in each block once. 510 DenseMap<BasicBlock*, CmpInst*> InsertedCmps; 511 512 bool MadeChange = false; 513 for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 514 UI != E; ) { 515 Use &TheUse = UI.getUse(); 516 Instruction *User = cast<Instruction>(*UI); 517 518 // Preincrement use iterator so we don't invalidate it. 519 ++UI; 520 521 // Don't bother for PHI nodes. 522 if (isa<PHINode>(User)) 523 continue; 524 525 // Figure out which BB this cmp is used in. 526 BasicBlock *UserBB = User->getParent(); 527 528 // If this user is in the same block as the cmp, don't change the cmp. 529 if (UserBB == DefBB) continue; 530 531 // If we have already inserted a cmp into this block, use it. 532 CmpInst *&InsertedCmp = InsertedCmps[UserBB]; 533 534 if (!InsertedCmp) { 535 BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 536 537 InsertedCmp = 538 CmpInst::Create(CI->getOpcode(), 539 CI->getPredicate(), CI->getOperand(0), 540 CI->getOperand(1), "", InsertPt); 541 MadeChange = true; 542 } 543 544 // Replace a use of the cmp with a use of the new cmp. 545 TheUse = InsertedCmp; 546 } 547 548 // If we removed all uses, nuke the cmp. 549 if (CI->use_empty()) 550 CI->eraseFromParent(); 551 552 return MadeChange; 553} 554 555namespace { 556class CodeGenPrepareFortifiedLibCalls : public SimplifyFortifiedLibCalls { 557protected: 558 void replaceCall(Value *With) { 559 CI->replaceAllUsesWith(With); 560 CI->eraseFromParent(); 561 } 562 bool isFoldable(unsigned SizeCIOp, unsigned, bool) const { 563 if (ConstantInt *SizeCI = 564 dyn_cast<ConstantInt>(CI->getArgOperand(SizeCIOp))) 565 return SizeCI->isAllOnesValue(); 566 return false; 567 } 568}; 569} // end anonymous namespace 570 571bool CodeGenPrepare::OptimizeCallInst(CallInst *CI) { 572 // Lower all uses of llvm.objectsize.* 573 IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI); 574 if (II && II->getIntrinsicID() == Intrinsic::objectsize) { 575 bool Min = (cast<ConstantInt>(II->getArgOperand(1))->getZExtValue() == 1); 576 const Type *ReturnTy = CI->getType(); 577 Constant *RetVal = ConstantInt::get(ReturnTy, Min ? 0 : -1ULL); 578 CI->replaceAllUsesWith(RetVal); 579 CI->eraseFromParent(); 580 return true; 581 } 582 583 // From here on out we're working with named functions. 584 if (CI->getCalledFunction() == 0) return false; 585 586 // We'll need TargetData from here on out. 587 const TargetData *TD = TLI ? TLI->getTargetData() : 0; 588 if (!TD) return false; 589 590 // Lower all default uses of _chk calls. This is very similar 591 // to what InstCombineCalls does, but here we are only lowering calls 592 // that have the default "don't know" as the objectsize. Anything else 593 // should be left alone. 594 CodeGenPrepareFortifiedLibCalls Simplifier; 595 return Simplifier.fold(CI, TD); 596} 597//===----------------------------------------------------------------------===// 598// Memory Optimization 599//===----------------------------------------------------------------------===// 600 601/// IsNonLocalValue - Return true if the specified values are defined in a 602/// different basic block than BB. 603static bool IsNonLocalValue(Value *V, BasicBlock *BB) { 604 if (Instruction *I = dyn_cast<Instruction>(V)) 605 return I->getParent() != BB; 606 return false; 607} 608 609/// OptimizeMemoryInst - Load and Store Instructions often have 610/// addressing modes that can do significant amounts of computation. As such, 611/// instruction selection will try to get the load or store to do as much 612/// computation as possible for the program. The problem is that isel can only 613/// see within a single block. As such, we sink as much legal addressing mode 614/// stuff into the block as possible. 615/// 616/// This method is used to optimize both load/store and inline asms with memory 617/// operands. 618bool CodeGenPrepare::OptimizeMemoryInst(Instruction *MemoryInst, Value *Addr, 619 const Type *AccessTy, 620 DenseMap<Value*,Value*> &SunkAddrs) { 621 // Figure out what addressing mode will be built up for this operation. 622 SmallVector<Instruction*, 16> AddrModeInsts; 623 ExtAddrMode AddrMode = AddressingModeMatcher::Match(Addr, AccessTy,MemoryInst, 624 AddrModeInsts, *TLI); 625 626 // Check to see if any of the instructions supersumed by this addr mode are 627 // non-local to I's BB. 628 bool AnyNonLocal = false; 629 for (unsigned i = 0, e = AddrModeInsts.size(); i != e; ++i) { 630 if (IsNonLocalValue(AddrModeInsts[i], MemoryInst->getParent())) { 631 AnyNonLocal = true; 632 break; 633 } 634 } 635 636 // If all the instructions matched are already in this BB, don't do anything. 637 if (!AnyNonLocal) { 638 DEBUG(dbgs() << "CGP: Found local addrmode: " << AddrMode << "\n"); 639 return false; 640 } 641 642 // Insert this computation right after this user. Since our caller is 643 // scanning from the top of the BB to the bottom, reuse of the expr are 644 // guaranteed to happen later. 645 BasicBlock::iterator InsertPt = MemoryInst; 646 647 // Now that we determined the addressing expression we want to use and know 648 // that we have to sink it into this block. Check to see if we have already 649 // done this for some other load/store instr in this block. If so, reuse the 650 // computation. 651 Value *&SunkAddr = SunkAddrs[Addr]; 652 if (SunkAddr) { 653 DEBUG(dbgs() << "CGP: Reusing nonlocal addrmode: " << AddrMode << " for " 654 << *MemoryInst); 655 if (SunkAddr->getType() != Addr->getType()) 656 SunkAddr = new BitCastInst(SunkAddr, Addr->getType(), "tmp", InsertPt); 657 } else { 658 DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for " 659 << *MemoryInst); 660 const Type *IntPtrTy = 661 TLI->getTargetData()->getIntPtrType(AccessTy->getContext()); 662 663 Value *Result = 0; 664 665 // Start with the base register. Do this first so that subsequent address 666 // matching finds it last, which will prevent it from trying to match it 667 // as the scaled value in case it happens to be a mul. That would be 668 // problematic if we've sunk a different mul for the scale, because then 669 // we'd end up sinking both muls. 670 if (AddrMode.BaseReg) { 671 Value *V = AddrMode.BaseReg; 672 if (V->getType()->isPointerTy()) 673 V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt); 674 if (V->getType() != IntPtrTy) 675 V = CastInst::CreateIntegerCast(V, IntPtrTy, /*isSigned=*/true, 676 "sunkaddr", InsertPt); 677 Result = V; 678 } 679 680 // Add the scale value. 681 if (AddrMode.Scale) { 682 Value *V = AddrMode.ScaledReg; 683 if (V->getType() == IntPtrTy) { 684 // done. 685 } else if (V->getType()->isPointerTy()) { 686 V = new PtrToIntInst(V, IntPtrTy, "sunkaddr", InsertPt); 687 } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() < 688 cast<IntegerType>(V->getType())->getBitWidth()) { 689 V = new TruncInst(V, IntPtrTy, "sunkaddr", InsertPt); 690 } else { 691 V = new SExtInst(V, IntPtrTy, "sunkaddr", InsertPt); 692 } 693 if (AddrMode.Scale != 1) 694 V = BinaryOperator::CreateMul(V, ConstantInt::get(IntPtrTy, 695 AddrMode.Scale), 696 "sunkaddr", InsertPt); 697 if (Result) 698 Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 699 else 700 Result = V; 701 } 702 703 // Add in the BaseGV if present. 704 if (AddrMode.BaseGV) { 705 Value *V = new PtrToIntInst(AddrMode.BaseGV, IntPtrTy, "sunkaddr", 706 InsertPt); 707 if (Result) 708 Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 709 else 710 Result = V; 711 } 712 713 // Add in the Base Offset if present. 714 if (AddrMode.BaseOffs) { 715 Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs); 716 if (Result) 717 Result = BinaryOperator::CreateAdd(Result, V, "sunkaddr", InsertPt); 718 else 719 Result = V; 720 } 721 722 if (Result == 0) 723 SunkAddr = Constant::getNullValue(Addr->getType()); 724 else 725 SunkAddr = new IntToPtrInst(Result, Addr->getType(), "sunkaddr",InsertPt); 726 } 727 728 MemoryInst->replaceUsesOfWith(Addr, SunkAddr); 729 730 if (Addr->use_empty()) { 731 RecursivelyDeleteTriviallyDeadInstructions(Addr); 732 // This address is now available for reassignment, so erase the table entry; 733 // we don't want to match some completely different instruction. 734 SunkAddrs[Addr] = 0; 735 } 736 return true; 737} 738 739/// OptimizeInlineAsmInst - If there are any memory operands, use 740/// OptimizeMemoryInst to sink their address computing into the block when 741/// possible / profitable. 742bool CodeGenPrepare::OptimizeInlineAsmInst(Instruction *I, CallSite CS, 743 DenseMap<Value*,Value*> &SunkAddrs) { 744 bool MadeChange = false; 745 746 TargetLowering::AsmOperandInfoVector TargetConstraints = TLI->ParseConstraints(CS); 747 unsigned ArgNo = 0; 748 for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) { 749 TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i]; 750 751 // Compute the constraint code and ConstraintType to use. 752 TLI->ComputeConstraintToUse(OpInfo, SDValue()); 753 754 if (OpInfo.ConstraintType == TargetLowering::C_Memory && 755 OpInfo.isIndirect) { 756 Value *OpVal = const_cast<Value *>(CS.getArgument(ArgNo++)); 757 MadeChange |= OptimizeMemoryInst(I, OpVal, OpVal->getType(), SunkAddrs); 758 } else if (OpInfo.Type == InlineAsm::isInput) 759 ArgNo++; 760 } 761 762 return MadeChange; 763} 764 765/// MoveExtToFormExtLoad - Move a zext or sext fed by a load into the same 766/// basic block as the load, unless conditions are unfavorable. This allows 767/// SelectionDAG to fold the extend into the load. 768/// 769bool CodeGenPrepare::MoveExtToFormExtLoad(Instruction *I) { 770 // Look for a load being extended. 771 LoadInst *LI = dyn_cast<LoadInst>(I->getOperand(0)); 772 if (!LI) return false; 773 774 // If they're already in the same block, there's nothing to do. 775 if (LI->getParent() == I->getParent()) 776 return false; 777 778 // If the load has other users and the truncate is not free, this probably 779 // isn't worthwhile. 780 if (!LI->hasOneUse() && 781 TLI && (TLI->isTypeLegal(TLI->getValueType(LI->getType())) || 782 !TLI->isTypeLegal(TLI->getValueType(I->getType()))) && 783 !TLI->isTruncateFree(I->getType(), LI->getType())) 784 return false; 785 786 // Check whether the target supports casts folded into loads. 787 unsigned LType; 788 if (isa<ZExtInst>(I)) 789 LType = ISD::ZEXTLOAD; 790 else { 791 assert(isa<SExtInst>(I) && "Unexpected ext type!"); 792 LType = ISD::SEXTLOAD; 793 } 794 if (TLI && !TLI->isLoadExtLegal(LType, TLI->getValueType(LI->getType()))) 795 return false; 796 797 // Move the extend into the same block as the load, so that SelectionDAG 798 // can fold it. 799 I->removeFromParent(); 800 I->insertAfter(LI); 801 return true; 802} 803 804bool CodeGenPrepare::OptimizeExtUses(Instruction *I) { 805 BasicBlock *DefBB = I->getParent(); 806 807 // If the result of a {s|z}ext and its source are both live out, rewrite all 808 // other uses of the source with result of extension. 809 Value *Src = I->getOperand(0); 810 if (Src->hasOneUse()) 811 return false; 812 813 // Only do this xform if truncating is free. 814 if (TLI && !TLI->isTruncateFree(I->getType(), Src->getType())) 815 return false; 816 817 // Only safe to perform the optimization if the source is also defined in 818 // this block. 819 if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->getParent()) 820 return false; 821 822 bool DefIsLiveOut = false; 823 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 824 UI != E; ++UI) { 825 Instruction *User = cast<Instruction>(*UI); 826 827 // Figure out which BB this ext is used in. 828 BasicBlock *UserBB = User->getParent(); 829 if (UserBB == DefBB) continue; 830 DefIsLiveOut = true; 831 break; 832 } 833 if (!DefIsLiveOut) 834 return false; 835 836 // Make sure non of the uses are PHI nodes. 837 for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 838 UI != E; ++UI) { 839 Instruction *User = cast<Instruction>(*UI); 840 BasicBlock *UserBB = User->getParent(); 841 if (UserBB == DefBB) continue; 842 // Be conservative. We don't want this xform to end up introducing 843 // reloads just before load / store instructions. 844 if (isa<PHINode>(User) || isa<LoadInst>(User) || isa<StoreInst>(User)) 845 return false; 846 } 847 848 // InsertedTruncs - Only insert one trunc in each block once. 849 DenseMap<BasicBlock*, Instruction*> InsertedTruncs; 850 851 bool MadeChange = false; 852 for (Value::use_iterator UI = Src->use_begin(), E = Src->use_end(); 853 UI != E; ++UI) { 854 Use &TheUse = UI.getUse(); 855 Instruction *User = cast<Instruction>(*UI); 856 857 // Figure out which BB this ext is used in. 858 BasicBlock *UserBB = User->getParent(); 859 if (UserBB == DefBB) continue; 860 861 // Both src and def are live in this block. Rewrite the use. 862 Instruction *&InsertedTrunc = InsertedTruncs[UserBB]; 863 864 if (!InsertedTrunc) { 865 BasicBlock::iterator InsertPt = UserBB->getFirstNonPHI(); 866 867 InsertedTrunc = new TruncInst(I, Src->getType(), "", InsertPt); 868 } 869 870 // Replace a use of the {s|z}ext source with a use of the result. 871 TheUse = InsertedTrunc; 872 873 MadeChange = true; 874 } 875 876 return MadeChange; 877} 878 879// In this pass we look for GEP and cast instructions that are used 880// across basic blocks and rewrite them to improve basic-block-at-a-time 881// selection. 882bool CodeGenPrepare::OptimizeBlock(BasicBlock &BB) { 883 bool MadeChange = false; 884 885 // Split all critical edges where the dest block has a PHI. 886 if (CriticalEdgeSplit) { 887 TerminatorInst *BBTI = BB.getTerminator(); 888 if (BBTI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(BBTI)) { 889 for (unsigned i = 0, e = BBTI->getNumSuccessors(); i != e; ++i) { 890 BasicBlock *SuccBB = BBTI->getSuccessor(i); 891 if (isa<PHINode>(SuccBB->begin()) && isCriticalEdge(BBTI, i, true)) 892 SplitEdgeNicely(BBTI, i, BackEdges, this); 893 } 894 } 895 } 896 897 // Keep track of non-local addresses that have been sunk into this block. 898 // This allows us to avoid inserting duplicate code for blocks with multiple 899 // load/stores of the same address. 900 DenseMap<Value*, Value*> SunkAddrs; 901 902 for (BasicBlock::iterator BBI = BB.begin(), E = BB.end(); BBI != E; ) { 903 Instruction *I = BBI++; 904 905 if (CastInst *CI = dyn_cast<CastInst>(I)) { 906 // If the source of the cast is a constant, then this should have 907 // already been constant folded. The only reason NOT to constant fold 908 // it is if something (e.g. LSR) was careful to place the constant 909 // evaluation in a block other than then one that uses it (e.g. to hoist 910 // the address of globals out of a loop). If this is the case, we don't 911 // want to forward-subst the cast. 912 if (isa<Constant>(CI->getOperand(0))) 913 continue; 914 915 bool Change = false; 916 if (TLI) { 917 Change = OptimizeNoopCopyExpression(CI, *TLI); 918 MadeChange |= Change; 919 } 920 921 if (!Change && (isa<ZExtInst>(I) || isa<SExtInst>(I))) { 922 MadeChange |= MoveExtToFormExtLoad(I); 923 MadeChange |= OptimizeExtUses(I); 924 } 925 } else if (CmpInst *CI = dyn_cast<CmpInst>(I)) { 926 MadeChange |= OptimizeCmpExpression(CI); 927 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 928 if (TLI) 929 MadeChange |= OptimizeMemoryInst(I, I->getOperand(0), LI->getType(), 930 SunkAddrs); 931 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 932 if (TLI) 933 MadeChange |= OptimizeMemoryInst(I, SI->getOperand(1), 934 SI->getOperand(0)->getType(), 935 SunkAddrs); 936 } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 937 if (GEPI->hasAllZeroIndices()) { 938 /// The GEP operand must be a pointer, so must its result -> BitCast 939 Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(), 940 GEPI->getName(), GEPI); 941 GEPI->replaceAllUsesWith(NC); 942 GEPI->eraseFromParent(); 943 MadeChange = true; 944 BBI = NC; 945 } 946 } else if (CallInst *CI = dyn_cast<CallInst>(I)) { 947 // If we found an inline asm expession, and if the target knows how to 948 // lower it to normal LLVM code, do so now. 949 if (TLI && isa<InlineAsm>(CI->getCalledValue())) { 950 if (TLI->ExpandInlineAsm(CI)) { 951 BBI = BB.begin(); 952 // Avoid processing instructions out of order, which could cause 953 // reuse before a value is defined. 954 SunkAddrs.clear(); 955 } else 956 // Sink address computing for memory operands into the block. 957 MadeChange |= OptimizeInlineAsmInst(I, &(*CI), SunkAddrs); 958 } else { 959 // Other CallInst optimizations that don't need to muck with the 960 // enclosing iterator here. 961 MadeChange |= OptimizeCallInst(CI); 962 } 963 } 964 } 965 966 return MadeChange; 967} 968