1 //===- Local.cpp - Functions to perform local transformations -------------===// 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 family of functions perform various local transformations to the 11 // program. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "llvm/Transforms/Utils/Local.h" 16 #include "llvm/ADT/APInt.h" 17 #include "llvm/ADT/DenseMap.h" 18 #include "llvm/ADT/DenseMapInfo.h" 19 #include "llvm/ADT/DenseSet.h" 20 #include "llvm/ADT/Hashing.h" 21 #include "llvm/ADT/None.h" 22 #include "llvm/ADT/Optional.h" 23 #include "llvm/ADT/STLExtras.h" 24 #include "llvm/ADT/SetVector.h" 25 #include "llvm/ADT/SmallPtrSet.h" 26 #include "llvm/ADT/SmallVector.h" 27 #include "llvm/ADT/Statistic.h" 28 #include "llvm/ADT/TinyPtrVector.h" 29 #include "llvm/Analysis/ConstantFolding.h" 30 #include "llvm/Analysis/EHPersonalities.h" 31 #include "llvm/Analysis/InstructionSimplify.h" 32 #include "llvm/Analysis/LazyValueInfo.h" 33 #include "llvm/Analysis/MemoryBuiltins.h" 34 #include "llvm/Analysis/TargetLibraryInfo.h" 35 #include "llvm/Analysis/ValueTracking.h" 36 #include "llvm/BinaryFormat/Dwarf.h" 37 #include "llvm/IR/Argument.h" 38 #include "llvm/IR/Attributes.h" 39 #include "llvm/IR/BasicBlock.h" 40 #include "llvm/IR/CFG.h" 41 #include "llvm/IR/CallSite.h" 42 #include "llvm/IR/Constant.h" 43 #include "llvm/IR/ConstantRange.h" 44 #include "llvm/IR/Constants.h" 45 #include "llvm/IR/DIBuilder.h" 46 #include "llvm/IR/DataLayout.h" 47 #include "llvm/IR/DebugInfoMetadata.h" 48 #include "llvm/IR/DebugLoc.h" 49 #include "llvm/IR/DerivedTypes.h" 50 #include "llvm/IR/Dominators.h" 51 #include "llvm/IR/Function.h" 52 #include "llvm/IR/GetElementPtrTypeIterator.h" 53 #include "llvm/IR/GlobalObject.h" 54 #include "llvm/IR/IRBuilder.h" 55 #include "llvm/IR/InstrTypes.h" 56 #include "llvm/IR/Instruction.h" 57 #include "llvm/IR/Instructions.h" 58 #include "llvm/IR/IntrinsicInst.h" 59 #include "llvm/IR/Intrinsics.h" 60 #include "llvm/IR/LLVMContext.h" 61 #include "llvm/IR/MDBuilder.h" 62 #include "llvm/IR/Metadata.h" 63 #include "llvm/IR/Module.h" 64 #include "llvm/IR/Operator.h" 65 #include "llvm/IR/PatternMatch.h" 66 #include "llvm/IR/Type.h" 67 #include "llvm/IR/Use.h" 68 #include "llvm/IR/User.h" 69 #include "llvm/IR/Value.h" 70 #include "llvm/IR/ValueHandle.h" 71 #include "llvm/Support/Casting.h" 72 #include "llvm/Support/Debug.h" 73 #include "llvm/Support/ErrorHandling.h" 74 #include "llvm/Support/KnownBits.h" 75 #include "llvm/Support/raw_ostream.h" 76 #include "llvm/Transforms/Utils/ValueMapper.h" 77 #include <algorithm> 78 #include <cassert> 79 #include <climits> 80 #include <cstdint> 81 #include <iterator> 82 #include <map> 83 #include <utility> 84 85 using namespace llvm; 86 using namespace llvm::PatternMatch; 87 88 #define DEBUG_TYPE "local" 89 90 STATISTIC(NumRemoved, "Number of unreachable basic blocks removed"); 91 92 //===----------------------------------------------------------------------===// 93 // Local constant propagation. 94 // 95 96 /// ConstantFoldTerminator - If a terminator instruction is predicated on a 97 /// constant value, convert it into an unconditional branch to the constant 98 /// destination. This is a nontrivial operation because the successors of this 99 /// basic block must have their PHI nodes updated. 100 /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch 101 /// conditions and indirectbr addresses this might make dead if 102 /// DeleteDeadConditions is true. 103 bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, 104 const TargetLibraryInfo *TLI, 105 DeferredDominance *DDT) { 106 TerminatorInst *T = BB->getTerminator(); 107 IRBuilder<> Builder(T); 108 109 // Branch - See if we are conditional jumping on constant 110 if (auto *BI = dyn_cast<BranchInst>(T)) { 111 if (BI->isUnconditional()) return false; // Can't optimize uncond branch 112 BasicBlock *Dest1 = BI->getSuccessor(0); 113 BasicBlock *Dest2 = BI->getSuccessor(1); 114 115 if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition())) { 116 // Are we branching on constant? 117 // YES. Change to unconditional branch... 118 BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2; 119 BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1; 120 121 // Let the basic block know that we are letting go of it. Based on this, 122 // it will adjust it's PHI nodes. 123 OldDest->removePredecessor(BB); 124 125 // Replace the conditional branch with an unconditional one. 126 Builder.CreateBr(Destination); 127 BI->eraseFromParent(); 128 if (DDT) 129 DDT->deleteEdge(BB, OldDest); 130 return true; 131 } 132 133 if (Dest2 == Dest1) { // Conditional branch to same location? 134 // This branch matches something like this: 135 // br bool %cond, label %Dest, label %Dest 136 // and changes it into: br label %Dest 137 138 // Let the basic block know that we are letting go of one copy of it. 139 assert(BI->getParent() && "Terminator not inserted in block!"); 140 Dest1->removePredecessor(BI->getParent()); 141 142 // Replace the conditional branch with an unconditional one. 143 Builder.CreateBr(Dest1); 144 Value *Cond = BI->getCondition(); 145 BI->eraseFromParent(); 146 if (DeleteDeadConditions) 147 RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI); 148 return true; 149 } 150 return false; 151 } 152 153 if (auto *SI = dyn_cast<SwitchInst>(T)) { 154 // If we are switching on a constant, we can convert the switch to an 155 // unconditional branch. 156 auto *CI = dyn_cast<ConstantInt>(SI->getCondition()); 157 BasicBlock *DefaultDest = SI->getDefaultDest(); 158 BasicBlock *TheOnlyDest = DefaultDest; 159 160 // If the default is unreachable, ignore it when searching for TheOnlyDest. 161 if (isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg()) && 162 SI->getNumCases() > 0) { 163 TheOnlyDest = SI->case_begin()->getCaseSuccessor(); 164 } 165 166 // Figure out which case it goes to. 167 for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) { 168 // Found case matching a constant operand? 169 if (i->getCaseValue() == CI) { 170 TheOnlyDest = i->getCaseSuccessor(); 171 break; 172 } 173 174 // Check to see if this branch is going to the same place as the default 175 // dest. If so, eliminate it as an explicit compare. 176 if (i->getCaseSuccessor() == DefaultDest) { 177 MDNode *MD = SI->getMetadata(LLVMContext::MD_prof); 178 unsigned NCases = SI->getNumCases(); 179 // Fold the case metadata into the default if there will be any branches 180 // left, unless the metadata doesn't match the switch. 181 if (NCases > 1 && MD && MD->getNumOperands() == 2 + NCases) { 182 // Collect branch weights into a vector. 183 SmallVector<uint32_t, 8> Weights; 184 for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e; 185 ++MD_i) { 186 auto *CI = mdconst::extract<ConstantInt>(MD->getOperand(MD_i)); 187 Weights.push_back(CI->getValue().getZExtValue()); 188 } 189 // Merge weight of this case to the default weight. 190 unsigned idx = i->getCaseIndex(); 191 Weights[0] += Weights[idx+1]; 192 // Remove weight for this case. 193 std::swap(Weights[idx+1], Weights.back()); 194 Weights.pop_back(); 195 SI->setMetadata(LLVMContext::MD_prof, 196 MDBuilder(BB->getContext()). 197 createBranchWeights(Weights)); 198 } 199 // Remove this entry. 200 BasicBlock *ParentBB = SI->getParent(); 201 DefaultDest->removePredecessor(ParentBB); 202 i = SI->removeCase(i); 203 e = SI->case_end(); 204 if (DDT) 205 DDT->deleteEdge(ParentBB, DefaultDest); 206 continue; 207 } 208 209 // Otherwise, check to see if the switch only branches to one destination. 210 // We do this by reseting "TheOnlyDest" to null when we find two non-equal 211 // destinations. 212 if (i->getCaseSuccessor() != TheOnlyDest) 213 TheOnlyDest = nullptr; 214 215 // Increment this iterator as we haven't removed the case. 216 ++i; 217 } 218 219 if (CI && !TheOnlyDest) { 220 // Branching on a constant, but not any of the cases, go to the default 221 // successor. 222 TheOnlyDest = SI->getDefaultDest(); 223 } 224 225 // If we found a single destination that we can fold the switch into, do so 226 // now. 227 if (TheOnlyDest) { 228 // Insert the new branch. 229 Builder.CreateBr(TheOnlyDest); 230 BasicBlock *BB = SI->getParent(); 231 std::vector <DominatorTree::UpdateType> Updates; 232 if (DDT) 233 Updates.reserve(SI->getNumSuccessors() - 1); 234 235 // Remove entries from PHI nodes which we no longer branch to... 236 for (BasicBlock *Succ : SI->successors()) { 237 // Found case matching a constant operand? 238 if (Succ == TheOnlyDest) { 239 TheOnlyDest = nullptr; // Don't modify the first branch to TheOnlyDest 240 } else { 241 Succ->removePredecessor(BB); 242 if (DDT) 243 Updates.push_back({DominatorTree::Delete, BB, Succ}); 244 } 245 } 246 247 // Delete the old switch. 248 Value *Cond = SI->getCondition(); 249 SI->eraseFromParent(); 250 if (DeleteDeadConditions) 251 RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI); 252 if (DDT) 253 DDT->applyUpdates(Updates); 254 return true; 255 } 256 257 if (SI->getNumCases() == 1) { 258 // Otherwise, we can fold this switch into a conditional branch 259 // instruction if it has only one non-default destination. 260 auto FirstCase = *SI->case_begin(); 261 Value *Cond = Builder.CreateICmpEQ(SI->getCondition(), 262 FirstCase.getCaseValue(), "cond"); 263 264 // Insert the new branch. 265 BranchInst *NewBr = Builder.CreateCondBr(Cond, 266 FirstCase.getCaseSuccessor(), 267 SI->getDefaultDest()); 268 MDNode *MD = SI->getMetadata(LLVMContext::MD_prof); 269 if (MD && MD->getNumOperands() == 3) { 270 ConstantInt *SICase = 271 mdconst::dyn_extract<ConstantInt>(MD->getOperand(2)); 272 ConstantInt *SIDef = 273 mdconst::dyn_extract<ConstantInt>(MD->getOperand(1)); 274 assert(SICase && SIDef); 275 // The TrueWeight should be the weight for the single case of SI. 276 NewBr->setMetadata(LLVMContext::MD_prof, 277 MDBuilder(BB->getContext()). 278 createBranchWeights(SICase->getValue().getZExtValue(), 279 SIDef->getValue().getZExtValue())); 280 } 281 282 // Update make.implicit metadata to the newly-created conditional branch. 283 MDNode *MakeImplicitMD = SI->getMetadata(LLVMContext::MD_make_implicit); 284 if (MakeImplicitMD) 285 NewBr->setMetadata(LLVMContext::MD_make_implicit, MakeImplicitMD); 286 287 // Delete the old switch. 288 SI->eraseFromParent(); 289 return true; 290 } 291 return false; 292 } 293 294 if (auto *IBI = dyn_cast<IndirectBrInst>(T)) { 295 // indirectbr blockaddress(@F, @BB) -> br label @BB 296 if (auto *BA = 297 dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) { 298 BasicBlock *TheOnlyDest = BA->getBasicBlock(); 299 std::vector <DominatorTree::UpdateType> Updates; 300 if (DDT) 301 Updates.reserve(IBI->getNumDestinations() - 1); 302 303 // Insert the new branch. 304 Builder.CreateBr(TheOnlyDest); 305 306 for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) { 307 if (IBI->getDestination(i) == TheOnlyDest) { 308 TheOnlyDest = nullptr; 309 } else { 310 BasicBlock *ParentBB = IBI->getParent(); 311 BasicBlock *DestBB = IBI->getDestination(i); 312 DestBB->removePredecessor(ParentBB); 313 if (DDT) 314 Updates.push_back({DominatorTree::Delete, ParentBB, DestBB}); 315 } 316 } 317 Value *Address = IBI->getAddress(); 318 IBI->eraseFromParent(); 319 if (DeleteDeadConditions) 320 RecursivelyDeleteTriviallyDeadInstructions(Address, TLI); 321 322 // If we didn't find our destination in the IBI successor list, then we 323 // have undefined behavior. Replace the unconditional branch with an 324 // 'unreachable' instruction. 325 if (TheOnlyDest) { 326 BB->getTerminator()->eraseFromParent(); 327 new UnreachableInst(BB->getContext(), BB); 328 } 329 330 if (DDT) 331 DDT->applyUpdates(Updates); 332 return true; 333 } 334 } 335 336 return false; 337 } 338 339 //===----------------------------------------------------------------------===// 340 // Local dead code elimination. 341 // 342 343 /// isInstructionTriviallyDead - Return true if the result produced by the 344 /// instruction is not used, and the instruction has no side effects. 345 /// 346 bool llvm::isInstructionTriviallyDead(Instruction *I, 347 const TargetLibraryInfo *TLI) { 348 if (!I->use_empty()) 349 return false; 350 return wouldInstructionBeTriviallyDead(I, TLI); 351 } 352 353 bool llvm::wouldInstructionBeTriviallyDead(Instruction *I, 354 const TargetLibraryInfo *TLI) { 355 if (isa<TerminatorInst>(I)) 356 return false; 357 358 // We don't want the landingpad-like instructions removed by anything this 359 // general. 360 if (I->isEHPad()) 361 return false; 362 363 // We don't want debug info removed by anything this general, unless 364 // debug info is empty. 365 if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) { 366 if (DDI->getAddress()) 367 return false; 368 return true; 369 } 370 if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) { 371 if (DVI->getValue()) 372 return false; 373 return true; 374 } 375 if (DbgLabelInst *DLI = dyn_cast<DbgLabelInst>(I)) { 376 if (DLI->getLabel()) 377 return false; 378 return true; 379 } 380 381 if (!I->mayHaveSideEffects()) 382 return true; 383 384 // Special case intrinsics that "may have side effects" but can be deleted 385 // when dead. 386 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 387 // Safe to delete llvm.stacksave and launder.invariant.group if dead. 388 if (II->getIntrinsicID() == Intrinsic::stacksave || 389 II->getIntrinsicID() == Intrinsic::launder_invariant_group) 390 return true; 391 392 // Lifetime intrinsics are dead when their right-hand is undef. 393 if (II->getIntrinsicID() == Intrinsic::lifetime_start || 394 II->getIntrinsicID() == Intrinsic::lifetime_end) 395 return isa<UndefValue>(II->getArgOperand(1)); 396 397 // Assumptions are dead if their condition is trivially true. Guards on 398 // true are operationally no-ops. In the future we can consider more 399 // sophisticated tradeoffs for guards considering potential for check 400 // widening, but for now we keep things simple. 401 if (II->getIntrinsicID() == Intrinsic::assume || 402 II->getIntrinsicID() == Intrinsic::experimental_guard) { 403 if (ConstantInt *Cond = dyn_cast<ConstantInt>(II->getArgOperand(0))) 404 return !Cond->isZero(); 405 406 return false; 407 } 408 } 409 410 if (isAllocLikeFn(I, TLI)) 411 return true; 412 413 if (CallInst *CI = isFreeCall(I, TLI)) 414 if (Constant *C = dyn_cast<Constant>(CI->getArgOperand(0))) 415 return C->isNullValue() || isa<UndefValue>(C); 416 417 if (CallSite CS = CallSite(I)) 418 if (isMathLibCallNoop(CS, TLI)) 419 return true; 420 421 return false; 422 } 423 424 /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a 425 /// trivially dead instruction, delete it. If that makes any of its operands 426 /// trivially dead, delete them too, recursively. Return true if any 427 /// instructions were deleted. 428 bool 429 llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V, 430 const TargetLibraryInfo *TLI) { 431 Instruction *I = dyn_cast<Instruction>(V); 432 if (!I || !I->use_empty() || !isInstructionTriviallyDead(I, TLI)) 433 return false; 434 435 SmallVector<Instruction*, 16> DeadInsts; 436 DeadInsts.push_back(I); 437 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI); 438 439 return true; 440 } 441 442 void llvm::RecursivelyDeleteTriviallyDeadInstructions( 443 SmallVectorImpl<Instruction *> &DeadInsts, const TargetLibraryInfo *TLI) { 444 // Process the dead instruction list until empty. 445 while (!DeadInsts.empty()) { 446 Instruction &I = *DeadInsts.pop_back_val(); 447 assert(I.use_empty() && "Instructions with uses are not dead."); 448 assert(isInstructionTriviallyDead(&I, TLI) && 449 "Live instruction found in dead worklist!"); 450 451 // Don't lose the debug info while deleting the instructions. 452 salvageDebugInfo(I); 453 454 // Null out all of the instruction's operands to see if any operand becomes 455 // dead as we go. 456 for (Use &OpU : I.operands()) { 457 Value *OpV = OpU.get(); 458 OpU.set(nullptr); 459 460 if (!OpV->use_empty()) 461 continue; 462 463 // If the operand is an instruction that became dead as we nulled out the 464 // operand, and if it is 'trivially' dead, delete it in a future loop 465 // iteration. 466 if (Instruction *OpI = dyn_cast<Instruction>(OpV)) 467 if (isInstructionTriviallyDead(OpI, TLI)) 468 DeadInsts.push_back(OpI); 469 } 470 471 I.eraseFromParent(); 472 } 473 } 474 475 /// areAllUsesEqual - Check whether the uses of a value are all the same. 476 /// This is similar to Instruction::hasOneUse() except this will also return 477 /// true when there are no uses or multiple uses that all refer to the same 478 /// value. 479 static bool areAllUsesEqual(Instruction *I) { 480 Value::user_iterator UI = I->user_begin(); 481 Value::user_iterator UE = I->user_end(); 482 if (UI == UE) 483 return true; 484 485 User *TheUse = *UI; 486 for (++UI; UI != UE; ++UI) { 487 if (*UI != TheUse) 488 return false; 489 } 490 return true; 491 } 492 493 /// RecursivelyDeleteDeadPHINode - If the specified value is an effectively 494 /// dead PHI node, due to being a def-use chain of single-use nodes that 495 /// either forms a cycle or is terminated by a trivially dead instruction, 496 /// delete it. If that makes any of its operands trivially dead, delete them 497 /// too, recursively. Return true if a change was made. 498 bool llvm::RecursivelyDeleteDeadPHINode(PHINode *PN, 499 const TargetLibraryInfo *TLI) { 500 SmallPtrSet<Instruction*, 4> Visited; 501 for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects(); 502 I = cast<Instruction>(*I->user_begin())) { 503 if (I->use_empty()) 504 return RecursivelyDeleteTriviallyDeadInstructions(I, TLI); 505 506 // If we find an instruction more than once, we're on a cycle that 507 // won't prove fruitful. 508 if (!Visited.insert(I).second) { 509 // Break the cycle and delete the instruction and its operands. 510 I->replaceAllUsesWith(UndefValue::get(I->getType())); 511 (void)RecursivelyDeleteTriviallyDeadInstructions(I, TLI); 512 return true; 513 } 514 } 515 return false; 516 } 517 518 static bool 519 simplifyAndDCEInstruction(Instruction *I, 520 SmallSetVector<Instruction *, 16> &WorkList, 521 const DataLayout &DL, 522 const TargetLibraryInfo *TLI) { 523 if (isInstructionTriviallyDead(I, TLI)) { 524 salvageDebugInfo(*I); 525 526 // Null out all of the instruction's operands to see if any operand becomes 527 // dead as we go. 528 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 529 Value *OpV = I->getOperand(i); 530 I->setOperand(i, nullptr); 531 532 if (!OpV->use_empty() || I == OpV) 533 continue; 534 535 // If the operand is an instruction that became dead as we nulled out the 536 // operand, and if it is 'trivially' dead, delete it in a future loop 537 // iteration. 538 if (Instruction *OpI = dyn_cast<Instruction>(OpV)) 539 if (isInstructionTriviallyDead(OpI, TLI)) 540 WorkList.insert(OpI); 541 } 542 543 I->eraseFromParent(); 544 545 return true; 546 } 547 548 if (Value *SimpleV = SimplifyInstruction(I, DL)) { 549 // Add the users to the worklist. CAREFUL: an instruction can use itself, 550 // in the case of a phi node. 551 for (User *U : I->users()) { 552 if (U != I) { 553 WorkList.insert(cast<Instruction>(U)); 554 } 555 } 556 557 // Replace the instruction with its simplified value. 558 bool Changed = false; 559 if (!I->use_empty()) { 560 I->replaceAllUsesWith(SimpleV); 561 Changed = true; 562 } 563 if (isInstructionTriviallyDead(I, TLI)) { 564 I->eraseFromParent(); 565 Changed = true; 566 } 567 return Changed; 568 } 569 return false; 570 } 571 572 /// SimplifyInstructionsInBlock - Scan the specified basic block and try to 573 /// simplify any instructions in it and recursively delete dead instructions. 574 /// 575 /// This returns true if it changed the code, note that it can delete 576 /// instructions in other blocks as well in this block. 577 bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB, 578 const TargetLibraryInfo *TLI) { 579 bool MadeChange = false; 580 const DataLayout &DL = BB->getModule()->getDataLayout(); 581 582 #ifndef NDEBUG 583 // In debug builds, ensure that the terminator of the block is never replaced 584 // or deleted by these simplifications. The idea of simplification is that it 585 // cannot introduce new instructions, and there is no way to replace the 586 // terminator of a block without introducing a new instruction. 587 AssertingVH<Instruction> TerminatorVH(&BB->back()); 588 #endif 589 590 SmallSetVector<Instruction *, 16> WorkList; 591 // Iterate over the original function, only adding insts to the worklist 592 // if they actually need to be revisited. This avoids having to pre-init 593 // the worklist with the entire function's worth of instructions. 594 for (BasicBlock::iterator BI = BB->begin(), E = std::prev(BB->end()); 595 BI != E;) { 596 assert(!BI->isTerminator()); 597 Instruction *I = &*BI; 598 ++BI; 599 600 // We're visiting this instruction now, so make sure it's not in the 601 // worklist from an earlier visit. 602 if (!WorkList.count(I)) 603 MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI); 604 } 605 606 while (!WorkList.empty()) { 607 Instruction *I = WorkList.pop_back_val(); 608 MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI); 609 } 610 return MadeChange; 611 } 612 613 //===----------------------------------------------------------------------===// 614 // Control Flow Graph Restructuring. 615 // 616 617 /// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this 618 /// method is called when we're about to delete Pred as a predecessor of BB. If 619 /// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred. 620 /// 621 /// Unlike the removePredecessor method, this attempts to simplify uses of PHI 622 /// nodes that collapse into identity values. For example, if we have: 623 /// x = phi(1, 0, 0, 0) 624 /// y = and x, z 625 /// 626 /// .. and delete the predecessor corresponding to the '1', this will attempt to 627 /// recursively fold the and to 0. 628 void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred, 629 DeferredDominance *DDT) { 630 // This only adjusts blocks with PHI nodes. 631 if (!isa<PHINode>(BB->begin())) 632 return; 633 634 // Remove the entries for Pred from the PHI nodes in BB, but do not simplify 635 // them down. This will leave us with single entry phi nodes and other phis 636 // that can be removed. 637 BB->removePredecessor(Pred, true); 638 639 WeakTrackingVH PhiIt = &BB->front(); 640 while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) { 641 PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt)); 642 Value *OldPhiIt = PhiIt; 643 644 if (!recursivelySimplifyInstruction(PN)) 645 continue; 646 647 // If recursive simplification ended up deleting the next PHI node we would 648 // iterate to, then our iterator is invalid, restart scanning from the top 649 // of the block. 650 if (PhiIt != OldPhiIt) PhiIt = &BB->front(); 651 } 652 if (DDT) 653 DDT->deleteEdge(Pred, BB); 654 } 655 656 /// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its 657 /// predecessor is known to have one successor (DestBB!). Eliminate the edge 658 /// between them, moving the instructions in the predecessor into DestBB and 659 /// deleting the predecessor block. 660 void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT, 661 DeferredDominance *DDT) { 662 assert(!(DT && DDT) && "Cannot call with both DT and DDT."); 663 664 // If BB has single-entry PHI nodes, fold them. 665 while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) { 666 Value *NewVal = PN->getIncomingValue(0); 667 // Replace self referencing PHI with undef, it must be dead. 668 if (NewVal == PN) NewVal = UndefValue::get(PN->getType()); 669 PN->replaceAllUsesWith(NewVal); 670 PN->eraseFromParent(); 671 } 672 673 BasicBlock *PredBB = DestBB->getSinglePredecessor(); 674 assert(PredBB && "Block doesn't have a single predecessor!"); 675 676 bool ReplaceEntryBB = false; 677 if (PredBB == &DestBB->getParent()->getEntryBlock()) 678 ReplaceEntryBB = true; 679 680 // Deferred DT update: Collect all the edges that enter PredBB. These 681 // dominator edges will be redirected to DestBB. 682 std::vector <DominatorTree::UpdateType> Updates; 683 if (DDT && !ReplaceEntryBB) { 684 Updates.reserve(1 + (2 * pred_size(PredBB))); 685 Updates.push_back({DominatorTree::Delete, PredBB, DestBB}); 686 for (auto I = pred_begin(PredBB), E = pred_end(PredBB); I != E; ++I) { 687 Updates.push_back({DominatorTree::Delete, *I, PredBB}); 688 // This predecessor of PredBB may already have DestBB as a successor. 689 if (llvm::find(successors(*I), DestBB) == succ_end(*I)) 690 Updates.push_back({DominatorTree::Insert, *I, DestBB}); 691 } 692 } 693 694 // Zap anything that took the address of DestBB. Not doing this will give the 695 // address an invalid value. 696 if (DestBB->hasAddressTaken()) { 697 BlockAddress *BA = BlockAddress::get(DestBB); 698 Constant *Replacement = 699 ConstantInt::get(Type::getInt32Ty(BA->getContext()), 1); 700 BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement, 701 BA->getType())); 702 BA->destroyConstant(); 703 } 704 705 // Anything that branched to PredBB now branches to DestBB. 706 PredBB->replaceAllUsesWith(DestBB); 707 708 // Splice all the instructions from PredBB to DestBB. 709 PredBB->getTerminator()->eraseFromParent(); 710 DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList()); 711 712 // If the PredBB is the entry block of the function, move DestBB up to 713 // become the entry block after we erase PredBB. 714 if (ReplaceEntryBB) 715 DestBB->moveAfter(PredBB); 716 717 if (DT) { 718 // For some irreducible CFG we end up having forward-unreachable blocks 719 // so check if getNode returns a valid node before updating the domtree. 720 if (DomTreeNode *DTN = DT->getNode(PredBB)) { 721 BasicBlock *PredBBIDom = DTN->getIDom()->getBlock(); 722 DT->changeImmediateDominator(DestBB, PredBBIDom); 723 DT->eraseNode(PredBB); 724 } 725 } 726 727 if (DDT) { 728 DDT->deleteBB(PredBB); // Deferred deletion of BB. 729 if (ReplaceEntryBB) 730 // The entry block was removed and there is no external interface for the 731 // dominator tree to be notified of this change. In this corner-case we 732 // recalculate the entire tree. 733 DDT->recalculate(*(DestBB->getParent())); 734 else 735 DDT->applyUpdates(Updates); 736 } else { 737 PredBB->eraseFromParent(); // Nuke BB. 738 } 739 } 740 741 /// CanMergeValues - Return true if we can choose one of these values to use 742 /// in place of the other. Note that we will always choose the non-undef 743 /// value to keep. 744 static bool CanMergeValues(Value *First, Value *Second) { 745 return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second); 746 } 747 748 /// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an 749 /// almost-empty BB ending in an unconditional branch to Succ, into Succ. 750 /// 751 /// Assumption: Succ is the single successor for BB. 752 static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 753 assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 754 755 LLVM_DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into " 756 << Succ->getName() << "\n"); 757 // Shortcut, if there is only a single predecessor it must be BB and merging 758 // is always safe 759 if (Succ->getSinglePredecessor()) return true; 760 761 // Make a list of the predecessors of BB 762 SmallPtrSet<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB)); 763 764 // Look at all the phi nodes in Succ, to see if they present a conflict when 765 // merging these blocks 766 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 767 PHINode *PN = cast<PHINode>(I); 768 769 // If the incoming value from BB is again a PHINode in 770 // BB which has the same incoming value for *PI as PN does, we can 771 // merge the phi nodes and then the blocks can still be merged 772 PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB)); 773 if (BBPN && BBPN->getParent() == BB) { 774 for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) { 775 BasicBlock *IBB = PN->getIncomingBlock(PI); 776 if (BBPreds.count(IBB) && 777 !CanMergeValues(BBPN->getIncomingValueForBlock(IBB), 778 PN->getIncomingValue(PI))) { 779 LLVM_DEBUG(dbgs() 780 << "Can't fold, phi node " << PN->getName() << " in " 781 << Succ->getName() << " is conflicting with " 782 << BBPN->getName() << " with regard to common predecessor " 783 << IBB->getName() << "\n"); 784 return false; 785 } 786 } 787 } else { 788 Value* Val = PN->getIncomingValueForBlock(BB); 789 for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) { 790 // See if the incoming value for the common predecessor is equal to the 791 // one for BB, in which case this phi node will not prevent the merging 792 // of the block. 793 BasicBlock *IBB = PN->getIncomingBlock(PI); 794 if (BBPreds.count(IBB) && 795 !CanMergeValues(Val, PN->getIncomingValue(PI))) { 796 LLVM_DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() 797 << " in " << Succ->getName() 798 << " is conflicting with regard to common " 799 << "predecessor " << IBB->getName() << "\n"); 800 return false; 801 } 802 } 803 } 804 } 805 806 return true; 807 } 808 809 using PredBlockVector = SmallVector<BasicBlock *, 16>; 810 using IncomingValueMap = DenseMap<BasicBlock *, Value *>; 811 812 /// Determines the value to use as the phi node input for a block. 813 /// 814 /// Select between \p OldVal any value that we know flows from \p BB 815 /// to a particular phi on the basis of which one (if either) is not 816 /// undef. Update IncomingValues based on the selected value. 817 /// 818 /// \param OldVal The value we are considering selecting. 819 /// \param BB The block that the value flows in from. 820 /// \param IncomingValues A map from block-to-value for other phi inputs 821 /// that we have examined. 822 /// 823 /// \returns the selected value. 824 static Value *selectIncomingValueForBlock(Value *OldVal, BasicBlock *BB, 825 IncomingValueMap &IncomingValues) { 826 if (!isa<UndefValue>(OldVal)) { 827 assert((!IncomingValues.count(BB) || 828 IncomingValues.find(BB)->second == OldVal) && 829 "Expected OldVal to match incoming value from BB!"); 830 831 IncomingValues.insert(std::make_pair(BB, OldVal)); 832 return OldVal; 833 } 834 835 IncomingValueMap::const_iterator It = IncomingValues.find(BB); 836 if (It != IncomingValues.end()) return It->second; 837 838 return OldVal; 839 } 840 841 /// Create a map from block to value for the operands of a 842 /// given phi. 843 /// 844 /// Create a map from block to value for each non-undef value flowing 845 /// into \p PN. 846 /// 847 /// \param PN The phi we are collecting the map for. 848 /// \param IncomingValues [out] The map from block to value for this phi. 849 static void gatherIncomingValuesToPhi(PHINode *PN, 850 IncomingValueMap &IncomingValues) { 851 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 852 BasicBlock *BB = PN->getIncomingBlock(i); 853 Value *V = PN->getIncomingValue(i); 854 855 if (!isa<UndefValue>(V)) 856 IncomingValues.insert(std::make_pair(BB, V)); 857 } 858 } 859 860 /// Replace the incoming undef values to a phi with the values 861 /// from a block-to-value map. 862 /// 863 /// \param PN The phi we are replacing the undefs in. 864 /// \param IncomingValues A map from block to value. 865 static void replaceUndefValuesInPhi(PHINode *PN, 866 const IncomingValueMap &IncomingValues) { 867 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 868 Value *V = PN->getIncomingValue(i); 869 870 if (!isa<UndefValue>(V)) continue; 871 872 BasicBlock *BB = PN->getIncomingBlock(i); 873 IncomingValueMap::const_iterator It = IncomingValues.find(BB); 874 if (It == IncomingValues.end()) continue; 875 876 PN->setIncomingValue(i, It->second); 877 } 878 } 879 880 /// Replace a value flowing from a block to a phi with 881 /// potentially multiple instances of that value flowing from the 882 /// block's predecessors to the phi. 883 /// 884 /// \param BB The block with the value flowing into the phi. 885 /// \param BBPreds The predecessors of BB. 886 /// \param PN The phi that we are updating. 887 static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB, 888 const PredBlockVector &BBPreds, 889 PHINode *PN) { 890 Value *OldVal = PN->removeIncomingValue(BB, false); 891 assert(OldVal && "No entry in PHI for Pred BB!"); 892 893 IncomingValueMap IncomingValues; 894 895 // We are merging two blocks - BB, and the block containing PN - and 896 // as a result we need to redirect edges from the predecessors of BB 897 // to go to the block containing PN, and update PN 898 // accordingly. Since we allow merging blocks in the case where the 899 // predecessor and successor blocks both share some predecessors, 900 // and where some of those common predecessors might have undef 901 // values flowing into PN, we want to rewrite those values to be 902 // consistent with the non-undef values. 903 904 gatherIncomingValuesToPhi(PN, IncomingValues); 905 906 // If this incoming value is one of the PHI nodes in BB, the new entries 907 // in the PHI node are the entries from the old PHI. 908 if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { 909 PHINode *OldValPN = cast<PHINode>(OldVal); 910 for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) { 911 // Note that, since we are merging phi nodes and BB and Succ might 912 // have common predecessors, we could end up with a phi node with 913 // identical incoming branches. This will be cleaned up later (and 914 // will trigger asserts if we try to clean it up now, without also 915 // simplifying the corresponding conditional branch). 916 BasicBlock *PredBB = OldValPN->getIncomingBlock(i); 917 Value *PredVal = OldValPN->getIncomingValue(i); 918 Value *Selected = selectIncomingValueForBlock(PredVal, PredBB, 919 IncomingValues); 920 921 // And add a new incoming value for this predecessor for the 922 // newly retargeted branch. 923 PN->addIncoming(Selected, PredBB); 924 } 925 } else { 926 for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) { 927 // Update existing incoming values in PN for this 928 // predecessor of BB. 929 BasicBlock *PredBB = BBPreds[i]; 930 Value *Selected = selectIncomingValueForBlock(OldVal, PredBB, 931 IncomingValues); 932 933 // And add a new incoming value for this predecessor for the 934 // newly retargeted branch. 935 PN->addIncoming(Selected, PredBB); 936 } 937 } 938 939 replaceUndefValuesInPhi(PN, IncomingValues); 940 } 941 942 /// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an 943 /// unconditional branch, and contains no instructions other than PHI nodes, 944 /// potential side-effect free intrinsics and the branch. If possible, 945 /// eliminate BB by rewriting all the predecessors to branch to the successor 946 /// block and return true. If we can't transform, return false. 947 bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, 948 DeferredDominance *DDT) { 949 assert(BB != &BB->getParent()->getEntryBlock() && 950 "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!"); 951 952 // We can't eliminate infinite loops. 953 BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0); 954 if (BB == Succ) return false; 955 956 // Check to see if merging these blocks would cause conflicts for any of the 957 // phi nodes in BB or Succ. If not, we can safely merge. 958 if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false; 959 960 // Check for cases where Succ has multiple predecessors and a PHI node in BB 961 // has uses which will not disappear when the PHI nodes are merged. It is 962 // possible to handle such cases, but difficult: it requires checking whether 963 // BB dominates Succ, which is non-trivial to calculate in the case where 964 // Succ has multiple predecessors. Also, it requires checking whether 965 // constructing the necessary self-referential PHI node doesn't introduce any 966 // conflicts; this isn't too difficult, but the previous code for doing this 967 // was incorrect. 968 // 969 // Note that if this check finds a live use, BB dominates Succ, so BB is 970 // something like a loop pre-header (or rarely, a part of an irreducible CFG); 971 // folding the branch isn't profitable in that case anyway. 972 if (!Succ->getSinglePredecessor()) { 973 BasicBlock::iterator BBI = BB->begin(); 974 while (isa<PHINode>(*BBI)) { 975 for (Use &U : BBI->uses()) { 976 if (PHINode* PN = dyn_cast<PHINode>(U.getUser())) { 977 if (PN->getIncomingBlock(U) != BB) 978 return false; 979 } else { 980 return false; 981 } 982 } 983 ++BBI; 984 } 985 } 986 987 LLVM_DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB); 988 989 std::vector<DominatorTree::UpdateType> Updates; 990 if (DDT) { 991 Updates.reserve(1 + (2 * pred_size(BB))); 992 Updates.push_back({DominatorTree::Delete, BB, Succ}); 993 // All predecessors of BB will be moved to Succ. 994 for (auto I = pred_begin(BB), E = pred_end(BB); I != E; ++I) { 995 Updates.push_back({DominatorTree::Delete, *I, BB}); 996 // This predecessor of BB may already have Succ as a successor. 997 if (llvm::find(successors(*I), Succ) == succ_end(*I)) 998 Updates.push_back({DominatorTree::Insert, *I, Succ}); 999 } 1000 } 1001 1002 if (isa<PHINode>(Succ->begin())) { 1003 // If there is more than one pred of succ, and there are PHI nodes in 1004 // the successor, then we need to add incoming edges for the PHI nodes 1005 // 1006 const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB)); 1007 1008 // Loop over all of the PHI nodes in the successor of BB. 1009 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 1010 PHINode *PN = cast<PHINode>(I); 1011 1012 redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN); 1013 } 1014 } 1015 1016 if (Succ->getSinglePredecessor()) { 1017 // BB is the only predecessor of Succ, so Succ will end up with exactly 1018 // the same predecessors BB had. 1019 1020 // Copy over any phi, debug or lifetime instruction. 1021 BB->getTerminator()->eraseFromParent(); 1022 Succ->getInstList().splice(Succ->getFirstNonPHI()->getIterator(), 1023 BB->getInstList()); 1024 } else { 1025 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 1026 // We explicitly check for such uses in CanPropagatePredecessorsForPHIs. 1027 assert(PN->use_empty() && "There shouldn't be any uses here!"); 1028 PN->eraseFromParent(); 1029 } 1030 } 1031 1032 // If the unconditional branch we replaced contains llvm.loop metadata, we 1033 // add the metadata to the branch instructions in the predecessors. 1034 unsigned LoopMDKind = BB->getContext().getMDKindID("llvm.loop"); 1035 Instruction *TI = BB->getTerminator(); 1036 if (TI) 1037 if (MDNode *LoopMD = TI->getMetadata(LoopMDKind)) 1038 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 1039 BasicBlock *Pred = *PI; 1040 Pred->getTerminator()->setMetadata(LoopMDKind, LoopMD); 1041 } 1042 1043 // Everything that jumped to BB now goes to Succ. 1044 BB->replaceAllUsesWith(Succ); 1045 if (!Succ->hasName()) Succ->takeName(BB); 1046 1047 if (DDT) { 1048 DDT->deleteBB(BB); // Deferred deletion of the old basic block. 1049 DDT->applyUpdates(Updates); 1050 } else { 1051 BB->eraseFromParent(); // Delete the old basic block. 1052 } 1053 return true; 1054 } 1055 1056 /// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI 1057 /// nodes in this block. This doesn't try to be clever about PHI nodes 1058 /// which differ only in the order of the incoming values, but instcombine 1059 /// orders them so it usually won't matter. 1060 bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { 1061 // This implementation doesn't currently consider undef operands 1062 // specially. Theoretically, two phis which are identical except for 1063 // one having an undef where the other doesn't could be collapsed. 1064 1065 struct PHIDenseMapInfo { 1066 static PHINode *getEmptyKey() { 1067 return DenseMapInfo<PHINode *>::getEmptyKey(); 1068 } 1069 1070 static PHINode *getTombstoneKey() { 1071 return DenseMapInfo<PHINode *>::getTombstoneKey(); 1072 } 1073 1074 static unsigned getHashValue(PHINode *PN) { 1075 // Compute a hash value on the operands. Instcombine will likely have 1076 // sorted them, which helps expose duplicates, but we have to check all 1077 // the operands to be safe in case instcombine hasn't run. 1078 return static_cast<unsigned>(hash_combine( 1079 hash_combine_range(PN->value_op_begin(), PN->value_op_end()), 1080 hash_combine_range(PN->block_begin(), PN->block_end()))); 1081 } 1082 1083 static bool isEqual(PHINode *LHS, PHINode *RHS) { 1084 if (LHS == getEmptyKey() || LHS == getTombstoneKey() || 1085 RHS == getEmptyKey() || RHS == getTombstoneKey()) 1086 return LHS == RHS; 1087 return LHS->isIdenticalTo(RHS); 1088 } 1089 }; 1090 1091 // Set of unique PHINodes. 1092 DenseSet<PHINode *, PHIDenseMapInfo> PHISet; 1093 1094 // Examine each PHI. 1095 bool Changed = false; 1096 for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I++);) { 1097 auto Inserted = PHISet.insert(PN); 1098 if (!Inserted.second) { 1099 // A duplicate. Replace this PHI with its duplicate. 1100 PN->replaceAllUsesWith(*Inserted.first); 1101 PN->eraseFromParent(); 1102 Changed = true; 1103 1104 // The RAUW can change PHIs that we already visited. Start over from the 1105 // beginning. 1106 PHISet.clear(); 1107 I = BB->begin(); 1108 } 1109 } 1110 1111 return Changed; 1112 } 1113 1114 /// enforceKnownAlignment - If the specified pointer points to an object that 1115 /// we control, modify the object's alignment to PrefAlign. This isn't 1116 /// often possible though. If alignment is important, a more reliable approach 1117 /// is to simply align all global variables and allocation instructions to 1118 /// their preferred alignment from the beginning. 1119 static unsigned enforceKnownAlignment(Value *V, unsigned Align, 1120 unsigned PrefAlign, 1121 const DataLayout &DL) { 1122 assert(PrefAlign > Align); 1123 1124 V = V->stripPointerCasts(); 1125 1126 if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) { 1127 // TODO: ideally, computeKnownBits ought to have used 1128 // AllocaInst::getAlignment() in its computation already, making 1129 // the below max redundant. But, as it turns out, 1130 // stripPointerCasts recurses through infinite layers of bitcasts, 1131 // while computeKnownBits is not allowed to traverse more than 6 1132 // levels. 1133 Align = std::max(AI->getAlignment(), Align); 1134 if (PrefAlign <= Align) 1135 return Align; 1136 1137 // If the preferred alignment is greater than the natural stack alignment 1138 // then don't round up. This avoids dynamic stack realignment. 1139 if (DL.exceedsNaturalStackAlignment(PrefAlign)) 1140 return Align; 1141 AI->setAlignment(PrefAlign); 1142 return PrefAlign; 1143 } 1144 1145 if (auto *GO = dyn_cast<GlobalObject>(V)) { 1146 // TODO: as above, this shouldn't be necessary. 1147 Align = std::max(GO->getAlignment(), Align); 1148 if (PrefAlign <= Align) 1149 return Align; 1150 1151 // If there is a large requested alignment and we can, bump up the alignment 1152 // of the global. If the memory we set aside for the global may not be the 1153 // memory used by the final program then it is impossible for us to reliably 1154 // enforce the preferred alignment. 1155 if (!GO->canIncreaseAlignment()) 1156 return Align; 1157 1158 GO->setAlignment(PrefAlign); 1159 return PrefAlign; 1160 } 1161 1162 return Align; 1163 } 1164 1165 unsigned llvm::getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, 1166 const DataLayout &DL, 1167 const Instruction *CxtI, 1168 AssumptionCache *AC, 1169 const DominatorTree *DT) { 1170 assert(V->getType()->isPointerTy() && 1171 "getOrEnforceKnownAlignment expects a pointer!"); 1172 1173 KnownBits Known = computeKnownBits(V, DL, 0, AC, CxtI, DT); 1174 unsigned TrailZ = Known.countMinTrailingZeros(); 1175 1176 // Avoid trouble with ridiculously large TrailZ values, such as 1177 // those computed from a null pointer. 1178 TrailZ = std::min(TrailZ, unsigned(sizeof(unsigned) * CHAR_BIT - 1)); 1179 1180 unsigned Align = 1u << std::min(Known.getBitWidth() - 1, TrailZ); 1181 1182 // LLVM doesn't support alignments larger than this currently. 1183 Align = std::min(Align, +Value::MaximumAlignment); 1184 1185 if (PrefAlign > Align) 1186 Align = enforceKnownAlignment(V, Align, PrefAlign, DL); 1187 1188 // We don't need to make any adjustment. 1189 return Align; 1190 } 1191 1192 ///===---------------------------------------------------------------------===// 1193 /// Dbg Intrinsic utilities 1194 /// 1195 1196 /// See if there is a dbg.value intrinsic for DIVar before I. 1197 static bool LdStHasDebugValue(DILocalVariable *DIVar, DIExpression *DIExpr, 1198 Instruction *I) { 1199 // Since we can't guarantee that the original dbg.declare instrinsic 1200 // is removed by LowerDbgDeclare(), we need to make sure that we are 1201 // not inserting the same dbg.value intrinsic over and over. 1202 BasicBlock::InstListType::iterator PrevI(I); 1203 if (PrevI != I->getParent()->getInstList().begin()) { 1204 --PrevI; 1205 if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(PrevI)) 1206 if (DVI->getValue() == I->getOperand(0) && 1207 DVI->getVariable() == DIVar && 1208 DVI->getExpression() == DIExpr) 1209 return true; 1210 } 1211 return false; 1212 } 1213 1214 /// See if there is a dbg.value intrinsic for DIVar for the PHI node. 1215 static bool PhiHasDebugValue(DILocalVariable *DIVar, 1216 DIExpression *DIExpr, 1217 PHINode *APN) { 1218 // Since we can't guarantee that the original dbg.declare instrinsic 1219 // is removed by LowerDbgDeclare(), we need to make sure that we are 1220 // not inserting the same dbg.value intrinsic over and over. 1221 SmallVector<DbgValueInst *, 1> DbgValues; 1222 findDbgValues(DbgValues, APN); 1223 for (auto *DVI : DbgValues) { 1224 assert(DVI->getValue() == APN); 1225 if ((DVI->getVariable() == DIVar) && (DVI->getExpression() == DIExpr)) 1226 return true; 1227 } 1228 return false; 1229 } 1230 1231 /// Check if the alloc size of \p ValTy is large enough to cover the variable 1232 /// (or fragment of the variable) described by \p DII. 1233 /// 1234 /// This is primarily intended as a helper for the different 1235 /// ConvertDebugDeclareToDebugValue functions. The dbg.declare/dbg.addr that is 1236 /// converted describes an alloca'd variable, so we need to use the 1237 /// alloc size of the value when doing the comparison. E.g. an i1 value will be 1238 /// identified as covering an n-bit fragment, if the store size of i1 is at 1239 /// least n bits. 1240 static bool valueCoversEntireFragment(Type *ValTy, DbgInfoIntrinsic *DII) { 1241 const DataLayout &DL = DII->getModule()->getDataLayout(); 1242 uint64_t ValueSize = DL.getTypeAllocSizeInBits(ValTy); 1243 if (auto FragmentSize = DII->getFragmentSizeInBits()) 1244 return ValueSize >= *FragmentSize; 1245 // We can't always calculate the size of the DI variable (e.g. if it is a 1246 // VLA). Try to use the size of the alloca that the dbg intrinsic describes 1247 // intead. 1248 if (DII->isAddressOfVariable()) 1249 if (auto *AI = dyn_cast_or_null<AllocaInst>(DII->getVariableLocation())) 1250 if (auto FragmentSize = AI->getAllocationSizeInBits(DL)) 1251 return ValueSize >= *FragmentSize; 1252 // Could not determine size of variable. Conservatively return false. 1253 return false; 1254 } 1255 1256 /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value 1257 /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic. 1258 void llvm::ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII, 1259 StoreInst *SI, DIBuilder &Builder) { 1260 assert(DII->isAddressOfVariable()); 1261 auto *DIVar = DII->getVariable(); 1262 assert(DIVar && "Missing variable"); 1263 auto *DIExpr = DII->getExpression(); 1264 Value *DV = SI->getOperand(0); 1265 1266 if (!valueCoversEntireFragment(SI->getValueOperand()->getType(), DII)) { 1267 // FIXME: If storing to a part of the variable described by the dbg.declare, 1268 // then we want to insert a dbg.value for the corresponding fragment. 1269 LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: " 1270 << *DII << '\n'); 1271 // For now, when there is a store to parts of the variable (but we do not 1272 // know which part) we insert an dbg.value instrinsic to indicate that we 1273 // know nothing about the variable's content. 1274 DV = UndefValue::get(DV->getType()); 1275 if (!LdStHasDebugValue(DIVar, DIExpr, SI)) 1276 Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, DII->getDebugLoc(), 1277 SI); 1278 return; 1279 } 1280 1281 // If an argument is zero extended then use argument directly. The ZExt 1282 // may be zapped by an optimization pass in future. 1283 Argument *ExtendedArg = nullptr; 1284 if (ZExtInst *ZExt = dyn_cast<ZExtInst>(SI->getOperand(0))) 1285 ExtendedArg = dyn_cast<Argument>(ZExt->getOperand(0)); 1286 if (SExtInst *SExt = dyn_cast<SExtInst>(SI->getOperand(0))) 1287 ExtendedArg = dyn_cast<Argument>(SExt->getOperand(0)); 1288 if (ExtendedArg) { 1289 // If this DII was already describing only a fragment of a variable, ensure 1290 // that fragment is appropriately narrowed here. 1291 // But if a fragment wasn't used, describe the value as the original 1292 // argument (rather than the zext or sext) so that it remains described even 1293 // if the sext/zext is optimized away. This widens the variable description, 1294 // leaving it up to the consumer to know how the smaller value may be 1295 // represented in a larger register. 1296 if (auto Fragment = DIExpr->getFragmentInfo()) { 1297 unsigned FragmentOffset = Fragment->OffsetInBits; 1298 SmallVector<uint64_t, 3> Ops(DIExpr->elements_begin(), 1299 DIExpr->elements_end() - 3); 1300 Ops.push_back(dwarf::DW_OP_LLVM_fragment); 1301 Ops.push_back(FragmentOffset); 1302 const DataLayout &DL = DII->getModule()->getDataLayout(); 1303 Ops.push_back(DL.getTypeSizeInBits(ExtendedArg->getType())); 1304 DIExpr = Builder.createExpression(Ops); 1305 } 1306 DV = ExtendedArg; 1307 } 1308 if (!LdStHasDebugValue(DIVar, DIExpr, SI)) 1309 Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, DII->getDebugLoc(), 1310 SI); 1311 } 1312 1313 /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value 1314 /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic. 1315 void llvm::ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII, 1316 LoadInst *LI, DIBuilder &Builder) { 1317 auto *DIVar = DII->getVariable(); 1318 auto *DIExpr = DII->getExpression(); 1319 assert(DIVar && "Missing variable"); 1320 1321 if (LdStHasDebugValue(DIVar, DIExpr, LI)) 1322 return; 1323 1324 if (!valueCoversEntireFragment(LI->getType(), DII)) { 1325 // FIXME: If only referring to a part of the variable described by the 1326 // dbg.declare, then we want to insert a dbg.value for the corresponding 1327 // fragment. 1328 LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: " 1329 << *DII << '\n'); 1330 return; 1331 } 1332 1333 // We are now tracking the loaded value instead of the address. In the 1334 // future if multi-location support is added to the IR, it might be 1335 // preferable to keep tracking both the loaded value and the original 1336 // address in case the alloca can not be elided. 1337 Instruction *DbgValue = Builder.insertDbgValueIntrinsic( 1338 LI, DIVar, DIExpr, DII->getDebugLoc(), (Instruction *)nullptr); 1339 DbgValue->insertAfter(LI); 1340 } 1341 1342 /// Inserts a llvm.dbg.value intrinsic after a phi that has an associated 1343 /// llvm.dbg.declare or llvm.dbg.addr intrinsic. 1344 void llvm::ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII, 1345 PHINode *APN, DIBuilder &Builder) { 1346 auto *DIVar = DII->getVariable(); 1347 auto *DIExpr = DII->getExpression(); 1348 assert(DIVar && "Missing variable"); 1349 1350 if (PhiHasDebugValue(DIVar, DIExpr, APN)) 1351 return; 1352 1353 if (!valueCoversEntireFragment(APN->getType(), DII)) { 1354 // FIXME: If only referring to a part of the variable described by the 1355 // dbg.declare, then we want to insert a dbg.value for the corresponding 1356 // fragment. 1357 LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: " 1358 << *DII << '\n'); 1359 return; 1360 } 1361 1362 BasicBlock *BB = APN->getParent(); 1363 auto InsertionPt = BB->getFirstInsertionPt(); 1364 1365 // The block may be a catchswitch block, which does not have a valid 1366 // insertion point. 1367 // FIXME: Insert dbg.value markers in the successors when appropriate. 1368 if (InsertionPt != BB->end()) 1369 Builder.insertDbgValueIntrinsic(APN, DIVar, DIExpr, DII->getDebugLoc(), 1370 &*InsertionPt); 1371 } 1372 1373 /// Determine whether this alloca is either a VLA or an array. 1374 static bool isArray(AllocaInst *AI) { 1375 return AI->isArrayAllocation() || 1376 AI->getType()->getElementType()->isArrayTy(); 1377 } 1378 1379 /// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set 1380 /// of llvm.dbg.value intrinsics. 1381 bool llvm::LowerDbgDeclare(Function &F) { 1382 DIBuilder DIB(*F.getParent(), /*AllowUnresolved*/ false); 1383 SmallVector<DbgDeclareInst *, 4> Dbgs; 1384 for (auto &FI : F) 1385 for (Instruction &BI : FI) 1386 if (auto DDI = dyn_cast<DbgDeclareInst>(&BI)) 1387 Dbgs.push_back(DDI); 1388 1389 if (Dbgs.empty()) 1390 return false; 1391 1392 for (auto &I : Dbgs) { 1393 DbgDeclareInst *DDI = I; 1394 AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress()); 1395 // If this is an alloca for a scalar variable, insert a dbg.value 1396 // at each load and store to the alloca and erase the dbg.declare. 1397 // The dbg.values allow tracking a variable even if it is not 1398 // stored on the stack, while the dbg.declare can only describe 1399 // the stack slot (and at a lexical-scope granularity). Later 1400 // passes will attempt to elide the stack slot. 1401 if (!AI || isArray(AI)) 1402 continue; 1403 1404 // A volatile load/store means that the alloca can't be elided anyway. 1405 if (llvm::any_of(AI->users(), [](User *U) -> bool { 1406 if (LoadInst *LI = dyn_cast<LoadInst>(U)) 1407 return LI->isVolatile(); 1408 if (StoreInst *SI = dyn_cast<StoreInst>(U)) 1409 return SI->isVolatile(); 1410 return false; 1411 })) 1412 continue; 1413 1414 for (auto &AIUse : AI->uses()) { 1415 User *U = AIUse.getUser(); 1416 if (StoreInst *SI = dyn_cast<StoreInst>(U)) { 1417 if (AIUse.getOperandNo() == 1) 1418 ConvertDebugDeclareToDebugValue(DDI, SI, DIB); 1419 } else if (LoadInst *LI = dyn_cast<LoadInst>(U)) { 1420 ConvertDebugDeclareToDebugValue(DDI, LI, DIB); 1421 } else if (CallInst *CI = dyn_cast<CallInst>(U)) { 1422 // This is a call by-value or some other instruction that 1423 // takes a pointer to the variable. Insert a *value* 1424 // intrinsic that describes the alloca. 1425 DIB.insertDbgValueIntrinsic(AI, DDI->getVariable(), 1426 DDI->getExpression(), DDI->getDebugLoc(), 1427 CI); 1428 } 1429 } 1430 DDI->eraseFromParent(); 1431 } 1432 return true; 1433 } 1434 1435 /// Propagate dbg.value intrinsics through the newly inserted PHIs. 1436 void llvm::insertDebugValuesForPHIs(BasicBlock *BB, 1437 SmallVectorImpl<PHINode *> &InsertedPHIs) { 1438 assert(BB && "No BasicBlock to clone dbg.value(s) from."); 1439 if (InsertedPHIs.size() == 0) 1440 return; 1441 1442 // Map existing PHI nodes to their dbg.values. 1443 ValueToValueMapTy DbgValueMap; 1444 for (auto &I : *BB) { 1445 if (auto DbgII = dyn_cast<DbgInfoIntrinsic>(&I)) { 1446 if (auto *Loc = dyn_cast_or_null<PHINode>(DbgII->getVariableLocation())) 1447 DbgValueMap.insert({Loc, DbgII}); 1448 } 1449 } 1450 if (DbgValueMap.size() == 0) 1451 return; 1452 1453 // Then iterate through the new PHIs and look to see if they use one of the 1454 // previously mapped PHIs. If so, insert a new dbg.value intrinsic that will 1455 // propagate the info through the new PHI. 1456 LLVMContext &C = BB->getContext(); 1457 for (auto PHI : InsertedPHIs) { 1458 BasicBlock *Parent = PHI->getParent(); 1459 // Avoid inserting an intrinsic into an EH block. 1460 if (Parent->getFirstNonPHI()->isEHPad()) 1461 continue; 1462 auto PhiMAV = MetadataAsValue::get(C, ValueAsMetadata::get(PHI)); 1463 for (auto VI : PHI->operand_values()) { 1464 auto V = DbgValueMap.find(VI); 1465 if (V != DbgValueMap.end()) { 1466 auto *DbgII = cast<DbgInfoIntrinsic>(V->second); 1467 Instruction *NewDbgII = DbgII->clone(); 1468 NewDbgII->setOperand(0, PhiMAV); 1469 auto InsertionPt = Parent->getFirstInsertionPt(); 1470 assert(InsertionPt != Parent->end() && "Ill-formed basic block"); 1471 NewDbgII->insertBefore(&*InsertionPt); 1472 } 1473 } 1474 } 1475 } 1476 1477 /// Finds all intrinsics declaring local variables as living in the memory that 1478 /// 'V' points to. This may include a mix of dbg.declare and 1479 /// dbg.addr intrinsics. 1480 TinyPtrVector<DbgInfoIntrinsic *> llvm::FindDbgAddrUses(Value *V) { 1481 // This function is hot. Check whether the value has any metadata to avoid a 1482 // DenseMap lookup. 1483 if (!V->isUsedByMetadata()) 1484 return {}; 1485 auto *L = LocalAsMetadata::getIfExists(V); 1486 if (!L) 1487 return {}; 1488 auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L); 1489 if (!MDV) 1490 return {}; 1491 1492 TinyPtrVector<DbgInfoIntrinsic *> Declares; 1493 for (User *U : MDV->users()) { 1494 if (auto *DII = dyn_cast<DbgInfoIntrinsic>(U)) 1495 if (DII->isAddressOfVariable()) 1496 Declares.push_back(DII); 1497 } 1498 1499 return Declares; 1500 } 1501 1502 void llvm::findDbgValues(SmallVectorImpl<DbgValueInst *> &DbgValues, Value *V) { 1503 // This function is hot. Check whether the value has any metadata to avoid a 1504 // DenseMap lookup. 1505 if (!V->isUsedByMetadata()) 1506 return; 1507 if (auto *L = LocalAsMetadata::getIfExists(V)) 1508 if (auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L)) 1509 for (User *U : MDV->users()) 1510 if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(U)) 1511 DbgValues.push_back(DVI); 1512 } 1513 1514 void llvm::findDbgUsers(SmallVectorImpl<DbgInfoIntrinsic *> &DbgUsers, 1515 Value *V) { 1516 // This function is hot. Check whether the value has any metadata to avoid a 1517 // DenseMap lookup. 1518 if (!V->isUsedByMetadata()) 1519 return; 1520 if (auto *L = LocalAsMetadata::getIfExists(V)) 1521 if (auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L)) 1522 for (User *U : MDV->users()) 1523 if (DbgInfoIntrinsic *DII = dyn_cast<DbgInfoIntrinsic>(U)) 1524 DbgUsers.push_back(DII); 1525 } 1526 1527 bool llvm::replaceDbgDeclare(Value *Address, Value *NewAddress, 1528 Instruction *InsertBefore, DIBuilder &Builder, 1529 bool DerefBefore, int Offset, bool DerefAfter) { 1530 auto DbgAddrs = FindDbgAddrUses(Address); 1531 for (DbgInfoIntrinsic *DII : DbgAddrs) { 1532 DebugLoc Loc = DII->getDebugLoc(); 1533 auto *DIVar = DII->getVariable(); 1534 auto *DIExpr = DII->getExpression(); 1535 assert(DIVar && "Missing variable"); 1536 DIExpr = DIExpression::prepend(DIExpr, DerefBefore, Offset, DerefAfter); 1537 // Insert llvm.dbg.declare immediately after InsertBefore, and remove old 1538 // llvm.dbg.declare. 1539 Builder.insertDeclare(NewAddress, DIVar, DIExpr, Loc, InsertBefore); 1540 if (DII == InsertBefore) 1541 InsertBefore = &*std::next(InsertBefore->getIterator()); 1542 DII->eraseFromParent(); 1543 } 1544 return !DbgAddrs.empty(); 1545 } 1546 1547 bool llvm::replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, 1548 DIBuilder &Builder, bool DerefBefore, 1549 int Offset, bool DerefAfter) { 1550 return replaceDbgDeclare(AI, NewAllocaAddress, AI->getNextNode(), Builder, 1551 DerefBefore, Offset, DerefAfter); 1552 } 1553 1554 static void replaceOneDbgValueForAlloca(DbgValueInst *DVI, Value *NewAddress, 1555 DIBuilder &Builder, int Offset) { 1556 DebugLoc Loc = DVI->getDebugLoc(); 1557 auto *DIVar = DVI->getVariable(); 1558 auto *DIExpr = DVI->getExpression(); 1559 assert(DIVar && "Missing variable"); 1560 1561 // This is an alloca-based llvm.dbg.value. The first thing it should do with 1562 // the alloca pointer is dereference it. Otherwise we don't know how to handle 1563 // it and give up. 1564 if (!DIExpr || DIExpr->getNumElements() < 1 || 1565 DIExpr->getElement(0) != dwarf::DW_OP_deref) 1566 return; 1567 1568 // Insert the offset immediately after the first deref. 1569 // We could just change the offset argument of dbg.value, but it's unsigned... 1570 if (Offset) { 1571 SmallVector<uint64_t, 4> Ops; 1572 Ops.push_back(dwarf::DW_OP_deref); 1573 DIExpression::appendOffset(Ops, Offset); 1574 Ops.append(DIExpr->elements_begin() + 1, DIExpr->elements_end()); 1575 DIExpr = Builder.createExpression(Ops); 1576 } 1577 1578 Builder.insertDbgValueIntrinsic(NewAddress, DIVar, DIExpr, Loc, DVI); 1579 DVI->eraseFromParent(); 1580 } 1581 1582 void llvm::replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress, 1583 DIBuilder &Builder, int Offset) { 1584 if (auto *L = LocalAsMetadata::getIfExists(AI)) 1585 if (auto *MDV = MetadataAsValue::getIfExists(AI->getContext(), L)) 1586 for (auto UI = MDV->use_begin(), UE = MDV->use_end(); UI != UE;) { 1587 Use &U = *UI++; 1588 if (auto *DVI = dyn_cast<DbgValueInst>(U.getUser())) 1589 replaceOneDbgValueForAlloca(DVI, NewAllocaAddress, Builder, Offset); 1590 } 1591 } 1592 1593 void llvm::salvageDebugInfo(Instruction &I) { 1594 SmallVector<DbgInfoIntrinsic *, 1> DbgUsers; 1595 findDbgUsers(DbgUsers, &I); 1596 if (DbgUsers.empty()) 1597 return; 1598 1599 auto &M = *I.getModule(); 1600 auto &DL = M.getDataLayout(); 1601 1602 auto wrapMD = [&](Value *V) { 1603 return MetadataAsValue::get(I.getContext(), ValueAsMetadata::get(V)); 1604 }; 1605 1606 auto doSalvage = [&](DbgInfoIntrinsic *DII, SmallVectorImpl<uint64_t> &Ops) { 1607 auto *DIExpr = DII->getExpression(); 1608 if (!Ops.empty()) { 1609 // Do not add DW_OP_stack_value for DbgDeclare and DbgAddr, because they 1610 // are implicitly pointing out the value as a DWARF memory location 1611 // description. 1612 bool WithStackValue = isa<DbgValueInst>(DII); 1613 DIExpr = DIExpression::prependOpcodes(DIExpr, Ops, WithStackValue); 1614 } 1615 DII->setOperand(0, wrapMD(I.getOperand(0))); 1616 DII->setOperand(2, MetadataAsValue::get(I.getContext(), DIExpr)); 1617 LLVM_DEBUG(dbgs() << "SALVAGE: " << *DII << '\n'); 1618 }; 1619 1620 auto applyOffset = [&](DbgInfoIntrinsic *DII, uint64_t Offset) { 1621 SmallVector<uint64_t, 8> Ops; 1622 DIExpression::appendOffset(Ops, Offset); 1623 doSalvage(DII, Ops); 1624 }; 1625 1626 auto applyOps = [&](DbgInfoIntrinsic *DII, 1627 std::initializer_list<uint64_t> Opcodes) { 1628 SmallVector<uint64_t, 8> Ops(Opcodes); 1629 doSalvage(DII, Ops); 1630 }; 1631 1632 if (auto *CI = dyn_cast<CastInst>(&I)) { 1633 if (!CI->isNoopCast(DL)) 1634 return; 1635 1636 // No-op casts are irrelevant for debug info. 1637 MetadataAsValue *CastSrc = wrapMD(I.getOperand(0)); 1638 for (auto *DII : DbgUsers) { 1639 DII->setOperand(0, CastSrc); 1640 LLVM_DEBUG(dbgs() << "SALVAGE: " << *DII << '\n'); 1641 } 1642 } else if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) { 1643 unsigned BitWidth = 1644 M.getDataLayout().getIndexSizeInBits(GEP->getPointerAddressSpace()); 1645 // Rewrite a constant GEP into a DIExpression. Since we are performing 1646 // arithmetic to compute the variable's *value* in the DIExpression, we 1647 // need to mark the expression with a DW_OP_stack_value. 1648 APInt Offset(BitWidth, 0); 1649 if (GEP->accumulateConstantOffset(M.getDataLayout(), Offset)) 1650 for (auto *DII : DbgUsers) 1651 applyOffset(DII, Offset.getSExtValue()); 1652 } else if (auto *BI = dyn_cast<BinaryOperator>(&I)) { 1653 // Rewrite binary operations with constant integer operands. 1654 auto *ConstInt = dyn_cast<ConstantInt>(I.getOperand(1)); 1655 if (!ConstInt || ConstInt->getBitWidth() > 64) 1656 return; 1657 1658 uint64_t Val = ConstInt->getSExtValue(); 1659 for (auto *DII : DbgUsers) { 1660 switch (BI->getOpcode()) { 1661 case Instruction::Add: 1662 applyOffset(DII, Val); 1663 break; 1664 case Instruction::Sub: 1665 applyOffset(DII, -int64_t(Val)); 1666 break; 1667 case Instruction::Mul: 1668 applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_mul}); 1669 break; 1670 case Instruction::SDiv: 1671 applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_div}); 1672 break; 1673 case Instruction::SRem: 1674 applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_mod}); 1675 break; 1676 case Instruction::Or: 1677 applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_or}); 1678 break; 1679 case Instruction::And: 1680 applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_and}); 1681 break; 1682 case Instruction::Xor: 1683 applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_xor}); 1684 break; 1685 case Instruction::Shl: 1686 applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_shl}); 1687 break; 1688 case Instruction::LShr: 1689 applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_shr}); 1690 break; 1691 case Instruction::AShr: 1692 applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_shra}); 1693 break; 1694 default: 1695 // TODO: Salvage constants from each kind of binop we know about. 1696 continue; 1697 } 1698 } 1699 } else if (isa<LoadInst>(&I)) { 1700 MetadataAsValue *AddrMD = wrapMD(I.getOperand(0)); 1701 for (auto *DII : DbgUsers) { 1702 // Rewrite the load into DW_OP_deref. 1703 auto *DIExpr = DII->getExpression(); 1704 DIExpr = DIExpression::prepend(DIExpr, DIExpression::WithDeref); 1705 DII->setOperand(0, AddrMD); 1706 DII->setOperand(2, MetadataAsValue::get(I.getContext(), DIExpr)); 1707 LLVM_DEBUG(dbgs() << "SALVAGE: " << *DII << '\n'); 1708 } 1709 } 1710 } 1711 1712 void llvm::insertReplacementDbgValues( 1713 Value &From, Value &To, Instruction &InsertBefore, 1714 function_ref<DIExpression *(DbgInfoIntrinsic &OldDII)> RewriteExpr) { 1715 // Collect all debug users of From. 1716 SmallVector<DbgInfoIntrinsic *, 1> Users; 1717 findDbgUsers(Users, &From); 1718 if (Users.empty()) 1719 return; 1720 1721 // Insert a replacement debug value for each old debug user. It's assumed 1722 // that the old debug users will be erased later. 1723 DIBuilder DIB(*InsertBefore.getModule()); 1724 for (auto *OldDII : Users) 1725 if (DIExpression *Expr = RewriteExpr(*OldDII)) { 1726 auto *I = DIB.insertDbgValueIntrinsic(&To, OldDII->getVariable(), Expr, 1727 OldDII->getDebugLoc().get(), 1728 &InsertBefore); 1729 (void)I; 1730 LLVM_DEBUG(dbgs() << "REPLACE: " << *I << '\n'); 1731 } 1732 } 1733 1734 void llvm::insertReplacementDbgValues(Value &From, Value &To, 1735 Instruction &InsertBefore) { 1736 return llvm::insertReplacementDbgValues( 1737 From, To, InsertBefore, 1738 [](DbgInfoIntrinsic &OldDII) { return OldDII.getExpression(); }); 1739 } 1740 1741 unsigned llvm::removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB) { 1742 unsigned NumDeadInst = 0; 1743 // Delete the instructions backwards, as it has a reduced likelihood of 1744 // having to update as many def-use and use-def chains. 1745 Instruction *EndInst = BB->getTerminator(); // Last not to be deleted. 1746 while (EndInst != &BB->front()) { 1747 // Delete the next to last instruction. 1748 Instruction *Inst = &*--EndInst->getIterator(); 1749 if (!Inst->use_empty() && !Inst->getType()->isTokenTy()) 1750 Inst->replaceAllUsesWith(UndefValue::get(Inst->getType())); 1751 if (Inst->isEHPad() || Inst->getType()->isTokenTy()) { 1752 EndInst = Inst; 1753 continue; 1754 } 1755 if (!isa<DbgInfoIntrinsic>(Inst)) 1756 ++NumDeadInst; 1757 Inst->eraseFromParent(); 1758 } 1759 return NumDeadInst; 1760 } 1761 1762 unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap, 1763 bool PreserveLCSSA, DeferredDominance *DDT) { 1764 BasicBlock *BB = I->getParent(); 1765 std::vector <DominatorTree::UpdateType> Updates; 1766 1767 // Loop over all of the successors, removing BB's entry from any PHI 1768 // nodes. 1769 if (DDT) 1770 Updates.reserve(BB->getTerminator()->getNumSuccessors()); 1771 for (BasicBlock *Successor : successors(BB)) { 1772 Successor->removePredecessor(BB, PreserveLCSSA); 1773 if (DDT) 1774 Updates.push_back({DominatorTree::Delete, BB, Successor}); 1775 } 1776 // Insert a call to llvm.trap right before this. This turns the undefined 1777 // behavior into a hard fail instead of falling through into random code. 1778 if (UseLLVMTrap) { 1779 Function *TrapFn = 1780 Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap); 1781 CallInst *CallTrap = CallInst::Create(TrapFn, "", I); 1782 CallTrap->setDebugLoc(I->getDebugLoc()); 1783 } 1784 new UnreachableInst(I->getContext(), I); 1785 1786 // All instructions after this are dead. 1787 unsigned NumInstrsRemoved = 0; 1788 BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end(); 1789 while (BBI != BBE) { 1790 if (!BBI->use_empty()) 1791 BBI->replaceAllUsesWith(UndefValue::get(BBI->getType())); 1792 BB->getInstList().erase(BBI++); 1793 ++NumInstrsRemoved; 1794 } 1795 if (DDT) 1796 DDT->applyUpdates(Updates); 1797 return NumInstrsRemoved; 1798 } 1799 1800 /// changeToCall - Convert the specified invoke into a normal call. 1801 static void changeToCall(InvokeInst *II, DeferredDominance *DDT = nullptr) { 1802 SmallVector<Value*, 8> Args(II->arg_begin(), II->arg_end()); 1803 SmallVector<OperandBundleDef, 1> OpBundles; 1804 II->getOperandBundlesAsDefs(OpBundles); 1805 CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, OpBundles, 1806 "", II); 1807 NewCall->takeName(II); 1808 NewCall->setCallingConv(II->getCallingConv()); 1809 NewCall->setAttributes(II->getAttributes()); 1810 NewCall->setDebugLoc(II->getDebugLoc()); 1811 II->replaceAllUsesWith(NewCall); 1812 1813 // Follow the call by a branch to the normal destination. 1814 BasicBlock *NormalDestBB = II->getNormalDest(); 1815 BranchInst::Create(NormalDestBB, II); 1816 1817 // Update PHI nodes in the unwind destination 1818 BasicBlock *BB = II->getParent(); 1819 BasicBlock *UnwindDestBB = II->getUnwindDest(); 1820 UnwindDestBB->removePredecessor(BB); 1821 II->eraseFromParent(); 1822 if (DDT) 1823 DDT->deleteEdge(BB, UnwindDestBB); 1824 } 1825 1826 BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI, 1827 BasicBlock *UnwindEdge) { 1828 BasicBlock *BB = CI->getParent(); 1829 1830 // Convert this function call into an invoke instruction. First, split the 1831 // basic block. 1832 BasicBlock *Split = 1833 BB->splitBasicBlock(CI->getIterator(), CI->getName() + ".noexc"); 1834 1835 // Delete the unconditional branch inserted by splitBasicBlock 1836 BB->getInstList().pop_back(); 1837 1838 // Create the new invoke instruction. 1839 SmallVector<Value *, 8> InvokeArgs(CI->arg_begin(), CI->arg_end()); 1840 SmallVector<OperandBundleDef, 1> OpBundles; 1841 1842 CI->getOperandBundlesAsDefs(OpBundles); 1843 1844 // Note: we're round tripping operand bundles through memory here, and that 1845 // can potentially be avoided with a cleverer API design that we do not have 1846 // as of this time. 1847 1848 InvokeInst *II = InvokeInst::Create(CI->getCalledValue(), Split, UnwindEdge, 1849 InvokeArgs, OpBundles, CI->getName(), BB); 1850 II->setDebugLoc(CI->getDebugLoc()); 1851 II->setCallingConv(CI->getCallingConv()); 1852 II->setAttributes(CI->getAttributes()); 1853 1854 // Make sure that anything using the call now uses the invoke! This also 1855 // updates the CallGraph if present, because it uses a WeakTrackingVH. 1856 CI->replaceAllUsesWith(II); 1857 1858 // Delete the original call 1859 Split->getInstList().pop_front(); 1860 return Split; 1861 } 1862 1863 static bool markAliveBlocks(Function &F, 1864 SmallPtrSetImpl<BasicBlock*> &Reachable, 1865 DeferredDominance *DDT = nullptr) { 1866 SmallVector<BasicBlock*, 128> Worklist; 1867 BasicBlock *BB = &F.front(); 1868 Worklist.push_back(BB); 1869 Reachable.insert(BB); 1870 bool Changed = false; 1871 do { 1872 BB = Worklist.pop_back_val(); 1873 1874 // Do a quick scan of the basic block, turning any obviously unreachable 1875 // instructions into LLVM unreachable insts. The instruction combining pass 1876 // canonicalizes unreachable insts into stores to null or undef. 1877 for (Instruction &I : *BB) { 1878 // Assumptions that are known to be false are equivalent to unreachable. 1879 // Also, if the condition is undefined, then we make the choice most 1880 // beneficial to the optimizer, and choose that to also be unreachable. 1881 if (auto *II = dyn_cast<IntrinsicInst>(&I)) { 1882 if (II->getIntrinsicID() == Intrinsic::assume) { 1883 if (match(II->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) { 1884 // Don't insert a call to llvm.trap right before the unreachable. 1885 changeToUnreachable(II, false, false, DDT); 1886 Changed = true; 1887 break; 1888 } 1889 } 1890 1891 if (II->getIntrinsicID() == Intrinsic::experimental_guard) { 1892 // A call to the guard intrinsic bails out of the current compilation 1893 // unit if the predicate passed to it is false. If the predicate is a 1894 // constant false, then we know the guard will bail out of the current 1895 // compile unconditionally, so all code following it is dead. 1896 // 1897 // Note: unlike in llvm.assume, it is not "obviously profitable" for 1898 // guards to treat `undef` as `false` since a guard on `undef` can 1899 // still be useful for widening. 1900 if (match(II->getArgOperand(0), m_Zero())) 1901 if (!isa<UnreachableInst>(II->getNextNode())) { 1902 changeToUnreachable(II->getNextNode(), /*UseLLVMTrap=*/false, 1903 false, DDT); 1904 Changed = true; 1905 break; 1906 } 1907 } 1908 } 1909 1910 if (auto *CI = dyn_cast<CallInst>(&I)) { 1911 Value *Callee = CI->getCalledValue(); 1912 if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) { 1913 changeToUnreachable(CI, /*UseLLVMTrap=*/false, false, DDT); 1914 Changed = true; 1915 break; 1916 } 1917 if (CI->doesNotReturn()) { 1918 // If we found a call to a no-return function, insert an unreachable 1919 // instruction after it. Make sure there isn't *already* one there 1920 // though. 1921 if (!isa<UnreachableInst>(CI->getNextNode())) { 1922 // Don't insert a call to llvm.trap right before the unreachable. 1923 changeToUnreachable(CI->getNextNode(), false, false, DDT); 1924 Changed = true; 1925 } 1926 break; 1927 } 1928 } 1929 1930 // Store to undef and store to null are undefined and used to signal that 1931 // they should be changed to unreachable by passes that can't modify the 1932 // CFG. 1933 if (auto *SI = dyn_cast<StoreInst>(&I)) { 1934 // Don't touch volatile stores. 1935 if (SI->isVolatile()) continue; 1936 1937 Value *Ptr = SI->getOperand(1); 1938 1939 if (isa<UndefValue>(Ptr) || 1940 (isa<ConstantPointerNull>(Ptr) && 1941 SI->getPointerAddressSpace() == 0)) { 1942 changeToUnreachable(SI, true, false, DDT); 1943 Changed = true; 1944 break; 1945 } 1946 } 1947 } 1948 1949 TerminatorInst *Terminator = BB->getTerminator(); 1950 if (auto *II = dyn_cast<InvokeInst>(Terminator)) { 1951 // Turn invokes that call 'nounwind' functions into ordinary calls. 1952 Value *Callee = II->getCalledValue(); 1953 if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) { 1954 changeToUnreachable(II, true, false, DDT); 1955 Changed = true; 1956 } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) { 1957 if (II->use_empty() && II->onlyReadsMemory()) { 1958 // jump to the normal destination branch. 1959 BasicBlock *NormalDestBB = II->getNormalDest(); 1960 BasicBlock *UnwindDestBB = II->getUnwindDest(); 1961 BranchInst::Create(NormalDestBB, II); 1962 UnwindDestBB->removePredecessor(II->getParent()); 1963 II->eraseFromParent(); 1964 if (DDT) 1965 DDT->deleteEdge(BB, UnwindDestBB); 1966 } else 1967 changeToCall(II, DDT); 1968 Changed = true; 1969 } 1970 } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) { 1971 // Remove catchpads which cannot be reached. 1972 struct CatchPadDenseMapInfo { 1973 static CatchPadInst *getEmptyKey() { 1974 return DenseMapInfo<CatchPadInst *>::getEmptyKey(); 1975 } 1976 1977 static CatchPadInst *getTombstoneKey() { 1978 return DenseMapInfo<CatchPadInst *>::getTombstoneKey(); 1979 } 1980 1981 static unsigned getHashValue(CatchPadInst *CatchPad) { 1982 return static_cast<unsigned>(hash_combine_range( 1983 CatchPad->value_op_begin(), CatchPad->value_op_end())); 1984 } 1985 1986 static bool isEqual(CatchPadInst *LHS, CatchPadInst *RHS) { 1987 if (LHS == getEmptyKey() || LHS == getTombstoneKey() || 1988 RHS == getEmptyKey() || RHS == getTombstoneKey()) 1989 return LHS == RHS; 1990 return LHS->isIdenticalTo(RHS); 1991 } 1992 }; 1993 1994 // Set of unique CatchPads. 1995 SmallDenseMap<CatchPadInst *, detail::DenseSetEmpty, 4, 1996 CatchPadDenseMapInfo, detail::DenseSetPair<CatchPadInst *>> 1997 HandlerSet; 1998 detail::DenseSetEmpty Empty; 1999 for (CatchSwitchInst::handler_iterator I = CatchSwitch->handler_begin(), 2000 E = CatchSwitch->handler_end(); 2001 I != E; ++I) { 2002 BasicBlock *HandlerBB = *I; 2003 auto *CatchPad = cast<CatchPadInst>(HandlerBB->getFirstNonPHI()); 2004 if (!HandlerSet.insert({CatchPad, Empty}).second) { 2005 CatchSwitch->removeHandler(I); 2006 --I; 2007 --E; 2008 Changed = true; 2009 } 2010 } 2011 } 2012 2013 Changed |= ConstantFoldTerminator(BB, true, nullptr, DDT); 2014 for (BasicBlock *Successor : successors(BB)) 2015 if (Reachable.insert(Successor).second) 2016 Worklist.push_back(Successor); 2017 } while (!Worklist.empty()); 2018 return Changed; 2019 } 2020 2021 void llvm::removeUnwindEdge(BasicBlock *BB, DeferredDominance *DDT) { 2022 TerminatorInst *TI = BB->getTerminator(); 2023 2024 if (auto *II = dyn_cast<InvokeInst>(TI)) { 2025 changeToCall(II, DDT); 2026 return; 2027 } 2028 2029 TerminatorInst *NewTI; 2030 BasicBlock *UnwindDest; 2031 2032 if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) { 2033 NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI); 2034 UnwindDest = CRI->getUnwindDest(); 2035 } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) { 2036 auto *NewCatchSwitch = CatchSwitchInst::Create( 2037 CatchSwitch->getParentPad(), nullptr, CatchSwitch->getNumHandlers(), 2038 CatchSwitch->getName(), CatchSwitch); 2039 for (BasicBlock *PadBB : CatchSwitch->handlers()) 2040 NewCatchSwitch->addHandler(PadBB); 2041 2042 NewTI = NewCatchSwitch; 2043 UnwindDest = CatchSwitch->getUnwindDest(); 2044 } else { 2045 llvm_unreachable("Could not find unwind successor"); 2046 } 2047 2048 NewTI->takeName(TI); 2049 NewTI->setDebugLoc(TI->getDebugLoc()); 2050 UnwindDest->removePredecessor(BB); 2051 TI->replaceAllUsesWith(NewTI); 2052 TI->eraseFromParent(); 2053 if (DDT) 2054 DDT->deleteEdge(BB, UnwindDest); 2055 } 2056 2057 /// removeUnreachableBlocks - Remove blocks that are not reachable, even 2058 /// if they are in a dead cycle. Return true if a change was made, false 2059 /// otherwise. If `LVI` is passed, this function preserves LazyValueInfo 2060 /// after modifying the CFG. 2061 bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI, 2062 DeferredDominance *DDT) { 2063 SmallPtrSet<BasicBlock*, 16> Reachable; 2064 bool Changed = markAliveBlocks(F, Reachable, DDT); 2065 2066 // If there are unreachable blocks in the CFG... 2067 if (Reachable.size() == F.size()) 2068 return Changed; 2069 2070 assert(Reachable.size() < F.size()); 2071 NumRemoved += F.size()-Reachable.size(); 2072 2073 // Loop over all of the basic blocks that are not reachable, dropping all of 2074 // their internal references. Update DDT and LVI if available. 2075 std::vector <DominatorTree::UpdateType> Updates; 2076 for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ++I) { 2077 auto *BB = &*I; 2078 if (Reachable.count(BB)) 2079 continue; 2080 for (BasicBlock *Successor : successors(BB)) { 2081 if (Reachable.count(Successor)) 2082 Successor->removePredecessor(BB); 2083 if (DDT) 2084 Updates.push_back({DominatorTree::Delete, BB, Successor}); 2085 } 2086 if (LVI) 2087 LVI->eraseBlock(BB); 2088 BB->dropAllReferences(); 2089 } 2090 2091 for (Function::iterator I = ++F.begin(); I != F.end();) { 2092 auto *BB = &*I; 2093 if (Reachable.count(BB)) { 2094 ++I; 2095 continue; 2096 } 2097 if (DDT) { 2098 DDT->deleteBB(BB); // deferred deletion of BB. 2099 ++I; 2100 } else { 2101 I = F.getBasicBlockList().erase(I); 2102 } 2103 } 2104 2105 if (DDT) 2106 DDT->applyUpdates(Updates); 2107 return true; 2108 } 2109 2110 void llvm::combineMetadata(Instruction *K, const Instruction *J, 2111 ArrayRef<unsigned> KnownIDs) { 2112 SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata; 2113 K->dropUnknownNonDebugMetadata(KnownIDs); 2114 K->getAllMetadataOtherThanDebugLoc(Metadata); 2115 for (const auto &MD : Metadata) { 2116 unsigned Kind = MD.first; 2117 MDNode *JMD = J->getMetadata(Kind); 2118 MDNode *KMD = MD.second; 2119 2120 switch (Kind) { 2121 default: 2122 K->setMetadata(Kind, nullptr); // Remove unknown metadata 2123 break; 2124 case LLVMContext::MD_dbg: 2125 llvm_unreachable("getAllMetadataOtherThanDebugLoc returned a MD_dbg"); 2126 case LLVMContext::MD_tbaa: 2127 K->setMetadata(Kind, MDNode::getMostGenericTBAA(JMD, KMD)); 2128 break; 2129 case LLVMContext::MD_alias_scope: 2130 K->setMetadata(Kind, MDNode::getMostGenericAliasScope(JMD, KMD)); 2131 break; 2132 case LLVMContext::MD_noalias: 2133 case LLVMContext::MD_mem_parallel_loop_access: 2134 K->setMetadata(Kind, MDNode::intersect(JMD, KMD)); 2135 break; 2136 case LLVMContext::MD_range: 2137 K->setMetadata(Kind, MDNode::getMostGenericRange(JMD, KMD)); 2138 break; 2139 case LLVMContext::MD_fpmath: 2140 K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD)); 2141 break; 2142 case LLVMContext::MD_invariant_load: 2143 // Only set the !invariant.load if it is present in both instructions. 2144 K->setMetadata(Kind, JMD); 2145 break; 2146 case LLVMContext::MD_nonnull: 2147 // Only set the !nonnull if it is present in both instructions. 2148 K->setMetadata(Kind, JMD); 2149 break; 2150 case LLVMContext::MD_invariant_group: 2151 // Preserve !invariant.group in K. 2152 break; 2153 case LLVMContext::MD_align: 2154 K->setMetadata(Kind, 2155 MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD)); 2156 break; 2157 case LLVMContext::MD_dereferenceable: 2158 case LLVMContext::MD_dereferenceable_or_null: 2159 K->setMetadata(Kind, 2160 MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD)); 2161 break; 2162 } 2163 } 2164 // Set !invariant.group from J if J has it. If both instructions have it 2165 // then we will just pick it from J - even when they are different. 2166 // Also make sure that K is load or store - f.e. combining bitcast with load 2167 // could produce bitcast with invariant.group metadata, which is invalid. 2168 // FIXME: we should try to preserve both invariant.group md if they are 2169 // different, but right now instruction can only have one invariant.group. 2170 if (auto *JMD = J->getMetadata(LLVMContext::MD_invariant_group)) 2171 if (isa<LoadInst>(K) || isa<StoreInst>(K)) 2172 K->setMetadata(LLVMContext::MD_invariant_group, JMD); 2173 } 2174 2175 void llvm::combineMetadataForCSE(Instruction *K, const Instruction *J) { 2176 unsigned KnownIDs[] = { 2177 LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope, 2178 LLVMContext::MD_noalias, LLVMContext::MD_range, 2179 LLVMContext::MD_invariant_load, LLVMContext::MD_nonnull, 2180 LLVMContext::MD_invariant_group, LLVMContext::MD_align, 2181 LLVMContext::MD_dereferenceable, 2182 LLVMContext::MD_dereferenceable_or_null}; 2183 combineMetadata(K, J, KnownIDs); 2184 } 2185 2186 template <typename RootType, typename DominatesFn> 2187 static unsigned replaceDominatedUsesWith(Value *From, Value *To, 2188 const RootType &Root, 2189 const DominatesFn &Dominates) { 2190 assert(From->getType() == To->getType()); 2191 2192 unsigned Count = 0; 2193 for (Value::use_iterator UI = From->use_begin(), UE = From->use_end(); 2194 UI != UE;) { 2195 Use &U = *UI++; 2196 if (!Dominates(Root, U)) 2197 continue; 2198 U.set(To); 2199 LLVM_DEBUG(dbgs() << "Replace dominated use of '" << From->getName() 2200 << "' as " << *To << " in " << *U << "\n"); 2201 ++Count; 2202 } 2203 return Count; 2204 } 2205 2206 unsigned llvm::replaceNonLocalUsesWith(Instruction *From, Value *To) { 2207 assert(From->getType() == To->getType()); 2208 auto *BB = From->getParent(); 2209 unsigned Count = 0; 2210 2211 for (Value::use_iterator UI = From->use_begin(), UE = From->use_end(); 2212 UI != UE;) { 2213 Use &U = *UI++; 2214 auto *I = cast<Instruction>(U.getUser()); 2215 if (I->getParent() == BB) 2216 continue; 2217 U.set(To); 2218 ++Count; 2219 } 2220 return Count; 2221 } 2222 2223 unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To, 2224 DominatorTree &DT, 2225 const BasicBlockEdge &Root) { 2226 auto Dominates = [&DT](const BasicBlockEdge &Root, const Use &U) { 2227 return DT.dominates(Root, U); 2228 }; 2229 return ::replaceDominatedUsesWith(From, To, Root, Dominates); 2230 } 2231 2232 unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To, 2233 DominatorTree &DT, 2234 const BasicBlock *BB) { 2235 auto ProperlyDominates = [&DT](const BasicBlock *BB, const Use &U) { 2236 auto *I = cast<Instruction>(U.getUser())->getParent(); 2237 return DT.properlyDominates(BB, I); 2238 }; 2239 return ::replaceDominatedUsesWith(From, To, BB, ProperlyDominates); 2240 } 2241 2242 bool llvm::callsGCLeafFunction(ImmutableCallSite CS, 2243 const TargetLibraryInfo &TLI) { 2244 // Check if the function is specifically marked as a gc leaf function. 2245 if (CS.hasFnAttr("gc-leaf-function")) 2246 return true; 2247 if (const Function *F = CS.getCalledFunction()) { 2248 if (F->hasFnAttribute("gc-leaf-function")) 2249 return true; 2250 2251 if (auto IID = F->getIntrinsicID()) 2252 // Most LLVM intrinsics do not take safepoints. 2253 return IID != Intrinsic::experimental_gc_statepoint && 2254 IID != Intrinsic::experimental_deoptimize; 2255 } 2256 2257 // Lib calls can be materialized by some passes, and won't be 2258 // marked as 'gc-leaf-function.' All available Libcalls are 2259 // GC-leaf. 2260 LibFunc LF; 2261 if (TLI.getLibFunc(CS, LF)) { 2262 return TLI.has(LF); 2263 } 2264 2265 return false; 2266 } 2267 2268 void llvm::copyNonnullMetadata(const LoadInst &OldLI, MDNode *N, 2269 LoadInst &NewLI) { 2270 auto *NewTy = NewLI.getType(); 2271 2272 // This only directly applies if the new type is also a pointer. 2273 if (NewTy->isPointerTy()) { 2274 NewLI.setMetadata(LLVMContext::MD_nonnull, N); 2275 return; 2276 } 2277 2278 // The only other translation we can do is to integral loads with !range 2279 // metadata. 2280 if (!NewTy->isIntegerTy()) 2281 return; 2282 2283 MDBuilder MDB(NewLI.getContext()); 2284 const Value *Ptr = OldLI.getPointerOperand(); 2285 auto *ITy = cast<IntegerType>(NewTy); 2286 auto *NullInt = ConstantExpr::getPtrToInt( 2287 ConstantPointerNull::get(cast<PointerType>(Ptr->getType())), ITy); 2288 auto *NonNullInt = ConstantExpr::getAdd(NullInt, ConstantInt::get(ITy, 1)); 2289 NewLI.setMetadata(LLVMContext::MD_range, 2290 MDB.createRange(NonNullInt, NullInt)); 2291 } 2292 2293 void llvm::copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI, 2294 MDNode *N, LoadInst &NewLI) { 2295 auto *NewTy = NewLI.getType(); 2296 2297 // Give up unless it is converted to a pointer where there is a single very 2298 // valuable mapping we can do reliably. 2299 // FIXME: It would be nice to propagate this in more ways, but the type 2300 // conversions make it hard. 2301 if (!NewTy->isPointerTy()) 2302 return; 2303 2304 unsigned BitWidth = DL.getIndexTypeSizeInBits(NewTy); 2305 if (!getConstantRangeFromMetadata(*N).contains(APInt(BitWidth, 0))) { 2306 MDNode *NN = MDNode::get(OldLI.getContext(), None); 2307 NewLI.setMetadata(LLVMContext::MD_nonnull, NN); 2308 } 2309 } 2310 2311 namespace { 2312 2313 /// A potential constituent of a bitreverse or bswap expression. See 2314 /// collectBitParts for a fuller explanation. 2315 struct BitPart { 2316 BitPart(Value *P, unsigned BW) : Provider(P) { 2317 Provenance.resize(BW); 2318 } 2319 2320 /// The Value that this is a bitreverse/bswap of. 2321 Value *Provider; 2322 2323 /// The "provenance" of each bit. Provenance[A] = B means that bit A 2324 /// in Provider becomes bit B in the result of this expression. 2325 SmallVector<int8_t, 32> Provenance; // int8_t means max size is i128. 2326 2327 enum { Unset = -1 }; 2328 }; 2329 2330 } // end anonymous namespace 2331 2332 /// Analyze the specified subexpression and see if it is capable of providing 2333 /// pieces of a bswap or bitreverse. The subexpression provides a potential 2334 /// piece of a bswap or bitreverse if it can be proven that each non-zero bit in 2335 /// the output of the expression came from a corresponding bit in some other 2336 /// value. This function is recursive, and the end result is a mapping of 2337 /// bitnumber to bitnumber. It is the caller's responsibility to validate that 2338 /// the bitnumber to bitnumber mapping is correct for a bswap or bitreverse. 2339 /// 2340 /// For example, if the current subexpression if "(shl i32 %X, 24)" then we know 2341 /// that the expression deposits the low byte of %X into the high byte of the 2342 /// result and that all other bits are zero. This expression is accepted and a 2343 /// BitPart is returned with Provider set to %X and Provenance[24-31] set to 2344 /// [0-7]. 2345 /// 2346 /// To avoid revisiting values, the BitPart results are memoized into the 2347 /// provided map. To avoid unnecessary copying of BitParts, BitParts are 2348 /// constructed in-place in the \c BPS map. Because of this \c BPS needs to 2349 /// store BitParts objects, not pointers. As we need the concept of a nullptr 2350 /// BitParts (Value has been analyzed and the analysis failed), we an Optional 2351 /// type instead to provide the same functionality. 2352 /// 2353 /// Because we pass around references into \c BPS, we must use a container that 2354 /// does not invalidate internal references (std::map instead of DenseMap). 2355 static const Optional<BitPart> & 2356 collectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals, 2357 std::map<Value *, Optional<BitPart>> &BPS) { 2358 auto I = BPS.find(V); 2359 if (I != BPS.end()) 2360 return I->second; 2361 2362 auto &Result = BPS[V] = None; 2363 auto BitWidth = cast<IntegerType>(V->getType())->getBitWidth(); 2364 2365 if (Instruction *I = dyn_cast<Instruction>(V)) { 2366 // If this is an or instruction, it may be an inner node of the bswap. 2367 if (I->getOpcode() == Instruction::Or) { 2368 auto &A = collectBitParts(I->getOperand(0), MatchBSwaps, 2369 MatchBitReversals, BPS); 2370 auto &B = collectBitParts(I->getOperand(1), MatchBSwaps, 2371 MatchBitReversals, BPS); 2372 if (!A || !B) 2373 return Result; 2374 2375 // Try and merge the two together. 2376 if (!A->Provider || A->Provider != B->Provider) 2377 return Result; 2378 2379 Result = BitPart(A->Provider, BitWidth); 2380 for (unsigned i = 0; i < A->Provenance.size(); ++i) { 2381 if (A->Provenance[i] != BitPart::Unset && 2382 B->Provenance[i] != BitPart::Unset && 2383 A->Provenance[i] != B->Provenance[i]) 2384 return Result = None; 2385 2386 if (A->Provenance[i] == BitPart::Unset) 2387 Result->Provenance[i] = B->Provenance[i]; 2388 else 2389 Result->Provenance[i] = A->Provenance[i]; 2390 } 2391 2392 return Result; 2393 } 2394 2395 // If this is a logical shift by a constant, recurse then shift the result. 2396 if (I->isLogicalShift() && isa<ConstantInt>(I->getOperand(1))) { 2397 unsigned BitShift = 2398 cast<ConstantInt>(I->getOperand(1))->getLimitedValue(~0U); 2399 // Ensure the shift amount is defined. 2400 if (BitShift > BitWidth) 2401 return Result; 2402 2403 auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps, 2404 MatchBitReversals, BPS); 2405 if (!Res) 2406 return Result; 2407 Result = Res; 2408 2409 // Perform the "shift" on BitProvenance. 2410 auto &P = Result->Provenance; 2411 if (I->getOpcode() == Instruction::Shl) { 2412 P.erase(std::prev(P.end(), BitShift), P.end()); 2413 P.insert(P.begin(), BitShift, BitPart::Unset); 2414 } else { 2415 P.erase(P.begin(), std::next(P.begin(), BitShift)); 2416 P.insert(P.end(), BitShift, BitPart::Unset); 2417 } 2418 2419 return Result; 2420 } 2421 2422 // If this is a logical 'and' with a mask that clears bits, recurse then 2423 // unset the appropriate bits. 2424 if (I->getOpcode() == Instruction::And && 2425 isa<ConstantInt>(I->getOperand(1))) { 2426 APInt Bit(I->getType()->getPrimitiveSizeInBits(), 1); 2427 const APInt &AndMask = cast<ConstantInt>(I->getOperand(1))->getValue(); 2428 2429 // Check that the mask allows a multiple of 8 bits for a bswap, for an 2430 // early exit. 2431 unsigned NumMaskedBits = AndMask.countPopulation(); 2432 if (!MatchBitReversals && NumMaskedBits % 8 != 0) 2433 return Result; 2434 2435 auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps, 2436 MatchBitReversals, BPS); 2437 if (!Res) 2438 return Result; 2439 Result = Res; 2440 2441 for (unsigned i = 0; i < BitWidth; ++i, Bit <<= 1) 2442 // If the AndMask is zero for this bit, clear the bit. 2443 if ((AndMask & Bit) == 0) 2444 Result->Provenance[i] = BitPart::Unset; 2445 return Result; 2446 } 2447 2448 // If this is a zext instruction zero extend the result. 2449 if (I->getOpcode() == Instruction::ZExt) { 2450 auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps, 2451 MatchBitReversals, BPS); 2452 if (!Res) 2453 return Result; 2454 2455 Result = BitPart(Res->Provider, BitWidth); 2456 auto NarrowBitWidth = 2457 cast<IntegerType>(cast<ZExtInst>(I)->getSrcTy())->getBitWidth(); 2458 for (unsigned i = 0; i < NarrowBitWidth; ++i) 2459 Result->Provenance[i] = Res->Provenance[i]; 2460 for (unsigned i = NarrowBitWidth; i < BitWidth; ++i) 2461 Result->Provenance[i] = BitPart::Unset; 2462 return Result; 2463 } 2464 } 2465 2466 // Okay, we got to something that isn't a shift, 'or' or 'and'. This must be 2467 // the input value to the bswap/bitreverse. 2468 Result = BitPart(V, BitWidth); 2469 for (unsigned i = 0; i < BitWidth; ++i) 2470 Result->Provenance[i] = i; 2471 return Result; 2472 } 2473 2474 static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To, 2475 unsigned BitWidth) { 2476 if (From % 8 != To % 8) 2477 return false; 2478 // Convert from bit indices to byte indices and check for a byte reversal. 2479 From >>= 3; 2480 To >>= 3; 2481 BitWidth >>= 3; 2482 return From == BitWidth - To - 1; 2483 } 2484 2485 static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To, 2486 unsigned BitWidth) { 2487 return From == BitWidth - To - 1; 2488 } 2489 2490 bool llvm::recognizeBSwapOrBitReverseIdiom( 2491 Instruction *I, bool MatchBSwaps, bool MatchBitReversals, 2492 SmallVectorImpl<Instruction *> &InsertedInsts) { 2493 if (Operator::getOpcode(I) != Instruction::Or) 2494 return false; 2495 if (!MatchBSwaps && !MatchBitReversals) 2496 return false; 2497 IntegerType *ITy = dyn_cast<IntegerType>(I->getType()); 2498 if (!ITy || ITy->getBitWidth() > 128) 2499 return false; // Can't do vectors or integers > 128 bits. 2500 unsigned BW = ITy->getBitWidth(); 2501 2502 unsigned DemandedBW = BW; 2503 IntegerType *DemandedTy = ITy; 2504 if (I->hasOneUse()) { 2505 if (TruncInst *Trunc = dyn_cast<TruncInst>(I->user_back())) { 2506 DemandedTy = cast<IntegerType>(Trunc->getType()); 2507 DemandedBW = DemandedTy->getBitWidth(); 2508 } 2509 } 2510 2511 // Try to find all the pieces corresponding to the bswap. 2512 std::map<Value *, Optional<BitPart>> BPS; 2513 auto Res = collectBitParts(I, MatchBSwaps, MatchBitReversals, BPS); 2514 if (!Res) 2515 return false; 2516 auto &BitProvenance = Res->Provenance; 2517 2518 // Now, is the bit permutation correct for a bswap or a bitreverse? We can 2519 // only byteswap values with an even number of bytes. 2520 bool OKForBSwap = DemandedBW % 16 == 0, OKForBitReverse = true; 2521 for (unsigned i = 0; i < DemandedBW; ++i) { 2522 OKForBSwap &= 2523 bitTransformIsCorrectForBSwap(BitProvenance[i], i, DemandedBW); 2524 OKForBitReverse &= 2525 bitTransformIsCorrectForBitReverse(BitProvenance[i], i, DemandedBW); 2526 } 2527 2528 Intrinsic::ID Intrin; 2529 if (OKForBSwap && MatchBSwaps) 2530 Intrin = Intrinsic::bswap; 2531 else if (OKForBitReverse && MatchBitReversals) 2532 Intrin = Intrinsic::bitreverse; 2533 else 2534 return false; 2535 2536 if (ITy != DemandedTy) { 2537 Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, DemandedTy); 2538 Value *Provider = Res->Provider; 2539 IntegerType *ProviderTy = cast<IntegerType>(Provider->getType()); 2540 // We may need to truncate the provider. 2541 if (DemandedTy != ProviderTy) { 2542 auto *Trunc = CastInst::Create(Instruction::Trunc, Provider, DemandedTy, 2543 "trunc", I); 2544 InsertedInsts.push_back(Trunc); 2545 Provider = Trunc; 2546 } 2547 auto *CI = CallInst::Create(F, Provider, "rev", I); 2548 InsertedInsts.push_back(CI); 2549 auto *ExtInst = CastInst::Create(Instruction::ZExt, CI, ITy, "zext", I); 2550 InsertedInsts.push_back(ExtInst); 2551 return true; 2552 } 2553 2554 Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, ITy); 2555 InsertedInsts.push_back(CallInst::Create(F, Res->Provider, "rev", I)); 2556 return true; 2557 } 2558 2559 // CodeGen has special handling for some string functions that may replace 2560 // them with target-specific intrinsics. Since that'd skip our interceptors 2561 // in ASan/MSan/TSan/DFSan, and thus make us miss some memory accesses, 2562 // we mark affected calls as NoBuiltin, which will disable optimization 2563 // in CodeGen. 2564 void llvm::maybeMarkSanitizerLibraryCallNoBuiltin( 2565 CallInst *CI, const TargetLibraryInfo *TLI) { 2566 Function *F = CI->getCalledFunction(); 2567 LibFunc Func; 2568 if (F && !F->hasLocalLinkage() && F->hasName() && 2569 TLI->getLibFunc(F->getName(), Func) && TLI->hasOptimizedCodeGen(Func) && 2570 !F->doesNotAccessMemory()) 2571 CI->addAttribute(AttributeList::FunctionIndex, Attribute::NoBuiltin); 2572 } 2573 2574 bool llvm::canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx) { 2575 // We can't have a PHI with a metadata type. 2576 if (I->getOperand(OpIdx)->getType()->isMetadataTy()) 2577 return false; 2578 2579 // Early exit. 2580 if (!isa<Constant>(I->getOperand(OpIdx))) 2581 return true; 2582 2583 switch (I->getOpcode()) { 2584 default: 2585 return true; 2586 case Instruction::Call: 2587 case Instruction::Invoke: 2588 // Can't handle inline asm. Skip it. 2589 if (isa<InlineAsm>(ImmutableCallSite(I).getCalledValue())) 2590 return false; 2591 // Many arithmetic intrinsics have no issue taking a 2592 // variable, however it's hard to distingish these from 2593 // specials such as @llvm.frameaddress that require a constant. 2594 if (isa<IntrinsicInst>(I)) 2595 return false; 2596 2597 // Constant bundle operands may need to retain their constant-ness for 2598 // correctness. 2599 if (ImmutableCallSite(I).isBundleOperand(OpIdx)) 2600 return false; 2601 return true; 2602 case Instruction::ShuffleVector: 2603 // Shufflevector masks are constant. 2604 return OpIdx != 2; 2605 case Instruction::Switch: 2606 case Instruction::ExtractValue: 2607 // All operands apart from the first are constant. 2608 return OpIdx == 0; 2609 case Instruction::InsertValue: 2610 // All operands apart from the first and the second are constant. 2611 return OpIdx < 2; 2612 case Instruction::Alloca: 2613 // Static allocas (constant size in the entry block) are handled by 2614 // prologue/epilogue insertion so they're free anyway. We definitely don't 2615 // want to make them non-constant. 2616 return !cast<AllocaInst>(I)->isStaticAlloca(); 2617 case Instruction::GetElementPtr: 2618 if (OpIdx == 0) 2619 return true; 2620 gep_type_iterator It = gep_type_begin(I); 2621 for (auto E = std::next(It, OpIdx); It != E; ++It) 2622 if (It.isStruct()) 2623 return false; 2624 return true; 2625 } 2626 } 2627