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/DenseMap.h" 17 #include "llvm/ADT/STLExtras.h" 18 #include "llvm/ADT/SmallPtrSet.h" 19 #include "llvm/ADT/Statistic.h" 20 #include "llvm/Analysis/LibCallSemantics.h" 21 #include "llvm/Analysis/InstructionSimplify.h" 22 #include "llvm/Analysis/MemoryBuiltins.h" 23 #include "llvm/Analysis/ValueTracking.h" 24 #include "llvm/IR/CFG.h" 25 #include "llvm/IR/Constants.h" 26 #include "llvm/IR/DIBuilder.h" 27 #include "llvm/IR/DataLayout.h" 28 #include "llvm/IR/DebugInfo.h" 29 #include "llvm/IR/DerivedTypes.h" 30 #include "llvm/IR/Dominators.h" 31 #include "llvm/IR/GetElementPtrTypeIterator.h" 32 #include "llvm/IR/GlobalAlias.h" 33 #include "llvm/IR/GlobalVariable.h" 34 #include "llvm/IR/IRBuilder.h" 35 #include "llvm/IR/Instructions.h" 36 #include "llvm/IR/IntrinsicInst.h" 37 #include "llvm/IR/Intrinsics.h" 38 #include "llvm/IR/MDBuilder.h" 39 #include "llvm/IR/Metadata.h" 40 #include "llvm/IR/Operator.h" 41 #include "llvm/IR/ValueHandle.h" 42 #include "llvm/Support/Debug.h" 43 #include "llvm/Support/MathExtras.h" 44 #include "llvm/Support/raw_ostream.h" 45 using namespace llvm; 46 47 #define DEBUG_TYPE "local" 48 49 STATISTIC(NumRemoved, "Number of unreachable basic blocks removed"); 50 51 //===----------------------------------------------------------------------===// 52 // Local constant propagation. 53 // 54 55 /// ConstantFoldTerminator - If a terminator instruction is predicated on a 56 /// constant value, convert it into an unconditional branch to the constant 57 /// destination. This is a nontrivial operation because the successors of this 58 /// basic block must have their PHI nodes updated. 59 /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch 60 /// conditions and indirectbr addresses this might make dead if 61 /// DeleteDeadConditions is true. 62 bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, 63 const TargetLibraryInfo *TLI) { 64 TerminatorInst *T = BB->getTerminator(); 65 IRBuilder<> Builder(T); 66 67 // Branch - See if we are conditional jumping on constant 68 if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 69 if (BI->isUnconditional()) return false; // Can't optimize uncond branch 70 BasicBlock *Dest1 = BI->getSuccessor(0); 71 BasicBlock *Dest2 = BI->getSuccessor(1); 72 73 if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) { 74 // Are we branching on constant? 75 // YES. Change to unconditional branch... 76 BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2; 77 BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1; 78 79 //cerr << "Function: " << T->getParent()->getParent() 80 // << "\nRemoving branch from " << T->getParent() 81 // << "\n\nTo: " << OldDest << endl; 82 83 // Let the basic block know that we are letting go of it. Based on this, 84 // it will adjust it's PHI nodes. 85 OldDest->removePredecessor(BB); 86 87 // Replace the conditional branch with an unconditional one. 88 Builder.CreateBr(Destination); 89 BI->eraseFromParent(); 90 return true; 91 } 92 93 if (Dest2 == Dest1) { // Conditional branch to same location? 94 // This branch matches something like this: 95 // br bool %cond, label %Dest, label %Dest 96 // and changes it into: br label %Dest 97 98 // Let the basic block know that we are letting go of one copy of it. 99 assert(BI->getParent() && "Terminator not inserted in block!"); 100 Dest1->removePredecessor(BI->getParent()); 101 102 // Replace the conditional branch with an unconditional one. 103 Builder.CreateBr(Dest1); 104 Value *Cond = BI->getCondition(); 105 BI->eraseFromParent(); 106 if (DeleteDeadConditions) 107 RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI); 108 return true; 109 } 110 return false; 111 } 112 113 if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { 114 // If we are switching on a constant, we can convert the switch to an 115 // unconditional branch. 116 ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); 117 BasicBlock *DefaultDest = SI->getDefaultDest(); 118 BasicBlock *TheOnlyDest = DefaultDest; 119 120 // If the default is unreachable, ignore it when searching for TheOnlyDest. 121 if (isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg()) && 122 SI->getNumCases() > 0) { 123 TheOnlyDest = SI->case_begin().getCaseSuccessor(); 124 } 125 126 // Figure out which case it goes to. 127 for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); 128 i != e; ++i) { 129 // Found case matching a constant operand? 130 if (i.getCaseValue() == CI) { 131 TheOnlyDest = i.getCaseSuccessor(); 132 break; 133 } 134 135 // Check to see if this branch is going to the same place as the default 136 // dest. If so, eliminate it as an explicit compare. 137 if (i.getCaseSuccessor() == DefaultDest) { 138 MDNode *MD = SI->getMetadata(LLVMContext::MD_prof); 139 unsigned NCases = SI->getNumCases(); 140 // Fold the case metadata into the default if there will be any branches 141 // left, unless the metadata doesn't match the switch. 142 if (NCases > 1 && MD && MD->getNumOperands() == 2 + NCases) { 143 // Collect branch weights into a vector. 144 SmallVector<uint32_t, 8> Weights; 145 for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e; 146 ++MD_i) { 147 ConstantInt *CI = 148 mdconst::dyn_extract<ConstantInt>(MD->getOperand(MD_i)); 149 assert(CI); 150 Weights.push_back(CI->getValue().getZExtValue()); 151 } 152 // Merge weight of this case to the default weight. 153 unsigned idx = i.getCaseIndex(); 154 Weights[0] += Weights[idx+1]; 155 // Remove weight for this case. 156 std::swap(Weights[idx+1], Weights.back()); 157 Weights.pop_back(); 158 SI->setMetadata(LLVMContext::MD_prof, 159 MDBuilder(BB->getContext()). 160 createBranchWeights(Weights)); 161 } 162 // Remove this entry. 163 DefaultDest->removePredecessor(SI->getParent()); 164 SI->removeCase(i); 165 --i; --e; 166 continue; 167 } 168 169 // Otherwise, check to see if the switch only branches to one destination. 170 // We do this by reseting "TheOnlyDest" to null when we find two non-equal 171 // destinations. 172 if (i.getCaseSuccessor() != TheOnlyDest) TheOnlyDest = nullptr; 173 } 174 175 if (CI && !TheOnlyDest) { 176 // Branching on a constant, but not any of the cases, go to the default 177 // successor. 178 TheOnlyDest = SI->getDefaultDest(); 179 } 180 181 // If we found a single destination that we can fold the switch into, do so 182 // now. 183 if (TheOnlyDest) { 184 // Insert the new branch. 185 Builder.CreateBr(TheOnlyDest); 186 BasicBlock *BB = SI->getParent(); 187 188 // Remove entries from PHI nodes which we no longer branch to... 189 for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { 190 // Found case matching a constant operand? 191 BasicBlock *Succ = SI->getSuccessor(i); 192 if (Succ == TheOnlyDest) 193 TheOnlyDest = nullptr; // Don't modify the first branch to TheOnlyDest 194 else 195 Succ->removePredecessor(BB); 196 } 197 198 // Delete the old switch. 199 Value *Cond = SI->getCondition(); 200 SI->eraseFromParent(); 201 if (DeleteDeadConditions) 202 RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI); 203 return true; 204 } 205 206 if (SI->getNumCases() == 1) { 207 // Otherwise, we can fold this switch into a conditional branch 208 // instruction if it has only one non-default destination. 209 SwitchInst::CaseIt FirstCase = SI->case_begin(); 210 Value *Cond = Builder.CreateICmpEQ(SI->getCondition(), 211 FirstCase.getCaseValue(), "cond"); 212 213 // Insert the new branch. 214 BranchInst *NewBr = Builder.CreateCondBr(Cond, 215 FirstCase.getCaseSuccessor(), 216 SI->getDefaultDest()); 217 MDNode *MD = SI->getMetadata(LLVMContext::MD_prof); 218 if (MD && MD->getNumOperands() == 3) { 219 ConstantInt *SICase = 220 mdconst::dyn_extract<ConstantInt>(MD->getOperand(2)); 221 ConstantInt *SIDef = 222 mdconst::dyn_extract<ConstantInt>(MD->getOperand(1)); 223 assert(SICase && SIDef); 224 // The TrueWeight should be the weight for the single case of SI. 225 NewBr->setMetadata(LLVMContext::MD_prof, 226 MDBuilder(BB->getContext()). 227 createBranchWeights(SICase->getValue().getZExtValue(), 228 SIDef->getValue().getZExtValue())); 229 } 230 231 // Delete the old switch. 232 SI->eraseFromParent(); 233 return true; 234 } 235 return false; 236 } 237 238 if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(T)) { 239 // indirectbr blockaddress(@F, @BB) -> br label @BB 240 if (BlockAddress *BA = 241 dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) { 242 BasicBlock *TheOnlyDest = BA->getBasicBlock(); 243 // Insert the new branch. 244 Builder.CreateBr(TheOnlyDest); 245 246 for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) { 247 if (IBI->getDestination(i) == TheOnlyDest) 248 TheOnlyDest = nullptr; 249 else 250 IBI->getDestination(i)->removePredecessor(IBI->getParent()); 251 } 252 Value *Address = IBI->getAddress(); 253 IBI->eraseFromParent(); 254 if (DeleteDeadConditions) 255 RecursivelyDeleteTriviallyDeadInstructions(Address, TLI); 256 257 // If we didn't find our destination in the IBI successor list, then we 258 // have undefined behavior. Replace the unconditional branch with an 259 // 'unreachable' instruction. 260 if (TheOnlyDest) { 261 BB->getTerminator()->eraseFromParent(); 262 new UnreachableInst(BB->getContext(), BB); 263 } 264 265 return true; 266 } 267 } 268 269 return false; 270 } 271 272 273 //===----------------------------------------------------------------------===// 274 // Local dead code elimination. 275 // 276 277 /// isInstructionTriviallyDead - Return true if the result produced by the 278 /// instruction is not used, and the instruction has no side effects. 279 /// 280 bool llvm::isInstructionTriviallyDead(Instruction *I, 281 const TargetLibraryInfo *TLI) { 282 if (!I->use_empty() || isa<TerminatorInst>(I)) return false; 283 284 // We don't want the landingpad instruction removed by anything this general. 285 if (isa<LandingPadInst>(I)) 286 return false; 287 288 // We don't want debug info removed by anything this general, unless 289 // debug info is empty. 290 if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) { 291 if (DDI->getAddress()) 292 return false; 293 return true; 294 } 295 if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) { 296 if (DVI->getValue()) 297 return false; 298 return true; 299 } 300 301 if (!I->mayHaveSideEffects()) return true; 302 303 // Special case intrinsics that "may have side effects" but can be deleted 304 // when dead. 305 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 306 // Safe to delete llvm.stacksave if dead. 307 if (II->getIntrinsicID() == Intrinsic::stacksave) 308 return true; 309 310 // Lifetime intrinsics are dead when their right-hand is undef. 311 if (II->getIntrinsicID() == Intrinsic::lifetime_start || 312 II->getIntrinsicID() == Intrinsic::lifetime_end) 313 return isa<UndefValue>(II->getArgOperand(1)); 314 315 // Assumptions are dead if their condition is trivially true. 316 if (II->getIntrinsicID() == Intrinsic::assume) { 317 if (ConstantInt *Cond = dyn_cast<ConstantInt>(II->getArgOperand(0))) 318 return !Cond->isZero(); 319 320 return false; 321 } 322 } 323 324 if (isAllocLikeFn(I, TLI)) return true; 325 326 if (CallInst *CI = isFreeCall(I, TLI)) 327 if (Constant *C = dyn_cast<Constant>(CI->getArgOperand(0))) 328 return C->isNullValue() || isa<UndefValue>(C); 329 330 return false; 331 } 332 333 /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a 334 /// trivially dead instruction, delete it. If that makes any of its operands 335 /// trivially dead, delete them too, recursively. Return true if any 336 /// instructions were deleted. 337 bool 338 llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V, 339 const TargetLibraryInfo *TLI) { 340 Instruction *I = dyn_cast<Instruction>(V); 341 if (!I || !I->use_empty() || !isInstructionTriviallyDead(I, TLI)) 342 return false; 343 344 SmallVector<Instruction*, 16> DeadInsts; 345 DeadInsts.push_back(I); 346 347 do { 348 I = DeadInsts.pop_back_val(); 349 350 // Null out all of the instruction's operands to see if any operand becomes 351 // dead as we go. 352 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 353 Value *OpV = I->getOperand(i); 354 I->setOperand(i, nullptr); 355 356 if (!OpV->use_empty()) continue; 357 358 // If the operand is an instruction that became dead as we nulled out the 359 // operand, and if it is 'trivially' dead, delete it in a future loop 360 // iteration. 361 if (Instruction *OpI = dyn_cast<Instruction>(OpV)) 362 if (isInstructionTriviallyDead(OpI, TLI)) 363 DeadInsts.push_back(OpI); 364 } 365 366 I->eraseFromParent(); 367 } while (!DeadInsts.empty()); 368 369 return true; 370 } 371 372 /// areAllUsesEqual - Check whether the uses of a value are all the same. 373 /// This is similar to Instruction::hasOneUse() except this will also return 374 /// true when there are no uses or multiple uses that all refer to the same 375 /// value. 376 static bool areAllUsesEqual(Instruction *I) { 377 Value::user_iterator UI = I->user_begin(); 378 Value::user_iterator UE = I->user_end(); 379 if (UI == UE) 380 return true; 381 382 User *TheUse = *UI; 383 for (++UI; UI != UE; ++UI) { 384 if (*UI != TheUse) 385 return false; 386 } 387 return true; 388 } 389 390 /// RecursivelyDeleteDeadPHINode - If the specified value is an effectively 391 /// dead PHI node, due to being a def-use chain of single-use nodes that 392 /// either forms a cycle or is terminated by a trivially dead instruction, 393 /// delete it. If that makes any of its operands trivially dead, delete them 394 /// too, recursively. Return true if a change was made. 395 bool llvm::RecursivelyDeleteDeadPHINode(PHINode *PN, 396 const TargetLibraryInfo *TLI) { 397 SmallPtrSet<Instruction*, 4> Visited; 398 for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects(); 399 I = cast<Instruction>(*I->user_begin())) { 400 if (I->use_empty()) 401 return RecursivelyDeleteTriviallyDeadInstructions(I, TLI); 402 403 // If we find an instruction more than once, we're on a cycle that 404 // won't prove fruitful. 405 if (!Visited.insert(I).second) { 406 // Break the cycle and delete the instruction and its operands. 407 I->replaceAllUsesWith(UndefValue::get(I->getType())); 408 (void)RecursivelyDeleteTriviallyDeadInstructions(I, TLI); 409 return true; 410 } 411 } 412 return false; 413 } 414 415 /// SimplifyInstructionsInBlock - Scan the specified basic block and try to 416 /// simplify any instructions in it and recursively delete dead instructions. 417 /// 418 /// This returns true if it changed the code, note that it can delete 419 /// instructions in other blocks as well in this block. 420 bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB, const DataLayout *TD, 421 const TargetLibraryInfo *TLI) { 422 bool MadeChange = false; 423 424 #ifndef NDEBUG 425 // In debug builds, ensure that the terminator of the block is never replaced 426 // or deleted by these simplifications. The idea of simplification is that it 427 // cannot introduce new instructions, and there is no way to replace the 428 // terminator of a block without introducing a new instruction. 429 AssertingVH<Instruction> TerminatorVH(--BB->end()); 430 #endif 431 432 for (BasicBlock::iterator BI = BB->begin(), E = --BB->end(); BI != E; ) { 433 assert(!BI->isTerminator()); 434 Instruction *Inst = BI++; 435 436 WeakVH BIHandle(BI); 437 if (recursivelySimplifyInstruction(Inst, TD, TLI)) { 438 MadeChange = true; 439 if (BIHandle != BI) 440 BI = BB->begin(); 441 continue; 442 } 443 444 MadeChange |= RecursivelyDeleteTriviallyDeadInstructions(Inst, TLI); 445 if (BIHandle != BI) 446 BI = BB->begin(); 447 } 448 return MadeChange; 449 } 450 451 //===----------------------------------------------------------------------===// 452 // Control Flow Graph Restructuring. 453 // 454 455 456 /// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this 457 /// method is called when we're about to delete Pred as a predecessor of BB. If 458 /// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred. 459 /// 460 /// Unlike the removePredecessor method, this attempts to simplify uses of PHI 461 /// nodes that collapse into identity values. For example, if we have: 462 /// x = phi(1, 0, 0, 0) 463 /// y = and x, z 464 /// 465 /// .. and delete the predecessor corresponding to the '1', this will attempt to 466 /// recursively fold the and to 0. 467 void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred, 468 DataLayout *TD) { 469 // This only adjusts blocks with PHI nodes. 470 if (!isa<PHINode>(BB->begin())) 471 return; 472 473 // Remove the entries for Pred from the PHI nodes in BB, but do not simplify 474 // them down. This will leave us with single entry phi nodes and other phis 475 // that can be removed. 476 BB->removePredecessor(Pred, true); 477 478 WeakVH PhiIt = &BB->front(); 479 while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) { 480 PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt)); 481 Value *OldPhiIt = PhiIt; 482 483 if (!recursivelySimplifyInstruction(PN, TD)) 484 continue; 485 486 // If recursive simplification ended up deleting the next PHI node we would 487 // iterate to, then our iterator is invalid, restart scanning from the top 488 // of the block. 489 if (PhiIt != OldPhiIt) PhiIt = &BB->front(); 490 } 491 } 492 493 494 /// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its 495 /// predecessor is known to have one successor (DestBB!). Eliminate the edge 496 /// between them, moving the instructions in the predecessor into DestBB and 497 /// deleting the predecessor block. 498 /// 499 void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT) { 500 // If BB has single-entry PHI nodes, fold them. 501 while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) { 502 Value *NewVal = PN->getIncomingValue(0); 503 // Replace self referencing PHI with undef, it must be dead. 504 if (NewVal == PN) NewVal = UndefValue::get(PN->getType()); 505 PN->replaceAllUsesWith(NewVal); 506 PN->eraseFromParent(); 507 } 508 509 BasicBlock *PredBB = DestBB->getSinglePredecessor(); 510 assert(PredBB && "Block doesn't have a single predecessor!"); 511 512 // Zap anything that took the address of DestBB. Not doing this will give the 513 // address an invalid value. 514 if (DestBB->hasAddressTaken()) { 515 BlockAddress *BA = BlockAddress::get(DestBB); 516 Constant *Replacement = 517 ConstantInt::get(llvm::Type::getInt32Ty(BA->getContext()), 1); 518 BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement, 519 BA->getType())); 520 BA->destroyConstant(); 521 } 522 523 // Anything that branched to PredBB now branches to DestBB. 524 PredBB->replaceAllUsesWith(DestBB); 525 526 // Splice all the instructions from PredBB to DestBB. 527 PredBB->getTerminator()->eraseFromParent(); 528 DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList()); 529 530 // If the PredBB is the entry block of the function, move DestBB up to 531 // become the entry block after we erase PredBB. 532 if (PredBB == &DestBB->getParent()->getEntryBlock()) 533 DestBB->moveAfter(PredBB); 534 535 if (DT) { 536 BasicBlock *PredBBIDom = DT->getNode(PredBB)->getIDom()->getBlock(); 537 DT->changeImmediateDominator(DestBB, PredBBIDom); 538 DT->eraseNode(PredBB); 539 } 540 // Nuke BB. 541 PredBB->eraseFromParent(); 542 } 543 544 /// CanMergeValues - Return true if we can choose one of these values to use 545 /// in place of the other. Note that we will always choose the non-undef 546 /// value to keep. 547 static bool CanMergeValues(Value *First, Value *Second) { 548 return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second); 549 } 550 551 /// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an 552 /// almost-empty BB ending in an unconditional branch to Succ, into Succ. 553 /// 554 /// Assumption: Succ is the single successor for BB. 555 /// 556 static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 557 assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 558 559 DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into " 560 << Succ->getName() << "\n"); 561 // Shortcut, if there is only a single predecessor it must be BB and merging 562 // is always safe 563 if (Succ->getSinglePredecessor()) return true; 564 565 // Make a list of the predecessors of BB 566 SmallPtrSet<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB)); 567 568 // Look at all the phi nodes in Succ, to see if they present a conflict when 569 // merging these blocks 570 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 571 PHINode *PN = cast<PHINode>(I); 572 573 // If the incoming value from BB is again a PHINode in 574 // BB which has the same incoming value for *PI as PN does, we can 575 // merge the phi nodes and then the blocks can still be merged 576 PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB)); 577 if (BBPN && BBPN->getParent() == BB) { 578 for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) { 579 BasicBlock *IBB = PN->getIncomingBlock(PI); 580 if (BBPreds.count(IBB) && 581 !CanMergeValues(BBPN->getIncomingValueForBlock(IBB), 582 PN->getIncomingValue(PI))) { 583 DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in " 584 << Succ->getName() << " is conflicting with " 585 << BBPN->getName() << " with regard to common predecessor " 586 << IBB->getName() << "\n"); 587 return false; 588 } 589 } 590 } else { 591 Value* Val = PN->getIncomingValueForBlock(BB); 592 for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) { 593 // See if the incoming value for the common predecessor is equal to the 594 // one for BB, in which case this phi node will not prevent the merging 595 // of the block. 596 BasicBlock *IBB = PN->getIncomingBlock(PI); 597 if (BBPreds.count(IBB) && 598 !CanMergeValues(Val, PN->getIncomingValue(PI))) { 599 DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in " 600 << Succ->getName() << " is conflicting with regard to common " 601 << "predecessor " << IBB->getName() << "\n"); 602 return false; 603 } 604 } 605 } 606 } 607 608 return true; 609 } 610 611 typedef SmallVector<BasicBlock *, 16> PredBlockVector; 612 typedef DenseMap<BasicBlock *, Value *> IncomingValueMap; 613 614 /// \brief Determines the value to use as the phi node input for a block. 615 /// 616 /// Select between \p OldVal any value that we know flows from \p BB 617 /// to a particular phi on the basis of which one (if either) is not 618 /// undef. Update IncomingValues based on the selected value. 619 /// 620 /// \param OldVal The value we are considering selecting. 621 /// \param BB The block that the value flows in from. 622 /// \param IncomingValues A map from block-to-value for other phi inputs 623 /// that we have examined. 624 /// 625 /// \returns the selected value. 626 static Value *selectIncomingValueForBlock(Value *OldVal, BasicBlock *BB, 627 IncomingValueMap &IncomingValues) { 628 if (!isa<UndefValue>(OldVal)) { 629 assert((!IncomingValues.count(BB) || 630 IncomingValues.find(BB)->second == OldVal) && 631 "Expected OldVal to match incoming value from BB!"); 632 633 IncomingValues.insert(std::make_pair(BB, OldVal)); 634 return OldVal; 635 } 636 637 IncomingValueMap::const_iterator It = IncomingValues.find(BB); 638 if (It != IncomingValues.end()) return It->second; 639 640 return OldVal; 641 } 642 643 /// \brief Create a map from block to value for the operands of a 644 /// given phi. 645 /// 646 /// Create a map from block to value for each non-undef value flowing 647 /// into \p PN. 648 /// 649 /// \param PN The phi we are collecting the map for. 650 /// \param IncomingValues [out] The map from block to value for this phi. 651 static void gatherIncomingValuesToPhi(PHINode *PN, 652 IncomingValueMap &IncomingValues) { 653 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 654 BasicBlock *BB = PN->getIncomingBlock(i); 655 Value *V = PN->getIncomingValue(i); 656 657 if (!isa<UndefValue>(V)) 658 IncomingValues.insert(std::make_pair(BB, V)); 659 } 660 } 661 662 /// \brief Replace the incoming undef values to a phi with the values 663 /// from a block-to-value map. 664 /// 665 /// \param PN The phi we are replacing the undefs in. 666 /// \param IncomingValues A map from block to value. 667 static void replaceUndefValuesInPhi(PHINode *PN, 668 const IncomingValueMap &IncomingValues) { 669 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 670 Value *V = PN->getIncomingValue(i); 671 672 if (!isa<UndefValue>(V)) continue; 673 674 BasicBlock *BB = PN->getIncomingBlock(i); 675 IncomingValueMap::const_iterator It = IncomingValues.find(BB); 676 if (It == IncomingValues.end()) continue; 677 678 PN->setIncomingValue(i, It->second); 679 } 680 } 681 682 /// \brief Replace a value flowing from a block to a phi with 683 /// potentially multiple instances of that value flowing from the 684 /// block's predecessors to the phi. 685 /// 686 /// \param BB The block with the value flowing into the phi. 687 /// \param BBPreds The predecessors of BB. 688 /// \param PN The phi that we are updating. 689 static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB, 690 const PredBlockVector &BBPreds, 691 PHINode *PN) { 692 Value *OldVal = PN->removeIncomingValue(BB, false); 693 assert(OldVal && "No entry in PHI for Pred BB!"); 694 695 IncomingValueMap IncomingValues; 696 697 // We are merging two blocks - BB, and the block containing PN - and 698 // as a result we need to redirect edges from the predecessors of BB 699 // to go to the block containing PN, and update PN 700 // accordingly. Since we allow merging blocks in the case where the 701 // predecessor and successor blocks both share some predecessors, 702 // and where some of those common predecessors might have undef 703 // values flowing into PN, we want to rewrite those values to be 704 // consistent with the non-undef values. 705 706 gatherIncomingValuesToPhi(PN, IncomingValues); 707 708 // If this incoming value is one of the PHI nodes in BB, the new entries 709 // in the PHI node are the entries from the old PHI. 710 if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { 711 PHINode *OldValPN = cast<PHINode>(OldVal); 712 for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) { 713 // Note that, since we are merging phi nodes and BB and Succ might 714 // have common predecessors, we could end up with a phi node with 715 // identical incoming branches. This will be cleaned up later (and 716 // will trigger asserts if we try to clean it up now, without also 717 // simplifying the corresponding conditional branch). 718 BasicBlock *PredBB = OldValPN->getIncomingBlock(i); 719 Value *PredVal = OldValPN->getIncomingValue(i); 720 Value *Selected = selectIncomingValueForBlock(PredVal, PredBB, 721 IncomingValues); 722 723 // And add a new incoming value for this predecessor for the 724 // newly retargeted branch. 725 PN->addIncoming(Selected, PredBB); 726 } 727 } else { 728 for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) { 729 // Update existing incoming values in PN for this 730 // predecessor of BB. 731 BasicBlock *PredBB = BBPreds[i]; 732 Value *Selected = selectIncomingValueForBlock(OldVal, PredBB, 733 IncomingValues); 734 735 // And add a new incoming value for this predecessor for the 736 // newly retargeted branch. 737 PN->addIncoming(Selected, PredBB); 738 } 739 } 740 741 replaceUndefValuesInPhi(PN, IncomingValues); 742 } 743 744 /// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an 745 /// unconditional branch, and contains no instructions other than PHI nodes, 746 /// potential side-effect free intrinsics and the branch. If possible, 747 /// eliminate BB by rewriting all the predecessors to branch to the successor 748 /// block and return true. If we can't transform, return false. 749 bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) { 750 assert(BB != &BB->getParent()->getEntryBlock() && 751 "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!"); 752 753 // We can't eliminate infinite loops. 754 BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0); 755 if (BB == Succ) return false; 756 757 // Check to see if merging these blocks would cause conflicts for any of the 758 // phi nodes in BB or Succ. If not, we can safely merge. 759 if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false; 760 761 // Check for cases where Succ has multiple predecessors and a PHI node in BB 762 // has uses which will not disappear when the PHI nodes are merged. It is 763 // possible to handle such cases, but difficult: it requires checking whether 764 // BB dominates Succ, which is non-trivial to calculate in the case where 765 // Succ has multiple predecessors. Also, it requires checking whether 766 // constructing the necessary self-referential PHI node doesn't introduce any 767 // conflicts; this isn't too difficult, but the previous code for doing this 768 // was incorrect. 769 // 770 // Note that if this check finds a live use, BB dominates Succ, so BB is 771 // something like a loop pre-header (or rarely, a part of an irreducible CFG); 772 // folding the branch isn't profitable in that case anyway. 773 if (!Succ->getSinglePredecessor()) { 774 BasicBlock::iterator BBI = BB->begin(); 775 while (isa<PHINode>(*BBI)) { 776 for (Use &U : BBI->uses()) { 777 if (PHINode* PN = dyn_cast<PHINode>(U.getUser())) { 778 if (PN->getIncomingBlock(U) != BB) 779 return false; 780 } else { 781 return false; 782 } 783 } 784 ++BBI; 785 } 786 } 787 788 DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB); 789 790 if (isa<PHINode>(Succ->begin())) { 791 // If there is more than one pred of succ, and there are PHI nodes in 792 // the successor, then we need to add incoming edges for the PHI nodes 793 // 794 const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB)); 795 796 // Loop over all of the PHI nodes in the successor of BB. 797 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 798 PHINode *PN = cast<PHINode>(I); 799 800 redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN); 801 } 802 } 803 804 if (Succ->getSinglePredecessor()) { 805 // BB is the only predecessor of Succ, so Succ will end up with exactly 806 // the same predecessors BB had. 807 808 // Copy over any phi, debug or lifetime instruction. 809 BB->getTerminator()->eraseFromParent(); 810 Succ->getInstList().splice(Succ->getFirstNonPHI(), BB->getInstList()); 811 } else { 812 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 813 // We explicitly check for such uses in CanPropagatePredecessorsForPHIs. 814 assert(PN->use_empty() && "There shouldn't be any uses here!"); 815 PN->eraseFromParent(); 816 } 817 } 818 819 // Everything that jumped to BB now goes to Succ. 820 BB->replaceAllUsesWith(Succ); 821 if (!Succ->hasName()) Succ->takeName(BB); 822 BB->eraseFromParent(); // Delete the old basic block. 823 return true; 824 } 825 826 /// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI 827 /// nodes in this block. This doesn't try to be clever about PHI nodes 828 /// which differ only in the order of the incoming values, but instcombine 829 /// orders them so it usually won't matter. 830 /// 831 bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { 832 bool Changed = false; 833 834 // This implementation doesn't currently consider undef operands 835 // specially. Theoretically, two phis which are identical except for 836 // one having an undef where the other doesn't could be collapsed. 837 838 // Map from PHI hash values to PHI nodes. If multiple PHIs have 839 // the same hash value, the element is the first PHI in the 840 // linked list in CollisionMap. 841 DenseMap<uintptr_t, PHINode *> HashMap; 842 843 // Maintain linked lists of PHI nodes with common hash values. 844 DenseMap<PHINode *, PHINode *> CollisionMap; 845 846 // Examine each PHI. 847 for (BasicBlock::iterator I = BB->begin(); 848 PHINode *PN = dyn_cast<PHINode>(I++); ) { 849 // Compute a hash value on the operands. Instcombine will likely have sorted 850 // them, which helps expose duplicates, but we have to check all the 851 // operands to be safe in case instcombine hasn't run. 852 uintptr_t Hash = 0; 853 // This hash algorithm is quite weak as hash functions go, but it seems 854 // to do a good enough job for this particular purpose, and is very quick. 855 for (User::op_iterator I = PN->op_begin(), E = PN->op_end(); I != E; ++I) { 856 Hash ^= reinterpret_cast<uintptr_t>(static_cast<Value *>(*I)); 857 Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7)); 858 } 859 for (PHINode::block_iterator I = PN->block_begin(), E = PN->block_end(); 860 I != E; ++I) { 861 Hash ^= reinterpret_cast<uintptr_t>(static_cast<BasicBlock *>(*I)); 862 Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7)); 863 } 864 // Avoid colliding with the DenseMap sentinels ~0 and ~0-1. 865 Hash >>= 1; 866 // If we've never seen this hash value before, it's a unique PHI. 867 std::pair<DenseMap<uintptr_t, PHINode *>::iterator, bool> Pair = 868 HashMap.insert(std::make_pair(Hash, PN)); 869 if (Pair.second) continue; 870 // Otherwise it's either a duplicate or a hash collision. 871 for (PHINode *OtherPN = Pair.first->second; ; ) { 872 if (OtherPN->isIdenticalTo(PN)) { 873 // A duplicate. Replace this PHI with its duplicate. 874 PN->replaceAllUsesWith(OtherPN); 875 PN->eraseFromParent(); 876 Changed = true; 877 break; 878 } 879 // A non-duplicate hash collision. 880 DenseMap<PHINode *, PHINode *>::iterator I = CollisionMap.find(OtherPN); 881 if (I == CollisionMap.end()) { 882 // Set this PHI to be the head of the linked list of colliding PHIs. 883 PHINode *Old = Pair.first->second; 884 Pair.first->second = PN; 885 CollisionMap[PN] = Old; 886 break; 887 } 888 // Proceed to the next PHI in the list. 889 OtherPN = I->second; 890 } 891 } 892 893 return Changed; 894 } 895 896 /// enforceKnownAlignment - If the specified pointer points to an object that 897 /// we control, modify the object's alignment to PrefAlign. This isn't 898 /// often possible though. If alignment is important, a more reliable approach 899 /// is to simply align all global variables and allocation instructions to 900 /// their preferred alignment from the beginning. 901 /// 902 static unsigned enforceKnownAlignment(Value *V, unsigned Align, 903 unsigned PrefAlign, const DataLayout *TD) { 904 V = V->stripPointerCasts(); 905 906 if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) { 907 // If the preferred alignment is greater than the natural stack alignment 908 // then don't round up. This avoids dynamic stack realignment. 909 if (TD && TD->exceedsNaturalStackAlignment(PrefAlign)) 910 return Align; 911 // If there is a requested alignment and if this is an alloca, round up. 912 if (AI->getAlignment() >= PrefAlign) 913 return AI->getAlignment(); 914 AI->setAlignment(PrefAlign); 915 return PrefAlign; 916 } 917 918 if (auto *GO = dyn_cast<GlobalObject>(V)) { 919 // If there is a large requested alignment and we can, bump up the alignment 920 // of the global. 921 if (GO->isDeclaration()) 922 return Align; 923 // If the memory we set aside for the global may not be the memory used by 924 // the final program then it is impossible for us to reliably enforce the 925 // preferred alignment. 926 if (GO->isWeakForLinker()) 927 return Align; 928 929 if (GO->getAlignment() >= PrefAlign) 930 return GO->getAlignment(); 931 // We can only increase the alignment of the global if it has no alignment 932 // specified or if it is not assigned a section. If it is assigned a 933 // section, the global could be densely packed with other objects in the 934 // section, increasing the alignment could cause padding issues. 935 if (!GO->hasSection() || GO->getAlignment() == 0) 936 GO->setAlignment(PrefAlign); 937 return GO->getAlignment(); 938 } 939 940 return Align; 941 } 942 943 /// getOrEnforceKnownAlignment - If the specified pointer has an alignment that 944 /// we can determine, return it, otherwise return 0. If PrefAlign is specified, 945 /// and it is more than the alignment of the ultimate object, see if we can 946 /// increase the alignment of the ultimate object, making this check succeed. 947 unsigned llvm::getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, 948 const DataLayout *DL, 949 AssumptionCache *AC, 950 const Instruction *CxtI, 951 const DominatorTree *DT) { 952 assert(V->getType()->isPointerTy() && 953 "getOrEnforceKnownAlignment expects a pointer!"); 954 unsigned BitWidth = DL ? DL->getPointerTypeSizeInBits(V->getType()) : 64; 955 956 APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); 957 computeKnownBits(V, KnownZero, KnownOne, DL, 0, AC, CxtI, DT); 958 unsigned TrailZ = KnownZero.countTrailingOnes(); 959 960 // Avoid trouble with ridiculously large TrailZ values, such as 961 // those computed from a null pointer. 962 TrailZ = std::min(TrailZ, unsigned(sizeof(unsigned) * CHAR_BIT - 1)); 963 964 unsigned Align = 1u << std::min(BitWidth - 1, TrailZ); 965 966 // LLVM doesn't support alignments larger than this currently. 967 Align = std::min(Align, +Value::MaximumAlignment); 968 969 if (PrefAlign > Align) 970 Align = enforceKnownAlignment(V, Align, PrefAlign, DL); 971 972 // We don't need to make any adjustment. 973 return Align; 974 } 975 976 ///===---------------------------------------------------------------------===// 977 /// Dbg Intrinsic utilities 978 /// 979 980 /// See if there is a dbg.value intrinsic for DIVar before I. 981 static bool LdStHasDebugValue(DIVariable &DIVar, Instruction *I) { 982 // Since we can't guarantee that the original dbg.declare instrinsic 983 // is removed by LowerDbgDeclare(), we need to make sure that we are 984 // not inserting the same dbg.value intrinsic over and over. 985 llvm::BasicBlock::InstListType::iterator PrevI(I); 986 if (PrevI != I->getParent()->getInstList().begin()) { 987 --PrevI; 988 if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(PrevI)) 989 if (DVI->getValue() == I->getOperand(0) && 990 DVI->getOffset() == 0 && 991 DVI->getVariable() == DIVar) 992 return true; 993 } 994 return false; 995 } 996 997 /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value 998 /// that has an associated llvm.dbg.decl intrinsic. 999 bool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, 1000 StoreInst *SI, DIBuilder &Builder) { 1001 DIVariable DIVar(DDI->getVariable()); 1002 DIExpression DIExpr(DDI->getExpression()); 1003 assert((!DIVar || DIVar.isVariable()) && 1004 "Variable in DbgDeclareInst should be either null or a DIVariable."); 1005 if (!DIVar) 1006 return false; 1007 1008 if (LdStHasDebugValue(DIVar, SI)) 1009 return true; 1010 1011 Instruction *DbgVal = nullptr; 1012 // If an argument is zero extended then use argument directly. The ZExt 1013 // may be zapped by an optimization pass in future. 1014 Argument *ExtendedArg = nullptr; 1015 if (ZExtInst *ZExt = dyn_cast<ZExtInst>(SI->getOperand(0))) 1016 ExtendedArg = dyn_cast<Argument>(ZExt->getOperand(0)); 1017 if (SExtInst *SExt = dyn_cast<SExtInst>(SI->getOperand(0))) 1018 ExtendedArg = dyn_cast<Argument>(SExt->getOperand(0)); 1019 if (ExtendedArg) 1020 DbgVal = Builder.insertDbgValueIntrinsic(ExtendedArg, 0, DIVar, DIExpr, SI); 1021 else 1022 DbgVal = Builder.insertDbgValueIntrinsic(SI->getOperand(0), 0, DIVar, 1023 DIExpr, SI); 1024 DbgVal->setDebugLoc(DDI->getDebugLoc()); 1025 return true; 1026 } 1027 1028 /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value 1029 /// that has an associated llvm.dbg.decl intrinsic. 1030 bool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, 1031 LoadInst *LI, DIBuilder &Builder) { 1032 DIVariable DIVar(DDI->getVariable()); 1033 DIExpression DIExpr(DDI->getExpression()); 1034 assert((!DIVar || DIVar.isVariable()) && 1035 "Variable in DbgDeclareInst should be either null or a DIVariable."); 1036 if (!DIVar) 1037 return false; 1038 1039 if (LdStHasDebugValue(DIVar, LI)) 1040 return true; 1041 1042 Instruction *DbgVal = 1043 Builder.insertDbgValueIntrinsic(LI->getOperand(0), 0, DIVar, DIExpr, LI); 1044 DbgVal->setDebugLoc(DDI->getDebugLoc()); 1045 return true; 1046 } 1047 1048 /// Determine whether this alloca is either a VLA or an array. 1049 static bool isArray(AllocaInst *AI) { 1050 return AI->isArrayAllocation() || 1051 AI->getType()->getElementType()->isArrayTy(); 1052 } 1053 1054 /// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set 1055 /// of llvm.dbg.value intrinsics. 1056 bool llvm::LowerDbgDeclare(Function &F) { 1057 DIBuilder DIB(*F.getParent(), /*AllowUnresolved*/ false); 1058 SmallVector<DbgDeclareInst *, 4> Dbgs; 1059 for (auto &FI : F) 1060 for (BasicBlock::iterator BI : FI) 1061 if (auto DDI = dyn_cast<DbgDeclareInst>(BI)) 1062 Dbgs.push_back(DDI); 1063 1064 if (Dbgs.empty()) 1065 return false; 1066 1067 for (auto &I : Dbgs) { 1068 DbgDeclareInst *DDI = I; 1069 AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress()); 1070 // If this is an alloca for a scalar variable, insert a dbg.value 1071 // at each load and store to the alloca and erase the dbg.declare. 1072 // The dbg.values allow tracking a variable even if it is not 1073 // stored on the stack, while the dbg.declare can only describe 1074 // the stack slot (and at a lexical-scope granularity). Later 1075 // passes will attempt to elide the stack slot. 1076 if (AI && !isArray(AI)) { 1077 for (User *U : AI->users()) 1078 if (StoreInst *SI = dyn_cast<StoreInst>(U)) 1079 ConvertDebugDeclareToDebugValue(DDI, SI, DIB); 1080 else if (LoadInst *LI = dyn_cast<LoadInst>(U)) 1081 ConvertDebugDeclareToDebugValue(DDI, LI, DIB); 1082 else if (CallInst *CI = dyn_cast<CallInst>(U)) { 1083 // This is a call by-value or some other instruction that 1084 // takes a pointer to the variable. Insert a *value* 1085 // intrinsic that describes the alloca. 1086 auto DbgVal = DIB.insertDbgValueIntrinsic( 1087 AI, 0, DIVariable(DDI->getVariable()), 1088 DIExpression(DDI->getExpression()), CI); 1089 DbgVal->setDebugLoc(DDI->getDebugLoc()); 1090 } 1091 DDI->eraseFromParent(); 1092 } 1093 } 1094 return true; 1095 } 1096 1097 /// FindAllocaDbgDeclare - Finds the llvm.dbg.declare intrinsic describing the 1098 /// alloca 'V', if any. 1099 DbgDeclareInst *llvm::FindAllocaDbgDeclare(Value *V) { 1100 if (auto *L = LocalAsMetadata::getIfExists(V)) 1101 if (auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L)) 1102 for (User *U : MDV->users()) 1103 if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(U)) 1104 return DDI; 1105 1106 return nullptr; 1107 } 1108 1109 bool llvm::replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, 1110 DIBuilder &Builder, bool Deref) { 1111 DbgDeclareInst *DDI = FindAllocaDbgDeclare(AI); 1112 if (!DDI) 1113 return false; 1114 DebugLoc Loc = DDI->getDebugLoc(); 1115 DIVariable DIVar(DDI->getVariable()); 1116 DIExpression DIExpr(DDI->getExpression()); 1117 assert((!DIVar || DIVar.isVariable()) && 1118 "Variable in DbgDeclareInst should be either null or a DIVariable."); 1119 if (!DIVar) 1120 return false; 1121 1122 if (Deref) { 1123 // Create a copy of the original DIDescriptor for user variable, prepending 1124 // "deref" operation to a list of address elements, as new llvm.dbg.declare 1125 // will take a value storing address of the memory for variable, not 1126 // alloca itself. 1127 SmallVector<uint64_t, 4> NewDIExpr; 1128 NewDIExpr.push_back(dwarf::DW_OP_deref); 1129 if (DIExpr) 1130 for (unsigned i = 0, n = DIExpr.getNumElements(); i < n; ++i) 1131 NewDIExpr.push_back(DIExpr.getElement(i)); 1132 DIExpr = Builder.createExpression(NewDIExpr); 1133 } 1134 1135 // Insert llvm.dbg.declare in the same basic block as the original alloca, 1136 // and remove old llvm.dbg.declare. 1137 BasicBlock *BB = AI->getParent(); 1138 Builder.insertDeclare(NewAllocaAddress, DIVar, DIExpr, BB) 1139 ->setDebugLoc(Loc); 1140 DDI->eraseFromParent(); 1141 return true; 1142 } 1143 1144 /// changeToUnreachable - Insert an unreachable instruction before the specified 1145 /// instruction, making it and the rest of the code in the block dead. 1146 static void changeToUnreachable(Instruction *I, bool UseLLVMTrap) { 1147 BasicBlock *BB = I->getParent(); 1148 // Loop over all of the successors, removing BB's entry from any PHI 1149 // nodes. 1150 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 1151 (*SI)->removePredecessor(BB); 1152 1153 // Insert a call to llvm.trap right before this. This turns the undefined 1154 // behavior into a hard fail instead of falling through into random code. 1155 if (UseLLVMTrap) { 1156 Function *TrapFn = 1157 Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap); 1158 CallInst *CallTrap = CallInst::Create(TrapFn, "", I); 1159 CallTrap->setDebugLoc(I->getDebugLoc()); 1160 } 1161 new UnreachableInst(I->getContext(), I); 1162 1163 // All instructions after this are dead. 1164 BasicBlock::iterator BBI = I, BBE = BB->end(); 1165 while (BBI != BBE) { 1166 if (!BBI->use_empty()) 1167 BBI->replaceAllUsesWith(UndefValue::get(BBI->getType())); 1168 BB->getInstList().erase(BBI++); 1169 } 1170 } 1171 1172 /// changeToCall - Convert the specified invoke into a normal call. 1173 static void changeToCall(InvokeInst *II) { 1174 SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3); 1175 CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, "", II); 1176 NewCall->takeName(II); 1177 NewCall->setCallingConv(II->getCallingConv()); 1178 NewCall->setAttributes(II->getAttributes()); 1179 NewCall->setDebugLoc(II->getDebugLoc()); 1180 II->replaceAllUsesWith(NewCall); 1181 1182 // Follow the call by a branch to the normal destination. 1183 BranchInst::Create(II->getNormalDest(), II); 1184 1185 // Update PHI nodes in the unwind destination 1186 II->getUnwindDest()->removePredecessor(II->getParent()); 1187 II->eraseFromParent(); 1188 } 1189 1190 static bool markAliveBlocks(BasicBlock *BB, 1191 SmallPtrSetImpl<BasicBlock*> &Reachable) { 1192 1193 SmallVector<BasicBlock*, 128> Worklist; 1194 Worklist.push_back(BB); 1195 Reachable.insert(BB); 1196 bool Changed = false; 1197 do { 1198 BB = Worklist.pop_back_val(); 1199 1200 // Do a quick scan of the basic block, turning any obviously unreachable 1201 // instructions into LLVM unreachable insts. The instruction combining pass 1202 // canonicalizes unreachable insts into stores to null or undef. 1203 for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;++BBI){ 1204 // Assumptions that are known to be false are equivalent to unreachable. 1205 // Also, if the condition is undefined, then we make the choice most 1206 // beneficial to the optimizer, and choose that to also be unreachable. 1207 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(BBI)) 1208 if (II->getIntrinsicID() == Intrinsic::assume) { 1209 bool MakeUnreachable = false; 1210 if (isa<UndefValue>(II->getArgOperand(0))) 1211 MakeUnreachable = true; 1212 else if (ConstantInt *Cond = 1213 dyn_cast<ConstantInt>(II->getArgOperand(0))) 1214 MakeUnreachable = Cond->isZero(); 1215 1216 if (MakeUnreachable) { 1217 // Don't insert a call to llvm.trap right before the unreachable. 1218 changeToUnreachable(BBI, false); 1219 Changed = true; 1220 break; 1221 } 1222 } 1223 1224 if (CallInst *CI = dyn_cast<CallInst>(BBI)) { 1225 if (CI->doesNotReturn()) { 1226 // If we found a call to a no-return function, insert an unreachable 1227 // instruction after it. Make sure there isn't *already* one there 1228 // though. 1229 ++BBI; 1230 if (!isa<UnreachableInst>(BBI)) { 1231 // Don't insert a call to llvm.trap right before the unreachable. 1232 changeToUnreachable(BBI, false); 1233 Changed = true; 1234 } 1235 break; 1236 } 1237 } 1238 1239 // Store to undef and store to null are undefined and used to signal that 1240 // they should be changed to unreachable by passes that can't modify the 1241 // CFG. 1242 if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) { 1243 // Don't touch volatile stores. 1244 if (SI->isVolatile()) continue; 1245 1246 Value *Ptr = SI->getOperand(1); 1247 1248 if (isa<UndefValue>(Ptr) || 1249 (isa<ConstantPointerNull>(Ptr) && 1250 SI->getPointerAddressSpace() == 0)) { 1251 changeToUnreachable(SI, true); 1252 Changed = true; 1253 break; 1254 } 1255 } 1256 } 1257 1258 // Turn invokes that call 'nounwind' functions into ordinary calls. 1259 if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) { 1260 Value *Callee = II->getCalledValue(); 1261 if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) { 1262 changeToUnreachable(II, true); 1263 Changed = true; 1264 } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(II)) { 1265 if (II->use_empty() && II->onlyReadsMemory()) { 1266 // jump to the normal destination branch. 1267 BranchInst::Create(II->getNormalDest(), II); 1268 II->getUnwindDest()->removePredecessor(II->getParent()); 1269 II->eraseFromParent(); 1270 } else 1271 changeToCall(II); 1272 Changed = true; 1273 } 1274 } 1275 1276 Changed |= ConstantFoldTerminator(BB, true); 1277 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 1278 if (Reachable.insert(*SI).second) 1279 Worklist.push_back(*SI); 1280 } while (!Worklist.empty()); 1281 return Changed; 1282 } 1283 1284 /// removeUnreachableBlocksFromFn - Remove blocks that are not reachable, even 1285 /// if they are in a dead cycle. Return true if a change was made, false 1286 /// otherwise. 1287 bool llvm::removeUnreachableBlocks(Function &F) { 1288 SmallPtrSet<BasicBlock*, 128> Reachable; 1289 bool Changed = markAliveBlocks(F.begin(), Reachable); 1290 1291 // If there are unreachable blocks in the CFG... 1292 if (Reachable.size() == F.size()) 1293 return Changed; 1294 1295 assert(Reachable.size() < F.size()); 1296 NumRemoved += F.size()-Reachable.size(); 1297 1298 // Loop over all of the basic blocks that are not reachable, dropping all of 1299 // their internal references... 1300 for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) { 1301 if (Reachable.count(BB)) 1302 continue; 1303 1304 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 1305 if (Reachable.count(*SI)) 1306 (*SI)->removePredecessor(BB); 1307 BB->dropAllReferences(); 1308 } 1309 1310 for (Function::iterator I = ++F.begin(); I != F.end();) 1311 if (!Reachable.count(I)) 1312 I = F.getBasicBlockList().erase(I); 1313 else 1314 ++I; 1315 1316 return true; 1317 } 1318 1319 void llvm::combineMetadata(Instruction *K, const Instruction *J, ArrayRef<unsigned> KnownIDs) { 1320 SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata; 1321 K->dropUnknownMetadata(KnownIDs); 1322 K->getAllMetadataOtherThanDebugLoc(Metadata); 1323 for (unsigned i = 0, n = Metadata.size(); i < n; ++i) { 1324 unsigned Kind = Metadata[i].first; 1325 MDNode *JMD = J->getMetadata(Kind); 1326 MDNode *KMD = Metadata[i].second; 1327 1328 switch (Kind) { 1329 default: 1330 K->setMetadata(Kind, nullptr); // Remove unknown metadata 1331 break; 1332 case LLVMContext::MD_dbg: 1333 llvm_unreachable("getAllMetadataOtherThanDebugLoc returned a MD_dbg"); 1334 case LLVMContext::MD_tbaa: 1335 K->setMetadata(Kind, MDNode::getMostGenericTBAA(JMD, KMD)); 1336 break; 1337 case LLVMContext::MD_alias_scope: 1338 K->setMetadata(Kind, MDNode::getMostGenericAliasScope(JMD, KMD)); 1339 break; 1340 case LLVMContext::MD_noalias: 1341 K->setMetadata(Kind, MDNode::intersect(JMD, KMD)); 1342 break; 1343 case LLVMContext::MD_range: 1344 K->setMetadata(Kind, MDNode::getMostGenericRange(JMD, KMD)); 1345 break; 1346 case LLVMContext::MD_fpmath: 1347 K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD)); 1348 break; 1349 case LLVMContext::MD_invariant_load: 1350 // Only set the !invariant.load if it is present in both instructions. 1351 K->setMetadata(Kind, JMD); 1352 break; 1353 case LLVMContext::MD_nonnull: 1354 // Only set the !nonnull if it is present in both instructions. 1355 K->setMetadata(Kind, JMD); 1356 break; 1357 } 1358 } 1359 } 1360