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 #include "llvm/CodeGen/Passes.h" 17 #include "llvm/ADT/DenseMap.h" 18 #include "llvm/ADT/SmallSet.h" 19 #include "llvm/ADT/Statistic.h" 20 #include "llvm/Analysis/InstructionSimplify.h" 21 #include "llvm/Analysis/LoopInfo.h" 22 #include "llvm/Analysis/TargetLibraryInfo.h" 23 #include "llvm/Analysis/TargetTransformInfo.h" 24 #include "llvm/Analysis/ValueTracking.h" 25 #include "llvm/Analysis/MemoryBuiltins.h" 26 #include "llvm/IR/CallSite.h" 27 #include "llvm/IR/Constants.h" 28 #include "llvm/IR/DataLayout.h" 29 #include "llvm/IR/DerivedTypes.h" 30 #include "llvm/IR/Dominators.h" 31 #include "llvm/IR/Function.h" 32 #include "llvm/IR/GetElementPtrTypeIterator.h" 33 #include "llvm/IR/IRBuilder.h" 34 #include "llvm/IR/InlineAsm.h" 35 #include "llvm/IR/Instructions.h" 36 #include "llvm/IR/IntrinsicInst.h" 37 #include "llvm/IR/MDBuilder.h" 38 #include "llvm/IR/PatternMatch.h" 39 #include "llvm/IR/Statepoint.h" 40 #include "llvm/IR/ValueHandle.h" 41 #include "llvm/IR/ValueMap.h" 42 #include "llvm/Pass.h" 43 #include "llvm/Support/BranchProbability.h" 44 #include "llvm/Support/CommandLine.h" 45 #include "llvm/Support/Debug.h" 46 #include "llvm/Support/raw_ostream.h" 47 #include "llvm/Target/TargetLowering.h" 48 #include "llvm/Target/TargetSubtargetInfo.h" 49 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 50 #include "llvm/Transforms/Utils/BuildLibCalls.h" 51 #include "llvm/Transforms/Utils/BypassSlowDivision.h" 52 #include "llvm/Transforms/Utils/Local.h" 53 #include "llvm/Transforms/Utils/SimplifyLibCalls.h" 54 using namespace llvm; 55 using namespace llvm::PatternMatch; 56 57 #define DEBUG_TYPE "codegenprepare" 58 59 STATISTIC(NumBlocksElim, "Number of blocks eliminated"); 60 STATISTIC(NumPHIsElim, "Number of trivial PHIs eliminated"); 61 STATISTIC(NumGEPsElim, "Number of GEPs converted to casts"); 62 STATISTIC(NumCmpUses, "Number of uses of Cmp expressions replaced with uses of " 63 "sunken Cmps"); 64 STATISTIC(NumCastUses, "Number of uses of Cast expressions replaced with uses " 65 "of sunken Casts"); 66 STATISTIC(NumMemoryInsts, "Number of memory instructions whose address " 67 "computations were sunk"); 68 STATISTIC(NumExtsMoved, "Number of [s|z]ext instructions combined with loads"); 69 STATISTIC(NumExtUses, "Number of uses of [s|z]ext instructions optimized"); 70 STATISTIC(NumAndsAdded, 71 "Number of and mask instructions added to form ext loads"); 72 STATISTIC(NumAndUses, "Number of uses of and mask instructions optimized"); 73 STATISTIC(NumRetsDup, "Number of return instructions duplicated"); 74 STATISTIC(NumDbgValueMoved, "Number of debug value instructions moved"); 75 STATISTIC(NumSelectsExpanded, "Number of selects turned into branches"); 76 STATISTIC(NumAndCmpsMoved, "Number of and/cmp's pushed into branches"); 77 STATISTIC(NumStoreExtractExposed, "Number of store(extractelement) exposed"); 78 79 static cl::opt<bool> DisableBranchOpts( 80 "disable-cgp-branch-opts", cl::Hidden, cl::init(false), 81 cl::desc("Disable branch optimizations in CodeGenPrepare")); 82 83 static cl::opt<bool> 84 DisableGCOpts("disable-cgp-gc-opts", cl::Hidden, cl::init(false), 85 cl::desc("Disable GC optimizations in CodeGenPrepare")); 86 87 static cl::opt<bool> DisableSelectToBranch( 88 "disable-cgp-select2branch", cl::Hidden, cl::init(false), 89 cl::desc("Disable select to branch conversion.")); 90 91 static cl::opt<bool> AddrSinkUsingGEPs( 92 "addr-sink-using-gep", cl::Hidden, cl::init(false), 93 cl::desc("Address sinking in CGP using GEPs.")); 94 95 static cl::opt<bool> EnableAndCmpSinking( 96 "enable-andcmp-sinking", cl::Hidden, cl::init(true), 97 cl::desc("Enable sinkinig and/cmp into branches.")); 98 99 static cl::opt<bool> DisableStoreExtract( 100 "disable-cgp-store-extract", cl::Hidden, cl::init(false), 101 cl::desc("Disable store(extract) optimizations in CodeGenPrepare")); 102 103 static cl::opt<bool> StressStoreExtract( 104 "stress-cgp-store-extract", cl::Hidden, cl::init(false), 105 cl::desc("Stress test store(extract) optimizations in CodeGenPrepare")); 106 107 static cl::opt<bool> DisableExtLdPromotion( 108 "disable-cgp-ext-ld-promotion", cl::Hidden, cl::init(false), 109 cl::desc("Disable ext(promotable(ld)) -> promoted(ext(ld)) optimization in " 110 "CodeGenPrepare")); 111 112 static cl::opt<bool> StressExtLdPromotion( 113 "stress-cgp-ext-ld-promotion", cl::Hidden, cl::init(false), 114 cl::desc("Stress test ext(promotable(ld)) -> promoted(ext(ld)) " 115 "optimization in CodeGenPrepare")); 116 117 static cl::opt<bool> DisablePreheaderProtect( 118 "disable-preheader-prot", cl::Hidden, cl::init(false), 119 cl::desc("Disable protection against removing loop preheaders")); 120 121 namespace { 122 typedef SmallPtrSet<Instruction *, 16> SetOfInstrs; 123 typedef PointerIntPair<Type *, 1, bool> TypeIsSExt; 124 typedef DenseMap<Instruction *, TypeIsSExt> InstrToOrigTy; 125 class TypePromotionTransaction; 126 127 class CodeGenPrepare : public FunctionPass { 128 const TargetMachine *TM; 129 const TargetLowering *TLI; 130 const TargetTransformInfo *TTI; 131 const TargetLibraryInfo *TLInfo; 132 const LoopInfo *LI; 133 134 /// As we scan instructions optimizing them, this is the next instruction 135 /// to optimize. Transforms that can invalidate this should update it. 136 BasicBlock::iterator CurInstIterator; 137 138 /// Keeps track of non-local addresses that have been sunk into a block. 139 /// This allows us to avoid inserting duplicate code for blocks with 140 /// multiple load/stores of the same address. 141 ValueMap<Value*, Value*> SunkAddrs; 142 143 /// Keeps track of all instructions inserted for the current function. 144 SetOfInstrs InsertedInsts; 145 /// Keeps track of the type of the related instruction before their 146 /// promotion for the current function. 147 InstrToOrigTy PromotedInsts; 148 149 /// True if CFG is modified in any way. 150 bool ModifiedDT; 151 152 /// True if optimizing for size. 153 bool OptSize; 154 155 /// DataLayout for the Function being processed. 156 const DataLayout *DL; 157 158 public: 159 static char ID; // Pass identification, replacement for typeid 160 explicit CodeGenPrepare(const TargetMachine *TM = nullptr) 161 : FunctionPass(ID), TM(TM), TLI(nullptr), TTI(nullptr), DL(nullptr) { 162 initializeCodeGenPreparePass(*PassRegistry::getPassRegistry()); 163 } 164 bool runOnFunction(Function &F) override; 165 166 const char *getPassName() const override { return "CodeGen Prepare"; } 167 168 void getAnalysisUsage(AnalysisUsage &AU) const override { 169 // FIXME: When we can selectively preserve passes, preserve the domtree. 170 AU.addRequired<TargetLibraryInfoWrapperPass>(); 171 AU.addRequired<TargetTransformInfoWrapperPass>(); 172 AU.addRequired<LoopInfoWrapperPass>(); 173 } 174 175 private: 176 bool eliminateFallThrough(Function &F); 177 bool eliminateMostlyEmptyBlocks(Function &F); 178 bool canMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const; 179 void eliminateMostlyEmptyBlock(BasicBlock *BB); 180 bool optimizeBlock(BasicBlock &BB, bool& ModifiedDT); 181 bool optimizeInst(Instruction *I, bool& ModifiedDT); 182 bool optimizeMemoryInst(Instruction *I, Value *Addr, 183 Type *AccessTy, unsigned AS); 184 bool optimizeInlineAsmInst(CallInst *CS); 185 bool optimizeCallInst(CallInst *CI, bool& ModifiedDT); 186 bool moveExtToFormExtLoad(Instruction *&I); 187 bool optimizeExtUses(Instruction *I); 188 bool optimizeLoadExt(LoadInst *I); 189 bool optimizeSelectInst(SelectInst *SI); 190 bool optimizeShuffleVectorInst(ShuffleVectorInst *SI); 191 bool optimizeSwitchInst(SwitchInst *CI); 192 bool optimizeExtractElementInst(Instruction *Inst); 193 bool dupRetToEnableTailCallOpts(BasicBlock *BB); 194 bool placeDbgValues(Function &F); 195 bool sinkAndCmp(Function &F); 196 bool extLdPromotion(TypePromotionTransaction &TPT, LoadInst *&LI, 197 Instruction *&Inst, 198 const SmallVectorImpl<Instruction *> &Exts, 199 unsigned CreatedInstCost); 200 bool splitBranchCondition(Function &F); 201 bool simplifyOffsetableRelocate(Instruction &I); 202 void stripInvariantGroupMetadata(Instruction &I); 203 }; 204 } 205 206 char CodeGenPrepare::ID = 0; 207 INITIALIZE_TM_PASS(CodeGenPrepare, "codegenprepare", 208 "Optimize for code generation", false, false) 209 210 FunctionPass *llvm::createCodeGenPreparePass(const TargetMachine *TM) { 211 return new CodeGenPrepare(TM); 212 } 213 214 bool CodeGenPrepare::runOnFunction(Function &F) { 215 if (skipFunction(F)) 216 return false; 217 218 DL = &F.getParent()->getDataLayout(); 219 220 bool EverMadeChange = false; 221 // Clear per function information. 222 InsertedInsts.clear(); 223 PromotedInsts.clear(); 224 225 ModifiedDT = false; 226 if (TM) 227 TLI = TM->getSubtargetImpl(F)->getTargetLowering(); 228 TLInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); 229 TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 230 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 231 OptSize = F.optForSize(); 232 233 /// This optimization identifies DIV instructions that can be 234 /// profitably bypassed and carried out with a shorter, faster divide. 235 if (!OptSize && TLI && TLI->isSlowDivBypassed()) { 236 const DenseMap<unsigned int, unsigned int> &BypassWidths = 237 TLI->getBypassSlowDivWidths(); 238 BasicBlock* BB = &*F.begin(); 239 while (BB != nullptr) { 240 // bypassSlowDivision may create new BBs, but we don't want to reapply the 241 // optimization to those blocks. 242 BasicBlock* Next = BB->getNextNode(); 243 EverMadeChange |= bypassSlowDivision(BB, BypassWidths); 244 BB = Next; 245 } 246 } 247 248 // Eliminate blocks that contain only PHI nodes and an 249 // unconditional branch. 250 EverMadeChange |= eliminateMostlyEmptyBlocks(F); 251 252 // llvm.dbg.value is far away from the value then iSel may not be able 253 // handle it properly. iSel will drop llvm.dbg.value if it can not 254 // find a node corresponding to the value. 255 EverMadeChange |= placeDbgValues(F); 256 257 // If there is a mask, compare against zero, and branch that can be combined 258 // into a single target instruction, push the mask and compare into branch 259 // users. Do this before OptimizeBlock -> OptimizeInst -> 260 // OptimizeCmpExpression, which perturbs the pattern being searched for. 261 if (!DisableBranchOpts) { 262 EverMadeChange |= sinkAndCmp(F); 263 EverMadeChange |= splitBranchCondition(F); 264 } 265 266 bool MadeChange = true; 267 while (MadeChange) { 268 MadeChange = false; 269 for (Function::iterator I = F.begin(); I != F.end(); ) { 270 BasicBlock *BB = &*I++; 271 bool ModifiedDTOnIteration = false; 272 MadeChange |= optimizeBlock(*BB, ModifiedDTOnIteration); 273 274 // Restart BB iteration if the dominator tree of the Function was changed 275 if (ModifiedDTOnIteration) 276 break; 277 } 278 EverMadeChange |= MadeChange; 279 } 280 281 SunkAddrs.clear(); 282 283 if (!DisableBranchOpts) { 284 MadeChange = false; 285 SmallPtrSet<BasicBlock*, 8> WorkList; 286 for (BasicBlock &BB : F) { 287 SmallVector<BasicBlock *, 2> Successors(succ_begin(&BB), succ_end(&BB)); 288 MadeChange |= ConstantFoldTerminator(&BB, true); 289 if (!MadeChange) continue; 290 291 for (SmallVectorImpl<BasicBlock*>::iterator 292 II = Successors.begin(), IE = Successors.end(); II != IE; ++II) 293 if (pred_begin(*II) == pred_end(*II)) 294 WorkList.insert(*II); 295 } 296 297 // Delete the dead blocks and any of their dead successors. 298 MadeChange |= !WorkList.empty(); 299 while (!WorkList.empty()) { 300 BasicBlock *BB = *WorkList.begin(); 301 WorkList.erase(BB); 302 SmallVector<BasicBlock*, 2> Successors(succ_begin(BB), succ_end(BB)); 303 304 DeleteDeadBlock(BB); 305 306 for (SmallVectorImpl<BasicBlock*>::iterator 307 II = Successors.begin(), IE = Successors.end(); II != IE; ++II) 308 if (pred_begin(*II) == pred_end(*II)) 309 WorkList.insert(*II); 310 } 311 312 // Merge pairs of basic blocks with unconditional branches, connected by 313 // a single edge. 314 if (EverMadeChange || MadeChange) 315 MadeChange |= eliminateFallThrough(F); 316 317 EverMadeChange |= MadeChange; 318 } 319 320 if (!DisableGCOpts) { 321 SmallVector<Instruction *, 2> Statepoints; 322 for (BasicBlock &BB : F) 323 for (Instruction &I : BB) 324 if (isStatepoint(I)) 325 Statepoints.push_back(&I); 326 for (auto &I : Statepoints) 327 EverMadeChange |= simplifyOffsetableRelocate(*I); 328 } 329 330 return EverMadeChange; 331 } 332 333 /// Merge basic blocks which are connected by a single edge, where one of the 334 /// basic blocks has a single successor pointing to the other basic block, 335 /// which has a single predecessor. 336 bool CodeGenPrepare::eliminateFallThrough(Function &F) { 337 bool Changed = false; 338 // Scan all of the blocks in the function, except for the entry block. 339 for (Function::iterator I = std::next(F.begin()), E = F.end(); I != E;) { 340 BasicBlock *BB = &*I++; 341 // If the destination block has a single pred, then this is a trivial 342 // edge, just collapse it. 343 BasicBlock *SinglePred = BB->getSinglePredecessor(); 344 345 // Don't merge if BB's address is taken. 346 if (!SinglePred || SinglePred == BB || BB->hasAddressTaken()) continue; 347 348 BranchInst *Term = dyn_cast<BranchInst>(SinglePred->getTerminator()); 349 if (Term && !Term->isConditional()) { 350 Changed = true; 351 DEBUG(dbgs() << "To merge:\n"<< *SinglePred << "\n\n\n"); 352 // Remember if SinglePred was the entry block of the function. 353 // If so, we will need to move BB back to the entry position. 354 bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock(); 355 MergeBasicBlockIntoOnlyPred(BB, nullptr); 356 357 if (isEntry && BB != &BB->getParent()->getEntryBlock()) 358 BB->moveBefore(&BB->getParent()->getEntryBlock()); 359 360 // We have erased a block. Update the iterator. 361 I = BB->getIterator(); 362 } 363 } 364 return Changed; 365 } 366 367 /// Eliminate blocks that contain only PHI nodes, debug info directives, and an 368 /// unconditional branch. Passes before isel (e.g. LSR/loopsimplify) often split 369 /// edges in ways that are non-optimal for isel. Start by eliminating these 370 /// blocks so we can split them the way we want them. 371 bool CodeGenPrepare::eliminateMostlyEmptyBlocks(Function &F) { 372 SmallPtrSet<BasicBlock *, 16> Preheaders; 373 SmallVector<Loop *, 16> LoopList(LI->begin(), LI->end()); 374 while (!LoopList.empty()) { 375 Loop *L = LoopList.pop_back_val(); 376 LoopList.insert(LoopList.end(), L->begin(), L->end()); 377 if (BasicBlock *Preheader = L->getLoopPreheader()) 378 Preheaders.insert(Preheader); 379 } 380 381 bool MadeChange = false; 382 // Note that this intentionally skips the entry block. 383 for (Function::iterator I = std::next(F.begin()), E = F.end(); I != E;) { 384 BasicBlock *BB = &*I++; 385 386 // If this block doesn't end with an uncond branch, ignore it. 387 BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 388 if (!BI || !BI->isUnconditional()) 389 continue; 390 391 // If the instruction before the branch (skipping debug info) isn't a phi 392 // node, then other stuff is happening here. 393 BasicBlock::iterator BBI = BI->getIterator(); 394 if (BBI != BB->begin()) { 395 --BBI; 396 while (isa<DbgInfoIntrinsic>(BBI)) { 397 if (BBI == BB->begin()) 398 break; 399 --BBI; 400 } 401 if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI)) 402 continue; 403 } 404 405 // Do not break infinite loops. 406 BasicBlock *DestBB = BI->getSuccessor(0); 407 if (DestBB == BB) 408 continue; 409 410 if (!canMergeBlocks(BB, DestBB)) 411 continue; 412 413 // Do not delete loop preheaders if doing so would create a critical edge. 414 // Loop preheaders can be good locations to spill registers. If the 415 // preheader is deleted and we create a critical edge, registers may be 416 // spilled in the loop body instead. 417 if (!DisablePreheaderProtect && Preheaders.count(BB) && 418 !(BB->getSinglePredecessor() && BB->getSinglePredecessor()->getSingleSuccessor())) 419 continue; 420 421 eliminateMostlyEmptyBlock(BB); 422 MadeChange = true; 423 } 424 return MadeChange; 425 } 426 427 /// Return true if we can merge BB into DestBB if there is a single 428 /// unconditional branch between them, and BB contains no other non-phi 429 /// instructions. 430 bool CodeGenPrepare::canMergeBlocks(const BasicBlock *BB, 431 const BasicBlock *DestBB) const { 432 // We only want to eliminate blocks whose phi nodes are used by phi nodes in 433 // the successor. If there are more complex condition (e.g. preheaders), 434 // don't mess around with them. 435 BasicBlock::const_iterator BBI = BB->begin(); 436 while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 437 for (const User *U : PN->users()) { 438 const Instruction *UI = cast<Instruction>(U); 439 if (UI->getParent() != DestBB || !isa<PHINode>(UI)) 440 return false; 441 // If User is inside DestBB block and it is a PHINode then check 442 // incoming value. If incoming value is not from BB then this is 443 // a complex condition (e.g. preheaders) we want to avoid here. 444 if (UI->getParent() == DestBB) { 445 if (const PHINode *UPN = dyn_cast<PHINode>(UI)) 446 for (unsigned I = 0, E = UPN->getNumIncomingValues(); I != E; ++I) { 447 Instruction *Insn = dyn_cast<Instruction>(UPN->getIncomingValue(I)); 448 if (Insn && Insn->getParent() == BB && 449 Insn->getParent() != UPN->getIncomingBlock(I)) 450 return false; 451 } 452 } 453 } 454 } 455 456 // If BB and DestBB contain any common predecessors, then the phi nodes in BB 457 // and DestBB may have conflicting incoming values for the block. If so, we 458 // can't merge the block. 459 const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->begin()); 460 if (!DestBBPN) return true; // no conflict. 461 462 // Collect the preds of BB. 463 SmallPtrSet<const BasicBlock*, 16> BBPreds; 464 if (const PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 465 // It is faster to get preds from a PHI than with pred_iterator. 466 for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 467 BBPreds.insert(BBPN->getIncomingBlock(i)); 468 } else { 469 BBPreds.insert(pred_begin(BB), pred_end(BB)); 470 } 471 472 // Walk the preds of DestBB. 473 for (unsigned i = 0, e = DestBBPN->getNumIncomingValues(); i != e; ++i) { 474 BasicBlock *Pred = DestBBPN->getIncomingBlock(i); 475 if (BBPreds.count(Pred)) { // Common predecessor? 476 BBI = DestBB->begin(); 477 while (const PHINode *PN = dyn_cast<PHINode>(BBI++)) { 478 const Value *V1 = PN->getIncomingValueForBlock(Pred); 479 const Value *V2 = PN->getIncomingValueForBlock(BB); 480 481 // If V2 is a phi node in BB, look up what the mapped value will be. 482 if (const PHINode *V2PN = dyn_cast<PHINode>(V2)) 483 if (V2PN->getParent() == BB) 484 V2 = V2PN->getIncomingValueForBlock(Pred); 485 486 // If there is a conflict, bail out. 487 if (V1 != V2) return false; 488 } 489 } 490 } 491 492 return true; 493 } 494 495 496 /// Eliminate a basic block that has only phi's and an unconditional branch in 497 /// it. 498 void CodeGenPrepare::eliminateMostlyEmptyBlock(BasicBlock *BB) { 499 BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 500 BasicBlock *DestBB = BI->getSuccessor(0); 501 502 DEBUG(dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n" << *BB << *DestBB); 503 504 // If the destination block has a single pred, then this is a trivial edge, 505 // just collapse it. 506 if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) { 507 if (SinglePred != DestBB) { 508 // Remember if SinglePred was the entry block of the function. If so, we 509 // will need to move BB back to the entry position. 510 bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock(); 511 MergeBasicBlockIntoOnlyPred(DestBB, nullptr); 512 513 if (isEntry && BB != &BB->getParent()->getEntryBlock()) 514 BB->moveBefore(&BB->getParent()->getEntryBlock()); 515 516 DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n"); 517 return; 518 } 519 } 520 521 // Otherwise, we have multiple predecessors of BB. Update the PHIs in DestBB 522 // to handle the new incoming edges it is about to have. 523 PHINode *PN; 524 for (BasicBlock::iterator BBI = DestBB->begin(); 525 (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 526 // Remove the incoming value for BB, and remember it. 527 Value *InVal = PN->removeIncomingValue(BB, false); 528 529 // Two options: either the InVal is a phi node defined in BB or it is some 530 // value that dominates BB. 531 PHINode *InValPhi = dyn_cast<PHINode>(InVal); 532 if (InValPhi && InValPhi->getParent() == BB) { 533 // Add all of the input values of the input PHI as inputs of this phi. 534 for (unsigned i = 0, e = InValPhi->getNumIncomingValues(); i != e; ++i) 535 PN->addIncoming(InValPhi->getIncomingValue(i), 536 InValPhi->getIncomingBlock(i)); 537 } else { 538 // Otherwise, add one instance of the dominating value for each edge that 539 // we will be adding. 540 if (PHINode *BBPN = dyn_cast<PHINode>(BB->begin())) { 541 for (unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i) 542 PN->addIncoming(InVal, BBPN->getIncomingBlock(i)); 543 } else { 544 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 545 PN->addIncoming(InVal, *PI); 546 } 547 } 548 } 549 550 // The PHIs are now updated, change everything that refers to BB to use 551 // DestBB and remove BB. 552 BB->replaceAllUsesWith(DestBB); 553 BB->eraseFromParent(); 554 ++NumBlocksElim; 555 556 DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n"); 557 } 558 559 // Computes a map of base pointer relocation instructions to corresponding 560 // derived pointer relocation instructions given a vector of all relocate calls 561 static void computeBaseDerivedRelocateMap( 562 const SmallVectorImpl<GCRelocateInst *> &AllRelocateCalls, 563 DenseMap<GCRelocateInst *, SmallVector<GCRelocateInst *, 2>> 564 &RelocateInstMap) { 565 // Collect information in two maps: one primarily for locating the base object 566 // while filling the second map; the second map is the final structure holding 567 // a mapping between Base and corresponding Derived relocate calls 568 DenseMap<std::pair<unsigned, unsigned>, GCRelocateInst *> RelocateIdxMap; 569 for (auto *ThisRelocate : AllRelocateCalls) { 570 auto K = std::make_pair(ThisRelocate->getBasePtrIndex(), 571 ThisRelocate->getDerivedPtrIndex()); 572 RelocateIdxMap.insert(std::make_pair(K, ThisRelocate)); 573 } 574 for (auto &Item : RelocateIdxMap) { 575 std::pair<unsigned, unsigned> Key = Item.first; 576 if (Key.first == Key.second) 577 // Base relocation: nothing to insert 578 continue; 579 580 GCRelocateInst *I = Item.second; 581 auto BaseKey = std::make_pair(Key.first, Key.first); 582 583 // We're iterating over RelocateIdxMap so we cannot modify it. 584 auto MaybeBase = RelocateIdxMap.find(BaseKey); 585 if (MaybeBase == RelocateIdxMap.end()) 586 // TODO: We might want to insert a new base object relocate and gep off 587 // that, if there are enough derived object relocates. 588 continue; 589 590 RelocateInstMap[MaybeBase->second].push_back(I); 591 } 592 } 593 594 // Accepts a GEP and extracts the operands into a vector provided they're all 595 // small integer constants 596 static bool getGEPSmallConstantIntOffsetV(GetElementPtrInst *GEP, 597 SmallVectorImpl<Value *> &OffsetV) { 598 for (unsigned i = 1; i < GEP->getNumOperands(); i++) { 599 // Only accept small constant integer operands 600 auto Op = dyn_cast<ConstantInt>(GEP->getOperand(i)); 601 if (!Op || Op->getZExtValue() > 20) 602 return false; 603 } 604 605 for (unsigned i = 1; i < GEP->getNumOperands(); i++) 606 OffsetV.push_back(GEP->getOperand(i)); 607 return true; 608 } 609 610 // Takes a RelocatedBase (base pointer relocation instruction) and Targets to 611 // replace, computes a replacement, and affects it. 612 static bool 613 simplifyRelocatesOffABase(GCRelocateInst *RelocatedBase, 614 const SmallVectorImpl<GCRelocateInst *> &Targets) { 615 bool MadeChange = false; 616 for (GCRelocateInst *ToReplace : Targets) { 617 assert(ToReplace->getBasePtrIndex() == RelocatedBase->getBasePtrIndex() && 618 "Not relocating a derived object of the original base object"); 619 if (ToReplace->getBasePtrIndex() == ToReplace->getDerivedPtrIndex()) { 620 // A duplicate relocate call. TODO: coalesce duplicates. 621 continue; 622 } 623 624 if (RelocatedBase->getParent() != ToReplace->getParent()) { 625 // Base and derived relocates are in different basic blocks. 626 // In this case transform is only valid when base dominates derived 627 // relocate. However it would be too expensive to check dominance 628 // for each such relocate, so we skip the whole transformation. 629 continue; 630 } 631 632 Value *Base = ToReplace->getBasePtr(); 633 auto Derived = dyn_cast<GetElementPtrInst>(ToReplace->getDerivedPtr()); 634 if (!Derived || Derived->getPointerOperand() != Base) 635 continue; 636 637 SmallVector<Value *, 2> OffsetV; 638 if (!getGEPSmallConstantIntOffsetV(Derived, OffsetV)) 639 continue; 640 641 // Create a Builder and replace the target callsite with a gep 642 assert(RelocatedBase->getNextNode() && 643 "Should always have one since it's not a terminator"); 644 645 // Insert after RelocatedBase 646 IRBuilder<> Builder(RelocatedBase->getNextNode()); 647 Builder.SetCurrentDebugLocation(ToReplace->getDebugLoc()); 648 649 // If gc_relocate does not match the actual type, cast it to the right type. 650 // In theory, there must be a bitcast after gc_relocate if the type does not 651 // match, and we should reuse it to get the derived pointer. But it could be 652 // cases like this: 653 // bb1: 654 // ... 655 // %g1 = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(...) 656 // br label %merge 657 // 658 // bb2: 659 // ... 660 // %g2 = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(...) 661 // br label %merge 662 // 663 // merge: 664 // %p1 = phi i8 addrspace(1)* [ %g1, %bb1 ], [ %g2, %bb2 ] 665 // %cast = bitcast i8 addrspace(1)* %p1 in to i32 addrspace(1)* 666 // 667 // In this case, we can not find the bitcast any more. So we insert a new bitcast 668 // no matter there is already one or not. In this way, we can handle all cases, and 669 // the extra bitcast should be optimized away in later passes. 670 Value *ActualRelocatedBase = RelocatedBase; 671 if (RelocatedBase->getType() != Base->getType()) { 672 ActualRelocatedBase = 673 Builder.CreateBitCast(RelocatedBase, Base->getType()); 674 } 675 Value *Replacement = Builder.CreateGEP( 676 Derived->getSourceElementType(), ActualRelocatedBase, makeArrayRef(OffsetV)); 677 Replacement->takeName(ToReplace); 678 // If the newly generated derived pointer's type does not match the original derived 679 // pointer's type, cast the new derived pointer to match it. Same reasoning as above. 680 Value *ActualReplacement = Replacement; 681 if (Replacement->getType() != ToReplace->getType()) { 682 ActualReplacement = 683 Builder.CreateBitCast(Replacement, ToReplace->getType()); 684 } 685 ToReplace->replaceAllUsesWith(ActualReplacement); 686 ToReplace->eraseFromParent(); 687 688 MadeChange = true; 689 } 690 return MadeChange; 691 } 692 693 // Turns this: 694 // 695 // %base = ... 696 // %ptr = gep %base + 15 697 // %tok = statepoint (%fun, i32 0, i32 0, i32 0, %base, %ptr) 698 // %base' = relocate(%tok, i32 4, i32 4) 699 // %ptr' = relocate(%tok, i32 4, i32 5) 700 // %val = load %ptr' 701 // 702 // into this: 703 // 704 // %base = ... 705 // %ptr = gep %base + 15 706 // %tok = statepoint (%fun, i32 0, i32 0, i32 0, %base, %ptr) 707 // %base' = gc.relocate(%tok, i32 4, i32 4) 708 // %ptr' = gep %base' + 15 709 // %val = load %ptr' 710 bool CodeGenPrepare::simplifyOffsetableRelocate(Instruction &I) { 711 bool MadeChange = false; 712 SmallVector<GCRelocateInst *, 2> AllRelocateCalls; 713 714 for (auto *U : I.users()) 715 if (GCRelocateInst *Relocate = dyn_cast<GCRelocateInst>(U)) 716 // Collect all the relocate calls associated with a statepoint 717 AllRelocateCalls.push_back(Relocate); 718 719 // We need atleast one base pointer relocation + one derived pointer 720 // relocation to mangle 721 if (AllRelocateCalls.size() < 2) 722 return false; 723 724 // RelocateInstMap is a mapping from the base relocate instruction to the 725 // corresponding derived relocate instructions 726 DenseMap<GCRelocateInst *, SmallVector<GCRelocateInst *, 2>> RelocateInstMap; 727 computeBaseDerivedRelocateMap(AllRelocateCalls, RelocateInstMap); 728 if (RelocateInstMap.empty()) 729 return false; 730 731 for (auto &Item : RelocateInstMap) 732 // Item.first is the RelocatedBase to offset against 733 // Item.second is the vector of Targets to replace 734 MadeChange = simplifyRelocatesOffABase(Item.first, Item.second); 735 return MadeChange; 736 } 737 738 /// SinkCast - Sink the specified cast instruction into its user blocks 739 static bool SinkCast(CastInst *CI) { 740 BasicBlock *DefBB = CI->getParent(); 741 742 /// InsertedCasts - Only insert a cast in each block once. 743 DenseMap<BasicBlock*, CastInst*> InsertedCasts; 744 745 bool MadeChange = false; 746 for (Value::user_iterator UI = CI->user_begin(), E = CI->user_end(); 747 UI != E; ) { 748 Use &TheUse = UI.getUse(); 749 Instruction *User = cast<Instruction>(*UI); 750 751 // Figure out which BB this cast is used in. For PHI's this is the 752 // appropriate predecessor block. 753 BasicBlock *UserBB = User->getParent(); 754 if (PHINode *PN = dyn_cast<PHINode>(User)) { 755 UserBB = PN->getIncomingBlock(TheUse); 756 } 757 758 // Preincrement use iterator so we don't invalidate it. 759 ++UI; 760 761 // The first insertion point of a block containing an EH pad is after the 762 // pad. If the pad is the user, we cannot sink the cast past the pad. 763 if (User->isEHPad()) 764 continue; 765 766 // If the block selected to receive the cast is an EH pad that does not 767 // allow non-PHI instructions before the terminator, we can't sink the 768 // cast. 769 if (UserBB->getTerminator()->isEHPad()) 770 continue; 771 772 // If this user is in the same block as the cast, don't change the cast. 773 if (UserBB == DefBB) continue; 774 775 // If we have already inserted a cast into this block, use it. 776 CastInst *&InsertedCast = InsertedCasts[UserBB]; 777 778 if (!InsertedCast) { 779 BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt(); 780 assert(InsertPt != UserBB->end()); 781 InsertedCast = CastInst::Create(CI->getOpcode(), CI->getOperand(0), 782 CI->getType(), "", &*InsertPt); 783 } 784 785 // Replace a use of the cast with a use of the new cast. 786 TheUse = InsertedCast; 787 MadeChange = true; 788 ++NumCastUses; 789 } 790 791 // If we removed all uses, nuke the cast. 792 if (CI->use_empty()) { 793 CI->eraseFromParent(); 794 MadeChange = true; 795 } 796 797 return MadeChange; 798 } 799 800 /// If the specified cast instruction is a noop copy (e.g. it's casting from 801 /// one pointer type to another, i32->i8 on PPC), sink it into user blocks to 802 /// reduce the number of virtual registers that must be created and coalesced. 803 /// 804 /// Return true if any changes are made. 805 /// 806 static bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI, 807 const DataLayout &DL) { 808 // If this is a noop copy, 809 EVT SrcVT = TLI.getValueType(DL, CI->getOperand(0)->getType()); 810 EVT DstVT = TLI.getValueType(DL, CI->getType()); 811 812 // This is an fp<->int conversion? 813 if (SrcVT.isInteger() != DstVT.isInteger()) 814 return false; 815 816 // If this is an extension, it will be a zero or sign extension, which 817 // isn't a noop. 818 if (SrcVT.bitsLT(DstVT)) return false; 819 820 // If these values will be promoted, find out what they will be promoted 821 // to. This helps us consider truncates on PPC as noop copies when they 822 // are. 823 if (TLI.getTypeAction(CI->getContext(), SrcVT) == 824 TargetLowering::TypePromoteInteger) 825 SrcVT = TLI.getTypeToTransformTo(CI->getContext(), SrcVT); 826 if (TLI.getTypeAction(CI->getContext(), DstVT) == 827 TargetLowering::TypePromoteInteger) 828 DstVT = TLI.getTypeToTransformTo(CI->getContext(), DstVT); 829 830 // If, after promotion, these are the same types, this is a noop copy. 831 if (SrcVT != DstVT) 832 return false; 833 834 return SinkCast(CI); 835 } 836 837 /// Try to combine CI into a call to the llvm.uadd.with.overflow intrinsic if 838 /// possible. 839 /// 840 /// Return true if any changes were made. 841 static bool CombineUAddWithOverflow(CmpInst *CI) { 842 Value *A, *B; 843 Instruction *AddI; 844 if (!match(CI, 845 m_UAddWithOverflow(m_Value(A), m_Value(B), m_Instruction(AddI)))) 846 return false; 847 848 Type *Ty = AddI->getType(); 849 if (!isa<IntegerType>(Ty)) 850 return false; 851 852 // We don't want to move around uses of condition values this late, so we we 853 // check if it is legal to create the call to the intrinsic in the basic 854 // block containing the icmp: 855 856 if (AddI->getParent() != CI->getParent() && !AddI->hasOneUse()) 857 return false; 858 859 #ifndef NDEBUG 860 // Someday m_UAddWithOverflow may get smarter, but this is a safe assumption 861 // for now: 862 if (AddI->hasOneUse()) 863 assert(*AddI->user_begin() == CI && "expected!"); 864 #endif 865 866 Module *M = CI->getModule(); 867 Value *F = Intrinsic::getDeclaration(M, Intrinsic::uadd_with_overflow, Ty); 868 869 auto *InsertPt = AddI->hasOneUse() ? CI : AddI; 870 871 auto *UAddWithOverflow = 872 CallInst::Create(F, {A, B}, "uadd.overflow", InsertPt); 873 auto *UAdd = ExtractValueInst::Create(UAddWithOverflow, 0, "uadd", InsertPt); 874 auto *Overflow = 875 ExtractValueInst::Create(UAddWithOverflow, 1, "overflow", InsertPt); 876 877 CI->replaceAllUsesWith(Overflow); 878 AddI->replaceAllUsesWith(UAdd); 879 CI->eraseFromParent(); 880 AddI->eraseFromParent(); 881 return true; 882 } 883 884 /// Sink the given CmpInst into user blocks to reduce the number of virtual 885 /// registers that must be created and coalesced. This is a clear win except on 886 /// targets with multiple condition code registers (PowerPC), where it might 887 /// lose; some adjustment may be wanted there. 888 /// 889 /// Return true if any changes are made. 890 static bool SinkCmpExpression(CmpInst *CI, const TargetLowering *TLI) { 891 BasicBlock *DefBB = CI->getParent(); 892 893 // Avoid sinking soft-FP comparisons, since this can move them into a loop. 894 if (TLI && TLI->useSoftFloat() && isa<FCmpInst>(CI)) 895 return false; 896 897 // Only insert a cmp in each block once. 898 DenseMap<BasicBlock*, CmpInst*> InsertedCmps; 899 900 bool MadeChange = false; 901 for (Value::user_iterator UI = CI->user_begin(), E = CI->user_end(); 902 UI != E; ) { 903 Use &TheUse = UI.getUse(); 904 Instruction *User = cast<Instruction>(*UI); 905 906 // Preincrement use iterator so we don't invalidate it. 907 ++UI; 908 909 // Don't bother for PHI nodes. 910 if (isa<PHINode>(User)) 911 continue; 912 913 // Figure out which BB this cmp is used in. 914 BasicBlock *UserBB = User->getParent(); 915 916 // If this user is in the same block as the cmp, don't change the cmp. 917 if (UserBB == DefBB) continue; 918 919 // If we have already inserted a cmp into this block, use it. 920 CmpInst *&InsertedCmp = InsertedCmps[UserBB]; 921 922 if (!InsertedCmp) { 923 BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt(); 924 assert(InsertPt != UserBB->end()); 925 InsertedCmp = 926 CmpInst::Create(CI->getOpcode(), CI->getPredicate(), 927 CI->getOperand(0), CI->getOperand(1), "", &*InsertPt); 928 } 929 930 // Replace a use of the cmp with a use of the new cmp. 931 TheUse = InsertedCmp; 932 MadeChange = true; 933 ++NumCmpUses; 934 } 935 936 // If we removed all uses, nuke the cmp. 937 if (CI->use_empty()) { 938 CI->eraseFromParent(); 939 MadeChange = true; 940 } 941 942 return MadeChange; 943 } 944 945 static bool OptimizeCmpExpression(CmpInst *CI, const TargetLowering *TLI) { 946 if (SinkCmpExpression(CI, TLI)) 947 return true; 948 949 if (CombineUAddWithOverflow(CI)) 950 return true; 951 952 return false; 953 } 954 955 /// Check if the candidates could be combined with a shift instruction, which 956 /// includes: 957 /// 1. Truncate instruction 958 /// 2. And instruction and the imm is a mask of the low bits: 959 /// imm & (imm+1) == 0 960 static bool isExtractBitsCandidateUse(Instruction *User) { 961 if (!isa<TruncInst>(User)) { 962 if (User->getOpcode() != Instruction::And || 963 !isa<ConstantInt>(User->getOperand(1))) 964 return false; 965 966 const APInt &Cimm = cast<ConstantInt>(User->getOperand(1))->getValue(); 967 968 if ((Cimm & (Cimm + 1)).getBoolValue()) 969 return false; 970 } 971 return true; 972 } 973 974 /// Sink both shift and truncate instruction to the use of truncate's BB. 975 static bool 976 SinkShiftAndTruncate(BinaryOperator *ShiftI, Instruction *User, ConstantInt *CI, 977 DenseMap<BasicBlock *, BinaryOperator *> &InsertedShifts, 978 const TargetLowering &TLI, const DataLayout &DL) { 979 BasicBlock *UserBB = User->getParent(); 980 DenseMap<BasicBlock *, CastInst *> InsertedTruncs; 981 TruncInst *TruncI = dyn_cast<TruncInst>(User); 982 bool MadeChange = false; 983 984 for (Value::user_iterator TruncUI = TruncI->user_begin(), 985 TruncE = TruncI->user_end(); 986 TruncUI != TruncE;) { 987 988 Use &TruncTheUse = TruncUI.getUse(); 989 Instruction *TruncUser = cast<Instruction>(*TruncUI); 990 // Preincrement use iterator so we don't invalidate it. 991 992 ++TruncUI; 993 994 int ISDOpcode = TLI.InstructionOpcodeToISD(TruncUser->getOpcode()); 995 if (!ISDOpcode) 996 continue; 997 998 // If the use is actually a legal node, there will not be an 999 // implicit truncate. 1000 // FIXME: always querying the result type is just an 1001 // approximation; some nodes' legality is determined by the 1002 // operand or other means. There's no good way to find out though. 1003 if (TLI.isOperationLegalOrCustom( 1004 ISDOpcode, TLI.getValueType(DL, TruncUser->getType(), true))) 1005 continue; 1006 1007 // Don't bother for PHI nodes. 1008 if (isa<PHINode>(TruncUser)) 1009 continue; 1010 1011 BasicBlock *TruncUserBB = TruncUser->getParent(); 1012 1013 if (UserBB == TruncUserBB) 1014 continue; 1015 1016 BinaryOperator *&InsertedShift = InsertedShifts[TruncUserBB]; 1017 CastInst *&InsertedTrunc = InsertedTruncs[TruncUserBB]; 1018 1019 if (!InsertedShift && !InsertedTrunc) { 1020 BasicBlock::iterator InsertPt = TruncUserBB->getFirstInsertionPt(); 1021 assert(InsertPt != TruncUserBB->end()); 1022 // Sink the shift 1023 if (ShiftI->getOpcode() == Instruction::AShr) 1024 InsertedShift = BinaryOperator::CreateAShr(ShiftI->getOperand(0), CI, 1025 "", &*InsertPt); 1026 else 1027 InsertedShift = BinaryOperator::CreateLShr(ShiftI->getOperand(0), CI, 1028 "", &*InsertPt); 1029 1030 // Sink the trunc 1031 BasicBlock::iterator TruncInsertPt = TruncUserBB->getFirstInsertionPt(); 1032 TruncInsertPt++; 1033 assert(TruncInsertPt != TruncUserBB->end()); 1034 1035 InsertedTrunc = CastInst::Create(TruncI->getOpcode(), InsertedShift, 1036 TruncI->getType(), "", &*TruncInsertPt); 1037 1038 MadeChange = true; 1039 1040 TruncTheUse = InsertedTrunc; 1041 } 1042 } 1043 return MadeChange; 1044 } 1045 1046 /// Sink the shift *right* instruction into user blocks if the uses could 1047 /// potentially be combined with this shift instruction and generate BitExtract 1048 /// instruction. It will only be applied if the architecture supports BitExtract 1049 /// instruction. Here is an example: 1050 /// BB1: 1051 /// %x.extract.shift = lshr i64 %arg1, 32 1052 /// BB2: 1053 /// %x.extract.trunc = trunc i64 %x.extract.shift to i16 1054 /// ==> 1055 /// 1056 /// BB2: 1057 /// %x.extract.shift.1 = lshr i64 %arg1, 32 1058 /// %x.extract.trunc = trunc i64 %x.extract.shift.1 to i16 1059 /// 1060 /// CodeGen will recoginze the pattern in BB2 and generate BitExtract 1061 /// instruction. 1062 /// Return true if any changes are made. 1063 static bool OptimizeExtractBits(BinaryOperator *ShiftI, ConstantInt *CI, 1064 const TargetLowering &TLI, 1065 const DataLayout &DL) { 1066 BasicBlock *DefBB = ShiftI->getParent(); 1067 1068 /// Only insert instructions in each block once. 1069 DenseMap<BasicBlock *, BinaryOperator *> InsertedShifts; 1070 1071 bool shiftIsLegal = TLI.isTypeLegal(TLI.getValueType(DL, ShiftI->getType())); 1072 1073 bool MadeChange = false; 1074 for (Value::user_iterator UI = ShiftI->user_begin(), E = ShiftI->user_end(); 1075 UI != E;) { 1076 Use &TheUse = UI.getUse(); 1077 Instruction *User = cast<Instruction>(*UI); 1078 // Preincrement use iterator so we don't invalidate it. 1079 ++UI; 1080 1081 // Don't bother for PHI nodes. 1082 if (isa<PHINode>(User)) 1083 continue; 1084 1085 if (!isExtractBitsCandidateUse(User)) 1086 continue; 1087 1088 BasicBlock *UserBB = User->getParent(); 1089 1090 if (UserBB == DefBB) { 1091 // If the shift and truncate instruction are in the same BB. The use of 1092 // the truncate(TruncUse) may still introduce another truncate if not 1093 // legal. In this case, we would like to sink both shift and truncate 1094 // instruction to the BB of TruncUse. 1095 // for example: 1096 // BB1: 1097 // i64 shift.result = lshr i64 opnd, imm 1098 // trunc.result = trunc shift.result to i16 1099 // 1100 // BB2: 1101 // ----> We will have an implicit truncate here if the architecture does 1102 // not have i16 compare. 1103 // cmp i16 trunc.result, opnd2 1104 // 1105 if (isa<TruncInst>(User) && shiftIsLegal 1106 // If the type of the truncate is legal, no trucate will be 1107 // introduced in other basic blocks. 1108 && 1109 (!TLI.isTypeLegal(TLI.getValueType(DL, User->getType())))) 1110 MadeChange = 1111 SinkShiftAndTruncate(ShiftI, User, CI, InsertedShifts, TLI, DL); 1112 1113 continue; 1114 } 1115 // If we have already inserted a shift into this block, use it. 1116 BinaryOperator *&InsertedShift = InsertedShifts[UserBB]; 1117 1118 if (!InsertedShift) { 1119 BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt(); 1120 assert(InsertPt != UserBB->end()); 1121 1122 if (ShiftI->getOpcode() == Instruction::AShr) 1123 InsertedShift = BinaryOperator::CreateAShr(ShiftI->getOperand(0), CI, 1124 "", &*InsertPt); 1125 else 1126 InsertedShift = BinaryOperator::CreateLShr(ShiftI->getOperand(0), CI, 1127 "", &*InsertPt); 1128 1129 MadeChange = true; 1130 } 1131 1132 // Replace a use of the shift with a use of the new shift. 1133 TheUse = InsertedShift; 1134 } 1135 1136 // If we removed all uses, nuke the shift. 1137 if (ShiftI->use_empty()) 1138 ShiftI->eraseFromParent(); 1139 1140 return MadeChange; 1141 } 1142 1143 // Translate a masked load intrinsic like 1144 // <16 x i32 > @llvm.masked.load( <16 x i32>* %addr, i32 align, 1145 // <16 x i1> %mask, <16 x i32> %passthru) 1146 // to a chain of basic blocks, with loading element one-by-one if 1147 // the appropriate mask bit is set 1148 // 1149 // %1 = bitcast i8* %addr to i32* 1150 // %2 = extractelement <16 x i1> %mask, i32 0 1151 // %3 = icmp eq i1 %2, true 1152 // br i1 %3, label %cond.load, label %else 1153 // 1154 //cond.load: ; preds = %0 1155 // %4 = getelementptr i32* %1, i32 0 1156 // %5 = load i32* %4 1157 // %6 = insertelement <16 x i32> undef, i32 %5, i32 0 1158 // br label %else 1159 // 1160 //else: ; preds = %0, %cond.load 1161 // %res.phi.else = phi <16 x i32> [ %6, %cond.load ], [ undef, %0 ] 1162 // %7 = extractelement <16 x i1> %mask, i32 1 1163 // %8 = icmp eq i1 %7, true 1164 // br i1 %8, label %cond.load1, label %else2 1165 // 1166 //cond.load1: ; preds = %else 1167 // %9 = getelementptr i32* %1, i32 1 1168 // %10 = load i32* %9 1169 // %11 = insertelement <16 x i32> %res.phi.else, i32 %10, i32 1 1170 // br label %else2 1171 // 1172 //else2: ; preds = %else, %cond.load1 1173 // %res.phi.else3 = phi <16 x i32> [ %11, %cond.load1 ], [ %res.phi.else, %else ] 1174 // %12 = extractelement <16 x i1> %mask, i32 2 1175 // %13 = icmp eq i1 %12, true 1176 // br i1 %13, label %cond.load4, label %else5 1177 // 1178 static void scalarizeMaskedLoad(CallInst *CI) { 1179 Value *Ptr = CI->getArgOperand(0); 1180 Value *Alignment = CI->getArgOperand(1); 1181 Value *Mask = CI->getArgOperand(2); 1182 Value *Src0 = CI->getArgOperand(3); 1183 1184 unsigned AlignVal = cast<ConstantInt>(Alignment)->getZExtValue(); 1185 VectorType *VecType = dyn_cast<VectorType>(CI->getType()); 1186 assert(VecType && "Unexpected return type of masked load intrinsic"); 1187 1188 Type *EltTy = CI->getType()->getVectorElementType(); 1189 1190 IRBuilder<> Builder(CI->getContext()); 1191 Instruction *InsertPt = CI; 1192 BasicBlock *IfBlock = CI->getParent(); 1193 BasicBlock *CondBlock = nullptr; 1194 BasicBlock *PrevIfBlock = CI->getParent(); 1195 1196 Builder.SetInsertPoint(InsertPt); 1197 Builder.SetCurrentDebugLocation(CI->getDebugLoc()); 1198 1199 // Short-cut if the mask is all-true. 1200 bool IsAllOnesMask = isa<Constant>(Mask) && 1201 cast<Constant>(Mask)->isAllOnesValue(); 1202 1203 if (IsAllOnesMask) { 1204 Value *NewI = Builder.CreateAlignedLoad(Ptr, AlignVal); 1205 CI->replaceAllUsesWith(NewI); 1206 CI->eraseFromParent(); 1207 return; 1208 } 1209 1210 // Adjust alignment for the scalar instruction. 1211 AlignVal = std::min(AlignVal, VecType->getScalarSizeInBits()/8); 1212 // Bitcast %addr fron i8* to EltTy* 1213 Type *NewPtrType = 1214 EltTy->getPointerTo(cast<PointerType>(Ptr->getType())->getAddressSpace()); 1215 Value *FirstEltPtr = Builder.CreateBitCast(Ptr, NewPtrType); 1216 unsigned VectorWidth = VecType->getNumElements(); 1217 1218 Value *UndefVal = UndefValue::get(VecType); 1219 1220 // The result vector 1221 Value *VResult = UndefVal; 1222 1223 if (isa<ConstantVector>(Mask)) { 1224 for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) { 1225 if (cast<ConstantVector>(Mask)->getOperand(Idx)->isNullValue()) 1226 continue; 1227 Value *Gep = 1228 Builder.CreateInBoundsGEP(EltTy, FirstEltPtr, Builder.getInt32(Idx)); 1229 LoadInst* Load = Builder.CreateAlignedLoad(Gep, AlignVal); 1230 VResult = Builder.CreateInsertElement(VResult, Load, 1231 Builder.getInt32(Idx)); 1232 } 1233 Value *NewI = Builder.CreateSelect(Mask, VResult, Src0); 1234 CI->replaceAllUsesWith(NewI); 1235 CI->eraseFromParent(); 1236 return; 1237 } 1238 1239 PHINode *Phi = nullptr; 1240 Value *PrevPhi = UndefVal; 1241 1242 for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) { 1243 1244 // Fill the "else" block, created in the previous iteration 1245 // 1246 // %res.phi.else3 = phi <16 x i32> [ %11, %cond.load1 ], [ %res.phi.else, %else ] 1247 // %mask_1 = extractelement <16 x i1> %mask, i32 Idx 1248 // %to_load = icmp eq i1 %mask_1, true 1249 // br i1 %to_load, label %cond.load, label %else 1250 // 1251 if (Idx > 0) { 1252 Phi = Builder.CreatePHI(VecType, 2, "res.phi.else"); 1253 Phi->addIncoming(VResult, CondBlock); 1254 Phi->addIncoming(PrevPhi, PrevIfBlock); 1255 PrevPhi = Phi; 1256 VResult = Phi; 1257 } 1258 1259 Value *Predicate = Builder.CreateExtractElement(Mask, Builder.getInt32(Idx)); 1260 Value *Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Predicate, 1261 ConstantInt::get(Predicate->getType(), 1)); 1262 1263 // Create "cond" block 1264 // 1265 // %EltAddr = getelementptr i32* %1, i32 0 1266 // %Elt = load i32* %EltAddr 1267 // VResult = insertelement <16 x i32> VResult, i32 %Elt, i32 Idx 1268 // 1269 CondBlock = IfBlock->splitBasicBlock(InsertPt->getIterator(), "cond.load"); 1270 Builder.SetInsertPoint(InsertPt); 1271 1272 Value *Gep = 1273 Builder.CreateInBoundsGEP(EltTy, FirstEltPtr, Builder.getInt32(Idx)); 1274 LoadInst *Load = Builder.CreateAlignedLoad(Gep, AlignVal); 1275 VResult = Builder.CreateInsertElement(VResult, Load, Builder.getInt32(Idx)); 1276 1277 // Create "else" block, fill it in the next iteration 1278 BasicBlock *NewIfBlock = 1279 CondBlock->splitBasicBlock(InsertPt->getIterator(), "else"); 1280 Builder.SetInsertPoint(InsertPt); 1281 Instruction *OldBr = IfBlock->getTerminator(); 1282 BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr); 1283 OldBr->eraseFromParent(); 1284 PrevIfBlock = IfBlock; 1285 IfBlock = NewIfBlock; 1286 } 1287 1288 Phi = Builder.CreatePHI(VecType, 2, "res.phi.select"); 1289 Phi->addIncoming(VResult, CondBlock); 1290 Phi->addIncoming(PrevPhi, PrevIfBlock); 1291 Value *NewI = Builder.CreateSelect(Mask, Phi, Src0); 1292 CI->replaceAllUsesWith(NewI); 1293 CI->eraseFromParent(); 1294 } 1295 1296 // Translate a masked store intrinsic, like 1297 // void @llvm.masked.store(<16 x i32> %src, <16 x i32>* %addr, i32 align, 1298 // <16 x i1> %mask) 1299 // to a chain of basic blocks, that stores element one-by-one if 1300 // the appropriate mask bit is set 1301 // 1302 // %1 = bitcast i8* %addr to i32* 1303 // %2 = extractelement <16 x i1> %mask, i32 0 1304 // %3 = icmp eq i1 %2, true 1305 // br i1 %3, label %cond.store, label %else 1306 // 1307 // cond.store: ; preds = %0 1308 // %4 = extractelement <16 x i32> %val, i32 0 1309 // %5 = getelementptr i32* %1, i32 0 1310 // store i32 %4, i32* %5 1311 // br label %else 1312 // 1313 // else: ; preds = %0, %cond.store 1314 // %6 = extractelement <16 x i1> %mask, i32 1 1315 // %7 = icmp eq i1 %6, true 1316 // br i1 %7, label %cond.store1, label %else2 1317 // 1318 // cond.store1: ; preds = %else 1319 // %8 = extractelement <16 x i32> %val, i32 1 1320 // %9 = getelementptr i32* %1, i32 1 1321 // store i32 %8, i32* %9 1322 // br label %else2 1323 // . . . 1324 static void scalarizeMaskedStore(CallInst *CI) { 1325 Value *Src = CI->getArgOperand(0); 1326 Value *Ptr = CI->getArgOperand(1); 1327 Value *Alignment = CI->getArgOperand(2); 1328 Value *Mask = CI->getArgOperand(3); 1329 1330 unsigned AlignVal = cast<ConstantInt>(Alignment)->getZExtValue(); 1331 VectorType *VecType = dyn_cast<VectorType>(Src->getType()); 1332 assert(VecType && "Unexpected data type in masked store intrinsic"); 1333 1334 Type *EltTy = VecType->getElementType(); 1335 1336 IRBuilder<> Builder(CI->getContext()); 1337 Instruction *InsertPt = CI; 1338 BasicBlock *IfBlock = CI->getParent(); 1339 Builder.SetInsertPoint(InsertPt); 1340 Builder.SetCurrentDebugLocation(CI->getDebugLoc()); 1341 1342 // Short-cut if the mask is all-true. 1343 bool IsAllOnesMask = isa<Constant>(Mask) && 1344 cast<Constant>(Mask)->isAllOnesValue(); 1345 1346 if (IsAllOnesMask) { 1347 Builder.CreateAlignedStore(Src, Ptr, AlignVal); 1348 CI->eraseFromParent(); 1349 return; 1350 } 1351 1352 // Adjust alignment for the scalar instruction. 1353 AlignVal = std::max(AlignVal, VecType->getScalarSizeInBits()/8); 1354 // Bitcast %addr fron i8* to EltTy* 1355 Type *NewPtrType = 1356 EltTy->getPointerTo(cast<PointerType>(Ptr->getType())->getAddressSpace()); 1357 Value *FirstEltPtr = Builder.CreateBitCast(Ptr, NewPtrType); 1358 unsigned VectorWidth = VecType->getNumElements(); 1359 1360 if (isa<ConstantVector>(Mask)) { 1361 for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) { 1362 if (cast<ConstantVector>(Mask)->getOperand(Idx)->isNullValue()) 1363 continue; 1364 Value *OneElt = Builder.CreateExtractElement(Src, Builder.getInt32(Idx)); 1365 Value *Gep = 1366 Builder.CreateInBoundsGEP(EltTy, FirstEltPtr, Builder.getInt32(Idx)); 1367 Builder.CreateAlignedStore(OneElt, Gep, AlignVal); 1368 } 1369 CI->eraseFromParent(); 1370 return; 1371 } 1372 1373 for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) { 1374 1375 // Fill the "else" block, created in the previous iteration 1376 // 1377 // %mask_1 = extractelement <16 x i1> %mask, i32 Idx 1378 // %to_store = icmp eq i1 %mask_1, true 1379 // br i1 %to_store, label %cond.store, label %else 1380 // 1381 Value *Predicate = Builder.CreateExtractElement(Mask, Builder.getInt32(Idx)); 1382 Value *Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Predicate, 1383 ConstantInt::get(Predicate->getType(), 1)); 1384 1385 // Create "cond" block 1386 // 1387 // %OneElt = extractelement <16 x i32> %Src, i32 Idx 1388 // %EltAddr = getelementptr i32* %1, i32 0 1389 // %store i32 %OneElt, i32* %EltAddr 1390 // 1391 BasicBlock *CondBlock = 1392 IfBlock->splitBasicBlock(InsertPt->getIterator(), "cond.store"); 1393 Builder.SetInsertPoint(InsertPt); 1394 1395 Value *OneElt = Builder.CreateExtractElement(Src, Builder.getInt32(Idx)); 1396 Value *Gep = 1397 Builder.CreateInBoundsGEP(EltTy, FirstEltPtr, Builder.getInt32(Idx)); 1398 Builder.CreateAlignedStore(OneElt, Gep, AlignVal); 1399 1400 // Create "else" block, fill it in the next iteration 1401 BasicBlock *NewIfBlock = 1402 CondBlock->splitBasicBlock(InsertPt->getIterator(), "else"); 1403 Builder.SetInsertPoint(InsertPt); 1404 Instruction *OldBr = IfBlock->getTerminator(); 1405 BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr); 1406 OldBr->eraseFromParent(); 1407 IfBlock = NewIfBlock; 1408 } 1409 CI->eraseFromParent(); 1410 } 1411 1412 // Translate a masked gather intrinsic like 1413 // <16 x i32 > @llvm.masked.gather.v16i32( <16 x i32*> %Ptrs, i32 4, 1414 // <16 x i1> %Mask, <16 x i32> %Src) 1415 // to a chain of basic blocks, with loading element one-by-one if 1416 // the appropriate mask bit is set 1417 // 1418 // % Ptrs = getelementptr i32, i32* %base, <16 x i64> %ind 1419 // % Mask0 = extractelement <16 x i1> %Mask, i32 0 1420 // % ToLoad0 = icmp eq i1 % Mask0, true 1421 // br i1 % ToLoad0, label %cond.load, label %else 1422 // 1423 // cond.load: 1424 // % Ptr0 = extractelement <16 x i32*> %Ptrs, i32 0 1425 // % Load0 = load i32, i32* % Ptr0, align 4 1426 // % Res0 = insertelement <16 x i32> undef, i32 % Load0, i32 0 1427 // br label %else 1428 // 1429 // else: 1430 // %res.phi.else = phi <16 x i32>[% Res0, %cond.load], [undef, % 0] 1431 // % Mask1 = extractelement <16 x i1> %Mask, i32 1 1432 // % ToLoad1 = icmp eq i1 % Mask1, true 1433 // br i1 % ToLoad1, label %cond.load1, label %else2 1434 // 1435 // cond.load1: 1436 // % Ptr1 = extractelement <16 x i32*> %Ptrs, i32 1 1437 // % Load1 = load i32, i32* % Ptr1, align 4 1438 // % Res1 = insertelement <16 x i32> %res.phi.else, i32 % Load1, i32 1 1439 // br label %else2 1440 // . . . 1441 // % Result = select <16 x i1> %Mask, <16 x i32> %res.phi.select, <16 x i32> %Src 1442 // ret <16 x i32> %Result 1443 static void scalarizeMaskedGather(CallInst *CI) { 1444 Value *Ptrs = CI->getArgOperand(0); 1445 Value *Alignment = CI->getArgOperand(1); 1446 Value *Mask = CI->getArgOperand(2); 1447 Value *Src0 = CI->getArgOperand(3); 1448 1449 VectorType *VecType = dyn_cast<VectorType>(CI->getType()); 1450 1451 assert(VecType && "Unexpected return type of masked load intrinsic"); 1452 1453 IRBuilder<> Builder(CI->getContext()); 1454 Instruction *InsertPt = CI; 1455 BasicBlock *IfBlock = CI->getParent(); 1456 BasicBlock *CondBlock = nullptr; 1457 BasicBlock *PrevIfBlock = CI->getParent(); 1458 Builder.SetInsertPoint(InsertPt); 1459 unsigned AlignVal = cast<ConstantInt>(Alignment)->getZExtValue(); 1460 1461 Builder.SetCurrentDebugLocation(CI->getDebugLoc()); 1462 1463 Value *UndefVal = UndefValue::get(VecType); 1464 1465 // The result vector 1466 Value *VResult = UndefVal; 1467 unsigned VectorWidth = VecType->getNumElements(); 1468 1469 // Shorten the way if the mask is a vector of constants. 1470 bool IsConstMask = isa<ConstantVector>(Mask); 1471 1472 if (IsConstMask) { 1473 for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) { 1474 if (cast<ConstantVector>(Mask)->getOperand(Idx)->isNullValue()) 1475 continue; 1476 Value *Ptr = Builder.CreateExtractElement(Ptrs, Builder.getInt32(Idx), 1477 "Ptr" + Twine(Idx)); 1478 LoadInst *Load = Builder.CreateAlignedLoad(Ptr, AlignVal, 1479 "Load" + Twine(Idx)); 1480 VResult = Builder.CreateInsertElement(VResult, Load, 1481 Builder.getInt32(Idx), 1482 "Res" + Twine(Idx)); 1483 } 1484 Value *NewI = Builder.CreateSelect(Mask, VResult, Src0); 1485 CI->replaceAllUsesWith(NewI); 1486 CI->eraseFromParent(); 1487 return; 1488 } 1489 1490 PHINode *Phi = nullptr; 1491 Value *PrevPhi = UndefVal; 1492 1493 for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) { 1494 1495 // Fill the "else" block, created in the previous iteration 1496 // 1497 // %Mask1 = extractelement <16 x i1> %Mask, i32 1 1498 // %ToLoad1 = icmp eq i1 %Mask1, true 1499 // br i1 %ToLoad1, label %cond.load, label %else 1500 // 1501 if (Idx > 0) { 1502 Phi = Builder.CreatePHI(VecType, 2, "res.phi.else"); 1503 Phi->addIncoming(VResult, CondBlock); 1504 Phi->addIncoming(PrevPhi, PrevIfBlock); 1505 PrevPhi = Phi; 1506 VResult = Phi; 1507 } 1508 1509 Value *Predicate = Builder.CreateExtractElement(Mask, 1510 Builder.getInt32(Idx), 1511 "Mask" + Twine(Idx)); 1512 Value *Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Predicate, 1513 ConstantInt::get(Predicate->getType(), 1), 1514 "ToLoad" + Twine(Idx)); 1515 1516 // Create "cond" block 1517 // 1518 // %EltAddr = getelementptr i32* %1, i32 0 1519 // %Elt = load i32* %EltAddr 1520 // VResult = insertelement <16 x i32> VResult, i32 %Elt, i32 Idx 1521 // 1522 CondBlock = IfBlock->splitBasicBlock(InsertPt, "cond.load"); 1523 Builder.SetInsertPoint(InsertPt); 1524 1525 Value *Ptr = Builder.CreateExtractElement(Ptrs, Builder.getInt32(Idx), 1526 "Ptr" + Twine(Idx)); 1527 LoadInst *Load = Builder.CreateAlignedLoad(Ptr, AlignVal, 1528 "Load" + Twine(Idx)); 1529 VResult = Builder.CreateInsertElement(VResult, Load, Builder.getInt32(Idx), 1530 "Res" + Twine(Idx)); 1531 1532 // Create "else" block, fill it in the next iteration 1533 BasicBlock *NewIfBlock = CondBlock->splitBasicBlock(InsertPt, "else"); 1534 Builder.SetInsertPoint(InsertPt); 1535 Instruction *OldBr = IfBlock->getTerminator(); 1536 BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr); 1537 OldBr->eraseFromParent(); 1538 PrevIfBlock = IfBlock; 1539 IfBlock = NewIfBlock; 1540 } 1541 1542 Phi = Builder.CreatePHI(VecType, 2, "res.phi.select"); 1543 Phi->addIncoming(VResult, CondBlock); 1544 Phi->addIncoming(PrevPhi, PrevIfBlock); 1545 Value *NewI = Builder.CreateSelect(Mask, Phi, Src0); 1546 CI->replaceAllUsesWith(NewI); 1547 CI->eraseFromParent(); 1548 } 1549 1550 // Translate a masked scatter intrinsic, like 1551 // void @llvm.masked.scatter.v16i32(<16 x i32> %Src, <16 x i32*>* %Ptrs, i32 4, 1552 // <16 x i1> %Mask) 1553 // to a chain of basic blocks, that stores element one-by-one if 1554 // the appropriate mask bit is set. 1555 // 1556 // % Ptrs = getelementptr i32, i32* %ptr, <16 x i64> %ind 1557 // % Mask0 = extractelement <16 x i1> % Mask, i32 0 1558 // % ToStore0 = icmp eq i1 % Mask0, true 1559 // br i1 %ToStore0, label %cond.store, label %else 1560 // 1561 // cond.store: 1562 // % Elt0 = extractelement <16 x i32> %Src, i32 0 1563 // % Ptr0 = extractelement <16 x i32*> %Ptrs, i32 0 1564 // store i32 %Elt0, i32* % Ptr0, align 4 1565 // br label %else 1566 // 1567 // else: 1568 // % Mask1 = extractelement <16 x i1> % Mask, i32 1 1569 // % ToStore1 = icmp eq i1 % Mask1, true 1570 // br i1 % ToStore1, label %cond.store1, label %else2 1571 // 1572 // cond.store1: 1573 // % Elt1 = extractelement <16 x i32> %Src, i32 1 1574 // % Ptr1 = extractelement <16 x i32*> %Ptrs, i32 1 1575 // store i32 % Elt1, i32* % Ptr1, align 4 1576 // br label %else2 1577 // . . . 1578 static void scalarizeMaskedScatter(CallInst *CI) { 1579 Value *Src = CI->getArgOperand(0); 1580 Value *Ptrs = CI->getArgOperand(1); 1581 Value *Alignment = CI->getArgOperand(2); 1582 Value *Mask = CI->getArgOperand(3); 1583 1584 assert(isa<VectorType>(Src->getType()) && 1585 "Unexpected data type in masked scatter intrinsic"); 1586 assert(isa<VectorType>(Ptrs->getType()) && 1587 isa<PointerType>(Ptrs->getType()->getVectorElementType()) && 1588 "Vector of pointers is expected in masked scatter intrinsic"); 1589 1590 IRBuilder<> Builder(CI->getContext()); 1591 Instruction *InsertPt = CI; 1592 BasicBlock *IfBlock = CI->getParent(); 1593 Builder.SetInsertPoint(InsertPt); 1594 Builder.SetCurrentDebugLocation(CI->getDebugLoc()); 1595 1596 unsigned AlignVal = cast<ConstantInt>(Alignment)->getZExtValue(); 1597 unsigned VectorWidth = Src->getType()->getVectorNumElements(); 1598 1599 // Shorten the way if the mask is a vector of constants. 1600 bool IsConstMask = isa<ConstantVector>(Mask); 1601 1602 if (IsConstMask) { 1603 for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) { 1604 if (cast<ConstantVector>(Mask)->getOperand(Idx)->isNullValue()) 1605 continue; 1606 Value *OneElt = Builder.CreateExtractElement(Src, Builder.getInt32(Idx), 1607 "Elt" + Twine(Idx)); 1608 Value *Ptr = Builder.CreateExtractElement(Ptrs, Builder.getInt32(Idx), 1609 "Ptr" + Twine(Idx)); 1610 Builder.CreateAlignedStore(OneElt, Ptr, AlignVal); 1611 } 1612 CI->eraseFromParent(); 1613 return; 1614 } 1615 for (unsigned Idx = 0; Idx < VectorWidth; ++Idx) { 1616 // Fill the "else" block, created in the previous iteration 1617 // 1618 // % Mask1 = extractelement <16 x i1> % Mask, i32 Idx 1619 // % ToStore = icmp eq i1 % Mask1, true 1620 // br i1 % ToStore, label %cond.store, label %else 1621 // 1622 Value *Predicate = Builder.CreateExtractElement(Mask, 1623 Builder.getInt32(Idx), 1624 "Mask" + Twine(Idx)); 1625 Value *Cmp = 1626 Builder.CreateICmp(ICmpInst::ICMP_EQ, Predicate, 1627 ConstantInt::get(Predicate->getType(), 1), 1628 "ToStore" + Twine(Idx)); 1629 1630 // Create "cond" block 1631 // 1632 // % Elt1 = extractelement <16 x i32> %Src, i32 1 1633 // % Ptr1 = extractelement <16 x i32*> %Ptrs, i32 1 1634 // %store i32 % Elt1, i32* % Ptr1 1635 // 1636 BasicBlock *CondBlock = IfBlock->splitBasicBlock(InsertPt, "cond.store"); 1637 Builder.SetInsertPoint(InsertPt); 1638 1639 Value *OneElt = Builder.CreateExtractElement(Src, Builder.getInt32(Idx), 1640 "Elt" + Twine(Idx)); 1641 Value *Ptr = Builder.CreateExtractElement(Ptrs, Builder.getInt32(Idx), 1642 "Ptr" + Twine(Idx)); 1643 Builder.CreateAlignedStore(OneElt, Ptr, AlignVal); 1644 1645 // Create "else" block, fill it in the next iteration 1646 BasicBlock *NewIfBlock = CondBlock->splitBasicBlock(InsertPt, "else"); 1647 Builder.SetInsertPoint(InsertPt); 1648 Instruction *OldBr = IfBlock->getTerminator(); 1649 BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr); 1650 OldBr->eraseFromParent(); 1651 IfBlock = NewIfBlock; 1652 } 1653 CI->eraseFromParent(); 1654 } 1655 1656 /// If counting leading or trailing zeros is an expensive operation and a zero 1657 /// input is defined, add a check for zero to avoid calling the intrinsic. 1658 /// 1659 /// We want to transform: 1660 /// %z = call i64 @llvm.cttz.i64(i64 %A, i1 false) 1661 /// 1662 /// into: 1663 /// entry: 1664 /// %cmpz = icmp eq i64 %A, 0 1665 /// br i1 %cmpz, label %cond.end, label %cond.false 1666 /// cond.false: 1667 /// %z = call i64 @llvm.cttz.i64(i64 %A, i1 true) 1668 /// br label %cond.end 1669 /// cond.end: 1670 /// %ctz = phi i64 [ 64, %entry ], [ %z, %cond.false ] 1671 /// 1672 /// If the transform is performed, return true and set ModifiedDT to true. 1673 static bool despeculateCountZeros(IntrinsicInst *CountZeros, 1674 const TargetLowering *TLI, 1675 const DataLayout *DL, 1676 bool &ModifiedDT) { 1677 if (!TLI || !DL) 1678 return false; 1679 1680 // If a zero input is undefined, it doesn't make sense to despeculate that. 1681 if (match(CountZeros->getOperand(1), m_One())) 1682 return false; 1683 1684 // If it's cheap to speculate, there's nothing to do. 1685 auto IntrinsicID = CountZeros->getIntrinsicID(); 1686 if ((IntrinsicID == Intrinsic::cttz && TLI->isCheapToSpeculateCttz()) || 1687 (IntrinsicID == Intrinsic::ctlz && TLI->isCheapToSpeculateCtlz())) 1688 return false; 1689 1690 // Only handle legal scalar cases. Anything else requires too much work. 1691 Type *Ty = CountZeros->getType(); 1692 unsigned SizeInBits = Ty->getPrimitiveSizeInBits(); 1693 if (Ty->isVectorTy() || SizeInBits > DL->getLargestLegalIntTypeSizeInBits()) 1694 return false; 1695 1696 // The intrinsic will be sunk behind a compare against zero and branch. 1697 BasicBlock *StartBlock = CountZeros->getParent(); 1698 BasicBlock *CallBlock = StartBlock->splitBasicBlock(CountZeros, "cond.false"); 1699 1700 // Create another block after the count zero intrinsic. A PHI will be added 1701 // in this block to select the result of the intrinsic or the bit-width 1702 // constant if the input to the intrinsic is zero. 1703 BasicBlock::iterator SplitPt = ++(BasicBlock::iterator(CountZeros)); 1704 BasicBlock *EndBlock = CallBlock->splitBasicBlock(SplitPt, "cond.end"); 1705 1706 // Set up a builder to create a compare, conditional branch, and PHI. 1707 IRBuilder<> Builder(CountZeros->getContext()); 1708 Builder.SetInsertPoint(StartBlock->getTerminator()); 1709 Builder.SetCurrentDebugLocation(CountZeros->getDebugLoc()); 1710 1711 // Replace the unconditional branch that was created by the first split with 1712 // a compare against zero and a conditional branch. 1713 Value *Zero = Constant::getNullValue(Ty); 1714 Value *Cmp = Builder.CreateICmpEQ(CountZeros->getOperand(0), Zero, "cmpz"); 1715 Builder.CreateCondBr(Cmp, EndBlock, CallBlock); 1716 StartBlock->getTerminator()->eraseFromParent(); 1717 1718 // Create a PHI in the end block to select either the output of the intrinsic 1719 // or the bit width of the operand. 1720 Builder.SetInsertPoint(&EndBlock->front()); 1721 PHINode *PN = Builder.CreatePHI(Ty, 2, "ctz"); 1722 CountZeros->replaceAllUsesWith(PN); 1723 Value *BitWidth = Builder.getInt(APInt(SizeInBits, SizeInBits)); 1724 PN->addIncoming(BitWidth, StartBlock); 1725 PN->addIncoming(CountZeros, CallBlock); 1726 1727 // We are explicitly handling the zero case, so we can set the intrinsic's 1728 // undefined zero argument to 'true'. This will also prevent reprocessing the 1729 // intrinsic; we only despeculate when a zero input is defined. 1730 CountZeros->setArgOperand(1, Builder.getTrue()); 1731 ModifiedDT = true; 1732 return true; 1733 } 1734 1735 bool CodeGenPrepare::optimizeCallInst(CallInst *CI, bool& ModifiedDT) { 1736 BasicBlock *BB = CI->getParent(); 1737 1738 // Lower inline assembly if we can. 1739 // If we found an inline asm expession, and if the target knows how to 1740 // lower it to normal LLVM code, do so now. 1741 if (TLI && isa<InlineAsm>(CI->getCalledValue())) { 1742 if (TLI->ExpandInlineAsm(CI)) { 1743 // Avoid invalidating the iterator. 1744 CurInstIterator = BB->begin(); 1745 // Avoid processing instructions out of order, which could cause 1746 // reuse before a value is defined. 1747 SunkAddrs.clear(); 1748 return true; 1749 } 1750 // Sink address computing for memory operands into the block. 1751 if (optimizeInlineAsmInst(CI)) 1752 return true; 1753 } 1754 1755 // Align the pointer arguments to this call if the target thinks it's a good 1756 // idea 1757 unsigned MinSize, PrefAlign; 1758 if (TLI && TLI->shouldAlignPointerArgs(CI, MinSize, PrefAlign)) { 1759 for (auto &Arg : CI->arg_operands()) { 1760 // We want to align both objects whose address is used directly and 1761 // objects whose address is used in casts and GEPs, though it only makes 1762 // sense for GEPs if the offset is a multiple of the desired alignment and 1763 // if size - offset meets the size threshold. 1764 if (!Arg->getType()->isPointerTy()) 1765 continue; 1766 APInt Offset(DL->getPointerSizeInBits( 1767 cast<PointerType>(Arg->getType())->getAddressSpace()), 1768 0); 1769 Value *Val = Arg->stripAndAccumulateInBoundsConstantOffsets(*DL, Offset); 1770 uint64_t Offset2 = Offset.getLimitedValue(); 1771 if ((Offset2 & (PrefAlign-1)) != 0) 1772 continue; 1773 AllocaInst *AI; 1774 if ((AI = dyn_cast<AllocaInst>(Val)) && AI->getAlignment() < PrefAlign && 1775 DL->getTypeAllocSize(AI->getAllocatedType()) >= MinSize + Offset2) 1776 AI->setAlignment(PrefAlign); 1777 // Global variables can only be aligned if they are defined in this 1778 // object (i.e. they are uniquely initialized in this object), and 1779 // over-aligning global variables that have an explicit section is 1780 // forbidden. 1781 GlobalVariable *GV; 1782 if ((GV = dyn_cast<GlobalVariable>(Val)) && GV->canIncreaseAlignment() && 1783 GV->getAlignment() < PrefAlign && 1784 DL->getTypeAllocSize(GV->getValueType()) >= 1785 MinSize + Offset2) 1786 GV->setAlignment(PrefAlign); 1787 } 1788 // If this is a memcpy (or similar) then we may be able to improve the 1789 // alignment 1790 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(CI)) { 1791 unsigned Align = getKnownAlignment(MI->getDest(), *DL); 1792 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) 1793 Align = std::min(Align, getKnownAlignment(MTI->getSource(), *DL)); 1794 if (Align > MI->getAlignment()) 1795 MI->setAlignment(ConstantInt::get(MI->getAlignmentType(), Align)); 1796 } 1797 } 1798 1799 // If we have a cold call site, try to sink addressing computation into the 1800 // cold block. This interacts with our handling for loads and stores to 1801 // ensure that we can fold all uses of a potential addressing computation 1802 // into their uses. TODO: generalize this to work over profiling data 1803 if (!OptSize && CI->hasFnAttr(Attribute::Cold)) 1804 for (auto &Arg : CI->arg_operands()) { 1805 if (!Arg->getType()->isPointerTy()) 1806 continue; 1807 unsigned AS = Arg->getType()->getPointerAddressSpace(); 1808 return optimizeMemoryInst(CI, Arg, Arg->getType(), AS); 1809 } 1810 1811 IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI); 1812 if (II) { 1813 switch (II->getIntrinsicID()) { 1814 default: break; 1815 case Intrinsic::objectsize: { 1816 // Lower all uses of llvm.objectsize.* 1817 uint64_t Size; 1818 Type *ReturnTy = CI->getType(); 1819 Constant *RetVal = nullptr; 1820 ConstantInt *Op1 = cast<ConstantInt>(II->getArgOperand(1)); 1821 ObjSizeMode Mode = Op1->isZero() ? ObjSizeMode::Max : ObjSizeMode::Min; 1822 if (getObjectSize(II->getArgOperand(0), 1823 Size, *DL, TLInfo, false, Mode)) { 1824 RetVal = ConstantInt::get(ReturnTy, Size); 1825 } else { 1826 RetVal = ConstantInt::get(ReturnTy, 1827 Mode == ObjSizeMode::Min ? 0 : -1ULL); 1828 } 1829 // Substituting this can cause recursive simplifications, which can 1830 // invalidate our iterator. Use a WeakVH to hold onto it in case this 1831 // happens. 1832 Value *CurValue = &*CurInstIterator; 1833 WeakVH IterHandle(CurValue); 1834 1835 replaceAndRecursivelySimplify(CI, RetVal, TLInfo, nullptr); 1836 1837 // If the iterator instruction was recursively deleted, start over at the 1838 // start of the block. 1839 if (IterHandle != CurValue) { 1840 CurInstIterator = BB->begin(); 1841 SunkAddrs.clear(); 1842 } 1843 return true; 1844 } 1845 case Intrinsic::masked_load: { 1846 // Scalarize unsupported vector masked load 1847 if (!TTI->isLegalMaskedLoad(CI->getType())) { 1848 scalarizeMaskedLoad(CI); 1849 ModifiedDT = true; 1850 return true; 1851 } 1852 return false; 1853 } 1854 case Intrinsic::masked_store: { 1855 if (!TTI->isLegalMaskedStore(CI->getArgOperand(0)->getType())) { 1856 scalarizeMaskedStore(CI); 1857 ModifiedDT = true; 1858 return true; 1859 } 1860 return false; 1861 } 1862 case Intrinsic::masked_gather: { 1863 if (!TTI->isLegalMaskedGather(CI->getType())) { 1864 scalarizeMaskedGather(CI); 1865 ModifiedDT = true; 1866 return true; 1867 } 1868 return false; 1869 } 1870 case Intrinsic::masked_scatter: { 1871 if (!TTI->isLegalMaskedScatter(CI->getArgOperand(0)->getType())) { 1872 scalarizeMaskedScatter(CI); 1873 ModifiedDT = true; 1874 return true; 1875 } 1876 return false; 1877 } 1878 case Intrinsic::aarch64_stlxr: 1879 case Intrinsic::aarch64_stxr: { 1880 ZExtInst *ExtVal = dyn_cast<ZExtInst>(CI->getArgOperand(0)); 1881 if (!ExtVal || !ExtVal->hasOneUse() || 1882 ExtVal->getParent() == CI->getParent()) 1883 return false; 1884 // Sink a zext feeding stlxr/stxr before it, so it can be folded into it. 1885 ExtVal->moveBefore(CI); 1886 // Mark this instruction as "inserted by CGP", so that other 1887 // optimizations don't touch it. 1888 InsertedInsts.insert(ExtVal); 1889 return true; 1890 } 1891 case Intrinsic::invariant_group_barrier: 1892 II->replaceAllUsesWith(II->getArgOperand(0)); 1893 II->eraseFromParent(); 1894 return true; 1895 1896 case Intrinsic::cttz: 1897 case Intrinsic::ctlz: 1898 // If counting zeros is expensive, try to avoid it. 1899 return despeculateCountZeros(II, TLI, DL, ModifiedDT); 1900 } 1901 1902 if (TLI) { 1903 // Unknown address space. 1904 // TODO: Target hook to pick which address space the intrinsic cares 1905 // about? 1906 unsigned AddrSpace = ~0u; 1907 SmallVector<Value*, 2> PtrOps; 1908 Type *AccessTy; 1909 if (TLI->GetAddrModeArguments(II, PtrOps, AccessTy, AddrSpace)) 1910 while (!PtrOps.empty()) 1911 if (optimizeMemoryInst(II, PtrOps.pop_back_val(), AccessTy, AddrSpace)) 1912 return true; 1913 } 1914 } 1915 1916 // From here on out we're working with named functions. 1917 if (!CI->getCalledFunction()) return false; 1918 1919 // Lower all default uses of _chk calls. This is very similar 1920 // to what InstCombineCalls does, but here we are only lowering calls 1921 // to fortified library functions (e.g. __memcpy_chk) that have the default 1922 // "don't know" as the objectsize. Anything else should be left alone. 1923 FortifiedLibCallSimplifier Simplifier(TLInfo, true); 1924 if (Value *V = Simplifier.optimizeCall(CI)) { 1925 CI->replaceAllUsesWith(V); 1926 CI->eraseFromParent(); 1927 return true; 1928 } 1929 return false; 1930 } 1931 1932 /// Look for opportunities to duplicate return instructions to the predecessor 1933 /// to enable tail call optimizations. The case it is currently looking for is: 1934 /// @code 1935 /// bb0: 1936 /// %tmp0 = tail call i32 @f0() 1937 /// br label %return 1938 /// bb1: 1939 /// %tmp1 = tail call i32 @f1() 1940 /// br label %return 1941 /// bb2: 1942 /// %tmp2 = tail call i32 @f2() 1943 /// br label %return 1944 /// return: 1945 /// %retval = phi i32 [ %tmp0, %bb0 ], [ %tmp1, %bb1 ], [ %tmp2, %bb2 ] 1946 /// ret i32 %retval 1947 /// @endcode 1948 /// 1949 /// => 1950 /// 1951 /// @code 1952 /// bb0: 1953 /// %tmp0 = tail call i32 @f0() 1954 /// ret i32 %tmp0 1955 /// bb1: 1956 /// %tmp1 = tail call i32 @f1() 1957 /// ret i32 %tmp1 1958 /// bb2: 1959 /// %tmp2 = tail call i32 @f2() 1960 /// ret i32 %tmp2 1961 /// @endcode 1962 bool CodeGenPrepare::dupRetToEnableTailCallOpts(BasicBlock *BB) { 1963 if (!TLI) 1964 return false; 1965 1966 ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()); 1967 if (!RI) 1968 return false; 1969 1970 PHINode *PN = nullptr; 1971 BitCastInst *BCI = nullptr; 1972 Value *V = RI->getReturnValue(); 1973 if (V) { 1974 BCI = dyn_cast<BitCastInst>(V); 1975 if (BCI) 1976 V = BCI->getOperand(0); 1977 1978 PN = dyn_cast<PHINode>(V); 1979 if (!PN) 1980 return false; 1981 } 1982 1983 if (PN && PN->getParent() != BB) 1984 return false; 1985 1986 // It's not safe to eliminate the sign / zero extension of the return value. 1987 // See llvm::isInTailCallPosition(). 1988 const Function *F = BB->getParent(); 1989 AttributeSet CallerAttrs = F->getAttributes(); 1990 if (CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::ZExt) || 1991 CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::SExt)) 1992 return false; 1993 1994 // Make sure there are no instructions between the PHI and return, or that the 1995 // return is the first instruction in the block. 1996 if (PN) { 1997 BasicBlock::iterator BI = BB->begin(); 1998 do { ++BI; } while (isa<DbgInfoIntrinsic>(BI)); 1999 if (&*BI == BCI) 2000 // Also skip over the bitcast. 2001 ++BI; 2002 if (&*BI != RI) 2003 return false; 2004 } else { 2005 BasicBlock::iterator BI = BB->begin(); 2006 while (isa<DbgInfoIntrinsic>(BI)) ++BI; 2007 if (&*BI != RI) 2008 return false; 2009 } 2010 2011 /// Only dup the ReturnInst if the CallInst is likely to be emitted as a tail 2012 /// call. 2013 SmallVector<CallInst*, 4> TailCalls; 2014 if (PN) { 2015 for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) { 2016 CallInst *CI = dyn_cast<CallInst>(PN->getIncomingValue(I)); 2017 // Make sure the phi value is indeed produced by the tail call. 2018 if (CI && CI->hasOneUse() && CI->getParent() == PN->getIncomingBlock(I) && 2019 TLI->mayBeEmittedAsTailCall(CI)) 2020 TailCalls.push_back(CI); 2021 } 2022 } else { 2023 SmallPtrSet<BasicBlock*, 4> VisitedBBs; 2024 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) { 2025 if (!VisitedBBs.insert(*PI).second) 2026 continue; 2027 2028 BasicBlock::InstListType &InstList = (*PI)->getInstList(); 2029 BasicBlock::InstListType::reverse_iterator RI = InstList.rbegin(); 2030 BasicBlock::InstListType::reverse_iterator RE = InstList.rend(); 2031 do { ++RI; } while (RI != RE && isa<DbgInfoIntrinsic>(&*RI)); 2032 if (RI == RE) 2033 continue; 2034 2035 CallInst *CI = dyn_cast<CallInst>(&*RI); 2036 if (CI && CI->use_empty() && TLI->mayBeEmittedAsTailCall(CI)) 2037 TailCalls.push_back(CI); 2038 } 2039 } 2040 2041 bool Changed = false; 2042 for (unsigned i = 0, e = TailCalls.size(); i != e; ++i) { 2043 CallInst *CI = TailCalls[i]; 2044 CallSite CS(CI); 2045 2046 // Conservatively require the attributes of the call to match those of the 2047 // return. Ignore noalias because it doesn't affect the call sequence. 2048 AttributeSet CalleeAttrs = CS.getAttributes(); 2049 if (AttrBuilder(CalleeAttrs, AttributeSet::ReturnIndex). 2050 removeAttribute(Attribute::NoAlias) != 2051 AttrBuilder(CalleeAttrs, AttributeSet::ReturnIndex). 2052 removeAttribute(Attribute::NoAlias)) 2053 continue; 2054 2055 // Make sure the call instruction is followed by an unconditional branch to 2056 // the return block. 2057 BasicBlock *CallBB = CI->getParent(); 2058 BranchInst *BI = dyn_cast<BranchInst>(CallBB->getTerminator()); 2059 if (!BI || !BI->isUnconditional() || BI->getSuccessor(0) != BB) 2060 continue; 2061 2062 // Duplicate the return into CallBB. 2063 (void)FoldReturnIntoUncondBranch(RI, BB, CallBB); 2064 ModifiedDT = Changed = true; 2065 ++NumRetsDup; 2066 } 2067 2068 // If we eliminated all predecessors of the block, delete the block now. 2069 if (Changed && !BB->hasAddressTaken() && pred_begin(BB) == pred_end(BB)) 2070 BB->eraseFromParent(); 2071 2072 return Changed; 2073 } 2074 2075 //===----------------------------------------------------------------------===// 2076 // Memory Optimization 2077 //===----------------------------------------------------------------------===// 2078 2079 namespace { 2080 2081 /// This is an extended version of TargetLowering::AddrMode 2082 /// which holds actual Value*'s for register values. 2083 struct ExtAddrMode : public TargetLowering::AddrMode { 2084 Value *BaseReg; 2085 Value *ScaledReg; 2086 ExtAddrMode() : BaseReg(nullptr), ScaledReg(nullptr) {} 2087 void print(raw_ostream &OS) const; 2088 void dump() const; 2089 2090 bool operator==(const ExtAddrMode& O) const { 2091 return (BaseReg == O.BaseReg) && (ScaledReg == O.ScaledReg) && 2092 (BaseGV == O.BaseGV) && (BaseOffs == O.BaseOffs) && 2093 (HasBaseReg == O.HasBaseReg) && (Scale == O.Scale); 2094 } 2095 }; 2096 2097 #ifndef NDEBUG 2098 static inline raw_ostream &operator<<(raw_ostream &OS, const ExtAddrMode &AM) { 2099 AM.print(OS); 2100 return OS; 2101 } 2102 #endif 2103 2104 void ExtAddrMode::print(raw_ostream &OS) const { 2105 bool NeedPlus = false; 2106 OS << "["; 2107 if (BaseGV) { 2108 OS << (NeedPlus ? " + " : "") 2109 << "GV:"; 2110 BaseGV->printAsOperand(OS, /*PrintType=*/false); 2111 NeedPlus = true; 2112 } 2113 2114 if (BaseOffs) { 2115 OS << (NeedPlus ? " + " : "") 2116 << BaseOffs; 2117 NeedPlus = true; 2118 } 2119 2120 if (BaseReg) { 2121 OS << (NeedPlus ? " + " : "") 2122 << "Base:"; 2123 BaseReg->printAsOperand(OS, /*PrintType=*/false); 2124 NeedPlus = true; 2125 } 2126 if (Scale) { 2127 OS << (NeedPlus ? " + " : "") 2128 << Scale << "*"; 2129 ScaledReg->printAsOperand(OS, /*PrintType=*/false); 2130 } 2131 2132 OS << ']'; 2133 } 2134 2135 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 2136 LLVM_DUMP_METHOD void ExtAddrMode::dump() const { 2137 print(dbgs()); 2138 dbgs() << '\n'; 2139 } 2140 #endif 2141 2142 /// \brief This class provides transaction based operation on the IR. 2143 /// Every change made through this class is recorded in the internal state and 2144 /// can be undone (rollback) until commit is called. 2145 class TypePromotionTransaction { 2146 2147 /// \brief This represents the common interface of the individual transaction. 2148 /// Each class implements the logic for doing one specific modification on 2149 /// the IR via the TypePromotionTransaction. 2150 class TypePromotionAction { 2151 protected: 2152 /// The Instruction modified. 2153 Instruction *Inst; 2154 2155 public: 2156 /// \brief Constructor of the action. 2157 /// The constructor performs the related action on the IR. 2158 TypePromotionAction(Instruction *Inst) : Inst(Inst) {} 2159 2160 virtual ~TypePromotionAction() {} 2161 2162 /// \brief Undo the modification done by this action. 2163 /// When this method is called, the IR must be in the same state as it was 2164 /// before this action was applied. 2165 /// \pre Undoing the action works if and only if the IR is in the exact same 2166 /// state as it was directly after this action was applied. 2167 virtual void undo() = 0; 2168 2169 /// \brief Advocate every change made by this action. 2170 /// When the results on the IR of the action are to be kept, it is important 2171 /// to call this function, otherwise hidden information may be kept forever. 2172 virtual void commit() { 2173 // Nothing to be done, this action is not doing anything. 2174 } 2175 }; 2176 2177 /// \brief Utility to remember the position of an instruction. 2178 class InsertionHandler { 2179 /// Position of an instruction. 2180 /// Either an instruction: 2181 /// - Is the first in a basic block: BB is used. 2182 /// - Has a previous instructon: PrevInst is used. 2183 union { 2184 Instruction *PrevInst; 2185 BasicBlock *BB; 2186 } Point; 2187 /// Remember whether or not the instruction had a previous instruction. 2188 bool HasPrevInstruction; 2189 2190 public: 2191 /// \brief Record the position of \p Inst. 2192 InsertionHandler(Instruction *Inst) { 2193 BasicBlock::iterator It = Inst->getIterator(); 2194 HasPrevInstruction = (It != (Inst->getParent()->begin())); 2195 if (HasPrevInstruction) 2196 Point.PrevInst = &*--It; 2197 else 2198 Point.BB = Inst->getParent(); 2199 } 2200 2201 /// \brief Insert \p Inst at the recorded position. 2202 void insert(Instruction *Inst) { 2203 if (HasPrevInstruction) { 2204 if (Inst->getParent()) 2205 Inst->removeFromParent(); 2206 Inst->insertAfter(Point.PrevInst); 2207 } else { 2208 Instruction *Position = &*Point.BB->getFirstInsertionPt(); 2209 if (Inst->getParent()) 2210 Inst->moveBefore(Position); 2211 else 2212 Inst->insertBefore(Position); 2213 } 2214 } 2215 }; 2216 2217 /// \brief Move an instruction before another. 2218 class InstructionMoveBefore : public TypePromotionAction { 2219 /// Original position of the instruction. 2220 InsertionHandler Position; 2221 2222 public: 2223 /// \brief Move \p Inst before \p Before. 2224 InstructionMoveBefore(Instruction *Inst, Instruction *Before) 2225 : TypePromotionAction(Inst), Position(Inst) { 2226 DEBUG(dbgs() << "Do: move: " << *Inst << "\nbefore: " << *Before << "\n"); 2227 Inst->moveBefore(Before); 2228 } 2229 2230 /// \brief Move the instruction back to its original position. 2231 void undo() override { 2232 DEBUG(dbgs() << "Undo: moveBefore: " << *Inst << "\n"); 2233 Position.insert(Inst); 2234 } 2235 }; 2236 2237 /// \brief Set the operand of an instruction with a new value. 2238 class OperandSetter : public TypePromotionAction { 2239 /// Original operand of the instruction. 2240 Value *Origin; 2241 /// Index of the modified instruction. 2242 unsigned Idx; 2243 2244 public: 2245 /// \brief Set \p Idx operand of \p Inst with \p NewVal. 2246 OperandSetter(Instruction *Inst, unsigned Idx, Value *NewVal) 2247 : TypePromotionAction(Inst), Idx(Idx) { 2248 DEBUG(dbgs() << "Do: setOperand: " << Idx << "\n" 2249 << "for:" << *Inst << "\n" 2250 << "with:" << *NewVal << "\n"); 2251 Origin = Inst->getOperand(Idx); 2252 Inst->setOperand(Idx, NewVal); 2253 } 2254 2255 /// \brief Restore the original value of the instruction. 2256 void undo() override { 2257 DEBUG(dbgs() << "Undo: setOperand:" << Idx << "\n" 2258 << "for: " << *Inst << "\n" 2259 << "with: " << *Origin << "\n"); 2260 Inst->setOperand(Idx, Origin); 2261 } 2262 }; 2263 2264 /// \brief Hide the operands of an instruction. 2265 /// Do as if this instruction was not using any of its operands. 2266 class OperandsHider : public TypePromotionAction { 2267 /// The list of original operands. 2268 SmallVector<Value *, 4> OriginalValues; 2269 2270 public: 2271 /// \brief Remove \p Inst from the uses of the operands of \p Inst. 2272 OperandsHider(Instruction *Inst) : TypePromotionAction(Inst) { 2273 DEBUG(dbgs() << "Do: OperandsHider: " << *Inst << "\n"); 2274 unsigned NumOpnds = Inst->getNumOperands(); 2275 OriginalValues.reserve(NumOpnds); 2276 for (unsigned It = 0; It < NumOpnds; ++It) { 2277 // Save the current operand. 2278 Value *Val = Inst->getOperand(It); 2279 OriginalValues.push_back(Val); 2280 // Set a dummy one. 2281 // We could use OperandSetter here, but that would imply an overhead 2282 // that we are not willing to pay. 2283 Inst->setOperand(It, UndefValue::get(Val->getType())); 2284 } 2285 } 2286 2287 /// \brief Restore the original list of uses. 2288 void undo() override { 2289 DEBUG(dbgs() << "Undo: OperandsHider: " << *Inst << "\n"); 2290 for (unsigned It = 0, EndIt = OriginalValues.size(); It != EndIt; ++It) 2291 Inst->setOperand(It, OriginalValues[It]); 2292 } 2293 }; 2294 2295 /// \brief Build a truncate instruction. 2296 class TruncBuilder : public TypePromotionAction { 2297 Value *Val; 2298 public: 2299 /// \brief Build a truncate instruction of \p Opnd producing a \p Ty 2300 /// result. 2301 /// trunc Opnd to Ty. 2302 TruncBuilder(Instruction *Opnd, Type *Ty) : TypePromotionAction(Opnd) { 2303 IRBuilder<> Builder(Opnd); 2304 Val = Builder.CreateTrunc(Opnd, Ty, "promoted"); 2305 DEBUG(dbgs() << "Do: TruncBuilder: " << *Val << "\n"); 2306 } 2307 2308 /// \brief Get the built value. 2309 Value *getBuiltValue() { return Val; } 2310 2311 /// \brief Remove the built instruction. 2312 void undo() override { 2313 DEBUG(dbgs() << "Undo: TruncBuilder: " << *Val << "\n"); 2314 if (Instruction *IVal = dyn_cast<Instruction>(Val)) 2315 IVal->eraseFromParent(); 2316 } 2317 }; 2318 2319 /// \brief Build a sign extension instruction. 2320 class SExtBuilder : public TypePromotionAction { 2321 Value *Val; 2322 public: 2323 /// \brief Build a sign extension instruction of \p Opnd producing a \p Ty 2324 /// result. 2325 /// sext Opnd to Ty. 2326 SExtBuilder(Instruction *InsertPt, Value *Opnd, Type *Ty) 2327 : TypePromotionAction(InsertPt) { 2328 IRBuilder<> Builder(InsertPt); 2329 Val = Builder.CreateSExt(Opnd, Ty, "promoted"); 2330 DEBUG(dbgs() << "Do: SExtBuilder: " << *Val << "\n"); 2331 } 2332 2333 /// \brief Get the built value. 2334 Value *getBuiltValue() { return Val; } 2335 2336 /// \brief Remove the built instruction. 2337 void undo() override { 2338 DEBUG(dbgs() << "Undo: SExtBuilder: " << *Val << "\n"); 2339 if (Instruction *IVal = dyn_cast<Instruction>(Val)) 2340 IVal->eraseFromParent(); 2341 } 2342 }; 2343 2344 /// \brief Build a zero extension instruction. 2345 class ZExtBuilder : public TypePromotionAction { 2346 Value *Val; 2347 public: 2348 /// \brief Build a zero extension instruction of \p Opnd producing a \p Ty 2349 /// result. 2350 /// zext Opnd to Ty. 2351 ZExtBuilder(Instruction *InsertPt, Value *Opnd, Type *Ty) 2352 : TypePromotionAction(InsertPt) { 2353 IRBuilder<> Builder(InsertPt); 2354 Val = Builder.CreateZExt(Opnd, Ty, "promoted"); 2355 DEBUG(dbgs() << "Do: ZExtBuilder: " << *Val << "\n"); 2356 } 2357 2358 /// \brief Get the built value. 2359 Value *getBuiltValue() { return Val; } 2360 2361 /// \brief Remove the built instruction. 2362 void undo() override { 2363 DEBUG(dbgs() << "Undo: ZExtBuilder: " << *Val << "\n"); 2364 if (Instruction *IVal = dyn_cast<Instruction>(Val)) 2365 IVal->eraseFromParent(); 2366 } 2367 }; 2368 2369 /// \brief Mutate an instruction to another type. 2370 class TypeMutator : public TypePromotionAction { 2371 /// Record the original type. 2372 Type *OrigTy; 2373 2374 public: 2375 /// \brief Mutate the type of \p Inst into \p NewTy. 2376 TypeMutator(Instruction *Inst, Type *NewTy) 2377 : TypePromotionAction(Inst), OrigTy(Inst->getType()) { 2378 DEBUG(dbgs() << "Do: MutateType: " << *Inst << " with " << *NewTy 2379 << "\n"); 2380 Inst->mutateType(NewTy); 2381 } 2382 2383 /// \brief Mutate the instruction back to its original type. 2384 void undo() override { 2385 DEBUG(dbgs() << "Undo: MutateType: " << *Inst << " with " << *OrigTy 2386 << "\n"); 2387 Inst->mutateType(OrigTy); 2388 } 2389 }; 2390 2391 /// \brief Replace the uses of an instruction by another instruction. 2392 class UsesReplacer : public TypePromotionAction { 2393 /// Helper structure to keep track of the replaced uses. 2394 struct InstructionAndIdx { 2395 /// The instruction using the instruction. 2396 Instruction *Inst; 2397 /// The index where this instruction is used for Inst. 2398 unsigned Idx; 2399 InstructionAndIdx(Instruction *Inst, unsigned Idx) 2400 : Inst(Inst), Idx(Idx) {} 2401 }; 2402 2403 /// Keep track of the original uses (pair Instruction, Index). 2404 SmallVector<InstructionAndIdx, 4> OriginalUses; 2405 typedef SmallVectorImpl<InstructionAndIdx>::iterator use_iterator; 2406 2407 public: 2408 /// \brief Replace all the use of \p Inst by \p New. 2409 UsesReplacer(Instruction *Inst, Value *New) : TypePromotionAction(Inst) { 2410 DEBUG(dbgs() << "Do: UsersReplacer: " << *Inst << " with " << *New 2411 << "\n"); 2412 // Record the original uses. 2413 for (Use &U : Inst->uses()) { 2414 Instruction *UserI = cast<Instruction>(U.getUser()); 2415 OriginalUses.push_back(InstructionAndIdx(UserI, U.getOperandNo())); 2416 } 2417 // Now, we can replace the uses. 2418 Inst->replaceAllUsesWith(New); 2419 } 2420 2421 /// \brief Reassign the original uses of Inst to Inst. 2422 void undo() override { 2423 DEBUG(dbgs() << "Undo: UsersReplacer: " << *Inst << "\n"); 2424 for (use_iterator UseIt = OriginalUses.begin(), 2425 EndIt = OriginalUses.end(); 2426 UseIt != EndIt; ++UseIt) { 2427 UseIt->Inst->setOperand(UseIt->Idx, Inst); 2428 } 2429 } 2430 }; 2431 2432 /// \brief Remove an instruction from the IR. 2433 class InstructionRemover : public TypePromotionAction { 2434 /// Original position of the instruction. 2435 InsertionHandler Inserter; 2436 /// Helper structure to hide all the link to the instruction. In other 2437 /// words, this helps to do as if the instruction was removed. 2438 OperandsHider Hider; 2439 /// Keep track of the uses replaced, if any. 2440 UsesReplacer *Replacer; 2441 2442 public: 2443 /// \brief Remove all reference of \p Inst and optinally replace all its 2444 /// uses with New. 2445 /// \pre If !Inst->use_empty(), then New != nullptr 2446 InstructionRemover(Instruction *Inst, Value *New = nullptr) 2447 : TypePromotionAction(Inst), Inserter(Inst), Hider(Inst), 2448 Replacer(nullptr) { 2449 if (New) 2450 Replacer = new UsesReplacer(Inst, New); 2451 DEBUG(dbgs() << "Do: InstructionRemover: " << *Inst << "\n"); 2452 Inst->removeFromParent(); 2453 } 2454 2455 ~InstructionRemover() override { delete Replacer; } 2456 2457 /// \brief Really remove the instruction. 2458 void commit() override { delete Inst; } 2459 2460 /// \brief Resurrect the instruction and reassign it to the proper uses if 2461 /// new value was provided when build this action. 2462 void undo() override { 2463 DEBUG(dbgs() << "Undo: InstructionRemover: " << *Inst << "\n"); 2464 Inserter.insert(Inst); 2465 if (Replacer) 2466 Replacer->undo(); 2467 Hider.undo(); 2468 } 2469 }; 2470 2471 public: 2472 /// Restoration point. 2473 /// The restoration point is a pointer to an action instead of an iterator 2474 /// because the iterator may be invalidated but not the pointer. 2475 typedef const TypePromotionAction *ConstRestorationPt; 2476 /// Advocate every changes made in that transaction. 2477 void commit(); 2478 /// Undo all the changes made after the given point. 2479 void rollback(ConstRestorationPt Point); 2480 /// Get the current restoration point. 2481 ConstRestorationPt getRestorationPoint() const; 2482 2483 /// \name API for IR modification with state keeping to support rollback. 2484 /// @{ 2485 /// Same as Instruction::setOperand. 2486 void setOperand(Instruction *Inst, unsigned Idx, Value *NewVal); 2487 /// Same as Instruction::eraseFromParent. 2488 void eraseInstruction(Instruction *Inst, Value *NewVal = nullptr); 2489 /// Same as Value::replaceAllUsesWith. 2490 void replaceAllUsesWith(Instruction *Inst, Value *New); 2491 /// Same as Value::mutateType. 2492 void mutateType(Instruction *Inst, Type *NewTy); 2493 /// Same as IRBuilder::createTrunc. 2494 Value *createTrunc(Instruction *Opnd, Type *Ty); 2495 /// Same as IRBuilder::createSExt. 2496 Value *createSExt(Instruction *Inst, Value *Opnd, Type *Ty); 2497 /// Same as IRBuilder::createZExt. 2498 Value *createZExt(Instruction *Inst, Value *Opnd, Type *Ty); 2499 /// Same as Instruction::moveBefore. 2500 void moveBefore(Instruction *Inst, Instruction *Before); 2501 /// @} 2502 2503 private: 2504 /// The ordered list of actions made so far. 2505 SmallVector<std::unique_ptr<TypePromotionAction>, 16> Actions; 2506 typedef SmallVectorImpl<std::unique_ptr<TypePromotionAction>>::iterator CommitPt; 2507 }; 2508 2509 void TypePromotionTransaction::setOperand(Instruction *Inst, unsigned Idx, 2510 Value *NewVal) { 2511 Actions.push_back( 2512 make_unique<TypePromotionTransaction::OperandSetter>(Inst, Idx, NewVal)); 2513 } 2514 2515 void TypePromotionTransaction::eraseInstruction(Instruction *Inst, 2516 Value *NewVal) { 2517 Actions.push_back( 2518 make_unique<TypePromotionTransaction::InstructionRemover>(Inst, NewVal)); 2519 } 2520 2521 void TypePromotionTransaction::replaceAllUsesWith(Instruction *Inst, 2522 Value *New) { 2523 Actions.push_back(make_unique<TypePromotionTransaction::UsesReplacer>(Inst, New)); 2524 } 2525 2526 void TypePromotionTransaction::mutateType(Instruction *Inst, Type *NewTy) { 2527 Actions.push_back(make_unique<TypePromotionTransaction::TypeMutator>(Inst, NewTy)); 2528 } 2529 2530 Value *TypePromotionTransaction::createTrunc(Instruction *Opnd, 2531 Type *Ty) { 2532 std::unique_ptr<TruncBuilder> Ptr(new TruncBuilder(Opnd, Ty)); 2533 Value *Val = Ptr->getBuiltValue(); 2534 Actions.push_back(std::move(Ptr)); 2535 return Val; 2536 } 2537 2538 Value *TypePromotionTransaction::createSExt(Instruction *Inst, 2539 Value *Opnd, Type *Ty) { 2540 std::unique_ptr<SExtBuilder> Ptr(new SExtBuilder(Inst, Opnd, Ty)); 2541 Value *Val = Ptr->getBuiltValue(); 2542 Actions.push_back(std::move(Ptr)); 2543 return Val; 2544 } 2545 2546 Value *TypePromotionTransaction::createZExt(Instruction *Inst, 2547 Value *Opnd, Type *Ty) { 2548 std::unique_ptr<ZExtBuilder> Ptr(new ZExtBuilder(Inst, Opnd, Ty)); 2549 Value *Val = Ptr->getBuiltValue(); 2550 Actions.push_back(std::move(Ptr)); 2551 return Val; 2552 } 2553 2554 void TypePromotionTransaction::moveBefore(Instruction *Inst, 2555 Instruction *Before) { 2556 Actions.push_back( 2557 make_unique<TypePromotionTransaction::InstructionMoveBefore>(Inst, Before)); 2558 } 2559 2560 TypePromotionTransaction::ConstRestorationPt 2561 TypePromotionTransaction::getRestorationPoint() const { 2562 return !Actions.empty() ? Actions.back().get() : nullptr; 2563 } 2564 2565 void TypePromotionTransaction::commit() { 2566 for (CommitPt It = Actions.begin(), EndIt = Actions.end(); It != EndIt; 2567 ++It) 2568 (*It)->commit(); 2569 Actions.clear(); 2570 } 2571 2572 void TypePromotionTransaction::rollback( 2573 TypePromotionTransaction::ConstRestorationPt Point) { 2574 while (!Actions.empty() && Point != Actions.back().get()) { 2575 std::unique_ptr<TypePromotionAction> Curr = Actions.pop_back_val(); 2576 Curr->undo(); 2577 } 2578 } 2579 2580 /// \brief A helper class for matching addressing modes. 2581 /// 2582 /// This encapsulates the logic for matching the target-legal addressing modes. 2583 class AddressingModeMatcher { 2584 SmallVectorImpl<Instruction*> &AddrModeInsts; 2585 const TargetMachine &TM; 2586 const TargetLowering &TLI; 2587 const DataLayout &DL; 2588 2589 /// AccessTy/MemoryInst - This is the type for the access (e.g. double) and 2590 /// the memory instruction that we're computing this address for. 2591 Type *AccessTy; 2592 unsigned AddrSpace; 2593 Instruction *MemoryInst; 2594 2595 /// This is the addressing mode that we're building up. This is 2596 /// part of the return value of this addressing mode matching stuff. 2597 ExtAddrMode &AddrMode; 2598 2599 /// The instructions inserted by other CodeGenPrepare optimizations. 2600 const SetOfInstrs &InsertedInsts; 2601 /// A map from the instructions to their type before promotion. 2602 InstrToOrigTy &PromotedInsts; 2603 /// The ongoing transaction where every action should be registered. 2604 TypePromotionTransaction &TPT; 2605 2606 /// This is set to true when we should not do profitability checks. 2607 /// When true, IsProfitableToFoldIntoAddressingMode always returns true. 2608 bool IgnoreProfitability; 2609 2610 AddressingModeMatcher(SmallVectorImpl<Instruction *> &AMI, 2611 const TargetMachine &TM, Type *AT, unsigned AS, 2612 Instruction *MI, ExtAddrMode &AM, 2613 const SetOfInstrs &InsertedInsts, 2614 InstrToOrigTy &PromotedInsts, 2615 TypePromotionTransaction &TPT) 2616 : AddrModeInsts(AMI), TM(TM), 2617 TLI(*TM.getSubtargetImpl(*MI->getParent()->getParent()) 2618 ->getTargetLowering()), 2619 DL(MI->getModule()->getDataLayout()), AccessTy(AT), AddrSpace(AS), 2620 MemoryInst(MI), AddrMode(AM), InsertedInsts(InsertedInsts), 2621 PromotedInsts(PromotedInsts), TPT(TPT) { 2622 IgnoreProfitability = false; 2623 } 2624 public: 2625 2626 /// Find the maximal addressing mode that a load/store of V can fold, 2627 /// give an access type of AccessTy. This returns a list of involved 2628 /// instructions in AddrModeInsts. 2629 /// \p InsertedInsts The instructions inserted by other CodeGenPrepare 2630 /// optimizations. 2631 /// \p PromotedInsts maps the instructions to their type before promotion. 2632 /// \p The ongoing transaction where every action should be registered. 2633 static ExtAddrMode Match(Value *V, Type *AccessTy, unsigned AS, 2634 Instruction *MemoryInst, 2635 SmallVectorImpl<Instruction*> &AddrModeInsts, 2636 const TargetMachine &TM, 2637 const SetOfInstrs &InsertedInsts, 2638 InstrToOrigTy &PromotedInsts, 2639 TypePromotionTransaction &TPT) { 2640 ExtAddrMode Result; 2641 2642 bool Success = AddressingModeMatcher(AddrModeInsts, TM, AccessTy, AS, 2643 MemoryInst, Result, InsertedInsts, 2644 PromotedInsts, TPT).matchAddr(V, 0); 2645 (void)Success; assert(Success && "Couldn't select *anything*?"); 2646 return Result; 2647 } 2648 private: 2649 bool matchScaledValue(Value *ScaleReg, int64_t Scale, unsigned Depth); 2650 bool matchAddr(Value *V, unsigned Depth); 2651 bool matchOperationAddr(User *Operation, unsigned Opcode, unsigned Depth, 2652 bool *MovedAway = nullptr); 2653 bool isProfitableToFoldIntoAddressingMode(Instruction *I, 2654 ExtAddrMode &AMBefore, 2655 ExtAddrMode &AMAfter); 2656 bool valueAlreadyLiveAtInst(Value *Val, Value *KnownLive1, Value *KnownLive2); 2657 bool isPromotionProfitable(unsigned NewCost, unsigned OldCost, 2658 Value *PromotedOperand) const; 2659 }; 2660 2661 /// Try adding ScaleReg*Scale to the current addressing mode. 2662 /// Return true and update AddrMode if this addr mode is legal for the target, 2663 /// false if not. 2664 bool AddressingModeMatcher::matchScaledValue(Value *ScaleReg, int64_t Scale, 2665 unsigned Depth) { 2666 // If Scale is 1, then this is the same as adding ScaleReg to the addressing 2667 // mode. Just process that directly. 2668 if (Scale == 1) 2669 return matchAddr(ScaleReg, Depth); 2670 2671 // If the scale is 0, it takes nothing to add this. 2672 if (Scale == 0) 2673 return true; 2674 2675 // If we already have a scale of this value, we can add to it, otherwise, we 2676 // need an available scale field. 2677 if (AddrMode.Scale != 0 && AddrMode.ScaledReg != ScaleReg) 2678 return false; 2679 2680 ExtAddrMode TestAddrMode = AddrMode; 2681 2682 // Add scale to turn X*4+X*3 -> X*7. This could also do things like 2683 // [A+B + A*7] -> [B+A*8]. 2684 TestAddrMode.Scale += Scale; 2685 TestAddrMode.ScaledReg = ScaleReg; 2686 2687 // If the new address isn't legal, bail out. 2688 if (!TLI.isLegalAddressingMode(DL, TestAddrMode, AccessTy, AddrSpace)) 2689 return false; 2690 2691 // It was legal, so commit it. 2692 AddrMode = TestAddrMode; 2693 2694 // Okay, we decided that we can add ScaleReg+Scale to AddrMode. Check now 2695 // to see if ScaleReg is actually X+C. If so, we can turn this into adding 2696 // X*Scale + C*Scale to addr mode. 2697 ConstantInt *CI = nullptr; Value *AddLHS = nullptr; 2698 if (isa<Instruction>(ScaleReg) && // not a constant expr. 2699 match(ScaleReg, m_Add(m_Value(AddLHS), m_ConstantInt(CI)))) { 2700 TestAddrMode.ScaledReg = AddLHS; 2701 TestAddrMode.BaseOffs += CI->getSExtValue()*TestAddrMode.Scale; 2702 2703 // If this addressing mode is legal, commit it and remember that we folded 2704 // this instruction. 2705 if (TLI.isLegalAddressingMode(DL, TestAddrMode, AccessTy, AddrSpace)) { 2706 AddrModeInsts.push_back(cast<Instruction>(ScaleReg)); 2707 AddrMode = TestAddrMode; 2708 return true; 2709 } 2710 } 2711 2712 // Otherwise, not (x+c)*scale, just return what we have. 2713 return true; 2714 } 2715 2716 /// This is a little filter, which returns true if an addressing computation 2717 /// involving I might be folded into a load/store accessing it. 2718 /// This doesn't need to be perfect, but needs to accept at least 2719 /// the set of instructions that MatchOperationAddr can. 2720 static bool MightBeFoldableInst(Instruction *I) { 2721 switch (I->getOpcode()) { 2722 case Instruction::BitCast: 2723 case Instruction::AddrSpaceCast: 2724 // Don't touch identity bitcasts. 2725 if (I->getType() == I->getOperand(0)->getType()) 2726 return false; 2727 return I->getType()->isPointerTy() || I->getType()->isIntegerTy(); 2728 case Instruction::PtrToInt: 2729 // PtrToInt is always a noop, as we know that the int type is pointer sized. 2730 return true; 2731 case Instruction::IntToPtr: 2732 // We know the input is intptr_t, so this is foldable. 2733 return true; 2734 case Instruction::Add: 2735 return true; 2736 case Instruction::Mul: 2737 case Instruction::Shl: 2738 // Can only handle X*C and X << C. 2739 return isa<ConstantInt>(I->getOperand(1)); 2740 case Instruction::GetElementPtr: 2741 return true; 2742 default: 2743 return false; 2744 } 2745 } 2746 2747 /// \brief Check whether or not \p Val is a legal instruction for \p TLI. 2748 /// \note \p Val is assumed to be the product of some type promotion. 2749 /// Therefore if \p Val has an undefined state in \p TLI, this is assumed 2750 /// to be legal, as the non-promoted value would have had the same state. 2751 static bool isPromotedInstructionLegal(const TargetLowering &TLI, 2752 const DataLayout &DL, Value *Val) { 2753 Instruction *PromotedInst = dyn_cast<Instruction>(Val); 2754 if (!PromotedInst) 2755 return false; 2756 int ISDOpcode = TLI.InstructionOpcodeToISD(PromotedInst->getOpcode()); 2757 // If the ISDOpcode is undefined, it was undefined before the promotion. 2758 if (!ISDOpcode) 2759 return true; 2760 // Otherwise, check if the promoted instruction is legal or not. 2761 return TLI.isOperationLegalOrCustom( 2762 ISDOpcode, TLI.getValueType(DL, PromotedInst->getType())); 2763 } 2764 2765 /// \brief Hepler class to perform type promotion. 2766 class TypePromotionHelper { 2767 /// \brief Utility function to check whether or not a sign or zero extension 2768 /// of \p Inst with \p ConsideredExtType can be moved through \p Inst by 2769 /// either using the operands of \p Inst or promoting \p Inst. 2770 /// The type of the extension is defined by \p IsSExt. 2771 /// In other words, check if: 2772 /// ext (Ty Inst opnd1 opnd2 ... opndN) to ConsideredExtType. 2773 /// #1 Promotion applies: 2774 /// ConsideredExtType Inst (ext opnd1 to ConsideredExtType, ...). 2775 /// #2 Operand reuses: 2776 /// ext opnd1 to ConsideredExtType. 2777 /// \p PromotedInsts maps the instructions to their type before promotion. 2778 static bool canGetThrough(const Instruction *Inst, Type *ConsideredExtType, 2779 const InstrToOrigTy &PromotedInsts, bool IsSExt); 2780 2781 /// \brief Utility function to determine if \p OpIdx should be promoted when 2782 /// promoting \p Inst. 2783 static bool shouldExtOperand(const Instruction *Inst, int OpIdx) { 2784 return !(isa<SelectInst>(Inst) && OpIdx == 0); 2785 } 2786 2787 /// \brief Utility function to promote the operand of \p Ext when this 2788 /// operand is a promotable trunc or sext or zext. 2789 /// \p PromotedInsts maps the instructions to their type before promotion. 2790 /// \p CreatedInstsCost[out] contains the cost of all instructions 2791 /// created to promote the operand of Ext. 2792 /// Newly added extensions are inserted in \p Exts. 2793 /// Newly added truncates are inserted in \p Truncs. 2794 /// Should never be called directly. 2795 /// \return The promoted value which is used instead of Ext. 2796 static Value *promoteOperandForTruncAndAnyExt( 2797 Instruction *Ext, TypePromotionTransaction &TPT, 2798 InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost, 2799 SmallVectorImpl<Instruction *> *Exts, 2800 SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI); 2801 2802 /// \brief Utility function to promote the operand of \p Ext when this 2803 /// operand is promotable and is not a supported trunc or sext. 2804 /// \p PromotedInsts maps the instructions to their type before promotion. 2805 /// \p CreatedInstsCost[out] contains the cost of all the instructions 2806 /// created to promote the operand of Ext. 2807 /// Newly added extensions are inserted in \p Exts. 2808 /// Newly added truncates are inserted in \p Truncs. 2809 /// Should never be called directly. 2810 /// \return The promoted value which is used instead of Ext. 2811 static Value *promoteOperandForOther(Instruction *Ext, 2812 TypePromotionTransaction &TPT, 2813 InstrToOrigTy &PromotedInsts, 2814 unsigned &CreatedInstsCost, 2815 SmallVectorImpl<Instruction *> *Exts, 2816 SmallVectorImpl<Instruction *> *Truncs, 2817 const TargetLowering &TLI, bool IsSExt); 2818 2819 /// \see promoteOperandForOther. 2820 static Value *signExtendOperandForOther( 2821 Instruction *Ext, TypePromotionTransaction &TPT, 2822 InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost, 2823 SmallVectorImpl<Instruction *> *Exts, 2824 SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI) { 2825 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost, 2826 Exts, Truncs, TLI, true); 2827 } 2828 2829 /// \see promoteOperandForOther. 2830 static Value *zeroExtendOperandForOther( 2831 Instruction *Ext, TypePromotionTransaction &TPT, 2832 InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost, 2833 SmallVectorImpl<Instruction *> *Exts, 2834 SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI) { 2835 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost, 2836 Exts, Truncs, TLI, false); 2837 } 2838 2839 public: 2840 /// Type for the utility function that promotes the operand of Ext. 2841 typedef Value *(*Action)(Instruction *Ext, TypePromotionTransaction &TPT, 2842 InstrToOrigTy &PromotedInsts, 2843 unsigned &CreatedInstsCost, 2844 SmallVectorImpl<Instruction *> *Exts, 2845 SmallVectorImpl<Instruction *> *Truncs, 2846 const TargetLowering &TLI); 2847 /// \brief Given a sign/zero extend instruction \p Ext, return the approriate 2848 /// action to promote the operand of \p Ext instead of using Ext. 2849 /// \return NULL if no promotable action is possible with the current 2850 /// sign extension. 2851 /// \p InsertedInsts keeps track of all the instructions inserted by the 2852 /// other CodeGenPrepare optimizations. This information is important 2853 /// because we do not want to promote these instructions as CodeGenPrepare 2854 /// will reinsert them later. Thus creating an infinite loop: create/remove. 2855 /// \p PromotedInsts maps the instructions to their type before promotion. 2856 static Action getAction(Instruction *Ext, const SetOfInstrs &InsertedInsts, 2857 const TargetLowering &TLI, 2858 const InstrToOrigTy &PromotedInsts); 2859 }; 2860 2861 bool TypePromotionHelper::canGetThrough(const Instruction *Inst, 2862 Type *ConsideredExtType, 2863 const InstrToOrigTy &PromotedInsts, 2864 bool IsSExt) { 2865 // The promotion helper does not know how to deal with vector types yet. 2866 // To be able to fix that, we would need to fix the places where we 2867 // statically extend, e.g., constants and such. 2868 if (Inst->getType()->isVectorTy()) 2869 return false; 2870 2871 // We can always get through zext. 2872 if (isa<ZExtInst>(Inst)) 2873 return true; 2874 2875 // sext(sext) is ok too. 2876 if (IsSExt && isa<SExtInst>(Inst)) 2877 return true; 2878 2879 // We can get through binary operator, if it is legal. In other words, the 2880 // binary operator must have a nuw or nsw flag. 2881 const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst); 2882 if (BinOp && isa<OverflowingBinaryOperator>(BinOp) && 2883 ((!IsSExt && BinOp->hasNoUnsignedWrap()) || 2884 (IsSExt && BinOp->hasNoSignedWrap()))) 2885 return true; 2886 2887 // Check if we can do the following simplification. 2888 // ext(trunc(opnd)) --> ext(opnd) 2889 if (!isa<TruncInst>(Inst)) 2890 return false; 2891 2892 Value *OpndVal = Inst->getOperand(0); 2893 // Check if we can use this operand in the extension. 2894 // If the type is larger than the result type of the extension, we cannot. 2895 if (!OpndVal->getType()->isIntegerTy() || 2896 OpndVal->getType()->getIntegerBitWidth() > 2897 ConsideredExtType->getIntegerBitWidth()) 2898 return false; 2899 2900 // If the operand of the truncate is not an instruction, we will not have 2901 // any information on the dropped bits. 2902 // (Actually we could for constant but it is not worth the extra logic). 2903 Instruction *Opnd = dyn_cast<Instruction>(OpndVal); 2904 if (!Opnd) 2905 return false; 2906 2907 // Check if the source of the type is narrow enough. 2908 // I.e., check that trunc just drops extended bits of the same kind of 2909 // the extension. 2910 // #1 get the type of the operand and check the kind of the extended bits. 2911 const Type *OpndType; 2912 InstrToOrigTy::const_iterator It = PromotedInsts.find(Opnd); 2913 if (It != PromotedInsts.end() && It->second.getInt() == IsSExt) 2914 OpndType = It->second.getPointer(); 2915 else if ((IsSExt && isa<SExtInst>(Opnd)) || (!IsSExt && isa<ZExtInst>(Opnd))) 2916 OpndType = Opnd->getOperand(0)->getType(); 2917 else 2918 return false; 2919 2920 // #2 check that the truncate just drops extended bits. 2921 return Inst->getType()->getIntegerBitWidth() >= 2922 OpndType->getIntegerBitWidth(); 2923 } 2924 2925 TypePromotionHelper::Action TypePromotionHelper::getAction( 2926 Instruction *Ext, const SetOfInstrs &InsertedInsts, 2927 const TargetLowering &TLI, const InstrToOrigTy &PromotedInsts) { 2928 assert((isa<SExtInst>(Ext) || isa<ZExtInst>(Ext)) && 2929 "Unexpected instruction type"); 2930 Instruction *ExtOpnd = dyn_cast<Instruction>(Ext->getOperand(0)); 2931 Type *ExtTy = Ext->getType(); 2932 bool IsSExt = isa<SExtInst>(Ext); 2933 // If the operand of the extension is not an instruction, we cannot 2934 // get through. 2935 // If it, check we can get through. 2936 if (!ExtOpnd || !canGetThrough(ExtOpnd, ExtTy, PromotedInsts, IsSExt)) 2937 return nullptr; 2938 2939 // Do not promote if the operand has been added by codegenprepare. 2940 // Otherwise, it means we are undoing an optimization that is likely to be 2941 // redone, thus causing potential infinite loop. 2942 if (isa<TruncInst>(ExtOpnd) && InsertedInsts.count(ExtOpnd)) 2943 return nullptr; 2944 2945 // SExt or Trunc instructions. 2946 // Return the related handler. 2947 if (isa<SExtInst>(ExtOpnd) || isa<TruncInst>(ExtOpnd) || 2948 isa<ZExtInst>(ExtOpnd)) 2949 return promoteOperandForTruncAndAnyExt; 2950 2951 // Regular instruction. 2952 // Abort early if we will have to insert non-free instructions. 2953 if (!ExtOpnd->hasOneUse() && !TLI.isTruncateFree(ExtTy, ExtOpnd->getType())) 2954 return nullptr; 2955 return IsSExt ? signExtendOperandForOther : zeroExtendOperandForOther; 2956 } 2957 2958 Value *TypePromotionHelper::promoteOperandForTruncAndAnyExt( 2959 llvm::Instruction *SExt, TypePromotionTransaction &TPT, 2960 InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost, 2961 SmallVectorImpl<Instruction *> *Exts, 2962 SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI) { 2963 // By construction, the operand of SExt is an instruction. Otherwise we cannot 2964 // get through it and this method should not be called. 2965 Instruction *SExtOpnd = cast<Instruction>(SExt->getOperand(0)); 2966 Value *ExtVal = SExt; 2967 bool HasMergedNonFreeExt = false; 2968 if (isa<ZExtInst>(SExtOpnd)) { 2969 // Replace s|zext(zext(opnd)) 2970 // => zext(opnd). 2971 HasMergedNonFreeExt = !TLI.isExtFree(SExtOpnd); 2972 Value *ZExt = 2973 TPT.createZExt(SExt, SExtOpnd->getOperand(0), SExt->getType()); 2974 TPT.replaceAllUsesWith(SExt, ZExt); 2975 TPT.eraseInstruction(SExt); 2976 ExtVal = ZExt; 2977 } else { 2978 // Replace z|sext(trunc(opnd)) or sext(sext(opnd)) 2979 // => z|sext(opnd). 2980 TPT.setOperand(SExt, 0, SExtOpnd->getOperand(0)); 2981 } 2982 CreatedInstsCost = 0; 2983 2984 // Remove dead code. 2985 if (SExtOpnd->use_empty()) 2986 TPT.eraseInstruction(SExtOpnd); 2987 2988 // Check if the extension is still needed. 2989 Instruction *ExtInst = dyn_cast<Instruction>(ExtVal); 2990 if (!ExtInst || ExtInst->getType() != ExtInst->getOperand(0)->getType()) { 2991 if (ExtInst) { 2992 if (Exts) 2993 Exts->push_back(ExtInst); 2994 CreatedInstsCost = !TLI.isExtFree(ExtInst) && !HasMergedNonFreeExt; 2995 } 2996 return ExtVal; 2997 } 2998 2999 // At this point we have: ext ty opnd to ty. 3000 // Reassign the uses of ExtInst to the opnd and remove ExtInst. 3001 Value *NextVal = ExtInst->getOperand(0); 3002 TPT.eraseInstruction(ExtInst, NextVal); 3003 return NextVal; 3004 } 3005 3006 Value *TypePromotionHelper::promoteOperandForOther( 3007 Instruction *Ext, TypePromotionTransaction &TPT, 3008 InstrToOrigTy &PromotedInsts, unsigned &CreatedInstsCost, 3009 SmallVectorImpl<Instruction *> *Exts, 3010 SmallVectorImpl<Instruction *> *Truncs, const TargetLowering &TLI, 3011 bool IsSExt) { 3012 // By construction, the operand of Ext is an instruction. Otherwise we cannot 3013 // get through it and this method should not be called. 3014 Instruction *ExtOpnd = cast<Instruction>(Ext->getOperand(0)); 3015 CreatedInstsCost = 0; 3016 if (!ExtOpnd->hasOneUse()) { 3017 // ExtOpnd will be promoted. 3018 // All its uses, but Ext, will need to use a truncated value of the 3019 // promoted version. 3020 // Create the truncate now. 3021 Value *Trunc = TPT.createTrunc(Ext, ExtOpnd->getType()); 3022 if (Instruction *ITrunc = dyn_cast<Instruction>(Trunc)) { 3023 ITrunc->removeFromParent(); 3024 // Insert it just after the definition. 3025 ITrunc->insertAfter(ExtOpnd); 3026 if (Truncs) 3027 Truncs->push_back(ITrunc); 3028 } 3029 3030 TPT.replaceAllUsesWith(ExtOpnd, Trunc); 3031 // Restore the operand of Ext (which has been replaced by the previous call 3032 // to replaceAllUsesWith) to avoid creating a cycle trunc <-> sext. 3033 TPT.setOperand(Ext, 0, ExtOpnd); 3034 } 3035 3036 // Get through the Instruction: 3037 // 1. Update its type. 3038 // 2. Replace the uses of Ext by Inst. 3039 // 3. Extend each operand that needs to be extended. 3040 3041 // Remember the original type of the instruction before promotion. 3042 // This is useful to know that the high bits are sign extended bits. 3043 PromotedInsts.insert(std::pair<Instruction *, TypeIsSExt>( 3044 ExtOpnd, TypeIsSExt(ExtOpnd->getType(), IsSExt))); 3045 // Step #1. 3046 TPT.mutateType(ExtOpnd, Ext->getType()); 3047 // Step #2. 3048 TPT.replaceAllUsesWith(Ext, ExtOpnd); 3049 // Step #3. 3050 Instruction *ExtForOpnd = Ext; 3051 3052 DEBUG(dbgs() << "Propagate Ext to operands\n"); 3053 for (int OpIdx = 0, EndOpIdx = ExtOpnd->getNumOperands(); OpIdx != EndOpIdx; 3054 ++OpIdx) { 3055 DEBUG(dbgs() << "Operand:\n" << *(ExtOpnd->getOperand(OpIdx)) << '\n'); 3056 if (ExtOpnd->getOperand(OpIdx)->getType() == Ext->getType() || 3057 !shouldExtOperand(ExtOpnd, OpIdx)) { 3058 DEBUG(dbgs() << "No need to propagate\n"); 3059 continue; 3060 } 3061 // Check if we can statically extend the operand. 3062 Value *Opnd = ExtOpnd->getOperand(OpIdx); 3063 if (const ConstantInt *Cst = dyn_cast<ConstantInt>(Opnd)) { 3064 DEBUG(dbgs() << "Statically extend\n"); 3065 unsigned BitWidth = Ext->getType()->getIntegerBitWidth(); 3066 APInt CstVal = IsSExt ? Cst->getValue().sext(BitWidth) 3067 : Cst->getValue().zext(BitWidth); 3068 TPT.setOperand(ExtOpnd, OpIdx, ConstantInt::get(Ext->getType(), CstVal)); 3069 continue; 3070 } 3071 // UndefValue are typed, so we have to statically sign extend them. 3072 if (isa<UndefValue>(Opnd)) { 3073 DEBUG(dbgs() << "Statically extend\n"); 3074 TPT.setOperand(ExtOpnd, OpIdx, UndefValue::get(Ext->getType())); 3075 continue; 3076 } 3077 3078 // Otherwise we have to explicity sign extend the operand. 3079 // Check if Ext was reused to extend an operand. 3080 if (!ExtForOpnd) { 3081 // If yes, create a new one. 3082 DEBUG(dbgs() << "More operands to ext\n"); 3083 Value *ValForExtOpnd = IsSExt ? TPT.createSExt(Ext, Opnd, Ext->getType()) 3084 : TPT.createZExt(Ext, Opnd, Ext->getType()); 3085 if (!isa<Instruction>(ValForExtOpnd)) { 3086 TPT.setOperand(ExtOpnd, OpIdx, ValForExtOpnd); 3087 continue; 3088 } 3089 ExtForOpnd = cast<Instruction>(ValForExtOpnd); 3090 } 3091 if (Exts) 3092 Exts->push_back(ExtForOpnd); 3093 TPT.setOperand(ExtForOpnd, 0, Opnd); 3094 3095 // Move the sign extension before the insertion point. 3096 TPT.moveBefore(ExtForOpnd, ExtOpnd); 3097 TPT.setOperand(ExtOpnd, OpIdx, ExtForOpnd); 3098 CreatedInstsCost += !TLI.isExtFree(ExtForOpnd); 3099 // If more sext are required, new instructions will have to be created. 3100 ExtForOpnd = nullptr; 3101 } 3102 if (ExtForOpnd == Ext) { 3103 DEBUG(dbgs() << "Extension is useless now\n"); 3104 TPT.eraseInstruction(Ext); 3105 } 3106 return ExtOpnd; 3107 } 3108 3109 /// Check whether or not promoting an instruction to a wider type is profitable. 3110 /// \p NewCost gives the cost of extension instructions created by the 3111 /// promotion. 3112 /// \p OldCost gives the cost of extension instructions before the promotion 3113 /// plus the number of instructions that have been 3114 /// matched in the addressing mode the promotion. 3115 /// \p PromotedOperand is the value that has been promoted. 3116 /// \return True if the promotion is profitable, false otherwise. 3117 bool AddressingModeMatcher::isPromotionProfitable( 3118 unsigned NewCost, unsigned OldCost, Value *PromotedOperand) const { 3119 DEBUG(dbgs() << "OldCost: " << OldCost << "\tNewCost: " << NewCost << '\n'); 3120 // The cost of the new extensions is greater than the cost of the 3121 // old extension plus what we folded. 3122 // This is not profitable. 3123 if (NewCost > OldCost) 3124 return false; 3125 if (NewCost < OldCost) 3126 return true; 3127 // The promotion is neutral but it may help folding the sign extension in 3128 // loads for instance. 3129 // Check that we did not create an illegal instruction. 3130 return isPromotedInstructionLegal(TLI, DL, PromotedOperand); 3131 } 3132 3133 /// Given an instruction or constant expr, see if we can fold the operation 3134 /// into the addressing mode. If so, update the addressing mode and return 3135 /// true, otherwise return false without modifying AddrMode. 3136 /// If \p MovedAway is not NULL, it contains the information of whether or 3137 /// not AddrInst has to be folded into the addressing mode on success. 3138 /// If \p MovedAway == true, \p AddrInst will not be part of the addressing 3139 /// because it has been moved away. 3140 /// Thus AddrInst must not be added in the matched instructions. 3141 /// This state can happen when AddrInst is a sext, since it may be moved away. 3142 /// Therefore, AddrInst may not be valid when MovedAway is true and it must 3143 /// not be referenced anymore. 3144 bool AddressingModeMatcher::matchOperationAddr(User *AddrInst, unsigned Opcode, 3145 unsigned Depth, 3146 bool *MovedAway) { 3147 // Avoid exponential behavior on extremely deep expression trees. 3148 if (Depth >= 5) return false; 3149 3150 // By default, all matched instructions stay in place. 3151 if (MovedAway) 3152 *MovedAway = false; 3153 3154 switch (Opcode) { 3155 case Instruction::PtrToInt: 3156 // PtrToInt is always a noop, as we know that the int type is pointer sized. 3157 return matchAddr(AddrInst->getOperand(0), Depth); 3158 case Instruction::IntToPtr: { 3159 auto AS = AddrInst->getType()->getPointerAddressSpace(); 3160 auto PtrTy = MVT::getIntegerVT(DL.getPointerSizeInBits(AS)); 3161 // This inttoptr is a no-op if the integer type is pointer sized. 3162 if (TLI.getValueType(DL, AddrInst->getOperand(0)->getType()) == PtrTy) 3163 return matchAddr(AddrInst->getOperand(0), Depth); 3164 return false; 3165 } 3166 case Instruction::BitCast: 3167 // BitCast is always a noop, and we can handle it as long as it is 3168 // int->int or pointer->pointer (we don't want int<->fp or something). 3169 if ((AddrInst->getOperand(0)->getType()->isPointerTy() || 3170 AddrInst->getOperand(0)->getType()->isIntegerTy()) && 3171 // Don't touch identity bitcasts. These were probably put here by LSR, 3172 // and we don't want to mess around with them. Assume it knows what it 3173 // is doing. 3174 AddrInst->getOperand(0)->getType() != AddrInst->getType()) 3175 return matchAddr(AddrInst->getOperand(0), Depth); 3176 return false; 3177 case Instruction::AddrSpaceCast: { 3178 unsigned SrcAS 3179 = AddrInst->getOperand(0)->getType()->getPointerAddressSpace(); 3180 unsigned DestAS = AddrInst->getType()->getPointerAddressSpace(); 3181 if (TLI.isNoopAddrSpaceCast(SrcAS, DestAS)) 3182 return matchAddr(AddrInst->getOperand(0), Depth); 3183 return false; 3184 } 3185 case Instruction::Add: { 3186 // Check to see if we can merge in the RHS then the LHS. If so, we win. 3187 ExtAddrMode BackupAddrMode = AddrMode; 3188 unsigned OldSize = AddrModeInsts.size(); 3189 // Start a transaction at this point. 3190 // The LHS may match but not the RHS. 3191 // Therefore, we need a higher level restoration point to undo partially 3192 // matched operation. 3193 TypePromotionTransaction::ConstRestorationPt LastKnownGood = 3194 TPT.getRestorationPoint(); 3195 3196 if (matchAddr(AddrInst->getOperand(1), Depth+1) && 3197 matchAddr(AddrInst->getOperand(0), Depth+1)) 3198 return true; 3199 3200 // Restore the old addr mode info. 3201 AddrMode = BackupAddrMode; 3202 AddrModeInsts.resize(OldSize); 3203 TPT.rollback(LastKnownGood); 3204 3205 // Otherwise this was over-aggressive. Try merging in the LHS then the RHS. 3206 if (matchAddr(AddrInst->getOperand(0), Depth+1) && 3207 matchAddr(AddrInst->getOperand(1), Depth+1)) 3208 return true; 3209 3210 // Otherwise we definitely can't merge the ADD in. 3211 AddrMode = BackupAddrMode; 3212 AddrModeInsts.resize(OldSize); 3213 TPT.rollback(LastKnownGood); 3214 break; 3215 } 3216 //case Instruction::Or: 3217 // TODO: We can handle "Or Val, Imm" iff this OR is equivalent to an ADD. 3218 //break; 3219 case Instruction::Mul: 3220 case Instruction::Shl: { 3221 // Can only handle X*C and X << C. 3222 ConstantInt *RHS = dyn_cast<ConstantInt>(AddrInst->getOperand(1)); 3223 if (!RHS) 3224 return false; 3225 int64_t Scale = RHS->getSExtValue(); 3226 if (Opcode == Instruction::Shl) 3227 Scale = 1LL << Scale; 3228 3229 return matchScaledValue(AddrInst->getOperand(0), Scale, Depth); 3230 } 3231 case Instruction::GetElementPtr: { 3232 // Scan the GEP. We check it if it contains constant offsets and at most 3233 // one variable offset. 3234 int VariableOperand = -1; 3235 unsigned VariableScale = 0; 3236 3237 int64_t ConstantOffset = 0; 3238 gep_type_iterator GTI = gep_type_begin(AddrInst); 3239 for (unsigned i = 1, e = AddrInst->getNumOperands(); i != e; ++i, ++GTI) { 3240 if (StructType *STy = dyn_cast<StructType>(*GTI)) { 3241 const StructLayout *SL = DL.getStructLayout(STy); 3242 unsigned Idx = 3243 cast<ConstantInt>(AddrInst->getOperand(i))->getZExtValue(); 3244 ConstantOffset += SL->getElementOffset(Idx); 3245 } else { 3246 uint64_t TypeSize = DL.getTypeAllocSize(GTI.getIndexedType()); 3247 if (ConstantInt *CI = dyn_cast<ConstantInt>(AddrInst->getOperand(i))) { 3248 ConstantOffset += CI->getSExtValue()*TypeSize; 3249 } else if (TypeSize) { // Scales of zero don't do anything. 3250 // We only allow one variable index at the moment. 3251 if (VariableOperand != -1) 3252 return false; 3253 3254 // Remember the variable index. 3255 VariableOperand = i; 3256 VariableScale = TypeSize; 3257 } 3258 } 3259 } 3260 3261 // A common case is for the GEP to only do a constant offset. In this case, 3262 // just add it to the disp field and check validity. 3263 if (VariableOperand == -1) { 3264 AddrMode.BaseOffs += ConstantOffset; 3265 if (ConstantOffset == 0 || 3266 TLI.isLegalAddressingMode(DL, AddrMode, AccessTy, AddrSpace)) { 3267 // Check to see if we can fold the base pointer in too. 3268 if (matchAddr(AddrInst->getOperand(0), Depth+1)) 3269 return true; 3270 } 3271 AddrMode.BaseOffs -= ConstantOffset; 3272 return false; 3273 } 3274 3275 // Save the valid addressing mode in case we can't match. 3276 ExtAddrMode BackupAddrMode = AddrMode; 3277 unsigned OldSize = AddrModeInsts.size(); 3278 3279 // See if the scale and offset amount is valid for this target. 3280 AddrMode.BaseOffs += ConstantOffset; 3281 3282 // Match the base operand of the GEP. 3283 if (!matchAddr(AddrInst->getOperand(0), Depth+1)) { 3284 // If it couldn't be matched, just stuff the value in a register. 3285 if (AddrMode.HasBaseReg) { 3286 AddrMode = BackupAddrMode; 3287 AddrModeInsts.resize(OldSize); 3288 return false; 3289 } 3290 AddrMode.HasBaseReg = true; 3291 AddrMode.BaseReg = AddrInst->getOperand(0); 3292 } 3293 3294 // Match the remaining variable portion of the GEP. 3295 if (!matchScaledValue(AddrInst->getOperand(VariableOperand), VariableScale, 3296 Depth)) { 3297 // If it couldn't be matched, try stuffing the base into a register 3298 // instead of matching it, and retrying the match of the scale. 3299 AddrMode = BackupAddrMode; 3300 AddrModeInsts.resize(OldSize); 3301 if (AddrMode.HasBaseReg) 3302 return false; 3303 AddrMode.HasBaseReg = true; 3304 AddrMode.BaseReg = AddrInst->getOperand(0); 3305 AddrMode.BaseOffs += ConstantOffset; 3306 if (!matchScaledValue(AddrInst->getOperand(VariableOperand), 3307 VariableScale, Depth)) { 3308 // If even that didn't work, bail. 3309 AddrMode = BackupAddrMode; 3310 AddrModeInsts.resize(OldSize); 3311 return false; 3312 } 3313 } 3314 3315 return true; 3316 } 3317 case Instruction::SExt: 3318 case Instruction::ZExt: { 3319 Instruction *Ext = dyn_cast<Instruction>(AddrInst); 3320 if (!Ext) 3321 return false; 3322 3323 // Try to move this ext out of the way of the addressing mode. 3324 // Ask for a method for doing so. 3325 TypePromotionHelper::Action TPH = 3326 TypePromotionHelper::getAction(Ext, InsertedInsts, TLI, PromotedInsts); 3327 if (!TPH) 3328 return false; 3329 3330 TypePromotionTransaction::ConstRestorationPt LastKnownGood = 3331 TPT.getRestorationPoint(); 3332 unsigned CreatedInstsCost = 0; 3333 unsigned ExtCost = !TLI.isExtFree(Ext); 3334 Value *PromotedOperand = 3335 TPH(Ext, TPT, PromotedInsts, CreatedInstsCost, nullptr, nullptr, TLI); 3336 // SExt has been moved away. 3337 // Thus either it will be rematched later in the recursive calls or it is 3338 // gone. Anyway, we must not fold it into the addressing mode at this point. 3339 // E.g., 3340 // op = add opnd, 1 3341 // idx = ext op 3342 // addr = gep base, idx 3343 // is now: 3344 // promotedOpnd = ext opnd <- no match here 3345 // op = promoted_add promotedOpnd, 1 <- match (later in recursive calls) 3346 // addr = gep base, op <- match 3347 if (MovedAway) 3348 *MovedAway = true; 3349 3350 assert(PromotedOperand && 3351 "TypePromotionHelper should have filtered out those cases"); 3352 3353 ExtAddrMode BackupAddrMode = AddrMode; 3354 unsigned OldSize = AddrModeInsts.size(); 3355 3356 if (!matchAddr(PromotedOperand, Depth) || 3357 // The total of the new cost is equal to the cost of the created 3358 // instructions. 3359 // The total of the old cost is equal to the cost of the extension plus 3360 // what we have saved in the addressing mode. 3361 !isPromotionProfitable(CreatedInstsCost, 3362 ExtCost + (AddrModeInsts.size() - OldSize), 3363 PromotedOperand)) { 3364 AddrMode = BackupAddrMode; 3365 AddrModeInsts.resize(OldSize); 3366 DEBUG(dbgs() << "Sign extension does not pay off: rollback\n"); 3367 TPT.rollback(LastKnownGood); 3368 return false; 3369 } 3370 return true; 3371 } 3372 } 3373 return false; 3374 } 3375 3376 /// If we can, try to add the value of 'Addr' into the current addressing mode. 3377 /// If Addr can't be added to AddrMode this returns false and leaves AddrMode 3378 /// unmodified. This assumes that Addr is either a pointer type or intptr_t 3379 /// for the target. 3380 /// 3381 bool AddressingModeMatcher::matchAddr(Value *Addr, unsigned Depth) { 3382 // Start a transaction at this point that we will rollback if the matching 3383 // fails. 3384 TypePromotionTransaction::ConstRestorationPt LastKnownGood = 3385 TPT.getRestorationPoint(); 3386 if (ConstantInt *CI = dyn_cast<ConstantInt>(Addr)) { 3387 // Fold in immediates if legal for the target. 3388 AddrMode.BaseOffs += CI->getSExtValue(); 3389 if (TLI.isLegalAddressingMode(DL, AddrMode, AccessTy, AddrSpace)) 3390 return true; 3391 AddrMode.BaseOffs -= CI->getSExtValue(); 3392 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(Addr)) { 3393 // If this is a global variable, try to fold it into the addressing mode. 3394 if (!AddrMode.BaseGV) { 3395 AddrMode.BaseGV = GV; 3396 if (TLI.isLegalAddressingMode(DL, AddrMode, AccessTy, AddrSpace)) 3397 return true; 3398 AddrMode.BaseGV = nullptr; 3399 } 3400 } else if (Instruction *I = dyn_cast<Instruction>(Addr)) { 3401 ExtAddrMode BackupAddrMode = AddrMode; 3402 unsigned OldSize = AddrModeInsts.size(); 3403 3404 // Check to see if it is possible to fold this operation. 3405 bool MovedAway = false; 3406 if (matchOperationAddr(I, I->getOpcode(), Depth, &MovedAway)) { 3407 // This instruction may have been moved away. If so, there is nothing 3408 // to check here. 3409 if (MovedAway) 3410 return true; 3411 // Okay, it's possible to fold this. Check to see if it is actually 3412 // *profitable* to do so. We use a simple cost model to avoid increasing 3413 // register pressure too much. 3414 if (I->hasOneUse() || 3415 isProfitableToFoldIntoAddressingMode(I, BackupAddrMode, AddrMode)) { 3416 AddrModeInsts.push_back(I); 3417 return true; 3418 } 3419 3420 // It isn't profitable to do this, roll back. 3421 //cerr << "NOT FOLDING: " << *I; 3422 AddrMode = BackupAddrMode; 3423 AddrModeInsts.resize(OldSize); 3424 TPT.rollback(LastKnownGood); 3425 } 3426 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Addr)) { 3427 if (matchOperationAddr(CE, CE->getOpcode(), Depth)) 3428 return true; 3429 TPT.rollback(LastKnownGood); 3430 } else if (isa<ConstantPointerNull>(Addr)) { 3431 // Null pointer gets folded without affecting the addressing mode. 3432 return true; 3433 } 3434 3435 // Worse case, the target should support [reg] addressing modes. :) 3436 if (!AddrMode.HasBaseReg) { 3437 AddrMode.HasBaseReg = true; 3438 AddrMode.BaseReg = Addr; 3439 // Still check for legality in case the target supports [imm] but not [i+r]. 3440 if (TLI.isLegalAddressingMode(DL, AddrMode, AccessTy, AddrSpace)) 3441 return true; 3442 AddrMode.HasBaseReg = false; 3443 AddrMode.BaseReg = nullptr; 3444 } 3445 3446 // If the base register is already taken, see if we can do [r+r]. 3447 if (AddrMode.Scale == 0) { 3448 AddrMode.Scale = 1; 3449 AddrMode.ScaledReg = Addr; 3450 if (TLI.isLegalAddressingMode(DL, AddrMode, AccessTy, AddrSpace)) 3451 return true; 3452 AddrMode.Scale = 0; 3453 AddrMode.ScaledReg = nullptr; 3454 } 3455 // Couldn't match. 3456 TPT.rollback(LastKnownGood); 3457 return false; 3458 } 3459 3460 /// Check to see if all uses of OpVal by the specified inline asm call are due 3461 /// to memory operands. If so, return true, otherwise return false. 3462 static bool IsOperandAMemoryOperand(CallInst *CI, InlineAsm *IA, Value *OpVal, 3463 const TargetMachine &TM) { 3464 const Function *F = CI->getParent()->getParent(); 3465 const TargetLowering *TLI = TM.getSubtargetImpl(*F)->getTargetLowering(); 3466 const TargetRegisterInfo *TRI = TM.getSubtargetImpl(*F)->getRegisterInfo(); 3467 TargetLowering::AsmOperandInfoVector TargetConstraints = 3468 TLI->ParseConstraints(F->getParent()->getDataLayout(), TRI, 3469 ImmutableCallSite(CI)); 3470 for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) { 3471 TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i]; 3472 3473 // Compute the constraint code and ConstraintType to use. 3474 TLI->ComputeConstraintToUse(OpInfo, SDValue()); 3475 3476 // If this asm operand is our Value*, and if it isn't an indirect memory 3477 // operand, we can't fold it! 3478 if (OpInfo.CallOperandVal == OpVal && 3479 (OpInfo.ConstraintType != TargetLowering::C_Memory || 3480 !OpInfo.isIndirect)) 3481 return false; 3482 } 3483 3484 return true; 3485 } 3486 3487 /// Recursively walk all the uses of I until we find a memory use. 3488 /// If we find an obviously non-foldable instruction, return true. 3489 /// Add the ultimately found memory instructions to MemoryUses. 3490 static bool FindAllMemoryUses( 3491 Instruction *I, 3492 SmallVectorImpl<std::pair<Instruction *, unsigned>> &MemoryUses, 3493 SmallPtrSetImpl<Instruction *> &ConsideredInsts, const TargetMachine &TM) { 3494 // If we already considered this instruction, we're done. 3495 if (!ConsideredInsts.insert(I).second) 3496 return false; 3497 3498 // If this is an obviously unfoldable instruction, bail out. 3499 if (!MightBeFoldableInst(I)) 3500 return true; 3501 3502 const bool OptSize = I->getFunction()->optForSize(); 3503 3504 // Loop over all the uses, recursively processing them. 3505 for (Use &U : I->uses()) { 3506 Instruction *UserI = cast<Instruction>(U.getUser()); 3507 3508 if (LoadInst *LI = dyn_cast<LoadInst>(UserI)) { 3509 MemoryUses.push_back(std::make_pair(LI, U.getOperandNo())); 3510 continue; 3511 } 3512 3513 if (StoreInst *SI = dyn_cast<StoreInst>(UserI)) { 3514 unsigned opNo = U.getOperandNo(); 3515 if (opNo == 0) return true; // Storing addr, not into addr. 3516 MemoryUses.push_back(std::make_pair(SI, opNo)); 3517 continue; 3518 } 3519 3520 if (CallInst *CI = dyn_cast<CallInst>(UserI)) { 3521 // If this is a cold call, we can sink the addressing calculation into 3522 // the cold path. See optimizeCallInst 3523 if (!OptSize && CI->hasFnAttr(Attribute::Cold)) 3524 continue; 3525 3526 InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledValue()); 3527 if (!IA) return true; 3528 3529 // If this is a memory operand, we're cool, otherwise bail out. 3530 if (!IsOperandAMemoryOperand(CI, IA, I, TM)) 3531 return true; 3532 continue; 3533 } 3534 3535 if (FindAllMemoryUses(UserI, MemoryUses, ConsideredInsts, TM)) 3536 return true; 3537 } 3538 3539 return false; 3540 } 3541 3542 /// Return true if Val is already known to be live at the use site that we're 3543 /// folding it into. If so, there is no cost to include it in the addressing 3544 /// mode. KnownLive1 and KnownLive2 are two values that we know are live at the 3545 /// instruction already. 3546 bool AddressingModeMatcher::valueAlreadyLiveAtInst(Value *Val,Value *KnownLive1, 3547 Value *KnownLive2) { 3548 // If Val is either of the known-live values, we know it is live! 3549 if (Val == nullptr || Val == KnownLive1 || Val == KnownLive2) 3550 return true; 3551 3552 // All values other than instructions and arguments (e.g. constants) are live. 3553 if (!isa<Instruction>(Val) && !isa<Argument>(Val)) return true; 3554 3555 // If Val is a constant sized alloca in the entry block, it is live, this is 3556 // true because it is just a reference to the stack/frame pointer, which is 3557 // live for the whole function. 3558 if (AllocaInst *AI = dyn_cast<AllocaInst>(Val)) 3559 if (AI->isStaticAlloca()) 3560 return true; 3561 3562 // Check to see if this value is already used in the memory instruction's 3563 // block. If so, it's already live into the block at the very least, so we 3564 // can reasonably fold it. 3565 return Val->isUsedInBasicBlock(MemoryInst->getParent()); 3566 } 3567 3568 /// It is possible for the addressing mode of the machine to fold the specified 3569 /// instruction into a load or store that ultimately uses it. 3570 /// However, the specified instruction has multiple uses. 3571 /// Given this, it may actually increase register pressure to fold it 3572 /// into the load. For example, consider this code: 3573 /// 3574 /// X = ... 3575 /// Y = X+1 3576 /// use(Y) -> nonload/store 3577 /// Z = Y+1 3578 /// load Z 3579 /// 3580 /// In this case, Y has multiple uses, and can be folded into the load of Z 3581 /// (yielding load [X+2]). However, doing this will cause both "X" and "X+1" to 3582 /// be live at the use(Y) line. If we don't fold Y into load Z, we use one 3583 /// fewer register. Since Y can't be folded into "use(Y)" we don't increase the 3584 /// number of computations either. 3585 /// 3586 /// Note that this (like most of CodeGenPrepare) is just a rough heuristic. If 3587 /// X was live across 'load Z' for other reasons, we actually *would* want to 3588 /// fold the addressing mode in the Z case. This would make Y die earlier. 3589 bool AddressingModeMatcher:: 3590 isProfitableToFoldIntoAddressingMode(Instruction *I, ExtAddrMode &AMBefore, 3591 ExtAddrMode &AMAfter) { 3592 if (IgnoreProfitability) return true; 3593 3594 // AMBefore is the addressing mode before this instruction was folded into it, 3595 // and AMAfter is the addressing mode after the instruction was folded. Get 3596 // the set of registers referenced by AMAfter and subtract out those 3597 // referenced by AMBefore: this is the set of values which folding in this 3598 // address extends the lifetime of. 3599 // 3600 // Note that there are only two potential values being referenced here, 3601 // BaseReg and ScaleReg (global addresses are always available, as are any 3602 // folded immediates). 3603 Value *BaseReg = AMAfter.BaseReg, *ScaledReg = AMAfter.ScaledReg; 3604 3605 // If the BaseReg or ScaledReg was referenced by the previous addrmode, their 3606 // lifetime wasn't extended by adding this instruction. 3607 if (valueAlreadyLiveAtInst(BaseReg, AMBefore.BaseReg, AMBefore.ScaledReg)) 3608 BaseReg = nullptr; 3609 if (valueAlreadyLiveAtInst(ScaledReg, AMBefore.BaseReg, AMBefore.ScaledReg)) 3610 ScaledReg = nullptr; 3611 3612 // If folding this instruction (and it's subexprs) didn't extend any live 3613 // ranges, we're ok with it. 3614 if (!BaseReg && !ScaledReg) 3615 return true; 3616 3617 // If all uses of this instruction can have the address mode sunk into them, 3618 // we can remove the addressing mode and effectively trade one live register 3619 // for another (at worst.) In this context, folding an addressing mode into 3620 // the use is just a particularly nice way of sinking it. 3621 SmallVector<std::pair<Instruction*,unsigned>, 16> MemoryUses; 3622 SmallPtrSet<Instruction*, 16> ConsideredInsts; 3623 if (FindAllMemoryUses(I, MemoryUses, ConsideredInsts, TM)) 3624 return false; // Has a non-memory, non-foldable use! 3625 3626 // Now that we know that all uses of this instruction are part of a chain of 3627 // computation involving only operations that could theoretically be folded 3628 // into a memory use, loop over each of these memory operation uses and see 3629 // if they could *actually* fold the instruction. The assumption is that 3630 // addressing modes are cheap and that duplicating the computation involved 3631 // many times is worthwhile, even on a fastpath. For sinking candidates 3632 // (i.e. cold call sites), this serves as a way to prevent excessive code 3633 // growth since most architectures have some reasonable small and fast way to 3634 // compute an effective address. (i.e LEA on x86) 3635 SmallVector<Instruction*, 32> MatchedAddrModeInsts; 3636 for (unsigned i = 0, e = MemoryUses.size(); i != e; ++i) { 3637 Instruction *User = MemoryUses[i].first; 3638 unsigned OpNo = MemoryUses[i].second; 3639 3640 // Get the access type of this use. If the use isn't a pointer, we don't 3641 // know what it accesses. 3642 Value *Address = User->getOperand(OpNo); 3643 PointerType *AddrTy = dyn_cast<PointerType>(Address->getType()); 3644 if (!AddrTy) 3645 return false; 3646 Type *AddressAccessTy = AddrTy->getElementType(); 3647 unsigned AS = AddrTy->getAddressSpace(); 3648 3649 // Do a match against the root of this address, ignoring profitability. This 3650 // will tell us if the addressing mode for the memory operation will 3651 // *actually* cover the shared instruction. 3652 ExtAddrMode Result; 3653 TypePromotionTransaction::ConstRestorationPt LastKnownGood = 3654 TPT.getRestorationPoint(); 3655 AddressingModeMatcher Matcher(MatchedAddrModeInsts, TM, AddressAccessTy, AS, 3656 MemoryInst, Result, InsertedInsts, 3657 PromotedInsts, TPT); 3658 Matcher.IgnoreProfitability = true; 3659 bool Success = Matcher.matchAddr(Address, 0); 3660 (void)Success; assert(Success && "Couldn't select *anything*?"); 3661 3662 // The match was to check the profitability, the changes made are not 3663 // part of the original matcher. Therefore, they should be dropped 3664 // otherwise the original matcher will not present the right state. 3665 TPT.rollback(LastKnownGood); 3666 3667 // If the match didn't cover I, then it won't be shared by it. 3668 if (std::find(MatchedAddrModeInsts.begin(), MatchedAddrModeInsts.end(), 3669 I) == MatchedAddrModeInsts.end()) 3670 return false; 3671 3672 MatchedAddrModeInsts.clear(); 3673 } 3674 3675 return true; 3676 } 3677 3678 } // end anonymous namespace 3679 3680 /// Return true if the specified values are defined in a 3681 /// different basic block than BB. 3682 static bool IsNonLocalValue(Value *V, BasicBlock *BB) { 3683 if (Instruction *I = dyn_cast<Instruction>(V)) 3684 return I->getParent() != BB; 3685 return false; 3686 } 3687 3688 /// Sink addressing mode computation immediate before MemoryInst if doing so 3689 /// can be done without increasing register pressure. The need for the 3690 /// register pressure constraint means this can end up being an all or nothing 3691 /// decision for all uses of the same addressing computation. 3692 /// 3693 /// Load and Store Instructions often have addressing modes that can do 3694 /// significant amounts of computation. As such, instruction selection will try 3695 /// to get the load or store to do as much computation as possible for the 3696 /// program. The problem is that isel can only see within a single block. As 3697 /// such, we sink as much legal addressing mode work into the block as possible. 3698 /// 3699 /// This method is used to optimize both load/store and inline asms with memory 3700 /// operands. It's also used to sink addressing computations feeding into cold 3701 /// call sites into their (cold) basic block. 3702 /// 3703 /// The motivation for handling sinking into cold blocks is that doing so can 3704 /// both enable other address mode sinking (by satisfying the register pressure 3705 /// constraint above), and reduce register pressure globally (by removing the 3706 /// addressing mode computation from the fast path entirely.). 3707 bool CodeGenPrepare::optimizeMemoryInst(Instruction *MemoryInst, Value *Addr, 3708 Type *AccessTy, unsigned AddrSpace) { 3709 Value *Repl = Addr; 3710 3711 // Try to collapse single-value PHI nodes. This is necessary to undo 3712 // unprofitable PRE transformations. 3713 SmallVector<Value*, 8> worklist; 3714 SmallPtrSet<Value*, 16> Visited; 3715 worklist.push_back(Addr); 3716 3717 // Use a worklist to iteratively look through PHI nodes, and ensure that 3718 // the addressing mode obtained from the non-PHI roots of the graph 3719 // are equivalent. 3720 Value *Consensus = nullptr; 3721 unsigned NumUsesConsensus = 0; 3722 bool IsNumUsesConsensusValid = false; 3723 SmallVector<Instruction*, 16> AddrModeInsts; 3724 ExtAddrMode AddrMode; 3725 TypePromotionTransaction TPT; 3726 TypePromotionTransaction::ConstRestorationPt LastKnownGood = 3727 TPT.getRestorationPoint(); 3728 while (!worklist.empty()) { 3729 Value *V = worklist.back(); 3730 worklist.pop_back(); 3731 3732 // Break use-def graph loops. 3733 if (!Visited.insert(V).second) { 3734 Consensus = nullptr; 3735 break; 3736 } 3737 3738 // For a PHI node, push all of its incoming values. 3739 if (PHINode *P = dyn_cast<PHINode>(V)) { 3740 for (Value *IncValue : P->incoming_values()) 3741 worklist.push_back(IncValue); 3742 continue; 3743 } 3744 3745 // For non-PHIs, determine the addressing mode being computed. Note that 3746 // the result may differ depending on what other uses our candidate 3747 // addressing instructions might have. 3748 SmallVector<Instruction*, 16> NewAddrModeInsts; 3749 ExtAddrMode NewAddrMode = AddressingModeMatcher::Match( 3750 V, AccessTy, AddrSpace, MemoryInst, NewAddrModeInsts, *TM, 3751 InsertedInsts, PromotedInsts, TPT); 3752 3753 // This check is broken into two cases with very similar code to avoid using 3754 // getNumUses() as much as possible. Some values have a lot of uses, so 3755 // calling getNumUses() unconditionally caused a significant compile-time 3756 // regression. 3757 if (!Consensus) { 3758 Consensus = V; 3759 AddrMode = NewAddrMode; 3760 AddrModeInsts = NewAddrModeInsts; 3761 continue; 3762 } else if (NewAddrMode == AddrMode) { 3763 if (!IsNumUsesConsensusValid) { 3764 NumUsesConsensus = Consensus->getNumUses(); 3765 IsNumUsesConsensusValid = true; 3766 } 3767 3768 // Ensure that the obtained addressing mode is equivalent to that obtained 3769 // for all other roots of the PHI traversal. Also, when choosing one 3770 // such root as representative, select the one with the most uses in order 3771 // to keep the cost modeling heuristics in AddressingModeMatcher 3772 // applicable. 3773 unsigned NumUses = V->getNumUses(); 3774 if (NumUses > NumUsesConsensus) { 3775 Consensus = V; 3776 NumUsesConsensus = NumUses; 3777 AddrModeInsts = NewAddrModeInsts; 3778 } 3779 continue; 3780 } 3781 3782 Consensus = nullptr; 3783 break; 3784 } 3785 3786 // If the addressing mode couldn't be determined, or if multiple different 3787 // ones were determined, bail out now. 3788 if (!Consensus) { 3789 TPT.rollback(LastKnownGood); 3790 return false; 3791 } 3792 TPT.commit(); 3793 3794 // Check to see if any of the instructions supersumed by this addr mode are 3795 // non-local to I's BB. 3796 bool AnyNonLocal = false; 3797 for (unsigned i = 0, e = AddrModeInsts.size(); i != e; ++i) { 3798 if (IsNonLocalValue(AddrModeInsts[i], MemoryInst->getParent())) { 3799 AnyNonLocal = true; 3800 break; 3801 } 3802 } 3803 3804 // If all the instructions matched are already in this BB, don't do anything. 3805 if (!AnyNonLocal) { 3806 DEBUG(dbgs() << "CGP: Found local addrmode: " << AddrMode << "\n"); 3807 return false; 3808 } 3809 3810 // Insert this computation right after this user. Since our caller is 3811 // scanning from the top of the BB to the bottom, reuse of the expr are 3812 // guaranteed to happen later. 3813 IRBuilder<> Builder(MemoryInst); 3814 3815 // Now that we determined the addressing expression we want to use and know 3816 // that we have to sink it into this block. Check to see if we have already 3817 // done this for some other load/store instr in this block. If so, reuse the 3818 // computation. 3819 Value *&SunkAddr = SunkAddrs[Addr]; 3820 if (SunkAddr) { 3821 DEBUG(dbgs() << "CGP: Reusing nonlocal addrmode: " << AddrMode << " for " 3822 << *MemoryInst << "\n"); 3823 if (SunkAddr->getType() != Addr->getType()) 3824 SunkAddr = Builder.CreateBitCast(SunkAddr, Addr->getType()); 3825 } else if (AddrSinkUsingGEPs || 3826 (!AddrSinkUsingGEPs.getNumOccurrences() && TM && 3827 TM->getSubtargetImpl(*MemoryInst->getParent()->getParent()) 3828 ->useAA())) { 3829 // By default, we use the GEP-based method when AA is used later. This 3830 // prevents new inttoptr/ptrtoint pairs from degrading AA capabilities. 3831 DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for " 3832 << *MemoryInst << "\n"); 3833 Type *IntPtrTy = DL->getIntPtrType(Addr->getType()); 3834 Value *ResultPtr = nullptr, *ResultIndex = nullptr; 3835 3836 // First, find the pointer. 3837 if (AddrMode.BaseReg && AddrMode.BaseReg->getType()->isPointerTy()) { 3838 ResultPtr = AddrMode.BaseReg; 3839 AddrMode.BaseReg = nullptr; 3840 } 3841 3842 if (AddrMode.Scale && AddrMode.ScaledReg->getType()->isPointerTy()) { 3843 // We can't add more than one pointer together, nor can we scale a 3844 // pointer (both of which seem meaningless). 3845 if (ResultPtr || AddrMode.Scale != 1) 3846 return false; 3847 3848 ResultPtr = AddrMode.ScaledReg; 3849 AddrMode.Scale = 0; 3850 } 3851 3852 if (AddrMode.BaseGV) { 3853 if (ResultPtr) 3854 return false; 3855 3856 ResultPtr = AddrMode.BaseGV; 3857 } 3858 3859 // If the real base value actually came from an inttoptr, then the matcher 3860 // will look through it and provide only the integer value. In that case, 3861 // use it here. 3862 if (!ResultPtr && AddrMode.BaseReg) { 3863 ResultPtr = 3864 Builder.CreateIntToPtr(AddrMode.BaseReg, Addr->getType(), "sunkaddr"); 3865 AddrMode.BaseReg = nullptr; 3866 } else if (!ResultPtr && AddrMode.Scale == 1) { 3867 ResultPtr = 3868 Builder.CreateIntToPtr(AddrMode.ScaledReg, Addr->getType(), "sunkaddr"); 3869 AddrMode.Scale = 0; 3870 } 3871 3872 if (!ResultPtr && 3873 !AddrMode.BaseReg && !AddrMode.Scale && !AddrMode.BaseOffs) { 3874 SunkAddr = Constant::getNullValue(Addr->getType()); 3875 } else if (!ResultPtr) { 3876 return false; 3877 } else { 3878 Type *I8PtrTy = 3879 Builder.getInt8PtrTy(Addr->getType()->getPointerAddressSpace()); 3880 Type *I8Ty = Builder.getInt8Ty(); 3881 3882 // Start with the base register. Do this first so that subsequent address 3883 // matching finds it last, which will prevent it from trying to match it 3884 // as the scaled value in case it happens to be a mul. That would be 3885 // problematic if we've sunk a different mul for the scale, because then 3886 // we'd end up sinking both muls. 3887 if (AddrMode.BaseReg) { 3888 Value *V = AddrMode.BaseReg; 3889 if (V->getType() != IntPtrTy) 3890 V = Builder.CreateIntCast(V, IntPtrTy, /*isSigned=*/true, "sunkaddr"); 3891 3892 ResultIndex = V; 3893 } 3894 3895 // Add the scale value. 3896 if (AddrMode.Scale) { 3897 Value *V = AddrMode.ScaledReg; 3898 if (V->getType() == IntPtrTy) { 3899 // done. 3900 } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() < 3901 cast<IntegerType>(V->getType())->getBitWidth()) { 3902 V = Builder.CreateTrunc(V, IntPtrTy, "sunkaddr"); 3903 } else { 3904 // It is only safe to sign extend the BaseReg if we know that the math 3905 // required to create it did not overflow before we extend it. Since 3906 // the original IR value was tossed in favor of a constant back when 3907 // the AddrMode was created we need to bail out gracefully if widths 3908 // do not match instead of extending it. 3909 Instruction *I = dyn_cast_or_null<Instruction>(ResultIndex); 3910 if (I && (ResultIndex != AddrMode.BaseReg)) 3911 I->eraseFromParent(); 3912 return false; 3913 } 3914 3915 if (AddrMode.Scale != 1) 3916 V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy, AddrMode.Scale), 3917 "sunkaddr"); 3918 if (ResultIndex) 3919 ResultIndex = Builder.CreateAdd(ResultIndex, V, "sunkaddr"); 3920 else 3921 ResultIndex = V; 3922 } 3923 3924 // Add in the Base Offset if present. 3925 if (AddrMode.BaseOffs) { 3926 Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs); 3927 if (ResultIndex) { 3928 // We need to add this separately from the scale above to help with 3929 // SDAG consecutive load/store merging. 3930 if (ResultPtr->getType() != I8PtrTy) 3931 ResultPtr = Builder.CreateBitCast(ResultPtr, I8PtrTy); 3932 ResultPtr = Builder.CreateGEP(I8Ty, ResultPtr, ResultIndex, "sunkaddr"); 3933 } 3934 3935 ResultIndex = V; 3936 } 3937 3938 if (!ResultIndex) { 3939 SunkAddr = ResultPtr; 3940 } else { 3941 if (ResultPtr->getType() != I8PtrTy) 3942 ResultPtr = Builder.CreateBitCast(ResultPtr, I8PtrTy); 3943 SunkAddr = Builder.CreateGEP(I8Ty, ResultPtr, ResultIndex, "sunkaddr"); 3944 } 3945 3946 if (SunkAddr->getType() != Addr->getType()) 3947 SunkAddr = Builder.CreateBitCast(SunkAddr, Addr->getType()); 3948 } 3949 } else { 3950 DEBUG(dbgs() << "CGP: SINKING nonlocal addrmode: " << AddrMode << " for " 3951 << *MemoryInst << "\n"); 3952 Type *IntPtrTy = DL->getIntPtrType(Addr->getType()); 3953 Value *Result = nullptr; 3954 3955 // Start with the base register. Do this first so that subsequent address 3956 // matching finds it last, which will prevent it from trying to match it 3957 // as the scaled value in case it happens to be a mul. That would be 3958 // problematic if we've sunk a different mul for the scale, because then 3959 // we'd end up sinking both muls. 3960 if (AddrMode.BaseReg) { 3961 Value *V = AddrMode.BaseReg; 3962 if (V->getType()->isPointerTy()) 3963 V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr"); 3964 if (V->getType() != IntPtrTy) 3965 V = Builder.CreateIntCast(V, IntPtrTy, /*isSigned=*/true, "sunkaddr"); 3966 Result = V; 3967 } 3968 3969 // Add the scale value. 3970 if (AddrMode.Scale) { 3971 Value *V = AddrMode.ScaledReg; 3972 if (V->getType() == IntPtrTy) { 3973 // done. 3974 } else if (V->getType()->isPointerTy()) { 3975 V = Builder.CreatePtrToInt(V, IntPtrTy, "sunkaddr"); 3976 } else if (cast<IntegerType>(IntPtrTy)->getBitWidth() < 3977 cast<IntegerType>(V->getType())->getBitWidth()) { 3978 V = Builder.CreateTrunc(V, IntPtrTy, "sunkaddr"); 3979 } else { 3980 // It is only safe to sign extend the BaseReg if we know that the math 3981 // required to create it did not overflow before we extend it. Since 3982 // the original IR value was tossed in favor of a constant back when 3983 // the AddrMode was created we need to bail out gracefully if widths 3984 // do not match instead of extending it. 3985 Instruction *I = dyn_cast_or_null<Instruction>(Result); 3986 if (I && (Result != AddrMode.BaseReg)) 3987 I->eraseFromParent(); 3988 return false; 3989 } 3990 if (AddrMode.Scale != 1) 3991 V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy, AddrMode.Scale), 3992 "sunkaddr"); 3993 if (Result) 3994 Result = Builder.CreateAdd(Result, V, "sunkaddr"); 3995 else 3996 Result = V; 3997 } 3998 3999 // Add in the BaseGV if present. 4000 if (AddrMode.BaseGV) { 4001 Value *V = Builder.CreatePtrToInt(AddrMode.BaseGV, IntPtrTy, "sunkaddr"); 4002 if (Result) 4003 Result = Builder.CreateAdd(Result, V, "sunkaddr"); 4004 else 4005 Result = V; 4006 } 4007 4008 // Add in the Base Offset if present. 4009 if (AddrMode.BaseOffs) { 4010 Value *V = ConstantInt::get(IntPtrTy, AddrMode.BaseOffs); 4011 if (Result) 4012 Result = Builder.CreateAdd(Result, V, "sunkaddr"); 4013 else 4014 Result = V; 4015 } 4016 4017 if (!Result) 4018 SunkAddr = Constant::getNullValue(Addr->getType()); 4019 else 4020 SunkAddr = Builder.CreateIntToPtr(Result, Addr->getType(), "sunkaddr"); 4021 } 4022 4023 MemoryInst->replaceUsesOfWith(Repl, SunkAddr); 4024 4025 // If we have no uses, recursively delete the value and all dead instructions 4026 // using it. 4027 if (Repl->use_empty()) { 4028 // This can cause recursive deletion, which can invalidate our iterator. 4029 // Use a WeakVH to hold onto it in case this happens. 4030 Value *CurValue = &*CurInstIterator; 4031 WeakVH IterHandle(CurValue); 4032 BasicBlock *BB = CurInstIterator->getParent(); 4033 4034 RecursivelyDeleteTriviallyDeadInstructions(Repl, TLInfo); 4035 4036 if (IterHandle != CurValue) { 4037 // If the iterator instruction was recursively deleted, start over at the 4038 // start of the block. 4039 CurInstIterator = BB->begin(); 4040 SunkAddrs.clear(); 4041 } 4042 } 4043 ++NumMemoryInsts; 4044 return true; 4045 } 4046 4047 /// If there are any memory operands, use OptimizeMemoryInst to sink their 4048 /// address computing into the block when possible / profitable. 4049 bool CodeGenPrepare::optimizeInlineAsmInst(CallInst *CS) { 4050 bool MadeChange = false; 4051 4052 const TargetRegisterInfo *TRI = 4053 TM->getSubtargetImpl(*CS->getParent()->getParent())->getRegisterInfo(); 4054 TargetLowering::AsmOperandInfoVector TargetConstraints = 4055 TLI->ParseConstraints(*DL, TRI, CS); 4056 unsigned ArgNo = 0; 4057 for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) { 4058 TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i]; 4059 4060 // Compute the constraint code and ConstraintType to use. 4061 TLI->ComputeConstraintToUse(OpInfo, SDValue()); 4062 4063 if (OpInfo.ConstraintType == TargetLowering::C_Memory && 4064 OpInfo.isIndirect) { 4065 Value *OpVal = CS->getArgOperand(ArgNo++); 4066 MadeChange |= optimizeMemoryInst(CS, OpVal, OpVal->getType(), ~0u); 4067 } else if (OpInfo.Type == InlineAsm::isInput) 4068 ArgNo++; 4069 } 4070 4071 return MadeChange; 4072 } 4073 4074 /// \brief Check if all the uses of \p Inst are equivalent (or free) zero or 4075 /// sign extensions. 4076 static bool hasSameExtUse(Instruction *Inst, const TargetLowering &TLI) { 4077 assert(!Inst->use_empty() && "Input must have at least one use"); 4078 const Instruction *FirstUser = cast<Instruction>(*Inst->user_begin()); 4079 bool IsSExt = isa<SExtInst>(FirstUser); 4080 Type *ExtTy = FirstUser->getType(); 4081 for (const User *U : Inst->users()) { 4082 const Instruction *UI = cast<Instruction>(U); 4083 if ((IsSExt && !isa<SExtInst>(UI)) || (!IsSExt && !isa<ZExtInst>(UI))) 4084 return false; 4085 Type *CurTy = UI->getType(); 4086 // Same input and output types: Same instruction after CSE. 4087 if (CurTy == ExtTy) 4088 continue; 4089 4090 // If IsSExt is true, we are in this situation: 4091 // a = Inst 4092 // b = sext ty1 a to ty2 4093 // c = sext ty1 a to ty3 4094 // Assuming ty2 is shorter than ty3, this could be turned into: 4095 // a = Inst 4096 // b = sext ty1 a to ty2 4097 // c = sext ty2 b to ty3 4098 // However, the last sext is not free. 4099 if (IsSExt) 4100 return false; 4101 4102 // This is a ZExt, maybe this is free to extend from one type to another. 4103 // In that case, we would not account for a different use. 4104 Type *NarrowTy; 4105 Type *LargeTy; 4106 if (ExtTy->getScalarType()->getIntegerBitWidth() > 4107 CurTy->getScalarType()->getIntegerBitWidth()) { 4108 NarrowTy = CurTy; 4109 LargeTy = ExtTy; 4110 } else { 4111 NarrowTy = ExtTy; 4112 LargeTy = CurTy; 4113 } 4114 4115 if (!TLI.isZExtFree(NarrowTy, LargeTy)) 4116 return false; 4117 } 4118 // All uses are the same or can be derived from one another for free. 4119 return true; 4120 } 4121 4122 /// \brief Try to form ExtLd by promoting \p Exts until they reach a 4123 /// load instruction. 4124 /// If an ext(load) can be formed, it is returned via \p LI for the load 4125 /// and \p Inst for the extension. 4126 /// Otherwise LI == nullptr and Inst == nullptr. 4127 /// When some promotion happened, \p TPT contains the proper state to 4128 /// revert them. 4129 /// 4130 /// \return true when promoting was necessary to expose the ext(load) 4131 /// opportunity, false otherwise. 4132 /// 4133 /// Example: 4134 /// \code 4135 /// %ld = load i32* %addr 4136 /// %add = add nuw i32 %ld, 4 4137 /// %zext = zext i32 %add to i64 4138 /// \endcode 4139 /// => 4140 /// \code 4141 /// %ld = load i32* %addr 4142 /// %zext = zext i32 %ld to i64 4143 /// %add = add nuw i64 %zext, 4 4144 /// \encode 4145 /// Thanks to the promotion, we can match zext(load i32*) to i64. 4146 bool CodeGenPrepare::extLdPromotion(TypePromotionTransaction &TPT, 4147 LoadInst *&LI, Instruction *&Inst, 4148 const SmallVectorImpl<Instruction *> &Exts, 4149 unsigned CreatedInstsCost = 0) { 4150 // Iterate over all the extensions to see if one form an ext(load). 4151 for (auto I : Exts) { 4152 // Check if we directly have ext(load). 4153 if ((LI = dyn_cast<LoadInst>(I->getOperand(0)))) { 4154 Inst = I; 4155 // No promotion happened here. 4156 return false; 4157 } 4158 // Check whether or not we want to do any promotion. 4159 if (!TLI || !TLI->enableExtLdPromotion() || DisableExtLdPromotion) 4160 continue; 4161 // Get the action to perform the promotion. 4162 TypePromotionHelper::Action TPH = TypePromotionHelper::getAction( 4163 I, InsertedInsts, *TLI, PromotedInsts); 4164 // Check if we can promote. 4165 if (!TPH) 4166 continue; 4167 // Save the current state. 4168 TypePromotionTransaction::ConstRestorationPt LastKnownGood = 4169 TPT.getRestorationPoint(); 4170 SmallVector<Instruction *, 4> NewExts; 4171 unsigned NewCreatedInstsCost = 0; 4172 unsigned ExtCost = !TLI->isExtFree(I); 4173 // Promote. 4174 Value *PromotedVal = TPH(I, TPT, PromotedInsts, NewCreatedInstsCost, 4175 &NewExts, nullptr, *TLI); 4176 assert(PromotedVal && 4177 "TypePromotionHelper should have filtered out those cases"); 4178 4179 // We would be able to merge only one extension in a load. 4180 // Therefore, if we have more than 1 new extension we heuristically 4181 // cut this search path, because it means we degrade the code quality. 4182 // With exactly 2, the transformation is neutral, because we will merge 4183 // one extension but leave one. However, we optimistically keep going, 4184 // because the new extension may be removed too. 4185 long long TotalCreatedInstsCost = CreatedInstsCost + NewCreatedInstsCost; 4186 TotalCreatedInstsCost -= ExtCost; 4187 if (!StressExtLdPromotion && 4188 (TotalCreatedInstsCost > 1 || 4189 !isPromotedInstructionLegal(*TLI, *DL, PromotedVal))) { 4190 // The promotion is not profitable, rollback to the previous state. 4191 TPT.rollback(LastKnownGood); 4192 continue; 4193 } 4194 // The promotion is profitable. 4195 // Check if it exposes an ext(load). 4196 (void)extLdPromotion(TPT, LI, Inst, NewExts, TotalCreatedInstsCost); 4197 if (LI && (StressExtLdPromotion || NewCreatedInstsCost <= ExtCost || 4198 // If we have created a new extension, i.e., now we have two 4199 // extensions. We must make sure one of them is merged with 4200 // the load, otherwise we may degrade the code quality. 4201 (LI->hasOneUse() || hasSameExtUse(LI, *TLI)))) 4202 // Promotion happened. 4203 return true; 4204 // If this does not help to expose an ext(load) then, rollback. 4205 TPT.rollback(LastKnownGood); 4206 } 4207 // None of the extension can form an ext(load). 4208 LI = nullptr; 4209 Inst = nullptr; 4210 return false; 4211 } 4212 4213 /// Move a zext or sext fed by a load into the same basic block as the load, 4214 /// unless conditions are unfavorable. This allows SelectionDAG to fold the 4215 /// extend into the load. 4216 /// \p I[in/out] the extension may be modified during the process if some 4217 /// promotions apply. 4218 /// 4219 bool CodeGenPrepare::moveExtToFormExtLoad(Instruction *&I) { 4220 // Try to promote a chain of computation if it allows to form 4221 // an extended load. 4222 TypePromotionTransaction TPT; 4223 TypePromotionTransaction::ConstRestorationPt LastKnownGood = 4224 TPT.getRestorationPoint(); 4225 SmallVector<Instruction *, 1> Exts; 4226 Exts.push_back(I); 4227 // Look for a load being extended. 4228 LoadInst *LI = nullptr; 4229 Instruction *OldExt = I; 4230 bool HasPromoted = extLdPromotion(TPT, LI, I, Exts); 4231 if (!LI || !I) { 4232 assert(!HasPromoted && !LI && "If we did not match any load instruction " 4233 "the code must remain the same"); 4234 I = OldExt; 4235 return false; 4236 } 4237 4238 // If they're already in the same block, there's nothing to do. 4239 // Make the cheap checks first if we did not promote. 4240 // If we promoted, we need to check if it is indeed profitable. 4241 if (!HasPromoted && LI->getParent() == I->getParent()) 4242 return false; 4243 4244 EVT VT = TLI->getValueType(*DL, I->getType()); 4245 EVT LoadVT = TLI->getValueType(*DL, LI->getType()); 4246 4247 // If the load has other users and the truncate is not free, this probably 4248 // isn't worthwhile. 4249 if (!LI->hasOneUse() && TLI && 4250 (TLI->isTypeLegal(LoadVT) || !TLI->isTypeLegal(VT)) && 4251 !TLI->isTruncateFree(I->getType(), LI->getType())) { 4252 I = OldExt; 4253 TPT.rollback(LastKnownGood); 4254 return false; 4255 } 4256 4257 // Check whether the target supports casts folded into loads. 4258 unsigned LType; 4259 if (isa<ZExtInst>(I)) 4260 LType = ISD::ZEXTLOAD; 4261 else { 4262 assert(isa<SExtInst>(I) && "Unexpected ext type!"); 4263 LType = ISD::SEXTLOAD; 4264 } 4265 if (TLI && !TLI->isLoadExtLegal(LType, VT, LoadVT)) { 4266 I = OldExt; 4267 TPT.rollback(LastKnownGood); 4268 return false; 4269 } 4270 4271 // Move the extend into the same block as the load, so that SelectionDAG 4272 // can fold it. 4273 TPT.commit(); 4274 I->removeFromParent(); 4275 I->insertAfter(LI); 4276 ++NumExtsMoved; 4277 return true; 4278 } 4279 4280 bool CodeGenPrepare::optimizeExtUses(Instruction *I) { 4281 BasicBlock *DefBB = I->getParent(); 4282 4283 // If the result of a {s|z}ext and its source are both live out, rewrite all 4284 // other uses of the source with result of extension. 4285 Value *Src = I->getOperand(0); 4286 if (Src->hasOneUse()) 4287 return false; 4288 4289 // Only do this xform if truncating is free. 4290 if (TLI && !TLI->isTruncateFree(I->getType(), Src->getType())) 4291 return false; 4292 4293 // Only safe to perform the optimization if the source is also defined in 4294 // this block. 4295 if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->getParent()) 4296 return false; 4297 4298 bool DefIsLiveOut = false; 4299 for (User *U : I->users()) { 4300 Instruction *UI = cast<Instruction>(U); 4301 4302 // Figure out which BB this ext is used in. 4303 BasicBlock *UserBB = UI->getParent(); 4304 if (UserBB == DefBB) continue; 4305 DefIsLiveOut = true; 4306 break; 4307 } 4308 if (!DefIsLiveOut) 4309 return false; 4310 4311 // Make sure none of the uses are PHI nodes. 4312 for (User *U : Src->users()) { 4313 Instruction *UI = cast<Instruction>(U); 4314 BasicBlock *UserBB = UI->getParent(); 4315 if (UserBB == DefBB) continue; 4316 // Be conservative. We don't want this xform to end up introducing 4317 // reloads just before load / store instructions. 4318 if (isa<PHINode>(UI) || isa<LoadInst>(UI) || isa<StoreInst>(UI)) 4319 return false; 4320 } 4321 4322 // InsertedTruncs - Only insert one trunc in each block once. 4323 DenseMap<BasicBlock*, Instruction*> InsertedTruncs; 4324 4325 bool MadeChange = false; 4326 for (Use &U : Src->uses()) { 4327 Instruction *User = cast<Instruction>(U.getUser()); 4328 4329 // Figure out which BB this ext is used in. 4330 BasicBlock *UserBB = User->getParent(); 4331 if (UserBB == DefBB) continue; 4332 4333 // Both src and def are live in this block. Rewrite the use. 4334 Instruction *&InsertedTrunc = InsertedTruncs[UserBB]; 4335 4336 if (!InsertedTrunc) { 4337 BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt(); 4338 assert(InsertPt != UserBB->end()); 4339 InsertedTrunc = new TruncInst(I, Src->getType(), "", &*InsertPt); 4340 InsertedInsts.insert(InsertedTrunc); 4341 } 4342 4343 // Replace a use of the {s|z}ext source with a use of the result. 4344 U = InsertedTrunc; 4345 ++NumExtUses; 4346 MadeChange = true; 4347 } 4348 4349 return MadeChange; 4350 } 4351 4352 // Find loads whose uses only use some of the loaded value's bits. Add an "and" 4353 // just after the load if the target can fold this into one extload instruction, 4354 // with the hope of eliminating some of the other later "and" instructions using 4355 // the loaded value. "and"s that are made trivially redundant by the insertion 4356 // of the new "and" are removed by this function, while others (e.g. those whose 4357 // path from the load goes through a phi) are left for isel to potentially 4358 // remove. 4359 // 4360 // For example: 4361 // 4362 // b0: 4363 // x = load i32 4364 // ... 4365 // b1: 4366 // y = and x, 0xff 4367 // z = use y 4368 // 4369 // becomes: 4370 // 4371 // b0: 4372 // x = load i32 4373 // x' = and x, 0xff 4374 // ... 4375 // b1: 4376 // z = use x' 4377 // 4378 // whereas: 4379 // 4380 // b0: 4381 // x1 = load i32 4382 // ... 4383 // b1: 4384 // x2 = load i32 4385 // ... 4386 // b2: 4387 // x = phi x1, x2 4388 // y = and x, 0xff 4389 // 4390 // becomes (after a call to optimizeLoadExt for each load): 4391 // 4392 // b0: 4393 // x1 = load i32 4394 // x1' = and x1, 0xff 4395 // ... 4396 // b1: 4397 // x2 = load i32 4398 // x2' = and x2, 0xff 4399 // ... 4400 // b2: 4401 // x = phi x1', x2' 4402 // y = and x, 0xff 4403 // 4404 4405 bool CodeGenPrepare::optimizeLoadExt(LoadInst *Load) { 4406 4407 if (!Load->isSimple() || 4408 !(Load->getType()->isIntegerTy() || Load->getType()->isPointerTy())) 4409 return false; 4410 4411 // Skip loads we've already transformed or have no reason to transform. 4412 if (Load->hasOneUse()) { 4413 User *LoadUser = *Load->user_begin(); 4414 if (cast<Instruction>(LoadUser)->getParent() == Load->getParent() && 4415 !dyn_cast<PHINode>(LoadUser)) 4416 return false; 4417 } 4418 4419 // Look at all uses of Load, looking through phis, to determine how many bits 4420 // of the loaded value are needed. 4421 SmallVector<Instruction *, 8> WorkList; 4422 SmallPtrSet<Instruction *, 16> Visited; 4423 SmallVector<Instruction *, 8> AndsToMaybeRemove; 4424 for (auto *U : Load->users()) 4425 WorkList.push_back(cast<Instruction>(U)); 4426 4427 EVT LoadResultVT = TLI->getValueType(*DL, Load->getType()); 4428 unsigned BitWidth = LoadResultVT.getSizeInBits(); 4429 APInt DemandBits(BitWidth, 0); 4430 APInt WidestAndBits(BitWidth, 0); 4431 4432 while (!WorkList.empty()) { 4433 Instruction *I = WorkList.back(); 4434 WorkList.pop_back(); 4435 4436 // Break use-def graph loops. 4437 if (!Visited.insert(I).second) 4438 continue; 4439 4440 // For a PHI node, push all of its users. 4441 if (auto *Phi = dyn_cast<PHINode>(I)) { 4442 for (auto *U : Phi->users()) 4443 WorkList.push_back(cast<Instruction>(U)); 4444 continue; 4445 } 4446 4447 switch (I->getOpcode()) { 4448 case llvm::Instruction::And: { 4449 auto *AndC = dyn_cast<ConstantInt>(I->getOperand(1)); 4450 if (!AndC) 4451 return false; 4452 APInt AndBits = AndC->getValue(); 4453 DemandBits |= AndBits; 4454 // Keep track of the widest and mask we see. 4455 if (AndBits.ugt(WidestAndBits)) 4456 WidestAndBits = AndBits; 4457 if (AndBits == WidestAndBits && I->getOperand(0) == Load) 4458 AndsToMaybeRemove.push_back(I); 4459 break; 4460 } 4461 4462 case llvm::Instruction::Shl: { 4463 auto *ShlC = dyn_cast<ConstantInt>(I->getOperand(1)); 4464 if (!ShlC) 4465 return false; 4466 uint64_t ShiftAmt = ShlC->getLimitedValue(BitWidth - 1); 4467 auto ShlDemandBits = APInt::getAllOnesValue(BitWidth).lshr(ShiftAmt); 4468 DemandBits |= ShlDemandBits; 4469 break; 4470 } 4471 4472 case llvm::Instruction::Trunc: { 4473 EVT TruncVT = TLI->getValueType(*DL, I->getType()); 4474 unsigned TruncBitWidth = TruncVT.getSizeInBits(); 4475 auto TruncBits = APInt::getAllOnesValue(TruncBitWidth).zext(BitWidth); 4476 DemandBits |= TruncBits; 4477 break; 4478 } 4479 4480 default: 4481 return false; 4482 } 4483 } 4484 4485 uint32_t ActiveBits = DemandBits.getActiveBits(); 4486 // Avoid hoisting (and (load x) 1) since it is unlikely to be folded by the 4487 // target even if isLoadExtLegal says an i1 EXTLOAD is valid. For example, 4488 // for the AArch64 target isLoadExtLegal(ZEXTLOAD, i32, i1) returns true, but 4489 // (and (load x) 1) is not matched as a single instruction, rather as a LDR 4490 // followed by an AND. 4491 // TODO: Look into removing this restriction by fixing backends to either 4492 // return false for isLoadExtLegal for i1 or have them select this pattern to 4493 // a single instruction. 4494 // 4495 // Also avoid hoisting if we didn't see any ands with the exact DemandBits 4496 // mask, since these are the only ands that will be removed by isel. 4497 if (ActiveBits <= 1 || !APIntOps::isMask(ActiveBits, DemandBits) || 4498 WidestAndBits != DemandBits) 4499 return false; 4500 4501 LLVMContext &Ctx = Load->getType()->getContext(); 4502 Type *TruncTy = Type::getIntNTy(Ctx, ActiveBits); 4503 EVT TruncVT = TLI->getValueType(*DL, TruncTy); 4504 4505 // Reject cases that won't be matched as extloads. 4506 if (!LoadResultVT.bitsGT(TruncVT) || !TruncVT.isRound() || 4507 !TLI->isLoadExtLegal(ISD::ZEXTLOAD, LoadResultVT, TruncVT)) 4508 return false; 4509 4510 IRBuilder<> Builder(Load->getNextNode()); 4511 auto *NewAnd = dyn_cast<Instruction>( 4512 Builder.CreateAnd(Load, ConstantInt::get(Ctx, DemandBits))); 4513 4514 // Replace all uses of load with new and (except for the use of load in the 4515 // new and itself). 4516 Load->replaceAllUsesWith(NewAnd); 4517 NewAnd->setOperand(0, Load); 4518 4519 // Remove any and instructions that are now redundant. 4520 for (auto *And : AndsToMaybeRemove) 4521 // Check that the and mask is the same as the one we decided to put on the 4522 // new and. 4523 if (cast<ConstantInt>(And->getOperand(1))->getValue() == DemandBits) { 4524 And->replaceAllUsesWith(NewAnd); 4525 if (&*CurInstIterator == And) 4526 CurInstIterator = std::next(And->getIterator()); 4527 And->eraseFromParent(); 4528 ++NumAndUses; 4529 } 4530 4531 ++NumAndsAdded; 4532 return true; 4533 } 4534 4535 /// Check if V (an operand of a select instruction) is an expensive instruction 4536 /// that is only used once. 4537 static bool sinkSelectOperand(const TargetTransformInfo *TTI, Value *V) { 4538 auto *I = dyn_cast<Instruction>(V); 4539 // If it's safe to speculatively execute, then it should not have side 4540 // effects; therefore, it's safe to sink and possibly *not* execute. 4541 return I && I->hasOneUse() && isSafeToSpeculativelyExecute(I) && 4542 TTI->getUserCost(I) >= TargetTransformInfo::TCC_Expensive; 4543 } 4544 4545 /// Returns true if a SelectInst should be turned into an explicit branch. 4546 static bool isFormingBranchFromSelectProfitable(const TargetTransformInfo *TTI, 4547 const TargetLowering *TLI, 4548 SelectInst *SI) { 4549 // If even a predictable select is cheap, then a branch can't be cheaper. 4550 if (!TLI->isPredictableSelectExpensive()) 4551 return false; 4552 4553 // FIXME: This should use the same heuristics as IfConversion to determine 4554 // whether a select is better represented as a branch. 4555 4556 // If metadata tells us that the select condition is obviously predictable, 4557 // then we want to replace the select with a branch. 4558 uint64_t TrueWeight, FalseWeight; 4559 if (SI->extractProfMetadata(TrueWeight, FalseWeight)) { 4560 uint64_t Max = std::max(TrueWeight, FalseWeight); 4561 uint64_t Sum = TrueWeight + FalseWeight; 4562 if (Sum != 0) { 4563 auto Probability = BranchProbability::getBranchProbability(Max, Sum); 4564 if (Probability > TLI->getPredictableBranchThreshold()) 4565 return true; 4566 } 4567 } 4568 4569 CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition()); 4570 4571 // If a branch is predictable, an out-of-order CPU can avoid blocking on its 4572 // comparison condition. If the compare has more than one use, there's 4573 // probably another cmov or setcc around, so it's not worth emitting a branch. 4574 if (!Cmp || !Cmp->hasOneUse()) 4575 return false; 4576 4577 // If either operand of the select is expensive and only needed on one side 4578 // of the select, we should form a branch. 4579 if (sinkSelectOperand(TTI, SI->getTrueValue()) || 4580 sinkSelectOperand(TTI, SI->getFalseValue())) 4581 return true; 4582 4583 return false; 4584 } 4585 4586 4587 /// If we have a SelectInst that will likely profit from branch prediction, 4588 /// turn it into a branch. 4589 bool CodeGenPrepare::optimizeSelectInst(SelectInst *SI) { 4590 bool VectorCond = !SI->getCondition()->getType()->isIntegerTy(1); 4591 4592 // Can we convert the 'select' to CF ? 4593 if (DisableSelectToBranch || OptSize || !TLI || VectorCond || 4594 SI->getMetadata(LLVMContext::MD_unpredictable)) 4595 return false; 4596 4597 TargetLowering::SelectSupportKind SelectKind; 4598 if (VectorCond) 4599 SelectKind = TargetLowering::VectorMaskSelect; 4600 else if (SI->getType()->isVectorTy()) 4601 SelectKind = TargetLowering::ScalarCondVectorVal; 4602 else 4603 SelectKind = TargetLowering::ScalarValSelect; 4604 4605 if (TLI->isSelectSupported(SelectKind) && 4606 !isFormingBranchFromSelectProfitable(TTI, TLI, SI)) 4607 return false; 4608 4609 ModifiedDT = true; 4610 4611 // Transform a sequence like this: 4612 // start: 4613 // %cmp = cmp uge i32 %a, %b 4614 // %sel = select i1 %cmp, i32 %c, i32 %d 4615 // 4616 // Into: 4617 // start: 4618 // %cmp = cmp uge i32 %a, %b 4619 // br i1 %cmp, label %select.true, label %select.false 4620 // select.true: 4621 // br label %select.end 4622 // select.false: 4623 // br label %select.end 4624 // select.end: 4625 // %sel = phi i32 [ %c, %select.true ], [ %d, %select.false ] 4626 // 4627 // In addition, we may sink instructions that produce %c or %d from 4628 // the entry block into the destination(s) of the new branch. 4629 // If the true or false blocks do not contain a sunken instruction, that 4630 // block and its branch may be optimized away. In that case, one side of the 4631 // first branch will point directly to select.end, and the corresponding PHI 4632 // predecessor block will be the start block. 4633 4634 // First, we split the block containing the select into 2 blocks. 4635 BasicBlock *StartBlock = SI->getParent(); 4636 BasicBlock::iterator SplitPt = ++(BasicBlock::iterator(SI)); 4637 BasicBlock *EndBlock = StartBlock->splitBasicBlock(SplitPt, "select.end"); 4638 4639 // Delete the unconditional branch that was just created by the split. 4640 StartBlock->getTerminator()->eraseFromParent(); 4641 4642 // These are the new basic blocks for the conditional branch. 4643 // At least one will become an actual new basic block. 4644 BasicBlock *TrueBlock = nullptr; 4645 BasicBlock *FalseBlock = nullptr; 4646 4647 // Sink expensive instructions into the conditional blocks to avoid executing 4648 // them speculatively. 4649 if (sinkSelectOperand(TTI, SI->getTrueValue())) { 4650 TrueBlock = BasicBlock::Create(SI->getContext(), "select.true.sink", 4651 EndBlock->getParent(), EndBlock); 4652 auto *TrueBranch = BranchInst::Create(EndBlock, TrueBlock); 4653 auto *TrueInst = cast<Instruction>(SI->getTrueValue()); 4654 TrueInst->moveBefore(TrueBranch); 4655 } 4656 if (sinkSelectOperand(TTI, SI->getFalseValue())) { 4657 FalseBlock = BasicBlock::Create(SI->getContext(), "select.false.sink", 4658 EndBlock->getParent(), EndBlock); 4659 auto *FalseBranch = BranchInst::Create(EndBlock, FalseBlock); 4660 auto *FalseInst = cast<Instruction>(SI->getFalseValue()); 4661 FalseInst->moveBefore(FalseBranch); 4662 } 4663 4664 // If there was nothing to sink, then arbitrarily choose the 'false' side 4665 // for a new input value to the PHI. 4666 if (TrueBlock == FalseBlock) { 4667 assert(TrueBlock == nullptr && 4668 "Unexpected basic block transform while optimizing select"); 4669 4670 FalseBlock = BasicBlock::Create(SI->getContext(), "select.false", 4671 EndBlock->getParent(), EndBlock); 4672 BranchInst::Create(EndBlock, FalseBlock); 4673 } 4674 4675 // Insert the real conditional branch based on the original condition. 4676 // If we did not create a new block for one of the 'true' or 'false' paths 4677 // of the condition, it means that side of the branch goes to the end block 4678 // directly and the path originates from the start block from the point of 4679 // view of the new PHI. 4680 if (TrueBlock == nullptr) { 4681 BranchInst::Create(EndBlock, FalseBlock, SI->getCondition(), SI); 4682 TrueBlock = StartBlock; 4683 } else if (FalseBlock == nullptr) { 4684 BranchInst::Create(TrueBlock, EndBlock, SI->getCondition(), SI); 4685 FalseBlock = StartBlock; 4686 } else { 4687 BranchInst::Create(TrueBlock, FalseBlock, SI->getCondition(), SI); 4688 } 4689 4690 // The select itself is replaced with a PHI Node. 4691 PHINode *PN = PHINode::Create(SI->getType(), 2, "", &EndBlock->front()); 4692 PN->takeName(SI); 4693 PN->addIncoming(SI->getTrueValue(), TrueBlock); 4694 PN->addIncoming(SI->getFalseValue(), FalseBlock); 4695 4696 SI->replaceAllUsesWith(PN); 4697 SI->eraseFromParent(); 4698 4699 // Instruct OptimizeBlock to skip to the next block. 4700 CurInstIterator = StartBlock->end(); 4701 ++NumSelectsExpanded; 4702 return true; 4703 } 4704 4705 static bool isBroadcastShuffle(ShuffleVectorInst *SVI) { 4706 SmallVector<int, 16> Mask(SVI->getShuffleMask()); 4707 int SplatElem = -1; 4708 for (unsigned i = 0; i < Mask.size(); ++i) { 4709 if (SplatElem != -1 && Mask[i] != -1 && Mask[i] != SplatElem) 4710 return false; 4711 SplatElem = Mask[i]; 4712 } 4713 4714 return true; 4715 } 4716 4717 /// Some targets have expensive vector shifts if the lanes aren't all the same 4718 /// (e.g. x86 only introduced "vpsllvd" and friends with AVX2). In these cases 4719 /// it's often worth sinking a shufflevector splat down to its use so that 4720 /// codegen can spot all lanes are identical. 4721 bool CodeGenPrepare::optimizeShuffleVectorInst(ShuffleVectorInst *SVI) { 4722 BasicBlock *DefBB = SVI->getParent(); 4723 4724 // Only do this xform if variable vector shifts are particularly expensive. 4725 if (!TLI || !TLI->isVectorShiftByScalarCheap(SVI->getType())) 4726 return false; 4727 4728 // We only expect better codegen by sinking a shuffle if we can recognise a 4729 // constant splat. 4730 if (!isBroadcastShuffle(SVI)) 4731 return false; 4732 4733 // InsertedShuffles - Only insert a shuffle in each block once. 4734 DenseMap<BasicBlock*, Instruction*> InsertedShuffles; 4735 4736 bool MadeChange = false; 4737 for (User *U : SVI->users()) { 4738 Instruction *UI = cast<Instruction>(U); 4739 4740 // Figure out which BB this ext is used in. 4741 BasicBlock *UserBB = UI->getParent(); 4742 if (UserBB == DefBB) continue; 4743 4744 // For now only apply this when the splat is used by a shift instruction. 4745 if (!UI->isShift()) continue; 4746 4747 // Everything checks out, sink the shuffle if the user's block doesn't 4748 // already have a copy. 4749 Instruction *&InsertedShuffle = InsertedShuffles[UserBB]; 4750 4751 if (!InsertedShuffle) { 4752 BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt(); 4753 assert(InsertPt != UserBB->end()); 4754 InsertedShuffle = 4755 new ShuffleVectorInst(SVI->getOperand(0), SVI->getOperand(1), 4756 SVI->getOperand(2), "", &*InsertPt); 4757 } 4758 4759 UI->replaceUsesOfWith(SVI, InsertedShuffle); 4760 MadeChange = true; 4761 } 4762 4763 // If we removed all uses, nuke the shuffle. 4764 if (SVI->use_empty()) { 4765 SVI->eraseFromParent(); 4766 MadeChange = true; 4767 } 4768 4769 return MadeChange; 4770 } 4771 4772 bool CodeGenPrepare::optimizeSwitchInst(SwitchInst *SI) { 4773 if (!TLI || !DL) 4774 return false; 4775 4776 Value *Cond = SI->getCondition(); 4777 Type *OldType = Cond->getType(); 4778 LLVMContext &Context = Cond->getContext(); 4779 MVT RegType = TLI->getRegisterType(Context, TLI->getValueType(*DL, OldType)); 4780 unsigned RegWidth = RegType.getSizeInBits(); 4781 4782 if (RegWidth <= cast<IntegerType>(OldType)->getBitWidth()) 4783 return false; 4784 4785 // If the register width is greater than the type width, expand the condition 4786 // of the switch instruction and each case constant to the width of the 4787 // register. By widening the type of the switch condition, subsequent 4788 // comparisons (for case comparisons) will not need to be extended to the 4789 // preferred register width, so we will potentially eliminate N-1 extends, 4790 // where N is the number of cases in the switch. 4791 auto *NewType = Type::getIntNTy(Context, RegWidth); 4792 4793 // Zero-extend the switch condition and case constants unless the switch 4794 // condition is a function argument that is already being sign-extended. 4795 // In that case, we can avoid an unnecessary mask/extension by sign-extending 4796 // everything instead. 4797 Instruction::CastOps ExtType = Instruction::ZExt; 4798 if (auto *Arg = dyn_cast<Argument>(Cond)) 4799 if (Arg->hasSExtAttr()) 4800 ExtType = Instruction::SExt; 4801 4802 auto *ExtInst = CastInst::Create(ExtType, Cond, NewType); 4803 ExtInst->insertBefore(SI); 4804 SI->setCondition(ExtInst); 4805 for (SwitchInst::CaseIt Case : SI->cases()) { 4806 APInt NarrowConst = Case.getCaseValue()->getValue(); 4807 APInt WideConst = (ExtType == Instruction::ZExt) ? 4808 NarrowConst.zext(RegWidth) : NarrowConst.sext(RegWidth); 4809 Case.setValue(ConstantInt::get(Context, WideConst)); 4810 } 4811 4812 return true; 4813 } 4814 4815 namespace { 4816 /// \brief Helper class to promote a scalar operation to a vector one. 4817 /// This class is used to move downward extractelement transition. 4818 /// E.g., 4819 /// a = vector_op <2 x i32> 4820 /// b = extractelement <2 x i32> a, i32 0 4821 /// c = scalar_op b 4822 /// store c 4823 /// 4824 /// => 4825 /// a = vector_op <2 x i32> 4826 /// c = vector_op a (equivalent to scalar_op on the related lane) 4827 /// * d = extractelement <2 x i32> c, i32 0 4828 /// * store d 4829 /// Assuming both extractelement and store can be combine, we get rid of the 4830 /// transition. 4831 class VectorPromoteHelper { 4832 /// DataLayout associated with the current module. 4833 const DataLayout &DL; 4834 4835 /// Used to perform some checks on the legality of vector operations. 4836 const TargetLowering &TLI; 4837 4838 /// Used to estimated the cost of the promoted chain. 4839 const TargetTransformInfo &TTI; 4840 4841 /// The transition being moved downwards. 4842 Instruction *Transition; 4843 /// The sequence of instructions to be promoted. 4844 SmallVector<Instruction *, 4> InstsToBePromoted; 4845 /// Cost of combining a store and an extract. 4846 unsigned StoreExtractCombineCost; 4847 /// Instruction that will be combined with the transition. 4848 Instruction *CombineInst; 4849 4850 /// \brief The instruction that represents the current end of the transition. 4851 /// Since we are faking the promotion until we reach the end of the chain 4852 /// of computation, we need a way to get the current end of the transition. 4853 Instruction *getEndOfTransition() const { 4854 if (InstsToBePromoted.empty()) 4855 return Transition; 4856 return InstsToBePromoted.back(); 4857 } 4858 4859 /// \brief Return the index of the original value in the transition. 4860 /// E.g., for "extractelement <2 x i32> c, i32 1" the original value, 4861 /// c, is at index 0. 4862 unsigned getTransitionOriginalValueIdx() const { 4863 assert(isa<ExtractElementInst>(Transition) && 4864 "Other kind of transitions are not supported yet"); 4865 return 0; 4866 } 4867 4868 /// \brief Return the index of the index in the transition. 4869 /// E.g., for "extractelement <2 x i32> c, i32 0" the index 4870 /// is at index 1. 4871 unsigned getTransitionIdx() const { 4872 assert(isa<ExtractElementInst>(Transition) && 4873 "Other kind of transitions are not supported yet"); 4874 return 1; 4875 } 4876 4877 /// \brief Get the type of the transition. 4878 /// This is the type of the original value. 4879 /// E.g., for "extractelement <2 x i32> c, i32 1" the type of the 4880 /// transition is <2 x i32>. 4881 Type *getTransitionType() const { 4882 return Transition->getOperand(getTransitionOriginalValueIdx())->getType(); 4883 } 4884 4885 /// \brief Promote \p ToBePromoted by moving \p Def downward through. 4886 /// I.e., we have the following sequence: 4887 /// Def = Transition <ty1> a to <ty2> 4888 /// b = ToBePromoted <ty2> Def, ... 4889 /// => 4890 /// b = ToBePromoted <ty1> a, ... 4891 /// Def = Transition <ty1> ToBePromoted to <ty2> 4892 void promoteImpl(Instruction *ToBePromoted); 4893 4894 /// \brief Check whether or not it is profitable to promote all the 4895 /// instructions enqueued to be promoted. 4896 bool isProfitableToPromote() { 4897 Value *ValIdx = Transition->getOperand(getTransitionOriginalValueIdx()); 4898 unsigned Index = isa<ConstantInt>(ValIdx) 4899 ? cast<ConstantInt>(ValIdx)->getZExtValue() 4900 : -1; 4901 Type *PromotedType = getTransitionType(); 4902 4903 StoreInst *ST = cast<StoreInst>(CombineInst); 4904 unsigned AS = ST->getPointerAddressSpace(); 4905 unsigned Align = ST->getAlignment(); 4906 // Check if this store is supported. 4907 if (!TLI.allowsMisalignedMemoryAccesses( 4908 TLI.getValueType(DL, ST->getValueOperand()->getType()), AS, 4909 Align)) { 4910 // If this is not supported, there is no way we can combine 4911 // the extract with the store. 4912 return false; 4913 } 4914 4915 // The scalar chain of computation has to pay for the transition 4916 // scalar to vector. 4917 // The vector chain has to account for the combining cost. 4918 uint64_t ScalarCost = 4919 TTI.getVectorInstrCost(Transition->getOpcode(), PromotedType, Index); 4920 uint64_t VectorCost = StoreExtractCombineCost; 4921 for (const auto &Inst : InstsToBePromoted) { 4922 // Compute the cost. 4923 // By construction, all instructions being promoted are arithmetic ones. 4924 // Moreover, one argument is a constant that can be viewed as a splat 4925 // constant. 4926 Value *Arg0 = Inst->getOperand(0); 4927 bool IsArg0Constant = isa<UndefValue>(Arg0) || isa<ConstantInt>(Arg0) || 4928 isa<ConstantFP>(Arg0); 4929 TargetTransformInfo::OperandValueKind Arg0OVK = 4930 IsArg0Constant ? TargetTransformInfo::OK_UniformConstantValue 4931 : TargetTransformInfo::OK_AnyValue; 4932 TargetTransformInfo::OperandValueKind Arg1OVK = 4933 !IsArg0Constant ? TargetTransformInfo::OK_UniformConstantValue 4934 : TargetTransformInfo::OK_AnyValue; 4935 ScalarCost += TTI.getArithmeticInstrCost( 4936 Inst->getOpcode(), Inst->getType(), Arg0OVK, Arg1OVK); 4937 VectorCost += TTI.getArithmeticInstrCost(Inst->getOpcode(), PromotedType, 4938 Arg0OVK, Arg1OVK); 4939 } 4940 DEBUG(dbgs() << "Estimated cost of computation to be promoted:\nScalar: " 4941 << ScalarCost << "\nVector: " << VectorCost << '\n'); 4942 return ScalarCost > VectorCost; 4943 } 4944 4945 /// \brief Generate a constant vector with \p Val with the same 4946 /// number of elements as the transition. 4947 /// \p UseSplat defines whether or not \p Val should be replicated 4948 /// across the whole vector. 4949 /// In other words, if UseSplat == true, we generate <Val, Val, ..., Val>, 4950 /// otherwise we generate a vector with as many undef as possible: 4951 /// <undef, ..., undef, Val, undef, ..., undef> where \p Val is only 4952 /// used at the index of the extract. 4953 Value *getConstantVector(Constant *Val, bool UseSplat) const { 4954 unsigned ExtractIdx = UINT_MAX; 4955 if (!UseSplat) { 4956 // If we cannot determine where the constant must be, we have to 4957 // use a splat constant. 4958 Value *ValExtractIdx = Transition->getOperand(getTransitionIdx()); 4959 if (ConstantInt *CstVal = dyn_cast<ConstantInt>(ValExtractIdx)) 4960 ExtractIdx = CstVal->getSExtValue(); 4961 else 4962 UseSplat = true; 4963 } 4964 4965 unsigned End = getTransitionType()->getVectorNumElements(); 4966 if (UseSplat) 4967 return ConstantVector::getSplat(End, Val); 4968 4969 SmallVector<Constant *, 4> ConstVec; 4970 UndefValue *UndefVal = UndefValue::get(Val->getType()); 4971 for (unsigned Idx = 0; Idx != End; ++Idx) { 4972 if (Idx == ExtractIdx) 4973 ConstVec.push_back(Val); 4974 else 4975 ConstVec.push_back(UndefVal); 4976 } 4977 return ConstantVector::get(ConstVec); 4978 } 4979 4980 /// \brief Check if promoting to a vector type an operand at \p OperandIdx 4981 /// in \p Use can trigger undefined behavior. 4982 static bool canCauseUndefinedBehavior(const Instruction *Use, 4983 unsigned OperandIdx) { 4984 // This is not safe to introduce undef when the operand is on 4985 // the right hand side of a division-like instruction. 4986 if (OperandIdx != 1) 4987 return false; 4988 switch (Use->getOpcode()) { 4989 default: 4990 return false; 4991 case Instruction::SDiv: 4992 case Instruction::UDiv: 4993 case Instruction::SRem: 4994 case Instruction::URem: 4995 return true; 4996 case Instruction::FDiv: 4997 case Instruction::FRem: 4998 return !Use->hasNoNaNs(); 4999 } 5000 llvm_unreachable(nullptr); 5001 } 5002 5003 public: 5004 VectorPromoteHelper(const DataLayout &DL, const TargetLowering &TLI, 5005 const TargetTransformInfo &TTI, Instruction *Transition, 5006 unsigned CombineCost) 5007 : DL(DL), TLI(TLI), TTI(TTI), Transition(Transition), 5008 StoreExtractCombineCost(CombineCost), CombineInst(nullptr) { 5009 assert(Transition && "Do not know how to promote null"); 5010 } 5011 5012 /// \brief Check if we can promote \p ToBePromoted to \p Type. 5013 bool canPromote(const Instruction *ToBePromoted) const { 5014 // We could support CastInst too. 5015 return isa<BinaryOperator>(ToBePromoted); 5016 } 5017 5018 /// \brief Check if it is profitable to promote \p ToBePromoted 5019 /// by moving downward the transition through. 5020 bool shouldPromote(const Instruction *ToBePromoted) const { 5021 // Promote only if all the operands can be statically expanded. 5022 // Indeed, we do not want to introduce any new kind of transitions. 5023 for (const Use &U : ToBePromoted->operands()) { 5024 const Value *Val = U.get(); 5025 if (Val == getEndOfTransition()) { 5026 // If the use is a division and the transition is on the rhs, 5027 // we cannot promote the operation, otherwise we may create a 5028 // division by zero. 5029 if (canCauseUndefinedBehavior(ToBePromoted, U.getOperandNo())) 5030 return false; 5031 continue; 5032 } 5033 if (!isa<ConstantInt>(Val) && !isa<UndefValue>(Val) && 5034 !isa<ConstantFP>(Val)) 5035 return false; 5036 } 5037 // Check that the resulting operation is legal. 5038 int ISDOpcode = TLI.InstructionOpcodeToISD(ToBePromoted->getOpcode()); 5039 if (!ISDOpcode) 5040 return false; 5041 return StressStoreExtract || 5042 TLI.isOperationLegalOrCustom( 5043 ISDOpcode, TLI.getValueType(DL, getTransitionType(), true)); 5044 } 5045 5046 /// \brief Check whether or not \p Use can be combined 5047 /// with the transition. 5048 /// I.e., is it possible to do Use(Transition) => AnotherUse? 5049 bool canCombine(const Instruction *Use) { return isa<StoreInst>(Use); } 5050 5051 /// \brief Record \p ToBePromoted as part of the chain to be promoted. 5052 void enqueueForPromotion(Instruction *ToBePromoted) { 5053 InstsToBePromoted.push_back(ToBePromoted); 5054 } 5055 5056 /// \brief Set the instruction that will be combined with the transition. 5057 void recordCombineInstruction(Instruction *ToBeCombined) { 5058 assert(canCombine(ToBeCombined) && "Unsupported instruction to combine"); 5059 CombineInst = ToBeCombined; 5060 } 5061 5062 /// \brief Promote all the instructions enqueued for promotion if it is 5063 /// is profitable. 5064 /// \return True if the promotion happened, false otherwise. 5065 bool promote() { 5066 // Check if there is something to promote. 5067 // Right now, if we do not have anything to combine with, 5068 // we assume the promotion is not profitable. 5069 if (InstsToBePromoted.empty() || !CombineInst) 5070 return false; 5071 5072 // Check cost. 5073 if (!StressStoreExtract && !isProfitableToPromote()) 5074 return false; 5075 5076 // Promote. 5077 for (auto &ToBePromoted : InstsToBePromoted) 5078 promoteImpl(ToBePromoted); 5079 InstsToBePromoted.clear(); 5080 return true; 5081 } 5082 }; 5083 } // End of anonymous namespace. 5084 5085 void VectorPromoteHelper::promoteImpl(Instruction *ToBePromoted) { 5086 // At this point, we know that all the operands of ToBePromoted but Def 5087 // can be statically promoted. 5088 // For Def, we need to use its parameter in ToBePromoted: 5089 // b = ToBePromoted ty1 a 5090 // Def = Transition ty1 b to ty2 5091 // Move the transition down. 5092 // 1. Replace all uses of the promoted operation by the transition. 5093 // = ... b => = ... Def. 5094 assert(ToBePromoted->getType() == Transition->getType() && 5095 "The type of the result of the transition does not match " 5096 "the final type"); 5097 ToBePromoted->replaceAllUsesWith(Transition); 5098 // 2. Update the type of the uses. 5099 // b = ToBePromoted ty2 Def => b = ToBePromoted ty1 Def. 5100 Type *TransitionTy = getTransitionType(); 5101 ToBePromoted->mutateType(TransitionTy); 5102 // 3. Update all the operands of the promoted operation with promoted 5103 // operands. 5104 // b = ToBePromoted ty1 Def => b = ToBePromoted ty1 a. 5105 for (Use &U : ToBePromoted->operands()) { 5106 Value *Val = U.get(); 5107 Value *NewVal = nullptr; 5108 if (Val == Transition) 5109 NewVal = Transition->getOperand(getTransitionOriginalValueIdx()); 5110 else if (isa<UndefValue>(Val) || isa<ConstantInt>(Val) || 5111 isa<ConstantFP>(Val)) { 5112 // Use a splat constant if it is not safe to use undef. 5113 NewVal = getConstantVector( 5114 cast<Constant>(Val), 5115 isa<UndefValue>(Val) || 5116 canCauseUndefinedBehavior(ToBePromoted, U.getOperandNo())); 5117 } else 5118 llvm_unreachable("Did you modified shouldPromote and forgot to update " 5119 "this?"); 5120 ToBePromoted->setOperand(U.getOperandNo(), NewVal); 5121 } 5122 Transition->removeFromParent(); 5123 Transition->insertAfter(ToBePromoted); 5124 Transition->setOperand(getTransitionOriginalValueIdx(), ToBePromoted); 5125 } 5126 5127 /// Some targets can do store(extractelement) with one instruction. 5128 /// Try to push the extractelement towards the stores when the target 5129 /// has this feature and this is profitable. 5130 bool CodeGenPrepare::optimizeExtractElementInst(Instruction *Inst) { 5131 unsigned CombineCost = UINT_MAX; 5132 if (DisableStoreExtract || !TLI || 5133 (!StressStoreExtract && 5134 !TLI->canCombineStoreAndExtract(Inst->getOperand(0)->getType(), 5135 Inst->getOperand(1), CombineCost))) 5136 return false; 5137 5138 // At this point we know that Inst is a vector to scalar transition. 5139 // Try to move it down the def-use chain, until: 5140 // - We can combine the transition with its single use 5141 // => we got rid of the transition. 5142 // - We escape the current basic block 5143 // => we would need to check that we are moving it at a cheaper place and 5144 // we do not do that for now. 5145 BasicBlock *Parent = Inst->getParent(); 5146 DEBUG(dbgs() << "Found an interesting transition: " << *Inst << '\n'); 5147 VectorPromoteHelper VPH(*DL, *TLI, *TTI, Inst, CombineCost); 5148 // If the transition has more than one use, assume this is not going to be 5149 // beneficial. 5150 while (Inst->hasOneUse()) { 5151 Instruction *ToBePromoted = cast<Instruction>(*Inst->user_begin()); 5152 DEBUG(dbgs() << "Use: " << *ToBePromoted << '\n'); 5153 5154 if (ToBePromoted->getParent() != Parent) { 5155 DEBUG(dbgs() << "Instruction to promote is in a different block (" 5156 << ToBePromoted->getParent()->getName() 5157 << ") than the transition (" << Parent->getName() << ").\n"); 5158 return false; 5159 } 5160 5161 if (VPH.canCombine(ToBePromoted)) { 5162 DEBUG(dbgs() << "Assume " << *Inst << '\n' 5163 << "will be combined with: " << *ToBePromoted << '\n'); 5164 VPH.recordCombineInstruction(ToBePromoted); 5165 bool Changed = VPH.promote(); 5166 NumStoreExtractExposed += Changed; 5167 return Changed; 5168 } 5169 5170 DEBUG(dbgs() << "Try promoting.\n"); 5171 if (!VPH.canPromote(ToBePromoted) || !VPH.shouldPromote(ToBePromoted)) 5172 return false; 5173 5174 DEBUG(dbgs() << "Promoting is possible... Enqueue for promotion!\n"); 5175 5176 VPH.enqueueForPromotion(ToBePromoted); 5177 Inst = ToBePromoted; 5178 } 5179 return false; 5180 } 5181 5182 bool CodeGenPrepare::optimizeInst(Instruction *I, bool& ModifiedDT) { 5183 // Bail out if we inserted the instruction to prevent optimizations from 5184 // stepping on each other's toes. 5185 if (InsertedInsts.count(I)) 5186 return false; 5187 5188 if (PHINode *P = dyn_cast<PHINode>(I)) { 5189 // It is possible for very late stage optimizations (such as SimplifyCFG) 5190 // to introduce PHI nodes too late to be cleaned up. If we detect such a 5191 // trivial PHI, go ahead and zap it here. 5192 if (Value *V = SimplifyInstruction(P, *DL, TLInfo, nullptr)) { 5193 P->replaceAllUsesWith(V); 5194 P->eraseFromParent(); 5195 ++NumPHIsElim; 5196 return true; 5197 } 5198 return false; 5199 } 5200 5201 if (CastInst *CI = dyn_cast<CastInst>(I)) { 5202 // If the source of the cast is a constant, then this should have 5203 // already been constant folded. The only reason NOT to constant fold 5204 // it is if something (e.g. LSR) was careful to place the constant 5205 // evaluation in a block other than then one that uses it (e.g. to hoist 5206 // the address of globals out of a loop). If this is the case, we don't 5207 // want to forward-subst the cast. 5208 if (isa<Constant>(CI->getOperand(0))) 5209 return false; 5210 5211 if (TLI && OptimizeNoopCopyExpression(CI, *TLI, *DL)) 5212 return true; 5213 5214 if (isa<ZExtInst>(I) || isa<SExtInst>(I)) { 5215 /// Sink a zext or sext into its user blocks if the target type doesn't 5216 /// fit in one register 5217 if (TLI && 5218 TLI->getTypeAction(CI->getContext(), 5219 TLI->getValueType(*DL, CI->getType())) == 5220 TargetLowering::TypeExpandInteger) { 5221 return SinkCast(CI); 5222 } else { 5223 bool MadeChange = moveExtToFormExtLoad(I); 5224 return MadeChange | optimizeExtUses(I); 5225 } 5226 } 5227 return false; 5228 } 5229 5230 if (CmpInst *CI = dyn_cast<CmpInst>(I)) 5231 if (!TLI || !TLI->hasMultipleConditionRegisters()) 5232 return OptimizeCmpExpression(CI, TLI); 5233 5234 if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 5235 stripInvariantGroupMetadata(*LI); 5236 if (TLI) { 5237 bool Modified = optimizeLoadExt(LI); 5238 unsigned AS = LI->getPointerAddressSpace(); 5239 Modified |= optimizeMemoryInst(I, I->getOperand(0), LI->getType(), AS); 5240 return Modified; 5241 } 5242 return false; 5243 } 5244 5245 if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 5246 stripInvariantGroupMetadata(*SI); 5247 if (TLI) { 5248 unsigned AS = SI->getPointerAddressSpace(); 5249 return optimizeMemoryInst(I, SI->getOperand(1), 5250 SI->getOperand(0)->getType(), AS); 5251 } 5252 return false; 5253 } 5254 5255 BinaryOperator *BinOp = dyn_cast<BinaryOperator>(I); 5256 5257 if (BinOp && (BinOp->getOpcode() == Instruction::AShr || 5258 BinOp->getOpcode() == Instruction::LShr)) { 5259 ConstantInt *CI = dyn_cast<ConstantInt>(BinOp->getOperand(1)); 5260 if (TLI && CI && TLI->hasExtractBitsInsn()) 5261 return OptimizeExtractBits(BinOp, CI, *TLI, *DL); 5262 5263 return false; 5264 } 5265 5266 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 5267 if (GEPI->hasAllZeroIndices()) { 5268 /// The GEP operand must be a pointer, so must its result -> BitCast 5269 Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(), 5270 GEPI->getName(), GEPI); 5271 GEPI->replaceAllUsesWith(NC); 5272 GEPI->eraseFromParent(); 5273 ++NumGEPsElim; 5274 optimizeInst(NC, ModifiedDT); 5275 return true; 5276 } 5277 return false; 5278 } 5279 5280 if (CallInst *CI = dyn_cast<CallInst>(I)) 5281 return optimizeCallInst(CI, ModifiedDT); 5282 5283 if (SelectInst *SI = dyn_cast<SelectInst>(I)) 5284 return optimizeSelectInst(SI); 5285 5286 if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(I)) 5287 return optimizeShuffleVectorInst(SVI); 5288 5289 if (auto *Switch = dyn_cast<SwitchInst>(I)) 5290 return optimizeSwitchInst(Switch); 5291 5292 if (isa<ExtractElementInst>(I)) 5293 return optimizeExtractElementInst(I); 5294 5295 return false; 5296 } 5297 5298 /// Given an OR instruction, check to see if this is a bitreverse 5299 /// idiom. If so, insert the new intrinsic and return true. 5300 static bool makeBitReverse(Instruction &I, const DataLayout &DL, 5301 const TargetLowering &TLI) { 5302 if (!I.getType()->isIntegerTy() || 5303 !TLI.isOperationLegalOrCustom(ISD::BITREVERSE, 5304 TLI.getValueType(DL, I.getType(), true))) 5305 return false; 5306 5307 SmallVector<Instruction*, 4> Insts; 5308 if (!recognizeBSwapOrBitReverseIdiom(&I, false, true, Insts)) 5309 return false; 5310 Instruction *LastInst = Insts.back(); 5311 I.replaceAllUsesWith(LastInst); 5312 RecursivelyDeleteTriviallyDeadInstructions(&I); 5313 return true; 5314 } 5315 5316 // In this pass we look for GEP and cast instructions that are used 5317 // across basic blocks and rewrite them to improve basic-block-at-a-time 5318 // selection. 5319 bool CodeGenPrepare::optimizeBlock(BasicBlock &BB, bool& ModifiedDT) { 5320 SunkAddrs.clear(); 5321 bool MadeChange = false; 5322 5323 CurInstIterator = BB.begin(); 5324 while (CurInstIterator != BB.end()) { 5325 MadeChange |= optimizeInst(&*CurInstIterator++, ModifiedDT); 5326 if (ModifiedDT) 5327 return true; 5328 } 5329 5330 bool MadeBitReverse = true; 5331 while (TLI && MadeBitReverse) { 5332 MadeBitReverse = false; 5333 for (auto &I : reverse(BB)) { 5334 if (makeBitReverse(I, *DL, *TLI)) { 5335 MadeBitReverse = MadeChange = true; 5336 ModifiedDT = true; 5337 break; 5338 } 5339 } 5340 } 5341 MadeChange |= dupRetToEnableTailCallOpts(&BB); 5342 5343 return MadeChange; 5344 } 5345 5346 // llvm.dbg.value is far away from the value then iSel may not be able 5347 // handle it properly. iSel will drop llvm.dbg.value if it can not 5348 // find a node corresponding to the value. 5349 bool CodeGenPrepare::placeDbgValues(Function &F) { 5350 bool MadeChange = false; 5351 for (BasicBlock &BB : F) { 5352 Instruction *PrevNonDbgInst = nullptr; 5353 for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE;) { 5354 Instruction *Insn = &*BI++; 5355 DbgValueInst *DVI = dyn_cast<DbgValueInst>(Insn); 5356 // Leave dbg.values that refer to an alloca alone. These 5357 // instrinsics describe the address of a variable (= the alloca) 5358 // being taken. They should not be moved next to the alloca 5359 // (and to the beginning of the scope), but rather stay close to 5360 // where said address is used. 5361 if (!DVI || (DVI->getValue() && isa<AllocaInst>(DVI->getValue()))) { 5362 PrevNonDbgInst = Insn; 5363 continue; 5364 } 5365 5366 Instruction *VI = dyn_cast_or_null<Instruction>(DVI->getValue()); 5367 if (VI && VI != PrevNonDbgInst && !VI->isTerminator()) { 5368 // If VI is a phi in a block with an EHPad terminator, we can't insert 5369 // after it. 5370 if (isa<PHINode>(VI) && VI->getParent()->getTerminator()->isEHPad()) 5371 continue; 5372 DEBUG(dbgs() << "Moving Debug Value before :\n" << *DVI << ' ' << *VI); 5373 DVI->removeFromParent(); 5374 if (isa<PHINode>(VI)) 5375 DVI->insertBefore(&*VI->getParent()->getFirstInsertionPt()); 5376 else 5377 DVI->insertAfter(VI); 5378 MadeChange = true; 5379 ++NumDbgValueMoved; 5380 } 5381 } 5382 } 5383 return MadeChange; 5384 } 5385 5386 // If there is a sequence that branches based on comparing a single bit 5387 // against zero that can be combined into a single instruction, and the 5388 // target supports folding these into a single instruction, sink the 5389 // mask and compare into the branch uses. Do this before OptimizeBlock -> 5390 // OptimizeInst -> OptimizeCmpExpression, which perturbs the pattern being 5391 // searched for. 5392 bool CodeGenPrepare::sinkAndCmp(Function &F) { 5393 if (!EnableAndCmpSinking) 5394 return false; 5395 if (!TLI || !TLI->isMaskAndBranchFoldingLegal()) 5396 return false; 5397 bool MadeChange = false; 5398 for (BasicBlock &BB : F) { 5399 // Does this BB end with the following? 5400 // %andVal = and %val, #single-bit-set 5401 // %icmpVal = icmp %andResult, 0 5402 // br i1 %cmpVal label %dest1, label %dest2" 5403 BranchInst *Brcc = dyn_cast<BranchInst>(BB.getTerminator()); 5404 if (!Brcc || !Brcc->isConditional()) 5405 continue; 5406 ICmpInst *Cmp = dyn_cast<ICmpInst>(Brcc->getOperand(0)); 5407 if (!Cmp || Cmp->getParent() != &BB) 5408 continue; 5409 ConstantInt *Zero = dyn_cast<ConstantInt>(Cmp->getOperand(1)); 5410 if (!Zero || !Zero->isZero()) 5411 continue; 5412 Instruction *And = dyn_cast<Instruction>(Cmp->getOperand(0)); 5413 if (!And || And->getOpcode() != Instruction::And || And->getParent() != &BB) 5414 continue; 5415 ConstantInt* Mask = dyn_cast<ConstantInt>(And->getOperand(1)); 5416 if (!Mask || !Mask->getUniqueInteger().isPowerOf2()) 5417 continue; 5418 DEBUG(dbgs() << "found and; icmp ?,0; brcc\n"); DEBUG(BB.dump()); 5419 5420 // Push the "and; icmp" for any users that are conditional branches. 5421 // Since there can only be one branch use per BB, we don't need to keep 5422 // track of which BBs we insert into. 5423 for (Use &TheUse : Cmp->uses()) { 5424 // Find brcc use. 5425 BranchInst *BrccUser = dyn_cast<BranchInst>(TheUse); 5426 if (!BrccUser || !BrccUser->isConditional()) 5427 continue; 5428 BasicBlock *UserBB = BrccUser->getParent(); 5429 if (UserBB == &BB) continue; 5430 DEBUG(dbgs() << "found Brcc use\n"); 5431 5432 // Sink the "and; icmp" to use. 5433 MadeChange = true; 5434 BinaryOperator *NewAnd = 5435 BinaryOperator::CreateAnd(And->getOperand(0), And->getOperand(1), "", 5436 BrccUser); 5437 CmpInst *NewCmp = 5438 CmpInst::Create(Cmp->getOpcode(), Cmp->getPredicate(), NewAnd, Zero, 5439 "", BrccUser); 5440 TheUse = NewCmp; 5441 ++NumAndCmpsMoved; 5442 DEBUG(BrccUser->getParent()->dump()); 5443 } 5444 } 5445 return MadeChange; 5446 } 5447 5448 /// \brief Scale down both weights to fit into uint32_t. 5449 static void scaleWeights(uint64_t &NewTrue, uint64_t &NewFalse) { 5450 uint64_t NewMax = (NewTrue > NewFalse) ? NewTrue : NewFalse; 5451 uint32_t Scale = (NewMax / UINT32_MAX) + 1; 5452 NewTrue = NewTrue / Scale; 5453 NewFalse = NewFalse / Scale; 5454 } 5455 5456 /// \brief Some targets prefer to split a conditional branch like: 5457 /// \code 5458 /// %0 = icmp ne i32 %a, 0 5459 /// %1 = icmp ne i32 %b, 0 5460 /// %or.cond = or i1 %0, %1 5461 /// br i1 %or.cond, label %TrueBB, label %FalseBB 5462 /// \endcode 5463 /// into multiple branch instructions like: 5464 /// \code 5465 /// bb1: 5466 /// %0 = icmp ne i32 %a, 0 5467 /// br i1 %0, label %TrueBB, label %bb2 5468 /// bb2: 5469 /// %1 = icmp ne i32 %b, 0 5470 /// br i1 %1, label %TrueBB, label %FalseBB 5471 /// \endcode 5472 /// This usually allows instruction selection to do even further optimizations 5473 /// and combine the compare with the branch instruction. Currently this is 5474 /// applied for targets which have "cheap" jump instructions. 5475 /// 5476 /// FIXME: Remove the (equivalent?) implementation in SelectionDAG. 5477 /// 5478 bool CodeGenPrepare::splitBranchCondition(Function &F) { 5479 if (!TM || !TM->Options.EnableFastISel || !TLI || TLI->isJumpExpensive()) 5480 return false; 5481 5482 bool MadeChange = false; 5483 for (auto &BB : F) { 5484 // Does this BB end with the following? 5485 // %cond1 = icmp|fcmp|binary instruction ... 5486 // %cond2 = icmp|fcmp|binary instruction ... 5487 // %cond.or = or|and i1 %cond1, cond2 5488 // br i1 %cond.or label %dest1, label %dest2" 5489 BinaryOperator *LogicOp; 5490 BasicBlock *TBB, *FBB; 5491 if (!match(BB.getTerminator(), m_Br(m_OneUse(m_BinOp(LogicOp)), TBB, FBB))) 5492 continue; 5493 5494 auto *Br1 = cast<BranchInst>(BB.getTerminator()); 5495 if (Br1->getMetadata(LLVMContext::MD_unpredictable)) 5496 continue; 5497 5498 unsigned Opc; 5499 Value *Cond1, *Cond2; 5500 if (match(LogicOp, m_And(m_OneUse(m_Value(Cond1)), 5501 m_OneUse(m_Value(Cond2))))) 5502 Opc = Instruction::And; 5503 else if (match(LogicOp, m_Or(m_OneUse(m_Value(Cond1)), 5504 m_OneUse(m_Value(Cond2))))) 5505 Opc = Instruction::Or; 5506 else 5507 continue; 5508 5509 if (!match(Cond1, m_CombineOr(m_Cmp(), m_BinOp())) || 5510 !match(Cond2, m_CombineOr(m_Cmp(), m_BinOp())) ) 5511 continue; 5512 5513 DEBUG(dbgs() << "Before branch condition splitting\n"; BB.dump()); 5514 5515 // Create a new BB. 5516 auto TmpBB = 5517 BasicBlock::Create(BB.getContext(), BB.getName() + ".cond.split", 5518 BB.getParent(), BB.getNextNode()); 5519 5520 // Update original basic block by using the first condition directly by the 5521 // branch instruction and removing the no longer needed and/or instruction. 5522 Br1->setCondition(Cond1); 5523 LogicOp->eraseFromParent(); 5524 5525 // Depending on the conditon we have to either replace the true or the false 5526 // successor of the original branch instruction. 5527 if (Opc == Instruction::And) 5528 Br1->setSuccessor(0, TmpBB); 5529 else 5530 Br1->setSuccessor(1, TmpBB); 5531 5532 // Fill in the new basic block. 5533 auto *Br2 = IRBuilder<>(TmpBB).CreateCondBr(Cond2, TBB, FBB); 5534 if (auto *I = dyn_cast<Instruction>(Cond2)) { 5535 I->removeFromParent(); 5536 I->insertBefore(Br2); 5537 } 5538 5539 // Update PHI nodes in both successors. The original BB needs to be 5540 // replaced in one succesor's PHI nodes, because the branch comes now from 5541 // the newly generated BB (NewBB). In the other successor we need to add one 5542 // incoming edge to the PHI nodes, because both branch instructions target 5543 // now the same successor. Depending on the original branch condition 5544 // (and/or) we have to swap the successors (TrueDest, FalseDest), so that 5545 // we perfrom the correct update for the PHI nodes. 5546 // This doesn't change the successor order of the just created branch 5547 // instruction (or any other instruction). 5548 if (Opc == Instruction::Or) 5549 std::swap(TBB, FBB); 5550 5551 // Replace the old BB with the new BB. 5552 for (auto &I : *TBB) { 5553 PHINode *PN = dyn_cast<PHINode>(&I); 5554 if (!PN) 5555 break; 5556 int i; 5557 while ((i = PN->getBasicBlockIndex(&BB)) >= 0) 5558 PN->setIncomingBlock(i, TmpBB); 5559 } 5560 5561 // Add another incoming edge form the new BB. 5562 for (auto &I : *FBB) { 5563 PHINode *PN = dyn_cast<PHINode>(&I); 5564 if (!PN) 5565 break; 5566 auto *Val = PN->getIncomingValueForBlock(&BB); 5567 PN->addIncoming(Val, TmpBB); 5568 } 5569 5570 // Update the branch weights (from SelectionDAGBuilder:: 5571 // FindMergedConditions). 5572 if (Opc == Instruction::Or) { 5573 // Codegen X | Y as: 5574 // BB1: 5575 // jmp_if_X TBB 5576 // jmp TmpBB 5577 // TmpBB: 5578 // jmp_if_Y TBB 5579 // jmp FBB 5580 // 5581 5582 // We have flexibility in setting Prob for BB1 and Prob for NewBB. 5583 // The requirement is that 5584 // TrueProb for BB1 + (FalseProb for BB1 * TrueProb for TmpBB) 5585 // = TrueProb for orignal BB. 5586 // Assuming the orignal weights are A and B, one choice is to set BB1's 5587 // weights to A and A+2B, and set TmpBB's weights to A and 2B. This choice 5588 // assumes that 5589 // TrueProb for BB1 == FalseProb for BB1 * TrueProb for TmpBB. 5590 // Another choice is to assume TrueProb for BB1 equals to TrueProb for 5591 // TmpBB, but the math is more complicated. 5592 uint64_t TrueWeight, FalseWeight; 5593 if (Br1->extractProfMetadata(TrueWeight, FalseWeight)) { 5594 uint64_t NewTrueWeight = TrueWeight; 5595 uint64_t NewFalseWeight = TrueWeight + 2 * FalseWeight; 5596 scaleWeights(NewTrueWeight, NewFalseWeight); 5597 Br1->setMetadata(LLVMContext::MD_prof, MDBuilder(Br1->getContext()) 5598 .createBranchWeights(TrueWeight, FalseWeight)); 5599 5600 NewTrueWeight = TrueWeight; 5601 NewFalseWeight = 2 * FalseWeight; 5602 scaleWeights(NewTrueWeight, NewFalseWeight); 5603 Br2->setMetadata(LLVMContext::MD_prof, MDBuilder(Br2->getContext()) 5604 .createBranchWeights(TrueWeight, FalseWeight)); 5605 } 5606 } else { 5607 // Codegen X & Y as: 5608 // BB1: 5609 // jmp_if_X TmpBB 5610 // jmp FBB 5611 // TmpBB: 5612 // jmp_if_Y TBB 5613 // jmp FBB 5614 // 5615 // This requires creation of TmpBB after CurBB. 5616 5617 // We have flexibility in setting Prob for BB1 and Prob for TmpBB. 5618 // The requirement is that 5619 // FalseProb for BB1 + (TrueProb for BB1 * FalseProb for TmpBB) 5620 // = FalseProb for orignal BB. 5621 // Assuming the orignal weights are A and B, one choice is to set BB1's 5622 // weights to 2A+B and B, and set TmpBB's weights to 2A and B. This choice 5623 // assumes that 5624 // FalseProb for BB1 == TrueProb for BB1 * FalseProb for TmpBB. 5625 uint64_t TrueWeight, FalseWeight; 5626 if (Br1->extractProfMetadata(TrueWeight, FalseWeight)) { 5627 uint64_t NewTrueWeight = 2 * TrueWeight + FalseWeight; 5628 uint64_t NewFalseWeight = FalseWeight; 5629 scaleWeights(NewTrueWeight, NewFalseWeight); 5630 Br1->setMetadata(LLVMContext::MD_prof, MDBuilder(Br1->getContext()) 5631 .createBranchWeights(TrueWeight, FalseWeight)); 5632 5633 NewTrueWeight = 2 * TrueWeight; 5634 NewFalseWeight = FalseWeight; 5635 scaleWeights(NewTrueWeight, NewFalseWeight); 5636 Br2->setMetadata(LLVMContext::MD_prof, MDBuilder(Br2->getContext()) 5637 .createBranchWeights(TrueWeight, FalseWeight)); 5638 } 5639 } 5640 5641 // Note: No point in getting fancy here, since the DT info is never 5642 // available to CodeGenPrepare. 5643 ModifiedDT = true; 5644 5645 MadeChange = true; 5646 5647 DEBUG(dbgs() << "After branch condition splitting\n"; BB.dump(); 5648 TmpBB->dump()); 5649 } 5650 return MadeChange; 5651 } 5652 5653 void CodeGenPrepare::stripInvariantGroupMetadata(Instruction &I) { 5654 if (auto *InvariantMD = I.getMetadata(LLVMContext::MD_invariant_group)) 5655 I.dropUnknownNonDebugMetadata(InvariantMD->getMetadataID()); 5656 } 5657