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