1139823Simp//===- Local.cpp - Functions to perform local transformations -------------===// 2122922Sandre// 3122922Sandre// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4122922Sandre// See https://llvm.org/LICENSE.txt for license information. 5122922Sandre// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6122922Sandre// 7122922Sandre//===----------------------------------------------------------------------===// 8122922Sandre// 9122922Sandre// This family of functions perform various local transformations to the 10122922Sandre// program. 11122922Sandre// 12122922Sandre//===----------------------------------------------------------------------===// 13122922Sandre 14122922Sandre#include "llvm/Transforms/Utils/Local.h" 15122922Sandre#include "llvm/ADT/APInt.h" 16122922Sandre#include "llvm/ADT/DenseMap.h" 17122922Sandre#include "llvm/ADT/DenseMapInfo.h" 18122922Sandre#include "llvm/ADT/DenseSet.h" 19122922Sandre#include "llvm/ADT/Hashing.h" 20122922Sandre#include "llvm/ADT/None.h" 21122922Sandre#include "llvm/ADT/Optional.h" 22122922Sandre#include "llvm/ADT/STLExtras.h" 23122922Sandre#include "llvm/ADT/SetVector.h" 24122922Sandre#include "llvm/ADT/SmallPtrSet.h" 25122922Sandre#include "llvm/ADT/SmallVector.h" 26122922Sandre#include "llvm/ADT/Statistic.h" 27122922Sandre#include "llvm/Analysis/AssumeBundleQueries.h" 28122922Sandre#include "llvm/Analysis/ConstantFolding.h" 29122922Sandre#include "llvm/Analysis/DomTreeUpdater.h" 30122922Sandre#include "llvm/Analysis/EHPersonalities.h" 31170030Srwatson#include "llvm/Analysis/InstructionSimplify.h" 32170030Srwatson#include "llvm/Analysis/LazyValueInfo.h" 33170030Srwatson#include "llvm/Analysis/MemoryBuiltins.h" 34170030Srwatson#include "llvm/Analysis/MemorySSAUpdater.h" 35170030Srwatson#include "llvm/Analysis/TargetLibraryInfo.h" 36170030Srwatson#include "llvm/Analysis/ValueTracking.h" 37170030Srwatson#include "llvm/Analysis/VectorUtils.h" 38122922Sandre#include "llvm/BinaryFormat/Dwarf.h" 39170030Srwatson#include "llvm/IR/Argument.h" 40182411Srpaulo#include "llvm/IR/Attributes.h" 41170030Srwatson#include "llvm/IR/BasicBlock.h" 42170030Srwatson#include "llvm/IR/CFG.h" 43170030Srwatson#include "llvm/IR/Constant.h" 44122922Sandre#include "llvm/IR/ConstantRange.h" 45170030Srwatson#include "llvm/IR/Constants.h" 46170030Srwatson#include "llvm/IR/DIBuilder.h" 47170030Srwatson#include "llvm/IR/DataLayout.h" 48170030Srwatson#include "llvm/IR/DebugInfoMetadata.h" 49170030Srwatson#include "llvm/IR/DebugLoc.h" 50170030Srwatson#include "llvm/IR/DerivedTypes.h" 51170030Srwatson#include "llvm/IR/Dominators.h" 52170030Srwatson#include "llvm/IR/Function.h" 53170030Srwatson#include "llvm/IR/GetElementPtrTypeIterator.h" 54170030Srwatson#include "llvm/IR/GlobalObject.h" 55170030Srwatson#include "llvm/IR/IRBuilder.h" 56170030Srwatson#include "llvm/IR/InstrTypes.h" 57170030Srwatson#include "llvm/IR/Instruction.h" 58122922Sandre#include "llvm/IR/Instructions.h" 59122922Sandre#include "llvm/IR/IntrinsicInst.h" 60122922Sandre#include "llvm/IR/Intrinsics.h" 61122922Sandre#include "llvm/IR/LLVMContext.h" 62122922Sandre#include "llvm/IR/MDBuilder.h" 63122922Sandre#include "llvm/IR/Metadata.h" 64122922Sandre#include "llvm/IR/Module.h" 65172467Ssilby#include "llvm/IR/Operator.h" 66172467Ssilby#include "llvm/IR/PatternMatch.h" 67172467Ssilby#include "llvm/IR/PseudoProbe.h" 68122922Sandre#include "llvm/IR/Type.h" 69122922Sandre#include "llvm/IR/Use.h" 70122922Sandre#include "llvm/IR/User.h" 71122922Sandre#include "llvm/IR/Value.h" 72122922Sandre#include "llvm/IR/ValueHandle.h" 73122922Sandre#include "llvm/Support/Casting.h" 74122922Sandre#include "llvm/Support/Debug.h" 75122922Sandre#include "llvm/Support/ErrorHandling.h" 76122922Sandre#include "llvm/Support/KnownBits.h" 77122922Sandre#include "llvm/Support/raw_ostream.h" 78122922Sandre#include "llvm/Transforms/Utils/BasicBlockUtils.h" 79181803Sbz#include "llvm/Transforms/Utils/ValueMapper.h" 80122922Sandre#include <algorithm> 81122922Sandre#include <cassert> 82194739Sbz#include <climits> 83122922Sandre#include <cstdint> 84122922Sandre#include <iterator> 85122922Sandre#include <map> 86122922Sandre#include <utility> 87122922Sandre 88122922Sandreusing namespace llvm; 89122922Sandreusing namespace llvm::PatternMatch; 90122922Sandre 91122922Sandre#define DEBUG_TYPE "local" 92122922Sandre 93122922SandreSTATISTIC(NumRemoved, "Number of unreachable basic blocks removed"); 94122922SandreSTATISTIC(NumPHICSEs, "Number of PHI's that got CSE'd"); 95122922Sandre 96185571Sbzstatic cl::opt<bool> PHICSEDebugHash( 97122922Sandre "phicse-debug-hash", 98122922Sandre#ifdef EXPENSIVE_CHECKS 99122922Sandre cl::init(true), 100122922Sandre#else 101122922Sandre cl::init(false), 102122922Sandre#endif 103122922Sandre cl::Hidden, 104122922Sandre cl::desc("Perform extra assertion checking to verify that PHINodes's hash " 105122922Sandre "function is well-behaved w.r.t. its isEqual predicate")); 106122922Sandre 107122922Sandrestatic cl::opt<unsigned> PHICSENumPHISmallSize( 108122922Sandre "phicse-num-phi-smallsize", cl::init(32), cl::Hidden, 109195699Srwatson cl::desc( 110195699Srwatson "When the basic block contains not more than this number of PHI nodes, " 111122922Sandre "perform a (faster!) exhaustive search instead of set-driven one.")); 112195699Srwatson 113195699Srwatson// Max recursion depth for collectBitParts used when detecting bswap and 114195699Srwatson// bitreverse idioms. 115122922Sandrestatic const unsigned BitPartRecursionMaxDepth = 48; 116122922Sandre 117122922Sandre//===----------------------------------------------------------------------===// 118122922Sandre// Local constant propagation. 119122922Sandre// 120182633Sbrooks 121182633Sbrooks/// ConstantFoldTerminator - If a terminator instruction is predicated on a 122122922Sandre/// constant value, convert it into an unconditional branch to the constant 123195699Srwatson/// destination. This is a nontrivial operation because the successors of this 124195699Srwatson/// basic block must have their PHI nodes updated. 125183550Szec/// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch 126122922Sandre/// conditions and indirectbr addresses this might make dead if 127195699Srwatson/// DeleteDeadConditions is true. 128195699Srwatsonbool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, 129183550Szec const TargetLibraryInfo *TLI, 130122922Sandre DomTreeUpdater *DTU) { 131195699Srwatson Instruction *T = BB->getTerminator(); 132195699Srwatson IRBuilder<> Builder(T); 133183550Szec 134122922Sandre // Branch - See if we are conditional jumping on constant 135195699Srwatson if (auto *BI = dyn_cast<BranchInst>(T)) { 136195699Srwatson if (BI->isUnconditional()) return false; // Can't optimize uncond branch 137183550Szec 138122922Sandre BasicBlock *Dest1 = BI->getSuccessor(0); 139195699Srwatson BasicBlock *Dest2 = BI->getSuccessor(1); 140195699Srwatson 141183550Szec if (Dest2 == Dest1) { // Conditional branch to same location? 142122922Sandre // This branch matches something like this: 143195699Srwatson // br bool %cond, label %Dest, label %Dest 144195699Srwatson // and changes it into: br label %Dest 145195699Srwatson 146170434Syar // Let the basic block know that we are letting go of one copy of it. 147195699Srwatson assert(BI->getParent() && "Terminator not inserted in block!"); 148195699Srwatson Dest1->removePredecessor(BI->getParent()); 149183550Szec 150122922Sandre // Replace the conditional branch with an unconditional one. 151122922Sandre BranchInst *NewBI = Builder.CreateBr(Dest1); 152167784Sandre 153167784Sandre // Transfer the metadata to the new branch instruction. 154122922Sandre NewBI->copyMetadata(*BI, {LLVMContext::MD_loop, LLVMContext::MD_dbg, 155122922Sandre LLVMContext::MD_annotation}); 156122922Sandre 157122922Sandre Value *Cond = BI->getCondition(); 158122922Sandre BI->eraseFromParent(); 159133874Srwatson if (DeleteDeadConditions) 160181803Sbz RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI); 161122922Sandre return true; 162122922Sandre } 163133874Srwatson 164122922Sandre if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition())) { 165122922Sandre // Are we branching on constant? 166122922Sandre // YES. Change to unconditional branch... 167122922Sandre BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2; 168181803Sbz BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1; 169122922Sandre 170122922Sandre // Let the basic block know that we are letting go of it. Based on this, 171122922Sandre // it will adjust it's PHI nodes. 172122922Sandre OldDest->removePredecessor(BB); 173122922Sandre 174122922Sandre // Replace the conditional branch with an unconditional one. 175122922Sandre BranchInst *NewBI = Builder.CreateBr(Destination); 176122922Sandre 177122922Sandre // Transfer the metadata to the new branch instruction. 178122922Sandre NewBI->copyMetadata(*BI, {LLVMContext::MD_loop, LLVMContext::MD_dbg, 179170030Srwatson LLVMContext::MD_annotation}); 180122922Sandre 181181803Sbz BI->eraseFromParent(); 182181803Sbz if (DTU) 183181803Sbz DTU->applyUpdates({{DominatorTree::Delete, BB, OldDest}}); 184181803Sbz return true; 185181803Sbz } 186181803Sbz 187181803Sbz return false; 188122922Sandre } 189133874Srwatson 190181803Sbz if (auto *SI = dyn_cast<SwitchInst>(T)) { 191133874Srwatson // If we are switching on a constant, we can convert the switch to an 192181803Sbz // unconditional branch. 193133874Srwatson auto *CI = dyn_cast<ConstantInt>(SI->getCondition()); 194181803Sbz BasicBlock *DefaultDest = SI->getDefaultDest(); 195181803Sbz BasicBlock *TheOnlyDest = DefaultDest; 196133874Srwatson 197181803Sbz // If the default is unreachable, ignore it when searching for TheOnlyDest. 198133874Srwatson if (isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg()) && 199181803Sbz SI->getNumCases() > 0) { 200122922Sandre TheOnlyDest = SI->case_begin()->getCaseSuccessor(); 201122922Sandre } 202170030Srwatson 203122922Sandre bool Changed = false; 204181803Sbz 205181803Sbz // Figure out which case it goes to. 206122922Sandre for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) { 207122922Sandre // Found case matching a constant operand? 208122922Sandre if (i->getCaseValue() == CI) { 209170030Srwatson TheOnlyDest = i->getCaseSuccessor(); 210122922Sandre break; 211181803Sbz } 212181803Sbz 213181803Sbz // Check to see if this branch is going to the same place as the default 214181803Sbz // dest. If so, eliminate it as an explicit compare. 215122922Sandre if (i->getCaseSuccessor() == DefaultDest) { 216122922Sandre MDNode *MD = SI->getMetadata(LLVMContext::MD_prof); 217122922Sandre unsigned NCases = SI->getNumCases(); 218122922Sandre // Fold the case metadata into the default if there will be any branches 219122922Sandre // left, unless the metadata doesn't match the switch. 220122922Sandre if (NCases > 1 && MD && MD->getNumOperands() == 2 + NCases) { 221181887Sjulian // Collect branch weights into a vector. 222181888Sjulian SmallVector<uint32_t, 8> Weights; 223181888Sjulian for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e; 224181803Sbz ++MD_i) { 225122922Sandre auto *CI = mdconst::extract<ConstantInt>(MD->getOperand(MD_i)); 226122922Sandre Weights.push_back(CI->getValue().getZExtValue()); 227122922Sandre } 228122922Sandre // Merge weight of this case to the default weight. 229181803Sbz unsigned idx = i->getCaseIndex(); 230181887Sjulian Weights[0] += Weights[idx+1]; 231191816Szec // Remove weight for this case. 232122922Sandre std::swap(Weights[idx+1], Weights.back()); 233122922Sandre Weights.pop_back(); 234193731Szec SI->setMetadata(LLVMContext::MD_prof, 235193731Szec MDBuilder(BB->getContext()). 236193731Szec createBranchWeights(Weights)); 237193731Szec } 238193731Szec // Remove this entry. 239193731Szec BasicBlock *ParentBB = SI->getParent(); 240193731Szec DefaultDest->removePredecessor(ParentBB); 241193731Szec i = SI->removeCase(i); 242193731Szec e = SI->case_end(); 243193731Szec Changed = true; 244193731Szec continue; 245122922Sandre } 246170030Srwatson 247122922Sandre // Otherwise, check to see if the switch only branches to one destination. 248122922Sandre // We do this by reseting "TheOnlyDest" to null when we find two non-equal 249122922Sandre // destinations. 250122922Sandre if (i->getCaseSuccessor() != TheOnlyDest) 251122922Sandre TheOnlyDest = nullptr; 252122922Sandre 253122922Sandre // Increment this iterator as we haven't removed the case. 254122922Sandre ++i; 255122922Sandre } 256122922Sandre 257122922Sandre if (CI && !TheOnlyDest) { 258122922Sandre // Branching on a constant, but not any of the cases, go to the default 259122922Sandre // successor. 260122922Sandre TheOnlyDest = SI->getDefaultDest(); 261122922Sandre } 262122922Sandre 263186222Sbz // If we found a single destination that we can fold the switch into, do so 264122922Sandre // now. 265122922Sandre if (TheOnlyDest) { 266122922Sandre // Insert the new branch. 267122922Sandre Builder.CreateBr(TheOnlyDest); 268181803Sbz BasicBlock *BB = SI->getParent(); 269122922Sandre 270122922Sandre SmallSet<BasicBlock *, 8> RemovedSuccessors; 271170030Srwatson 272170030Srwatson // Remove entries from PHI nodes which we no longer branch to... 273170030Srwatson BasicBlock *SuccToKeep = TheOnlyDest; 274122922Sandre for (BasicBlock *Succ : successors(SI)) { 275122922Sandre if (DTU && Succ != TheOnlyDest) 276122922Sandre RemovedSuccessors.insert(Succ); 277122922Sandre // Found case matching a constant operand? 278170030Srwatson if (Succ == SuccToKeep) { 279122922Sandre SuccToKeep = nullptr; // Don't modify the first branch to TheOnlyDest 280122922Sandre } else { 281186222Sbz Succ->removePredecessor(BB); 282122922Sandre } 283122922Sandre } 284122922Sandre 285122922Sandre // Delete the old switch. 286122922Sandre Value *Cond = SI->getCondition(); 287122922Sandre SI->eraseFromParent(); 288122922Sandre if (DeleteDeadConditions) 289122922Sandre RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI); 290122922Sandre if (DTU) { 291122922Sandre std::vector<DominatorTree::UpdateType> Updates; 292122922Sandre Updates.reserve(RemovedSuccessors.size()); 293170030Srwatson for (auto *RemovedSuccessor : RemovedSuccessors) 294122922Sandre Updates.push_back({DominatorTree::Delete, BB, RemovedSuccessor}); 295122922Sandre DTU->applyUpdates(Updates); 296122922Sandre } 297122922Sandre return true; 298122922Sandre } 299122922Sandre 300170030Srwatson if (SI->getNumCases() == 1) { 301170030Srwatson // Otherwise, we can fold this switch into a conditional branch 302133874Srwatson // instruction if it has only one non-default destination. 303122922Sandre auto FirstCase = *SI->case_begin(); 304122922Sandre Value *Cond = Builder.CreateICmpEQ(SI->getCondition(), 305122922Sandre FirstCase.getCaseValue(), "cond"); 306122922Sandre 307122922Sandre // Insert the new branch. 308122922Sandre BranchInst *NewBr = Builder.CreateCondBr(Cond, 309122922Sandre FirstCase.getCaseSuccessor(), 310122922Sandre SI->getDefaultDest()); 311122922Sandre MDNode *MD = SI->getMetadata(LLVMContext::MD_prof); 312122922Sandre if (MD && MD->getNumOperands() == 3) { 313122922Sandre ConstantInt *SICase = 314122922Sandre mdconst::dyn_extract<ConstantInt>(MD->getOperand(2)); 315122922Sandre ConstantInt *SIDef = 316170030Srwatson mdconst::dyn_extract<ConstantInt>(MD->getOperand(1)); 317122922Sandre assert(SICase && SIDef); 318186222Sbz // The TrueWeight should be the weight for the single case of SI. 319122922Sandre NewBr->setMetadata(LLVMContext::MD_prof, 320122922Sandre MDBuilder(BB->getContext()). 321122922Sandre createBranchWeights(SICase->getValue().getZExtValue(), 322122922Sandre SIDef->getValue().getZExtValue())); 323181803Sbz } 324122922Sandre 325122922Sandre // Update make.implicit metadata to the newly-created conditional branch. 326170030Srwatson MDNode *MakeImplicitMD = SI->getMetadata(LLVMContext::MD_make_implicit); 327170030Srwatson if (MakeImplicitMD) 328170030Srwatson NewBr->setMetadata(LLVMContext::MD_make_implicit, MakeImplicitMD); 329122922Sandre 330122922Sandre // Delete the old switch. 331122922Sandre SI->eraseFromParent(); 332122922Sandre return true; 333170030Srwatson } 334122922Sandre return Changed; 335181803Sbz } 336181803Sbz 337122922Sandre if (auto *IBI = dyn_cast<IndirectBrInst>(T)) { 338122922Sandre // indirectbr blockaddress(@F, @BB) -> br label @BB 339122922Sandre if (auto *BA = 340170030Srwatson dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) { 341170030Srwatson BasicBlock *TheOnlyDest = BA->getBasicBlock(); 342170030Srwatson SmallSet<BasicBlock *, 8> RemovedSuccessors; 343170030Srwatson 344170405Sandre // Insert the new branch. 345170405Sandre Builder.CreateBr(TheOnlyDest); 346122922Sandre 347170405Sandre BasicBlock *SuccToKeep = TheOnlyDest; 348170405Sandre for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) { 349170405Sandre BasicBlock *DestBB = IBI->getDestination(i); 350170405Sandre if (DTU && DestBB != TheOnlyDest) 351122922Sandre RemovedSuccessors.insert(DestBB); 352181803Sbz if (IBI->getDestination(i) == SuccToKeep) { 353181803Sbz SuccToKeep = nullptr; 354190948Srwatson } else { 355123028Sandre DestBB->removePredecessor(BB); 356181803Sbz } 357122922Sandre } 358122922Sandre Value *Address = IBI->getAddress(); 359122922Sandre IBI->eraseFromParent(); 360170030Srwatson if (DeleteDeadConditions) 361122922Sandre // Delete pointer cast instructions. 362181803Sbz RecursivelyDeleteTriviallyDeadInstructions(Address, TLI); 363122922Sandre 364122922Sandre // Also zap the blockaddress constant if there are no users remaining, 365122922Sandre // otherwise the destination is still marked as having its address taken. 366122922Sandre if (BA->use_empty()) 367122922Sandre BA->destroyConstant(); 368122922Sandre 369122922Sandre // If we didn't find our destination in the IBI successor list, then we 370170030Srwatson // have undefined behavior. Replace the unconditional branch with an 371122922Sandre // 'unreachable' instruction. 372122922Sandre if (SuccToKeep) { 373186222Sbz BB->getTerminator()->eraseFromParent(); 374123113Sandre new UnreachableInst(BB->getContext(), BB); 375122922Sandre } 376122922Sandre 377122922Sandre if (DTU) { 378181803Sbz std::vector<DominatorTree::UpdateType> Updates; 379122922Sandre Updates.reserve(RemovedSuccessors.size()); 380122922Sandre for (auto *RemovedSuccessor : RemovedSuccessors) 381170030Srwatson Updates.push_back({DominatorTree::Delete, BB, RemovedSuccessor}); 382122922Sandre DTU->applyUpdates(Updates); 383122922Sandre } 384181803Sbz return true; 385181803Sbz } 386190948Srwatson } 387122922Sandre 388122922Sandre return false; 389122922Sandre} 390122922Sandre 391122922Sandre//===----------------------------------------------------------------------===// 392170030Srwatson// Local dead code elimination. 393170030Srwatson// 394170030Srwatson 395122922Sandre/// isInstructionTriviallyDead - Return true if the result produced by the 396122922Sandre/// instruction is not used, and the instruction has no side effects. 397122922Sandre/// 398122922Sandrebool llvm::isInstructionTriviallyDead(Instruction *I, 399122922Sandre const TargetLibraryInfo *TLI) { 400122922Sandre if (!I->use_empty()) 401122922Sandre return false; 402170030Srwatson return wouldInstructionBeTriviallyDead(I, TLI); 403122922Sandre} 404122922Sandre 405122922Sandrebool llvm::wouldInstructionBeTriviallyDead(Instruction *I, 406122922Sandre const TargetLibraryInfo *TLI) { 407170030Srwatson if (I->isTerminator()) 408122922Sandre return false; 409122922Sandre 410122922Sandre // We don't want the landingpad-like instructions removed by anything this 411122922Sandre // general. 412122922Sandre if (I->isEHPad()) 413122922Sandre return false; 414181803Sbz 415122922Sandre // We don't want debug info removed by anything this general, unless 416122922Sandre // debug info is empty. 417122922Sandre if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) { 418122922Sandre if (DDI->getAddress()) 419122922Sandre return false; 420122922Sandre return true; 421122922Sandre } 422122922Sandre if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) { 423122922Sandre if (DVI->hasArgList() || DVI->getValue(0)) 424122922Sandre return false; 425122922Sandre return true; 426170030Srwatson } 427122922Sandre if (DbgLabelInst *DLI = dyn_cast<DbgLabelInst>(I)) { 428122922Sandre if (DLI->getLabel()) 429122922Sandre return false; 430122922Sandre return true; 431122922Sandre } 432170030Srwatson 433170030Srwatson if (!I->willReturn()) 434138409Srwatson return false; 435122922Sandre 436122922Sandre if (!I->mayHaveSideEffects()) 437122922Sandre return true; 438122922Sandre 439122922Sandre // Special case intrinsics that "may have side effects" but can be deleted 440122922Sandre // when dead. 441122922Sandre if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 442122922Sandre // Safe to delete llvm.stacksave and launder.invariant.group if dead. 443122922Sandre if (II->getIntrinsicID() == Intrinsic::stacksave || 444122922Sandre II->getIntrinsicID() == Intrinsic::launder_invariant_group) 445122922Sandre return true; 446122922Sandre 447181803Sbz if (II->isLifetimeStartOrEnd()) { 448122922Sandre auto *Arg = II->getArgOperand(1); 449122922Sandre // Lifetime intrinsics are dead when their right-hand is undef. 450122922Sandre if (isa<UndefValue>(Arg)) 451122922Sandre return true; 452122922Sandre // If the right-hand is an alloc, global, or argument and the only uses 453122922Sandre // are lifetime intrinsics then the intrinsics are dead. 454122922Sandre if (isa<AllocaInst>(Arg) || isa<GlobalValue>(Arg) || isa<Argument>(Arg)) 455170030Srwatson return llvm::all_of(Arg->uses(), [](Use &Use) { 456122922Sandre if (IntrinsicInst *IntrinsicUse = 457122922Sandre dyn_cast<IntrinsicInst>(Use.getUser())) 458122922Sandre return IntrinsicUse->isLifetimeStartOrEnd(); 459122922Sandre return false; 460122922Sandre }); 461122922Sandre return false; 462122922Sandre } 463122922Sandre 464170030Srwatson // Assumptions are dead if their condition is trivially true. Guards on 465122922Sandre // true are operationally no-ops. In the future we can consider more 466122922Sandre // sophisticated tradeoffs for guards considering potential for check 467122922Sandre // widening, but for now we keep things simple. 468122922Sandre if ((II->getIntrinsicID() == Intrinsic::assume && 469170030Srwatson isAssumeWithEmptyBundle(cast<AssumeInst>(*II))) || 470122922Sandre II->getIntrinsicID() == Intrinsic::experimental_guard) { 471122922Sandre if (ConstantInt *Cond = dyn_cast<ConstantInt>(II->getArgOperand(0))) 472122922Sandre return !Cond->isZero(); 473122922Sandre 474122922Sandre return false; 475122922Sandre } 476122922Sandre } 477181803Sbz 478122922Sandre if (isAllocLikeFn(I, TLI)) 479122922Sandre return true; 480122922Sandre 481122922Sandre if (CallInst *CI = isFreeCall(I, TLI)) 482170030Srwatson if (Constant *C = dyn_cast<Constant>(CI->getArgOperand(0))) 483122922Sandre return C->isNullValue() || isa<UndefValue>(C); 484122922Sandre 485122922Sandre if (auto *Call = dyn_cast<CallBase>(I)) 486122922Sandre if (isMathLibCallNoop(Call, TLI)) 487122922Sandre return true; 488170030Srwatson 489122922Sandre return false; 490122922Sandre} 491122922Sandre 492122922Sandre/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a 493122922Sandre/// trivially dead instruction, delete it. If that makes any of its operands 494170030Srwatson/// trivially dead, delete them too, recursively. Return true if any 495122922Sandre/// instructions were deleted. 496122922Sandrebool llvm::RecursivelyDeleteTriviallyDeadInstructions( 497122922Sandre Value *V, const TargetLibraryInfo *TLI, MemorySSAUpdater *MSSAU, 498122922Sandre std::function<void(Value *)> AboutToDeleteCallback) { 499122922Sandre Instruction *I = dyn_cast<Instruction>(V); 500122922Sandre if (!I || !isInstructionTriviallyDead(I, TLI)) 501122922Sandre return false; 502122922Sandre 503122922Sandre SmallVector<WeakTrackingVH, 16> DeadInsts; 504122922Sandre DeadInsts.push_back(I); 505122922Sandre RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI, MSSAU, 506122922Sandre AboutToDeleteCallback); 507122922Sandre 508122922Sandre return true; 509181803Sbz} 510122922Sandre 511122922Sandrebool llvm::RecursivelyDeleteTriviallyDeadInstructionsPermissive( 512122922Sandre SmallVectorImpl<WeakTrackingVH> &DeadInsts, const TargetLibraryInfo *TLI, 513122922Sandre MemorySSAUpdater *MSSAU, 514122922Sandre std::function<void(Value *)> AboutToDeleteCallback) { 515122922Sandre unsigned S = 0, E = DeadInsts.size(), Alive = 0; 516122922Sandre for (; S != E; ++S) { 517190948Srwatson auto *I = cast<Instruction>(DeadInsts[S]); 518122922Sandre if (!isInstructionTriviallyDead(I)) { 519122922Sandre DeadInsts[S] = nullptr; 520122922Sandre ++Alive; 521133874Srwatson } 522122922Sandre } 523122922Sandre if (Alive == E) 524122922Sandre return false; 525190948Srwatson RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI, MSSAU, 526122922Sandre AboutToDeleteCallback); 527122922Sandre return true; 528122922Sandre} 529122922Sandre 530122922Sandrevoid llvm::RecursivelyDeleteTriviallyDeadInstructions( 531122922Sandre SmallVectorImpl<WeakTrackingVH> &DeadInsts, const TargetLibraryInfo *TLI, 532122922Sandre MemorySSAUpdater *MSSAU, 533190948Srwatson std::function<void(Value *)> AboutToDeleteCallback) { 534122922Sandre // Process the dead instruction list until empty. 535122922Sandre while (!DeadInsts.empty()) { 536122922Sandre Value *V = DeadInsts.pop_back_val(); 537122922Sandre Instruction *I = cast_or_null<Instruction>(V); 538122922Sandre if (!I) 539122922Sandre continue; 540122922Sandre assert(isInstructionTriviallyDead(I, TLI) && 541190948Srwatson "Live instruction found in dead worklist!"); 542122922Sandre assert(I->use_empty() && "Instructions with uses are not dead."); 543122922Sandre 544122922Sandre // Don't lose the debug info while deleting the instructions. 545122922Sandre salvageDebugInfo(*I); 546122922Sandre 547122922Sandre if (AboutToDeleteCallback) 548122922Sandre AboutToDeleteCallback(I); 549190948Srwatson 550122922Sandre // Null out all of the instruction's operands to see if any operand becomes 551122922Sandre // dead as we go. 552122922Sandre for (Use &OpU : I->operands()) { 553122922Sandre Value *OpV = OpU.get(); 554122922Sandre OpU.set(nullptr); 555122922Sandre 556122922Sandre if (!OpV->use_empty()) 557190948Srwatson continue; 558133874Srwatson 559122922Sandre // If the operand is an instruction that became dead as we nulled out the 560122922Sandre // operand, and if it is 'trivially' dead, delete it in a future loop 561122922Sandre // iteration. 562122922Sandre if (Instruction *OpI = dyn_cast<Instruction>(OpV)) 563122922Sandre if (isInstructionTriviallyDead(OpI, TLI)) 564122922Sandre DeadInsts.push_back(OpI); 565190948Srwatson } 566122922Sandre if (MSSAU) 567122922Sandre MSSAU->removeMemoryAccess(I); 568122922Sandre 569122922Sandre I->eraseFromParent(); 570122922Sandre } 571122922Sandre} 572122922Sandre 573122922Sandrebool llvm::replaceDbgUsesWithUndef(Instruction *I) { 574122922Sandre SmallVector<DbgVariableIntrinsic *, 1> DbgUsers; 575122922Sandre findDbgUsers(DbgUsers, I); 576122922Sandre for (auto *DII : DbgUsers) { 577122922Sandre Value *Undef = UndefValue::get(I->getType()); 578122922Sandre DII->replaceVariableLocationOp(I, Undef); 579122922Sandre } 580122922Sandre return !DbgUsers.empty(); 581122922Sandre} 582122922Sandre 583122922Sandre/// areAllUsesEqual - Check whether the uses of a value are all the same. 584122922Sandre/// This is similar to Instruction::hasOneUse() except this will also return 585165118Sbz/// true when there are no uses or multiple uses that all refer to the same 586165118Sbz/// value. 587165118Sbzstatic bool areAllUsesEqual(Instruction *I) { 588122922Sandre Value::user_iterator UI = I->user_begin(); 589181803Sbz Value::user_iterator UE = I->user_end(); 590122922Sandre if (UI == UE) 591122922Sandre return true; 592122922Sandre 593122922Sandre User *TheUse = *UI; 594122922Sandre for (++UI; UI != UE; ++UI) { 595122922Sandre if (*UI != TheUse) 596122922Sandre return false; 597122922Sandre } 598122922Sandre return true; 599181803Sbz} 600181803Sbz 601181803Sbz/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively 602122922Sandre/// dead PHI node, due to being a def-use chain of single-use nodes that 603122922Sandre/// either forms a cycle or is terminated by a trivially dead instruction, 604122922Sandre/// delete it. If that makes any of its operands trivially dead, delete them 605122922Sandre/// too, recursively. Return true if a change was made. 606122922Sandrebool llvm::RecursivelyDeleteDeadPHINode(PHINode *PN, 607122922Sandre const TargetLibraryInfo *TLI, 608165118Sbz llvm::MemorySSAUpdater *MSSAU) { 609122922Sandre SmallPtrSet<Instruction*, 4> Visited; 610122922Sandre for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects(); 611122922Sandre I = cast<Instruction>(*I->user_begin())) { 612122922Sandre if (I->use_empty()) 613122922Sandre return RecursivelyDeleteTriviallyDeadInstructions(I, TLI, MSSAU); 614122922Sandre 615122922Sandre // If we find an instruction more than once, we're on a cycle that 616122922Sandre // won't prove fruitful. 617122922Sandre if (!Visited.insert(I).second) { 618133477Sandre // Break the cycle and delete the instruction and its operands. 619122922Sandre I->replaceAllUsesWith(UndefValue::get(I->getType())); 620122922Sandre (void)RecursivelyDeleteTriviallyDeadInstructions(I, TLI, MSSAU); 621122922Sandre return true; 622122922Sandre } 623122922Sandre } 624122922Sandre return false; 625122922Sandre} 626122922Sandre 627181803Sbzstatic bool 628122922SandresimplifyAndDCEInstruction(Instruction *I, 629122922Sandre SmallSetVector<Instruction *, 16> &WorkList, 630122922Sandre const DataLayout &DL, 631122922Sandre const TargetLibraryInfo *TLI) { 632122922Sandre if (isInstructionTriviallyDead(I, TLI)) { 633122922Sandre salvageDebugInfo(*I); 634122922Sandre 635122922Sandre // Null out all of the instruction's operands to see if any operand becomes 636170030Srwatson // dead as we go. 637170030Srwatson for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 638122922Sandre Value *OpV = I->getOperand(i); 639122922Sandre I->setOperand(i, nullptr); 640122922Sandre 641122922Sandre if (!OpV->use_empty() || I == OpV) 642191816Szec continue; 643128574Sandre 644191917Szec // If the operand is an instruction that became dead as we nulled out the 645122922Sandre // operand, and if it is 'trivially' dead, delete it in a future loop 646122922Sandre // iteration. 647181803Sbz if (Instruction *OpI = dyn_cast<Instruction>(OpV)) 648122922Sandre if (isInstructionTriviallyDead(OpI, TLI)) 649181803Sbz WorkList.insert(OpI); 650122922Sandre } 651122922Sandre 652181803Sbz I->eraseFromParent(); 653181803Sbz 654181887Sjulian return true; 655181888Sjulian } 656122922Sandre 657181803Sbz if (Value *SimpleV = SimplifyInstruction(I, DL)) { 658122922Sandre // Add the users to the worklist. CAREFUL: an instruction can use itself, 659181803Sbz // in the case of a phi node. 660181803Sbz for (User *U : I->users()) { 661181803Sbz if (U != I) { 662122922Sandre WorkList.insert(cast<Instruction>(U)); 663181803Sbz } 664122922Sandre } 665181803Sbz 666122922Sandre // Replace the instruction with its simplified value. 667181887Sjulian bool Changed = false; 668181887Sjulian if (!I->use_empty()) { 669181887Sjulian I->replaceAllUsesWith(SimpleV); 670191816Szec Changed = true; 671122922Sandre } 672 if (isInstructionTriviallyDead(I, TLI)) { 673 I->eraseFromParent(); 674 Changed = true; 675 } 676 return Changed; 677 } 678 return false; 679} 680 681/// SimplifyInstructionsInBlock - Scan the specified basic block and try to 682/// simplify any instructions in it and recursively delete dead instructions. 683/// 684/// This returns true if it changed the code, note that it can delete 685/// instructions in other blocks as well in this block. 686bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB, 687 const TargetLibraryInfo *TLI) { 688 bool MadeChange = false; 689 const DataLayout &DL = BB->getModule()->getDataLayout(); 690 691#ifndef NDEBUG 692 // In debug builds, ensure that the terminator of the block is never replaced 693 // or deleted by these simplifications. The idea of simplification is that it 694 // cannot introduce new instructions, and there is no way to replace the 695 // terminator of a block without introducing a new instruction. 696 AssertingVH<Instruction> TerminatorVH(&BB->back()); 697#endif 698 699 SmallSetVector<Instruction *, 16> WorkList; 700 // Iterate over the original function, only adding insts to the worklist 701 // if they actually need to be revisited. This avoids having to pre-init 702 // the worklist with the entire function's worth of instructions. 703 for (BasicBlock::iterator BI = BB->begin(), E = std::prev(BB->end()); 704 BI != E;) { 705 assert(!BI->isTerminator()); 706 Instruction *I = &*BI; 707 ++BI; 708 709 // We're visiting this instruction now, so make sure it's not in the 710 // worklist from an earlier visit. 711 if (!WorkList.count(I)) 712 MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI); 713 } 714 715 while (!WorkList.empty()) { 716 Instruction *I = WorkList.pop_back_val(); 717 MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI); 718 } 719 return MadeChange; 720} 721 722//===----------------------------------------------------------------------===// 723// Control Flow Graph Restructuring. 724// 725 726void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, 727 DomTreeUpdater *DTU) { 728 729 // If BB has single-entry PHI nodes, fold them. 730 while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) { 731 Value *NewVal = PN->getIncomingValue(0); 732 // Replace self referencing PHI with undef, it must be dead. 733 if (NewVal == PN) NewVal = UndefValue::get(PN->getType()); 734 PN->replaceAllUsesWith(NewVal); 735 PN->eraseFromParent(); 736 } 737 738 BasicBlock *PredBB = DestBB->getSinglePredecessor(); 739 assert(PredBB && "Block doesn't have a single predecessor!"); 740 741 bool ReplaceEntryBB = PredBB->isEntryBlock(); 742 743 // DTU updates: Collect all the edges that enter 744 // PredBB. These dominator edges will be redirected to DestBB. 745 SmallVector<DominatorTree::UpdateType, 32> Updates; 746 747 if (DTU) { 748 SmallPtrSet<BasicBlock *, 2> PredsOfPredBB(pred_begin(PredBB), 749 pred_end(PredBB)); 750 Updates.reserve(Updates.size() + 2 * PredsOfPredBB.size() + 1); 751 for (BasicBlock *PredOfPredBB : PredsOfPredBB) 752 // This predecessor of PredBB may already have DestBB as a successor. 753 if (PredOfPredBB != PredBB) 754 Updates.push_back({DominatorTree::Insert, PredOfPredBB, DestBB}); 755 for (BasicBlock *PredOfPredBB : PredsOfPredBB) 756 Updates.push_back({DominatorTree::Delete, PredOfPredBB, PredBB}); 757 Updates.push_back({DominatorTree::Delete, PredBB, DestBB}); 758 } 759 760 // Zap anything that took the address of DestBB. Not doing this will give the 761 // address an invalid value. 762 if (DestBB->hasAddressTaken()) { 763 BlockAddress *BA = BlockAddress::get(DestBB); 764 Constant *Replacement = 765 ConstantInt::get(Type::getInt32Ty(BA->getContext()), 1); 766 BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement, 767 BA->getType())); 768 BA->destroyConstant(); 769 } 770 771 // Anything that branched to PredBB now branches to DestBB. 772 PredBB->replaceAllUsesWith(DestBB); 773 774 // Splice all the instructions from PredBB to DestBB. 775 PredBB->getTerminator()->eraseFromParent(); 776 DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList()); 777 new UnreachableInst(PredBB->getContext(), PredBB); 778 779 // If the PredBB is the entry block of the function, move DestBB up to 780 // become the entry block after we erase PredBB. 781 if (ReplaceEntryBB) 782 DestBB->moveAfter(PredBB); 783 784 if (DTU) { 785 assert(PredBB->getInstList().size() == 1 && 786 isa<UnreachableInst>(PredBB->getTerminator()) && 787 "The successor list of PredBB isn't empty before " 788 "applying corresponding DTU updates."); 789 DTU->applyUpdatesPermissive(Updates); 790 DTU->deleteBB(PredBB); 791 // Recalculation of DomTree is needed when updating a forward DomTree and 792 // the Entry BB is replaced. 793 if (ReplaceEntryBB && DTU->hasDomTree()) { 794 // The entry block was removed and there is no external interface for 795 // the dominator tree to be notified of this change. In this corner-case 796 // we recalculate the entire tree. 797 DTU->recalculate(*(DestBB->getParent())); 798 } 799 } 800 801 else { 802 PredBB->eraseFromParent(); // Nuke BB if DTU is nullptr. 803 } 804} 805 806/// Return true if we can choose one of these values to use in place of the 807/// other. Note that we will always choose the non-undef value to keep. 808static bool CanMergeValues(Value *First, Value *Second) { 809 return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second); 810} 811 812/// Return true if we can fold BB, an almost-empty BB ending in an unconditional 813/// branch to Succ, into Succ. 814/// 815/// Assumption: Succ is the single successor for BB. 816static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 817 assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 818 819 LLVM_DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into " 820 << Succ->getName() << "\n"); 821 // Shortcut, if there is only a single predecessor it must be BB and merging 822 // is always safe 823 if (Succ->getSinglePredecessor()) return true; 824 825 // Make a list of the predecessors of BB 826 SmallPtrSet<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB)); 827 828 // Look at all the phi nodes in Succ, to see if they present a conflict when 829 // merging these blocks 830 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 831 PHINode *PN = cast<PHINode>(I); 832 833 // If the incoming value from BB is again a PHINode in 834 // BB which has the same incoming value for *PI as PN does, we can 835 // merge the phi nodes and then the blocks can still be merged 836 PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB)); 837 if (BBPN && BBPN->getParent() == BB) { 838 for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) { 839 BasicBlock *IBB = PN->getIncomingBlock(PI); 840 if (BBPreds.count(IBB) && 841 !CanMergeValues(BBPN->getIncomingValueForBlock(IBB), 842 PN->getIncomingValue(PI))) { 843 LLVM_DEBUG(dbgs() 844 << "Can't fold, phi node " << PN->getName() << " in " 845 << Succ->getName() << " is conflicting with " 846 << BBPN->getName() << " with regard to common predecessor " 847 << IBB->getName() << "\n"); 848 return false; 849 } 850 } 851 } else { 852 Value* Val = PN->getIncomingValueForBlock(BB); 853 for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) { 854 // See if the incoming value for the common predecessor is equal to the 855 // one for BB, in which case this phi node will not prevent the merging 856 // of the block. 857 BasicBlock *IBB = PN->getIncomingBlock(PI); 858 if (BBPreds.count(IBB) && 859 !CanMergeValues(Val, PN->getIncomingValue(PI))) { 860 LLVM_DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() 861 << " in " << Succ->getName() 862 << " is conflicting with regard to common " 863 << "predecessor " << IBB->getName() << "\n"); 864 return false; 865 } 866 } 867 } 868 } 869 870 return true; 871} 872 873using PredBlockVector = SmallVector<BasicBlock *, 16>; 874using IncomingValueMap = DenseMap<BasicBlock *, Value *>; 875 876/// Determines the value to use as the phi node input for a block. 877/// 878/// Select between \p OldVal any value that we know flows from \p BB 879/// to a particular phi on the basis of which one (if either) is not 880/// undef. Update IncomingValues based on the selected value. 881/// 882/// \param OldVal The value we are considering selecting. 883/// \param BB The block that the value flows in from. 884/// \param IncomingValues A map from block-to-value for other phi inputs 885/// that we have examined. 886/// 887/// \returns the selected value. 888static Value *selectIncomingValueForBlock(Value *OldVal, BasicBlock *BB, 889 IncomingValueMap &IncomingValues) { 890 if (!isa<UndefValue>(OldVal)) { 891 assert((!IncomingValues.count(BB) || 892 IncomingValues.find(BB)->second == OldVal) && 893 "Expected OldVal to match incoming value from BB!"); 894 895 IncomingValues.insert(std::make_pair(BB, OldVal)); 896 return OldVal; 897 } 898 899 IncomingValueMap::const_iterator It = IncomingValues.find(BB); 900 if (It != IncomingValues.end()) return It->second; 901 902 return OldVal; 903} 904 905/// Create a map from block to value for the operands of a 906/// given phi. 907/// 908/// Create a map from block to value for each non-undef value flowing 909/// into \p PN. 910/// 911/// \param PN The phi we are collecting the map for. 912/// \param IncomingValues [out] The map from block to value for this phi. 913static void gatherIncomingValuesToPhi(PHINode *PN, 914 IncomingValueMap &IncomingValues) { 915 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 916 BasicBlock *BB = PN->getIncomingBlock(i); 917 Value *V = PN->getIncomingValue(i); 918 919 if (!isa<UndefValue>(V)) 920 IncomingValues.insert(std::make_pair(BB, V)); 921 } 922} 923 924/// Replace the incoming undef values to a phi with the values 925/// from a block-to-value map. 926/// 927/// \param PN The phi we are replacing the undefs in. 928/// \param IncomingValues A map from block to value. 929static void replaceUndefValuesInPhi(PHINode *PN, 930 const IncomingValueMap &IncomingValues) { 931 SmallVector<unsigned> TrueUndefOps; 932 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 933 Value *V = PN->getIncomingValue(i); 934 935 if (!isa<UndefValue>(V)) continue; 936 937 BasicBlock *BB = PN->getIncomingBlock(i); 938 IncomingValueMap::const_iterator It = IncomingValues.find(BB); 939 940 // Keep track of undef/poison incoming values. Those must match, so we fix 941 // them up below if needed. 942 // Note: this is conservatively correct, but we could try harder and group 943 // the undef values per incoming basic block. 944 if (It == IncomingValues.end()) { 945 TrueUndefOps.push_back(i); 946 continue; 947 } 948 949 // There is a defined value for this incoming block, so map this undef 950 // incoming value to the defined value. 951 PN->setIncomingValue(i, It->second); 952 } 953 954 // If there are both undef and poison values incoming, then convert those 955 // values to undef. It is invalid to have different values for the same 956 // incoming block. 957 unsigned PoisonCount = count_if(TrueUndefOps, [&](unsigned i) { 958 return isa<PoisonValue>(PN->getIncomingValue(i)); 959 }); 960 if (PoisonCount != 0 && PoisonCount != TrueUndefOps.size()) { 961 for (unsigned i : TrueUndefOps) 962 PN->setIncomingValue(i, UndefValue::get(PN->getType())); 963 } 964} 965 966/// Replace a value flowing from a block to a phi with 967/// potentially multiple instances of that value flowing from the 968/// block's predecessors to the phi. 969/// 970/// \param BB The block with the value flowing into the phi. 971/// \param BBPreds The predecessors of BB. 972/// \param PN The phi that we are updating. 973static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB, 974 const PredBlockVector &BBPreds, 975 PHINode *PN) { 976 Value *OldVal = PN->removeIncomingValue(BB, false); 977 assert(OldVal && "No entry in PHI for Pred BB!"); 978 979 IncomingValueMap IncomingValues; 980 981 // We are merging two blocks - BB, and the block containing PN - and 982 // as a result we need to redirect edges from the predecessors of BB 983 // to go to the block containing PN, and update PN 984 // accordingly. Since we allow merging blocks in the case where the 985 // predecessor and successor blocks both share some predecessors, 986 // and where some of those common predecessors might have undef 987 // values flowing into PN, we want to rewrite those values to be 988 // consistent with the non-undef values. 989 990 gatherIncomingValuesToPhi(PN, IncomingValues); 991 992 // If this incoming value is one of the PHI nodes in BB, the new entries 993 // in the PHI node are the entries from the old PHI. 994 if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { 995 PHINode *OldValPN = cast<PHINode>(OldVal); 996 for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) { 997 // Note that, since we are merging phi nodes and BB and Succ might 998 // have common predecessors, we could end up with a phi node with 999 // identical incoming branches. This will be cleaned up later (and 1000 // will trigger asserts if we try to clean it up now, without also 1001 // simplifying the corresponding conditional branch). 1002 BasicBlock *PredBB = OldValPN->getIncomingBlock(i); 1003 Value *PredVal = OldValPN->getIncomingValue(i); 1004 Value *Selected = selectIncomingValueForBlock(PredVal, PredBB, 1005 IncomingValues); 1006 1007 // And add a new incoming value for this predecessor for the 1008 // newly retargeted branch. 1009 PN->addIncoming(Selected, PredBB); 1010 } 1011 } else { 1012 for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) { 1013 // Update existing incoming values in PN for this 1014 // predecessor of BB. 1015 BasicBlock *PredBB = BBPreds[i]; 1016 Value *Selected = selectIncomingValueForBlock(OldVal, PredBB, 1017 IncomingValues); 1018 1019 // And add a new incoming value for this predecessor for the 1020 // newly retargeted branch. 1021 PN->addIncoming(Selected, PredBB); 1022 } 1023 } 1024 1025 replaceUndefValuesInPhi(PN, IncomingValues); 1026} 1027 1028bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, 1029 DomTreeUpdater *DTU) { 1030 assert(BB != &BB->getParent()->getEntryBlock() && 1031 "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!"); 1032 1033 // We can't eliminate infinite loops. 1034 BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0); 1035 if (BB == Succ) return false; 1036 1037 // Check to see if merging these blocks would cause conflicts for any of the 1038 // phi nodes in BB or Succ. If not, we can safely merge. 1039 if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false; 1040 1041 // Check for cases where Succ has multiple predecessors and a PHI node in BB 1042 // has uses which will not disappear when the PHI nodes are merged. It is 1043 // possible to handle such cases, but difficult: it requires checking whether 1044 // BB dominates Succ, which is non-trivial to calculate in the case where 1045 // Succ has multiple predecessors. Also, it requires checking whether 1046 // constructing the necessary self-referential PHI node doesn't introduce any 1047 // conflicts; this isn't too difficult, but the previous code for doing this 1048 // was incorrect. 1049 // 1050 // Note that if this check finds a live use, BB dominates Succ, so BB is 1051 // something like a loop pre-header (or rarely, a part of an irreducible CFG); 1052 // folding the branch isn't profitable in that case anyway. 1053 if (!Succ->getSinglePredecessor()) { 1054 BasicBlock::iterator BBI = BB->begin(); 1055 while (isa<PHINode>(*BBI)) { 1056 for (Use &U : BBI->uses()) { 1057 if (PHINode* PN = dyn_cast<PHINode>(U.getUser())) { 1058 if (PN->getIncomingBlock(U) != BB) 1059 return false; 1060 } else { 1061 return false; 1062 } 1063 } 1064 ++BBI; 1065 } 1066 } 1067 1068 // We cannot fold the block if it's a branch to an already present callbr 1069 // successor because that creates duplicate successors. 1070 for (BasicBlock *PredBB : predecessors(BB)) { 1071 if (auto *CBI = dyn_cast<CallBrInst>(PredBB->getTerminator())) { 1072 if (Succ == CBI->getDefaultDest()) 1073 return false; 1074 for (unsigned i = 0, e = CBI->getNumIndirectDests(); i != e; ++i) 1075 if (Succ == CBI->getIndirectDest(i)) 1076 return false; 1077 } 1078 } 1079 1080 LLVM_DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB); 1081 1082 SmallVector<DominatorTree::UpdateType, 32> Updates; 1083 if (DTU) { 1084 // All predecessors of BB will be moved to Succ. 1085 SmallPtrSet<BasicBlock *, 8> PredsOfBB(pred_begin(BB), pred_end(BB)); 1086 SmallPtrSet<BasicBlock *, 8> PredsOfSucc(pred_begin(Succ), pred_end(Succ)); 1087 Updates.reserve(Updates.size() + 2 * PredsOfBB.size() + 1); 1088 for (auto *PredOfBB : PredsOfBB) 1089 // This predecessor of BB may already have Succ as a successor. 1090 if (!PredsOfSucc.contains(PredOfBB)) 1091 Updates.push_back({DominatorTree::Insert, PredOfBB, Succ}); 1092 for (auto *PredOfBB : PredsOfBB) 1093 Updates.push_back({DominatorTree::Delete, PredOfBB, BB}); 1094 Updates.push_back({DominatorTree::Delete, BB, Succ}); 1095 } 1096 1097 if (isa<PHINode>(Succ->begin())) { 1098 // If there is more than one pred of succ, and there are PHI nodes in 1099 // the successor, then we need to add incoming edges for the PHI nodes 1100 // 1101 const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB)); 1102 1103 // Loop over all of the PHI nodes in the successor of BB. 1104 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 1105 PHINode *PN = cast<PHINode>(I); 1106 1107 redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN); 1108 } 1109 } 1110 1111 if (Succ->getSinglePredecessor()) { 1112 // BB is the only predecessor of Succ, so Succ will end up with exactly 1113 // the same predecessors BB had. 1114 1115 // Copy over any phi, debug or lifetime instruction. 1116 BB->getTerminator()->eraseFromParent(); 1117 Succ->getInstList().splice(Succ->getFirstNonPHI()->getIterator(), 1118 BB->getInstList()); 1119 } else { 1120 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 1121 // We explicitly check for such uses in CanPropagatePredecessorsForPHIs. 1122 assert(PN->use_empty() && "There shouldn't be any uses here!"); 1123 PN->eraseFromParent(); 1124 } 1125 } 1126 1127 // If the unconditional branch we replaced contains llvm.loop metadata, we 1128 // add the metadata to the branch instructions in the predecessors. 1129 unsigned LoopMDKind = BB->getContext().getMDKindID("llvm.loop"); 1130 Instruction *TI = BB->getTerminator(); 1131 if (TI) 1132 if (MDNode *LoopMD = TI->getMetadata(LoopMDKind)) 1133 for (BasicBlock *Pred : predecessors(BB)) 1134 Pred->getTerminator()->setMetadata(LoopMDKind, LoopMD); 1135 1136 // For AutoFDO, since BB is going to be removed, we won't be able to sample 1137 // it. To avoid assigning a zero weight for BB, move all its pseudo probes 1138 // into Succ and mark them dangling. This should allow the counts inference a 1139 // chance to get a more reasonable weight for BB. 1140 moveAndDanglePseudoProbes(BB, &*Succ->getFirstInsertionPt()); 1141 1142 // Everything that jumped to BB now goes to Succ. 1143 BB->replaceAllUsesWith(Succ); 1144 if (!Succ->hasName()) Succ->takeName(BB); 1145 1146 // Clear the successor list of BB to match updates applying to DTU later. 1147 if (BB->getTerminator()) 1148 BB->getInstList().pop_back(); 1149 new UnreachableInst(BB->getContext(), BB); 1150 assert(succ_empty(BB) && "The successor list of BB isn't empty before " 1151 "applying corresponding DTU updates."); 1152 1153 if (DTU) 1154 DTU->applyUpdates(Updates); 1155 1156 DeleteDeadBlock(BB, DTU); 1157 1158 return true; 1159} 1160 1161static bool EliminateDuplicatePHINodesNaiveImpl(BasicBlock *BB) { 1162 // This implementation doesn't currently consider undef operands 1163 // specially. Theoretically, two phis which are identical except for 1164 // one having an undef where the other doesn't could be collapsed. 1165 1166 bool Changed = false; 1167 1168 // Examine each PHI. 1169 // Note that increment of I must *NOT* be in the iteration_expression, since 1170 // we don't want to immediately advance when we restart from the beginning. 1171 for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I);) { 1172 ++I; 1173 // Is there an identical PHI node in this basic block? 1174 // Note that we only look in the upper square's triangle, 1175 // we already checked that the lower triangle PHI's aren't identical. 1176 for (auto J = I; PHINode *DuplicatePN = dyn_cast<PHINode>(J); ++J) { 1177 if (!DuplicatePN->isIdenticalToWhenDefined(PN)) 1178 continue; 1179 // A duplicate. Replace this PHI with the base PHI. 1180 ++NumPHICSEs; 1181 DuplicatePN->replaceAllUsesWith(PN); 1182 DuplicatePN->eraseFromParent(); 1183 Changed = true; 1184 1185 // The RAUW can change PHIs that we already visited. 1186 I = BB->begin(); 1187 break; // Start over from the beginning. 1188 } 1189 } 1190 return Changed; 1191} 1192 1193static bool EliminateDuplicatePHINodesSetBasedImpl(BasicBlock *BB) { 1194 // This implementation doesn't currently consider undef operands 1195 // specially. Theoretically, two phis which are identical except for 1196 // one having an undef where the other doesn't could be collapsed. 1197 1198 struct PHIDenseMapInfo { 1199 static PHINode *getEmptyKey() { 1200 return DenseMapInfo<PHINode *>::getEmptyKey(); 1201 } 1202 1203 static PHINode *getTombstoneKey() { 1204 return DenseMapInfo<PHINode *>::getTombstoneKey(); 1205 } 1206 1207 static bool isSentinel(PHINode *PN) { 1208 return PN == getEmptyKey() || PN == getTombstoneKey(); 1209 } 1210 1211 // WARNING: this logic must be kept in sync with 1212 // Instruction::isIdenticalToWhenDefined()! 1213 static unsigned getHashValueImpl(PHINode *PN) { 1214 // Compute a hash value on the operands. Instcombine will likely have 1215 // sorted them, which helps expose duplicates, but we have to check all 1216 // the operands to be safe in case instcombine hasn't run. 1217 return static_cast<unsigned>(hash_combine( 1218 hash_combine_range(PN->value_op_begin(), PN->value_op_end()), 1219 hash_combine_range(PN->block_begin(), PN->block_end()))); 1220 } 1221 1222 static unsigned getHashValue(PHINode *PN) { 1223#ifndef NDEBUG 1224 // If -phicse-debug-hash was specified, return a constant -- this 1225 // will force all hashing to collide, so we'll exhaustively search 1226 // the table for a match, and the assertion in isEqual will fire if 1227 // there's a bug causing equal keys to hash differently. 1228 if (PHICSEDebugHash) 1229 return 0; 1230#endif 1231 return getHashValueImpl(PN); 1232 } 1233 1234 static bool isEqualImpl(PHINode *LHS, PHINode *RHS) { 1235 if (isSentinel(LHS) || isSentinel(RHS)) 1236 return LHS == RHS; 1237 return LHS->isIdenticalTo(RHS); 1238 } 1239 1240 static bool isEqual(PHINode *LHS, PHINode *RHS) { 1241 // These comparisons are nontrivial, so assert that equality implies 1242 // hash equality (DenseMap demands this as an invariant). 1243 bool Result = isEqualImpl(LHS, RHS); 1244 assert(!Result || (isSentinel(LHS) && LHS == RHS) || 1245 getHashValueImpl(LHS) == getHashValueImpl(RHS)); 1246 return Result; 1247 } 1248 }; 1249 1250 // Set of unique PHINodes. 1251 DenseSet<PHINode *, PHIDenseMapInfo> PHISet; 1252 PHISet.reserve(4 * PHICSENumPHISmallSize); 1253 1254 // Examine each PHI. 1255 bool Changed = false; 1256 for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I++);) { 1257 auto Inserted = PHISet.insert(PN); 1258 if (!Inserted.second) { 1259 // A duplicate. Replace this PHI with its duplicate. 1260 ++NumPHICSEs; 1261 PN->replaceAllUsesWith(*Inserted.first); 1262 PN->eraseFromParent(); 1263 Changed = true; 1264 1265 // The RAUW can change PHIs that we already visited. Start over from the 1266 // beginning. 1267 PHISet.clear(); 1268 I = BB->begin(); 1269 } 1270 } 1271 1272 return Changed; 1273} 1274 1275bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { 1276 if ( 1277#ifndef NDEBUG 1278 !PHICSEDebugHash && 1279#endif 1280 hasNItemsOrLess(BB->phis(), PHICSENumPHISmallSize)) 1281 return EliminateDuplicatePHINodesNaiveImpl(BB); 1282 return EliminateDuplicatePHINodesSetBasedImpl(BB); 1283} 1284 1285/// If the specified pointer points to an object that we control, try to modify 1286/// the object's alignment to PrefAlign. Returns a minimum known alignment of 1287/// the value after the operation, which may be lower than PrefAlign. 1288/// 1289/// Increating value alignment isn't often possible though. If alignment is 1290/// important, a more reliable approach is to simply align all global variables 1291/// and allocation instructions to their preferred alignment from the beginning. 1292static Align tryEnforceAlignment(Value *V, Align PrefAlign, 1293 const DataLayout &DL) { 1294 V = V->stripPointerCasts(); 1295 1296 if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) { 1297 // TODO: Ideally, this function would not be called if PrefAlign is smaller 1298 // than the current alignment, as the known bits calculation should have 1299 // already taken it into account. However, this is not always the case, 1300 // as computeKnownBits() has a depth limit, while stripPointerCasts() 1301 // doesn't. 1302 Align CurrentAlign = AI->getAlign(); 1303 if (PrefAlign <= CurrentAlign) 1304 return CurrentAlign; 1305 1306 // If the preferred alignment is greater than the natural stack alignment 1307 // then don't round up. This avoids dynamic stack realignment. 1308 if (DL.exceedsNaturalStackAlignment(PrefAlign)) 1309 return CurrentAlign; 1310 AI->setAlignment(PrefAlign); 1311 return PrefAlign; 1312 } 1313 1314 if (auto *GO = dyn_cast<GlobalObject>(V)) { 1315 // TODO: as above, this shouldn't be necessary. 1316 Align CurrentAlign = GO->getPointerAlignment(DL); 1317 if (PrefAlign <= CurrentAlign) 1318 return CurrentAlign; 1319 1320 // If there is a large requested alignment and we can, bump up the alignment 1321 // of the global. If the memory we set aside for the global may not be the 1322 // memory used by the final program then it is impossible for us to reliably 1323 // enforce the preferred alignment. 1324 if (!GO->canIncreaseAlignment()) 1325 return CurrentAlign; 1326 1327 GO->setAlignment(PrefAlign); 1328 return PrefAlign; 1329 } 1330 1331 return Align(1); 1332} 1333 1334Align llvm::getOrEnforceKnownAlignment(Value *V, MaybeAlign PrefAlign, 1335 const DataLayout &DL, 1336 const Instruction *CxtI, 1337 AssumptionCache *AC, 1338 const DominatorTree *DT) { 1339 assert(V->getType()->isPointerTy() && 1340 "getOrEnforceKnownAlignment expects a pointer!"); 1341 1342 KnownBits Known = computeKnownBits(V, DL, 0, AC, CxtI, DT); 1343 unsigned TrailZ = Known.countMinTrailingZeros(); 1344 1345 // Avoid trouble with ridiculously large TrailZ values, such as 1346 // those computed from a null pointer. 1347 // LLVM doesn't support alignments larger than (1 << MaxAlignmentExponent). 1348 TrailZ = std::min(TrailZ, +Value::MaxAlignmentExponent); 1349 1350 Align Alignment = Align(1ull << std::min(Known.getBitWidth() - 1, TrailZ)); 1351 1352 if (PrefAlign && *PrefAlign > Alignment) 1353 Alignment = std::max(Alignment, tryEnforceAlignment(V, *PrefAlign, DL)); 1354 1355 // We don't need to make any adjustment. 1356 return Alignment; 1357} 1358 1359///===---------------------------------------------------------------------===// 1360/// Dbg Intrinsic utilities 1361/// 1362 1363/// See if there is a dbg.value intrinsic for DIVar for the PHI node. 1364static bool PhiHasDebugValue(DILocalVariable *DIVar, 1365 DIExpression *DIExpr, 1366 PHINode *APN) { 1367 // Since we can't guarantee that the original dbg.declare instrinsic 1368 // is removed by LowerDbgDeclare(), we need to make sure that we are 1369 // not inserting the same dbg.value intrinsic over and over. 1370 SmallVector<DbgValueInst *, 1> DbgValues; 1371 findDbgValues(DbgValues, APN); 1372 for (auto *DVI : DbgValues) { 1373 assert(is_contained(DVI->getValues(), APN)); 1374 if ((DVI->getVariable() == DIVar) && (DVI->getExpression() == DIExpr)) 1375 return true; 1376 } 1377 return false; 1378} 1379 1380/// Check if the alloc size of \p ValTy is large enough to cover the variable 1381/// (or fragment of the variable) described by \p DII. 1382/// 1383/// This is primarily intended as a helper for the different 1384/// ConvertDebugDeclareToDebugValue functions. The dbg.declare/dbg.addr that is 1385/// converted describes an alloca'd variable, so we need to use the 1386/// alloc size of the value when doing the comparison. E.g. an i1 value will be 1387/// identified as covering an n-bit fragment, if the store size of i1 is at 1388/// least n bits. 1389static bool valueCoversEntireFragment(Type *ValTy, DbgVariableIntrinsic *DII) { 1390 const DataLayout &DL = DII->getModule()->getDataLayout(); 1391 TypeSize ValueSize = DL.getTypeAllocSizeInBits(ValTy); 1392 if (Optional<uint64_t> FragmentSize = DII->getFragmentSizeInBits()) { 1393 assert(!ValueSize.isScalable() && 1394 "Fragments don't work on scalable types."); 1395 return ValueSize.getFixedSize() >= *FragmentSize; 1396 } 1397 // We can't always calculate the size of the DI variable (e.g. if it is a 1398 // VLA). Try to use the size of the alloca that the dbg intrinsic describes 1399 // intead. 1400 if (DII->isAddressOfVariable()) { 1401 // DII should have exactly 1 location when it is an address. 1402 assert(DII->getNumVariableLocationOps() == 1 && 1403 "address of variable must have exactly 1 location operand."); 1404 if (auto *AI = 1405 dyn_cast_or_null<AllocaInst>(DII->getVariableLocationOp(0))) { 1406 if (Optional<TypeSize> FragmentSize = AI->getAllocationSizeInBits(DL)) { 1407 assert(ValueSize.isScalable() == FragmentSize->isScalable() && 1408 "Both sizes should agree on the scalable flag."); 1409 return TypeSize::isKnownGE(ValueSize, *FragmentSize); 1410 } 1411 } 1412 } 1413 // Could not determine size of variable. Conservatively return false. 1414 return false; 1415} 1416 1417/// Produce a DebugLoc to use for each dbg.declare/inst pair that are promoted 1418/// to a dbg.value. Because no machine insts can come from debug intrinsics, 1419/// only the scope and inlinedAt is significant. Zero line numbers are used in 1420/// case this DebugLoc leaks into any adjacent instructions. 1421static DebugLoc getDebugValueLoc(DbgVariableIntrinsic *DII, Instruction *Src) { 1422 // Original dbg.declare must have a location. 1423 const DebugLoc &DeclareLoc = DII->getDebugLoc(); 1424 MDNode *Scope = DeclareLoc.getScope(); 1425 DILocation *InlinedAt = DeclareLoc.getInlinedAt(); 1426 // Produce an unknown location with the correct scope / inlinedAt fields. 1427 return DILocation::get(DII->getContext(), 0, 0, Scope, InlinedAt); 1428} 1429 1430/// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value 1431/// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic. 1432void llvm::ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, 1433 StoreInst *SI, DIBuilder &Builder) { 1434 assert(DII->isAddressOfVariable()); 1435 auto *DIVar = DII->getVariable(); 1436 assert(DIVar && "Missing variable"); 1437 auto *DIExpr = DII->getExpression(); 1438 Value *DV = SI->getValueOperand(); 1439 1440 DebugLoc NewLoc = getDebugValueLoc(DII, SI); 1441 1442 if (!valueCoversEntireFragment(DV->getType(), DII)) { 1443 // FIXME: If storing to a part of the variable described by the dbg.declare, 1444 // then we want to insert a dbg.value for the corresponding fragment. 1445 LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: " 1446 << *DII << '\n'); 1447 // For now, when there is a store to parts of the variable (but we do not 1448 // know which part) we insert an dbg.value instrinsic to indicate that we 1449 // know nothing about the variable's content. 1450 DV = UndefValue::get(DV->getType()); 1451 Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, NewLoc, SI); 1452 return; 1453 } 1454 1455 Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, NewLoc, SI); 1456} 1457 1458/// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value 1459/// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic. 1460void llvm::ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, 1461 LoadInst *LI, DIBuilder &Builder) { 1462 auto *DIVar = DII->getVariable(); 1463 auto *DIExpr = DII->getExpression(); 1464 assert(DIVar && "Missing variable"); 1465 1466 if (!valueCoversEntireFragment(LI->getType(), DII)) { 1467 // FIXME: If only referring to a part of the variable described by the 1468 // dbg.declare, then we want to insert a dbg.value for the corresponding 1469 // fragment. 1470 LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: " 1471 << *DII << '\n'); 1472 return; 1473 } 1474 1475 DebugLoc NewLoc = getDebugValueLoc(DII, nullptr); 1476 1477 // We are now tracking the loaded value instead of the address. In the 1478 // future if multi-location support is added to the IR, it might be 1479 // preferable to keep tracking both the loaded value and the original 1480 // address in case the alloca can not be elided. 1481 Instruction *DbgValue = Builder.insertDbgValueIntrinsic( 1482 LI, DIVar, DIExpr, NewLoc, (Instruction *)nullptr); 1483 DbgValue->insertAfter(LI); 1484} 1485 1486/// Inserts a llvm.dbg.value intrinsic after a phi that has an associated 1487/// llvm.dbg.declare or llvm.dbg.addr intrinsic. 1488void llvm::ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, 1489 PHINode *APN, DIBuilder &Builder) { 1490 auto *DIVar = DII->getVariable(); 1491 auto *DIExpr = DII->getExpression(); 1492 assert(DIVar && "Missing variable"); 1493 1494 if (PhiHasDebugValue(DIVar, DIExpr, APN)) 1495 return; 1496 1497 if (!valueCoversEntireFragment(APN->getType(), DII)) { 1498 // FIXME: If only referring to a part of the variable described by the 1499 // dbg.declare, then we want to insert a dbg.value for the corresponding 1500 // fragment. 1501 LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: " 1502 << *DII << '\n'); 1503 return; 1504 } 1505 1506 BasicBlock *BB = APN->getParent(); 1507 auto InsertionPt = BB->getFirstInsertionPt(); 1508 1509 DebugLoc NewLoc = getDebugValueLoc(DII, nullptr); 1510 1511 // The block may be a catchswitch block, which does not have a valid 1512 // insertion point. 1513 // FIXME: Insert dbg.value markers in the successors when appropriate. 1514 if (InsertionPt != BB->end()) 1515 Builder.insertDbgValueIntrinsic(APN, DIVar, DIExpr, NewLoc, &*InsertionPt); 1516} 1517 1518/// Determine whether this alloca is either a VLA or an array. 1519static bool isArray(AllocaInst *AI) { 1520 return AI->isArrayAllocation() || 1521 (AI->getAllocatedType() && AI->getAllocatedType()->isArrayTy()); 1522} 1523 1524/// Determine whether this alloca is a structure. 1525static bool isStructure(AllocaInst *AI) { 1526 return AI->getAllocatedType() && AI->getAllocatedType()->isStructTy(); 1527} 1528 1529/// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set 1530/// of llvm.dbg.value intrinsics. 1531bool llvm::LowerDbgDeclare(Function &F) { 1532 bool Changed = false; 1533 DIBuilder DIB(*F.getParent(), /*AllowUnresolved*/ false); 1534 SmallVector<DbgDeclareInst *, 4> Dbgs; 1535 for (auto &FI : F) 1536 for (Instruction &BI : FI) 1537 if (auto DDI = dyn_cast<DbgDeclareInst>(&BI)) 1538 Dbgs.push_back(DDI); 1539 1540 if (Dbgs.empty()) 1541 return Changed; 1542 1543 for (auto &I : Dbgs) { 1544 DbgDeclareInst *DDI = I; 1545 AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress()); 1546 // If this is an alloca for a scalar variable, insert a dbg.value 1547 // at each load and store to the alloca and erase the dbg.declare. 1548 // The dbg.values allow tracking a variable even if it is not 1549 // stored on the stack, while the dbg.declare can only describe 1550 // the stack slot (and at a lexical-scope granularity). Later 1551 // passes will attempt to elide the stack slot. 1552 if (!AI || isArray(AI) || isStructure(AI)) 1553 continue; 1554 1555 // A volatile load/store means that the alloca can't be elided anyway. 1556 if (llvm::any_of(AI->users(), [](User *U) -> bool { 1557 if (LoadInst *LI = dyn_cast<LoadInst>(U)) 1558 return LI->isVolatile(); 1559 if (StoreInst *SI = dyn_cast<StoreInst>(U)) 1560 return SI->isVolatile(); 1561 return false; 1562 })) 1563 continue; 1564 1565 SmallVector<const Value *, 8> WorkList; 1566 WorkList.push_back(AI); 1567 while (!WorkList.empty()) { 1568 const Value *V = WorkList.pop_back_val(); 1569 for (auto &AIUse : V->uses()) { 1570 User *U = AIUse.getUser(); 1571 if (StoreInst *SI = dyn_cast<StoreInst>(U)) { 1572 if (AIUse.getOperandNo() == 1) 1573 ConvertDebugDeclareToDebugValue(DDI, SI, DIB); 1574 } else if (LoadInst *LI = dyn_cast<LoadInst>(U)) { 1575 ConvertDebugDeclareToDebugValue(DDI, LI, DIB); 1576 } else if (CallInst *CI = dyn_cast<CallInst>(U)) { 1577 // This is a call by-value or some other instruction that takes a 1578 // pointer to the variable. Insert a *value* intrinsic that describes 1579 // the variable by dereferencing the alloca. 1580 if (!CI->isLifetimeStartOrEnd()) { 1581 DebugLoc NewLoc = getDebugValueLoc(DDI, nullptr); 1582 auto *DerefExpr = 1583 DIExpression::append(DDI->getExpression(), dwarf::DW_OP_deref); 1584 DIB.insertDbgValueIntrinsic(AI, DDI->getVariable(), DerefExpr, 1585 NewLoc, CI); 1586 } 1587 } else if (BitCastInst *BI = dyn_cast<BitCastInst>(U)) { 1588 if (BI->getType()->isPointerTy()) 1589 WorkList.push_back(BI); 1590 } 1591 } 1592 } 1593 DDI->eraseFromParent(); 1594 Changed = true; 1595 } 1596 1597 if (Changed) 1598 for (BasicBlock &BB : F) 1599 RemoveRedundantDbgInstrs(&BB); 1600 1601 return Changed; 1602} 1603 1604/// Propagate dbg.value intrinsics through the newly inserted PHIs. 1605void llvm::insertDebugValuesForPHIs(BasicBlock *BB, 1606 SmallVectorImpl<PHINode *> &InsertedPHIs) { 1607 assert(BB && "No BasicBlock to clone dbg.value(s) from."); 1608 if (InsertedPHIs.size() == 0) 1609 return; 1610 1611 // Map existing PHI nodes to their dbg.values. 1612 ValueToValueMapTy DbgValueMap; 1613 for (auto &I : *BB) { 1614 if (auto DbgII = dyn_cast<DbgVariableIntrinsic>(&I)) { 1615 for (Value *V : DbgII->location_ops()) 1616 if (auto *Loc = dyn_cast_or_null<PHINode>(V)) 1617 DbgValueMap.insert({Loc, DbgII}); 1618 } 1619 } 1620 if (DbgValueMap.size() == 0) 1621 return; 1622 1623 // Map a pair of the destination BB and old dbg.value to the new dbg.value, 1624 // so that if a dbg.value is being rewritten to use more than one of the 1625 // inserted PHIs in the same destination BB, we can update the same dbg.value 1626 // with all the new PHIs instead of creating one copy for each. 1627 MapVector<std::pair<BasicBlock *, DbgVariableIntrinsic *>, 1628 DbgVariableIntrinsic *> 1629 NewDbgValueMap; 1630 // Then iterate through the new PHIs and look to see if they use one of the 1631 // previously mapped PHIs. If so, create a new dbg.value intrinsic that will 1632 // propagate the info through the new PHI. If we use more than one new PHI in 1633 // a single destination BB with the same old dbg.value, merge the updates so 1634 // that we get a single new dbg.value with all the new PHIs. 1635 for (auto PHI : InsertedPHIs) { 1636 BasicBlock *Parent = PHI->getParent(); 1637 // Avoid inserting an intrinsic into an EH block. 1638 if (Parent->getFirstNonPHI()->isEHPad()) 1639 continue; 1640 for (auto VI : PHI->operand_values()) { 1641 auto V = DbgValueMap.find(VI); 1642 if (V != DbgValueMap.end()) { 1643 auto *DbgII = cast<DbgVariableIntrinsic>(V->second); 1644 auto NewDI = NewDbgValueMap.find({Parent, DbgII}); 1645 if (NewDI == NewDbgValueMap.end()) { 1646 auto *NewDbgII = cast<DbgVariableIntrinsic>(DbgII->clone()); 1647 NewDI = NewDbgValueMap.insert({{Parent, DbgII}, NewDbgII}).first; 1648 } 1649 DbgVariableIntrinsic *NewDbgII = NewDI->second; 1650 // If PHI contains VI as an operand more than once, we may 1651 // replaced it in NewDbgII; confirm that it is present. 1652 if (is_contained(NewDbgII->location_ops(), VI)) 1653 NewDbgII->replaceVariableLocationOp(VI, PHI); 1654 } 1655 } 1656 } 1657 // Insert thew new dbg.values into their destination blocks. 1658 for (auto DI : NewDbgValueMap) { 1659 BasicBlock *Parent = DI.first.first; 1660 auto *NewDbgII = DI.second; 1661 auto InsertionPt = Parent->getFirstInsertionPt(); 1662 assert(InsertionPt != Parent->end() && "Ill-formed basic block"); 1663 NewDbgII->insertBefore(&*InsertionPt); 1664 } 1665} 1666 1667bool llvm::replaceDbgDeclare(Value *Address, Value *NewAddress, 1668 DIBuilder &Builder, uint8_t DIExprFlags, 1669 int Offset) { 1670 auto DbgAddrs = FindDbgAddrUses(Address); 1671 for (DbgVariableIntrinsic *DII : DbgAddrs) { 1672 const DebugLoc &Loc = DII->getDebugLoc(); 1673 auto *DIVar = DII->getVariable(); 1674 auto *DIExpr = DII->getExpression(); 1675 assert(DIVar && "Missing variable"); 1676 DIExpr = DIExpression::prepend(DIExpr, DIExprFlags, Offset); 1677 // Insert llvm.dbg.declare immediately before DII, and remove old 1678 // llvm.dbg.declare. 1679 Builder.insertDeclare(NewAddress, DIVar, DIExpr, Loc, DII); 1680 DII->eraseFromParent(); 1681 } 1682 return !DbgAddrs.empty(); 1683} 1684 1685static void replaceOneDbgValueForAlloca(DbgValueInst *DVI, Value *NewAddress, 1686 DIBuilder &Builder, int Offset) { 1687 const DebugLoc &Loc = DVI->getDebugLoc(); 1688 auto *DIVar = DVI->getVariable(); 1689 auto *DIExpr = DVI->getExpression(); 1690 assert(DIVar && "Missing variable"); 1691 1692 // This is an alloca-based llvm.dbg.value. The first thing it should do with 1693 // the alloca pointer is dereference it. Otherwise we don't know how to handle 1694 // it and give up. 1695 if (!DIExpr || DIExpr->getNumElements() < 1 || 1696 DIExpr->getElement(0) != dwarf::DW_OP_deref) 1697 return; 1698 1699 // Insert the offset before the first deref. 1700 // We could just change the offset argument of dbg.value, but it's unsigned... 1701 if (Offset) 1702 DIExpr = DIExpression::prepend(DIExpr, 0, Offset); 1703 1704 Builder.insertDbgValueIntrinsic(NewAddress, DIVar, DIExpr, Loc, DVI); 1705 DVI->eraseFromParent(); 1706} 1707 1708void llvm::replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress, 1709 DIBuilder &Builder, int Offset) { 1710 if (auto *L = LocalAsMetadata::getIfExists(AI)) 1711 if (auto *MDV = MetadataAsValue::getIfExists(AI->getContext(), L)) 1712 for (Use &U : llvm::make_early_inc_range(MDV->uses())) 1713 if (auto *DVI = dyn_cast<DbgValueInst>(U.getUser())) 1714 replaceOneDbgValueForAlloca(DVI, NewAllocaAddress, Builder, Offset); 1715} 1716 1717/// Where possible to salvage debug information for \p I do so 1718/// and return True. If not possible mark undef and return False. 1719void llvm::salvageDebugInfo(Instruction &I) { 1720 SmallVector<DbgVariableIntrinsic *, 1> DbgUsers; 1721 findDbgUsers(DbgUsers, &I); 1722 salvageDebugInfoForDbgValues(I, DbgUsers); 1723} 1724 1725void llvm::salvageDebugInfoForDbgValues( 1726 Instruction &I, ArrayRef<DbgVariableIntrinsic *> DbgUsers) { 1727 bool Salvaged = false; 1728 1729 for (auto *DII : DbgUsers) { 1730 // Do not add DW_OP_stack_value for DbgDeclare and DbgAddr, because they 1731 // are implicitly pointing out the value as a DWARF memory location 1732 // description. 1733 bool StackValue = isa<DbgValueInst>(DII); 1734 auto DIILocation = DII->location_ops(); 1735 assert( 1736 is_contained(DIILocation, &I) && 1737 "DbgVariableIntrinsic must use salvaged instruction as its location"); 1738 unsigned LocNo = std::distance(DIILocation.begin(), find(DIILocation, &I)); 1739 SmallVector<Value *, 4> AdditionalValues; 1740 DIExpression *SalvagedExpr = salvageDebugInfoImpl( 1741 I, DII->getExpression(), StackValue, LocNo, AdditionalValues); 1742 1743 // salvageDebugInfoImpl should fail on examining the first element of 1744 // DbgUsers, or none of them. 1745 if (!SalvagedExpr) 1746 break; 1747 1748 DII->replaceVariableLocationOp(&I, I.getOperand(0)); 1749 if (AdditionalValues.empty()) { 1750 DII->setExpression(SalvagedExpr); 1751 } else if (isa<DbgValueInst>(DII)) { 1752 DII->addVariableLocationOps(AdditionalValues, SalvagedExpr); 1753 } else { 1754 // Do not salvage using DIArgList for dbg.addr/dbg.declare, as it is 1755 // currently only valid for stack value expressions. 1756 Value *Undef = UndefValue::get(I.getOperand(0)->getType()); 1757 DII->replaceVariableLocationOp(I.getOperand(0), Undef); 1758 } 1759 LLVM_DEBUG(dbgs() << "SALVAGE: " << *DII << '\n'); 1760 Salvaged = true; 1761 } 1762 1763 if (Salvaged) 1764 return; 1765 1766 for (auto *DII : DbgUsers) { 1767 Value *Undef = UndefValue::get(I.getType()); 1768 DII->replaceVariableLocationOp(&I, Undef); 1769 } 1770} 1771 1772bool getSalvageOpsForGEP(GetElementPtrInst *GEP, const DataLayout &DL, 1773 uint64_t CurrentLocOps, 1774 SmallVectorImpl<uint64_t> &Opcodes, 1775 SmallVectorImpl<Value *> &AdditionalValues) { 1776 unsigned BitWidth = DL.getIndexSizeInBits(GEP->getPointerAddressSpace()); 1777 // Rewrite a GEP into a DIExpression. 1778 SmallDenseMap<Value *, APInt, 8> VariableOffsets; 1779 APInt ConstantOffset(BitWidth, 0); 1780 if (!GEP->collectOffset(DL, BitWidth, VariableOffsets, ConstantOffset)) 1781 return false; 1782 if (!VariableOffsets.empty() && !CurrentLocOps) { 1783 Opcodes.insert(Opcodes.begin(), {dwarf::DW_OP_LLVM_arg, 0}); 1784 CurrentLocOps = 1; 1785 } 1786 for (auto Offset : VariableOffsets) { 1787 AdditionalValues.push_back(Offset.first); 1788 assert(Offset.second.isStrictlyPositive() && 1789 "Expected strictly positive multiplier for offset."); 1790 Opcodes.append({dwarf::DW_OP_LLVM_arg, CurrentLocOps++, dwarf::DW_OP_constu, 1791 Offset.second.getZExtValue(), dwarf::DW_OP_mul, 1792 dwarf::DW_OP_plus}); 1793 } 1794 DIExpression::appendOffset(Opcodes, ConstantOffset.getSExtValue()); 1795 return true; 1796} 1797 1798uint64_t getDwarfOpForBinOp(Instruction::BinaryOps Opcode) { 1799 switch (Opcode) { 1800 case Instruction::Add: 1801 return dwarf::DW_OP_plus; 1802 case Instruction::Sub: 1803 return dwarf::DW_OP_minus; 1804 case Instruction::Mul: 1805 return dwarf::DW_OP_mul; 1806 case Instruction::SDiv: 1807 return dwarf::DW_OP_div; 1808 case Instruction::SRem: 1809 return dwarf::DW_OP_mod; 1810 case Instruction::Or: 1811 return dwarf::DW_OP_or; 1812 case Instruction::And: 1813 return dwarf::DW_OP_and; 1814 case Instruction::Xor: 1815 return dwarf::DW_OP_xor; 1816 case Instruction::Shl: 1817 return dwarf::DW_OP_shl; 1818 case Instruction::LShr: 1819 return dwarf::DW_OP_shr; 1820 case Instruction::AShr: 1821 return dwarf::DW_OP_shra; 1822 default: 1823 // TODO: Salvage from each kind of binop we know about. 1824 return 0; 1825 } 1826} 1827 1828bool getSalvageOpsForBinOp(BinaryOperator *BI, uint64_t CurrentLocOps, 1829 SmallVectorImpl<uint64_t> &Opcodes, 1830 SmallVectorImpl<Value *> &AdditionalValues) { 1831 // Handle binary operations with constant integer operands as a special case. 1832 auto *ConstInt = dyn_cast<ConstantInt>(BI->getOperand(1)); 1833 // Values wider than 64 bits cannot be represented within a DIExpression. 1834 if (ConstInt && ConstInt->getBitWidth() > 64) 1835 return false; 1836 1837 Instruction::BinaryOps BinOpcode = BI->getOpcode(); 1838 // Push any Constant Int operand onto the expression stack. 1839 if (ConstInt) { 1840 uint64_t Val = ConstInt->getSExtValue(); 1841 // Add or Sub Instructions with a constant operand can potentially be 1842 // simplified. 1843 if (BinOpcode == Instruction::Add || BinOpcode == Instruction::Sub) { 1844 uint64_t Offset = BinOpcode == Instruction::Add ? Val : -int64_t(Val); 1845 DIExpression::appendOffset(Opcodes, Offset); 1846 return true; 1847 } 1848 Opcodes.append({dwarf::DW_OP_constu, Val}); 1849 } else { 1850 if (!CurrentLocOps) { 1851 Opcodes.append({dwarf::DW_OP_LLVM_arg, 0}); 1852 CurrentLocOps = 1; 1853 } 1854 Opcodes.append({dwarf::DW_OP_LLVM_arg, CurrentLocOps}); 1855 AdditionalValues.push_back(BI->getOperand(1)); 1856 } 1857 1858 // Add salvaged binary operator to expression stack, if it has a valid 1859 // representation in a DIExpression. 1860 uint64_t DwarfBinOp = getDwarfOpForBinOp(BinOpcode); 1861 if (!DwarfBinOp) 1862 return false; 1863 Opcodes.push_back(DwarfBinOp); 1864 1865 return true; 1866} 1867 1868DIExpression * 1869llvm::salvageDebugInfoImpl(Instruction &I, DIExpression *SrcDIExpr, 1870 bool WithStackValue, unsigned LocNo, 1871 SmallVectorImpl<Value *> &AdditionalValues) { 1872 uint64_t CurrentLocOps = SrcDIExpr->getNumLocationOperands(); 1873 auto &M = *I.getModule(); 1874 auto &DL = M.getDataLayout(); 1875 1876 // Apply a vector of opcodes to the source DIExpression. 1877 auto doSalvage = [&](SmallVectorImpl<uint64_t> &Ops) -> DIExpression * { 1878 DIExpression *DIExpr = SrcDIExpr; 1879 if (!Ops.empty()) { 1880 DIExpr = DIExpression::appendOpsToArg(DIExpr, Ops, LocNo, WithStackValue); 1881 } 1882 return DIExpr; 1883 }; 1884 1885 // initializer-list helper for applying operators to the source DIExpression. 1886 auto applyOps = [&](ArrayRef<uint64_t> Opcodes) { 1887 SmallVector<uint64_t, 8> Ops(Opcodes.begin(), Opcodes.end()); 1888 return doSalvage(Ops); 1889 }; 1890 1891 if (auto *CI = dyn_cast<CastInst>(&I)) { 1892 // No-op casts are irrelevant for debug info. 1893 if (CI->isNoopCast(DL)) 1894 return SrcDIExpr; 1895 1896 Type *Type = CI->getType(); 1897 // Casts other than Trunc, SExt, or ZExt to scalar types cannot be salvaged. 1898 if (Type->isVectorTy() || 1899 !(isa<TruncInst>(&I) || isa<SExtInst>(&I) || isa<ZExtInst>(&I))) 1900 return nullptr; 1901 1902 Value *FromValue = CI->getOperand(0); 1903 unsigned FromTypeBitSize = FromValue->getType()->getScalarSizeInBits(); 1904 unsigned ToTypeBitSize = Type->getScalarSizeInBits(); 1905 1906 return applyOps(DIExpression::getExtOps(FromTypeBitSize, ToTypeBitSize, 1907 isa<SExtInst>(&I))); 1908 } 1909 1910 SmallVector<uint64_t, 8> Ops; 1911 if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) { 1912 if (getSalvageOpsForGEP(GEP, DL, CurrentLocOps, Ops, AdditionalValues)) 1913 return doSalvage(Ops); 1914 } else if (auto *BI = dyn_cast<BinaryOperator>(&I)) { 1915 if (getSalvageOpsForBinOp(BI, CurrentLocOps, Ops, AdditionalValues)) 1916 return doSalvage(Ops); 1917 } 1918 // *Not* to do: we should not attempt to salvage load instructions, 1919 // because the validity and lifetime of a dbg.value containing 1920 // DW_OP_deref becomes difficult to analyze. See PR40628 for examples. 1921 return nullptr; 1922} 1923 1924/// A replacement for a dbg.value expression. 1925using DbgValReplacement = Optional<DIExpression *>; 1926 1927/// Point debug users of \p From to \p To using exprs given by \p RewriteExpr, 1928/// possibly moving/undefing users to prevent use-before-def. Returns true if 1929/// changes are made. 1930static bool rewriteDebugUsers( 1931 Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT, 1932 function_ref<DbgValReplacement(DbgVariableIntrinsic &DII)> RewriteExpr) { 1933 // Find debug users of From. 1934 SmallVector<DbgVariableIntrinsic *, 1> Users; 1935 findDbgUsers(Users, &From); 1936 if (Users.empty()) 1937 return false; 1938 1939 // Prevent use-before-def of To. 1940 bool Changed = false; 1941 SmallPtrSet<DbgVariableIntrinsic *, 1> UndefOrSalvage; 1942 if (isa<Instruction>(&To)) { 1943 bool DomPointAfterFrom = From.getNextNonDebugInstruction() == &DomPoint; 1944 1945 for (auto *DII : Users) { 1946 // It's common to see a debug user between From and DomPoint. Move it 1947 // after DomPoint to preserve the variable update without any reordering. 1948 if (DomPointAfterFrom && DII->getNextNonDebugInstruction() == &DomPoint) { 1949 LLVM_DEBUG(dbgs() << "MOVE: " << *DII << '\n'); 1950 DII->moveAfter(&DomPoint); 1951 Changed = true; 1952 1953 // Users which otherwise aren't dominated by the replacement value must 1954 // be salvaged or deleted. 1955 } else if (!DT.dominates(&DomPoint, DII)) { 1956 UndefOrSalvage.insert(DII); 1957 } 1958 } 1959 } 1960 1961 // Update debug users without use-before-def risk. 1962 for (auto *DII : Users) { 1963 if (UndefOrSalvage.count(DII)) 1964 continue; 1965 1966 DbgValReplacement DVR = RewriteExpr(*DII); 1967 if (!DVR) 1968 continue; 1969 1970 DII->replaceVariableLocationOp(&From, &To); 1971 DII->setExpression(*DVR); 1972 LLVM_DEBUG(dbgs() << "REWRITE: " << *DII << '\n'); 1973 Changed = true; 1974 } 1975 1976 if (!UndefOrSalvage.empty()) { 1977 // Try to salvage the remaining debug users. 1978 salvageDebugInfo(From); 1979 Changed = true; 1980 } 1981 1982 return Changed; 1983} 1984 1985/// Check if a bitcast between a value of type \p FromTy to type \p ToTy would 1986/// losslessly preserve the bits and semantics of the value. This predicate is 1987/// symmetric, i.e swapping \p FromTy and \p ToTy should give the same result. 1988/// 1989/// Note that Type::canLosslesslyBitCastTo is not suitable here because it 1990/// allows semantically unequivalent bitcasts, such as <2 x i64> -> <4 x i32>, 1991/// and also does not allow lossless pointer <-> integer conversions. 1992static bool isBitCastSemanticsPreserving(const DataLayout &DL, Type *FromTy, 1993 Type *ToTy) { 1994 // Trivially compatible types. 1995 if (FromTy == ToTy) 1996 return true; 1997 1998 // Handle compatible pointer <-> integer conversions. 1999 if (FromTy->isIntOrPtrTy() && ToTy->isIntOrPtrTy()) { 2000 bool SameSize = DL.getTypeSizeInBits(FromTy) == DL.getTypeSizeInBits(ToTy); 2001 bool LosslessConversion = !DL.isNonIntegralPointerType(FromTy) && 2002 !DL.isNonIntegralPointerType(ToTy); 2003 return SameSize && LosslessConversion; 2004 } 2005 2006 // TODO: This is not exhaustive. 2007 return false; 2008} 2009 2010bool llvm::replaceAllDbgUsesWith(Instruction &From, Value &To, 2011 Instruction &DomPoint, DominatorTree &DT) { 2012 // Exit early if From has no debug users. 2013 if (!From.isUsedByMetadata()) 2014 return false; 2015 2016 assert(&From != &To && "Can't replace something with itself"); 2017 2018 Type *FromTy = From.getType(); 2019 Type *ToTy = To.getType(); 2020 2021 auto Identity = [&](DbgVariableIntrinsic &DII) -> DbgValReplacement { 2022 return DII.getExpression(); 2023 }; 2024 2025 // Handle no-op conversions. 2026 Module &M = *From.getModule(); 2027 const DataLayout &DL = M.getDataLayout(); 2028 if (isBitCastSemanticsPreserving(DL, FromTy, ToTy)) 2029 return rewriteDebugUsers(From, To, DomPoint, DT, Identity); 2030 2031 // Handle integer-to-integer widening and narrowing. 2032 // FIXME: Use DW_OP_convert when it's available everywhere. 2033 if (FromTy->isIntegerTy() && ToTy->isIntegerTy()) { 2034 uint64_t FromBits = FromTy->getPrimitiveSizeInBits(); 2035 uint64_t ToBits = ToTy->getPrimitiveSizeInBits(); 2036 assert(FromBits != ToBits && "Unexpected no-op conversion"); 2037 2038 // When the width of the result grows, assume that a debugger will only 2039 // access the low `FromBits` bits when inspecting the source variable. 2040 if (FromBits < ToBits) 2041 return rewriteDebugUsers(From, To, DomPoint, DT, Identity); 2042 2043 // The width of the result has shrunk. Use sign/zero extension to describe 2044 // the source variable's high bits. 2045 auto SignOrZeroExt = [&](DbgVariableIntrinsic &DII) -> DbgValReplacement { 2046 DILocalVariable *Var = DII.getVariable(); 2047 2048 // Without knowing signedness, sign/zero extension isn't possible. 2049 auto Signedness = Var->getSignedness(); 2050 if (!Signedness) 2051 return None; 2052 2053 bool Signed = *Signedness == DIBasicType::Signedness::Signed; 2054 return DIExpression::appendExt(DII.getExpression(), ToBits, FromBits, 2055 Signed); 2056 }; 2057 return rewriteDebugUsers(From, To, DomPoint, DT, SignOrZeroExt); 2058 } 2059 2060 // TODO: Floating-point conversions, vectors. 2061 return false; 2062} 2063 2064std::pair<unsigned, unsigned> 2065llvm::removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB) { 2066 unsigned NumDeadInst = 0; 2067 unsigned NumDeadDbgInst = 0; 2068 // Delete the instructions backwards, as it has a reduced likelihood of 2069 // having to update as many def-use and use-def chains. 2070 Instruction *EndInst = BB->getTerminator(); // Last not to be deleted. 2071 while (EndInst != &BB->front()) { 2072 // Delete the next to last instruction. 2073 Instruction *Inst = &*--EndInst->getIterator(); 2074 if (!Inst->use_empty() && !Inst->getType()->isTokenTy()) 2075 Inst->replaceAllUsesWith(UndefValue::get(Inst->getType())); 2076 if (Inst->isEHPad() || Inst->getType()->isTokenTy()) { 2077 EndInst = Inst; 2078 continue; 2079 } 2080 if (isa<DbgInfoIntrinsic>(Inst)) 2081 ++NumDeadDbgInst; 2082 else 2083 ++NumDeadInst; 2084 Inst->eraseFromParent(); 2085 } 2086 return {NumDeadInst, NumDeadDbgInst}; 2087} 2088 2089unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap, 2090 bool PreserveLCSSA, DomTreeUpdater *DTU, 2091 MemorySSAUpdater *MSSAU) { 2092 BasicBlock *BB = I->getParent(); 2093 2094 if (MSSAU) 2095 MSSAU->changeToUnreachable(I); 2096 2097 SmallSet<BasicBlock *, 8> UniqueSuccessors; 2098 2099 // Loop over all of the successors, removing BB's entry from any PHI 2100 // nodes. 2101 for (BasicBlock *Successor : successors(BB)) { 2102 Successor->removePredecessor(BB, PreserveLCSSA); 2103 if (DTU) 2104 UniqueSuccessors.insert(Successor); 2105 } 2106 // Insert a call to llvm.trap right before this. This turns the undefined 2107 // behavior into a hard fail instead of falling through into random code. 2108 if (UseLLVMTrap) { 2109 Function *TrapFn = 2110 Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap); 2111 CallInst *CallTrap = CallInst::Create(TrapFn, "", I); 2112 CallTrap->setDebugLoc(I->getDebugLoc()); 2113 } 2114 auto *UI = new UnreachableInst(I->getContext(), I); 2115 UI->setDebugLoc(I->getDebugLoc()); 2116 2117 // All instructions after this are dead. 2118 unsigned NumInstrsRemoved = 0; 2119 BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end(); 2120 while (BBI != BBE) { 2121 if (!BBI->use_empty()) 2122 BBI->replaceAllUsesWith(UndefValue::get(BBI->getType())); 2123 BB->getInstList().erase(BBI++); 2124 ++NumInstrsRemoved; 2125 } 2126 if (DTU) { 2127 SmallVector<DominatorTree::UpdateType, 8> Updates; 2128 Updates.reserve(UniqueSuccessors.size()); 2129 for (BasicBlock *UniqueSuccessor : UniqueSuccessors) 2130 Updates.push_back({DominatorTree::Delete, BB, UniqueSuccessor}); 2131 DTU->applyUpdates(Updates); 2132 } 2133 return NumInstrsRemoved; 2134} 2135 2136CallInst *llvm::createCallMatchingInvoke(InvokeInst *II) { 2137 SmallVector<Value *, 8> Args(II->args()); 2138 SmallVector<OperandBundleDef, 1> OpBundles; 2139 II->getOperandBundlesAsDefs(OpBundles); 2140 CallInst *NewCall = CallInst::Create(II->getFunctionType(), 2141 II->getCalledOperand(), Args, OpBundles); 2142 NewCall->setCallingConv(II->getCallingConv()); 2143 NewCall->setAttributes(II->getAttributes()); 2144 NewCall->setDebugLoc(II->getDebugLoc()); 2145 NewCall->copyMetadata(*II); 2146 2147 // If the invoke had profile metadata, try converting them for CallInst. 2148 uint64_t TotalWeight; 2149 if (NewCall->extractProfTotalWeight(TotalWeight)) { 2150 // Set the total weight if it fits into i32, otherwise reset. 2151 MDBuilder MDB(NewCall->getContext()); 2152 auto NewWeights = uint32_t(TotalWeight) != TotalWeight 2153 ? nullptr 2154 : MDB.createBranchWeights({uint32_t(TotalWeight)}); 2155 NewCall->setMetadata(LLVMContext::MD_prof, NewWeights); 2156 } 2157 2158 return NewCall; 2159} 2160 2161/// changeToCall - Convert the specified invoke into a normal call. 2162void llvm::changeToCall(InvokeInst *II, DomTreeUpdater *DTU) { 2163 CallInst *NewCall = createCallMatchingInvoke(II); 2164 NewCall->takeName(II); 2165 NewCall->insertBefore(II); 2166 II->replaceAllUsesWith(NewCall); 2167 2168 // Follow the call by a branch to the normal destination. 2169 BasicBlock *NormalDestBB = II->getNormalDest(); 2170 BranchInst::Create(NormalDestBB, II); 2171 2172 // Update PHI nodes in the unwind destination 2173 BasicBlock *BB = II->getParent(); 2174 BasicBlock *UnwindDestBB = II->getUnwindDest(); 2175 UnwindDestBB->removePredecessor(BB); 2176 II->eraseFromParent(); 2177 if (DTU) 2178 DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}}); 2179} 2180 2181BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI, 2182 BasicBlock *UnwindEdge, 2183 DomTreeUpdater *DTU) { 2184 BasicBlock *BB = CI->getParent(); 2185 2186 // Convert this function call into an invoke instruction. First, split the 2187 // basic block. 2188 BasicBlock *Split = SplitBlock(BB, CI, DTU, /*LI=*/nullptr, /*MSSAU*/ nullptr, 2189 CI->getName() + ".noexc"); 2190 2191 // Delete the unconditional branch inserted by SplitBlock 2192 BB->getInstList().pop_back(); 2193 2194 // Create the new invoke instruction. 2195 SmallVector<Value *, 8> InvokeArgs(CI->args()); 2196 SmallVector<OperandBundleDef, 1> OpBundles; 2197 2198 CI->getOperandBundlesAsDefs(OpBundles); 2199 2200 // Note: we're round tripping operand bundles through memory here, and that 2201 // can potentially be avoided with a cleverer API design that we do not have 2202 // as of this time. 2203 2204 InvokeInst *II = 2205 InvokeInst::Create(CI->getFunctionType(), CI->getCalledOperand(), Split, 2206 UnwindEdge, InvokeArgs, OpBundles, CI->getName(), BB); 2207 II->setDebugLoc(CI->getDebugLoc()); 2208 II->setCallingConv(CI->getCallingConv()); 2209 II->setAttributes(CI->getAttributes()); 2210 2211 if (DTU) 2212 DTU->applyUpdates({{DominatorTree::Insert, BB, UnwindEdge}}); 2213 2214 // Make sure that anything using the call now uses the invoke! This also 2215 // updates the CallGraph if present, because it uses a WeakTrackingVH. 2216 CI->replaceAllUsesWith(II); 2217 2218 // Delete the original call 2219 Split->getInstList().pop_front(); 2220 return Split; 2221} 2222 2223static bool markAliveBlocks(Function &F, 2224 SmallPtrSetImpl<BasicBlock *> &Reachable, 2225 DomTreeUpdater *DTU = nullptr) { 2226 SmallVector<BasicBlock*, 128> Worklist; 2227 BasicBlock *BB = &F.front(); 2228 Worklist.push_back(BB); 2229 Reachable.insert(BB); 2230 bool Changed = false; 2231 do { 2232 BB = Worklist.pop_back_val(); 2233 2234 // Do a quick scan of the basic block, turning any obviously unreachable 2235 // instructions into LLVM unreachable insts. The instruction combining pass 2236 // canonicalizes unreachable insts into stores to null or undef. 2237 for (Instruction &I : *BB) { 2238 if (auto *CI = dyn_cast<CallInst>(&I)) { 2239 Value *Callee = CI->getCalledOperand(); 2240 // Handle intrinsic calls. 2241 if (Function *F = dyn_cast<Function>(Callee)) { 2242 auto IntrinsicID = F->getIntrinsicID(); 2243 // Assumptions that are known to be false are equivalent to 2244 // unreachable. Also, if the condition is undefined, then we make the 2245 // choice most beneficial to the optimizer, and choose that to also be 2246 // unreachable. 2247 if (IntrinsicID == Intrinsic::assume) { 2248 if (match(CI->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) { 2249 // Don't insert a call to llvm.trap right before the unreachable. 2250 changeToUnreachable(CI, false, false, DTU); 2251 Changed = true; 2252 break; 2253 } 2254 } else if (IntrinsicID == Intrinsic::experimental_guard) { 2255 // A call to the guard intrinsic bails out of the current 2256 // compilation unit if the predicate passed to it is false. If the 2257 // predicate is a constant false, then we know the guard will bail 2258 // out of the current compile unconditionally, so all code following 2259 // it is dead. 2260 // 2261 // Note: unlike in llvm.assume, it is not "obviously profitable" for 2262 // guards to treat `undef` as `false` since a guard on `undef` can 2263 // still be useful for widening. 2264 if (match(CI->getArgOperand(0), m_Zero())) 2265 if (!isa<UnreachableInst>(CI->getNextNode())) { 2266 changeToUnreachable(CI->getNextNode(), /*UseLLVMTrap=*/false, 2267 false, DTU); 2268 Changed = true; 2269 break; 2270 } 2271 } 2272 } else if ((isa<ConstantPointerNull>(Callee) && 2273 !NullPointerIsDefined(CI->getFunction())) || 2274 isa<UndefValue>(Callee)) { 2275 changeToUnreachable(CI, /*UseLLVMTrap=*/false, false, DTU); 2276 Changed = true; 2277 break; 2278 } 2279 if (CI->doesNotReturn() && !CI->isMustTailCall()) { 2280 // If we found a call to a no-return function, insert an unreachable 2281 // instruction after it. Make sure there isn't *already* one there 2282 // though. 2283 if (!isa<UnreachableInst>(CI->getNextNode())) { 2284 // Don't insert a call to llvm.trap right before the unreachable. 2285 changeToUnreachable(CI->getNextNode(), false, false, DTU); 2286 Changed = true; 2287 } 2288 break; 2289 } 2290 } else if (auto *SI = dyn_cast<StoreInst>(&I)) { 2291 // Store to undef and store to null are undefined and used to signal 2292 // that they should be changed to unreachable by passes that can't 2293 // modify the CFG. 2294 2295 // Don't touch volatile stores. 2296 if (SI->isVolatile()) continue; 2297 2298 Value *Ptr = SI->getOperand(1); 2299 2300 if (isa<UndefValue>(Ptr) || 2301 (isa<ConstantPointerNull>(Ptr) && 2302 !NullPointerIsDefined(SI->getFunction(), 2303 SI->getPointerAddressSpace()))) { 2304 changeToUnreachable(SI, true, false, DTU); 2305 Changed = true; 2306 break; 2307 } 2308 } 2309 } 2310 2311 Instruction *Terminator = BB->getTerminator(); 2312 if (auto *II = dyn_cast<InvokeInst>(Terminator)) { 2313 // Turn invokes that call 'nounwind' functions into ordinary calls. 2314 Value *Callee = II->getCalledOperand(); 2315 if ((isa<ConstantPointerNull>(Callee) && 2316 !NullPointerIsDefined(BB->getParent())) || 2317 isa<UndefValue>(Callee)) { 2318 changeToUnreachable(II, true, false, DTU); 2319 Changed = true; 2320 } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) { 2321 if (II->use_empty() && II->onlyReadsMemory()) { 2322 // jump to the normal destination branch. 2323 BasicBlock *NormalDestBB = II->getNormalDest(); 2324 BasicBlock *UnwindDestBB = II->getUnwindDest(); 2325 BranchInst::Create(NormalDestBB, II); 2326 UnwindDestBB->removePredecessor(II->getParent()); 2327 II->eraseFromParent(); 2328 if (DTU) 2329 DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}}); 2330 } else 2331 changeToCall(II, DTU); 2332 Changed = true; 2333 } 2334 } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) { 2335 // Remove catchpads which cannot be reached. 2336 struct CatchPadDenseMapInfo { 2337 static CatchPadInst *getEmptyKey() { 2338 return DenseMapInfo<CatchPadInst *>::getEmptyKey(); 2339 } 2340 2341 static CatchPadInst *getTombstoneKey() { 2342 return DenseMapInfo<CatchPadInst *>::getTombstoneKey(); 2343 } 2344 2345 static unsigned getHashValue(CatchPadInst *CatchPad) { 2346 return static_cast<unsigned>(hash_combine_range( 2347 CatchPad->value_op_begin(), CatchPad->value_op_end())); 2348 } 2349 2350 static bool isEqual(CatchPadInst *LHS, CatchPadInst *RHS) { 2351 if (LHS == getEmptyKey() || LHS == getTombstoneKey() || 2352 RHS == getEmptyKey() || RHS == getTombstoneKey()) 2353 return LHS == RHS; 2354 return LHS->isIdenticalTo(RHS); 2355 } 2356 }; 2357 2358 SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases; 2359 // Set of unique CatchPads. 2360 SmallDenseMap<CatchPadInst *, detail::DenseSetEmpty, 4, 2361 CatchPadDenseMapInfo, detail::DenseSetPair<CatchPadInst *>> 2362 HandlerSet; 2363 detail::DenseSetEmpty Empty; 2364 for (CatchSwitchInst::handler_iterator I = CatchSwitch->handler_begin(), 2365 E = CatchSwitch->handler_end(); 2366 I != E; ++I) { 2367 BasicBlock *HandlerBB = *I; 2368 if (DTU) 2369 ++NumPerSuccessorCases[HandlerBB]; 2370 auto *CatchPad = cast<CatchPadInst>(HandlerBB->getFirstNonPHI()); 2371 if (!HandlerSet.insert({CatchPad, Empty}).second) { 2372 if (DTU) 2373 --NumPerSuccessorCases[HandlerBB]; 2374 CatchSwitch->removeHandler(I); 2375 --I; 2376 --E; 2377 Changed = true; 2378 } 2379 } 2380 if (DTU) { 2381 std::vector<DominatorTree::UpdateType> Updates; 2382 for (const std::pair<BasicBlock *, int> &I : NumPerSuccessorCases) 2383 if (I.second == 0) 2384 Updates.push_back({DominatorTree::Delete, BB, I.first}); 2385 DTU->applyUpdates(Updates); 2386 } 2387 } 2388 2389 Changed |= ConstantFoldTerminator(BB, true, nullptr, DTU); 2390 for (BasicBlock *Successor : successors(BB)) 2391 if (Reachable.insert(Successor).second) 2392 Worklist.push_back(Successor); 2393 } while (!Worklist.empty()); 2394 return Changed; 2395} 2396 2397void llvm::removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU) { 2398 Instruction *TI = BB->getTerminator(); 2399 2400 if (auto *II = dyn_cast<InvokeInst>(TI)) { 2401 changeToCall(II, DTU); 2402 return; 2403 } 2404 2405 Instruction *NewTI; 2406 BasicBlock *UnwindDest; 2407 2408 if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) { 2409 NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI); 2410 UnwindDest = CRI->getUnwindDest(); 2411 } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) { 2412 auto *NewCatchSwitch = CatchSwitchInst::Create( 2413 CatchSwitch->getParentPad(), nullptr, CatchSwitch->getNumHandlers(), 2414 CatchSwitch->getName(), CatchSwitch); 2415 for (BasicBlock *PadBB : CatchSwitch->handlers()) 2416 NewCatchSwitch->addHandler(PadBB); 2417 2418 NewTI = NewCatchSwitch; 2419 UnwindDest = CatchSwitch->getUnwindDest(); 2420 } else { 2421 llvm_unreachable("Could not find unwind successor"); 2422 } 2423 2424 NewTI->takeName(TI); 2425 NewTI->setDebugLoc(TI->getDebugLoc()); 2426 UnwindDest->removePredecessor(BB); 2427 TI->replaceAllUsesWith(NewTI); 2428 TI->eraseFromParent(); 2429 if (DTU) 2430 DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDest}}); 2431} 2432 2433/// removeUnreachableBlocks - Remove blocks that are not reachable, even 2434/// if they are in a dead cycle. Return true if a change was made, false 2435/// otherwise. 2436bool llvm::removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU, 2437 MemorySSAUpdater *MSSAU) { 2438 SmallPtrSet<BasicBlock *, 16> Reachable; 2439 bool Changed = markAliveBlocks(F, Reachable, DTU); 2440 2441 // If there are unreachable blocks in the CFG... 2442 if (Reachable.size() == F.size()) 2443 return Changed; 2444 2445 assert(Reachable.size() < F.size()); 2446 2447 // Are there any blocks left to actually delete? 2448 SmallSetVector<BasicBlock *, 8> BlocksToRemove; 2449 for (BasicBlock &BB : F) { 2450 // Skip reachable basic blocks 2451 if (Reachable.count(&BB)) 2452 continue; 2453 // Skip already-deleted blocks 2454 if (DTU && DTU->isBBPendingDeletion(&BB)) 2455 continue; 2456 BlocksToRemove.insert(&BB); 2457 } 2458 2459 if (BlocksToRemove.empty()) 2460 return Changed; 2461 2462 Changed = true; 2463 NumRemoved += BlocksToRemove.size(); 2464 2465 if (MSSAU) 2466 MSSAU->removeBlocks(BlocksToRemove); 2467 2468 DeleteDeadBlocks(BlocksToRemove.takeVector(), DTU); 2469 2470 return Changed; 2471} 2472 2473void llvm::combineMetadata(Instruction *K, const Instruction *J, 2474 ArrayRef<unsigned> KnownIDs, bool DoesKMove) { 2475 SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata; 2476 K->dropUnknownNonDebugMetadata(KnownIDs); 2477 K->getAllMetadataOtherThanDebugLoc(Metadata); 2478 for (const auto &MD : Metadata) { 2479 unsigned Kind = MD.first; 2480 MDNode *JMD = J->getMetadata(Kind); 2481 MDNode *KMD = MD.second; 2482 2483 switch (Kind) { 2484 default: 2485 K->setMetadata(Kind, nullptr); // Remove unknown metadata 2486 break; 2487 case LLVMContext::MD_dbg: 2488 llvm_unreachable("getAllMetadataOtherThanDebugLoc returned a MD_dbg"); 2489 case LLVMContext::MD_tbaa: 2490 K->setMetadata(Kind, MDNode::getMostGenericTBAA(JMD, KMD)); 2491 break; 2492 case LLVMContext::MD_alias_scope: 2493 K->setMetadata(Kind, MDNode::getMostGenericAliasScope(JMD, KMD)); 2494 break; 2495 case LLVMContext::MD_noalias: 2496 case LLVMContext::MD_mem_parallel_loop_access: 2497 K->setMetadata(Kind, MDNode::intersect(JMD, KMD)); 2498 break; 2499 case LLVMContext::MD_access_group: 2500 K->setMetadata(LLVMContext::MD_access_group, 2501 intersectAccessGroups(K, J)); 2502 break; 2503 case LLVMContext::MD_range: 2504 2505 // If K does move, use most generic range. Otherwise keep the range of 2506 // K. 2507 if (DoesKMove) 2508 // FIXME: If K does move, we should drop the range info and nonnull. 2509 // Currently this function is used with DoesKMove in passes 2510 // doing hoisting/sinking and the current behavior of using the 2511 // most generic range is correct in those cases. 2512 K->setMetadata(Kind, MDNode::getMostGenericRange(JMD, KMD)); 2513 break; 2514 case LLVMContext::MD_fpmath: 2515 K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD)); 2516 break; 2517 case LLVMContext::MD_invariant_load: 2518 // Only set the !invariant.load if it is present in both instructions. 2519 K->setMetadata(Kind, JMD); 2520 break; 2521 case LLVMContext::MD_nonnull: 2522 // If K does move, keep nonull if it is present in both instructions. 2523 if (DoesKMove) 2524 K->setMetadata(Kind, JMD); 2525 break; 2526 case LLVMContext::MD_invariant_group: 2527 // Preserve !invariant.group in K. 2528 break; 2529 case LLVMContext::MD_align: 2530 K->setMetadata(Kind, 2531 MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD)); 2532 break; 2533 case LLVMContext::MD_dereferenceable: 2534 case LLVMContext::MD_dereferenceable_or_null: 2535 K->setMetadata(Kind, 2536 MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD)); 2537 break; 2538 case LLVMContext::MD_preserve_access_index: 2539 // Preserve !preserve.access.index in K. 2540 break; 2541 } 2542 } 2543 // Set !invariant.group from J if J has it. If both instructions have it 2544 // then we will just pick it from J - even when they are different. 2545 // Also make sure that K is load or store - f.e. combining bitcast with load 2546 // could produce bitcast with invariant.group metadata, which is invalid. 2547 // FIXME: we should try to preserve both invariant.group md if they are 2548 // different, but right now instruction can only have one invariant.group. 2549 if (auto *JMD = J->getMetadata(LLVMContext::MD_invariant_group)) 2550 if (isa<LoadInst>(K) || isa<StoreInst>(K)) 2551 K->setMetadata(LLVMContext::MD_invariant_group, JMD); 2552} 2553 2554void llvm::combineMetadataForCSE(Instruction *K, const Instruction *J, 2555 bool KDominatesJ) { 2556 unsigned KnownIDs[] = { 2557 LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope, 2558 LLVMContext::MD_noalias, LLVMContext::MD_range, 2559 LLVMContext::MD_invariant_load, LLVMContext::MD_nonnull, 2560 LLVMContext::MD_invariant_group, LLVMContext::MD_align, 2561 LLVMContext::MD_dereferenceable, 2562 LLVMContext::MD_dereferenceable_or_null, 2563 LLVMContext::MD_access_group, LLVMContext::MD_preserve_access_index}; 2564 combineMetadata(K, J, KnownIDs, KDominatesJ); 2565} 2566 2567void llvm::copyMetadataForLoad(LoadInst &Dest, const LoadInst &Source) { 2568 SmallVector<std::pair<unsigned, MDNode *>, 8> MD; 2569 Source.getAllMetadata(MD); 2570 MDBuilder MDB(Dest.getContext()); 2571 Type *NewType = Dest.getType(); 2572 const DataLayout &DL = Source.getModule()->getDataLayout(); 2573 for (const auto &MDPair : MD) { 2574 unsigned ID = MDPair.first; 2575 MDNode *N = MDPair.second; 2576 // Note, essentially every kind of metadata should be preserved here! This 2577 // routine is supposed to clone a load instruction changing *only its type*. 2578 // The only metadata it makes sense to drop is metadata which is invalidated 2579 // when the pointer type changes. This should essentially never be the case 2580 // in LLVM, but we explicitly switch over only known metadata to be 2581 // conservatively correct. If you are adding metadata to LLVM which pertains 2582 // to loads, you almost certainly want to add it here. 2583 switch (ID) { 2584 case LLVMContext::MD_dbg: 2585 case LLVMContext::MD_tbaa: 2586 case LLVMContext::MD_prof: 2587 case LLVMContext::MD_fpmath: 2588 case LLVMContext::MD_tbaa_struct: 2589 case LLVMContext::MD_invariant_load: 2590 case LLVMContext::MD_alias_scope: 2591 case LLVMContext::MD_noalias: 2592 case LLVMContext::MD_nontemporal: 2593 case LLVMContext::MD_mem_parallel_loop_access: 2594 case LLVMContext::MD_access_group: 2595 // All of these directly apply. 2596 Dest.setMetadata(ID, N); 2597 break; 2598 2599 case LLVMContext::MD_nonnull: 2600 copyNonnullMetadata(Source, N, Dest); 2601 break; 2602 2603 case LLVMContext::MD_align: 2604 case LLVMContext::MD_dereferenceable: 2605 case LLVMContext::MD_dereferenceable_or_null: 2606 // These only directly apply if the new type is also a pointer. 2607 if (NewType->isPointerTy()) 2608 Dest.setMetadata(ID, N); 2609 break; 2610 2611 case LLVMContext::MD_range: 2612 copyRangeMetadata(DL, Source, N, Dest); 2613 break; 2614 } 2615 } 2616} 2617 2618void llvm::patchReplacementInstruction(Instruction *I, Value *Repl) { 2619 auto *ReplInst = dyn_cast<Instruction>(Repl); 2620 if (!ReplInst) 2621 return; 2622 2623 // Patch the replacement so that it is not more restrictive than the value 2624 // being replaced. 2625 // Note that if 'I' is a load being replaced by some operation, 2626 // for example, by an arithmetic operation, then andIRFlags() 2627 // would just erase all math flags from the original arithmetic 2628 // operation, which is clearly not wanted and not needed. 2629 if (!isa<LoadInst>(I)) 2630 ReplInst->andIRFlags(I); 2631 2632 // FIXME: If both the original and replacement value are part of the 2633 // same control-flow region (meaning that the execution of one 2634 // guarantees the execution of the other), then we can combine the 2635 // noalias scopes here and do better than the general conservative 2636 // answer used in combineMetadata(). 2637 2638 // In general, GVN unifies expressions over different control-flow 2639 // regions, and so we need a conservative combination of the noalias 2640 // scopes. 2641 static const unsigned KnownIDs[] = { 2642 LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope, 2643 LLVMContext::MD_noalias, LLVMContext::MD_range, 2644 LLVMContext::MD_fpmath, LLVMContext::MD_invariant_load, 2645 LLVMContext::MD_invariant_group, LLVMContext::MD_nonnull, 2646 LLVMContext::MD_access_group, LLVMContext::MD_preserve_access_index}; 2647 combineMetadata(ReplInst, I, KnownIDs, false); 2648} 2649 2650template <typename RootType, typename DominatesFn> 2651static unsigned replaceDominatedUsesWith(Value *From, Value *To, 2652 const RootType &Root, 2653 const DominatesFn &Dominates) { 2654 assert(From->getType() == To->getType()); 2655 2656 unsigned Count = 0; 2657 for (Value::use_iterator UI = From->use_begin(), UE = From->use_end(); 2658 UI != UE;) { 2659 Use &U = *UI++; 2660 if (!Dominates(Root, U)) 2661 continue; 2662 U.set(To); 2663 LLVM_DEBUG(dbgs() << "Replace dominated use of '" << From->getName() 2664 << "' as " << *To << " in " << *U << "\n"); 2665 ++Count; 2666 } 2667 return Count; 2668} 2669 2670unsigned llvm::replaceNonLocalUsesWith(Instruction *From, Value *To) { 2671 assert(From->getType() == To->getType()); 2672 auto *BB = From->getParent(); 2673 unsigned Count = 0; 2674 2675 for (Value::use_iterator UI = From->use_begin(), UE = From->use_end(); 2676 UI != UE;) { 2677 Use &U = *UI++; 2678 auto *I = cast<Instruction>(U.getUser()); 2679 if (I->getParent() == BB) 2680 continue; 2681 U.set(To); 2682 ++Count; 2683 } 2684 return Count; 2685} 2686 2687unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To, 2688 DominatorTree &DT, 2689 const BasicBlockEdge &Root) { 2690 auto Dominates = [&DT](const BasicBlockEdge &Root, const Use &U) { 2691 return DT.dominates(Root, U); 2692 }; 2693 return ::replaceDominatedUsesWith(From, To, Root, Dominates); 2694} 2695 2696unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To, 2697 DominatorTree &DT, 2698 const BasicBlock *BB) { 2699 auto Dominates = [&DT](const BasicBlock *BB, const Use &U) { 2700 return DT.dominates(BB, U); 2701 }; 2702 return ::replaceDominatedUsesWith(From, To, BB, Dominates); 2703} 2704 2705bool llvm::callsGCLeafFunction(const CallBase *Call, 2706 const TargetLibraryInfo &TLI) { 2707 // Check if the function is specifically marked as a gc leaf function. 2708 if (Call->hasFnAttr("gc-leaf-function")) 2709 return true; 2710 if (const Function *F = Call->getCalledFunction()) { 2711 if (F->hasFnAttribute("gc-leaf-function")) 2712 return true; 2713 2714 if (auto IID = F->getIntrinsicID()) { 2715 // Most LLVM intrinsics do not take safepoints. 2716 return IID != Intrinsic::experimental_gc_statepoint && 2717 IID != Intrinsic::experimental_deoptimize && 2718 IID != Intrinsic::memcpy_element_unordered_atomic && 2719 IID != Intrinsic::memmove_element_unordered_atomic; 2720 } 2721 } 2722 2723 // Lib calls can be materialized by some passes, and won't be 2724 // marked as 'gc-leaf-function.' All available Libcalls are 2725 // GC-leaf. 2726 LibFunc LF; 2727 if (TLI.getLibFunc(*Call, LF)) { 2728 return TLI.has(LF); 2729 } 2730 2731 return false; 2732} 2733 2734void llvm::copyNonnullMetadata(const LoadInst &OldLI, MDNode *N, 2735 LoadInst &NewLI) { 2736 auto *NewTy = NewLI.getType(); 2737 2738 // This only directly applies if the new type is also a pointer. 2739 if (NewTy->isPointerTy()) { 2740 NewLI.setMetadata(LLVMContext::MD_nonnull, N); 2741 return; 2742 } 2743 2744 // The only other translation we can do is to integral loads with !range 2745 // metadata. 2746 if (!NewTy->isIntegerTy()) 2747 return; 2748 2749 MDBuilder MDB(NewLI.getContext()); 2750 const Value *Ptr = OldLI.getPointerOperand(); 2751 auto *ITy = cast<IntegerType>(NewTy); 2752 auto *NullInt = ConstantExpr::getPtrToInt( 2753 ConstantPointerNull::get(cast<PointerType>(Ptr->getType())), ITy); 2754 auto *NonNullInt = ConstantExpr::getAdd(NullInt, ConstantInt::get(ITy, 1)); 2755 NewLI.setMetadata(LLVMContext::MD_range, 2756 MDB.createRange(NonNullInt, NullInt)); 2757} 2758 2759void llvm::copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI, 2760 MDNode *N, LoadInst &NewLI) { 2761 auto *NewTy = NewLI.getType(); 2762 2763 // Give up unless it is converted to a pointer where there is a single very 2764 // valuable mapping we can do reliably. 2765 // FIXME: It would be nice to propagate this in more ways, but the type 2766 // conversions make it hard. 2767 if (!NewTy->isPointerTy()) 2768 return; 2769 2770 unsigned BitWidth = DL.getPointerTypeSizeInBits(NewTy); 2771 if (!getConstantRangeFromMetadata(*N).contains(APInt(BitWidth, 0))) { 2772 MDNode *NN = MDNode::get(OldLI.getContext(), None); 2773 NewLI.setMetadata(LLVMContext::MD_nonnull, NN); 2774 } 2775} 2776 2777void llvm::dropDebugUsers(Instruction &I) { 2778 SmallVector<DbgVariableIntrinsic *, 1> DbgUsers; 2779 findDbgUsers(DbgUsers, &I); 2780 for (auto *DII : DbgUsers) 2781 DII->eraseFromParent(); 2782} 2783 2784void llvm::hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, 2785 BasicBlock *BB) { 2786 // Since we are moving the instructions out of its basic block, we do not 2787 // retain their original debug locations (DILocations) and debug intrinsic 2788 // instructions. 2789 // 2790 // Doing so would degrade the debugging experience and adversely affect the 2791 // accuracy of profiling information. 2792 // 2793 // Currently, when hoisting the instructions, we take the following actions: 2794 // - Remove their debug intrinsic instructions. 2795 // - Set their debug locations to the values from the insertion point. 2796 // 2797 // As per PR39141 (comment #8), the more fundamental reason why the dbg.values 2798 // need to be deleted, is because there will not be any instructions with a 2799 // DILocation in either branch left after performing the transformation. We 2800 // can only insert a dbg.value after the two branches are joined again. 2801 // 2802 // See PR38762, PR39243 for more details. 2803 // 2804 // TODO: Extend llvm.dbg.value to take more than one SSA Value (PR39141) to 2805 // encode predicated DIExpressions that yield different results on different 2806 // code paths. 2807 2808 // A hoisted conditional probe should be treated as dangling so that it will 2809 // not be over-counted when the samples collected on the non-conditional path 2810 // are counted towards the conditional path. We leave it for the counts 2811 // inference algorithm to figure out a proper count for a danglng probe. 2812 moveAndDanglePseudoProbes(BB, InsertPt); 2813 2814 for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE;) { 2815 Instruction *I = &*II; 2816 I->dropUnknownNonDebugMetadata(); 2817 if (I->isUsedByMetadata()) 2818 dropDebugUsers(*I); 2819 if (isa<DbgInfoIntrinsic>(I)) { 2820 // Remove DbgInfo Intrinsics. 2821 II = I->eraseFromParent(); 2822 continue; 2823 } 2824 I->setDebugLoc(InsertPt->getDebugLoc()); 2825 ++II; 2826 } 2827 DomBlock->getInstList().splice(InsertPt->getIterator(), BB->getInstList(), 2828 BB->begin(), 2829 BB->getTerminator()->getIterator()); 2830} 2831 2832namespace { 2833 2834/// A potential constituent of a bitreverse or bswap expression. See 2835/// collectBitParts for a fuller explanation. 2836struct BitPart { 2837 BitPart(Value *P, unsigned BW) : Provider(P) { 2838 Provenance.resize(BW); 2839 } 2840 2841 /// The Value that this is a bitreverse/bswap of. 2842 Value *Provider; 2843 2844 /// The "provenance" of each bit. Provenance[A] = B means that bit A 2845 /// in Provider becomes bit B in the result of this expression. 2846 SmallVector<int8_t, 32> Provenance; // int8_t means max size is i128. 2847 2848 enum { Unset = -1 }; 2849}; 2850 2851} // end anonymous namespace 2852 2853/// Analyze the specified subexpression and see if it is capable of providing 2854/// pieces of a bswap or bitreverse. The subexpression provides a potential 2855/// piece of a bswap or bitreverse if it can be proved that each non-zero bit in 2856/// the output of the expression came from a corresponding bit in some other 2857/// value. This function is recursive, and the end result is a mapping of 2858/// bitnumber to bitnumber. It is the caller's responsibility to validate that 2859/// the bitnumber to bitnumber mapping is correct for a bswap or bitreverse. 2860/// 2861/// For example, if the current subexpression if "(shl i32 %X, 24)" then we know 2862/// that the expression deposits the low byte of %X into the high byte of the 2863/// result and that all other bits are zero. This expression is accepted and a 2864/// BitPart is returned with Provider set to %X and Provenance[24-31] set to 2865/// [0-7]. 2866/// 2867/// For vector types, all analysis is performed at the per-element level. No 2868/// cross-element analysis is supported (shuffle/insertion/reduction), and all 2869/// constant masks must be splatted across all elements. 2870/// 2871/// To avoid revisiting values, the BitPart results are memoized into the 2872/// provided map. To avoid unnecessary copying of BitParts, BitParts are 2873/// constructed in-place in the \c BPS map. Because of this \c BPS needs to 2874/// store BitParts objects, not pointers. As we need the concept of a nullptr 2875/// BitParts (Value has been analyzed and the analysis failed), we an Optional 2876/// type instead to provide the same functionality. 2877/// 2878/// Because we pass around references into \c BPS, we must use a container that 2879/// does not invalidate internal references (std::map instead of DenseMap). 2880static const Optional<BitPart> & 2881collectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals, 2882 std::map<Value *, Optional<BitPart>> &BPS, int Depth, 2883 bool &FoundRoot) { 2884 auto I = BPS.find(V); 2885 if (I != BPS.end()) 2886 return I->second; 2887 2888 auto &Result = BPS[V] = None; 2889 auto BitWidth = V->getType()->getScalarSizeInBits(); 2890 2891 // Can't do integer/elements > 128 bits. 2892 if (BitWidth > 128) 2893 return Result; 2894 2895 // Prevent stack overflow by limiting the recursion depth 2896 if (Depth == BitPartRecursionMaxDepth) { 2897 LLVM_DEBUG(dbgs() << "collectBitParts max recursion depth reached.\n"); 2898 return Result; 2899 } 2900 2901 if (auto *I = dyn_cast<Instruction>(V)) { 2902 Value *X, *Y; 2903 const APInt *C; 2904 2905 // If this is an or instruction, it may be an inner node of the bswap. 2906 if (match(V, m_Or(m_Value(X), m_Value(Y)))) { 2907 // Check we have both sources and they are from the same provider. 2908 const auto &A = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS, 2909 Depth + 1, FoundRoot); 2910 if (!A || !A->Provider) 2911 return Result; 2912 2913 const auto &B = collectBitParts(Y, MatchBSwaps, MatchBitReversals, BPS, 2914 Depth + 1, FoundRoot); 2915 if (!B || A->Provider != B->Provider) 2916 return Result; 2917 2918 // Try and merge the two together. 2919 Result = BitPart(A->Provider, BitWidth); 2920 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx) { 2921 if (A->Provenance[BitIdx] != BitPart::Unset && 2922 B->Provenance[BitIdx] != BitPart::Unset && 2923 A->Provenance[BitIdx] != B->Provenance[BitIdx]) 2924 return Result = None; 2925 2926 if (A->Provenance[BitIdx] == BitPart::Unset) 2927 Result->Provenance[BitIdx] = B->Provenance[BitIdx]; 2928 else 2929 Result->Provenance[BitIdx] = A->Provenance[BitIdx]; 2930 } 2931 2932 return Result; 2933 } 2934 2935 // If this is a logical shift by a constant, recurse then shift the result. 2936 if (match(V, m_LogicalShift(m_Value(X), m_APInt(C)))) { 2937 const APInt &BitShift = *C; 2938 2939 // Ensure the shift amount is defined. 2940 if (BitShift.uge(BitWidth)) 2941 return Result; 2942 2943 // For bswap-only, limit shift amounts to whole bytes, for an early exit. 2944 if (!MatchBitReversals && (BitShift.getZExtValue() % 8) != 0) 2945 return Result; 2946 2947 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS, 2948 Depth + 1, FoundRoot); 2949 if (!Res) 2950 return Result; 2951 Result = Res; 2952 2953 // Perform the "shift" on BitProvenance. 2954 auto &P = Result->Provenance; 2955 if (I->getOpcode() == Instruction::Shl) { 2956 P.erase(std::prev(P.end(), BitShift.getZExtValue()), P.end()); 2957 P.insert(P.begin(), BitShift.getZExtValue(), BitPart::Unset); 2958 } else { 2959 P.erase(P.begin(), std::next(P.begin(), BitShift.getZExtValue())); 2960 P.insert(P.end(), BitShift.getZExtValue(), BitPart::Unset); 2961 } 2962 2963 return Result; 2964 } 2965 2966 // If this is a logical 'and' with a mask that clears bits, recurse then 2967 // unset the appropriate bits. 2968 if (match(V, m_And(m_Value(X), m_APInt(C)))) { 2969 const APInt &AndMask = *C; 2970 2971 // Check that the mask allows a multiple of 8 bits for a bswap, for an 2972 // early exit. 2973 unsigned NumMaskedBits = AndMask.countPopulation(); 2974 if (!MatchBitReversals && (NumMaskedBits % 8) != 0) 2975 return Result; 2976 2977 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS, 2978 Depth + 1, FoundRoot); 2979 if (!Res) 2980 return Result; 2981 Result = Res; 2982 2983 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx) 2984 // If the AndMask is zero for this bit, clear the bit. 2985 if (AndMask[BitIdx] == 0) 2986 Result->Provenance[BitIdx] = BitPart::Unset; 2987 return Result; 2988 } 2989 2990 // If this is a zext instruction zero extend the result. 2991 if (match(V, m_ZExt(m_Value(X)))) { 2992 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS, 2993 Depth + 1, FoundRoot); 2994 if (!Res) 2995 return Result; 2996 2997 Result = BitPart(Res->Provider, BitWidth); 2998 auto NarrowBitWidth = X->getType()->getScalarSizeInBits(); 2999 for (unsigned BitIdx = 0; BitIdx < NarrowBitWidth; ++BitIdx) 3000 Result->Provenance[BitIdx] = Res->Provenance[BitIdx]; 3001 for (unsigned BitIdx = NarrowBitWidth; BitIdx < BitWidth; ++BitIdx) 3002 Result->Provenance[BitIdx] = BitPart::Unset; 3003 return Result; 3004 } 3005 3006 // If this is a truncate instruction, extract the lower bits. 3007 if (match(V, m_Trunc(m_Value(X)))) { 3008 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS, 3009 Depth + 1, FoundRoot); 3010 if (!Res) 3011 return Result; 3012 3013 Result = BitPart(Res->Provider, BitWidth); 3014 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx) 3015 Result->Provenance[BitIdx] = Res->Provenance[BitIdx]; 3016 return Result; 3017 } 3018 3019 // BITREVERSE - most likely due to us previous matching a partial 3020 // bitreverse. 3021 if (match(V, m_BitReverse(m_Value(X)))) { 3022 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS, 3023 Depth + 1, FoundRoot); 3024 if (!Res) 3025 return Result; 3026 3027 Result = BitPart(Res->Provider, BitWidth); 3028 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx) 3029 Result->Provenance[(BitWidth - 1) - BitIdx] = Res->Provenance[BitIdx]; 3030 return Result; 3031 } 3032 3033 // BSWAP - most likely due to us previous matching a partial bswap. 3034 if (match(V, m_BSwap(m_Value(X)))) { 3035 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS, 3036 Depth + 1, FoundRoot); 3037 if (!Res) 3038 return Result; 3039 3040 unsigned ByteWidth = BitWidth / 8; 3041 Result = BitPart(Res->Provider, BitWidth); 3042 for (unsigned ByteIdx = 0; ByteIdx < ByteWidth; ++ByteIdx) { 3043 unsigned ByteBitOfs = ByteIdx * 8; 3044 for (unsigned BitIdx = 0; BitIdx < 8; ++BitIdx) 3045 Result->Provenance[(BitWidth - 8 - ByteBitOfs) + BitIdx] = 3046 Res->Provenance[ByteBitOfs + BitIdx]; 3047 } 3048 return Result; 3049 } 3050 3051 // Funnel 'double' shifts take 3 operands, 2 inputs and the shift 3052 // amount (modulo). 3053 // fshl(X,Y,Z): (X << (Z % BW)) | (Y >> (BW - (Z % BW))) 3054 // fshr(X,Y,Z): (X << (BW - (Z % BW))) | (Y >> (Z % BW)) 3055 if (match(V, m_FShl(m_Value(X), m_Value(Y), m_APInt(C))) || 3056 match(V, m_FShr(m_Value(X), m_Value(Y), m_APInt(C)))) { 3057 // We can treat fshr as a fshl by flipping the modulo amount. 3058 unsigned ModAmt = C->urem(BitWidth); 3059 if (cast<IntrinsicInst>(I)->getIntrinsicID() == Intrinsic::fshr) 3060 ModAmt = BitWidth - ModAmt; 3061 3062 // For bswap-only, limit shift amounts to whole bytes, for an early exit. 3063 if (!MatchBitReversals && (ModAmt % 8) != 0) 3064 return Result; 3065 3066 // Check we have both sources and they are from the same provider. 3067 const auto &LHS = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS, 3068 Depth + 1, FoundRoot); 3069 if (!LHS || !LHS->Provider) 3070 return Result; 3071 3072 const auto &RHS = collectBitParts(Y, MatchBSwaps, MatchBitReversals, BPS, 3073 Depth + 1, FoundRoot); 3074 if (!RHS || LHS->Provider != RHS->Provider) 3075 return Result; 3076 3077 unsigned StartBitRHS = BitWidth - ModAmt; 3078 Result = BitPart(LHS->Provider, BitWidth); 3079 for (unsigned BitIdx = 0; BitIdx < StartBitRHS; ++BitIdx) 3080 Result->Provenance[BitIdx + ModAmt] = LHS->Provenance[BitIdx]; 3081 for (unsigned BitIdx = 0; BitIdx < ModAmt; ++BitIdx) 3082 Result->Provenance[BitIdx] = RHS->Provenance[BitIdx + StartBitRHS]; 3083 return Result; 3084 } 3085 } 3086 3087 // If we've already found a root input value then we're never going to merge 3088 // these back together. 3089 if (FoundRoot) 3090 return Result; 3091 3092 // Okay, we got to something that isn't a shift, 'or', 'and', etc. This must 3093 // be the root input value to the bswap/bitreverse. 3094 FoundRoot = true; 3095 Result = BitPart(V, BitWidth); 3096 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx) 3097 Result->Provenance[BitIdx] = BitIdx; 3098 return Result; 3099} 3100 3101static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To, 3102 unsigned BitWidth) { 3103 if (From % 8 != To % 8) 3104 return false; 3105 // Convert from bit indices to byte indices and check for a byte reversal. 3106 From >>= 3; 3107 To >>= 3; 3108 BitWidth >>= 3; 3109 return From == BitWidth - To - 1; 3110} 3111 3112static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To, 3113 unsigned BitWidth) { 3114 return From == BitWidth - To - 1; 3115} 3116 3117bool llvm::recognizeBSwapOrBitReverseIdiom( 3118 Instruction *I, bool MatchBSwaps, bool MatchBitReversals, 3119 SmallVectorImpl<Instruction *> &InsertedInsts) { 3120 if (!match(I, m_Or(m_Value(), m_Value())) && 3121 !match(I, m_FShl(m_Value(), m_Value(), m_Value())) && 3122 !match(I, m_FShr(m_Value(), m_Value(), m_Value()))) 3123 return false; 3124 if (!MatchBSwaps && !MatchBitReversals) 3125 return false; 3126 Type *ITy = I->getType(); 3127 if (!ITy->isIntOrIntVectorTy() || ITy->getScalarSizeInBits() > 128) 3128 return false; // Can't do integer/elements > 128 bits. 3129 3130 Type *DemandedTy = ITy; 3131 if (I->hasOneUse()) 3132 if (auto *Trunc = dyn_cast<TruncInst>(I->user_back())) 3133 DemandedTy = Trunc->getType(); 3134 3135 // Try to find all the pieces corresponding to the bswap. 3136 bool FoundRoot = false; 3137 std::map<Value *, Optional<BitPart>> BPS; 3138 const auto &Res = 3139 collectBitParts(I, MatchBSwaps, MatchBitReversals, BPS, 0, FoundRoot); 3140 if (!Res) 3141 return false; 3142 ArrayRef<int8_t> BitProvenance = Res->Provenance; 3143 assert(all_of(BitProvenance, 3144 [](int8_t I) { return I == BitPart::Unset || 0 <= I; }) && 3145 "Illegal bit provenance index"); 3146 3147 // If the upper bits are zero, then attempt to perform as a truncated op. 3148 if (BitProvenance.back() == BitPart::Unset) { 3149 while (!BitProvenance.empty() && BitProvenance.back() == BitPart::Unset) 3150 BitProvenance = BitProvenance.drop_back(); 3151 if (BitProvenance.empty()) 3152 return false; // TODO - handle null value? 3153 DemandedTy = Type::getIntNTy(I->getContext(), BitProvenance.size()); 3154 if (auto *IVecTy = dyn_cast<VectorType>(ITy)) 3155 DemandedTy = VectorType::get(DemandedTy, IVecTy); 3156 } 3157 3158 // Check BitProvenance hasn't found a source larger than the result type. 3159 unsigned DemandedBW = DemandedTy->getScalarSizeInBits(); 3160 if (DemandedBW > ITy->getScalarSizeInBits()) 3161 return false; 3162 3163 // Now, is the bit permutation correct for a bswap or a bitreverse? We can 3164 // only byteswap values with an even number of bytes. 3165 APInt DemandedMask = APInt::getAllOnesValue(DemandedBW); 3166 bool OKForBSwap = MatchBSwaps && (DemandedBW % 16) == 0; 3167 bool OKForBitReverse = MatchBitReversals; 3168 for (unsigned BitIdx = 0; 3169 (BitIdx < DemandedBW) && (OKForBSwap || OKForBitReverse); ++BitIdx) { 3170 if (BitProvenance[BitIdx] == BitPart::Unset) { 3171 DemandedMask.clearBit(BitIdx); 3172 continue; 3173 } 3174 OKForBSwap &= bitTransformIsCorrectForBSwap(BitProvenance[BitIdx], BitIdx, 3175 DemandedBW); 3176 OKForBitReverse &= bitTransformIsCorrectForBitReverse(BitProvenance[BitIdx], 3177 BitIdx, DemandedBW); 3178 } 3179 3180 Intrinsic::ID Intrin; 3181 if (OKForBSwap) 3182 Intrin = Intrinsic::bswap; 3183 else if (OKForBitReverse) 3184 Intrin = Intrinsic::bitreverse; 3185 else 3186 return false; 3187 3188 Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, DemandedTy); 3189 Value *Provider = Res->Provider; 3190 3191 // We may need to truncate the provider. 3192 if (DemandedTy != Provider->getType()) { 3193 auto *Trunc = 3194 CastInst::CreateIntegerCast(Provider, DemandedTy, false, "trunc", I); 3195 InsertedInsts.push_back(Trunc); 3196 Provider = Trunc; 3197 } 3198 3199 Instruction *Result = CallInst::Create(F, Provider, "rev", I); 3200 InsertedInsts.push_back(Result); 3201 3202 if (!DemandedMask.isAllOnesValue()) { 3203 auto *Mask = ConstantInt::get(DemandedTy, DemandedMask); 3204 Result = BinaryOperator::Create(Instruction::And, Result, Mask, "mask", I); 3205 InsertedInsts.push_back(Result); 3206 } 3207 3208 // We may need to zeroextend back to the result type. 3209 if (ITy != Result->getType()) { 3210 auto *ExtInst = CastInst::CreateIntegerCast(Result, ITy, false, "zext", I); 3211 InsertedInsts.push_back(ExtInst); 3212 } 3213 3214 return true; 3215} 3216 3217// CodeGen has special handling for some string functions that may replace 3218// them with target-specific intrinsics. Since that'd skip our interceptors 3219// in ASan/MSan/TSan/DFSan, and thus make us miss some memory accesses, 3220// we mark affected calls as NoBuiltin, which will disable optimization 3221// in CodeGen. 3222void llvm::maybeMarkSanitizerLibraryCallNoBuiltin( 3223 CallInst *CI, const TargetLibraryInfo *TLI) { 3224 Function *F = CI->getCalledFunction(); 3225 LibFunc Func; 3226 if (F && !F->hasLocalLinkage() && F->hasName() && 3227 TLI->getLibFunc(F->getName(), Func) && TLI->hasOptimizedCodeGen(Func) && 3228 !F->doesNotAccessMemory()) 3229 CI->addAttribute(AttributeList::FunctionIndex, Attribute::NoBuiltin); 3230} 3231 3232bool llvm::canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx) { 3233 // We can't have a PHI with a metadata type. 3234 if (I->getOperand(OpIdx)->getType()->isMetadataTy()) 3235 return false; 3236 3237 // Early exit. 3238 if (!isa<Constant>(I->getOperand(OpIdx))) 3239 return true; 3240 3241 switch (I->getOpcode()) { 3242 default: 3243 return true; 3244 case Instruction::Call: 3245 case Instruction::Invoke: { 3246 const auto &CB = cast<CallBase>(*I); 3247 3248 // Can't handle inline asm. Skip it. 3249 if (CB.isInlineAsm()) 3250 return false; 3251 3252 // Constant bundle operands may need to retain their constant-ness for 3253 // correctness. 3254 if (CB.isBundleOperand(OpIdx)) 3255 return false; 3256 3257 if (OpIdx < CB.getNumArgOperands()) { 3258 // Some variadic intrinsics require constants in the variadic arguments, 3259 // which currently aren't markable as immarg. 3260 if (isa<IntrinsicInst>(CB) && 3261 OpIdx >= CB.getFunctionType()->getNumParams()) { 3262 // This is known to be OK for stackmap. 3263 return CB.getIntrinsicID() == Intrinsic::experimental_stackmap; 3264 } 3265 3266 // gcroot is a special case, since it requires a constant argument which 3267 // isn't also required to be a simple ConstantInt. 3268 if (CB.getIntrinsicID() == Intrinsic::gcroot) 3269 return false; 3270 3271 // Some intrinsic operands are required to be immediates. 3272 return !CB.paramHasAttr(OpIdx, Attribute::ImmArg); 3273 } 3274 3275 // It is never allowed to replace the call argument to an intrinsic, but it 3276 // may be possible for a call. 3277 return !isa<IntrinsicInst>(CB); 3278 } 3279 case Instruction::ShuffleVector: 3280 // Shufflevector masks are constant. 3281 return OpIdx != 2; 3282 case Instruction::Switch: 3283 case Instruction::ExtractValue: 3284 // All operands apart from the first are constant. 3285 return OpIdx == 0; 3286 case Instruction::InsertValue: 3287 // All operands apart from the first and the second are constant. 3288 return OpIdx < 2; 3289 case Instruction::Alloca: 3290 // Static allocas (constant size in the entry block) are handled by 3291 // prologue/epilogue insertion so they're free anyway. We definitely don't 3292 // want to make them non-constant. 3293 return !cast<AllocaInst>(I)->isStaticAlloca(); 3294 case Instruction::GetElementPtr: 3295 if (OpIdx == 0) 3296 return true; 3297 gep_type_iterator It = gep_type_begin(I); 3298 for (auto E = std::next(It, OpIdx); It != E; ++It) 3299 if (It.isStruct()) 3300 return false; 3301 return true; 3302 } 3303} 3304 3305Value *llvm::invertCondition(Value *Condition) { 3306 // First: Check if it's a constant 3307 if (Constant *C = dyn_cast<Constant>(Condition)) 3308 return ConstantExpr::getNot(C); 3309 3310 // Second: If the condition is already inverted, return the original value 3311 Value *NotCondition; 3312 if (match(Condition, m_Not(m_Value(NotCondition)))) 3313 return NotCondition; 3314 3315 BasicBlock *Parent = nullptr; 3316 Instruction *Inst = dyn_cast<Instruction>(Condition); 3317 if (Inst) 3318 Parent = Inst->getParent(); 3319 else if (Argument *Arg = dyn_cast<Argument>(Condition)) 3320 Parent = &Arg->getParent()->getEntryBlock(); 3321 assert(Parent && "Unsupported condition to invert"); 3322 3323 // Third: Check all the users for an invert 3324 for (User *U : Condition->users()) 3325 if (Instruction *I = dyn_cast<Instruction>(U)) 3326 if (I->getParent() == Parent && match(I, m_Not(m_Specific(Condition)))) 3327 return I; 3328 3329 // Last option: Create a new instruction 3330 auto *Inverted = 3331 BinaryOperator::CreateNot(Condition, Condition->getName() + ".inv"); 3332 if (Inst && !isa<PHINode>(Inst)) 3333 Inverted->insertAfter(Inst); 3334 else 3335 Inverted->insertBefore(&*Parent->getFirstInsertionPt()); 3336 return Inverted; 3337} 3338 3339bool llvm::inferAttributesFromOthers(Function &F) { 3340 // Note: We explicitly check for attributes rather than using cover functions 3341 // because some of the cover functions include the logic being implemented. 3342 3343 bool Changed = false; 3344 // readnone + not convergent implies nosync 3345 if (!F.hasFnAttribute(Attribute::NoSync) && 3346 F.doesNotAccessMemory() && !F.isConvergent()) { 3347 F.setNoSync(); 3348 Changed = true; 3349 } 3350 3351 // readonly implies nofree 3352 if (!F.hasFnAttribute(Attribute::NoFree) && F.onlyReadsMemory()) { 3353 F.setDoesNotFreeMemory(); 3354 Changed = true; 3355 } 3356 3357 // willreturn implies mustprogress 3358 if (!F.hasFnAttribute(Attribute::MustProgress) && F.willReturn()) { 3359 F.setMustProgress(); 3360 Changed = true; 3361 } 3362 3363 // TODO: There are a bunch of cases of restrictive memory effects we 3364 // can infer by inspecting arguments of argmemonly-ish functions. 3365 3366 return Changed; 3367} 3368