1193323Sed//===-- Local.cpp - Functions to perform local transformations ------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This family of functions perform various local transformations to the 11193323Sed// program. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15193323Sed#include "llvm/Transforms/Utils/Local.h" 16201360Srdivacky#include "llvm/ADT/DenseMap.h" 17288943Sdim#include "llvm/ADT/DenseSet.h" 18288943Sdim#include "llvm/ADT/Hashing.h" 19249423Sdim#include "llvm/ADT/STLExtras.h" 20296417Sdim#include "llvm/ADT/SetVector.h" 21193323Sed#include "llvm/ADT/SmallPtrSet.h" 22261991Sdim#include "llvm/ADT/Statistic.h" 23296417Sdim#include "llvm/Analysis/EHPersonalities.h" 24199481Srdivacky#include "llvm/Analysis/InstructionSimplify.h" 25234353Sdim#include "llvm/Analysis/MemoryBuiltins.h" 26296417Sdim#include "llvm/Analysis/LazyValueInfo.h" 27218893Sdim#include "llvm/Analysis/ValueTracking.h" 28276479Sdim#include "llvm/IR/CFG.h" 29249423Sdim#include "llvm/IR/Constants.h" 30276479Sdim#include "llvm/IR/DIBuilder.h" 31249423Sdim#include "llvm/IR/DataLayout.h" 32276479Sdim#include "llvm/IR/DebugInfo.h" 33249423Sdim#include "llvm/IR/DerivedTypes.h" 34276479Sdim#include "llvm/IR/Dominators.h" 35276479Sdim#include "llvm/IR/GetElementPtrTypeIterator.h" 36249423Sdim#include "llvm/IR/GlobalAlias.h" 37249423Sdim#include "llvm/IR/GlobalVariable.h" 38249423Sdim#include "llvm/IR/IRBuilder.h" 39249423Sdim#include "llvm/IR/Instructions.h" 40249423Sdim#include "llvm/IR/IntrinsicInst.h" 41249423Sdim#include "llvm/IR/Intrinsics.h" 42249423Sdim#include "llvm/IR/MDBuilder.h" 43249423Sdim#include "llvm/IR/Metadata.h" 44249423Sdim#include "llvm/IR/Operator.h" 45276479Sdim#include "llvm/IR/ValueHandle.h" 46199481Srdivacky#include "llvm/Support/Debug.h" 47193323Sed#include "llvm/Support/MathExtras.h" 48199481Srdivacky#include "llvm/Support/raw_ostream.h" 49193323Sedusing namespace llvm; 50193323Sed 51276479Sdim#define DEBUG_TYPE "local" 52276479Sdim 53261991SdimSTATISTIC(NumRemoved, "Number of unreachable basic blocks removed"); 54261991Sdim 55193323Sed//===----------------------------------------------------------------------===// 56193323Sed// Local constant propagation. 57193323Sed// 58193323Sed 59223017Sdim/// ConstantFoldTerminator - If a terminator instruction is predicated on a 60223017Sdim/// constant value, convert it into an unconditional branch to the constant 61223017Sdim/// destination. This is a nontrivial operation because the successors of this 62223017Sdim/// basic block must have their PHI nodes updated. 63223017Sdim/// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch 64223017Sdim/// conditions and indirectbr addresses this might make dead if 65223017Sdim/// DeleteDeadConditions is true. 66243830Sdimbool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, 67243830Sdim const TargetLibraryInfo *TLI) { 68193323Sed TerminatorInst *T = BB->getTerminator(); 69223017Sdim IRBuilder<> Builder(T); 70193323Sed 71193323Sed // Branch - See if we are conditional jumping on constant 72193323Sed if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 73193323Sed if (BI->isUnconditional()) return false; // Can't optimize uncond branch 74193323Sed BasicBlock *Dest1 = BI->getSuccessor(0); 75193323Sed BasicBlock *Dest2 = BI->getSuccessor(1); 76193323Sed 77193323Sed if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) { 78193323Sed // Are we branching on constant? 79193323Sed // YES. Change to unconditional branch... 80193323Sed BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2; 81193323Sed BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1; 82193323Sed 83193323Sed //cerr << "Function: " << T->getParent()->getParent() 84193323Sed // << "\nRemoving branch from " << T->getParent() 85193323Sed // << "\n\nTo: " << OldDest << endl; 86193323Sed 87193323Sed // Let the basic block know that we are letting go of it. Based on this, 88193323Sed // it will adjust it's PHI nodes. 89221345Sdim OldDest->removePredecessor(BB); 90193323Sed 91218893Sdim // Replace the conditional branch with an unconditional one. 92223017Sdim Builder.CreateBr(Destination); 93218893Sdim BI->eraseFromParent(); 94193323Sed return true; 95198892Srdivacky } 96261991Sdim 97198892Srdivacky if (Dest2 == Dest1) { // Conditional branch to same location? 98193323Sed // This branch matches something like this: 99193323Sed // br bool %cond, label %Dest, label %Dest 100193323Sed // and changes it into: br label %Dest 101193323Sed 102193323Sed // Let the basic block know that we are letting go of one copy of it. 103193323Sed assert(BI->getParent() && "Terminator not inserted in block!"); 104193323Sed Dest1->removePredecessor(BI->getParent()); 105193323Sed 106218893Sdim // Replace the conditional branch with an unconditional one. 107223017Sdim Builder.CreateBr(Dest1); 108223017Sdim Value *Cond = BI->getCondition(); 109218893Sdim BI->eraseFromParent(); 110223017Sdim if (DeleteDeadConditions) 111243830Sdim RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI); 112193323Sed return true; 113193323Sed } 114198892Srdivacky return false; 115198892Srdivacky } 116261991Sdim 117198892Srdivacky if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { 118288943Sdim // If we are switching on a constant, we can convert the switch to an 119288943Sdim // unconditional branch. 120193323Sed ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); 121288943Sdim BasicBlock *DefaultDest = SI->getDefaultDest(); 122288943Sdim BasicBlock *TheOnlyDest = DefaultDest; 123193323Sed 124288943Sdim // If the default is unreachable, ignore it when searching for TheOnlyDest. 125288943Sdim if (isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg()) && 126288943Sdim SI->getNumCases() > 0) { 127288943Sdim TheOnlyDest = SI->case_begin().getCaseSuccessor(); 128288943Sdim } 129288943Sdim 130198892Srdivacky // Figure out which case it goes to. 131234353Sdim for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); 132234353Sdim i != e; ++i) { 133193323Sed // Found case matching a constant operand? 134234353Sdim if (i.getCaseValue() == CI) { 135234353Sdim TheOnlyDest = i.getCaseSuccessor(); 136193323Sed break; 137193323Sed } 138193323Sed 139193323Sed // Check to see if this branch is going to the same place as the default 140193323Sed // dest. If so, eliminate it as an explicit compare. 141234353Sdim if (i.getCaseSuccessor() == DefaultDest) { 142280031Sdim MDNode *MD = SI->getMetadata(LLVMContext::MD_prof); 143276479Sdim unsigned NCases = SI->getNumCases(); 144276479Sdim // Fold the case metadata into the default if there will be any branches 145276479Sdim // left, unless the metadata doesn't match the switch. 146276479Sdim if (NCases > 1 && MD && MD->getNumOperands() == 2 + NCases) { 147243830Sdim // Collect branch weights into a vector. 148243830Sdim SmallVector<uint32_t, 8> Weights; 149243830Sdim for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e; 150243830Sdim ++MD_i) { 151280031Sdim ConstantInt *CI = 152280031Sdim mdconst::dyn_extract<ConstantInt>(MD->getOperand(MD_i)); 153243830Sdim assert(CI); 154243830Sdim Weights.push_back(CI->getValue().getZExtValue()); 155243830Sdim } 156243830Sdim // Merge weight of this case to the default weight. 157243830Sdim unsigned idx = i.getCaseIndex(); 158243830Sdim Weights[0] += Weights[idx+1]; 159243830Sdim // Remove weight for this case. 160243830Sdim std::swap(Weights[idx+1], Weights.back()); 161243830Sdim Weights.pop_back(); 162243830Sdim SI->setMetadata(LLVMContext::MD_prof, 163243830Sdim MDBuilder(BB->getContext()). 164243830Sdim createBranchWeights(Weights)); 165243830Sdim } 166198892Srdivacky // Remove this entry. 167193323Sed DefaultDest->removePredecessor(SI->getParent()); 168193323Sed SI->removeCase(i); 169234353Sdim --i; --e; 170193323Sed continue; 171193323Sed } 172193323Sed 173193323Sed // Otherwise, check to see if the switch only branches to one destination. 174193323Sed // We do this by reseting "TheOnlyDest" to null when we find two non-equal 175193323Sed // destinations. 176276479Sdim if (i.getCaseSuccessor() != TheOnlyDest) TheOnlyDest = nullptr; 177193323Sed } 178193323Sed 179193323Sed if (CI && !TheOnlyDest) { 180193323Sed // Branching on a constant, but not any of the cases, go to the default 181193323Sed // successor. 182193323Sed TheOnlyDest = SI->getDefaultDest(); 183193323Sed } 184193323Sed 185193323Sed // If we found a single destination that we can fold the switch into, do so 186193323Sed // now. 187193323Sed if (TheOnlyDest) { 188198892Srdivacky // Insert the new branch. 189223017Sdim Builder.CreateBr(TheOnlyDest); 190193323Sed BasicBlock *BB = SI->getParent(); 191193323Sed 192193323Sed // Remove entries from PHI nodes which we no longer branch to... 193296417Sdim for (BasicBlock *Succ : SI->successors()) { 194193323Sed // Found case matching a constant operand? 195193323Sed if (Succ == TheOnlyDest) 196276479Sdim TheOnlyDest = nullptr; // Don't modify the first branch to TheOnlyDest 197193323Sed else 198193323Sed Succ->removePredecessor(BB); 199193323Sed } 200193323Sed 201198892Srdivacky // Delete the old switch. 202223017Sdim Value *Cond = SI->getCondition(); 203223017Sdim SI->eraseFromParent(); 204223017Sdim if (DeleteDeadConditions) 205243830Sdim RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI); 206193323Sed return true; 207198892Srdivacky } 208261991Sdim 209234353Sdim if (SI->getNumCases() == 1) { 210193323Sed // Otherwise, we can fold this switch into a conditional branch 211193323Sed // instruction if it has only one non-default destination. 212234353Sdim SwitchInst::CaseIt FirstCase = SI->case_begin(); 213261991Sdim Value *Cond = Builder.CreateICmpEQ(SI->getCondition(), 214261991Sdim FirstCase.getCaseValue(), "cond"); 215223017Sdim 216261991Sdim // Insert the new branch. 217261991Sdim BranchInst *NewBr = Builder.CreateCondBr(Cond, 218261991Sdim FirstCase.getCaseSuccessor(), 219261991Sdim SI->getDefaultDest()); 220280031Sdim MDNode *MD = SI->getMetadata(LLVMContext::MD_prof); 221261991Sdim if (MD && MD->getNumOperands() == 3) { 222280031Sdim ConstantInt *SICase = 223280031Sdim mdconst::dyn_extract<ConstantInt>(MD->getOperand(2)); 224280031Sdim ConstantInt *SIDef = 225280031Sdim mdconst::dyn_extract<ConstantInt>(MD->getOperand(1)); 226261991Sdim assert(SICase && SIDef); 227261991Sdim // The TrueWeight should be the weight for the single case of SI. 228261991Sdim NewBr->setMetadata(LLVMContext::MD_prof, 229261991Sdim MDBuilder(BB->getContext()). 230261991Sdim createBranchWeights(SICase->getValue().getZExtValue(), 231261991Sdim SIDef->getValue().getZExtValue())); 232261991Sdim } 233193323Sed 234296417Sdim // Update make.implicit metadata to the newly-created conditional branch. 235296417Sdim MDNode *MakeImplicitMD = SI->getMetadata(LLVMContext::MD_make_implicit); 236296417Sdim if (MakeImplicitMD) 237296417Sdim NewBr->setMetadata(LLVMContext::MD_make_implicit, MakeImplicitMD); 238296417Sdim 239261991Sdim // Delete the old switch. 240261991Sdim SI->eraseFromParent(); 241261991Sdim return true; 242193323Sed } 243198892Srdivacky return false; 244193323Sed } 245198892Srdivacky 246198892Srdivacky if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(T)) { 247198892Srdivacky // indirectbr blockaddress(@F, @BB) -> br label @BB 248198892Srdivacky if (BlockAddress *BA = 249198892Srdivacky dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) { 250198892Srdivacky BasicBlock *TheOnlyDest = BA->getBasicBlock(); 251198892Srdivacky // Insert the new branch. 252223017Sdim Builder.CreateBr(TheOnlyDest); 253261991Sdim 254198892Srdivacky for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) { 255198892Srdivacky if (IBI->getDestination(i) == TheOnlyDest) 256276479Sdim TheOnlyDest = nullptr; 257198892Srdivacky else 258198892Srdivacky IBI->getDestination(i)->removePredecessor(IBI->getParent()); 259198892Srdivacky } 260223017Sdim Value *Address = IBI->getAddress(); 261198892Srdivacky IBI->eraseFromParent(); 262223017Sdim if (DeleteDeadConditions) 263243830Sdim RecursivelyDeleteTriviallyDeadInstructions(Address, TLI); 264261991Sdim 265198892Srdivacky // If we didn't find our destination in the IBI successor list, then we 266198892Srdivacky // have undefined behavior. Replace the unconditional branch with an 267198892Srdivacky // 'unreachable' instruction. 268198892Srdivacky if (TheOnlyDest) { 269198892Srdivacky BB->getTerminator()->eraseFromParent(); 270198892Srdivacky new UnreachableInst(BB->getContext(), BB); 271198892Srdivacky } 272261991Sdim 273198892Srdivacky return true; 274198892Srdivacky } 275198892Srdivacky } 276261991Sdim 277193323Sed return false; 278193323Sed} 279193323Sed 280193323Sed 281193323Sed//===----------------------------------------------------------------------===// 282199481Srdivacky// Local dead code elimination. 283193323Sed// 284193323Sed 285193323Sed/// isInstructionTriviallyDead - Return true if the result produced by the 286193323Sed/// instruction is not used, and the instruction has no side effects. 287193323Sed/// 288243830Sdimbool llvm::isInstructionTriviallyDead(Instruction *I, 289243830Sdim const TargetLibraryInfo *TLI) { 290193323Sed if (!I->use_empty() || isa<TerminatorInst>(I)) return false; 291193323Sed 292296417Sdim // We don't want the landingpad-like instructions removed by anything this 293296417Sdim // general. 294296417Sdim if (I->isEHPad()) 295226633Sdim return false; 296226633Sdim 297221345Sdim // We don't want debug info removed by anything this general, unless 298221345Sdim // debug info is empty. 299221345Sdim if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) { 300226633Sdim if (DDI->getAddress()) 301221345Sdim return false; 302221345Sdim return true; 303226633Sdim } 304221345Sdim if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) { 305221345Sdim if (DVI->getValue()) 306221345Sdim return false; 307221345Sdim return true; 308221345Sdim } 309193323Sed 310193323Sed if (!I->mayHaveSideEffects()) return true; 311193323Sed 312193323Sed // Special case intrinsics that "may have side effects" but can be deleted 313193323Sed // when dead. 314226633Sdim if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 315193323Sed // Safe to delete llvm.stacksave if dead. 316193323Sed if (II->getIntrinsicID() == Intrinsic::stacksave) 317193323Sed return true; 318226633Sdim 319226633Sdim // Lifetime intrinsics are dead when their right-hand is undef. 320226633Sdim if (II->getIntrinsicID() == Intrinsic::lifetime_start || 321226633Sdim II->getIntrinsicID() == Intrinsic::lifetime_end) 322226633Sdim return isa<UndefValue>(II->getArgOperand(1)); 323280031Sdim 324280031Sdim // Assumptions are dead if their condition is trivially true. 325280031Sdim if (II->getIntrinsicID() == Intrinsic::assume) { 326280031Sdim if (ConstantInt *Cond = dyn_cast<ConstantInt>(II->getArgOperand(0))) 327280031Sdim return !Cond->isZero(); 328280031Sdim 329280031Sdim return false; 330280031Sdim } 331226633Sdim } 332234353Sdim 333243830Sdim if (isAllocLikeFn(I, TLI)) return true; 334234353Sdim 335243830Sdim if (CallInst *CI = isFreeCall(I, TLI)) 336234353Sdim if (Constant *C = dyn_cast<Constant>(CI->getArgOperand(0))) 337234353Sdim return C->isNullValue() || isa<UndefValue>(C); 338234353Sdim 339193323Sed return false; 340193323Sed} 341193323Sed 342193323Sed/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a 343193323Sed/// trivially dead instruction, delete it. If that makes any of its operands 344202375Srdivacky/// trivially dead, delete them too, recursively. Return true if any 345202375Srdivacky/// instructions were deleted. 346243830Sdimbool 347243830Sdimllvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V, 348243830Sdim const TargetLibraryInfo *TLI) { 349193323Sed Instruction *I = dyn_cast<Instruction>(V); 350243830Sdim if (!I || !I->use_empty() || !isInstructionTriviallyDead(I, TLI)) 351202375Srdivacky return false; 352261991Sdim 353193323Sed SmallVector<Instruction*, 16> DeadInsts; 354193323Sed DeadInsts.push_back(I); 355261991Sdim 356202375Srdivacky do { 357193323Sed I = DeadInsts.pop_back_val(); 358193323Sed 359193323Sed // Null out all of the instruction's operands to see if any operand becomes 360193323Sed // dead as we go. 361193323Sed for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 362193323Sed Value *OpV = I->getOperand(i); 363276479Sdim I->setOperand(i, nullptr); 364261991Sdim 365193323Sed if (!OpV->use_empty()) continue; 366261991Sdim 367193323Sed // If the operand is an instruction that became dead as we nulled out the 368193323Sed // operand, and if it is 'trivially' dead, delete it in a future loop 369193323Sed // iteration. 370193323Sed if (Instruction *OpI = dyn_cast<Instruction>(OpV)) 371243830Sdim if (isInstructionTriviallyDead(OpI, TLI)) 372193323Sed DeadInsts.push_back(OpI); 373193323Sed } 374261991Sdim 375193323Sed I->eraseFromParent(); 376202375Srdivacky } while (!DeadInsts.empty()); 377202375Srdivacky 378202375Srdivacky return true; 379193323Sed} 380193323Sed 381218893Sdim/// areAllUsesEqual - Check whether the uses of a value are all the same. 382218893Sdim/// This is similar to Instruction::hasOneUse() except this will also return 383219077Sdim/// true when there are no uses or multiple uses that all refer to the same 384219077Sdim/// value. 385218893Sdimstatic bool areAllUsesEqual(Instruction *I) { 386276479Sdim Value::user_iterator UI = I->user_begin(); 387276479Sdim Value::user_iterator UE = I->user_end(); 388218893Sdim if (UI == UE) 389219077Sdim return true; 390218893Sdim 391218893Sdim User *TheUse = *UI; 392218893Sdim for (++UI; UI != UE; ++UI) { 393218893Sdim if (*UI != TheUse) 394218893Sdim return false; 395218893Sdim } 396218893Sdim return true; 397218893Sdim} 398218893Sdim 399193323Sed/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively 400193323Sed/// dead PHI node, due to being a def-use chain of single-use nodes that 401193323Sed/// either forms a cycle or is terminated by a trivially dead instruction, 402193323Sed/// delete it. If that makes any of its operands trivially dead, delete them 403219077Sdim/// too, recursively. Return true if a change was made. 404243830Sdimbool llvm::RecursivelyDeleteDeadPHINode(PHINode *PN, 405243830Sdim const TargetLibraryInfo *TLI) { 406219077Sdim SmallPtrSet<Instruction*, 4> Visited; 407219077Sdim for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects(); 408276479Sdim I = cast<Instruction>(*I->user_begin())) { 409219077Sdim if (I->use_empty()) 410243830Sdim return RecursivelyDeleteTriviallyDeadInstructions(I, TLI); 411193323Sed 412219077Sdim // If we find an instruction more than once, we're on a cycle that 413193323Sed // won't prove fruitful. 414280031Sdim if (!Visited.insert(I).second) { 415219077Sdim // Break the cycle and delete the instruction and its operands. 416219077Sdim I->replaceAllUsesWith(UndefValue::get(I->getType())); 417243830Sdim (void)RecursivelyDeleteTriviallyDeadInstructions(I, TLI); 418219077Sdim return true; 419219077Sdim } 420219077Sdim } 421219077Sdim return false; 422193323Sed} 423193323Sed 424296417Sdimstatic bool 425296417SdimsimplifyAndDCEInstruction(Instruction *I, 426296417Sdim SmallSetVector<Instruction *, 16> &WorkList, 427296417Sdim const DataLayout &DL, 428296417Sdim const TargetLibraryInfo *TLI) { 429296417Sdim if (isInstructionTriviallyDead(I, TLI)) { 430296417Sdim // Null out all of the instruction's operands to see if any operand becomes 431296417Sdim // dead as we go. 432296417Sdim for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 433296417Sdim Value *OpV = I->getOperand(i); 434296417Sdim I->setOperand(i, nullptr); 435296417Sdim 436296417Sdim if (!OpV->use_empty() || I == OpV) 437296417Sdim continue; 438296417Sdim 439296417Sdim // If the operand is an instruction that became dead as we nulled out the 440296417Sdim // operand, and if it is 'trivially' dead, delete it in a future loop 441296417Sdim // iteration. 442296417Sdim if (Instruction *OpI = dyn_cast<Instruction>(OpV)) 443296417Sdim if (isInstructionTriviallyDead(OpI, TLI)) 444296417Sdim WorkList.insert(OpI); 445296417Sdim } 446296417Sdim 447296417Sdim I->eraseFromParent(); 448296417Sdim 449296417Sdim return true; 450296417Sdim } 451296417Sdim 452296417Sdim if (Value *SimpleV = SimplifyInstruction(I, DL)) { 453296417Sdim // Add the users to the worklist. CAREFUL: an instruction can use itself, 454296417Sdim // in the case of a phi node. 455296417Sdim for (User *U : I->users()) 456296417Sdim if (U != I) 457296417Sdim WorkList.insert(cast<Instruction>(U)); 458296417Sdim 459296417Sdim // Replace the instruction with its simplified value. 460296417Sdim I->replaceAllUsesWith(SimpleV); 461296417Sdim I->eraseFromParent(); 462296417Sdim return true; 463296417Sdim } 464296417Sdim return false; 465296417Sdim} 466296417Sdim 467202375Srdivacky/// SimplifyInstructionsInBlock - Scan the specified basic block and try to 468202375Srdivacky/// simplify any instructions in it and recursively delete dead instructions. 469202375Srdivacky/// 470202375Srdivacky/// This returns true if it changed the code, note that it can delete 471202375Srdivacky/// instructions in other blocks as well in this block. 472288943Sdimbool llvm::SimplifyInstructionsInBlock(BasicBlock *BB, 473243830Sdim const TargetLibraryInfo *TLI) { 474202375Srdivacky bool MadeChange = false; 475296417Sdim const DataLayout &DL = BB->getModule()->getDataLayout(); 476234353Sdim 477234353Sdim#ifndef NDEBUG 478234353Sdim // In debug builds, ensure that the terminator of the block is never replaced 479234353Sdim // or deleted by these simplifications. The idea of simplification is that it 480234353Sdim // cannot introduce new instructions, and there is no way to replace the 481234353Sdim // terminator of a block without introducing a new instruction. 482296417Sdim AssertingVH<Instruction> TerminatorVH(&BB->back()); 483234353Sdim#endif 484234353Sdim 485296417Sdim SmallSetVector<Instruction *, 16> WorkList; 486296417Sdim // Iterate over the original function, only adding insts to the worklist 487296417Sdim // if they actually need to be revisited. This avoids having to pre-init 488296417Sdim // the worklist with the entire function's worth of instructions. 489296417Sdim for (BasicBlock::iterator BI = BB->begin(), E = std::prev(BB->end()); BI != E;) { 490234353Sdim assert(!BI->isTerminator()); 491296417Sdim Instruction *I = &*BI; 492296417Sdim ++BI; 493234353Sdim 494296417Sdim // We're visiting this instruction now, so make sure it's not in the 495296417Sdim // worklist from an earlier visit. 496296417Sdim if (!WorkList.count(I)) 497296417Sdim MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI); 498296417Sdim } 499221345Sdim 500296417Sdim while (!WorkList.empty()) { 501296417Sdim Instruction *I = WorkList.pop_back_val(); 502296417Sdim MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI); 503202375Srdivacky } 504202375Srdivacky return MadeChange; 505202375Srdivacky} 506202375Srdivacky 507193323Sed//===----------------------------------------------------------------------===// 508199481Srdivacky// Control Flow Graph Restructuring. 509193323Sed// 510193323Sed 511199481Srdivacky 512199481Srdivacky/// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this 513199481Srdivacky/// method is called when we're about to delete Pred as a predecessor of BB. If 514199481Srdivacky/// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred. 515199481Srdivacky/// 516199481Srdivacky/// Unlike the removePredecessor method, this attempts to simplify uses of PHI 517199481Srdivacky/// nodes that collapse into identity values. For example, if we have: 518199481Srdivacky/// x = phi(1, 0, 0, 0) 519199481Srdivacky/// y = and x, z 520199481Srdivacky/// 521199481Srdivacky/// .. and delete the predecessor corresponding to the '1', this will attempt to 522199481Srdivacky/// recursively fold the and to 0. 523288943Sdimvoid llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred) { 524199481Srdivacky // This only adjusts blocks with PHI nodes. 525199481Srdivacky if (!isa<PHINode>(BB->begin())) 526199481Srdivacky return; 527261991Sdim 528199481Srdivacky // Remove the entries for Pred from the PHI nodes in BB, but do not simplify 529199481Srdivacky // them down. This will leave us with single entry phi nodes and other phis 530199481Srdivacky // that can be removed. 531199481Srdivacky BB->removePredecessor(Pred, true); 532261991Sdim 533199481Srdivacky WeakVH PhiIt = &BB->front(); 534199481Srdivacky while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) { 535199481Srdivacky PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt)); 536234353Sdim Value *OldPhiIt = PhiIt; 537218893Sdim 538288943Sdim if (!recursivelySimplifyInstruction(PN)) 539234353Sdim continue; 540218893Sdim 541199481Srdivacky // If recursive simplification ended up deleting the next PHI node we would 542199481Srdivacky // iterate to, then our iterator is invalid, restart scanning from the top 543199481Srdivacky // of the block. 544210299Sed if (PhiIt != OldPhiIt) PhiIt = &BB->front(); 545199481Srdivacky } 546199481Srdivacky} 547199481Srdivacky 548199481Srdivacky 549193323Sed/// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its 550193323Sed/// predecessor is known to have one successor (DestBB!). Eliminate the edge 551193323Sed/// between them, moving the instructions in the predecessor into DestBB and 552193323Sed/// deleting the predecessor block. 553193323Sed/// 554288943Sdimvoid llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT) { 555193323Sed // If BB has single-entry PHI nodes, fold them. 556193323Sed while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) { 557193323Sed Value *NewVal = PN->getIncomingValue(0); 558193323Sed // Replace self referencing PHI with undef, it must be dead. 559193323Sed if (NewVal == PN) NewVal = UndefValue::get(PN->getType()); 560193323Sed PN->replaceAllUsesWith(NewVal); 561193323Sed PN->eraseFromParent(); 562193323Sed } 563261991Sdim 564193323Sed BasicBlock *PredBB = DestBB->getSinglePredecessor(); 565193323Sed assert(PredBB && "Block doesn't have a single predecessor!"); 566261991Sdim 567203954Srdivacky // Zap anything that took the address of DestBB. Not doing this will give the 568203954Srdivacky // address an invalid value. 569203954Srdivacky if (DestBB->hasAddressTaken()) { 570203954Srdivacky BlockAddress *BA = BlockAddress::get(DestBB); 571203954Srdivacky Constant *Replacement = 572203954Srdivacky ConstantInt::get(llvm::Type::getInt32Ty(BA->getContext()), 1); 573203954Srdivacky BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement, 574203954Srdivacky BA->getType())); 575203954Srdivacky BA->destroyConstant(); 576203954Srdivacky } 577261991Sdim 578193323Sed // Anything that branched to PredBB now branches to DestBB. 579193323Sed PredBB->replaceAllUsesWith(DestBB); 580261991Sdim 581224145Sdim // Splice all the instructions from PredBB to DestBB. 582224145Sdim PredBB->getTerminator()->eraseFromParent(); 583224145Sdim DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList()); 584224145Sdim 585276479Sdim // If the PredBB is the entry block of the function, move DestBB up to 586276479Sdim // become the entry block after we erase PredBB. 587276479Sdim if (PredBB == &DestBB->getParent()->getEntryBlock()) 588276479Sdim DestBB->moveAfter(PredBB); 589276479Sdim 590288943Sdim if (DT) { 591288943Sdim BasicBlock *PredBBIDom = DT->getNode(PredBB)->getIDom()->getBlock(); 592288943Sdim DT->changeImmediateDominator(DestBB, PredBBIDom); 593288943Sdim DT->eraseNode(PredBB); 594198090Srdivacky } 595193323Sed // Nuke BB. 596193323Sed PredBB->eraseFromParent(); 597193323Sed} 598193323Sed 599261991Sdim/// CanMergeValues - Return true if we can choose one of these values to use 600261991Sdim/// in place of the other. Note that we will always choose the non-undef 601261991Sdim/// value to keep. 602261991Sdimstatic bool CanMergeValues(Value *First, Value *Second) { 603261991Sdim return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second); 604261991Sdim} 605261991Sdim 606199481Srdivacky/// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an 607261991Sdim/// almost-empty BB ending in an unconditional branch to Succ, into Succ. 608199481Srdivacky/// 609199481Srdivacky/// Assumption: Succ is the single successor for BB. 610199481Srdivacky/// 611199481Srdivackystatic bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 612199481Srdivacky assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 613199481Srdivacky 614261991Sdim DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into " 615199481Srdivacky << Succ->getName() << "\n"); 616199481Srdivacky // Shortcut, if there is only a single predecessor it must be BB and merging 617199481Srdivacky // is always safe 618199481Srdivacky if (Succ->getSinglePredecessor()) return true; 619199481Srdivacky 620199481Srdivacky // Make a list of the predecessors of BB 621234353Sdim SmallPtrSet<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB)); 622199481Srdivacky 623199481Srdivacky // Look at all the phi nodes in Succ, to see if they present a conflict when 624199481Srdivacky // merging these blocks 625199481Srdivacky for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 626199481Srdivacky PHINode *PN = cast<PHINode>(I); 627199481Srdivacky 628199481Srdivacky // If the incoming value from BB is again a PHINode in 629199481Srdivacky // BB which has the same incoming value for *PI as PN does, we can 630199481Srdivacky // merge the phi nodes and then the blocks can still be merged 631199481Srdivacky PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB)); 632199481Srdivacky if (BBPN && BBPN->getParent() == BB) { 633234353Sdim for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) { 634234353Sdim BasicBlock *IBB = PN->getIncomingBlock(PI); 635234353Sdim if (BBPreds.count(IBB) && 636261991Sdim !CanMergeValues(BBPN->getIncomingValueForBlock(IBB), 637261991Sdim PN->getIncomingValue(PI))) { 638261991Sdim DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in " 639261991Sdim << Succ->getName() << " is conflicting with " 640199481Srdivacky << BBPN->getName() << " with regard to common predecessor " 641234353Sdim << IBB->getName() << "\n"); 642199481Srdivacky return false; 643199481Srdivacky } 644199481Srdivacky } 645199481Srdivacky } else { 646199481Srdivacky Value* Val = PN->getIncomingValueForBlock(BB); 647234353Sdim for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) { 648199481Srdivacky // See if the incoming value for the common predecessor is equal to the 649199481Srdivacky // one for BB, in which case this phi node will not prevent the merging 650199481Srdivacky // of the block. 651234353Sdim BasicBlock *IBB = PN->getIncomingBlock(PI); 652261991Sdim if (BBPreds.count(IBB) && 653261991Sdim !CanMergeValues(Val, PN->getIncomingValue(PI))) { 654261991Sdim DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in " 655199481Srdivacky << Succ->getName() << " is conflicting with regard to common " 656234353Sdim << "predecessor " << IBB->getName() << "\n"); 657199481Srdivacky return false; 658199481Srdivacky } 659199481Srdivacky } 660199481Srdivacky } 661199481Srdivacky } 662199481Srdivacky 663199481Srdivacky return true; 664199481Srdivacky} 665199481Srdivacky 666261991Sdimtypedef SmallVector<BasicBlock *, 16> PredBlockVector; 667261991Sdimtypedef DenseMap<BasicBlock *, Value *> IncomingValueMap; 668261991Sdim 669261991Sdim/// \brief Determines the value to use as the phi node input for a block. 670261991Sdim/// 671261991Sdim/// Select between \p OldVal any value that we know flows from \p BB 672261991Sdim/// to a particular phi on the basis of which one (if either) is not 673261991Sdim/// undef. Update IncomingValues based on the selected value. 674261991Sdim/// 675261991Sdim/// \param OldVal The value we are considering selecting. 676261991Sdim/// \param BB The block that the value flows in from. 677261991Sdim/// \param IncomingValues A map from block-to-value for other phi inputs 678261991Sdim/// that we have examined. 679261991Sdim/// 680261991Sdim/// \returns the selected value. 681261991Sdimstatic Value *selectIncomingValueForBlock(Value *OldVal, BasicBlock *BB, 682261991Sdim IncomingValueMap &IncomingValues) { 683261991Sdim if (!isa<UndefValue>(OldVal)) { 684261991Sdim assert((!IncomingValues.count(BB) || 685261991Sdim IncomingValues.find(BB)->second == OldVal) && 686261991Sdim "Expected OldVal to match incoming value from BB!"); 687261991Sdim 688261991Sdim IncomingValues.insert(std::make_pair(BB, OldVal)); 689261991Sdim return OldVal; 690261991Sdim } 691261991Sdim 692261991Sdim IncomingValueMap::const_iterator It = IncomingValues.find(BB); 693261991Sdim if (It != IncomingValues.end()) return It->second; 694261991Sdim 695261991Sdim return OldVal; 696261991Sdim} 697261991Sdim 698261991Sdim/// \brief Create a map from block to value for the operands of a 699261991Sdim/// given phi. 700261991Sdim/// 701261991Sdim/// Create a map from block to value for each non-undef value flowing 702261991Sdim/// into \p PN. 703261991Sdim/// 704261991Sdim/// \param PN The phi we are collecting the map for. 705261991Sdim/// \param IncomingValues [out] The map from block to value for this phi. 706261991Sdimstatic void gatherIncomingValuesToPhi(PHINode *PN, 707261991Sdim IncomingValueMap &IncomingValues) { 708261991Sdim for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 709261991Sdim BasicBlock *BB = PN->getIncomingBlock(i); 710261991Sdim Value *V = PN->getIncomingValue(i); 711261991Sdim 712261991Sdim if (!isa<UndefValue>(V)) 713261991Sdim IncomingValues.insert(std::make_pair(BB, V)); 714261991Sdim } 715261991Sdim} 716261991Sdim 717261991Sdim/// \brief Replace the incoming undef values to a phi with the values 718261991Sdim/// from a block-to-value map. 719261991Sdim/// 720261991Sdim/// \param PN The phi we are replacing the undefs in. 721261991Sdim/// \param IncomingValues A map from block to value. 722261991Sdimstatic void replaceUndefValuesInPhi(PHINode *PN, 723261991Sdim const IncomingValueMap &IncomingValues) { 724261991Sdim for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 725261991Sdim Value *V = PN->getIncomingValue(i); 726261991Sdim 727261991Sdim if (!isa<UndefValue>(V)) continue; 728261991Sdim 729261991Sdim BasicBlock *BB = PN->getIncomingBlock(i); 730261991Sdim IncomingValueMap::const_iterator It = IncomingValues.find(BB); 731261991Sdim if (It == IncomingValues.end()) continue; 732261991Sdim 733261991Sdim PN->setIncomingValue(i, It->second); 734261991Sdim } 735261991Sdim} 736261991Sdim 737261991Sdim/// \brief Replace a value flowing from a block to a phi with 738261991Sdim/// potentially multiple instances of that value flowing from the 739261991Sdim/// block's predecessors to the phi. 740261991Sdim/// 741261991Sdim/// \param BB The block with the value flowing into the phi. 742261991Sdim/// \param BBPreds The predecessors of BB. 743261991Sdim/// \param PN The phi that we are updating. 744261991Sdimstatic void redirectValuesFromPredecessorsToPhi(BasicBlock *BB, 745261991Sdim const PredBlockVector &BBPreds, 746261991Sdim PHINode *PN) { 747261991Sdim Value *OldVal = PN->removeIncomingValue(BB, false); 748261991Sdim assert(OldVal && "No entry in PHI for Pred BB!"); 749261991Sdim 750261991Sdim IncomingValueMap IncomingValues; 751261991Sdim 752261991Sdim // We are merging two blocks - BB, and the block containing PN - and 753261991Sdim // as a result we need to redirect edges from the predecessors of BB 754261991Sdim // to go to the block containing PN, and update PN 755261991Sdim // accordingly. Since we allow merging blocks in the case where the 756261991Sdim // predecessor and successor blocks both share some predecessors, 757261991Sdim // and where some of those common predecessors might have undef 758261991Sdim // values flowing into PN, we want to rewrite those values to be 759261991Sdim // consistent with the non-undef values. 760261991Sdim 761261991Sdim gatherIncomingValuesToPhi(PN, IncomingValues); 762261991Sdim 763261991Sdim // If this incoming value is one of the PHI nodes in BB, the new entries 764261991Sdim // in the PHI node are the entries from the old PHI. 765261991Sdim if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { 766261991Sdim PHINode *OldValPN = cast<PHINode>(OldVal); 767261991Sdim for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) { 768261991Sdim // Note that, since we are merging phi nodes and BB and Succ might 769261991Sdim // have common predecessors, we could end up with a phi node with 770261991Sdim // identical incoming branches. This will be cleaned up later (and 771261991Sdim // will trigger asserts if we try to clean it up now, without also 772261991Sdim // simplifying the corresponding conditional branch). 773261991Sdim BasicBlock *PredBB = OldValPN->getIncomingBlock(i); 774261991Sdim Value *PredVal = OldValPN->getIncomingValue(i); 775261991Sdim Value *Selected = selectIncomingValueForBlock(PredVal, PredBB, 776261991Sdim IncomingValues); 777261991Sdim 778261991Sdim // And add a new incoming value for this predecessor for the 779261991Sdim // newly retargeted branch. 780261991Sdim PN->addIncoming(Selected, PredBB); 781261991Sdim } 782261991Sdim } else { 783261991Sdim for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) { 784261991Sdim // Update existing incoming values in PN for this 785261991Sdim // predecessor of BB. 786261991Sdim BasicBlock *PredBB = BBPreds[i]; 787261991Sdim Value *Selected = selectIncomingValueForBlock(OldVal, PredBB, 788261991Sdim IncomingValues); 789261991Sdim 790261991Sdim // And add a new incoming value for this predecessor for the 791261991Sdim // newly retargeted branch. 792261991Sdim PN->addIncoming(Selected, PredBB); 793261991Sdim } 794261991Sdim } 795261991Sdim 796261991Sdim replaceUndefValuesInPhi(PN, IncomingValues); 797261991Sdim} 798261991Sdim 799199481Srdivacky/// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an 800199481Srdivacky/// unconditional branch, and contains no instructions other than PHI nodes, 801224145Sdim/// potential side-effect free intrinsics and the branch. If possible, 802224145Sdim/// eliminate BB by rewriting all the predecessors to branch to the successor 803224145Sdim/// block and return true. If we can't transform, return false. 804199481Srdivackybool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) { 805212904Sdim assert(BB != &BB->getParent()->getEntryBlock() && 806212904Sdim "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!"); 807212904Sdim 808199481Srdivacky // We can't eliminate infinite loops. 809199481Srdivacky BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0); 810199481Srdivacky if (BB == Succ) return false; 811261991Sdim 812199481Srdivacky // Check to see if merging these blocks would cause conflicts for any of the 813199481Srdivacky // phi nodes in BB or Succ. If not, we can safely merge. 814199481Srdivacky if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false; 815199481Srdivacky 816199481Srdivacky // Check for cases where Succ has multiple predecessors and a PHI node in BB 817199481Srdivacky // has uses which will not disappear when the PHI nodes are merged. It is 818199481Srdivacky // possible to handle such cases, but difficult: it requires checking whether 819199481Srdivacky // BB dominates Succ, which is non-trivial to calculate in the case where 820199481Srdivacky // Succ has multiple predecessors. Also, it requires checking whether 821249423Sdim // constructing the necessary self-referential PHI node doesn't introduce any 822199481Srdivacky // conflicts; this isn't too difficult, but the previous code for doing this 823199481Srdivacky // was incorrect. 824199481Srdivacky // 825199481Srdivacky // Note that if this check finds a live use, BB dominates Succ, so BB is 826199481Srdivacky // something like a loop pre-header (or rarely, a part of an irreducible CFG); 827199481Srdivacky // folding the branch isn't profitable in that case anyway. 828199481Srdivacky if (!Succ->getSinglePredecessor()) { 829199481Srdivacky BasicBlock::iterator BBI = BB->begin(); 830199481Srdivacky while (isa<PHINode>(*BBI)) { 831276479Sdim for (Use &U : BBI->uses()) { 832276479Sdim if (PHINode* PN = dyn_cast<PHINode>(U.getUser())) { 833276479Sdim if (PN->getIncomingBlock(U) != BB) 834199481Srdivacky return false; 835199481Srdivacky } else { 836199481Srdivacky return false; 837199481Srdivacky } 838199481Srdivacky } 839199481Srdivacky ++BBI; 840199481Srdivacky } 841199481Srdivacky } 842199481Srdivacky 843202375Srdivacky DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB); 844261991Sdim 845199481Srdivacky if (isa<PHINode>(Succ->begin())) { 846199481Srdivacky // If there is more than one pred of succ, and there are PHI nodes in 847199481Srdivacky // the successor, then we need to add incoming edges for the PHI nodes 848199481Srdivacky // 849261991Sdim const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB)); 850261991Sdim 851199481Srdivacky // Loop over all of the PHI nodes in the successor of BB. 852199481Srdivacky for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 853199481Srdivacky PHINode *PN = cast<PHINode>(I); 854261991Sdim 855261991Sdim redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN); 856199481Srdivacky } 857199481Srdivacky } 858261991Sdim 859224145Sdim if (Succ->getSinglePredecessor()) { 860224145Sdim // BB is the only predecessor of Succ, so Succ will end up with exactly 861224145Sdim // the same predecessors BB had. 862224145Sdim 863224145Sdim // Copy over any phi, debug or lifetime instruction. 864224145Sdim BB->getTerminator()->eraseFromParent(); 865296417Sdim Succ->getInstList().splice(Succ->getFirstNonPHI()->getIterator(), 866296417Sdim BB->getInstList()); 867224145Sdim } else { 868224145Sdim while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 869199481Srdivacky // We explicitly check for such uses in CanPropagatePredecessorsForPHIs. 870199481Srdivacky assert(PN->use_empty() && "There shouldn't be any uses here!"); 871199481Srdivacky PN->eraseFromParent(); 872199481Srdivacky } 873199481Srdivacky } 874261991Sdim 875199481Srdivacky // Everything that jumped to BB now goes to Succ. 876199481Srdivacky BB->replaceAllUsesWith(Succ); 877199481Srdivacky if (!Succ->hasName()) Succ->takeName(BB); 878199481Srdivacky BB->eraseFromParent(); // Delete the old basic block. 879199481Srdivacky return true; 880199481Srdivacky} 881199481Srdivacky 882200581Srdivacky/// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI 883200581Srdivacky/// nodes in this block. This doesn't try to be clever about PHI nodes 884200581Srdivacky/// which differ only in the order of the incoming values, but instcombine 885200581Srdivacky/// orders them so it usually won't matter. 886200581Srdivacky/// 887200581Srdivackybool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { 888200581Srdivacky // This implementation doesn't currently consider undef operands 889224145Sdim // specially. Theoretically, two phis which are identical except for 890200581Srdivacky // one having an undef where the other doesn't could be collapsed. 891200581Srdivacky 892288943Sdim struct PHIDenseMapInfo { 893288943Sdim static PHINode *getEmptyKey() { 894288943Sdim return DenseMapInfo<PHINode *>::getEmptyKey(); 895288943Sdim } 896288943Sdim static PHINode *getTombstoneKey() { 897288943Sdim return DenseMapInfo<PHINode *>::getTombstoneKey(); 898288943Sdim } 899288943Sdim static unsigned getHashValue(PHINode *PN) { 900288943Sdim // Compute a hash value on the operands. Instcombine will likely have 901288943Sdim // sorted them, which helps expose duplicates, but we have to check all 902288943Sdim // the operands to be safe in case instcombine hasn't run. 903288943Sdim return static_cast<unsigned>(hash_combine( 904288943Sdim hash_combine_range(PN->value_op_begin(), PN->value_op_end()), 905288943Sdim hash_combine_range(PN->block_begin(), PN->block_end()))); 906288943Sdim } 907288943Sdim static bool isEqual(PHINode *LHS, PHINode *RHS) { 908288943Sdim if (LHS == getEmptyKey() || LHS == getTombstoneKey() || 909288943Sdim RHS == getEmptyKey() || RHS == getTombstoneKey()) 910288943Sdim return LHS == RHS; 911288943Sdim return LHS->isIdenticalTo(RHS); 912288943Sdim } 913288943Sdim }; 914200581Srdivacky 915288943Sdim // Set of unique PHINodes. 916288943Sdim DenseSet<PHINode *, PHIDenseMapInfo> PHISet; 917200581Srdivacky 918200581Srdivacky // Examine each PHI. 919288943Sdim bool Changed = false; 920288943Sdim for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I++);) { 921288943Sdim auto Inserted = PHISet.insert(PN); 922288943Sdim if (!Inserted.second) { 923288943Sdim // A duplicate. Replace this PHI with its duplicate. 924288943Sdim PN->replaceAllUsesWith(*Inserted.first); 925288943Sdim PN->eraseFromParent(); 926288943Sdim Changed = true; 927292735Sdim 928292735Sdim // The RAUW can change PHIs that we already visited. Start over from the 929292735Sdim // beginning. 930292735Sdim PHISet.clear(); 931292735Sdim I = BB->begin(); 932200581Srdivacky } 933200581Srdivacky } 934200581Srdivacky 935200581Srdivacky return Changed; 936200581Srdivacky} 937218893Sdim 938218893Sdim/// enforceKnownAlignment - If the specified pointer points to an object that 939218893Sdim/// we control, modify the object's alignment to PrefAlign. This isn't 940218893Sdim/// often possible though. If alignment is important, a more reliable approach 941218893Sdim/// is to simply align all global variables and allocation instructions to 942218893Sdim/// their preferred alignment from the beginning. 943218893Sdim/// 944218893Sdimstatic unsigned enforceKnownAlignment(Value *V, unsigned Align, 945288943Sdim unsigned PrefAlign, 946288943Sdim const DataLayout &DL) { 947296417Sdim assert(PrefAlign > Align); 948296417Sdim 949224145Sdim V = V->stripPointerCasts(); 950218893Sdim 951224145Sdim if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) { 952296417Sdim // TODO: ideally, computeKnownBits ought to have used 953296417Sdim // AllocaInst::getAlignment() in its computation already, making 954296417Sdim // the below max redundant. But, as it turns out, 955296417Sdim // stripPointerCasts recurses through infinite layers of bitcasts, 956296417Sdim // while computeKnownBits is not allowed to traverse more than 6 957296417Sdim // levels. 958296417Sdim Align = std::max(AI->getAlignment(), Align); 959296417Sdim if (PrefAlign <= Align) 960296417Sdim return Align; 961296417Sdim 962226633Sdim // If the preferred alignment is greater than the natural stack alignment 963226633Sdim // then don't round up. This avoids dynamic stack realignment. 964288943Sdim if (DL.exceedsNaturalStackAlignment(PrefAlign)) 965226633Sdim return Align; 966218893Sdim AI->setAlignment(PrefAlign); 967218893Sdim return PrefAlign; 968218893Sdim } 969218893Sdim 970276479Sdim if (auto *GO = dyn_cast<GlobalObject>(V)) { 971296417Sdim // TODO: as above, this shouldn't be necessary. 972296417Sdim Align = std::max(GO->getAlignment(), Align); 973296417Sdim if (PrefAlign <= Align) 974296417Sdim return Align; 975296417Sdim 976218893Sdim // If there is a large requested alignment and we can, bump up the alignment 977288943Sdim // of the global. If the memory we set aside for the global may not be the 978288943Sdim // memory used by the final program then it is impossible for us to reliably 979288943Sdim // enforce the preferred alignment. 980296417Sdim if (!GO->canIncreaseAlignment()) 981276479Sdim return Align; 982261991Sdim 983296417Sdim GO->setAlignment(PrefAlign); 984296417Sdim return PrefAlign; 985218893Sdim } 986218893Sdim 987218893Sdim return Align; 988218893Sdim} 989218893Sdim 990218893Sdim/// getOrEnforceKnownAlignment - If the specified pointer has an alignment that 991218893Sdim/// we can determine, return it, otherwise return 0. If PrefAlign is specified, 992218893Sdim/// and it is more than the alignment of the ultimate object, see if we can 993218893Sdim/// increase the alignment of the ultimate object, making this check succeed. 994218893Sdimunsigned llvm::getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, 995288943Sdim const DataLayout &DL, 996288943Sdim const Instruction *CxtI, 997280031Sdim AssumptionCache *AC, 998280031Sdim const DominatorTree *DT) { 999218893Sdim assert(V->getType()->isPointerTy() && 1000218893Sdim "getOrEnforceKnownAlignment expects a pointer!"); 1001288943Sdim unsigned BitWidth = DL.getPointerTypeSizeInBits(V->getType()); 1002261991Sdim 1003218893Sdim APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); 1004280031Sdim computeKnownBits(V, KnownZero, KnownOne, DL, 0, AC, CxtI, DT); 1005218893Sdim unsigned TrailZ = KnownZero.countTrailingOnes(); 1006261991Sdim 1007261991Sdim // Avoid trouble with ridiculously large TrailZ values, such as 1008218893Sdim // those computed from a null pointer. 1009218893Sdim TrailZ = std::min(TrailZ, unsigned(sizeof(unsigned) * CHAR_BIT - 1)); 1010261991Sdim 1011218893Sdim unsigned Align = 1u << std::min(BitWidth - 1, TrailZ); 1012261991Sdim 1013218893Sdim // LLVM doesn't support alignments larger than this currently. 1014218893Sdim Align = std::min(Align, +Value::MaximumAlignment); 1015261991Sdim 1016218893Sdim if (PrefAlign > Align) 1017261991Sdim Align = enforceKnownAlignment(V, Align, PrefAlign, DL); 1018261991Sdim 1019218893Sdim // We don't need to make any adjustment. 1020218893Sdim return Align; 1021218893Sdim} 1022218893Sdim 1023221345Sdim///===---------------------------------------------------------------------===// 1024221345Sdim/// Dbg Intrinsic utilities 1025221345Sdim/// 1026221345Sdim 1027251662Sdim/// See if there is a dbg.value intrinsic for DIVar before I. 1028288943Sdimstatic bool LdStHasDebugValue(const DILocalVariable *DIVar, Instruction *I) { 1029251662Sdim // Since we can't guarantee that the original dbg.declare instrinsic 1030251662Sdim // is removed by LowerDbgDeclare(), we need to make sure that we are 1031251662Sdim // not inserting the same dbg.value intrinsic over and over. 1032251662Sdim llvm::BasicBlock::InstListType::iterator PrevI(I); 1033251662Sdim if (PrevI != I->getParent()->getInstList().begin()) { 1034251662Sdim --PrevI; 1035251662Sdim if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(PrevI)) 1036251662Sdim if (DVI->getValue() == I->getOperand(0) && 1037251662Sdim DVI->getOffset() == 0 && 1038251662Sdim DVI->getVariable() == DIVar) 1039251662Sdim return true; 1040251662Sdim } 1041251662Sdim return false; 1042251662Sdim} 1043251662Sdim 1044251662Sdim/// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value 1045221345Sdim/// that has an associated llvm.dbg.decl intrinsic. 1046221345Sdimbool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, 1047221345Sdim StoreInst *SI, DIBuilder &Builder) { 1048288943Sdim auto *DIVar = DDI->getVariable(); 1049288943Sdim auto *DIExpr = DDI->getExpression(); 1050288943Sdim assert(DIVar && "Missing variable"); 1051221345Sdim 1052251662Sdim if (LdStHasDebugValue(DIVar, SI)) 1053251662Sdim return true; 1054251662Sdim 1055223017Sdim // If an argument is zero extended then use argument directly. The ZExt 1056223017Sdim // may be zapped by an optimization pass in future. 1057276479Sdim Argument *ExtendedArg = nullptr; 1058223017Sdim if (ZExtInst *ZExt = dyn_cast<ZExtInst>(SI->getOperand(0))) 1059223017Sdim ExtendedArg = dyn_cast<Argument>(ZExt->getOperand(0)); 1060223017Sdim if (SExtInst *SExt = dyn_cast<SExtInst>(SI->getOperand(0))) 1061223017Sdim ExtendedArg = dyn_cast<Argument>(SExt->getOperand(0)); 1062296417Sdim if (ExtendedArg) { 1063296417Sdim // We're now only describing a subset of the variable. The piece we're 1064296417Sdim // describing will always be smaller than the variable size, because 1065296417Sdim // VariableSize == Size of Alloca described by DDI. Since SI stores 1066296417Sdim // to the alloca described by DDI, if it's first operand is an extend, 1067296417Sdim // we're guaranteed that before extension, the value was narrower than 1068296417Sdim // the size of the alloca, hence the size of the described variable. 1069296417Sdim SmallVector<uint64_t, 3> NewDIExpr; 1070296417Sdim unsigned PieceOffset = 0; 1071296417Sdim // If this already is a bit piece, we drop the bit piece from the expression 1072296417Sdim // and record the offset. 1073296417Sdim if (DIExpr->isBitPiece()) { 1074296417Sdim NewDIExpr.append(DIExpr->elements_begin(), DIExpr->elements_end()-3); 1075296417Sdim PieceOffset = DIExpr->getBitPieceOffset(); 1076296417Sdim } else { 1077296417Sdim NewDIExpr.append(DIExpr->elements_begin(), DIExpr->elements_end()); 1078296417Sdim } 1079296417Sdim NewDIExpr.push_back(dwarf::DW_OP_bit_piece); 1080296417Sdim NewDIExpr.push_back(PieceOffset); //Offset 1081296417Sdim const DataLayout &DL = DDI->getModule()->getDataLayout(); 1082296417Sdim NewDIExpr.push_back(DL.getTypeSizeInBits(ExtendedArg->getType())); // Size 1083296417Sdim Builder.insertDbgValueIntrinsic(ExtendedArg, 0, DIVar, 1084296417Sdim Builder.createExpression(NewDIExpr), 1085288943Sdim DDI->getDebugLoc(), SI); 1086296417Sdim } 1087223017Sdim else 1088288943Sdim Builder.insertDbgValueIntrinsic(SI->getOperand(0), 0, DIVar, DIExpr, 1089288943Sdim DDI->getDebugLoc(), SI); 1090221345Sdim return true; 1091221345Sdim} 1092221345Sdim 1093251662Sdim/// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value 1094221345Sdim/// that has an associated llvm.dbg.decl intrinsic. 1095221345Sdimbool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, 1096221345Sdim LoadInst *LI, DIBuilder &Builder) { 1097288943Sdim auto *DIVar = DDI->getVariable(); 1098288943Sdim auto *DIExpr = DDI->getExpression(); 1099288943Sdim assert(DIVar && "Missing variable"); 1100221345Sdim 1101251662Sdim if (LdStHasDebugValue(DIVar, LI)) 1102251662Sdim return true; 1103251662Sdim 1104296417Sdim // We are now tracking the loaded value instead of the address. In the 1105296417Sdim // future if multi-location support is added to the IR, it might be 1106296417Sdim // preferable to keep tracking both the loaded value and the original 1107296417Sdim // address in case the alloca can not be elided. 1108296417Sdim Instruction *DbgValue = Builder.insertDbgValueIntrinsic( 1109296417Sdim LI, 0, DIVar, DIExpr, DDI->getDebugLoc(), (Instruction *)nullptr); 1110296417Sdim DbgValue->insertAfter(LI); 1111221345Sdim return true; 1112221345Sdim} 1113221345Sdim 1114276479Sdim/// Determine whether this alloca is either a VLA or an array. 1115276479Sdimstatic bool isArray(AllocaInst *AI) { 1116276479Sdim return AI->isArrayAllocation() || 1117276479Sdim AI->getType()->getElementType()->isArrayTy(); 1118276479Sdim} 1119276479Sdim 1120221345Sdim/// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set 1121221345Sdim/// of llvm.dbg.value intrinsics. 1122221345Sdimbool llvm::LowerDbgDeclare(Function &F) { 1123280031Sdim DIBuilder DIB(*F.getParent(), /*AllowUnresolved*/ false); 1124221345Sdim SmallVector<DbgDeclareInst *, 4> Dbgs; 1125276479Sdim for (auto &FI : F) 1126296417Sdim for (Instruction &BI : FI) 1127296417Sdim if (auto DDI = dyn_cast<DbgDeclareInst>(&BI)) 1128221345Sdim Dbgs.push_back(DDI); 1129276479Sdim 1130221345Sdim if (Dbgs.empty()) 1131221345Sdim return false; 1132221345Sdim 1133276479Sdim for (auto &I : Dbgs) { 1134276479Sdim DbgDeclareInst *DDI = I; 1135261991Sdim AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress()); 1136261991Sdim // If this is an alloca for a scalar variable, insert a dbg.value 1137261991Sdim // at each load and store to the alloca and erase the dbg.declare. 1138276479Sdim // The dbg.values allow tracking a variable even if it is not 1139276479Sdim // stored on the stack, while the dbg.declare can only describe 1140276479Sdim // the stack slot (and at a lexical-scope granularity). Later 1141276479Sdim // passes will attempt to elide the stack slot. 1142276479Sdim if (AI && !isArray(AI)) { 1143276479Sdim for (User *U : AI->users()) 1144276479Sdim if (StoreInst *SI = dyn_cast<StoreInst>(U)) 1145221345Sdim ConvertDebugDeclareToDebugValue(DDI, SI, DIB); 1146276479Sdim else if (LoadInst *LI = dyn_cast<LoadInst>(U)) 1147221345Sdim ConvertDebugDeclareToDebugValue(DDI, LI, DIB); 1148276479Sdim else if (CallInst *CI = dyn_cast<CallInst>(U)) { 1149280031Sdim // This is a call by-value or some other instruction that 1150280031Sdim // takes a pointer to the variable. Insert a *value* 1151280031Sdim // intrinsic that describes the alloca. 1152296417Sdim SmallVector<uint64_t, 1> NewDIExpr; 1153296417Sdim auto *DIExpr = DDI->getExpression(); 1154296417Sdim NewDIExpr.push_back(dwarf::DW_OP_deref); 1155296417Sdim NewDIExpr.append(DIExpr->elements_begin(), DIExpr->elements_end()); 1156288943Sdim DIB.insertDbgValueIntrinsic(AI, 0, DDI->getVariable(), 1157296417Sdim DIB.createExpression(NewDIExpr), 1158296417Sdim DDI->getDebugLoc(), CI); 1159280031Sdim } 1160276479Sdim DDI->eraseFromParent(); 1161221345Sdim } 1162221345Sdim } 1163221345Sdim return true; 1164221345Sdim} 1165223017Sdim 1166223017Sdim/// FindAllocaDbgDeclare - Finds the llvm.dbg.declare intrinsic describing the 1167223017Sdim/// alloca 'V', if any. 1168223017SdimDbgDeclareInst *llvm::FindAllocaDbgDeclare(Value *V) { 1169280031Sdim if (auto *L = LocalAsMetadata::getIfExists(V)) 1170280031Sdim if (auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L)) 1171280031Sdim for (User *U : MDV->users()) 1172280031Sdim if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(U)) 1173280031Sdim return DDI; 1174223017Sdim 1175276479Sdim return nullptr; 1176223017Sdim} 1177249423Sdim 1178296417Sdimbool llvm::replaceDbgDeclare(Value *Address, Value *NewAddress, 1179296417Sdim Instruction *InsertBefore, DIBuilder &Builder, 1180296417Sdim bool Deref, int Offset) { 1181296417Sdim DbgDeclareInst *DDI = FindAllocaDbgDeclare(Address); 1182249423Sdim if (!DDI) 1183249423Sdim return false; 1184288943Sdim DebugLoc Loc = DDI->getDebugLoc(); 1185288943Sdim auto *DIVar = DDI->getVariable(); 1186288943Sdim auto *DIExpr = DDI->getExpression(); 1187288943Sdim assert(DIVar && "Missing variable"); 1188249423Sdim 1189296417Sdim if (Deref || Offset) { 1190288943Sdim // Create a copy of the original DIDescriptor for user variable, prepending 1191288943Sdim // "deref" operation to a list of address elements, as new llvm.dbg.declare 1192288943Sdim // will take a value storing address of the memory for variable, not 1193288943Sdim // alloca itself. 1194288943Sdim SmallVector<uint64_t, 4> NewDIExpr; 1195296417Sdim if (Deref) 1196296417Sdim NewDIExpr.push_back(dwarf::DW_OP_deref); 1197296417Sdim if (Offset > 0) { 1198296417Sdim NewDIExpr.push_back(dwarf::DW_OP_plus); 1199296417Sdim NewDIExpr.push_back(Offset); 1200296417Sdim } else if (Offset < 0) { 1201296417Sdim NewDIExpr.push_back(dwarf::DW_OP_minus); 1202296417Sdim NewDIExpr.push_back(-Offset); 1203296417Sdim } 1204288943Sdim if (DIExpr) 1205288943Sdim NewDIExpr.append(DIExpr->elements_begin(), DIExpr->elements_end()); 1206288943Sdim DIExpr = Builder.createExpression(NewDIExpr); 1207288943Sdim } 1208249423Sdim 1209296417Sdim // Insert llvm.dbg.declare immediately after the original alloca, and remove 1210296417Sdim // old llvm.dbg.declare. 1211296417Sdim Builder.insertDeclare(NewAddress, DIVar, DIExpr, Loc, InsertBefore); 1212249423Sdim DDI->eraseFromParent(); 1213249423Sdim return true; 1214249423Sdim} 1215249423Sdim 1216296417Sdimbool llvm::replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, 1217296417Sdim DIBuilder &Builder, bool Deref, int Offset) { 1218296417Sdim return replaceDbgDeclare(AI, NewAllocaAddress, AI->getNextNode(), Builder, 1219296417Sdim Deref, Offset); 1220296417Sdim} 1221296417Sdim 1222296417Sdimvoid llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap) { 1223261991Sdim BasicBlock *BB = I->getParent(); 1224261991Sdim // Loop over all of the successors, removing BB's entry from any PHI 1225261991Sdim // nodes. 1226261991Sdim for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 1227261991Sdim (*SI)->removePredecessor(BB); 1228261991Sdim 1229261991Sdim // Insert a call to llvm.trap right before this. This turns the undefined 1230261991Sdim // behavior into a hard fail instead of falling through into random code. 1231261991Sdim if (UseLLVMTrap) { 1232261991Sdim Function *TrapFn = 1233261991Sdim Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap); 1234261991Sdim CallInst *CallTrap = CallInst::Create(TrapFn, "", I); 1235261991Sdim CallTrap->setDebugLoc(I->getDebugLoc()); 1236261991Sdim } 1237261991Sdim new UnreachableInst(I->getContext(), I); 1238261991Sdim 1239261991Sdim // All instructions after this are dead. 1240296417Sdim BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end(); 1241261991Sdim while (BBI != BBE) { 1242261991Sdim if (!BBI->use_empty()) 1243261991Sdim BBI->replaceAllUsesWith(UndefValue::get(BBI->getType())); 1244261991Sdim BB->getInstList().erase(BBI++); 1245261991Sdim } 1246261991Sdim} 1247261991Sdim 1248261991Sdim/// changeToCall - Convert the specified invoke into a normal call. 1249261991Sdimstatic void changeToCall(InvokeInst *II) { 1250296417Sdim SmallVector<Value*, 8> Args(II->arg_begin(), II->arg_end()); 1251296417Sdim SmallVector<OperandBundleDef, 1> OpBundles; 1252296417Sdim II->getOperandBundlesAsDefs(OpBundles); 1253296417Sdim CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, OpBundles, 1254296417Sdim "", II); 1255261991Sdim NewCall->takeName(II); 1256261991Sdim NewCall->setCallingConv(II->getCallingConv()); 1257261991Sdim NewCall->setAttributes(II->getAttributes()); 1258261991Sdim NewCall->setDebugLoc(II->getDebugLoc()); 1259261991Sdim II->replaceAllUsesWith(NewCall); 1260261991Sdim 1261261991Sdim // Follow the call by a branch to the normal destination. 1262261991Sdim BranchInst::Create(II->getNormalDest(), II); 1263261991Sdim 1264261991Sdim // Update PHI nodes in the unwind destination 1265261991Sdim II->getUnwindDest()->removePredecessor(II->getParent()); 1266261991Sdim II->eraseFromParent(); 1267261991Sdim} 1268261991Sdim 1269288943Sdimstatic bool markAliveBlocks(Function &F, 1270280031Sdim SmallPtrSetImpl<BasicBlock*> &Reachable) { 1271261991Sdim 1272249423Sdim SmallVector<BasicBlock*, 128> Worklist; 1273296417Sdim BasicBlock *BB = &F.front(); 1274261991Sdim Worklist.push_back(BB); 1275261991Sdim Reachable.insert(BB); 1276261991Sdim bool Changed = false; 1277249423Sdim do { 1278261991Sdim BB = Worklist.pop_back_val(); 1279261991Sdim 1280261991Sdim // Do a quick scan of the basic block, turning any obviously unreachable 1281261991Sdim // instructions into LLVM unreachable insts. The instruction combining pass 1282261991Sdim // canonicalizes unreachable insts into stores to null or undef. 1283261991Sdim for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;++BBI){ 1284280031Sdim // Assumptions that are known to be false are equivalent to unreachable. 1285280031Sdim // Also, if the condition is undefined, then we make the choice most 1286280031Sdim // beneficial to the optimizer, and choose that to also be unreachable. 1287280031Sdim if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(BBI)) 1288280031Sdim if (II->getIntrinsicID() == Intrinsic::assume) { 1289280031Sdim bool MakeUnreachable = false; 1290280031Sdim if (isa<UndefValue>(II->getArgOperand(0))) 1291280031Sdim MakeUnreachable = true; 1292280031Sdim else if (ConstantInt *Cond = 1293280031Sdim dyn_cast<ConstantInt>(II->getArgOperand(0))) 1294280031Sdim MakeUnreachable = Cond->isZero(); 1295280031Sdim 1296280031Sdim if (MakeUnreachable) { 1297280031Sdim // Don't insert a call to llvm.trap right before the unreachable. 1298296417Sdim changeToUnreachable(&*BBI, false); 1299280031Sdim Changed = true; 1300280031Sdim break; 1301280031Sdim } 1302280031Sdim } 1303280031Sdim 1304261991Sdim if (CallInst *CI = dyn_cast<CallInst>(BBI)) { 1305261991Sdim if (CI->doesNotReturn()) { 1306261991Sdim // If we found a call to a no-return function, insert an unreachable 1307261991Sdim // instruction after it. Make sure there isn't *already* one there 1308261991Sdim // though. 1309261991Sdim ++BBI; 1310261991Sdim if (!isa<UnreachableInst>(BBI)) { 1311261991Sdim // Don't insert a call to llvm.trap right before the unreachable. 1312296417Sdim changeToUnreachable(&*BBI, false); 1313261991Sdim Changed = true; 1314261991Sdim } 1315261991Sdim break; 1316261991Sdim } 1317261991Sdim } 1318261991Sdim 1319261991Sdim // Store to undef and store to null are undefined and used to signal that 1320261991Sdim // they should be changed to unreachable by passes that can't modify the 1321261991Sdim // CFG. 1322261991Sdim if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) { 1323261991Sdim // Don't touch volatile stores. 1324261991Sdim if (SI->isVolatile()) continue; 1325261991Sdim 1326261991Sdim Value *Ptr = SI->getOperand(1); 1327261991Sdim 1328261991Sdim if (isa<UndefValue>(Ptr) || 1329261991Sdim (isa<ConstantPointerNull>(Ptr) && 1330261991Sdim SI->getPointerAddressSpace() == 0)) { 1331261991Sdim changeToUnreachable(SI, true); 1332261991Sdim Changed = true; 1333261991Sdim break; 1334261991Sdim } 1335261991Sdim } 1336261991Sdim } 1337261991Sdim 1338296417Sdim TerminatorInst *Terminator = BB->getTerminator(); 1339296417Sdim if (auto *II = dyn_cast<InvokeInst>(Terminator)) { 1340296417Sdim // Turn invokes that call 'nounwind' functions into ordinary calls. 1341261991Sdim Value *Callee = II->getCalledValue(); 1342261991Sdim if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) { 1343261991Sdim changeToUnreachable(II, true); 1344261991Sdim Changed = true; 1345288943Sdim } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) { 1346261991Sdim if (II->use_empty() && II->onlyReadsMemory()) { 1347261991Sdim // jump to the normal destination branch. 1348261991Sdim BranchInst::Create(II->getNormalDest(), II); 1349261991Sdim II->getUnwindDest()->removePredecessor(II->getParent()); 1350261991Sdim II->eraseFromParent(); 1351261991Sdim } else 1352261991Sdim changeToCall(II); 1353261991Sdim Changed = true; 1354261991Sdim } 1355296417Sdim } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) { 1356296417Sdim // Remove catchpads which cannot be reached. 1357296417Sdim struct CatchPadDenseMapInfo { 1358296417Sdim static CatchPadInst *getEmptyKey() { 1359296417Sdim return DenseMapInfo<CatchPadInst *>::getEmptyKey(); 1360296417Sdim } 1361296417Sdim static CatchPadInst *getTombstoneKey() { 1362296417Sdim return DenseMapInfo<CatchPadInst *>::getTombstoneKey(); 1363296417Sdim } 1364296417Sdim static unsigned getHashValue(CatchPadInst *CatchPad) { 1365296417Sdim return static_cast<unsigned>(hash_combine_range( 1366296417Sdim CatchPad->value_op_begin(), CatchPad->value_op_end())); 1367296417Sdim } 1368296417Sdim static bool isEqual(CatchPadInst *LHS, CatchPadInst *RHS) { 1369296417Sdim if (LHS == getEmptyKey() || LHS == getTombstoneKey() || 1370296417Sdim RHS == getEmptyKey() || RHS == getTombstoneKey()) 1371296417Sdim return LHS == RHS; 1372296417Sdim return LHS->isIdenticalTo(RHS); 1373296417Sdim } 1374296417Sdim }; 1375296417Sdim 1376296417Sdim // Set of unique CatchPads. 1377296417Sdim SmallDenseMap<CatchPadInst *, detail::DenseSetEmpty, 4, 1378296417Sdim CatchPadDenseMapInfo, detail::DenseSetPair<CatchPadInst *>> 1379296417Sdim HandlerSet; 1380296417Sdim detail::DenseSetEmpty Empty; 1381296417Sdim for (CatchSwitchInst::handler_iterator I = CatchSwitch->handler_begin(), 1382296417Sdim E = CatchSwitch->handler_end(); 1383296417Sdim I != E; ++I) { 1384296417Sdim BasicBlock *HandlerBB = *I; 1385296417Sdim auto *CatchPad = cast<CatchPadInst>(HandlerBB->getFirstNonPHI()); 1386296417Sdim if (!HandlerSet.insert({CatchPad, Empty}).second) { 1387296417Sdim CatchSwitch->removeHandler(I); 1388296417Sdim --I; 1389296417Sdim --E; 1390296417Sdim Changed = true; 1391296417Sdim } 1392296417Sdim } 1393261991Sdim } 1394261991Sdim 1395261991Sdim Changed |= ConstantFoldTerminator(BB, true); 1396249423Sdim for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) 1397280031Sdim if (Reachable.insert(*SI).second) 1398249423Sdim Worklist.push_back(*SI); 1399249423Sdim } while (!Worklist.empty()); 1400261991Sdim return Changed; 1401261991Sdim} 1402249423Sdim 1403296417Sdimvoid llvm::removeUnwindEdge(BasicBlock *BB) { 1404296417Sdim TerminatorInst *TI = BB->getTerminator(); 1405296417Sdim 1406296417Sdim if (auto *II = dyn_cast<InvokeInst>(TI)) { 1407296417Sdim changeToCall(II); 1408296417Sdim return; 1409296417Sdim } 1410296417Sdim 1411296417Sdim TerminatorInst *NewTI; 1412296417Sdim BasicBlock *UnwindDest; 1413296417Sdim 1414296417Sdim if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) { 1415296417Sdim NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI); 1416296417Sdim UnwindDest = CRI->getUnwindDest(); 1417296417Sdim } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) { 1418296417Sdim auto *NewCatchSwitch = CatchSwitchInst::Create( 1419296417Sdim CatchSwitch->getParentPad(), nullptr, CatchSwitch->getNumHandlers(), 1420296417Sdim CatchSwitch->getName(), CatchSwitch); 1421296417Sdim for (BasicBlock *PadBB : CatchSwitch->handlers()) 1422296417Sdim NewCatchSwitch->addHandler(PadBB); 1423296417Sdim 1424296417Sdim NewTI = NewCatchSwitch; 1425296417Sdim UnwindDest = CatchSwitch->getUnwindDest(); 1426296417Sdim } else { 1427296417Sdim llvm_unreachable("Could not find unwind successor"); 1428296417Sdim } 1429296417Sdim 1430296417Sdim NewTI->takeName(TI); 1431296417Sdim NewTI->setDebugLoc(TI->getDebugLoc()); 1432296417Sdim UnwindDest->removePredecessor(BB); 1433296417Sdim TI->replaceAllUsesWith(NewTI); 1434296417Sdim TI->eraseFromParent(); 1435296417Sdim} 1436296417Sdim 1437261991Sdim/// removeUnreachableBlocksFromFn - Remove blocks that are not reachable, even 1438261991Sdim/// if they are in a dead cycle. Return true if a change was made, false 1439261991Sdim/// otherwise. 1440296417Sdimbool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI) { 1441261991Sdim SmallPtrSet<BasicBlock*, 128> Reachable; 1442288943Sdim bool Changed = markAliveBlocks(F, Reachable); 1443261991Sdim 1444261991Sdim // If there are unreachable blocks in the CFG... 1445249423Sdim if (Reachable.size() == F.size()) 1446261991Sdim return Changed; 1447249423Sdim 1448249423Sdim assert(Reachable.size() < F.size()); 1449261991Sdim NumRemoved += F.size()-Reachable.size(); 1450261991Sdim 1451261991Sdim // Loop over all of the basic blocks that are not reachable, dropping all of 1452261991Sdim // their internal references... 1453261991Sdim for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) { 1454296417Sdim if (Reachable.count(&*BB)) 1455249423Sdim continue; 1456249423Sdim 1457296417Sdim for (succ_iterator SI = succ_begin(&*BB), SE = succ_end(&*BB); SI != SE; 1458296417Sdim ++SI) 1459249423Sdim if (Reachable.count(*SI)) 1460296417Sdim (*SI)->removePredecessor(&*BB); 1461296417Sdim if (LVI) 1462296417Sdim LVI->eraseBlock(&*BB); 1463261991Sdim BB->dropAllReferences(); 1464249423Sdim } 1465249423Sdim 1466261991Sdim for (Function::iterator I = ++F.begin(); I != F.end();) 1467296417Sdim if (!Reachable.count(&*I)) 1468249423Sdim I = F.getBasicBlockList().erase(I); 1469249423Sdim else 1470249423Sdim ++I; 1471249423Sdim 1472249423Sdim return true; 1473249423Sdim} 1474280031Sdim 1475296417Sdimvoid llvm::combineMetadata(Instruction *K, const Instruction *J, 1476296417Sdim ArrayRef<unsigned> KnownIDs) { 1477280031Sdim SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata; 1478296417Sdim K->dropUnknownNonDebugMetadata(KnownIDs); 1479280031Sdim K->getAllMetadataOtherThanDebugLoc(Metadata); 1480280031Sdim for (unsigned i = 0, n = Metadata.size(); i < n; ++i) { 1481280031Sdim unsigned Kind = Metadata[i].first; 1482280031Sdim MDNode *JMD = J->getMetadata(Kind); 1483280031Sdim MDNode *KMD = Metadata[i].second; 1484280031Sdim 1485280031Sdim switch (Kind) { 1486280031Sdim default: 1487280031Sdim K->setMetadata(Kind, nullptr); // Remove unknown metadata 1488280031Sdim break; 1489280031Sdim case LLVMContext::MD_dbg: 1490280031Sdim llvm_unreachable("getAllMetadataOtherThanDebugLoc returned a MD_dbg"); 1491280031Sdim case LLVMContext::MD_tbaa: 1492280031Sdim K->setMetadata(Kind, MDNode::getMostGenericTBAA(JMD, KMD)); 1493280031Sdim break; 1494280031Sdim case LLVMContext::MD_alias_scope: 1495280031Sdim K->setMetadata(Kind, MDNode::getMostGenericAliasScope(JMD, KMD)); 1496280031Sdim break; 1497280031Sdim case LLVMContext::MD_noalias: 1498280031Sdim K->setMetadata(Kind, MDNode::intersect(JMD, KMD)); 1499280031Sdim break; 1500280031Sdim case LLVMContext::MD_range: 1501280031Sdim K->setMetadata(Kind, MDNode::getMostGenericRange(JMD, KMD)); 1502280031Sdim break; 1503280031Sdim case LLVMContext::MD_fpmath: 1504280031Sdim K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD)); 1505280031Sdim break; 1506280031Sdim case LLVMContext::MD_invariant_load: 1507280031Sdim // Only set the !invariant.load if it is present in both instructions. 1508280031Sdim K->setMetadata(Kind, JMD); 1509280031Sdim break; 1510280031Sdim case LLVMContext::MD_nonnull: 1511280031Sdim // Only set the !nonnull if it is present in both instructions. 1512280031Sdim K->setMetadata(Kind, JMD); 1513280031Sdim break; 1514296417Sdim case LLVMContext::MD_invariant_group: 1515296417Sdim // Preserve !invariant.group in K. 1516296417Sdim break; 1517296417Sdim case LLVMContext::MD_align: 1518296417Sdim K->setMetadata(Kind, 1519296417Sdim MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD)); 1520296417Sdim break; 1521296417Sdim case LLVMContext::MD_dereferenceable: 1522296417Sdim case LLVMContext::MD_dereferenceable_or_null: 1523296417Sdim K->setMetadata(Kind, 1524296417Sdim MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD)); 1525296417Sdim break; 1526280031Sdim } 1527280031Sdim } 1528296417Sdim // Set !invariant.group from J if J has it. If both instructions have it 1529296417Sdim // then we will just pick it from J - even when they are different. 1530296417Sdim // Also make sure that K is load or store - f.e. combining bitcast with load 1531296417Sdim // could produce bitcast with invariant.group metadata, which is invalid. 1532296417Sdim // FIXME: we should try to preserve both invariant.group md if they are 1533296417Sdim // different, but right now instruction can only have one invariant.group. 1534296417Sdim if (auto *JMD = J->getMetadata(LLVMContext::MD_invariant_group)) 1535296417Sdim if (isa<LoadInst>(K) || isa<StoreInst>(K)) 1536296417Sdim K->setMetadata(LLVMContext::MD_invariant_group, JMD); 1537280031Sdim} 1538288943Sdim 1539288943Sdimunsigned llvm::replaceDominatedUsesWith(Value *From, Value *To, 1540288943Sdim DominatorTree &DT, 1541288943Sdim const BasicBlockEdge &Root) { 1542288943Sdim assert(From->getType() == To->getType()); 1543288943Sdim 1544288943Sdim unsigned Count = 0; 1545288943Sdim for (Value::use_iterator UI = From->use_begin(), UE = From->use_end(); 1546288943Sdim UI != UE; ) { 1547288943Sdim Use &U = *UI++; 1548288943Sdim if (DT.dominates(Root, U)) { 1549288943Sdim U.set(To); 1550288943Sdim DEBUG(dbgs() << "Replace dominated use of '" 1551288943Sdim << From->getName() << "' as " 1552288943Sdim << *To << " in " << *U << "\n"); 1553288943Sdim ++Count; 1554288943Sdim } 1555288943Sdim } 1556288943Sdim return Count; 1557288943Sdim} 1558296417Sdim 1559296417Sdimunsigned llvm::replaceDominatedUsesWith(Value *From, Value *To, 1560296417Sdim DominatorTree &DT, 1561296417Sdim const BasicBlock *BB) { 1562296417Sdim assert(From->getType() == To->getType()); 1563296417Sdim 1564296417Sdim unsigned Count = 0; 1565296417Sdim for (Value::use_iterator UI = From->use_begin(), UE = From->use_end(); 1566296417Sdim UI != UE;) { 1567296417Sdim Use &U = *UI++; 1568296417Sdim auto *I = cast<Instruction>(U.getUser()); 1569296417Sdim if (DT.dominates(BB, I->getParent())) { 1570296417Sdim U.set(To); 1571296417Sdim DEBUG(dbgs() << "Replace dominated use of '" << From->getName() << "' as " 1572296417Sdim << *To << " in " << *U << "\n"); 1573296417Sdim ++Count; 1574296417Sdim } 1575296417Sdim } 1576296417Sdim return Count; 1577296417Sdim} 1578296417Sdim 1579296417Sdimbool llvm::callsGCLeafFunction(ImmutableCallSite CS) { 1580296417Sdim if (isa<IntrinsicInst>(CS.getInstruction())) 1581296417Sdim // Most LLVM intrinsics are things which can never take a safepoint. 1582296417Sdim // As a result, we don't need to have the stack parsable at the 1583296417Sdim // callsite. This is a highly useful optimization since intrinsic 1584296417Sdim // calls are fairly prevalent, particularly in debug builds. 1585296417Sdim return true; 1586296417Sdim 1587296417Sdim // Check if the function is specifically marked as a gc leaf function. 1588296417Sdim if (CS.hasFnAttr("gc-leaf-function")) 1589296417Sdim return true; 1590296417Sdim if (const Function *F = CS.getCalledFunction()) 1591296417Sdim return F->hasFnAttribute("gc-leaf-function"); 1592296417Sdim 1593296417Sdim return false; 1594296417Sdim} 1595296417Sdim 1596296417Sdim/// A potential constituent of a bitreverse or bswap expression. See 1597296417Sdim/// collectBitParts for a fuller explanation. 1598296417Sdimstruct BitPart { 1599296417Sdim BitPart(Value *P, unsigned BW) : Provider(P) { 1600296417Sdim Provenance.resize(BW); 1601296417Sdim } 1602296417Sdim 1603296417Sdim /// The Value that this is a bitreverse/bswap of. 1604296417Sdim Value *Provider; 1605296417Sdim /// The "provenance" of each bit. Provenance[A] = B means that bit A 1606296417Sdim /// in Provider becomes bit B in the result of this expression. 1607296417Sdim SmallVector<int8_t, 32> Provenance; // int8_t means max size is i128. 1608296417Sdim 1609296417Sdim enum { Unset = -1 }; 1610296417Sdim}; 1611296417Sdim 1612296417Sdim/// Analyze the specified subexpression and see if it is capable of providing 1613296417Sdim/// pieces of a bswap or bitreverse. The subexpression provides a potential 1614296417Sdim/// piece of a bswap or bitreverse if it can be proven that each non-zero bit in 1615296417Sdim/// the output of the expression came from a corresponding bit in some other 1616296417Sdim/// value. This function is recursive, and the end result is a mapping of 1617296417Sdim/// bitnumber to bitnumber. It is the caller's responsibility to validate that 1618296417Sdim/// the bitnumber to bitnumber mapping is correct for a bswap or bitreverse. 1619296417Sdim/// 1620296417Sdim/// For example, if the current subexpression if "(shl i32 %X, 24)" then we know 1621296417Sdim/// that the expression deposits the low byte of %X into the high byte of the 1622296417Sdim/// result and that all other bits are zero. This expression is accepted and a 1623296417Sdim/// BitPart is returned with Provider set to %X and Provenance[24-31] set to 1624296417Sdim/// [0-7]. 1625296417Sdim/// 1626296417Sdim/// To avoid revisiting values, the BitPart results are memoized into the 1627296417Sdim/// provided map. To avoid unnecessary copying of BitParts, BitParts are 1628296417Sdim/// constructed in-place in the \c BPS map. Because of this \c BPS needs to 1629296417Sdim/// store BitParts objects, not pointers. As we need the concept of a nullptr 1630296417Sdim/// BitParts (Value has been analyzed and the analysis failed), we an Optional 1631296417Sdim/// type instead to provide the same functionality. 1632296417Sdim/// 1633296417Sdim/// Because we pass around references into \c BPS, we must use a container that 1634296417Sdim/// does not invalidate internal references (std::map instead of DenseMap). 1635296417Sdim/// 1636296417Sdimstatic const Optional<BitPart> & 1637296417SdimcollectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals, 1638296417Sdim std::map<Value *, Optional<BitPart>> &BPS) { 1639296417Sdim auto I = BPS.find(V); 1640296417Sdim if (I != BPS.end()) 1641296417Sdim return I->second; 1642296417Sdim 1643296417Sdim auto &Result = BPS[V] = None; 1644296417Sdim auto BitWidth = cast<IntegerType>(V->getType())->getBitWidth(); 1645296417Sdim 1646296417Sdim if (Instruction *I = dyn_cast<Instruction>(V)) { 1647296417Sdim // If this is an or instruction, it may be an inner node of the bswap. 1648296417Sdim if (I->getOpcode() == Instruction::Or) { 1649296417Sdim auto &A = collectBitParts(I->getOperand(0), MatchBSwaps, 1650296417Sdim MatchBitReversals, BPS); 1651296417Sdim auto &B = collectBitParts(I->getOperand(1), MatchBSwaps, 1652296417Sdim MatchBitReversals, BPS); 1653296417Sdim if (!A || !B) 1654296417Sdim return Result; 1655296417Sdim 1656296417Sdim // Try and merge the two together. 1657296417Sdim if (!A->Provider || A->Provider != B->Provider) 1658296417Sdim return Result; 1659296417Sdim 1660296417Sdim Result = BitPart(A->Provider, BitWidth); 1661296417Sdim for (unsigned i = 0; i < A->Provenance.size(); ++i) { 1662296417Sdim if (A->Provenance[i] != BitPart::Unset && 1663296417Sdim B->Provenance[i] != BitPart::Unset && 1664296417Sdim A->Provenance[i] != B->Provenance[i]) 1665296417Sdim return Result = None; 1666296417Sdim 1667296417Sdim if (A->Provenance[i] == BitPart::Unset) 1668296417Sdim Result->Provenance[i] = B->Provenance[i]; 1669296417Sdim else 1670296417Sdim Result->Provenance[i] = A->Provenance[i]; 1671296417Sdim } 1672296417Sdim 1673296417Sdim return Result; 1674296417Sdim } 1675296417Sdim 1676296417Sdim // If this is a logical shift by a constant, recurse then shift the result. 1677296417Sdim if (I->isLogicalShift() && isa<ConstantInt>(I->getOperand(1))) { 1678296417Sdim unsigned BitShift = 1679296417Sdim cast<ConstantInt>(I->getOperand(1))->getLimitedValue(~0U); 1680296417Sdim // Ensure the shift amount is defined. 1681296417Sdim if (BitShift > BitWidth) 1682296417Sdim return Result; 1683296417Sdim 1684296417Sdim auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps, 1685296417Sdim MatchBitReversals, BPS); 1686296417Sdim if (!Res) 1687296417Sdim return Result; 1688296417Sdim Result = Res; 1689296417Sdim 1690296417Sdim // Perform the "shift" on BitProvenance. 1691296417Sdim auto &P = Result->Provenance; 1692296417Sdim if (I->getOpcode() == Instruction::Shl) { 1693296417Sdim P.erase(std::prev(P.end(), BitShift), P.end()); 1694296417Sdim P.insert(P.begin(), BitShift, BitPart::Unset); 1695296417Sdim } else { 1696296417Sdim P.erase(P.begin(), std::next(P.begin(), BitShift)); 1697296417Sdim P.insert(P.end(), BitShift, BitPart::Unset); 1698296417Sdim } 1699296417Sdim 1700296417Sdim return Result; 1701296417Sdim } 1702296417Sdim 1703296417Sdim // If this is a logical 'and' with a mask that clears bits, recurse then 1704296417Sdim // unset the appropriate bits. 1705296417Sdim if (I->getOpcode() == Instruction::And && 1706296417Sdim isa<ConstantInt>(I->getOperand(1))) { 1707296417Sdim APInt Bit(I->getType()->getPrimitiveSizeInBits(), 1); 1708296417Sdim const APInt &AndMask = cast<ConstantInt>(I->getOperand(1))->getValue(); 1709296417Sdim 1710296417Sdim // Check that the mask allows a multiple of 8 bits for a bswap, for an 1711296417Sdim // early exit. 1712296417Sdim unsigned NumMaskedBits = AndMask.countPopulation(); 1713296417Sdim if (!MatchBitReversals && NumMaskedBits % 8 != 0) 1714296417Sdim return Result; 1715296417Sdim 1716296417Sdim auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps, 1717296417Sdim MatchBitReversals, BPS); 1718296417Sdim if (!Res) 1719296417Sdim return Result; 1720296417Sdim Result = Res; 1721296417Sdim 1722296417Sdim for (unsigned i = 0; i < BitWidth; ++i, Bit <<= 1) 1723296417Sdim // If the AndMask is zero for this bit, clear the bit. 1724296417Sdim if ((AndMask & Bit) == 0) 1725296417Sdim Result->Provenance[i] = BitPart::Unset; 1726296417Sdim 1727296417Sdim return Result; 1728296417Sdim } 1729296417Sdim } 1730296417Sdim 1731296417Sdim // Okay, we got to something that isn't a shift, 'or' or 'and'. This must be 1732296417Sdim // the input value to the bswap/bitreverse. 1733296417Sdim Result = BitPart(V, BitWidth); 1734296417Sdim for (unsigned i = 0; i < BitWidth; ++i) 1735296417Sdim Result->Provenance[i] = i; 1736296417Sdim return Result; 1737296417Sdim} 1738296417Sdim 1739296417Sdimstatic bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To, 1740296417Sdim unsigned BitWidth) { 1741296417Sdim if (From % 8 != To % 8) 1742296417Sdim return false; 1743296417Sdim // Convert from bit indices to byte indices and check for a byte reversal. 1744296417Sdim From >>= 3; 1745296417Sdim To >>= 3; 1746296417Sdim BitWidth >>= 3; 1747296417Sdim return From == BitWidth - To - 1; 1748296417Sdim} 1749296417Sdim 1750296417Sdimstatic bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To, 1751296417Sdim unsigned BitWidth) { 1752296417Sdim return From == BitWidth - To - 1; 1753296417Sdim} 1754296417Sdim 1755296417Sdim/// Given an OR instruction, check to see if this is a bitreverse 1756296417Sdim/// idiom. If so, insert the new intrinsic and return true. 1757296417Sdimbool llvm::recognizeBitReverseOrBSwapIdiom( 1758296417Sdim Instruction *I, bool MatchBSwaps, bool MatchBitReversals, 1759296417Sdim SmallVectorImpl<Instruction *> &InsertedInsts) { 1760296417Sdim if (Operator::getOpcode(I) != Instruction::Or) 1761296417Sdim return false; 1762296417Sdim if (!MatchBSwaps && !MatchBitReversals) 1763296417Sdim return false; 1764296417Sdim IntegerType *ITy = dyn_cast<IntegerType>(I->getType()); 1765296417Sdim if (!ITy || ITy->getBitWidth() > 128) 1766296417Sdim return false; // Can't do vectors or integers > 128 bits. 1767296417Sdim unsigned BW = ITy->getBitWidth(); 1768296417Sdim 1769296417Sdim // Try to find all the pieces corresponding to the bswap. 1770296417Sdim std::map<Value *, Optional<BitPart>> BPS; 1771296417Sdim auto Res = collectBitParts(I, MatchBSwaps, MatchBitReversals, BPS); 1772296417Sdim if (!Res) 1773296417Sdim return false; 1774296417Sdim auto &BitProvenance = Res->Provenance; 1775296417Sdim 1776296417Sdim // Now, is the bit permutation correct for a bswap or a bitreverse? We can 1777296417Sdim // only byteswap values with an even number of bytes. 1778296417Sdim bool OKForBSwap = BW % 16 == 0, OKForBitReverse = true; 1779296417Sdim for (unsigned i = 0; i < BW; ++i) { 1780296417Sdim OKForBSwap &= bitTransformIsCorrectForBSwap(BitProvenance[i], i, BW); 1781296417Sdim OKForBitReverse &= 1782296417Sdim bitTransformIsCorrectForBitReverse(BitProvenance[i], i, BW); 1783296417Sdim } 1784296417Sdim 1785296417Sdim Intrinsic::ID Intrin; 1786296417Sdim if (OKForBSwap && MatchBSwaps) 1787296417Sdim Intrin = Intrinsic::bswap; 1788296417Sdim else if (OKForBitReverse && MatchBitReversals) 1789296417Sdim Intrin = Intrinsic::bitreverse; 1790296417Sdim else 1791296417Sdim return false; 1792296417Sdim 1793296417Sdim Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, ITy); 1794296417Sdim InsertedInsts.push_back(CallInst::Create(F, Res->Provider, "rev", I)); 1795296417Sdim return true; 1796296417Sdim} 1797