Local.cpp revision c10fa6c801e48771b5eade50afc2fe6abaf08227
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/Constants.h" 17#include "llvm/GlobalAlias.h" 18#include "llvm/GlobalVariable.h" 19#include "llvm/DerivedTypes.h" 20#include "llvm/Instructions.h" 21#include "llvm/Intrinsics.h" 22#include "llvm/IntrinsicInst.h" 23#include "llvm/Metadata.h" 24#include "llvm/Operator.h" 25#include "llvm/ADT/DenseMap.h" 26#include "llvm/ADT/SmallPtrSet.h" 27#include "llvm/Analysis/DebugInfo.h" 28#include "llvm/Analysis/DIBuilder.h" 29#include "llvm/Analysis/Dominators.h" 30#include "llvm/Analysis/InstructionSimplify.h" 31#include "llvm/Analysis/MemoryBuiltins.h" 32#include "llvm/Analysis/ProfileInfo.h" 33#include "llvm/Analysis/ValueTracking.h" 34#include "llvm/Target/TargetData.h" 35#include "llvm/Support/CFG.h" 36#include "llvm/Support/Debug.h" 37#include "llvm/Support/GetElementPtrTypeIterator.h" 38#include "llvm/Support/IRBuilder.h" 39#include "llvm/Support/MathExtras.h" 40#include "llvm/Support/ValueHandle.h" 41#include "llvm/Support/raw_ostream.h" 42using namespace llvm; 43 44//===----------------------------------------------------------------------===// 45// Local constant propagation. 46// 47 48/// ConstantFoldTerminator - If a terminator instruction is predicated on a 49/// constant value, convert it into an unconditional branch to the constant 50/// destination. This is a nontrivial operation because the successors of this 51/// basic block must have their PHI nodes updated. 52/// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch 53/// conditions and indirectbr addresses this might make dead if 54/// DeleteDeadConditions is true. 55bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions) { 56 TerminatorInst *T = BB->getTerminator(); 57 IRBuilder<> Builder(T); 58 59 // Branch - See if we are conditional jumping on constant 60 if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 61 if (BI->isUnconditional()) return false; // Can't optimize uncond branch 62 BasicBlock *Dest1 = BI->getSuccessor(0); 63 BasicBlock *Dest2 = BI->getSuccessor(1); 64 65 if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) { 66 // Are we branching on constant? 67 // YES. Change to unconditional branch... 68 BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2; 69 BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1; 70 71 //cerr << "Function: " << T->getParent()->getParent() 72 // << "\nRemoving branch from " << T->getParent() 73 // << "\n\nTo: " << OldDest << endl; 74 75 // Let the basic block know that we are letting go of it. Based on this, 76 // it will adjust it's PHI nodes. 77 OldDest->removePredecessor(BB); 78 79 // Replace the conditional branch with an unconditional one. 80 Builder.CreateBr(Destination); 81 BI->eraseFromParent(); 82 return true; 83 } 84 85 if (Dest2 == Dest1) { // Conditional branch to same location? 86 // This branch matches something like this: 87 // br bool %cond, label %Dest, label %Dest 88 // and changes it into: br label %Dest 89 90 // Let the basic block know that we are letting go of one copy of it. 91 assert(BI->getParent() && "Terminator not inserted in block!"); 92 Dest1->removePredecessor(BI->getParent()); 93 94 // Replace the conditional branch with an unconditional one. 95 Builder.CreateBr(Dest1); 96 Value *Cond = BI->getCondition(); 97 BI->eraseFromParent(); 98 if (DeleteDeadConditions) 99 RecursivelyDeleteTriviallyDeadInstructions(Cond); 100 return true; 101 } 102 return false; 103 } 104 105 if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { 106 // If we are switching on a constant, we can convert the switch into a 107 // single branch instruction! 108 ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); 109 BasicBlock *TheOnlyDest = SI->getDefaultDest(); 110 BasicBlock *DefaultDest = TheOnlyDest; 111 112 // Figure out which case it goes to. 113 for (SwitchInst::CaseIt i = SI->caseBegin(), e = SI->caseEnd(); 114 i != e; ++i) { 115 // Found case matching a constant operand? 116 if (i.getCaseValue() == CI) { 117 TheOnlyDest = i.getCaseSuccessor(); 118 break; 119 } 120 121 // Check to see if this branch is going to the same place as the default 122 // dest. If so, eliminate it as an explicit compare. 123 if (i.getCaseSuccessor() == DefaultDest) { 124 // Remove this entry. 125 DefaultDest->removePredecessor(SI->getParent()); 126 SI->removeCase(i); 127 --i; --e; 128 continue; 129 } 130 131 // Otherwise, check to see if the switch only branches to one destination. 132 // We do this by reseting "TheOnlyDest" to null when we find two non-equal 133 // destinations. 134 if (i.getCaseSuccessor() != TheOnlyDest) TheOnlyDest = 0; 135 } 136 137 if (CI && !TheOnlyDest) { 138 // Branching on a constant, but not any of the cases, go to the default 139 // successor. 140 TheOnlyDest = SI->getDefaultDest(); 141 } 142 143 // If we found a single destination that we can fold the switch into, do so 144 // now. 145 if (TheOnlyDest) { 146 // Insert the new branch. 147 Builder.CreateBr(TheOnlyDest); 148 BasicBlock *BB = SI->getParent(); 149 150 // Remove entries from PHI nodes which we no longer branch to... 151 for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { 152 // Found case matching a constant operand? 153 BasicBlock *Succ = SI->getSuccessor(i); 154 if (Succ == TheOnlyDest) 155 TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest 156 else 157 Succ->removePredecessor(BB); 158 } 159 160 // Delete the old switch. 161 Value *Cond = SI->getCondition(); 162 SI->eraseFromParent(); 163 if (DeleteDeadConditions) 164 RecursivelyDeleteTriviallyDeadInstructions(Cond); 165 return true; 166 } 167 168 if (SI->getNumCases() == 1) { 169 // Otherwise, we can fold this switch into a conditional branch 170 // instruction if it has only one non-default destination. 171 SwitchInst::CaseIt FirstCase = SI->caseBegin(); 172 Value *Cond = Builder.CreateICmpEQ(SI->getCondition(), 173 FirstCase.getCaseValue(), "cond"); 174 175 // Insert the new branch. 176 Builder.CreateCondBr(Cond, FirstCase.getCaseSuccessor(), 177 SI->getDefaultDest()); 178 179 // Delete the old switch. 180 SI->eraseFromParent(); 181 return true; 182 } 183 return false; 184 } 185 186 if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(T)) { 187 // indirectbr blockaddress(@F, @BB) -> br label @BB 188 if (BlockAddress *BA = 189 dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) { 190 BasicBlock *TheOnlyDest = BA->getBasicBlock(); 191 // Insert the new branch. 192 Builder.CreateBr(TheOnlyDest); 193 194 for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) { 195 if (IBI->getDestination(i) == TheOnlyDest) 196 TheOnlyDest = 0; 197 else 198 IBI->getDestination(i)->removePredecessor(IBI->getParent()); 199 } 200 Value *Address = IBI->getAddress(); 201 IBI->eraseFromParent(); 202 if (DeleteDeadConditions) 203 RecursivelyDeleteTriviallyDeadInstructions(Address); 204 205 // If we didn't find our destination in the IBI successor list, then we 206 // have undefined behavior. Replace the unconditional branch with an 207 // 'unreachable' instruction. 208 if (TheOnlyDest) { 209 BB->getTerminator()->eraseFromParent(); 210 new UnreachableInst(BB->getContext(), BB); 211 } 212 213 return true; 214 } 215 } 216 217 return false; 218} 219 220 221//===----------------------------------------------------------------------===// 222// Local dead code elimination. 223// 224 225/// isInstructionTriviallyDead - Return true if the result produced by the 226/// instruction is not used, and the instruction has no side effects. 227/// 228bool llvm::isInstructionTriviallyDead(Instruction *I) { 229 if (!I->use_empty() || isa<TerminatorInst>(I)) return false; 230 231 // We don't want the landingpad instruction removed by anything this general. 232 if (isa<LandingPadInst>(I)) 233 return false; 234 235 // We don't want debug info removed by anything this general, unless 236 // debug info is empty. 237 if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) { 238 if (DDI->getAddress()) 239 return false; 240 return true; 241 } 242 if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) { 243 if (DVI->getValue()) 244 return false; 245 return true; 246 } 247 248 if (!I->mayHaveSideEffects()) return true; 249 250 // Special case intrinsics that "may have side effects" but can be deleted 251 // when dead. 252 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 253 // Safe to delete llvm.stacksave if dead. 254 if (II->getIntrinsicID() == Intrinsic::stacksave) 255 return true; 256 257 // Lifetime intrinsics are dead when their right-hand is undef. 258 if (II->getIntrinsicID() == Intrinsic::lifetime_start || 259 II->getIntrinsicID() == Intrinsic::lifetime_end) 260 return isa<UndefValue>(II->getArgOperand(1)); 261 } 262 263 if (extractMallocCall(I)) return true; 264 265 if (CallInst *CI = isFreeCall(I)) 266 if (Constant *C = dyn_cast<Constant>(CI->getArgOperand(0))) 267 return C->isNullValue() || isa<UndefValue>(C); 268 269 return false; 270} 271 272/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a 273/// trivially dead instruction, delete it. If that makes any of its operands 274/// trivially dead, delete them too, recursively. Return true if any 275/// instructions were deleted. 276bool llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V) { 277 Instruction *I = dyn_cast<Instruction>(V); 278 if (!I || !I->use_empty() || !isInstructionTriviallyDead(I)) 279 return false; 280 281 SmallVector<Instruction*, 16> DeadInsts; 282 DeadInsts.push_back(I); 283 284 do { 285 I = DeadInsts.pop_back_val(); 286 287 // Null out all of the instruction's operands to see if any operand becomes 288 // dead as we go. 289 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 290 Value *OpV = I->getOperand(i); 291 I->setOperand(i, 0); 292 293 if (!OpV->use_empty()) continue; 294 295 // If the operand is an instruction that became dead as we nulled out the 296 // operand, and if it is 'trivially' dead, delete it in a future loop 297 // iteration. 298 if (Instruction *OpI = dyn_cast<Instruction>(OpV)) 299 if (isInstructionTriviallyDead(OpI)) 300 DeadInsts.push_back(OpI); 301 } 302 303 I->eraseFromParent(); 304 } while (!DeadInsts.empty()); 305 306 return true; 307} 308 309/// areAllUsesEqual - Check whether the uses of a value are all the same. 310/// This is similar to Instruction::hasOneUse() except this will also return 311/// true when there are no uses or multiple uses that all refer to the same 312/// value. 313static bool areAllUsesEqual(Instruction *I) { 314 Value::use_iterator UI = I->use_begin(); 315 Value::use_iterator UE = I->use_end(); 316 if (UI == UE) 317 return true; 318 319 User *TheUse = *UI; 320 for (++UI; UI != UE; ++UI) { 321 if (*UI != TheUse) 322 return false; 323 } 324 return true; 325} 326 327/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively 328/// dead PHI node, due to being a def-use chain of single-use nodes that 329/// either forms a cycle or is terminated by a trivially dead instruction, 330/// delete it. If that makes any of its operands trivially dead, delete them 331/// too, recursively. Return true if a change was made. 332bool llvm::RecursivelyDeleteDeadPHINode(PHINode *PN) { 333 SmallPtrSet<Instruction*, 4> Visited; 334 for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects(); 335 I = cast<Instruction>(*I->use_begin())) { 336 if (I->use_empty()) 337 return RecursivelyDeleteTriviallyDeadInstructions(I); 338 339 // If we find an instruction more than once, we're on a cycle that 340 // won't prove fruitful. 341 if (!Visited.insert(I)) { 342 // Break the cycle and delete the instruction and its operands. 343 I->replaceAllUsesWith(UndefValue::get(I->getType())); 344 (void)RecursivelyDeleteTriviallyDeadInstructions(I); 345 return true; 346 } 347 } 348 return false; 349} 350 351/// SimplifyInstructionsInBlock - Scan the specified basic block and try to 352/// simplify any instructions in it and recursively delete dead instructions. 353/// 354/// This returns true if it changed the code, note that it can delete 355/// instructions in other blocks as well in this block. 356bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB, const TargetData *TD) { 357 bool MadeChange = false; 358 for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) { 359 Instruction *Inst = BI++; 360 361 if (Value *V = SimplifyInstruction(Inst, TD)) { 362 WeakVH BIHandle(BI); 363 ReplaceAndSimplifyAllUses(Inst, V, TD); 364 MadeChange = true; 365 if (BIHandle != BI) 366 BI = BB->begin(); 367 continue; 368 } 369 370 if (Inst->isTerminator()) 371 break; 372 373 WeakVH BIHandle(BI); 374 MadeChange |= RecursivelyDeleteTriviallyDeadInstructions(Inst); 375 if (BIHandle != BI) 376 BI = BB->begin(); 377 } 378 return MadeChange; 379} 380 381//===----------------------------------------------------------------------===// 382// Control Flow Graph Restructuring. 383// 384 385 386/// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this 387/// method is called when we're about to delete Pred as a predecessor of BB. If 388/// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred. 389/// 390/// Unlike the removePredecessor method, this attempts to simplify uses of PHI 391/// nodes that collapse into identity values. For example, if we have: 392/// x = phi(1, 0, 0, 0) 393/// y = and x, z 394/// 395/// .. and delete the predecessor corresponding to the '1', this will attempt to 396/// recursively fold the and to 0. 397void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred, 398 TargetData *TD) { 399 // This only adjusts blocks with PHI nodes. 400 if (!isa<PHINode>(BB->begin())) 401 return; 402 403 // Remove the entries for Pred from the PHI nodes in BB, but do not simplify 404 // them down. This will leave us with single entry phi nodes and other phis 405 // that can be removed. 406 BB->removePredecessor(Pred, true); 407 408 WeakVH PhiIt = &BB->front(); 409 while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) { 410 PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt)); 411 412 Value *PNV = SimplifyInstruction(PN, TD); 413 if (PNV == 0) continue; 414 415 // If we're able to simplify the phi to a single value, substitute the new 416 // value into all of its uses. 417 assert(PNV != PN && "SimplifyInstruction broken!"); 418 419 Value *OldPhiIt = PhiIt; 420 ReplaceAndSimplifyAllUses(PN, PNV, TD); 421 422 // If recursive simplification ended up deleting the next PHI node we would 423 // iterate to, then our iterator is invalid, restart scanning from the top 424 // of the block. 425 if (PhiIt != OldPhiIt) PhiIt = &BB->front(); 426 } 427} 428 429 430/// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its 431/// predecessor is known to have one successor (DestBB!). Eliminate the edge 432/// between them, moving the instructions in the predecessor into DestBB and 433/// deleting the predecessor block. 434/// 435void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, Pass *P) { 436 // If BB has single-entry PHI nodes, fold them. 437 while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) { 438 Value *NewVal = PN->getIncomingValue(0); 439 // Replace self referencing PHI with undef, it must be dead. 440 if (NewVal == PN) NewVal = UndefValue::get(PN->getType()); 441 PN->replaceAllUsesWith(NewVal); 442 PN->eraseFromParent(); 443 } 444 445 BasicBlock *PredBB = DestBB->getSinglePredecessor(); 446 assert(PredBB && "Block doesn't have a single predecessor!"); 447 448 // Zap anything that took the address of DestBB. Not doing this will give the 449 // address an invalid value. 450 if (DestBB->hasAddressTaken()) { 451 BlockAddress *BA = BlockAddress::get(DestBB); 452 Constant *Replacement = 453 ConstantInt::get(llvm::Type::getInt32Ty(BA->getContext()), 1); 454 BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement, 455 BA->getType())); 456 BA->destroyConstant(); 457 } 458 459 // Anything that branched to PredBB now branches to DestBB. 460 PredBB->replaceAllUsesWith(DestBB); 461 462 // Splice all the instructions from PredBB to DestBB. 463 PredBB->getTerminator()->eraseFromParent(); 464 DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList()); 465 466 if (P) { 467 DominatorTree *DT = P->getAnalysisIfAvailable<DominatorTree>(); 468 if (DT) { 469 BasicBlock *PredBBIDom = DT->getNode(PredBB)->getIDom()->getBlock(); 470 DT->changeImmediateDominator(DestBB, PredBBIDom); 471 DT->eraseNode(PredBB); 472 } 473 ProfileInfo *PI = P->getAnalysisIfAvailable<ProfileInfo>(); 474 if (PI) { 475 PI->replaceAllUses(PredBB, DestBB); 476 PI->removeEdge(ProfileInfo::getEdge(PredBB, DestBB)); 477 } 478 } 479 // Nuke BB. 480 PredBB->eraseFromParent(); 481} 482 483/// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an 484/// almost-empty BB ending in an unconditional branch to Succ, into succ. 485/// 486/// Assumption: Succ is the single successor for BB. 487/// 488static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 489 assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 490 491 DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into " 492 << Succ->getName() << "\n"); 493 // Shortcut, if there is only a single predecessor it must be BB and merging 494 // is always safe 495 if (Succ->getSinglePredecessor()) return true; 496 497 // Make a list of the predecessors of BB 498 SmallPtrSet<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB)); 499 500 // Look at all the phi nodes in Succ, to see if they present a conflict when 501 // merging these blocks 502 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 503 PHINode *PN = cast<PHINode>(I); 504 505 // If the incoming value from BB is again a PHINode in 506 // BB which has the same incoming value for *PI as PN does, we can 507 // merge the phi nodes and then the blocks can still be merged 508 PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB)); 509 if (BBPN && BBPN->getParent() == BB) { 510 for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) { 511 BasicBlock *IBB = PN->getIncomingBlock(PI); 512 if (BBPreds.count(IBB) && 513 BBPN->getIncomingValueForBlock(IBB) != PN->getIncomingValue(PI)) { 514 DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in " 515 << Succ->getName() << " is conflicting with " 516 << BBPN->getName() << " with regard to common predecessor " 517 << IBB->getName() << "\n"); 518 return false; 519 } 520 } 521 } else { 522 Value* Val = PN->getIncomingValueForBlock(BB); 523 for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) { 524 // See if the incoming value for the common predecessor is equal to the 525 // one for BB, in which case this phi node will not prevent the merging 526 // of the block. 527 BasicBlock *IBB = PN->getIncomingBlock(PI); 528 if (BBPreds.count(IBB) && Val != PN->getIncomingValue(PI)) { 529 DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in " 530 << Succ->getName() << " is conflicting with regard to common " 531 << "predecessor " << IBB->getName() << "\n"); 532 return false; 533 } 534 } 535 } 536 } 537 538 return true; 539} 540 541/// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an 542/// unconditional branch, and contains no instructions other than PHI nodes, 543/// potential side-effect free intrinsics and the branch. If possible, 544/// eliminate BB by rewriting all the predecessors to branch to the successor 545/// block and return true. If we can't transform, return false. 546bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) { 547 assert(BB != &BB->getParent()->getEntryBlock() && 548 "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!"); 549 550 // We can't eliminate infinite loops. 551 BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0); 552 if (BB == Succ) return false; 553 554 // Check to see if merging these blocks would cause conflicts for any of the 555 // phi nodes in BB or Succ. If not, we can safely merge. 556 if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false; 557 558 // Check for cases where Succ has multiple predecessors and a PHI node in BB 559 // has uses which will not disappear when the PHI nodes are merged. It is 560 // possible to handle such cases, but difficult: it requires checking whether 561 // BB dominates Succ, which is non-trivial to calculate in the case where 562 // Succ has multiple predecessors. Also, it requires checking whether 563 // constructing the necessary self-referential PHI node doesn't intoduce any 564 // conflicts; this isn't too difficult, but the previous code for doing this 565 // was incorrect. 566 // 567 // Note that if this check finds a live use, BB dominates Succ, so BB is 568 // something like a loop pre-header (or rarely, a part of an irreducible CFG); 569 // folding the branch isn't profitable in that case anyway. 570 if (!Succ->getSinglePredecessor()) { 571 BasicBlock::iterator BBI = BB->begin(); 572 while (isa<PHINode>(*BBI)) { 573 for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end(); 574 UI != E; ++UI) { 575 if (PHINode* PN = dyn_cast<PHINode>(*UI)) { 576 if (PN->getIncomingBlock(UI) != BB) 577 return false; 578 } else { 579 return false; 580 } 581 } 582 ++BBI; 583 } 584 } 585 586 DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB); 587 588 if (isa<PHINode>(Succ->begin())) { 589 // If there is more than one pred of succ, and there are PHI nodes in 590 // the successor, then we need to add incoming edges for the PHI nodes 591 // 592 const SmallVector<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB)); 593 594 // Loop over all of the PHI nodes in the successor of BB. 595 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 596 PHINode *PN = cast<PHINode>(I); 597 Value *OldVal = PN->removeIncomingValue(BB, false); 598 assert(OldVal && "No entry in PHI for Pred BB!"); 599 600 // If this incoming value is one of the PHI nodes in BB, the new entries 601 // in the PHI node are the entries from the old PHI. 602 if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { 603 PHINode *OldValPN = cast<PHINode>(OldVal); 604 for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) 605 // Note that, since we are merging phi nodes and BB and Succ might 606 // have common predecessors, we could end up with a phi node with 607 // identical incoming branches. This will be cleaned up later (and 608 // will trigger asserts if we try to clean it up now, without also 609 // simplifying the corresponding conditional branch). 610 PN->addIncoming(OldValPN->getIncomingValue(i), 611 OldValPN->getIncomingBlock(i)); 612 } else { 613 // Add an incoming value for each of the new incoming values. 614 for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) 615 PN->addIncoming(OldVal, BBPreds[i]); 616 } 617 } 618 } 619 620 if (Succ->getSinglePredecessor()) { 621 // BB is the only predecessor of Succ, so Succ will end up with exactly 622 // the same predecessors BB had. 623 624 // Copy over any phi, debug or lifetime instruction. 625 BB->getTerminator()->eraseFromParent(); 626 Succ->getInstList().splice(Succ->getFirstNonPHI(), BB->getInstList()); 627 } else { 628 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 629 // We explicitly check for such uses in CanPropagatePredecessorsForPHIs. 630 assert(PN->use_empty() && "There shouldn't be any uses here!"); 631 PN->eraseFromParent(); 632 } 633 } 634 635 // Everything that jumped to BB now goes to Succ. 636 BB->replaceAllUsesWith(Succ); 637 if (!Succ->hasName()) Succ->takeName(BB); 638 BB->eraseFromParent(); // Delete the old basic block. 639 return true; 640} 641 642/// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI 643/// nodes in this block. This doesn't try to be clever about PHI nodes 644/// which differ only in the order of the incoming values, but instcombine 645/// orders them so it usually won't matter. 646/// 647bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { 648 bool Changed = false; 649 650 // This implementation doesn't currently consider undef operands 651 // specially. Theoretically, two phis which are identical except for 652 // one having an undef where the other doesn't could be collapsed. 653 654 // Map from PHI hash values to PHI nodes. If multiple PHIs have 655 // the same hash value, the element is the first PHI in the 656 // linked list in CollisionMap. 657 DenseMap<uintptr_t, PHINode *> HashMap; 658 659 // Maintain linked lists of PHI nodes with common hash values. 660 DenseMap<PHINode *, PHINode *> CollisionMap; 661 662 // Examine each PHI. 663 for (BasicBlock::iterator I = BB->begin(); 664 PHINode *PN = dyn_cast<PHINode>(I++); ) { 665 // Compute a hash value on the operands. Instcombine will likely have sorted 666 // them, which helps expose duplicates, but we have to check all the 667 // operands to be safe in case instcombine hasn't run. 668 uintptr_t Hash = 0; 669 // This hash algorithm is quite weak as hash functions go, but it seems 670 // to do a good enough job for this particular purpose, and is very quick. 671 for (User::op_iterator I = PN->op_begin(), E = PN->op_end(); I != E; ++I) { 672 Hash ^= reinterpret_cast<uintptr_t>(static_cast<Value *>(*I)); 673 Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7)); 674 } 675 for (PHINode::block_iterator I = PN->block_begin(), E = PN->block_end(); 676 I != E; ++I) { 677 Hash ^= reinterpret_cast<uintptr_t>(static_cast<BasicBlock *>(*I)); 678 Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7)); 679 } 680 // Avoid colliding with the DenseMap sentinels ~0 and ~0-1. 681 Hash >>= 1; 682 // If we've never seen this hash value before, it's a unique PHI. 683 std::pair<DenseMap<uintptr_t, PHINode *>::iterator, bool> Pair = 684 HashMap.insert(std::make_pair(Hash, PN)); 685 if (Pair.second) continue; 686 // Otherwise it's either a duplicate or a hash collision. 687 for (PHINode *OtherPN = Pair.first->second; ; ) { 688 if (OtherPN->isIdenticalTo(PN)) { 689 // A duplicate. Replace this PHI with its duplicate. 690 PN->replaceAllUsesWith(OtherPN); 691 PN->eraseFromParent(); 692 Changed = true; 693 break; 694 } 695 // A non-duplicate hash collision. 696 DenseMap<PHINode *, PHINode *>::iterator I = CollisionMap.find(OtherPN); 697 if (I == CollisionMap.end()) { 698 // Set this PHI to be the head of the linked list of colliding PHIs. 699 PHINode *Old = Pair.first->second; 700 Pair.first->second = PN; 701 CollisionMap[PN] = Old; 702 break; 703 } 704 // Procede to the next PHI in the list. 705 OtherPN = I->second; 706 } 707 } 708 709 return Changed; 710} 711 712/// enforceKnownAlignment - If the specified pointer points to an object that 713/// we control, modify the object's alignment to PrefAlign. This isn't 714/// often possible though. If alignment is important, a more reliable approach 715/// is to simply align all global variables and allocation instructions to 716/// their preferred alignment from the beginning. 717/// 718static unsigned enforceKnownAlignment(Value *V, unsigned Align, 719 unsigned PrefAlign, const TargetData *TD) { 720 V = V->stripPointerCasts(); 721 722 if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) { 723 // If the preferred alignment is greater than the natural stack alignment 724 // then don't round up. This avoids dynamic stack realignment. 725 if (TD && TD->exceedsNaturalStackAlignment(PrefAlign)) 726 return Align; 727 // If there is a requested alignment and if this is an alloca, round up. 728 if (AI->getAlignment() >= PrefAlign) 729 return AI->getAlignment(); 730 AI->setAlignment(PrefAlign); 731 return PrefAlign; 732 } 733 734 if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 735 // If there is a large requested alignment and we can, bump up the alignment 736 // of the global. 737 if (GV->isDeclaration()) return Align; 738 // If the memory we set aside for the global may not be the memory used by 739 // the final program then it is impossible for us to reliably enforce the 740 // preferred alignment. 741 if (GV->isWeakForLinker()) return Align; 742 743 if (GV->getAlignment() >= PrefAlign) 744 return GV->getAlignment(); 745 // We can only increase the alignment of the global if it has no alignment 746 // specified or if it is not assigned a section. If it is assigned a 747 // section, the global could be densely packed with other objects in the 748 // section, increasing the alignment could cause padding issues. 749 if (!GV->hasSection() || GV->getAlignment() == 0) 750 GV->setAlignment(PrefAlign); 751 return GV->getAlignment(); 752 } 753 754 return Align; 755} 756 757/// getOrEnforceKnownAlignment - If the specified pointer has an alignment that 758/// we can determine, return it, otherwise return 0. If PrefAlign is specified, 759/// and it is more than the alignment of the ultimate object, see if we can 760/// increase the alignment of the ultimate object, making this check succeed. 761unsigned llvm::getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, 762 const TargetData *TD) { 763 assert(V->getType()->isPointerTy() && 764 "getOrEnforceKnownAlignment expects a pointer!"); 765 unsigned BitWidth = TD ? TD->getPointerSizeInBits() : 64; 766 APInt Mask = APInt::getAllOnesValue(BitWidth); 767 APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); 768 ComputeMaskedBits(V, Mask, KnownZero, KnownOne, TD); 769 unsigned TrailZ = KnownZero.countTrailingOnes(); 770 771 // Avoid trouble with rediculously large TrailZ values, such as 772 // those computed from a null pointer. 773 TrailZ = std::min(TrailZ, unsigned(sizeof(unsigned) * CHAR_BIT - 1)); 774 775 unsigned Align = 1u << std::min(BitWidth - 1, TrailZ); 776 777 // LLVM doesn't support alignments larger than this currently. 778 Align = std::min(Align, +Value::MaximumAlignment); 779 780 if (PrefAlign > Align) 781 Align = enforceKnownAlignment(V, Align, PrefAlign, TD); 782 783 // We don't need to make any adjustment. 784 return Align; 785} 786 787///===---------------------------------------------------------------------===// 788/// Dbg Intrinsic utilities 789/// 790 791/// Inserts a llvm.dbg.value instrinsic before the stores to an alloca'd value 792/// that has an associated llvm.dbg.decl intrinsic. 793bool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, 794 StoreInst *SI, DIBuilder &Builder) { 795 DIVariable DIVar(DDI->getVariable()); 796 if (!DIVar.Verify()) 797 return false; 798 799 Instruction *DbgVal = NULL; 800 // If an argument is zero extended then use argument directly. The ZExt 801 // may be zapped by an optimization pass in future. 802 Argument *ExtendedArg = NULL; 803 if (ZExtInst *ZExt = dyn_cast<ZExtInst>(SI->getOperand(0))) 804 ExtendedArg = dyn_cast<Argument>(ZExt->getOperand(0)); 805 if (SExtInst *SExt = dyn_cast<SExtInst>(SI->getOperand(0))) 806 ExtendedArg = dyn_cast<Argument>(SExt->getOperand(0)); 807 if (ExtendedArg) 808 DbgVal = Builder.insertDbgValueIntrinsic(ExtendedArg, 0, DIVar, SI); 809 else 810 DbgVal = Builder.insertDbgValueIntrinsic(SI->getOperand(0), 0, DIVar, SI); 811 812 // Propagate any debug metadata from the store onto the dbg.value. 813 DebugLoc SIDL = SI->getDebugLoc(); 814 if (!SIDL.isUnknown()) 815 DbgVal->setDebugLoc(SIDL); 816 // Otherwise propagate debug metadata from dbg.declare. 817 else 818 DbgVal->setDebugLoc(DDI->getDebugLoc()); 819 return true; 820} 821 822/// Inserts a llvm.dbg.value instrinsic before the stores to an alloca'd value 823/// that has an associated llvm.dbg.decl intrinsic. 824bool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, 825 LoadInst *LI, DIBuilder &Builder) { 826 DIVariable DIVar(DDI->getVariable()); 827 if (!DIVar.Verify()) 828 return false; 829 830 Instruction *DbgVal = 831 Builder.insertDbgValueIntrinsic(LI->getOperand(0), 0, 832 DIVar, LI); 833 834 // Propagate any debug metadata from the store onto the dbg.value. 835 DebugLoc LIDL = LI->getDebugLoc(); 836 if (!LIDL.isUnknown()) 837 DbgVal->setDebugLoc(LIDL); 838 // Otherwise propagate debug metadata from dbg.declare. 839 else 840 DbgVal->setDebugLoc(DDI->getDebugLoc()); 841 return true; 842} 843 844/// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set 845/// of llvm.dbg.value intrinsics. 846bool llvm::LowerDbgDeclare(Function &F) { 847 DIBuilder DIB(*F.getParent()); 848 SmallVector<DbgDeclareInst *, 4> Dbgs; 849 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 850 for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ++BI) { 851 if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(BI)) 852 Dbgs.push_back(DDI); 853 } 854 if (Dbgs.empty()) 855 return false; 856 857 for (SmallVector<DbgDeclareInst *, 4>::iterator I = Dbgs.begin(), 858 E = Dbgs.end(); I != E; ++I) { 859 DbgDeclareInst *DDI = *I; 860 if (AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress())) { 861 bool RemoveDDI = true; 862 for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); 863 UI != E; ++UI) 864 if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) 865 ConvertDebugDeclareToDebugValue(DDI, SI, DIB); 866 else if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) 867 ConvertDebugDeclareToDebugValue(DDI, LI, DIB); 868 else 869 RemoveDDI = false; 870 if (RemoveDDI) 871 DDI->eraseFromParent(); 872 } 873 } 874 return true; 875} 876 877/// FindAllocaDbgDeclare - Finds the llvm.dbg.declare intrinsic describing the 878/// alloca 'V', if any. 879DbgDeclareInst *llvm::FindAllocaDbgDeclare(Value *V) { 880 if (MDNode *DebugNode = MDNode::getIfExists(V->getContext(), V)) 881 for (Value::use_iterator UI = DebugNode->use_begin(), 882 E = DebugNode->use_end(); UI != E; ++UI) 883 if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(*UI)) 884 return DDI; 885 886 return 0; 887} 888