/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Transforms/Utils/Local.cpp

Bug Summary

File:	llvm/lib/Transforms/Utils/Local.cpp
Warning:	line 3332, column 30 Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name Local.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Transforms/Utils -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Transforms/Utils -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Transforms/Utils -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include -D NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Transforms/Utils -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-09-04-040900-46481-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Transforms/Utils/Local.cpp

/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Transforms/Utils/Local.cpp

→

1//===- Local.cpp - Functions to perform local transformations -------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This family of functions perform various local transformations to the
10// program.
11//
12//===----------------------------------------------------------------------===//

14#include "llvm/Transforms/Utils/Local.h"
15#include "llvm/ADT/APInt.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/DenseMapInfo.h"
18#include "llvm/ADT/DenseSet.h"
19#include "llvm/ADT/Hashing.h"
20#include "llvm/ADT/None.h"
21#include "llvm/ADT/Optional.h"
22#include "llvm/ADT/STLExtras.h"
23#include "llvm/ADT/SetVector.h"
24#include "llvm/ADT/SmallPtrSet.h"
25#include "llvm/ADT/SmallVector.h"
26#include "llvm/ADT/Statistic.h"
27#include "llvm/Analysis/AssumeBundleQueries.h"
28#include "llvm/Analysis/ConstantFolding.h"
29#include "llvm/Analysis/DomTreeUpdater.h"
30#include "llvm/Analysis/EHPersonalities.h"
31#include "llvm/Analysis/InstructionSimplify.h"
32#include "llvm/Analysis/LazyValueInfo.h"
33#include "llvm/Analysis/MemoryBuiltins.h"
34#include "llvm/Analysis/MemorySSAUpdater.h"
35#include "llvm/Analysis/TargetLibraryInfo.h"
36#include "llvm/Analysis/ValueTracking.h"
37#include "llvm/Analysis/VectorUtils.h"
38#include "llvm/BinaryFormat/Dwarf.h"
39#include "llvm/IR/Argument.h"
40#include "llvm/IR/Attributes.h"
41#include "llvm/IR/BasicBlock.h"
42#include "llvm/IR/CFG.h"
43#include "llvm/IR/Constant.h"
44#include "llvm/IR/ConstantRange.h"
45#include "llvm/IR/Constants.h"
46#include "llvm/IR/DIBuilder.h"
47#include "llvm/IR/DataLayout.h"
48#include "llvm/IR/DebugInfoMetadata.h"
49#include "llvm/IR/DebugLoc.h"
50#include "llvm/IR/DerivedTypes.h"
51#include "llvm/IR/Dominators.h"
52#include "llvm/IR/Function.h"
53#include "llvm/IR/GetElementPtrTypeIterator.h"
54#include "llvm/IR/GlobalObject.h"
55#include "llvm/IR/IRBuilder.h"
56#include "llvm/IR/InstrTypes.h"
57#include "llvm/IR/Instruction.h"
58#include "llvm/IR/Instructions.h"
59#include "llvm/IR/IntrinsicInst.h"
60#include "llvm/IR/Intrinsics.h"
61#include "llvm/IR/LLVMContext.h"
62#include "llvm/IR/MDBuilder.h"
63#include "llvm/IR/Metadata.h"
64#include "llvm/IR/Module.h"
65#include "llvm/IR/Operator.h"
66#include "llvm/IR/PatternMatch.h"
67#include "llvm/IR/PseudoProbe.h"
68#include "llvm/IR/Type.h"
69#include "llvm/IR/Use.h"
70#include "llvm/IR/User.h"
71#include "llvm/IR/Value.h"
72#include "llvm/IR/ValueHandle.h"
73#include "llvm/Support/Casting.h"
74#include "llvm/Support/Debug.h"
75#include "llvm/Support/ErrorHandling.h"
76#include "llvm/Support/KnownBits.h"
77#include "llvm/Support/raw_ostream.h"
78#include "llvm/Transforms/Utils/BasicBlockUtils.h"
79#include "llvm/Transforms/Utils/ValueMapper.h"
80#include <algorithm>
81#include <cassert>
82#include <climits>
83#include <cstdint>
84#include <iterator>
85#include <map>
86#include <utility>

88using namespace llvm;
89using namespace llvm::PatternMatch;

91#define DEBUG_TYPE"local" "local"

93STATISTIC(NumRemoved, "Number of unreachable basic blocks removed")static llvm::Statistic NumRemoved = {"local", "NumRemoved", "Number of unreachable basic blocks removed"
};
94STATISTIC(NumPHICSEs, "Number of PHI's that got CSE'd")static llvm::Statistic NumPHICSEs = {"local", "NumPHICSEs", "Number of PHI's that got CSE'd"
};

96static cl::opt<bool> PHICSEDebugHash(
  "phicse-debug-hash",
98#ifdef EXPENSIVE_CHECKS
  cl::init(true),
100#else
  cl::init(false),
102#endif
  cl::Hidden,
  cl::desc("Perform extra assertion checking to verify that PHINodes's hash "
           "function is well-behaved w.r.t. its isEqual predicate"));

107static cl::opt<unsigned> PHICSENumPHISmallSize(
  "phicse-num-phi-smallsize", cl::init(32), cl::Hidden,
  cl::desc(
      "When the basic block contains not more than this number of PHI nodes, "
      "perform a (faster!) exhaustive search instead of set-driven one."));

113// Max recursion depth for collectBitParts used when detecting bswap and
114// bitreverse idioms.
115static const unsigned BitPartRecursionMaxDepth = 48;

117//===----------------------------------------------------------------------===//
118//  Local constant propagation.
119//

121/// ConstantFoldTerminator - If a terminator instruction is predicated on a
122/// constant value, convert it into an unconditional branch to the constant
123/// destination.  This is a nontrivial operation because the successors of this
124/// basic block must have their PHI nodes updated.
125/// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
126/// conditions and indirectbr addresses this might make dead if
127/// DeleteDeadConditions is true.
128bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
                                const TargetLibraryInfo *TLI,
                                DomTreeUpdater *DTU) {
Instruction *T = BB->getTerminator();
IRBuilder<> Builder(T);

// Branch - See if we are conditional jumping on constant
if (auto *BI = dyn_cast<BranchInst>(T)) {
  if (BI->isUnconditional()) return false;  // Can't optimize uncond branch

  BasicBlock *Dest1 = BI->getSuccessor(0);
  BasicBlock *Dest2 = BI->getSuccessor(1);

  if (Dest2 == Dest1) {       // Conditional branch to same location?
    // This branch matches something like this:
    //     br bool %cond, label %Dest, label %Dest
    // and changes it into:  br label %Dest

    // Let the basic block know that we are letting go of one copy of it.
    assert(BI->getParent() && "Terminator not inserted in block!")(static_cast<void> (0));
    Dest1->removePredecessor(BI->getParent());

    // Replace the conditional branch with an unconditional one.
    BranchInst *NewBI = Builder.CreateBr(Dest1);

    // Transfer the metadata to the new branch instruction.
    NewBI->copyMetadata(*BI, {LLVMContext::MD_loop, LLVMContext::MD_dbg,
                              LLVMContext::MD_annotation});

    Value *Cond = BI->getCondition();
    BI->eraseFromParent();
    if (DeleteDeadConditions)
      RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
    return true;
  }

  if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
    // Are we branching on constant?
    // YES.  Change to unconditional branch...
    BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2;
    BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1;

    // Let the basic block know that we are letting go of it.  Based on this,
    // it will adjust it's PHI nodes.
    OldDest->removePredecessor(BB);

    // Replace the conditional branch with an unconditional one.
    BranchInst *NewBI = Builder.CreateBr(Destination);

    // Transfer the metadata to the new branch instruction.
    NewBI->copyMetadata(*BI, {LLVMContext::MD_loop, LLVMContext::MD_dbg,
                              LLVMContext::MD_annotation});

    BI->eraseFromParent();
    if (DTU)
      DTU->applyUpdates({{DominatorTree::Delete, BB, OldDest}});
    return true;
  }

  return false;
}

if (auto *SI = dyn_cast<SwitchInst>(T)) {
  // If we are switching on a constant, we can convert the switch to an
  // unconditional branch.
  auto *CI = dyn_cast<ConstantInt>(SI->getCondition());
  BasicBlock *DefaultDest = SI->getDefaultDest();
  BasicBlock *TheOnlyDest = DefaultDest;

  // If the default is unreachable, ignore it when searching for TheOnlyDest.
  if (isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg()) &&
      SI->getNumCases() > 0) {
    TheOnlyDest = SI->case_begin()->getCaseSuccessor();
  }

  bool Changed = false;

  // Figure out which case it goes to.
  for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
    // Found case matching a constant operand?
    if (i->getCaseValue() == CI) {
      TheOnlyDest = i->getCaseSuccessor();
      break;
    }

    // Check to see if this branch is going to the same place as the default
    // dest.  If so, eliminate it as an explicit compare.
    if (i->getCaseSuccessor() == DefaultDest) {
      MDNode *MD = SI->getMetadata(LLVMContext::MD_prof);
      unsigned NCases = SI->getNumCases();
      // Fold the case metadata into the default if there will be any branches
      // left, unless the metadata doesn't match the switch.
      if (NCases > 1 && MD && MD->getNumOperands() == 2 + NCases) {
        // Collect branch weights into a vector.
        SmallVector<uint32_t, 8> Weights;
        for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e;
             ++MD_i) {
          auto *CI = mdconst::extract<ConstantInt>(MD->getOperand(MD_i));
          Weights.push_back(CI->getValue().getZExtValue());
        }
        // Merge weight of this case to the default weight.
        unsigned idx = i->getCaseIndex();
        Weights[0] += Weights[idx+1];
        // Remove weight for this case.
        std::swap(Weights[idx+1], Weights.back());
        Weights.pop_back();
        SI->setMetadata(LLVMContext::MD_prof,
                        MDBuilder(BB->getContext()).
                        createBranchWeights(Weights));
      }
      // Remove this entry.
      BasicBlock *ParentBB = SI->getParent();
      DefaultDest->removePredecessor(ParentBB);
      i = SI->removeCase(i);
      e = SI->case_end();
      Changed = true;
      continue;
    }

    // Otherwise, check to see if the switch only branches to one destination.
    // We do this by reseting "TheOnlyDest" to null when we find two non-equal
    // destinations.
    if (i->getCaseSuccessor() != TheOnlyDest)
      TheOnlyDest = nullptr;

    // Increment this iterator as we haven't removed the case.
    ++i;
  }

  if (CI && !TheOnlyDest) {
    // Branching on a constant, but not any of the cases, go to the default
    // successor.
    TheOnlyDest = SI->getDefaultDest();
  }

  // If we found a single destination that we can fold the switch into, do so
  // now.
  if (TheOnlyDest) {
    // Insert the new branch.
    Builder.CreateBr(TheOnlyDest);
    BasicBlock *BB = SI->getParent();

    SmallSet<BasicBlock *, 8> RemovedSuccessors;

    // Remove entries from PHI nodes which we no longer branch to...
    BasicBlock *SuccToKeep = TheOnlyDest;
    for (BasicBlock *Succ : successors(SI)) {
      if (DTU && Succ != TheOnlyDest)
        RemovedSuccessors.insert(Succ);
      // Found case matching a constant operand?
      if (Succ == SuccToKeep) {
        SuccToKeep = nullptr; // Don't modify the first branch to TheOnlyDest
      } else {
        Succ->removePredecessor(BB);
      }
    }

    // Delete the old switch.
    Value *Cond = SI->getCondition();
    SI->eraseFromParent();
    if (DeleteDeadConditions)
      RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
    if (DTU) {
      std::vector<DominatorTree::UpdateType> Updates;
      Updates.reserve(RemovedSuccessors.size());
      for (auto *RemovedSuccessor : RemovedSuccessors)
        Updates.push_back({DominatorTree::Delete, BB, RemovedSuccessor});
      DTU->applyUpdates(Updates);
    }
    return true;
  }

  if (SI->getNumCases() == 1) {
    // Otherwise, we can fold this switch into a conditional branch
    // instruction if it has only one non-default destination.
    auto FirstCase = *SI->case_begin();
    Value *Cond = Builder.CreateICmpEQ(SI->getCondition(),
        FirstCase.getCaseValue(), "cond");

    // Insert the new branch.
    BranchInst *NewBr = Builder.CreateCondBr(Cond,
                                             FirstCase.getCaseSuccessor(),
                                             SI->getDefaultDest());
    MDNode *MD = SI->getMetadata(LLVMContext::MD_prof);
    if (MD && MD->getNumOperands() == 3) {
      ConstantInt *SICase =
          mdconst::dyn_extract<ConstantInt>(MD->getOperand(2));
      ConstantInt *SIDef =
          mdconst::dyn_extract<ConstantInt>(MD->getOperand(1));
      assert(SICase && SIDef)(static_cast<void> (0));
      // The TrueWeight should be the weight for the single case of SI.
      NewBr->setMetadata(LLVMContext::MD_prof,
                      MDBuilder(BB->getContext()).
                      createBranchWeights(SICase->getValue().getZExtValue(),
                                          SIDef->getValue().getZExtValue()));
    }

    // Update make.implicit metadata to the newly-created conditional branch.
    MDNode *MakeImplicitMD = SI->getMetadata(LLVMContext::MD_make_implicit);
    if (MakeImplicitMD)
      NewBr->setMetadata(LLVMContext::MD_make_implicit, MakeImplicitMD);

    // Delete the old switch.
    SI->eraseFromParent();
    return true;
  }
  return Changed;
}

if (auto *IBI = dyn_cast<IndirectBrInst>(T)) {
  // indirectbr blockaddress(@F, @BB) -> br label @BB
  if (auto *BA =
        dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) {
    BasicBlock *TheOnlyDest = BA->getBasicBlock();
    SmallSet<BasicBlock *, 8> RemovedSuccessors;

    // Insert the new branch.
    Builder.CreateBr(TheOnlyDest);

    BasicBlock *SuccToKeep = TheOnlyDest;
    for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
      BasicBlock *DestBB = IBI->getDestination(i);
      if (DTU && DestBB != TheOnlyDest)
        RemovedSuccessors.insert(DestBB);
      if (IBI->getDestination(i) == SuccToKeep) {
        SuccToKeep = nullptr;
      } else {
        DestBB->removePredecessor(BB);
      }
    }
    Value *Address = IBI->getAddress();
    IBI->eraseFromParent();
    if (DeleteDeadConditions)
      // Delete pointer cast instructions.
      RecursivelyDeleteTriviallyDeadInstructions(Address, TLI);

    // Also zap the blockaddress constant if there are no users remaining,
    // otherwise the destination is still marked as having its address taken.
    if (BA->use_empty())
      BA->destroyConstant();

    // If we didn't find our destination in the IBI successor list, then we
    // have undefined behavior.  Replace the unconditional branch with an
    // 'unreachable' instruction.
    if (SuccToKeep) {
      BB->getTerminator()->eraseFromParent();
      new UnreachableInst(BB->getContext(), BB);
    }

    if (DTU) {
      std::vector<DominatorTree::UpdateType> Updates;
      Updates.reserve(RemovedSuccessors.size());
      for (auto *RemovedSuccessor : RemovedSuccessors)
        Updates.push_back({DominatorTree::Delete, BB, RemovedSuccessor});
      DTU->applyUpdates(Updates);
    }
    return true;
  }
}

return false;
389}

391//===----------------------------------------------------------------------===//
392//  Local dead code elimination.
393//

395/// isInstructionTriviallyDead - Return true if the result produced by the
396/// instruction is not used, and the instruction has no side effects.
397///
398bool llvm::isInstructionTriviallyDead(Instruction *I,
                                    const TargetLibraryInfo *TLI) {
if (!I->use_empty())
  return false;
return wouldInstructionBeTriviallyDead(I, TLI);
403}

405bool llvm::wouldInstructionBeTriviallyDead(Instruction *I,
                                         const TargetLibraryInfo *TLI) {
if (I->isTerminator())
  return false;

// We don't want the landingpad-like instructions removed by anything this
// general.
if (I->isEHPad())
  return false;

// We don't want debug info removed by anything this general, unless
// debug info is empty.
if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) {
  if (DDI->getAddress())
    return false;
  return true;
}
if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) {
  if (DVI->hasArgList() || DVI->getValue(0))
    return false;
  return true;
}
if (DbgLabelInst *DLI = dyn_cast<DbgLabelInst>(I)) {
  if (DLI->getLabel())
    return false;
  return true;
}

if (!I->willReturn())
  return false;

if (!I->mayHaveSideEffects())
  return true;

// Special case intrinsics that "may have side effects" but can be deleted
// when dead.
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
  // Safe to delete llvm.stacksave and launder.invariant.group if dead.
  if (II->getIntrinsicID() == Intrinsic::stacksave ||
      II->getIntrinsicID() == Intrinsic::launder_invariant_group)
    return true;

  if (II->isLifetimeStartOrEnd()) {
    auto *Arg = II->getArgOperand(1);
    // Lifetime intrinsics are dead when their right-hand is undef.
    if (isa<UndefValue>(Arg))
      return true;
    // If the right-hand is an alloc, global, or argument and the only uses
    // are lifetime intrinsics then the intrinsics are dead.
    if (isa<AllocaInst>(Arg) || isa<GlobalValue>(Arg) || isa<Argument>(Arg))
      return llvm::all_of(Arg->uses(), [](Use &Use) {
        if (IntrinsicInst *IntrinsicUse =
                dyn_cast<IntrinsicInst>(Use.getUser()))
          return IntrinsicUse->isLifetimeStartOrEnd();
        return false;
      });
    return false;
  }

  // Assumptions are dead if their condition is trivially true.  Guards on
  // true are operationally no-ops.  In the future we can consider more
  // sophisticated tradeoffs for guards considering potential for check
  // widening, but for now we keep things simple.
  if ((II->getIntrinsicID() == Intrinsic::assume &&
       isAssumeWithEmptyBundle(cast<AssumeInst>(*II))) ||
      II->getIntrinsicID() == Intrinsic::experimental_guard) {
    if (ConstantInt *Cond = dyn_cast<ConstantInt>(II->getArgOperand(0)))
      return !Cond->isZero();

    return false;
  }

  if (auto *FPI = dyn_cast<ConstrainedFPIntrinsic>(I)) {
    Optional<fp::ExceptionBehavior> ExBehavior = FPI->getExceptionBehavior();
    return ExBehavior.getValue() != fp::ebStrict;
  }
}

if (isAllocLikeFn(I, TLI))
  return true;

if (CallInst *CI = isFreeCall(I, TLI))
  if (Constant *C = dyn_cast<Constant>(CI->getArgOperand(0)))
    return C->isNullValue() || isa<UndefValue>(C);

if (auto *Call = dyn_cast<CallBase>(I))
  if (isMathLibCallNoop(Call, TLI))
    return true;

// To express possible interaction with floating point environment constrained
// intrinsics are described as if they access memory. So they look like having
// side effect but actually do not have it unless they raise floating point
// exception. If FP exceptions are ignored, the intrinsic may be deleted.
if (auto *CI = dyn_cast<ConstrainedFPIntrinsic>(I)) {
  Optional<fp::ExceptionBehavior> EB = CI->getExceptionBehavior();
  if (!EB || *EB == fp::ExceptionBehavior::ebIgnore)
    return true;
}

return false;
505}

507/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
508/// trivially dead instruction, delete it.  If that makes any of its operands
509/// trivially dead, delete them too, recursively.  Return true if any
510/// instructions were deleted.
511bool llvm::RecursivelyDeleteTriviallyDeadInstructions(
  Value *V, const TargetLibraryInfo *TLI, MemorySSAUpdater *MSSAU,
  std::function<void(Value *)> AboutToDeleteCallback) {
Instruction *I = dyn_cast<Instruction>(V);
if (!I || !isInstructionTriviallyDead(I, TLI))
  return false;

SmallVector<WeakTrackingVH, 16> DeadInsts;
DeadInsts.push_back(I);
RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI, MSSAU,
                                           AboutToDeleteCallback);

return true;
524}

526bool llvm::RecursivelyDeleteTriviallyDeadInstructionsPermissive(
  SmallVectorImpl<WeakTrackingVH> &DeadInsts, const TargetLibraryInfo *TLI,
  MemorySSAUpdater *MSSAU,
  std::function<void(Value *)> AboutToDeleteCallback) {
unsigned S = 0, E = DeadInsts.size(), Alive = 0;
for (; S != E; ++S) {
  auto *I = cast<Instruction>(DeadInsts[S]);
  if (!isInstructionTriviallyDead(I)) {
    DeadInsts[S] = nullptr;
    ++Alive;
  }
}
if (Alive == E)
  return false;
RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI, MSSAU,
                                           AboutToDeleteCallback);
return true;
543}

545void llvm::RecursivelyDeleteTriviallyDeadInstructions(
  SmallVectorImpl<WeakTrackingVH> &DeadInsts, const TargetLibraryInfo *TLI,
  MemorySSAUpdater *MSSAU,
  std::function<void(Value *)> AboutToDeleteCallback) {
// Process the dead instruction list until empty.
while (!DeadInsts.empty()) {
  Value *V = DeadInsts.pop_back_val();
  Instruction *I = cast_or_null<Instruction>(V);
  if (!I)
    continue;
  assert(isInstructionTriviallyDead(I, TLI) &&(static_cast<void> (0))
         "Live instruction found in dead worklist!")(static_cast<void> (0));
  assert(I->use_empty() && "Instructions with uses are not dead.")(static_cast<void> (0));

  // Don't lose the debug info while deleting the instructions.
  salvageDebugInfo(*I);

  if (AboutToDeleteCallback)
    AboutToDeleteCallback(I);

  // Null out all of the instruction's operands to see if any operand becomes
  // dead as we go.
  for (Use &OpU : I->operands()) {
    Value *OpV = OpU.get();
    OpU.set(nullptr);

    if (!OpV->use_empty())
      continue;

    // If the operand is an instruction that became dead as we nulled out the
    // operand, and if it is 'trivially' dead, delete it in a future loop
    // iteration.
    if (Instruction *OpI = dyn_cast<Instruction>(OpV))
      if (isInstructionTriviallyDead(OpI, TLI))
        DeadInsts.push_back(OpI);
  }
  if (MSSAU)
    MSSAU->removeMemoryAccess(I);

  I->eraseFromParent();
}
586}

588bool llvm::replaceDbgUsesWithUndef(Instruction *I) {
SmallVector<DbgVariableIntrinsic *, 1> DbgUsers;
findDbgUsers(DbgUsers, I);
for (auto *DII : DbgUsers) {
  Value *Undef = UndefValue::get(I->getType());
  DII->replaceVariableLocationOp(I, Undef);
}
return !DbgUsers.empty();
596}

598/// areAllUsesEqual - Check whether the uses of a value are all the same.
599/// This is similar to Instruction::hasOneUse() except this will also return
600/// true when there are no uses or multiple uses that all refer to the same
601/// value.
602static bool areAllUsesEqual(Instruction *I) {
Value::user_iterator UI = I->user_begin();
Value::user_iterator UE = I->user_end();
if (UI == UE)
  return true;

User *TheUse = *UI;
for (++UI; UI != UE; ++UI) {
  if (*UI != TheUse)
    return false;
}
return true;
614}

616/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively
617/// dead PHI node, due to being a def-use chain of single-use nodes that
618/// either forms a cycle or is terminated by a trivially dead instruction,
619/// delete it.  If that makes any of its operands trivially dead, delete them
620/// too, recursively.  Return true if a change was made.
621bool llvm::RecursivelyDeleteDeadPHINode(PHINode *PN,
                                      const TargetLibraryInfo *TLI,
                                      llvm::MemorySSAUpdater *MSSAU) {
SmallPtrSet<Instruction*, 4> Visited;
for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects();
     I = cast<Instruction>(*I->user_begin())) {
  if (I->use_empty())
    return RecursivelyDeleteTriviallyDeadInstructions(I, TLI, MSSAU);

  // If we find an instruction more than once, we're on a cycle that
  // won't prove fruitful.
  if (!Visited.insert(I).second) {
    // Break the cycle and delete the instruction and its operands.
    I->replaceAllUsesWith(UndefValue::get(I->getType()));
    (void)RecursivelyDeleteTriviallyDeadInstructions(I, TLI, MSSAU);
    return true;
  }
}
return false;
640}

642static bool
643simplifyAndDCEInstruction(Instruction *I,
                        SmallSetVector<Instruction *, 16> &WorkList,
                        const DataLayout &DL,
                        const TargetLibraryInfo *TLI) {
if (isInstructionTriviallyDead(I, TLI)) {
  salvageDebugInfo(*I);

  // Null out all of the instruction's operands to see if any operand becomes
  // dead as we go.
  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
    Value *OpV = I->getOperand(i);
    I->setOperand(i, nullptr);

    if (!OpV->use_empty() || I == OpV)
      continue;

    // If the operand is an instruction that became dead as we nulled out the
    // operand, and if it is 'trivially' dead, delete it in a future loop
    // iteration.
    if (Instruction *OpI = dyn_cast<Instruction>(OpV))
      if (isInstructionTriviallyDead(OpI, TLI))
        WorkList.insert(OpI);
  }

  I->eraseFromParent();

  return true;
}

if (Value *SimpleV = SimplifyInstruction(I, DL)) {
  // Add the users to the worklist. CAREFUL: an instruction can use itself,
  // in the case of a phi node.
  for (User *U : I->users()) {
    if (U != I) {
      WorkList.insert(cast<Instruction>(U));
    }
  }

  // Replace the instruction with its simplified value.
  bool Changed = false;
  if (!I->use_empty()) {
    I->replaceAllUsesWith(SimpleV);
    Changed = true;
  }
  if (isInstructionTriviallyDead(I, TLI)) {
    I->eraseFromParent();
    Changed = true;
  }
  return Changed;
}
return false;
694}

696/// SimplifyInstructionsInBlock - Scan the specified basic block and try to
697/// simplify any instructions in it and recursively delete dead instructions.
698///
699/// This returns true if it changed the code, note that it can delete
700/// instructions in other blocks as well in this block.
701bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB,
                                     const TargetLibraryInfo *TLI) {
bool MadeChange = false;
const DataLayout &DL = BB->getModule()->getDataLayout();

706#ifndef NDEBUG1
// In debug builds, ensure that the terminator of the block is never replaced
// or deleted by these simplifications. The idea of simplification is that it
// cannot introduce new instructions, and there is no way to replace the
// terminator of a block without introducing a new instruction.
AssertingVH<Instruction> TerminatorVH(&BB->back());
712#endif

SmallSetVector<Instruction *, 16> WorkList;
// Iterate over the original function, only adding insts to the worklist
// if they actually need to be revisited. This avoids having to pre-init
// the worklist with the entire function's worth of instructions.
for (BasicBlock::iterator BI = BB->begin(), E = std::prev(BB->end());
     BI != E;) {
  assert(!BI->isTerminator())(static_cast<void> (0));
  Instruction *I = &*BI;
  ++BI;

  // We're visiting this instruction now, so make sure it's not in the
  // worklist from an earlier visit.
  if (!WorkList.count(I))
    MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI);
}

while (!WorkList.empty()) {
  Instruction *I = WorkList.pop_back_val();
  MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI);
}
return MadeChange;
735}

737//===----------------------------------------------------------------------===//
738//  Control Flow Graph Restructuring.
739//

741void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB,
                                     DomTreeUpdater *DTU) {

// If BB has single-entry PHI nodes, fold them.
while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {
  Value *NewVal = PN->getIncomingValue(0);
  // Replace self referencing PHI with undef, it must be dead.
  if (NewVal == PN) NewVal = UndefValue::get(PN->getType());
  PN->replaceAllUsesWith(NewVal);
  PN->eraseFromParent();
}

BasicBlock *PredBB = DestBB->getSinglePredecessor();
assert(PredBB && "Block doesn't have a single predecessor!")(static_cast<void> (0));

bool ReplaceEntryBB = PredBB->isEntryBlock();

// DTU updates: Collect all the edges that enter
// PredBB. These dominator edges will be redirected to DestBB.
SmallVector<DominatorTree::UpdateType, 32> Updates;

if (DTU) {
  SmallPtrSet<BasicBlock *, 2> PredsOfPredBB(pred_begin(PredBB),
                                             pred_end(PredBB));
  Updates.reserve(Updates.size() + 2 * PredsOfPredBB.size() + 1);
  for (BasicBlock *PredOfPredBB : PredsOfPredBB)
    // This predecessor of PredBB may already have DestBB as a successor.
    if (PredOfPredBB != PredBB)
      Updates.push_back({DominatorTree::Insert, PredOfPredBB, DestBB});
  for (BasicBlock *PredOfPredBB : PredsOfPredBB)
    Updates.push_back({DominatorTree::Delete, PredOfPredBB, PredBB});
  Updates.push_back({DominatorTree::Delete, PredBB, DestBB});
}

// Zap anything that took the address of DestBB.  Not doing this will give the
// address an invalid value.
if (DestBB->hasAddressTaken()) {
  BlockAddress *BA = BlockAddress::get(DestBB);
  Constant *Replacement =
    ConstantInt::get(Type::getInt32Ty(BA->getContext()), 1);
  BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
                                                   BA->getType()));
  BA->destroyConstant();
}

// Anything that branched to PredBB now branches to DestBB.
PredBB->replaceAllUsesWith(DestBB);

// Splice all the instructions from PredBB to DestBB.
PredBB->getTerminator()->eraseFromParent();
DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());
new UnreachableInst(PredBB->getContext(), PredBB);

// If the PredBB is the entry block of the function, move DestBB up to
// become the entry block after we erase PredBB.
if (ReplaceEntryBB)
  DestBB->moveAfter(PredBB);

if (DTU) {
  assert(PredBB->getInstList().size() == 1 &&(static_cast<void> (0))
         isa<UnreachableInst>(PredBB->getTerminator()) &&(static_cast<void> (0))
         "The successor list of PredBB isn't empty before "(static_cast<void> (0))
         "applying corresponding DTU updates.")(static_cast<void> (0));
  DTU->applyUpdatesPermissive(Updates);
  DTU->deleteBB(PredBB);
  // Recalculation of DomTree is needed when updating a forward DomTree and
  // the Entry BB is replaced.
  if (ReplaceEntryBB && DTU->hasDomTree()) {
    // The entry block was removed and there is no external interface for
    // the dominator tree to be notified of this change. In this corner-case
    // we recalculate the entire tree.
    DTU->recalculate(*(DestBB->getParent()));
  }
}

else {
  PredBB->eraseFromParent(); // Nuke BB if DTU is nullptr.
}
819}

821/// Return true if we can choose one of these values to use in place of the
822/// other. Note that we will always choose the non-undef value to keep.
823static bool CanMergeValues(Value *First, Value *Second) {
return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second);
825}

827/// Return true if we can fold BB, an almost-empty BB ending in an unconditional
828/// branch to Succ, into Succ.
829///
830/// Assumption: Succ is the single successor for BB.
831static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) {
assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!")(static_cast<void> (0));

LLVM_DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into "do { } while (false)
                  << Succ->getName() << "\n")do { } while (false);
// Shortcut, if there is only a single predecessor it must be BB and merging
// is always safe
if (Succ->getSinglePredecessor()) return true;

// Make a list of the predecessors of BB
SmallPtrSet<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB));

// Look at all the phi nodes in Succ, to see if they present a conflict when
// merging these blocks
for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
  PHINode *PN = cast<PHINode>(I);

  // If the incoming value from BB is again a PHINode in
  // BB which has the same incoming value for *PI as PN does, we can
  // merge the phi nodes and then the blocks can still be merged
  PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB));
  if (BBPN && BBPN->getParent() == BB) {
    for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
      BasicBlock *IBB = PN->getIncomingBlock(PI);
      if (BBPreds.count(IBB) &&
          !CanMergeValues(BBPN->getIncomingValueForBlock(IBB),
                          PN->getIncomingValue(PI))) {
        LLVM_DEBUG(dbgs()do { } while (false)
                   << "Can't fold, phi node " << PN->getName() << " in "do { } while (false)
                   << Succ->getName() << " is conflicting with "do { } while (false)
                   << BBPN->getName() << " with regard to common predecessor "do { } while (false)
                   << IBB->getName() << "\n")do { } while (false);
        return false;
      }
    }
  } else {
    Value* Val = PN->getIncomingValueForBlock(BB);
    for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
      // See if the incoming value for the common predecessor is equal to the
      // one for BB, in which case this phi node will not prevent the merging
      // of the block.
      BasicBlock *IBB = PN->getIncomingBlock(PI);
      if (BBPreds.count(IBB) &&
          !CanMergeValues(Val, PN->getIncomingValue(PI))) {
        LLVM_DEBUG(dbgs() << "Can't fold, phi node " << PN->getName()do { } while (false)
                          << " in " << Succ->getName()do { } while (false)
                          << " is conflicting with regard to common "do { } while (false)
                          << "predecessor " << IBB->getName() << "\n")do { } while (false);
        return false;
      }
    }
  }
}

return true;
886}

888using PredBlockVector = SmallVector<BasicBlock *, 16>;
889using IncomingValueMap = DenseMap<BasicBlock *, Value *>;

891/// Determines the value to use as the phi node input for a block.
892///
893/// Select between \p OldVal any value that we know flows from \p BB
894/// to a particular phi on the basis of which one (if either) is not
895/// undef. Update IncomingValues based on the selected value.
896///
897/// \param OldVal The value we are considering selecting.
898/// \param BB The block that the value flows in from.
899/// \param IncomingValues A map from block-to-value for other phi inputs
900/// that we have examined.
901///
902/// \returns the selected value.
903static Value *selectIncomingValueForBlock(Value *OldVal, BasicBlock *BB,
                                        IncomingValueMap &IncomingValues) {
if (!isa<UndefValue>(OldVal)) {
  assert((!IncomingValues.count(BB) ||(static_cast<void> (0))
          IncomingValues.find(BB)->second == OldVal) &&(static_cast<void> (0))
         "Expected OldVal to match incoming value from BB!")(static_cast<void> (0));

  IncomingValues.insert(std::make_pair(BB, OldVal));
  return OldVal;
}

IncomingValueMap::const_iterator It = IncomingValues.find(BB);
if (It != IncomingValues.end()) return It->second;

return OldVal;
918}

920/// Create a map from block to value for the operands of a
921/// given phi.
922///
923/// Create a map from block to value for each non-undef value flowing
924/// into \p PN.
925///
926/// \param PN The phi we are collecting the map for.
927/// \param IncomingValues [out] The map from block to value for this phi.
928static void gatherIncomingValuesToPhi(PHINode *PN,
                                    IncomingValueMap &IncomingValues) {
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
  BasicBlock *BB = PN->getIncomingBlock(i);
  Value *V = PN->getIncomingValue(i);

  if (!isa<UndefValue>(V))
    IncomingValues.insert(std::make_pair(BB, V));
}
937}

939/// Replace the incoming undef values to a phi with the values
940/// from a block-to-value map.
941///
942/// \param PN The phi we are replacing the undefs in.
943/// \param IncomingValues A map from block to value.
944static void replaceUndefValuesInPhi(PHINode *PN,
                                  const IncomingValueMap &IncomingValues) {
SmallVector<unsigned> TrueUndefOps;
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
  Value *V = PN->getIncomingValue(i);

  if (!isa<UndefValue>(V)) continue;

  BasicBlock *BB = PN->getIncomingBlock(i);
  IncomingValueMap::const_iterator It = IncomingValues.find(BB);

  // Keep track of undef/poison incoming values. Those must match, so we fix
  // them up below if needed.
  // Note: this is conservatively correct, but we could try harder and group
  // the undef values per incoming basic block.
  if (It == IncomingValues.end()) {
    TrueUndefOps.push_back(i);
    continue;
  }

  // There is a defined value for this incoming block, so map this undef
  // incoming value to the defined value.
  PN->setIncomingValue(i, It->second);
}

// If there are both undef and poison values incoming, then convert those
// values to undef. It is invalid to have different values for the same
// incoming block.
unsigned PoisonCount = count_if(TrueUndefOps, [&](unsigned i) {
  return isa<PoisonValue>(PN->getIncomingValue(i));
});
if (PoisonCount != 0 && PoisonCount != TrueUndefOps.size()) {
  for (unsigned i : TrueUndefOps)
    PN->setIncomingValue(i, UndefValue::get(PN->getType()));
}
979}

981/// Replace a value flowing from a block to a phi with
982/// potentially multiple instances of that value flowing from the
983/// block's predecessors to the phi.
984///
985/// \param BB The block with the value flowing into the phi.
986/// \param BBPreds The predecessors of BB.
987/// \param PN The phi that we are updating.
988static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB,
                                              const PredBlockVector &BBPreds,
                                              PHINode *PN) {
Value *OldVal = PN->removeIncomingValue(BB, false);
assert(OldVal && "No entry in PHI for Pred BB!")(static_cast<void> (0));

IncomingValueMap IncomingValues;

// We are merging two blocks - BB, and the block containing PN - and
// as a result we need to redirect edges from the predecessors of BB
// to go to the block containing PN, and update PN
// accordingly. Since we allow merging blocks in the case where the
// predecessor and successor blocks both share some predecessors,
// and where some of those common predecessors might have undef
// values flowing into PN, we want to rewrite those values to be
// consistent with the non-undef values.

gatherIncomingValuesToPhi(PN, IncomingValues);

// If this incoming value is one of the PHI nodes in BB, the new entries
// in the PHI node are the entries from the old PHI.
if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
  PHINode *OldValPN = cast<PHINode>(OldVal);
  for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) {
    // Note that, since we are merging phi nodes and BB and Succ might
    // have common predecessors, we could end up with a phi node with
    // identical incoming branches. This will be cleaned up later (and
    // will trigger asserts if we try to clean it up now, without also
    // simplifying the corresponding conditional branch).
    BasicBlock *PredBB = OldValPN->getIncomingBlock(i);
    Value *PredVal = OldValPN->getIncomingValue(i);
    Value *Selected = selectIncomingValueForBlock(PredVal, PredBB,
                                                  IncomingValues);

    // And add a new incoming value for this predecessor for the
    // newly retargeted branch.
    PN->addIncoming(Selected, PredBB);
  }
} else {
  for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) {
    // Update existing incoming values in PN for this
    // predecessor of BB.
    BasicBlock *PredBB = BBPreds[i];
    Value *Selected = selectIncomingValueForBlock(OldVal, PredBB,
                                                  IncomingValues);

    // And add a new incoming value for this predecessor for the
    // newly retargeted branch.
    PN->addIncoming(Selected, PredBB);
  }
}

replaceUndefValuesInPhi(PN, IncomingValues);
1041}

1043bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
                                                 DomTreeUpdater *DTU) {
assert(BB != &BB->getParent()->getEntryBlock() &&(static_cast<void> (0))
       "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!")(static_cast<void> (0));

// We can't eliminate infinite loops.
BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0);
if (BB == Succ) return false;

// Check to see if merging these blocks would cause conflicts for any of the
// phi nodes in BB or Succ. If not, we can safely merge.
if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false;

// Check for cases where Succ has multiple predecessors and a PHI node in BB
// has uses which will not disappear when the PHI nodes are merged.  It is
// possible to handle such cases, but difficult: it requires checking whether
// BB dominates Succ, which is non-trivial to calculate in the case where
// Succ has multiple predecessors.  Also, it requires checking whether
// constructing the necessary self-referential PHI node doesn't introduce any
// conflicts; this isn't too difficult, but the previous code for doing this
// was incorrect.
//
// Note that if this check finds a live use, BB dominates Succ, so BB is
// something like a loop pre-header (or rarely, a part of an irreducible CFG);
// folding the branch isn't profitable in that case anyway.
if (!Succ->getSinglePredecessor()) {
  BasicBlock::iterator BBI = BB->begin();
  while (isa<PHINode>(*BBI)) {
    for (Use &U : BBI->uses()) {
      if (PHINode* PN = dyn_cast<PHINode>(U.getUser())) {
        if (PN->getIncomingBlock(U) != BB)
          return false;
      } else {
        return false;
      }
    }
    ++BBI;
  }
}

// We cannot fold the block if it's a branch to an already present callbr
// successor because that creates duplicate successors.
for (BasicBlock *PredBB : predecessors(BB)) {
  if (auto *CBI = dyn_cast<CallBrInst>(PredBB->getTerminator())) {
    if (Succ == CBI->getDefaultDest())
      return false;
    for (unsigned i = 0, e = CBI->getNumIndirectDests(); i != e; ++i)
      if (Succ == CBI->getIndirectDest(i))
        return false;
  }
}

LLVM_DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB)do { } while (false);

SmallVector<DominatorTree::UpdateType, 32> Updates;
if (DTU) {
  // All predecessors of BB will be moved to Succ.
  SmallPtrSet<BasicBlock *, 8> PredsOfBB(pred_begin(BB), pred_end(BB));
  SmallPtrSet<BasicBlock *, 8> PredsOfSucc(pred_begin(Succ), pred_end(Succ));
  Updates.reserve(Updates.size() + 2 * PredsOfBB.size() + 1);
  for (auto *PredOfBB : PredsOfBB)
    // This predecessor of BB may already have Succ as a successor.
    if (!PredsOfSucc.contains(PredOfBB))
      Updates.push_back({DominatorTree::Insert, PredOfBB, Succ});
  for (auto *PredOfBB : PredsOfBB)
    Updates.push_back({DominatorTree::Delete, PredOfBB, BB});
  Updates.push_back({DominatorTree::Delete, BB, Succ});
}

if (isa<PHINode>(Succ->begin())) {
  // If there is more than one pred of succ, and there are PHI nodes in
  // the successor, then we need to add incoming edges for the PHI nodes
  //
  const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB));

  // Loop over all of the PHI nodes in the successor of BB.
  for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
    PHINode *PN = cast<PHINode>(I);

    redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN);
  }
}

if (Succ->getSinglePredecessor()) {
  // BB is the only predecessor of Succ, so Succ will end up with exactly
  // the same predecessors BB had.

  // Copy over any phi, debug or lifetime instruction.
  BB->getTerminator()->eraseFromParent();
  Succ->getInstList().splice(Succ->getFirstNonPHI()->getIterator(),
                             BB->getInstList());
} else {
  while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
    // We explicitly check for such uses in CanPropagatePredecessorsForPHIs.
    assert(PN->use_empty() && "There shouldn't be any uses here!")(static_cast<void> (0));
    PN->eraseFromParent();
  }
}

// If the unconditional branch we replaced contains llvm.loop metadata, we
// add the metadata to the branch instructions in the predecessors.
unsigned LoopMDKind = BB->getContext().getMDKindID("llvm.loop");
Instruction *TI = BB->getTerminator();
if (TI)
  if (MDNode *LoopMD = TI->getMetadata(LoopMDKind))
    for (BasicBlock *Pred : predecessors(BB))
      Pred->getTerminator()->setMetadata(LoopMDKind, LoopMD);

// Everything that jumped to BB now goes to Succ.
BB->replaceAllUsesWith(Succ);
if (!Succ->hasName()) Succ->takeName(BB);

// Clear the successor list of BB to match updates applying to DTU later.
if (BB->getTerminator())
  BB->getInstList().pop_back();
new UnreachableInst(BB->getContext(), BB);
assert(succ_empty(BB) && "The successor list of BB isn't empty before "(static_cast<void> (0))
                         "applying corresponding DTU updates.")(static_cast<void> (0));

if (DTU)
  DTU->applyUpdates(Updates);

DeleteDeadBlock(BB, DTU);

return true;
1168}

1170static bool EliminateDuplicatePHINodesNaiveImpl(BasicBlock *BB) {
// This implementation doesn't currently consider undef operands
// specially. Theoretically, two phis which are identical except for
// one having an undef where the other doesn't could be collapsed.

bool Changed = false;

// Examine each PHI.
// Note that increment of I must *NOT* be in the iteration_expression, since
// we don't want to immediately advance when we restart from the beginning.
for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I);) {
  ++I;
  // Is there an identical PHI node in this basic block?
  // Note that we only look in the upper square's triangle,
  // we already checked that the lower triangle PHI's aren't identical.
  for (auto J = I; PHINode *DuplicatePN = dyn_cast<PHINode>(J); ++J) {
    if (!DuplicatePN->isIdenticalToWhenDefined(PN))
      continue;
    // A duplicate. Replace this PHI with the base PHI.
    ++NumPHICSEs;
    DuplicatePN->replaceAllUsesWith(PN);
    DuplicatePN->eraseFromParent();
    Changed = true;

    // The RAUW can change PHIs that we already visited.
    I = BB->begin();
    break; // Start over from the beginning.
  }
}
return Changed;
1200}

1202static bool EliminateDuplicatePHINodesSetBasedImpl(BasicBlock *BB) {
// This implementation doesn't currently consider undef operands
// specially. Theoretically, two phis which are identical except for
// one having an undef where the other doesn't could be collapsed.

struct PHIDenseMapInfo {
  static PHINode *getEmptyKey() {
    return DenseMapInfo<PHINode *>::getEmptyKey();
  }

  static PHINode *getTombstoneKey() {
    return DenseMapInfo<PHINode *>::getTombstoneKey();
  }

  static bool isSentinel(PHINode *PN) {
    return PN == getEmptyKey() || PN == getTombstoneKey();
  }

  // WARNING: this logic must be kept in sync with
  //          Instruction::isIdenticalToWhenDefined()!
  static unsigned getHashValueImpl(PHINode *PN) {
    // Compute a hash value on the operands. Instcombine will likely have
    // sorted them, which helps expose duplicates, but we have to check all
    // the operands to be safe in case instcombine hasn't run.
    return static_cast<unsigned>(hash_combine(
        hash_combine_range(PN->value_op_begin(), PN->value_op_end()),
        hash_combine_range(PN->block_begin(), PN->block_end())));
  }

  static unsigned getHashValue(PHINode *PN) {
1232#ifndef NDEBUG1
    // If -phicse-debug-hash was specified, return a constant -- this
    // will force all hashing to collide, so we'll exhaustively search
    // the table for a match, and the assertion in isEqual will fire if
    // there's a bug causing equal keys to hash differently.
    if (PHICSEDebugHash)
      return 0;
1239#endif
    return getHashValueImpl(PN);
  }

  static bool isEqualImpl(PHINode *LHS, PHINode *RHS) {
    if (isSentinel(LHS) || isSentinel(RHS))
      return LHS == RHS;
    return LHS->isIdenticalTo(RHS);
  }

  static bool isEqual(PHINode *LHS, PHINode *RHS) {
    // These comparisons are nontrivial, so assert that equality implies
    // hash equality (DenseMap demands this as an invariant).
    bool Result = isEqualImpl(LHS, RHS);
    assert(!Result || (isSentinel(LHS) && LHS == RHS) ||(static_cast<void> (0))
           getHashValueImpl(LHS) == getHashValueImpl(RHS))(static_cast<void> (0));
    return Result;
  }
};

// Set of unique PHINodes.
DenseSet<PHINode *, PHIDenseMapInfo> PHISet;
PHISet.reserve(4 * PHICSENumPHISmallSize);

// Examine each PHI.
bool Changed = false;
for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I++);) {
  auto Inserted = PHISet.insert(PN);
  if (!Inserted.second) {
    // A duplicate. Replace this PHI with its duplicate.
    ++NumPHICSEs;
    PN->replaceAllUsesWith(*Inserted.first);
    PN->eraseFromParent();
    Changed = true;

    // The RAUW can change PHIs that we already visited. Start over from the
    // beginning.
    PHISet.clear();
    I = BB->begin();
  }
}

return Changed;
1282}

1284bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) {
if (
1286#ifndef NDEBUG1
    !PHICSEDebugHash &&
1288#endif
    hasNItemsOrLess(BB->phis(), PHICSENumPHISmallSize))
  return EliminateDuplicatePHINodesNaiveImpl(BB);
return EliminateDuplicatePHINodesSetBasedImpl(BB);
1292}

1294/// If the specified pointer points to an object that we control, try to modify
1295/// the object's alignment to PrefAlign. Returns a minimum known alignment of
1296/// the value after the operation, which may be lower than PrefAlign.
1297///
1298/// Increating value alignment isn't often possible though. If alignment is
1299/// important, a more reliable approach is to simply align all global variables
1300/// and allocation instructions to their preferred alignment from the beginning.
1301static Align tryEnforceAlignment(Value *V, Align PrefAlign,
                               const DataLayout &DL) {
V = V->stripPointerCasts();

if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
  // TODO: Ideally, this function would not be called if PrefAlign is smaller
  // than the current alignment, as the known bits calculation should have
  // already taken it into account. However, this is not always the case,
  // as computeKnownBits() has a depth limit, while stripPointerCasts()
  // doesn't.
  Align CurrentAlign = AI->getAlign();
  if (PrefAlign <= CurrentAlign)
    return CurrentAlign;

  // If the preferred alignment is greater than the natural stack alignment
  // then don't round up. This avoids dynamic stack realignment.
  if (DL.exceedsNaturalStackAlignment(PrefAlign))
    return CurrentAlign;
  AI->setAlignment(PrefAlign);
  return PrefAlign;
}

if (auto *GO = dyn_cast<GlobalObject>(V)) {
  // TODO: as above, this shouldn't be necessary.
  Align CurrentAlign = GO->getPointerAlignment(DL);
  if (PrefAlign <= CurrentAlign)
    return CurrentAlign;

  // If there is a large requested alignment and we can, bump up the alignment
  // of the global.  If the memory we set aside for the global may not be the
  // memory used by the final program then it is impossible for us to reliably
  // enforce the preferred alignment.
  if (!GO->canIncreaseAlignment())
    return CurrentAlign;

  GO->setAlignment(PrefAlign);
  return PrefAlign;
}

return Align(1);
1341}

1343Align llvm::getOrEnforceKnownAlignment(Value *V, MaybeAlign PrefAlign,
                                     const DataLayout &DL,
                                     const Instruction *CxtI,
                                     AssumptionCache *AC,
                                     const DominatorTree *DT) {
assert(V->getType()->isPointerTy() &&(static_cast<void> (0))
       "getOrEnforceKnownAlignment expects a pointer!")(static_cast<void> (0));

KnownBits Known = computeKnownBits(V, DL, 0, AC, CxtI, DT);
unsigned TrailZ = Known.countMinTrailingZeros();

// Avoid trouble with ridiculously large TrailZ values, such as
// those computed from a null pointer.
// LLVM doesn't support alignments larger than (1 << MaxAlignmentExponent).
TrailZ = std::min(TrailZ, +Value::MaxAlignmentExponent);

Align Alignment = Align(1ull << std::min(Known.getBitWidth() - 1, TrailZ));

if (PrefAlign && *PrefAlign > Alignment)
  Alignment = std::max(Alignment, tryEnforceAlignment(V, *PrefAlign, DL));

// We don't need to make any adjustment.
return Alignment;
1366}

1368///===---------------------------------------------------------------------===//
1369///  Dbg Intrinsic utilities
1370///

1372/// See if there is a dbg.value intrinsic for DIVar for the PHI node.
1373static bool PhiHasDebugValue(DILocalVariable *DIVar,
                           DIExpression *DIExpr,
                           PHINode *APN) {
// Since we can't guarantee that the original dbg.declare instrinsic
// is removed by LowerDbgDeclare(), we need to make sure that we are
// not inserting the same dbg.value intrinsic over and over.
SmallVector<DbgValueInst *, 1> DbgValues;
findDbgValues(DbgValues, APN);
for (auto *DVI : DbgValues) {
  assert(is_contained(DVI->getValues(), APN))(static_cast<void> (0));
  if ((DVI->getVariable() == DIVar) && (DVI->getExpression() == DIExpr))
    return true;
}
return false;
1387}

1389/// Check if the alloc size of \p ValTy is large enough to cover the variable
1390/// (or fragment of the variable) described by \p DII.
1391///
1392/// This is primarily intended as a helper for the different
1393/// ConvertDebugDeclareToDebugValue functions. The dbg.declare/dbg.addr that is
1394/// converted describes an alloca'd variable, so we need to use the
1395/// alloc size of the value when doing the comparison. E.g. an i1 value will be
1396/// identified as covering an n-bit fragment, if the store size of i1 is at
1397/// least n bits.
1398static bool valueCoversEntireFragment(Type *ValTy, DbgVariableIntrinsic *DII) {
const DataLayout &DL = DII->getModule()->getDataLayout();
TypeSize ValueSize = DL.getTypeAllocSizeInBits(ValTy);
if (Optional<uint64_t> FragmentSize = DII->getFragmentSizeInBits()) {
  assert(!ValueSize.isScalable() &&(static_cast<void> (0))
         "Fragments don't work on scalable types.")(static_cast<void> (0));
  return ValueSize.getFixedSize() >= *FragmentSize;
}
// We can't always calculate the size of the DI variable (e.g. if it is a
// VLA). Try to use the size of the alloca that the dbg intrinsic describes
// intead.
if (DII->isAddressOfVariable()) {
  // DII should have exactly 1 location when it is an address.
  assert(DII->getNumVariableLocationOps() == 1 &&(static_cast<void> (0))
         "address of variable must have exactly 1 location operand.")(static_cast<void> (0));
  if (auto *AI =
          dyn_cast_or_null<AllocaInst>(DII->getVariableLocationOp(0))) {
    if (Optional<TypeSize> FragmentSize = AI->getAllocationSizeInBits(DL)) {
      assert(ValueSize.isScalable() == FragmentSize->isScalable() &&(static_cast<void> (0))
             "Both sizes should agree on the scalable flag.")(static_cast<void> (0));
      return TypeSize::isKnownGE(ValueSize, *FragmentSize);
    }
  }
}
// Could not determine size of variable. Conservatively return false.
return false;
1424}

1426/// Produce a DebugLoc to use for each dbg.declare/inst pair that are promoted
1427/// to a dbg.value. Because no machine insts can come from debug intrinsics,
1428/// only the scope and inlinedAt is significant. Zero line numbers are used in
1429/// case this DebugLoc leaks into any adjacent instructions.
1430static DebugLoc getDebugValueLoc(DbgVariableIntrinsic *DII, Instruction *Src) {
// Original dbg.declare must have a location.
const DebugLoc &DeclareLoc = DII->getDebugLoc();
MDNode *Scope = DeclareLoc.getScope();
DILocation *InlinedAt = DeclareLoc.getInlinedAt();
// Produce an unknown location with the correct scope / inlinedAt fields.
return DILocation::get(DII->getContext(), 0, 0, Scope, InlinedAt);
1437}

1439/// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value
1440/// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic.
1441void llvm::ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII,
                                         StoreInst *SI, DIBuilder &Builder) {
assert(DII->isAddressOfVariable())(static_cast<void> (0));
auto *DIVar = DII->getVariable();
assert(DIVar && "Missing variable")(static_cast<void> (0));
auto *DIExpr = DII->getExpression();
Value *DV = SI->getValueOperand();

DebugLoc NewLoc = getDebugValueLoc(DII, SI);

if (!valueCoversEntireFragment(DV->getType(), DII)) {
  // FIXME: If storing to a part of the variable described by the dbg.declare,
  // then we want to insert a dbg.value for the corresponding fragment.
  LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: "do { } while (false)
                    << *DII << '\n')do { } while (false);
  // For now, when there is a store to parts of the variable (but we do not
  // know which part) we insert an dbg.value instrinsic to indicate that we
  // know nothing about the variable's content.
  DV = UndefValue::get(DV->getType());
  Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, NewLoc, SI);
  return;
}

Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, NewLoc, SI);
1465}

1467/// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value
1468/// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic.
1469void llvm::ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII,
                                         LoadInst *LI, DIBuilder &Builder) {
auto *DIVar = DII->getVariable();
auto *DIExpr = DII->getExpression();
assert(DIVar && "Missing variable")(static_cast<void> (0));

if (!valueCoversEntireFragment(LI->getType(), DII)) {
  // FIXME: If only referring to a part of the variable described by the
  // dbg.declare, then we want to insert a dbg.value for the corresponding
  // fragment.
  LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: "do { } while (false)
                    << *DII << '\n')do { } while (false);
  return;
}

DebugLoc NewLoc = getDebugValueLoc(DII, nullptr);

// We are now tracking the loaded value instead of the address. In the
// future if multi-location support is added to the IR, it might be
// preferable to keep tracking both the loaded value and the original
// address in case the alloca can not be elided.
Instruction *DbgValue = Builder.insertDbgValueIntrinsic(
    LI, DIVar, DIExpr, NewLoc, (Instruction *)nullptr);
DbgValue->insertAfter(LI);
1493}

1495/// Inserts a llvm.dbg.value intrinsic after a phi that has an associated
1496/// llvm.dbg.declare or llvm.dbg.addr intrinsic.
1497void llvm::ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII,
                                         PHINode *APN, DIBuilder &Builder) {
auto *DIVar = DII->getVariable();
auto *DIExpr = DII->getExpression();
assert(DIVar && "Missing variable")(static_cast<void> (0));

if (PhiHasDebugValue(DIVar, DIExpr, APN))
  return;

if (!valueCoversEntireFragment(APN->getType(), DII)) {
  // FIXME: If only referring to a part of the variable described by the
  // dbg.declare, then we want to insert a dbg.value for the corresponding
  // fragment.
  LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: "do { } while (false)
                    << *DII << '\n')do { } while (false);
  return;
}

BasicBlock *BB = APN->getParent();
auto InsertionPt = BB->getFirstInsertionPt();

DebugLoc NewLoc = getDebugValueLoc(DII, nullptr);

// The block may be a catchswitch block, which does not have a valid
// insertion point.
// FIXME: Insert dbg.value markers in the successors when appropriate.
if (InsertionPt != BB->end())
  Builder.insertDbgValueIntrinsic(APN, DIVar, DIExpr, NewLoc, &*InsertionPt);
1525}

1527/// Determine whether this alloca is either a VLA or an array.
1528static bool isArray(AllocaInst *AI) {
return AI->isArrayAllocation() ||
       (AI->getAllocatedType() && AI->getAllocatedType()->isArrayTy());
1531}

1533/// Determine whether this alloca is a structure.
1534static bool isStructure(AllocaInst *AI) {
return AI->getAllocatedType() && AI->getAllocatedType()->isStructTy();
1536}

1538/// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set
1539/// of llvm.dbg.value intrinsics.
1540bool llvm::LowerDbgDeclare(Function &F) {
bool Changed = false;
DIBuilder DIB(*F.getParent(), /*AllowUnresolved*/ false);
SmallVector<DbgDeclareInst *, 4> Dbgs;
for (auto &FI : F)
  for (Instruction &BI : FI)
    if (auto DDI = dyn_cast<DbgDeclareInst>(&BI))
      Dbgs.push_back(DDI);

if (Dbgs.empty())
  return Changed;

for (auto &I : Dbgs) {
  DbgDeclareInst *DDI = I;
  AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress());
  // If this is an alloca for a scalar variable, insert a dbg.value
  // at each load and store to the alloca and erase the dbg.declare.
  // The dbg.values allow tracking a variable even if it is not
  // stored on the stack, while the dbg.declare can only describe
  // the stack slot (and at a lexical-scope granularity). Later
  // passes will attempt to elide the stack slot.
  if (!AI || isArray(AI) || isStructure(AI))
    continue;

  // A volatile load/store means that the alloca can't be elided anyway.
  if (llvm::any_of(AI->users(), [](User *U) -> bool {
        if (LoadInst *LI = dyn_cast<LoadInst>(U))
          return LI->isVolatile();
        if (StoreInst *SI = dyn_cast<StoreInst>(U))
          return SI->isVolatile();
        return false;
      }))
    continue;

  SmallVector<const Value *, 8> WorkList;
  WorkList.push_back(AI);
  while (!WorkList.empty()) {
    const Value *V = WorkList.pop_back_val();
    for (auto &AIUse : V->uses()) {
      User *U = AIUse.getUser();
      if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
        if (AIUse.getOperandNo() == 1)
          ConvertDebugDeclareToDebugValue(DDI, SI, DIB);
      } else if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
        ConvertDebugDeclareToDebugValue(DDI, LI, DIB);
      } else if (CallInst *CI = dyn_cast<CallInst>(U)) {
        // This is a call by-value or some other instruction that takes a
        // pointer to the variable. Insert a *value* intrinsic that describes
        // the variable by dereferencing the alloca.
        if (!CI->isLifetimeStartOrEnd()) {
          DebugLoc NewLoc = getDebugValueLoc(DDI, nullptr);
          auto *DerefExpr =
              DIExpression::append(DDI->getExpression(), dwarf::DW_OP_deref);
          DIB.insertDbgValueIntrinsic(AI, DDI->getVariable(), DerefExpr,
                                      NewLoc, CI);
        }
      } else if (BitCastInst *BI = dyn_cast<BitCastInst>(U)) {
        if (BI->getType()->isPointerTy())
          WorkList.push_back(BI);
      }
    }
  }
  DDI->eraseFromParent();
  Changed = true;
}

if (Changed)
for (BasicBlock &BB : F)
  RemoveRedundantDbgInstrs(&BB);

return Changed;
1611}

1613/// Propagate dbg.value intrinsics through the newly inserted PHIs.
1614void llvm::insertDebugValuesForPHIs(BasicBlock *BB,
                                  SmallVectorImpl<PHINode *> &InsertedPHIs) {
assert(BB && "No BasicBlock to clone dbg.value(s) from.")(static_cast<void> (0));
if (InsertedPHIs.size() == 0)
  return;

// Map existing PHI nodes to their dbg.values.
ValueToValueMapTy DbgValueMap;
for (auto &I : *BB) {
  if (auto DbgII = dyn_cast<DbgVariableIntrinsic>(&I)) {
    for (Value *V : DbgII->location_ops())
      if (auto *Loc = dyn_cast_or_null<PHINode>(V))
        DbgValueMap.insert({Loc, DbgII});
  }
}
if (DbgValueMap.size() == 0)
  return;

// Map a pair of the destination BB and old dbg.value to the new dbg.value,
// so that if a dbg.value is being rewritten to use more than one of the
// inserted PHIs in the same destination BB, we can update the same dbg.value
// with all the new PHIs instead of creating one copy for each.
MapVector<std::pair<BasicBlock *, DbgVariableIntrinsic *>,
          DbgVariableIntrinsic *>
    NewDbgValueMap;
// Then iterate through the new PHIs and look to see if they use one of the
// previously mapped PHIs. If so, create a new dbg.value intrinsic that will
// propagate the info through the new PHI. If we use more than one new PHI in
// a single destination BB with the same old dbg.value, merge the updates so
// that we get a single new dbg.value with all the new PHIs.
for (auto PHI : InsertedPHIs) {
  BasicBlock *Parent = PHI->getParent();
  // Avoid inserting an intrinsic into an EH block.
  if (Parent->getFirstNonPHI()->isEHPad())
    continue;
  for (auto VI : PHI->operand_values()) {
    auto V = DbgValueMap.find(VI);
    if (V != DbgValueMap.end()) {
      auto *DbgII = cast<DbgVariableIntrinsic>(V->second);
      auto NewDI = NewDbgValueMap.find({Parent, DbgII});
      if (NewDI == NewDbgValueMap.end()) {
        auto *NewDbgII = cast<DbgVariableIntrinsic>(DbgII->clone());
        NewDI = NewDbgValueMap.insert({{Parent, DbgII}, NewDbgII}).first;
      }
      DbgVariableIntrinsic *NewDbgII = NewDI->second;
      // If PHI contains VI as an operand more than once, we may
      // replaced it in NewDbgII; confirm that it is present.
      if (is_contained(NewDbgII->location_ops(), VI))
        NewDbgII->replaceVariableLocationOp(VI, PHI);
    }
  }
}
// Insert thew new dbg.values into their destination blocks.
for (auto DI : NewDbgValueMap) {
  BasicBlock *Parent = DI.first.first;
  auto *NewDbgII = DI.second;
  auto InsertionPt = Parent->getFirstInsertionPt();
  assert(InsertionPt != Parent->end() && "Ill-formed basic block")(static_cast<void> (0));
  NewDbgII->insertBefore(&*InsertionPt);
}
1674}

1676bool llvm::replaceDbgDeclare(Value *Address, Value *NewAddress,
                           DIBuilder &Builder, uint8_t DIExprFlags,
                           int Offset) {
auto DbgAddrs = FindDbgAddrUses(Address);
for (DbgVariableIntrinsic *DII : DbgAddrs) {
  const DebugLoc &Loc = DII->getDebugLoc();
  auto *DIVar = DII->getVariable();
  auto *DIExpr = DII->getExpression();
  assert(DIVar && "Missing variable")(static_cast<void> (0));
  DIExpr = DIExpression::prepend(DIExpr, DIExprFlags, Offset);
  // Insert llvm.dbg.declare immediately before DII, and remove old
  // llvm.dbg.declare.
  Builder.insertDeclare(NewAddress, DIVar, DIExpr, Loc, DII);
  DII->eraseFromParent();
}
return !DbgAddrs.empty();
1692}

1694static void replaceOneDbgValueForAlloca(DbgValueInst *DVI, Value *NewAddress,
                                      DIBuilder &Builder, int Offset) {
const DebugLoc &Loc = DVI->getDebugLoc();
auto *DIVar = DVI->getVariable();
auto *DIExpr = DVI->getExpression();
assert(DIVar && "Missing variable")(static_cast<void> (0));

// This is an alloca-based llvm.dbg.value. The first thing it should do with
// the alloca pointer is dereference it. Otherwise we don't know how to handle
// it and give up.
if (!DIExpr || DIExpr->getNumElements() < 1 ||
    DIExpr->getElement(0) != dwarf::DW_OP_deref)
  return;

// Insert the offset before the first deref.
// We could just change the offset argument of dbg.value, but it's unsigned...
if (Offset)
  DIExpr = DIExpression::prepend(DIExpr, 0, Offset);

Builder.insertDbgValueIntrinsic(NewAddress, DIVar, DIExpr, Loc, DVI);
DVI->eraseFromParent();
1715}

1717void llvm::replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
                                  DIBuilder &Builder, int Offset) {
if (auto *L = LocalAsMetadata::getIfExists(AI))
  if (auto *MDV = MetadataAsValue::getIfExists(AI->getContext(), L))
    for (Use &U : llvm::make_early_inc_range(MDV->uses()))
      if (auto *DVI = dyn_cast<DbgValueInst>(U.getUser()))
        replaceOneDbgValueForAlloca(DVI, NewAllocaAddress, Builder, Offset);
1724}

1726/// Where possible to salvage debug information for \p I do so
1727/// and return True. If not possible mark undef and return False.
1728void llvm::salvageDebugInfo(Instruction &I) {
SmallVector<DbgVariableIntrinsic *, 1> DbgUsers;
findDbgUsers(DbgUsers, &I);
salvageDebugInfoForDbgValues(I, DbgUsers);
1732}

1734void llvm::salvageDebugInfoForDbgValues(
  Instruction &I, ArrayRef<DbgVariableIntrinsic *> DbgUsers) {
// This is an arbitrary chosen limit on the maximum number of values we can
// salvage up to in a DIArgList, used for performance reasons.
const unsigned MaxDebugArgs = 16;
bool Salvaged = false;

for (auto *DII : DbgUsers) {
  // Do not add DW_OP_stack_value for DbgDeclare and DbgAddr, because they
  // are implicitly pointing out the value as a DWARF memory location
  // description.
  bool StackValue = isa<DbgValueInst>(DII);
  auto DIILocation = DII->location_ops();
  assert((static_cast<void> (0))
      is_contained(DIILocation, &I) &&(static_cast<void> (0))
      "DbgVariableIntrinsic must use salvaged instruction as its location")(static_cast<void> (0));
  SmallVector<Value *, 4> AdditionalValues;
  // `I` may appear more than once in DII's location ops, and each use of `I`
  // must be updated in the DIExpression and potentially have additional
  // values added; thus we call salvageDebugInfoImpl for each `I` instance in
  // DIILocation.
  Value *Op0 = nullptr;
  DIExpression *SalvagedExpr = DII->getExpression();
  auto LocItr = find(DIILocation, &I);
  while (SalvagedExpr && LocItr != DIILocation.end()) {
    SmallVector<uint64_t, 16> Ops;
    unsigned LocNo = std::distance(DIILocation.begin(), LocItr);
    uint64_t CurrentLocOps = SalvagedExpr->getNumLocationOperands();
    Op0 = salvageDebugInfoImpl(I, CurrentLocOps, Ops, AdditionalValues);
    if (!Op0)
      break;
    SalvagedExpr =
        DIExpression::appendOpsToArg(SalvagedExpr, Ops, LocNo, StackValue);
    LocItr = std::find(++LocItr, DIILocation.end(), &I);
  }
  // salvageDebugInfoImpl should fail on examining the first element of
  // DbgUsers, or none of them.
  if (!Op0)
    break;

  DII->replaceVariableLocationOp(&I, Op0);
  if (AdditionalValues.empty()) {
    DII->setExpression(SalvagedExpr);
  } else if (isa<DbgValueInst>(DII) &&
             DII->getNumVariableLocationOps() + AdditionalValues.size() <=
                 MaxDebugArgs) {
    DII->addVariableLocationOps(AdditionalValues, SalvagedExpr);
  } else {
    // Do not salvage using DIArgList for dbg.addr/dbg.declare, as it is
    // currently only valid for stack value expressions.
    // Also do not salvage if the resulting DIArgList would contain an
    // unreasonably large number of values.
    Value *Undef = UndefValue::get(I.getOperand(0)->getType());
    DII->replaceVariableLocationOp(I.getOperand(0), Undef);
  }
  LLVM_DEBUG(dbgs() << "SALVAGE: " << *DII << '\n')do { } while (false);
  Salvaged = true;
}

if (Salvaged)
  return;

for (auto *DII : DbgUsers) {
  Value *Undef = UndefValue::get(I.getType());
  DII->replaceVariableLocationOp(&I, Undef);
}
1800}

1802Value *getSalvageOpsForGEP(GetElementPtrInst *GEP, const DataLayout &DL,
                         uint64_t CurrentLocOps,
                         SmallVectorImpl<uint64_t> &Opcodes,
                         SmallVectorImpl<Value *> &AdditionalValues) {
unsigned BitWidth = DL.getIndexSizeInBits(GEP->getPointerAddressSpace());
// Rewrite a GEP into a DIExpression.
MapVector<Value *, APInt> VariableOffsets;
APInt ConstantOffset(BitWidth, 0);
if (!GEP->collectOffset(DL, BitWidth, VariableOffsets, ConstantOffset))
  return nullptr;
if (!VariableOffsets.empty() && !CurrentLocOps) {
  Opcodes.insert(Opcodes.begin(), {dwarf::DW_OP_LLVM_arg, 0});
  CurrentLocOps = 1;
}
for (auto Offset : VariableOffsets) {
  AdditionalValues.push_back(Offset.first);
  assert(Offset.second.isStrictlyPositive() &&(static_cast<void> (0))
         "Expected strictly positive multiplier for offset.")(static_cast<void> (0));
  Opcodes.append({dwarf::DW_OP_LLVM_arg, CurrentLocOps++, dwarf::DW_OP_constu,
                  Offset.second.getZExtValue(), dwarf::DW_OP_mul,
                  dwarf::DW_OP_plus});
}
DIExpression::appendOffset(Opcodes, ConstantOffset.getSExtValue());
return GEP->getOperand(0);
1826}

1828uint64_t getDwarfOpForBinOp(Instruction::BinaryOps Opcode) {
switch (Opcode) {
case Instruction::Add:
  return dwarf::DW_OP_plus;
case Instruction::Sub:
  return dwarf::DW_OP_minus;
case Instruction::Mul:
  return dwarf::DW_OP_mul;
case Instruction::SDiv:
  return dwarf::DW_OP_div;
case Instruction::SRem:
  return dwarf::DW_OP_mod;
case Instruction::Or:
  return dwarf::DW_OP_or;
case Instruction::And:
  return dwarf::DW_OP_and;
case Instruction::Xor:
  return dwarf::DW_OP_xor;
case Instruction::Shl:
  return dwarf::DW_OP_shl;
case Instruction::LShr:
  return dwarf::DW_OP_shr;
case Instruction::AShr:
  return dwarf::DW_OP_shra;
default:
  // TODO: Salvage from each kind of binop we know about.
  return 0;
}
1856}

1858Value *getSalvageOpsForBinOp(BinaryOperator *BI, uint64_t CurrentLocOps,
                           SmallVectorImpl<uint64_t> &Opcodes,
                           SmallVectorImpl<Value *> &AdditionalValues) {
// Handle binary operations with constant integer operands as a special case.
auto *ConstInt = dyn_cast<ConstantInt>(BI->getOperand(1));
// Values wider than 64 bits cannot be represented within a DIExpression.
if (ConstInt && ConstInt->getBitWidth() > 64)
  return nullptr;

Instruction::BinaryOps BinOpcode = BI->getOpcode();
// Push any Constant Int operand onto the expression stack.
if (ConstInt) {
  uint64_t Val = ConstInt->getSExtValue();
  // Add or Sub Instructions with a constant operand can potentially be
  // simplified.
  if (BinOpcode == Instruction::Add || BinOpcode == Instruction::Sub) {
    uint64_t Offset = BinOpcode == Instruction::Add ? Val : -int64_t(Val);
    DIExpression::appendOffset(Opcodes, Offset);
    return BI->getOperand(0);
  }
  Opcodes.append({dwarf::DW_OP_constu, Val});
} else {
  if (!CurrentLocOps) {
    Opcodes.append({dwarf::DW_OP_LLVM_arg, 0});
    CurrentLocOps = 1;
  }
  Opcodes.append({dwarf::DW_OP_LLVM_arg, CurrentLocOps});
  AdditionalValues.push_back(BI->getOperand(1));
}

// Add salvaged binary operator to expression stack, if it has a valid
// representation in a DIExpression.
uint64_t DwarfBinOp = getDwarfOpForBinOp(BinOpcode);
if (!DwarfBinOp)
  return nullptr;
Opcodes.push_back(DwarfBinOp);
return BI->getOperand(0);
1895}

1897Value *llvm::salvageDebugInfoImpl(Instruction &I, uint64_t CurrentLocOps,
                                SmallVectorImpl<uint64_t> &Ops,
                                SmallVectorImpl<Value *> &AdditionalValues) {
auto &M = *I.getModule();
auto &DL = M.getDataLayout();

if (auto *CI = dyn_cast<CastInst>(&I)) {
  Value *FromValue = CI->getOperand(0);
  // No-op casts are irrelevant for debug info.
  if (CI->isNoopCast(DL)) {
    return FromValue;
  }

  Type *Type = CI->getType();
  // Casts other than Trunc, SExt, or ZExt to scalar types cannot be salvaged.
  if (Type->isVectorTy() ||
      !(isa<TruncInst>(&I) || isa<SExtInst>(&I) || isa<ZExtInst>(&I)))
    return nullptr;

  unsigned FromTypeBitSize = FromValue->getType()->getScalarSizeInBits();
  unsigned ToTypeBitSize = Type->getScalarSizeInBits();

  auto ExtOps = DIExpression::getExtOps(FromTypeBitSize, ToTypeBitSize,
                                        isa<SExtInst>(&I));
  Ops.append(ExtOps.begin(), ExtOps.end());
  return FromValue;
}

if (auto *GEP = dyn_cast<GetElementPtrInst>(&I))
  return getSalvageOpsForGEP(GEP, DL, CurrentLocOps, Ops, AdditionalValues);
else if (auto *BI = dyn_cast<BinaryOperator>(&I)) {
  return getSalvageOpsForBinOp(BI, CurrentLocOps, Ops, AdditionalValues);
}
// *Not* to do: we should not attempt to salvage load instructions,
// because the validity and lifetime of a dbg.value containing
// DW_OP_deref becomes difficult to analyze. See PR40628 for examples.
return nullptr;
1934}

1936/// A replacement for a dbg.value expression.
1937using DbgValReplacement = Optional<DIExpression *>;

1939/// Point debug users of \p From to \p To using exprs given by \p RewriteExpr,
1940/// possibly moving/undefing users to prevent use-before-def. Returns true if
1941/// changes are made.
1942static bool rewriteDebugUsers(
  Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT,
  function_ref<DbgValReplacement(DbgVariableIntrinsic &DII)> RewriteExpr) {
// Find debug users of From.
SmallVector<DbgVariableIntrinsic *, 1> Users;
findDbgUsers(Users, &From);
if (Users.empty())
  return false;

// Prevent use-before-def of To.
bool Changed = false;
SmallPtrSet<DbgVariableIntrinsic *, 1> UndefOrSalvage;
if (isa<Instruction>(&To)) {
  bool DomPointAfterFrom = From.getNextNonDebugInstruction() == &DomPoint;

  for (auto *DII : Users) {
    // It's common to see a debug user between From and DomPoint. Move it
    // after DomPoint to preserve the variable update without any reordering.
    if (DomPointAfterFrom && DII->getNextNonDebugInstruction() == &DomPoint) {
      LLVM_DEBUG(dbgs() << "MOVE:  " << *DII << '\n')do { } while (false);
      DII->moveAfter(&DomPoint);
      Changed = true;

    // Users which otherwise aren't dominated by the replacement value must
    // be salvaged or deleted.
    } else if (!DT.dominates(&DomPoint, DII)) {
      UndefOrSalvage.insert(DII);
    }
  }
}

// Update debug users without use-before-def risk.
for (auto *DII : Users) {
  if (UndefOrSalvage.count(DII))
    continue;

  DbgValReplacement DVR = RewriteExpr(*DII);
  if (!DVR)
    continue;

  DII->replaceVariableLocationOp(&From, &To);
  DII->setExpression(*DVR);
  LLVM_DEBUG(dbgs() << "REWRITE:  " << *DII << '\n')do { } while (false);
  Changed = true;
}

if (!UndefOrSalvage.empty()) {
  // Try to salvage the remaining debug users.
  salvageDebugInfo(From);
  Changed = true;
}

return Changed;
1995}

1997/// Check if a bitcast between a value of type \p FromTy to type \p ToTy would
1998/// losslessly preserve the bits and semantics of the value. This predicate is
1999/// symmetric, i.e swapping \p FromTy and \p ToTy should give the same result.
2000///
2001/// Note that Type::canLosslesslyBitCastTo is not suitable here because it
2002/// allows semantically unequivalent bitcasts, such as <2 x i64> -> <4 x i32>,
2003/// and also does not allow lossless pointer <-> integer conversions.
2004static bool isBitCastSemanticsPreserving(const DataLayout &DL, Type *FromTy,
                                       Type *ToTy) {
// Trivially compatible types.
if (FromTy == ToTy)
  return true;

// Handle compatible pointer <-> integer conversions.
if (FromTy->isIntOrPtrTy() && ToTy->isIntOrPtrTy()) {
  bool SameSize = DL.getTypeSizeInBits(FromTy) == DL.getTypeSizeInBits(ToTy);
  bool LosslessConversion = !DL.isNonIntegralPointerType(FromTy) &&
                            !DL.isNonIntegralPointerType(ToTy);
  return SameSize && LosslessConversion;
}

// TODO: This is not exhaustive.
return false;
2020}

2022bool llvm::replaceAllDbgUsesWith(Instruction &From, Value &To,
                               Instruction &DomPoint, DominatorTree &DT) {
// Exit early if From has no debug users.
if (!From.isUsedByMetadata())
  return false;

assert(&From != &To && "Can't replace something with itself")(static_cast<void> (0));

Type *FromTy = From.getType();
Type *ToTy = To.getType();

auto Identity = [&](DbgVariableIntrinsic &DII) -> DbgValReplacement {
  return DII.getExpression();
};

// Handle no-op conversions.
Module &M = *From.getModule();
const DataLayout &DL = M.getDataLayout();
if (isBitCastSemanticsPreserving(DL, FromTy, ToTy))
  return rewriteDebugUsers(From, To, DomPoint, DT, Identity);

// Handle integer-to-integer widening and narrowing.
// FIXME: Use DW_OP_convert when it's available everywhere.
if (FromTy->isIntegerTy() && ToTy->isIntegerTy()) {
  uint64_t FromBits = FromTy->getPrimitiveSizeInBits();
  uint64_t ToBits = ToTy->getPrimitiveSizeInBits();
  assert(FromBits != ToBits && "Unexpected no-op conversion")(static_cast<void> (0));

  // When the width of the result grows, assume that a debugger will only
  // access the low `FromBits` bits when inspecting the source variable.
  if (FromBits < ToBits)
    return rewriteDebugUsers(From, To, DomPoint, DT, Identity);

  // The width of the result has shrunk. Use sign/zero extension to describe
  // the source variable's high bits.
  auto SignOrZeroExt = [&](DbgVariableIntrinsic &DII) -> DbgValReplacement {
    DILocalVariable *Var = DII.getVariable();

    // Without knowing signedness, sign/zero extension isn't possible.
    auto Signedness = Var->getSignedness();
    if (!Signedness)
      return None;

    bool Signed = *Signedness == DIBasicType::Signedness::Signed;
    return DIExpression::appendExt(DII.getExpression(), ToBits, FromBits,
                                   Signed);
  };
  return rewriteDebugUsers(From, To, DomPoint, DT, SignOrZeroExt);
}

// TODO: Floating-point conversions, vectors.
return false;
2074}

2076std::pair<unsigned, unsigned>
2077llvm::removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB) {
unsigned NumDeadInst = 0;
unsigned NumDeadDbgInst = 0;
// Delete the instructions backwards, as it has a reduced likelihood of
// having to update as many def-use and use-def chains.
Instruction *EndInst = BB->getTerminator(); // Last not to be deleted.
while (EndInst != &BB->front()) {
  // Delete the next to last instruction.
  Instruction *Inst = &*--EndInst->getIterator();
  if (!Inst->use_empty() && !Inst->getType()->isTokenTy())
    Inst->replaceAllUsesWith(UndefValue::get(Inst->getType()));
  if (Inst->isEHPad() || Inst->getType()->isTokenTy()) {
    EndInst = Inst;
    continue;
  }
  if (isa<DbgInfoIntrinsic>(Inst))
    ++NumDeadDbgInst;
  else
    ++NumDeadInst;
  Inst->eraseFromParent();
}
return {NumDeadInst, NumDeadDbgInst};
2099}

2101unsigned llvm::changeToUnreachable(Instruction *I, bool PreserveLCSSA,
                                 DomTreeUpdater *DTU,
                                 MemorySSAUpdater *MSSAU) {
BasicBlock *BB = I->getParent();

if (MSSAU)
  MSSAU->changeToUnreachable(I);

SmallSet<BasicBlock *, 8> UniqueSuccessors;

// Loop over all of the successors, removing BB's entry from any PHI
// nodes.
for (BasicBlock *Successor : successors(BB)) {
  Successor->removePredecessor(BB, PreserveLCSSA);
  if (DTU)
    UniqueSuccessors.insert(Successor);
}
auto *UI = new UnreachableInst(I->getContext(), I);
UI->setDebugLoc(I->getDebugLoc());

// All instructions after this are dead.
unsigned NumInstrsRemoved = 0;
BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end();
while (BBI != BBE) {
  if (!BBI->use_empty())
    BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
  BB->getInstList().erase(BBI++);
  ++NumInstrsRemoved;
}
if (DTU) {
  SmallVector<DominatorTree::UpdateType, 8> Updates;
  Updates.reserve(UniqueSuccessors.size());
  for (BasicBlock *UniqueSuccessor : UniqueSuccessors)
    Updates.push_back({DominatorTree::Delete, BB, UniqueSuccessor});
  DTU->applyUpdates(Updates);
}
return NumInstrsRemoved;
2138}

2140CallInst *llvm::createCallMatchingInvoke(InvokeInst *II) {
SmallVector<Value *, 8> Args(II->args());
SmallVector<OperandBundleDef, 1> OpBundles;
II->getOperandBundlesAsDefs(OpBundles);
CallInst *NewCall = CallInst::Create(II->getFunctionType(),
                                     II->getCalledOperand(), Args, OpBundles);
NewCall->setCallingConv(II->getCallingConv());
NewCall->setAttributes(II->getAttributes());
NewCall->setDebugLoc(II->getDebugLoc());
NewCall->copyMetadata(*II);

// If the invoke had profile metadata, try converting them for CallInst.
uint64_t TotalWeight;
if (NewCall->extractProfTotalWeight(TotalWeight)) {
  // Set the total weight if it fits into i32, otherwise reset.
  MDBuilder MDB(NewCall->getContext());
  auto NewWeights = uint32_t(TotalWeight) != TotalWeight
                        ? nullptr
                        : MDB.createBranchWeights({uint32_t(TotalWeight)});
  NewCall->setMetadata(LLVMContext::MD_prof, NewWeights);
}

return NewCall;
2163}

2165/// changeToCall - Convert the specified invoke into a normal call.
2166void llvm::changeToCall(InvokeInst *II, DomTreeUpdater *DTU) {
CallInst *NewCall = createCallMatchingInvoke(II);
NewCall->takeName(II);
NewCall->insertBefore(II);
II->replaceAllUsesWith(NewCall);

// Follow the call by a branch to the normal destination.
BasicBlock *NormalDestBB = II->getNormalDest();
BranchInst::Create(NormalDestBB, II);

// Update PHI nodes in the unwind destination
BasicBlock *BB = II->getParent();
BasicBlock *UnwindDestBB = II->getUnwindDest();
UnwindDestBB->removePredecessor(BB);
II->eraseFromParent();
if (DTU)
  DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}});
2183}

2185BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI,
                                                 BasicBlock *UnwindEdge,
                                                 DomTreeUpdater *DTU) {
BasicBlock *BB = CI->getParent();

// Convert this function call into an invoke instruction.  First, split the
// basic block.
BasicBlock *Split = SplitBlock(BB, CI, DTU, /*LI=*/nullptr, /*MSSAU*/ nullptr,
                               CI->getName() + ".noexc");

// Delete the unconditional branch inserted by SplitBlock
BB->getInstList().pop_back();

// Create the new invoke instruction.
SmallVector<Value *, 8> InvokeArgs(CI->args());
SmallVector<OperandBundleDef, 1> OpBundles;

CI->getOperandBundlesAsDefs(OpBundles);

// Note: we're round tripping operand bundles through memory here, and that
// can potentially be avoided with a cleverer API design that we do not have
// as of this time.

InvokeInst *II =
    InvokeInst::Create(CI->getFunctionType(), CI->getCalledOperand(), Split,
                       UnwindEdge, InvokeArgs, OpBundles, CI->getName(), BB);
II->setDebugLoc(CI->getDebugLoc());
II->setCallingConv(CI->getCallingConv());
II->setAttributes(CI->getAttributes());

if (DTU)
  DTU->applyUpdates({{DominatorTree::Insert, BB, UnwindEdge}});

// Make sure that anything using the call now uses the invoke!  This also
// updates the CallGraph if present, because it uses a WeakTrackingVH.
CI->replaceAllUsesWith(II);

// Delete the original call
Split->getInstList().pop_front();
return Split;
2225}

2227static bool markAliveBlocks(Function &F,
                          SmallPtrSetImpl<BasicBlock *> &Reachable,
                          DomTreeUpdater *DTU = nullptr) {
SmallVector<BasicBlock*, 128> Worklist;
BasicBlock *BB = &F.front();
Worklist.push_back(BB);
Reachable.insert(BB);
bool Changed = false;
do {
  BB = Worklist.pop_back_val();

  // Do a quick scan of the basic block, turning any obviously unreachable
  // instructions into LLVM unreachable insts.  The instruction combining pass
  // canonicalizes unreachable insts into stores to null or undef.
  for (Instruction &I : *BB) {
    if (auto *CI = dyn_cast<CallInst>(&I)) {
      Value *Callee = CI->getCalledOperand();
      // Handle intrinsic calls.
      if (Function *F = dyn_cast<Function>(Callee)) {
        auto IntrinsicID = F->getIntrinsicID();
        // Assumptions that are known to be false are equivalent to
        // unreachable. Also, if the condition is undefined, then we make the
        // choice most beneficial to the optimizer, and choose that to also be
        // unreachable.
        if (IntrinsicID == Intrinsic::assume) {
          if (match(CI->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) {
            // Don't insert a call to llvm.trap right before the unreachable.
            changeToUnreachable(CI, false, DTU);
            Changed = true;
            break;
          }
        } else if (IntrinsicID == Intrinsic::experimental_guard) {
          // A call to the guard intrinsic bails out of the current
          // compilation unit if the predicate passed to it is false. If the
          // predicate is a constant false, then we know the guard will bail
          // out of the current compile unconditionally, so all code following
          // it is dead.
          //
          // Note: unlike in llvm.assume, it is not "obviously profitable" for
          // guards to treat `undef` as `false` since a guard on `undef` can
          // still be useful for widening.
          if (match(CI->getArgOperand(0), m_Zero()))
            if (!isa<UnreachableInst>(CI->getNextNode())) {
              changeToUnreachable(CI->getNextNode(), false, DTU);
              Changed = true;
              break;
            }
        }
      } else if ((isa<ConstantPointerNull>(Callee) &&
                  !NullPointerIsDefined(CI->getFunction())) ||
                 isa<UndefValue>(Callee)) {
        changeToUnreachable(CI, false, DTU);
        Changed = true;
        break;
      }
      if (CI->doesNotReturn() && !CI->isMustTailCall()) {
        // If we found a call to a no-return function, insert an unreachable
        // instruction after it.  Make sure there isn't *already* one there
        // though.
        if (!isa<UnreachableInst>(CI->getNextNode())) {
          // Don't insert a call to llvm.trap right before the unreachable.
          changeToUnreachable(CI->getNextNode(), false, DTU);
          Changed = true;
        }
        break;
      }
    } else if (auto *SI = dyn_cast<StoreInst>(&I)) {
      // Store to undef and store to null are undefined and used to signal
      // that they should be changed to unreachable by passes that can't
      // modify the CFG.

      // Don't touch volatile stores.
      if (SI->isVolatile()) continue;

      Value *Ptr = SI->getOperand(1);

      if (isa<UndefValue>(Ptr) ||
          (isa<ConstantPointerNull>(Ptr) &&
           !NullPointerIsDefined(SI->getFunction(),
                                 SI->getPointerAddressSpace()))) {
        changeToUnreachable(SI, false, DTU);
        Changed = true;
        break;
      }
    }
  }

  Instruction *Terminator = BB->getTerminator();
  if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
    // Turn invokes that call 'nounwind' functions into ordinary calls.
    Value *Callee = II->getCalledOperand();
    if ((isa<ConstantPointerNull>(Callee) &&
         !NullPointerIsDefined(BB->getParent())) ||
        isa<UndefValue>(Callee)) {
      changeToUnreachable(II, false, DTU);
      Changed = true;
    } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) {
      if (II->use_empty() && II->onlyReadsMemory()) {
        // jump to the normal destination branch.
        BasicBlock *NormalDestBB = II->getNormalDest();
        BasicBlock *UnwindDestBB = II->getUnwindDest();
        BranchInst::Create(NormalDestBB, II);
        UnwindDestBB->removePredecessor(II->getParent());
        II->eraseFromParent();
        if (DTU)
          DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}});
      } else
        changeToCall(II, DTU);
      Changed = true;
    }
  } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
    // Remove catchpads which cannot be reached.
    struct CatchPadDenseMapInfo {
      static CatchPadInst *getEmptyKey() {
        return DenseMapInfo<CatchPadInst *>::getEmptyKey();
      }

      static CatchPadInst *getTombstoneKey() {
        return DenseMapInfo<CatchPadInst *>::getTombstoneKey();
      }

      static unsigned getHashValue(CatchPadInst *CatchPad) {
        return static_cast<unsigned>(hash_combine_range(
            CatchPad->value_op_begin(), CatchPad->value_op_end()));
      }

      static bool isEqual(CatchPadInst *LHS, CatchPadInst *RHS) {
        if (LHS == getEmptyKey() || LHS == getTombstoneKey() ||
            RHS == getEmptyKey() || RHS == getTombstoneKey())
          return LHS == RHS;
        return LHS->isIdenticalTo(RHS);
      }
    };

    SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
    // Set of unique CatchPads.
    SmallDenseMap<CatchPadInst *, detail::DenseSetEmpty, 4,
                  CatchPadDenseMapInfo, detail::DenseSetPair<CatchPadInst *>>
        HandlerSet;
    detail::DenseSetEmpty Empty;
    for (CatchSwitchInst::handler_iterator I = CatchSwitch->handler_begin(),
                                           E = CatchSwitch->handler_end();
         I != E; ++I) {
      BasicBlock *HandlerBB = *I;
      if (DTU)
        ++NumPerSuccessorCases[HandlerBB];
      auto *CatchPad = cast<CatchPadInst>(HandlerBB->getFirstNonPHI());
      if (!HandlerSet.insert({CatchPad, Empty}).second) {
        if (DTU)
          --NumPerSuccessorCases[HandlerBB];
        CatchSwitch->removeHandler(I);
        --I;
        --E;
        Changed = true;
      }
    }
    if (DTU) {
      std::vector<DominatorTree::UpdateType> Updates;
      for (const std::pair<BasicBlock *, int> &I : NumPerSuccessorCases)
        if (I.second == 0)
          Updates.push_back({DominatorTree::Delete, BB, I.first});
      DTU->applyUpdates(Updates);
    }
  }

  Changed |= ConstantFoldTerminator(BB, true, nullptr, DTU);
  for (BasicBlock *Successor : successors(BB))
    if (Reachable.insert(Successor).second)
      Worklist.push_back(Successor);
} while (!Worklist.empty());
return Changed;
2398}

2400void llvm::removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU) {
Instruction *TI = BB->getTerminator();

if (auto *II = dyn_cast<InvokeInst>(TI)) {
  changeToCall(II, DTU);
  return;
}

Instruction *NewTI;
BasicBlock *UnwindDest;

if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
  NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI);
  UnwindDest = CRI->getUnwindDest();
} else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
  auto *NewCatchSwitch = CatchSwitchInst::Create(
      CatchSwitch->getParentPad(), nullptr, CatchSwitch->getNumHandlers(),
      CatchSwitch->getName(), CatchSwitch);
  for (BasicBlock *PadBB : CatchSwitch->handlers())
    NewCatchSwitch->addHandler(PadBB);

  NewTI = NewCatchSwitch;
  UnwindDest = CatchSwitch->getUnwindDest();
} else {
  llvm_unreachable("Could not find unwind successor")__builtin_unreachable();
}

NewTI->takeName(TI);
NewTI->setDebugLoc(TI->getDebugLoc());
UnwindDest->removePredecessor(BB);
TI->replaceAllUsesWith(NewTI);
TI->eraseFromParent();
if (DTU)
  DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDest}});
2434}

2436/// removeUnreachableBlocks - Remove blocks that are not reachable, even
2437/// if they are in a dead cycle.  Return true if a change was made, false
2438/// otherwise.
2439bool llvm::removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU,
                                 MemorySSAUpdater *MSSAU) {
SmallPtrSet<BasicBlock *, 16> Reachable;
bool Changed = markAliveBlocks(F, Reachable, DTU);

// If there are unreachable blocks in the CFG...
if (Reachable.size() == F.size())
  return Changed;

assert(Reachable.size() < F.size())(static_cast<void> (0));

// Are there any blocks left to actually delete?
SmallSetVector<BasicBlock *, 8> BlocksToRemove;
for (BasicBlock &BB : F) {
  // Skip reachable basic blocks
  if (Reachable.count(&BB))
    continue;
  // Skip already-deleted blocks
  if (DTU && DTU->isBBPendingDeletion(&BB))
    continue;
  BlocksToRemove.insert(&BB);
}

if (BlocksToRemove.empty())
  return Changed;

Changed = true;
NumRemoved += BlocksToRemove.size();

if (MSSAU)
  MSSAU->removeBlocks(BlocksToRemove);

DeleteDeadBlocks(BlocksToRemove.takeVector(), DTU);

return Changed;
2474}

2476void llvm::combineMetadata(Instruction *K, const Instruction *J,
                         ArrayRef<unsigned> KnownIDs, bool DoesKMove) {
SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
K->dropUnknownNonDebugMetadata(KnownIDs);
K->getAllMetadataOtherThanDebugLoc(Metadata);
for (const auto &MD : Metadata) {
  unsigned Kind = MD.first;
  MDNode *JMD = J->getMetadata(Kind);
  MDNode *KMD = MD.second;

  switch (Kind) {
    default:
      K->setMetadata(Kind, nullptr); // Remove unknown metadata
      break;
    case LLVMContext::MD_dbg:
      llvm_unreachable("getAllMetadataOtherThanDebugLoc returned a MD_dbg")__builtin_unreachable();
    case LLVMContext::MD_tbaa:
      K->setMetadata(Kind, MDNode::getMostGenericTBAA(JMD, KMD));
      break;
    case LLVMContext::MD_alias_scope:
      K->setMetadata(Kind, MDNode::getMostGenericAliasScope(JMD, KMD));
      break;
    case LLVMContext::MD_noalias:
    case LLVMContext::MD_mem_parallel_loop_access:
      K->setMetadata(Kind, MDNode::intersect(JMD, KMD));
      break;
    case LLVMContext::MD_access_group:
      K->setMetadata(LLVMContext::MD_access_group,
                     intersectAccessGroups(K, J));
      break;
    case LLVMContext::MD_range:

      // If K does move, use most generic range. Otherwise keep the range of
      // K.
      if (DoesKMove)
        // FIXME: If K does move, we should drop the range info and nonnull.
        //        Currently this function is used with DoesKMove in passes
        //        doing hoisting/sinking and the current behavior of using the
        //        most generic range is correct in those cases.
        K->setMetadata(Kind, MDNode::getMostGenericRange(JMD, KMD));
      break;
    case LLVMContext::MD_fpmath:
      K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD));
      break;
    case LLVMContext::MD_invariant_load:
      // Only set the !invariant.load if it is present in both instructions.
      K->setMetadata(Kind, JMD);
      break;
    case LLVMContext::MD_nonnull:
      // If K does move, keep nonull if it is present in both instructions.
      if (DoesKMove)
        K->setMetadata(Kind, JMD);
      break;
    case LLVMContext::MD_invariant_group:
      // Preserve !invariant.group in K.
      break;
    case LLVMContext::MD_align:
      K->setMetadata(Kind,
        MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD));
      break;
    case LLVMContext::MD_dereferenceable:
    case LLVMContext::MD_dereferenceable_or_null:
      K->setMetadata(Kind,
        MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD));
      break;
    case LLVMContext::MD_preserve_access_index:
      // Preserve !preserve.access.index in K.
      break;
  }
}
// Set !invariant.group from J if J has it. If both instructions have it
// then we will just pick it from J - even when they are different.
// Also make sure that K is load or store - f.e. combining bitcast with load
// could produce bitcast with invariant.group metadata, which is invalid.
// FIXME: we should try to preserve both invariant.group md if they are
// different, but right now instruction can only have one invariant.group.
if (auto *JMD = J->getMetadata(LLVMContext::MD_invariant_group))
  if (isa<LoadInst>(K) || isa<StoreInst>(K))
    K->setMetadata(LLVMContext::MD_invariant_group, JMD);
2555}

2557void llvm::combineMetadataForCSE(Instruction *K, const Instruction *J,
                               bool KDominatesJ) {
unsigned KnownIDs[] = {
    LLVMContext::MD_tbaa,            LLVMContext::MD_alias_scope,
    LLVMContext::MD_noalias,         LLVMContext::MD_range,
    LLVMContext::MD_invariant_load,  LLVMContext::MD_nonnull,
    LLVMContext::MD_invariant_group, LLVMContext::MD_align,
    LLVMContext::MD_dereferenceable,
    LLVMContext::MD_dereferenceable_or_null,
    LLVMContext::MD_access_group,    LLVMContext::MD_preserve_access_index};
combineMetadata(K, J, KnownIDs, KDominatesJ);
2568}

2570void llvm::copyMetadataForLoad(LoadInst &Dest, const LoadInst &Source) {
SmallVector<std::pair<unsigned, MDNode *>, 8> MD;
Source.getAllMetadata(MD);
MDBuilder MDB(Dest.getContext());
Type *NewType = Dest.getType();
const DataLayout &DL = Source.getModule()->getDataLayout();
for (const auto &MDPair : MD) {
  unsigned ID = MDPair.first;
  MDNode *N = MDPair.second;
  // Note, essentially every kind of metadata should be preserved here! This
  // routine is supposed to clone a load instruction changing *only its type*.
  // The only metadata it makes sense to drop is metadata which is invalidated
  // when the pointer type changes. This should essentially never be the case
  // in LLVM, but we explicitly switch over only known metadata to be
  // conservatively correct. If you are adding metadata to LLVM which pertains
  // to loads, you almost certainly want to add it here.
  switch (ID) {
  case LLVMContext::MD_dbg:
  case LLVMContext::MD_tbaa:
  case LLVMContext::MD_prof:
  case LLVMContext::MD_fpmath:
  case LLVMContext::MD_tbaa_struct:
  case LLVMContext::MD_invariant_load:
  case LLVMContext::MD_alias_scope:
  case LLVMContext::MD_noalias:
  case LLVMContext::MD_nontemporal:
  case LLVMContext::MD_mem_parallel_loop_access:
  case LLVMContext::MD_access_group:
    // All of these directly apply.
    Dest.setMetadata(ID, N);
    break;

  case LLVMContext::MD_nonnull:
    copyNonnullMetadata(Source, N, Dest);
    break;

  case LLVMContext::MD_align:
  case LLVMContext::MD_dereferenceable:
  case LLVMContext::MD_dereferenceable_or_null:
    // These only directly apply if the new type is also a pointer.
    if (NewType->isPointerTy())
      Dest.setMetadata(ID, N);
    break;

  case LLVMContext::MD_range:
    copyRangeMetadata(DL, Source, N, Dest);
    break;
  }
}
2619}

2621void llvm::patchReplacementInstruction(Instruction *I, Value *Repl) {
auto *ReplInst = dyn_cast<Instruction>(Repl);
if (!ReplInst)
  return;

// Patch the replacement so that it is not more restrictive than the value
// being replaced.
// Note that if 'I' is a load being replaced by some operation,
// for example, by an arithmetic operation, then andIRFlags()
// would just erase all math flags from the original arithmetic
// operation, which is clearly not wanted and not needed.
if (!isa<LoadInst>(I))
  ReplInst->andIRFlags(I);

// FIXME: If both the original and replacement value are part of the
// same control-flow region (meaning that the execution of one
// guarantees the execution of the other), then we can combine the
// noalias scopes here and do better than the general conservative
// answer used in combineMetadata().

// In general, GVN unifies expressions over different control-flow
// regions, and so we need a conservative combination of the noalias
// scopes.
static const unsigned KnownIDs[] = {
    LLVMContext::MD_tbaa,            LLVMContext::MD_alias_scope,
    LLVMContext::MD_noalias,         LLVMContext::MD_range,
    LLVMContext::MD_fpmath,          LLVMContext::MD_invariant_load,
    LLVMContext::MD_invariant_group, LLVMContext::MD_nonnull,
    LLVMContext::MD_access_group,    LLVMContext::MD_preserve_access_index};
combineMetadata(ReplInst, I, KnownIDs, false);
2651}

2653template <typename RootType, typename DominatesFn>
2654static unsigned replaceDominatedUsesWith(Value *From, Value *To,
                                       const RootType &Root,
                                       const DominatesFn &Dominates) {
assert(From->getType() == To->getType())(static_cast<void> (0));

unsigned Count = 0;
for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
     UI != UE;) {
  Use &U = *UI++;
  if (!Dominates(Root, U))
    continue;
  U.set(To);
  LLVM_DEBUG(dbgs() << "Replace dominated use of '" << From->getName()do { } while (false)
                    << "' as " << *To << " in " << *U << "\n")do { } while (false);
  ++Count;
}
return Count;
2671}

2673unsigned llvm::replaceNonLocalUsesWith(Instruction *From, Value *To) {
 assert(From->getType() == To->getType())(static_cast<void> (0));
 auto *BB = From->getParent();
 unsigned Count = 0;

for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
     UI != UE;) {
  Use &U = *UI++;
  auto *I = cast<Instruction>(U.getUser());
  if (I->getParent() == BB)
    continue;
  U.set(To);
  ++Count;
}
return Count;
2688}

2690unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
                                      DominatorTree &DT,
                                      const BasicBlockEdge &Root) {
auto Dominates = [&DT](const BasicBlockEdge &Root, const Use &U) {
  return DT.dominates(Root, U);
};
return ::replaceDominatedUsesWith(From, To, Root, Dominates);
2697}

2699unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
                                      DominatorTree &DT,
                                      const BasicBlock *BB) {
auto Dominates = [&DT](const BasicBlock *BB, const Use &U) {
  return DT.dominates(BB, U);
};
return ::replaceDominatedUsesWith(From, To, BB, Dominates);
2706}

2708bool llvm::callsGCLeafFunction(const CallBase *Call,
                             const TargetLibraryInfo &TLI) {
// Check if the function is specifically marked as a gc leaf function.
if (Call->hasFnAttr("gc-leaf-function"))
  return true;
if (const Function *F = Call->getCalledFunction()) {
  if (F->hasFnAttribute("gc-leaf-function"))
    return true;

  if (auto IID = F->getIntrinsicID()) {
    // Most LLVM intrinsics do not take safepoints.
    return IID != Intrinsic::experimental_gc_statepoint &&
           IID != Intrinsic::experimental_deoptimize &&
           IID != Intrinsic::memcpy_element_unordered_atomic &&
           IID != Intrinsic::memmove_element_unordered_atomic;
  }
}

// Lib calls can be materialized by some passes, and won't be
// marked as 'gc-leaf-function.' All available Libcalls are
// GC-leaf.
LibFunc LF;
if (TLI.getLibFunc(*Call, LF)) {
  return TLI.has(LF);
}

return false;
2735}

2737void llvm::copyNonnullMetadata(const LoadInst &OldLI, MDNode *N,
                             LoadInst &NewLI) {
auto *NewTy = NewLI.getType();

// This only directly applies if the new type is also a pointer.
if (NewTy->isPointerTy()) {
  NewLI.setMetadata(LLVMContext::MD_nonnull, N);
  return;
}

// The only other translation we can do is to integral loads with !range
// metadata.
if (!NewTy->isIntegerTy())
  return;

MDBuilder MDB(NewLI.getContext());
const Value *Ptr = OldLI.getPointerOperand();
auto *ITy = cast<IntegerType>(NewTy);
auto *NullInt = ConstantExpr::getPtrToInt(
    ConstantPointerNull::get(cast<PointerType>(Ptr->getType())), ITy);
auto *NonNullInt = ConstantExpr::getAdd(NullInt, ConstantInt::get(ITy, 1));
NewLI.setMetadata(LLVMContext::MD_range,
                  MDB.createRange(NonNullInt, NullInt));
2760}

2762void llvm::copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI,
                           MDNode *N, LoadInst &NewLI) {
auto *NewTy = NewLI.getType();

// Give up unless it is converted to a pointer where there is a single very
// valuable mapping we can do reliably.
// FIXME: It would be nice to propagate this in more ways, but the type
// conversions make it hard.
if (!NewTy->isPointerTy())
  return;

unsigned BitWidth = DL.getPointerTypeSizeInBits(NewTy);
if (!getConstantRangeFromMetadata(*N).contains(APInt(BitWidth, 0))) {
  MDNode *NN = MDNode::get(OldLI.getContext(), None);
  NewLI.setMetadata(LLVMContext::MD_nonnull, NN);
}
2778}

2780void llvm::dropDebugUsers(Instruction &I) {
SmallVector<DbgVariableIntrinsic *, 1> DbgUsers;
findDbgUsers(DbgUsers, &I);
for (auto *DII : DbgUsers)
  DII->eraseFromParent();
2785}

2787void llvm::hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt,
                                  BasicBlock *BB) {
// Since we are moving the instructions out of its basic block, we do not
// retain their original debug locations (DILocations) and debug intrinsic
// instructions.
//
// Doing so would degrade the debugging experience and adversely affect the
// accuracy of profiling information.
//
// Currently, when hoisting the instructions, we take the following actions:
// - Remove their debug intrinsic instructions.
// - Set their debug locations to the values from the insertion point.
//
// As per PR39141 (comment #8), the more fundamental reason why the dbg.values
// need to be deleted, is because there will not be any instructions with a
// DILocation in either branch left after performing the transformation. We
// can only insert a dbg.value after the two branches are joined again.
//
// See PR38762, PR39243 for more details.
//
// TODO: Extend llvm.dbg.value to take more than one SSA Value (PR39141) to
// encode predicated DIExpressions that yield different results on different
// code paths.

for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE;) {
  Instruction *I = &*II;
  I->dropUndefImplyingAttrsAndUnknownMetadata();
  if (I->isUsedByMetadata())
    dropDebugUsers(*I);
  if (I->isDebugOrPseudoInst()) {
    // Remove DbgInfo and pseudo probe Intrinsics.
    II = I->eraseFromParent();
    continue;
  }
  I->setDebugLoc(InsertPt->getDebugLoc());
  ++II;
}
DomBlock->getInstList().splice(InsertPt->getIterator(), BB->getInstList(),
                               BB->begin(),
                               BB->getTerminator()->getIterator());
2827}

2829namespace {

2831/// A potential constituent of a bitreverse or bswap expression. See
2832/// collectBitParts for a fuller explanation.
2833struct BitPart {
BitPart(Value *P, unsigned BW) : Provider(P) {
  Provenance.resize(BW);
}

/// The Value that this is a bitreverse/bswap of.
Value *Provider;

/// The "provenance" of each bit. Provenance[A] = B means that bit A
/// in Provider becomes bit B in the result of this expression.
SmallVector<int8_t, 32> Provenance; // int8_t means max size is i128.

enum { Unset = -1 };
2846};

2848} // end anonymous namespace

2850/// Analyze the specified subexpression and see if it is capable of providing
2851/// pieces of a bswap or bitreverse. The subexpression provides a potential
2852/// piece of a bswap or bitreverse if it can be proved that each non-zero bit in
2853/// the output of the expression came from a corresponding bit in some other
2854/// value. This function is recursive, and the end result is a mapping of
2855/// bitnumber to bitnumber. It is the caller's responsibility to validate that
2856/// the bitnumber to bitnumber mapping is correct for a bswap or bitreverse.
2857///
2858/// For example, if the current subexpression if "(shl i32 %X, 24)" then we know
2859/// that the expression deposits the low byte of %X into the high byte of the
2860/// result and that all other bits are zero. This expression is accepted and a
2861/// BitPart is returned with Provider set to %X and Provenance[24-31] set to
2862/// [0-7].
2863///
2864/// For vector types, all analysis is performed at the per-element level. No
2865/// cross-element analysis is supported (shuffle/insertion/reduction), and all
2866/// constant masks must be splatted across all elements.
2867///
2868/// To avoid revisiting values, the BitPart results are memoized into the
2869/// provided map. To avoid unnecessary copying of BitParts, BitParts are
2870/// constructed in-place in the \c BPS map. Because of this \c BPS needs to
2871/// store BitParts objects, not pointers. As we need the concept of a nullptr
2872/// BitParts (Value has been analyzed and the analysis failed), we an Optional
2873/// type instead to provide the same functionality.
2874///
2875/// Because we pass around references into \c BPS, we must use a container that
2876/// does not invalidate internal references (std::map instead of DenseMap).
2877static const Optional<BitPart> &
2878collectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals,
              std::map<Value *, Optional<BitPart>> &BPS, int Depth,
              bool &FoundRoot) {
auto I = BPS.find(V);
if (I != BPS.end())
  return I->second;

auto &Result = BPS[V] = None;
auto BitWidth = V->getType()->getScalarSizeInBits();

// Can't do integer/elements > 128 bits.
if (BitWidth > 128)
  return Result;

// Prevent stack overflow by limiting the recursion depth
if (Depth == BitPartRecursionMaxDepth) {
  LLVM_DEBUG(dbgs() << "collectBitParts max recursion depth reached.\n")do { } while (false);
  return Result;
}

if (auto *I = dyn_cast<Instruction>(V)) {
  Value *X, *Y;
  const APInt *C;

  // If this is an or instruction, it may be an inner node of the bswap.
  if (match(V, m_Or(m_Value(X), m_Value(Y)))) {
    // Check we have both sources and they are from the same provider.
    const auto &A = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
                                    Depth + 1, FoundRoot);
    if (!A || !A->Provider)
      return Result;

    const auto &B = collectBitParts(Y, MatchBSwaps, MatchBitReversals, BPS,
                                    Depth + 1, FoundRoot);
    if (!B || A->Provider != B->Provider)
      return Result;

    // Try and merge the two together.
    Result = BitPart(A->Provider, BitWidth);
    for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx) {
      if (A->Provenance[BitIdx] != BitPart::Unset &&
          B->Provenance[BitIdx] != BitPart::Unset &&
          A->Provenance[BitIdx] != B->Provenance[BitIdx])
        return Result = None;

      if (A->Provenance[BitIdx] == BitPart::Unset)
        Result->Provenance[BitIdx] = B->Provenance[BitIdx];
      else
        Result->Provenance[BitIdx] = A->Provenance[BitIdx];
    }

    return Result;
  }

  // If this is a logical shift by a constant, recurse then shift the result.
  if (match(V, m_LogicalShift(m_Value(X), m_APInt(C)))) {
    const APInt &BitShift = *C;

    // Ensure the shift amount is defined.
    if (BitShift.uge(BitWidth))
      return Result;

    // For bswap-only, limit shift amounts to whole bytes, for an early exit.
    if (!MatchBitReversals && (BitShift.getZExtValue() % 8) != 0)
      return Result;

    const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
                                      Depth + 1, FoundRoot);
    if (!Res)
      return Result;
    Result = Res;

    // Perform the "shift" on BitProvenance.
    auto &P = Result->Provenance;
    if (I->getOpcode() == Instruction::Shl) {
      P.erase(std::prev(P.end(), BitShift.getZExtValue()), P.end());
      P.insert(P.begin(), BitShift.getZExtValue(), BitPart::Unset);
    } else {
      P.erase(P.begin(), std::next(P.begin(), BitShift.getZExtValue()));
      P.insert(P.end(), BitShift.getZExtValue(), BitPart::Unset);
    }

    return Result;
  }

  // If this is a logical 'and' with a mask that clears bits, recurse then
  // unset the appropriate bits.
  if (match(V, m_And(m_Value(X), m_APInt(C)))) {
    const APInt &AndMask = *C;

    // Check that the mask allows a multiple of 8 bits for a bswap, for an
    // early exit.
    unsigned NumMaskedBits = AndMask.countPopulation();
    if (!MatchBitReversals && (NumMaskedBits % 8) != 0)
      return Result;

    const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
                                      Depth + 1, FoundRoot);
    if (!Res)
      return Result;
    Result = Res;

    for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
      // If the AndMask is zero for this bit, clear the bit.
      if (AndMask[BitIdx] == 0)
        Result->Provenance[BitIdx] = BitPart::Unset;
    return Result;
  }

  // If this is a zext instruction zero extend the result.
  if (match(V, m_ZExt(m_Value(X)))) {
    const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
                                      Depth + 1, FoundRoot);
    if (!Res)
      return Result;

    Result = BitPart(Res->Provider, BitWidth);
    auto NarrowBitWidth = X->getType()->getScalarSizeInBits();
    for (unsigned BitIdx = 0; BitIdx < NarrowBitWidth; ++BitIdx)
      Result->Provenance[BitIdx] = Res->Provenance[BitIdx];
    for (unsigned BitIdx = NarrowBitWidth; BitIdx < BitWidth; ++BitIdx)
      Result->Provenance[BitIdx] = BitPart::Unset;
    return Result;
  }

  // If this is a truncate instruction, extract the lower bits.
  if (match(V, m_Trunc(m_Value(X)))) {
    const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
                                      Depth + 1, FoundRoot);
    if (!Res)
      return Result;

    Result = BitPart(Res->Provider, BitWidth);
    for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
      Result->Provenance[BitIdx] = Res->Provenance[BitIdx];
    return Result;
  }

  // BITREVERSE - most likely due to us previous matching a partial
  // bitreverse.
  if (match(V, m_BitReverse(m_Value(X)))) {
    const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
                                      Depth + 1, FoundRoot);
    if (!Res)
      return Result;

    Result = BitPart(Res->Provider, BitWidth);
    for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
      Result->Provenance[(BitWidth - 1) - BitIdx] = Res->Provenance[BitIdx];
    return Result;
  }

  // BSWAP - most likely due to us previous matching a partial bswap.
  if (match(V, m_BSwap(m_Value(X)))) {
    const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
                                      Depth + 1, FoundRoot);
    if (!Res)
      return Result;

    unsigned ByteWidth = BitWidth / 8;
    Result = BitPart(Res->Provider, BitWidth);
    for (unsigned ByteIdx = 0; ByteIdx < ByteWidth; ++ByteIdx) {
      unsigned ByteBitOfs = ByteIdx * 8;
      for (unsigned BitIdx = 0; BitIdx < 8; ++BitIdx)
        Result->Provenance[(BitWidth - 8 - ByteBitOfs) + BitIdx] =
            Res->Provenance[ByteBitOfs + BitIdx];
    }
    return Result;
  }

  // Funnel 'double' shifts take 3 operands, 2 inputs and the shift
  // amount (modulo).
  // fshl(X,Y,Z): (X << (Z % BW)) | (Y >> (BW - (Z % BW)))
  // fshr(X,Y,Z): (X << (BW - (Z % BW))) | (Y >> (Z % BW))
  if (match(V, m_FShl(m_Value(X), m_Value(Y), m_APInt(C))) ||
      match(V, m_FShr(m_Value(X), m_Value(Y), m_APInt(C)))) {
    // We can treat fshr as a fshl by flipping the modulo amount.
    unsigned ModAmt = C->urem(BitWidth);
    if (cast<IntrinsicInst>(I)->getIntrinsicID() == Intrinsic::fshr)
      ModAmt = BitWidth - ModAmt;

    // For bswap-only, limit shift amounts to whole bytes, for an early exit.
    if (!MatchBitReversals && (ModAmt % 8) != 0)
      return Result;

    // Check we have both sources and they are from the same provider.
    const auto &LHS = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
                                      Depth + 1, FoundRoot);
    if (!LHS || !LHS->Provider)
      return Result;

    const auto &RHS = collectBitParts(Y, MatchBSwaps, MatchBitReversals, BPS,
                                      Depth + 1, FoundRoot);
    if (!RHS || LHS->Provider != RHS->Provider)
      return Result;

    unsigned StartBitRHS = BitWidth - ModAmt;
    Result = BitPart(LHS->Provider, BitWidth);
    for (unsigned BitIdx = 0; BitIdx < StartBitRHS; ++BitIdx)
      Result->Provenance[BitIdx + ModAmt] = LHS->Provenance[BitIdx];
    for (unsigned BitIdx = 0; BitIdx < ModAmt; ++BitIdx)
      Result->Provenance[BitIdx] = RHS->Provenance[BitIdx + StartBitRHS];
    return Result;
  }
}

// If we've already found a root input value then we're never going to merge
// these back together.
if (FoundRoot)
  return Result;

// Okay, we got to something that isn't a shift, 'or', 'and', etc. This must
// be the root input value to the bswap/bitreverse.
FoundRoot = true;
Result = BitPart(V, BitWidth);
for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
  Result->Provenance[BitIdx] = BitIdx;
return Result;
3096}

3098static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To,
                                        unsigned BitWidth) {
if (From % 8 != To % 8)
  return false;
// Convert from bit indices to byte indices and check for a byte reversal.
From >>= 3;
To >>= 3;
BitWidth >>= 3;
return From == BitWidth - To - 1;
3107}

3109static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To,
                                             unsigned BitWidth) {
return From == BitWidth - To - 1;
3112}

3114bool llvm::recognizeBSwapOrBitReverseIdiom(
  Instruction *I, bool MatchBSwaps, bool MatchBitReversals,
  SmallVectorImpl<Instruction *> &InsertedInsts) {
if (!match(I, m_Or(m_Value(), m_Value())) &&
    !match(I, m_FShl(m_Value(), m_Value(), m_Value())) &&
    !match(I, m_FShr(m_Value(), m_Value(), m_Value())))
  return false;
if (!MatchBSwaps && !MatchBitReversals)
  return false;
Type *ITy = I->getType();
if (!ITy->isIntOrIntVectorTy() || ITy->getScalarSizeInBits() > 128)
  return false;  // Can't do integer/elements > 128 bits.

Type *DemandedTy = ITy;
if (I->hasOneUse())
  if (auto *Trunc = dyn_cast<TruncInst>(I->user_back()))
    DemandedTy = Trunc->getType();

// Try to find all the pieces corresponding to the bswap.
bool FoundRoot = false;
std::map<Value *, Optional<BitPart>> BPS;
const auto &Res =
    collectBitParts(I, MatchBSwaps, MatchBitReversals, BPS, 0, FoundRoot);
if (!Res)
  return false;
ArrayRef<int8_t> BitProvenance = Res->Provenance;
assert(all_of(BitProvenance,(static_cast<void> (0))
              [](int8_t I) { return I == BitPart::Unset || 0 <= I; }) &&(static_cast<void> (0))
       "Illegal bit provenance index")(static_cast<void> (0));

// If the upper bits are zero, then attempt to perform as a truncated op.
if (BitProvenance.back() == BitPart::Unset) {
  while (!BitProvenance.empty() && BitProvenance.back() == BitPart::Unset)
    BitProvenance = BitProvenance.drop_back();
  if (BitProvenance.empty())
    return false; // TODO - handle null value?
  DemandedTy = Type::getIntNTy(I->getContext(), BitProvenance.size());
  if (auto *IVecTy = dyn_cast<VectorType>(ITy))
    DemandedTy = VectorType::get(DemandedTy, IVecTy);
}

// Check BitProvenance hasn't found a source larger than the result type.
unsigned DemandedBW = DemandedTy->getScalarSizeInBits();
if (DemandedBW > ITy->getScalarSizeInBits())
  return false;

// Now, is the bit permutation correct for a bswap or a bitreverse? We can
// only byteswap values with an even number of bytes.
APInt DemandedMask = APInt::getAllOnesValue(DemandedBW);
bool OKForBSwap = MatchBSwaps && (DemandedBW % 16) == 0;
bool OKForBitReverse = MatchBitReversals;
for (unsigned BitIdx = 0;
     (BitIdx < DemandedBW) && (OKForBSwap || OKForBitReverse); ++BitIdx) {
  if (BitProvenance[BitIdx] == BitPart::Unset) {
    DemandedMask.clearBit(BitIdx);
    continue;
  }
  OKForBSwap &= bitTransformIsCorrectForBSwap(BitProvenance[BitIdx], BitIdx,
                                              DemandedBW);
  OKForBitReverse &= bitTransformIsCorrectForBitReverse(BitProvenance[BitIdx],
                                                        BitIdx, DemandedBW);
}

Intrinsic::ID Intrin;
if (OKForBSwap)
  Intrin = Intrinsic::bswap;
else if (OKForBitReverse)
  Intrin = Intrinsic::bitreverse;
else
  return false;

Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, DemandedTy);
Value *Provider = Res->Provider;

// We may need to truncate the provider.
if (DemandedTy != Provider->getType()) {
  auto *Trunc =
      CastInst::CreateIntegerCast(Provider, DemandedTy, false, "trunc", I);
  InsertedInsts.push_back(Trunc);
  Provider = Trunc;
}

Instruction *Result = CallInst::Create(F, Provider, "rev", I);
InsertedInsts.push_back(Result);

if (!DemandedMask.isAllOnesValue()) {
  auto *Mask = ConstantInt::get(DemandedTy, DemandedMask);
  Result = BinaryOperator::Create(Instruction::And, Result, Mask, "mask", I);
  InsertedInsts.push_back(Result);
}

// We may need to zeroextend back to the result type.
if (ITy != Result->getType()) {
  auto *ExtInst = CastInst::CreateIntegerCast(Result, ITy, false, "zext", I);
  InsertedInsts.push_back(ExtInst);
}

return true;
3212}

3214// CodeGen has special handling for some string functions that may replace
3215// them with target-specific intrinsics.  Since that'd skip our interceptors
3216// in ASan/MSan/TSan/DFSan, and thus make us miss some memory accesses,
3217// we mark affected calls as NoBuiltin, which will disable optimization
3218// in CodeGen.
3219void llvm::maybeMarkSanitizerLibraryCallNoBuiltin(
  CallInst *CI, const TargetLibraryInfo *TLI) {
Function *F = CI->getCalledFunction();
LibFunc Func;
if (F && !F->hasLocalLinkage() && F->hasName() &&
    TLI->getLibFunc(F->getName(), Func) && TLI->hasOptimizedCodeGen(Func) &&
    !F->doesNotAccessMemory())
  CI->addFnAttr(Attribute::NoBuiltin);
3227}

3229bool llvm::canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx) {
// We can't have a PHI with a metadata type.
if (I->getOperand(OpIdx)->getType()->isMetadataTy())
  return false;

// Early exit.
if (!isa<Constant>(I->getOperand(OpIdx)))
  return true;

switch (I->getOpcode()) {
default:
  return true;
case Instruction::Call:
case Instruction::Invoke: {
  const auto &CB = cast<CallBase>(*I);

  // Can't handle inline asm. Skip it.
  if (CB.isInlineAsm())
    return false;

  // Constant bundle operands may need to retain their constant-ness for
  // correctness.
  if (CB.isBundleOperand(OpIdx))
    return false;

  if (OpIdx < CB.getNumArgOperands()) {
    // Some variadic intrinsics require constants in the variadic arguments,
    // which currently aren't markable as immarg.
    if (isa<IntrinsicInst>(CB) &&
        OpIdx >= CB.getFunctionType()->getNumParams()) {
      // This is known to be OK for stackmap.
      return CB.getIntrinsicID() == Intrinsic::experimental_stackmap;
    }

    // gcroot is a special case, since it requires a constant argument which
    // isn't also required to be a simple ConstantInt.
    if (CB.getIntrinsicID() == Intrinsic::gcroot)
      return false;

    // Some intrinsic operands are required to be immediates.
    return !CB.paramHasAttr(OpIdx, Attribute::ImmArg);
  }

  // It is never allowed to replace the call argument to an intrinsic, but it
  // may be possible for a call.
  return !isa<IntrinsicInst>(CB);
}
case Instruction::ShuffleVector:
  // Shufflevector masks are constant.
  return OpIdx != 2;
case Instruction::Switch:
case Instruction::ExtractValue:
  // All operands apart from the first are constant.
  return OpIdx == 0;
case Instruction::InsertValue:
  // All operands apart from the first and the second are constant.
  return OpIdx < 2;
case Instruction::Alloca:
  // Static allocas (constant size in the entry block) are handled by
  // prologue/epilogue insertion so they're free anyway. We definitely don't
  // want to make them non-constant.
  return !cast<AllocaInst>(I)->isStaticAlloca();
case Instruction::GetElementPtr:
  if (OpIdx == 0)
    return true;
  gep_type_iterator It = gep_type_begin(I);
  for (auto E = std::next(It, OpIdx); It != E; ++It)
    if (It.isStruct())
      return false;
  return true;
}
3300}

3302Value *llvm::invertCondition(Value *Condition) {
// First: Check if it's a constant
if (Constant *C1.1
'C' is null
1
'C' is null
 = dyn_cast<Constant>(Condition))
1
Assuming 'Condition' is not a 'Constant'→
2
←
Taking false branch→
  return ConstantExpr::getNot(C);

// Second: If the condition is already inverted, return the original value
Value *NotCondition;
if (match(Condition, m_Not(m_Value(NotCondition))))
3
←
Calling 'match<llvm::Value, llvm::PatternMatch::BinaryOp_match<llvm::PatternMatch::bind_ty<llvm::Value>, llvm::PatternMatch::cstval_pred_ty<llvm::PatternMatch::is_all_ones, llvm::ConstantInt>, 30, true>>'→
12
←
Returning from 'match<llvm::Value, llvm::PatternMatch::BinaryOp_match<llvm::PatternMatch::bind_ty<llvm::Value>, llvm::PatternMatch::cstval_pred_ty<llvm::PatternMatch::is_all_ones, llvm::ConstantInt>, 30, true>>'→
13
←
Taking false branch→
  return NotCondition;

BasicBlock *Parent = nullptr;
14
←
'Parent' initialized to a null pointer value→
Instruction *Inst = dyn_cast<Instruction>(Condition);
15
←
Assuming 'Condition' is not a 'Instruction'→
if (Inst15.1
'Inst' is null
1
'Inst' is null
)
16
←
Taking false branch→
  Parent = Inst->getParent();
else if (Argument *Arg17.1
'Arg' is null
1
'Arg' is null
 = dyn_cast<Argument>(Condition))
17
←
Assuming 'Condition' is not a 'Argument'→
18
←
Taking false branch→
  Parent = &Arg->getParent()->getEntryBlock();
assert(Parent && "Unsupported condition to invert")(static_cast<void> (0));

// Third: Check all the users for an invert
for (User *U : Condition->users())
  if (Instruction *I = dyn_cast<Instruction>(U))
    if (I->getParent() == Parent && match(I, m_Not(m_Specific(Condition))))
      return I;

// Last option: Create a new instruction
auto *Inverted =
    BinaryOperator::CreateNot(Condition, Condition->getName() + ".inv");
if (Inst18.1
'Inst' is null
1
'Inst' is null
 && !isa<PHINode>(Inst))
  Inverted->insertAfter(Inst);
else
  Inverted->insertBefore(&*Parent->getFirstInsertionPt());
19
←
Called C++ object pointer is null
return Inverted;
3334}

3336bool llvm::inferAttributesFromOthers(Function &F) {
// Note: We explicitly check for attributes rather than using cover functions
// because some of the cover functions include the logic being implemented.

bool Changed = false;
// readnone + not convergent implies nosync
if (!F.hasFnAttribute(Attribute::NoSync) &&
    F.doesNotAccessMemory() && !F.isConvergent()) {
  F.setNoSync();
  Changed = true;
}

// readonly implies nofree
if (!F.hasFnAttribute(Attribute::NoFree) && F.onlyReadsMemory()) {
  F.setDoesNotFreeMemory();
  Changed = true;
}

// willreturn implies mustprogress
if (!F.hasFnAttribute(Attribute::MustProgress) && F.willReturn()) {
  F.setMustProgress();
  Changed = true;
}

// TODO: There are a bunch of cases of restrictive memory effects we
// can infer by inspecting arguments of argmemonly-ish functions.

return Changed;
3364}

←

/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include/llvm/IR/PatternMatch.h

1//===- PatternMatch.h - Match on the LLVM IR --------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file provides a simple and efficient mechanism for performing general
10// tree-based pattern matches on the LLVM IR. The power of these routines is
11// that it allows you to write concise patterns that are expressive and easy to
12// understand. The other major advantage of this is that it allows you to
13// trivially capture/bind elements in the pattern to variables. For example,
14// you can do something like this:
15//
16//  Value *Exp = ...
17//  Value *X, *Y;  ConstantInt *C1, *C2;      // (X & C1) | (Y & C2)
18//  if (match(Exp, m_Or(m_And(m_Value(X), m_ConstantInt(C1)),
19//                      m_And(m_Value(Y), m_ConstantInt(C2))))) {
20//    ... Pattern is matched and variables are bound ...
21//  }
22//
23// This is primarily useful to things like the instruction combiner, but can
24// also be useful for static analysis tools or code generators.
25//
26//===----------------------------------------------------------------------===//
27 
28#ifndef LLVM_IR_PATTERNMATCH_H
29#define LLVM_IR_PATTERNMATCH_H
30 
31#include "llvm/ADT/APFloat.h"
32#include "llvm/ADT/APInt.h"
33#include "llvm/IR/Constant.h"
34#include "llvm/IR/Constants.h"
35#include "llvm/IR/DataLayout.h"
36#include "llvm/IR/InstrTypes.h"
37#include "llvm/IR/Instruction.h"
38#include "llvm/IR/Instructions.h"
39#include "llvm/IR/IntrinsicInst.h"
40#include "llvm/IR/Intrinsics.h"
41#include "llvm/IR/Operator.h"
42#include "llvm/IR/Value.h"
43#include "llvm/Support/Casting.h"
44#include <cstdint>
45 
46namespace llvm {
47namespace PatternMatch {
48 
49template <typename Val, typename Pattern> bool match(Val *V, const Pattern &P) {
50  return const_cast<Pattern &>(P).match(V);
4
←
Calling 'BinaryOp_match::match'→
10
←
Returning from 'BinaryOp_match::match'→
11
←
Returning zero, which participates in a condition later→
51}
52 
53template <typename Pattern> bool match(ArrayRef<int> Mask, const Pattern &P) {
54  return const_cast<Pattern &>(P).match(Mask);
55}
56 
57template <typename SubPattern_t> struct OneUse_match {
58  SubPattern_t SubPattern;
59 
60  OneUse_match(const SubPattern_t &SP) : SubPattern(SP) {}
61 
62  template <typename OpTy> bool match(OpTy *V) {
63    return V->hasOneUse() && SubPattern.match(V);
64  }
65};
66 
67template <typename T> inline OneUse_match<T> m_OneUse(const T &SubPattern) {
68  return SubPattern;
69}
70 
71template <typename Class> struct class_match {
72  template <typename ITy> bool match(ITy *V) { return isa<Class>(V); }
73};
74 
75/// Match an arbitrary value and ignore it.
76inline class_match<Value> m_Value() { return class_match<Value>(); }
77 
78/// Match an arbitrary unary operation and ignore it.
79inline class_match<UnaryOperator> m_UnOp() {
80  return class_match<UnaryOperator>();
81}
82 
83/// Match an arbitrary binary operation and ignore it.
84inline class_match<BinaryOperator> m_BinOp() {
85  return class_match<BinaryOperator>();
86}
87 
88/// Matches any compare instruction and ignore it.
89inline class_match<CmpInst> m_Cmp() { return class_match<CmpInst>(); }
90 
91struct undef_match {
92  static bool check(const Value *V) {
93    if (isa<UndefValue>(V))
94      return true;
95 
96    const auto *CA = dyn_cast<ConstantAggregate>(V);
97    if (!CA)
98      return false;
99 
100    SmallPtrSet<const ConstantAggregate *, 8> Seen;
101    SmallVector<const ConstantAggregate *, 8> Worklist;
102 
103    // Either UndefValue, PoisonValue, or an aggregate that only contains
104    // these is accepted by matcher.
105    // CheckValue returns false if CA cannot satisfy this constraint.
106    auto CheckValue = [&](const ConstantAggregate *CA) {
107      for (const Value *Op : CA->operand_values()) {
108        if (isa<UndefValue>(Op))
109          continue;
110 
111        const auto *CA = dyn_cast<ConstantAggregate>(Op);
112        if (!CA)
113          return false;
114        if (Seen.insert(CA).second)
115          Worklist.emplace_back(CA);
116      }
117 
118      return true;
119    };
120 
121    if (!CheckValue(CA))
122      return false;
123 
124    while (!Worklist.empty()) {
125      if (!CheckValue(Worklist.pop_back_val()))
126        return false;
127    }
128    return true;
129  }
130  template <typename ITy> bool match(ITy *V) { return check(V); }
131};
132 
133/// Match an arbitrary undef constant. This matches poison as well.
134/// If this is an aggregate and contains a non-aggregate element that is
135/// neither undef nor poison, the aggregate is not matched.
136inline auto m_Undef() { return undef_match(); }
137 
138/// Match an arbitrary poison constant.
139inline class_match<PoisonValue> m_Poison() { return class_match<PoisonValue>(); }
140 
141/// Match an arbitrary Constant and ignore it.
142inline class_match<Constant> m_Constant() { return class_match<Constant>(); }
143 
144/// Match an arbitrary ConstantInt and ignore it.
145inline class_match<ConstantInt> m_ConstantInt() {
146  return class_match<ConstantInt>();
147}
148 
149/// Match an arbitrary ConstantFP and ignore it.
150inline class_match<ConstantFP> m_ConstantFP() {
151  return class_match<ConstantFP>();
152}
153 
154/// Match an arbitrary ConstantExpr and ignore it.
155inline class_match<ConstantExpr> m_ConstantExpr() {
156  return class_match<ConstantExpr>();
157}
158 
159/// Match an arbitrary basic block value and ignore it.
160inline class_match<BasicBlock> m_BasicBlock() {
161  return class_match<BasicBlock>();
162}
163 
164/// Inverting matcher
165template <typename Ty> struct match_unless {
166  Ty M;
167 
168  match_unless(const Ty &Matcher) : M(Matcher) {}
169 
170  template <typename ITy> bool match(ITy *V) { return !M.match(V); }
171};
172 
173/// Match if the inner matcher does *NOT* match.
174template <typename Ty> inline match_unless<Ty> m_Unless(const Ty &M) {
175  return match_unless<Ty>(M);
176}
177 
178/// Matching combinators
179template <typename LTy, typename RTy> struct match_combine_or {
180  LTy L;
181  RTy R;
182 
183  match_combine_or(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
184 
185  template <typename ITy> bool match(ITy *V) {
186    if (L.match(V))
187      return true;
188    if (R.match(V))
189      return true;
190    return false;
191  }
192};
193 
194template <typename LTy, typename RTy> struct match_combine_and {
195  LTy L;
196  RTy R;
197 
198  match_combine_and(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
199 
200  template <typename ITy> bool match(ITy *V) {
201    if (L.match(V))
202      if (R.match(V))
203        return true;
204    return false;
205  }
206};
207 
208/// Combine two pattern matchers matching L || R
209template <typename LTy, typename RTy>
210inline match_combine_or<LTy, RTy> m_CombineOr(const LTy &L, const RTy &R) {
211  return match_combine_or<LTy, RTy>(L, R);
212}
213 
214/// Combine two pattern matchers matching L && R
215template <typename LTy, typename RTy>
216inline match_combine_and<LTy, RTy> m_CombineAnd(const LTy &L, const RTy &R) {
217  return match_combine_and<LTy, RTy>(L, R);
218}
219 
220struct apint_match {
221  const APInt *&Res;
222  bool AllowUndef;
223 
224  apint_match(const APInt *&Res, bool AllowUndef)
225    : Res(Res), AllowUndef(AllowUndef) {}
226 
227  template <typename ITy> bool match(ITy *V) {
228    if (auto *CI = dyn_cast<ConstantInt>(V)) {
229      Res = &CI->getValue();
230      return true;
231    }
232    if (V->getType()->isVectorTy())
233      if (const auto *C = dyn_cast<Constant>(V))
234        if (auto *CI = dyn_cast_or_null<ConstantInt>(
235                C->getSplatValue(AllowUndef))) {
236          Res = &CI->getValue();
237          return true;
238        }
239    return false;
240  }
241};
242// Either constexpr if or renaming ConstantFP::getValueAPF to
243// ConstantFP::getValue is needed to do it via single template
244// function for both apint/apfloat.
245struct apfloat_match {
246  const APFloat *&Res;
247  bool AllowUndef;
248 
249  apfloat_match(const APFloat *&Res, bool AllowUndef)
250      : Res(Res), AllowUndef(AllowUndef) {}
251 
252  template <typename ITy> bool match(ITy *V) {
253    if (auto *CI = dyn_cast<ConstantFP>(V)) {
254      Res = &CI->getValueAPF();
255      return true;
256    }
257    if (V->getType()->isVectorTy())
258      if (const auto *C = dyn_cast<Constant>(V))
259        if (auto *CI = dyn_cast_or_null<ConstantFP>(
260                C->getSplatValue(AllowUndef))) {
261          Res = &CI->getValueAPF();
262          return true;
263        }
264    return false;
265  }
266};
267 
268/// Match a ConstantInt or splatted ConstantVector, binding the
269/// specified pointer to the contained APInt.
270inline apint_match m_APInt(const APInt *&Res) {
271  // Forbid undefs by default to maintain previous behavior.
272  return apint_match(Res, /* AllowUndef */ false);
273}
274 
275/// Match APInt while allowing undefs in splat vector constants.
276inline apint_match m_APIntAllowUndef(const APInt *&Res) {
277  return apint_match(Res, /* AllowUndef */ true);
278}
279 
280/// Match APInt while forbidding undefs in splat vector constants.
281inline apint_match m_APIntForbidUndef(const APInt *&Res) {
282  return apint_match(Res, /* AllowUndef */ false);
283}
284 
285/// Match a ConstantFP or splatted ConstantVector, binding the
286/// specified pointer to the contained APFloat.
287inline apfloat_match m_APFloat(const APFloat *&Res) {
288  // Forbid undefs by default to maintain previous behavior.
289  return apfloat_match(Res, /* AllowUndef */ false);
290}
291 
292/// Match APFloat while allowing undefs in splat vector constants.
293inline apfloat_match m_APFloatAllowUndef(const APFloat *&Res) {
294  return apfloat_match(Res, /* AllowUndef */ true);
295}
296 
297/// Match APFloat while forbidding undefs in splat vector constants.
298inline apfloat_match m_APFloatForbidUndef(const APFloat *&Res) {
299  return apfloat_match(Res, /* AllowUndef */ false);
300}
301 
302template <int64_t Val> struct constantint_match {
303  template <typename ITy> bool match(ITy *V) {
304    if (const auto *CI = dyn_cast<ConstantInt>(V)) {
305      const APInt &CIV = CI->getValue();
306      if (Val >= 0)
307        return CIV == static_cast<uint64_t>(Val);
308      // If Val is negative, and CI is shorter than it, truncate to the right
309      // number of bits.  If it is larger, then we have to sign extend.  Just
310      // compare their negated values.
311      return -CIV == -Val;
312    }
313    return false;
314  }
315};
316 
317/// Match a ConstantInt with a specific value.
318template <int64_t Val> inline constantint_match<Val> m_ConstantInt() {
319  return constantint_match<Val>();
320}
321 
322/// This helper class is used to match constant scalars, vector splats,
323/// and fixed width vectors that satisfy a specified predicate.
324/// For fixed width vector constants, undefined elements are ignored.
325template <typename Predicate, typename ConstantVal>
326struct cstval_pred_ty : public Predicate {
327  template <typename ITy> bool match(ITy *V) {
328    if (const auto *CV = dyn_cast<ConstantVal>(V))
329      return this->isValue(CV->getValue());
330    if (const auto *VTy = dyn_cast<VectorType>(V->getType())) {
331      if (const auto *C = dyn_cast<Constant>(V)) {
332        if (const auto *CV = dyn_cast_or_null<ConstantVal>(C->getSplatValue()))
333          return this->isValue(CV->getValue());
334 
335        // Number of elements of a scalable vector unknown at compile time
336        auto *FVTy = dyn_cast<FixedVectorType>(VTy);
337        if (!FVTy)
338          return false;
339 
340        // Non-splat vector constant: check each element for a match.
341        unsigned NumElts = FVTy->getNumElements();
342        assert(NumElts != 0 && "Constant vector with no elements?")(static_cast<void> (0));
343        bool HasNonUndefElements = false;
344        for (unsigned i = 0; i != NumElts; ++i) {
345          Constant *Elt = C->getAggregateElement(i);
346          if (!Elt)
347            return false;
348          if (isa<UndefValue>(Elt))
349            continue;
350          auto *CV = dyn_cast<ConstantVal>(Elt);
351          if (!CV || !this->isValue(CV->getValue()))
352            return false;
353          HasNonUndefElements = true;
354        }
355        return HasNonUndefElements;
356      }
357    }
358    return false;
359  }
360};
361 
362/// specialization of cstval_pred_ty for ConstantInt
363template <typename Predicate>
364using cst_pred_ty = cstval_pred_ty<Predicate, ConstantInt>;
365 
366/// specialization of cstval_pred_ty for ConstantFP
367template <typename Predicate>
368using cstfp_pred_ty = cstval_pred_ty<Predicate, ConstantFP>;
369 
370/// This helper class is used to match scalar and vector constants that
371/// satisfy a specified predicate, and bind them to an APInt.
372template <typename Predicate> struct api_pred_ty : public Predicate {
373  const APInt *&Res;
374 
375  api_pred_ty(const APInt *&R) : Res(R) {}
376 
377  template <typename ITy> bool match(ITy *V) {
378    if (const auto *CI = dyn_cast<ConstantInt>(V))
379      if (this->isValue(CI->getValue())) {
380        Res = &CI->getValue();
381        return true;
382      }
383    if (V->getType()->isVectorTy())
384      if (const auto *C = dyn_cast<Constant>(V))
385        if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue()))
386          if (this->isValue(CI->getValue())) {
387            Res = &CI->getValue();
388            return true;
389          }
390 
391    return false;
392  }
393};
394 
395/// This helper class is used to match scalar and vector constants that
396/// satisfy a specified predicate, and bind them to an APFloat.
397/// Undefs are allowed in splat vector constants.
398template <typename Predicate> struct apf_pred_ty : public Predicate {
399  const APFloat *&Res;
400 
401  apf_pred_ty(const APFloat *&R) : Res(R) {}
402 
403  template <typename ITy> bool match(ITy *V) {
404    if (const auto *CI = dyn_cast<ConstantFP>(V))
405      if (this->isValue(CI->getValue())) {
406        Res = &CI->getValue();
407        return true;
408      }
409    if (V->getType()->isVectorTy())
410      if (const auto *C = dyn_cast<Constant>(V))
411        if (auto *CI = dyn_cast_or_null<ConstantFP>(
412                C->getSplatValue(/* AllowUndef */ true)))
413          if (this->isValue(CI->getValue())) {
414            Res = &CI->getValue();
415            return true;
416          }
417 
418    return false;
419  }
420};
421 
422///////////////////////////////////////////////////////////////////////////////
423//
424// Encapsulate constant value queries for use in templated predicate matchers.
425// This allows checking if constants match using compound predicates and works
426// with vector constants, possibly with relaxed constraints. For example, ignore
427// undef values.
428//
429///////////////////////////////////////////////////////////////////////////////
430 
431struct is_any_apint {
432  bool isValue(const APInt &C) { return true; }
433};
434/// Match an integer or vector with any integral constant.
435/// For vectors, this includes constants with undefined elements.
436inline cst_pred_ty<is_any_apint> m_AnyIntegralConstant() {
437  return cst_pred_ty<is_any_apint>();
438}
439 
440struct is_all_ones {
441  bool isValue(const APInt &C) { return C.isAllOnesValue(); }
442};
443/// Match an integer or vector with all bits set.
444/// For vectors, this includes constants with undefined elements.
445inline cst_pred_ty<is_all_ones> m_AllOnes() {
446  return cst_pred_ty<is_all_ones>();
447}
448 
449struct is_maxsignedvalue {
450  bool isValue(const APInt &C) { return C.isMaxSignedValue(); }
451};
452/// Match an integer or vector with values having all bits except for the high
453/// bit set (0x7f...).
454/// For vectors, this includes constants with undefined elements.
455inline cst_pred_ty<is_maxsignedvalue> m_MaxSignedValue() {
456  return cst_pred_ty<is_maxsignedvalue>();
457}
458inline api_pred_ty<is_maxsignedvalue> m_MaxSignedValue(const APInt *&V) {
459  return V;
460}
461 
462struct is_negative {
463  bool isValue(const APInt &C) { return C.isNegative(); }
464};
465/// Match an integer or vector of negative values.
466/// For vectors, this includes constants with undefined elements.
467inline cst_pred_ty<is_negative> m_Negative() {
468  return cst_pred_ty<is_negative>();
469}
470inline api_pred_ty<is_negative> m_Negative(const APInt *&V) {
471  return V;
472}
473 
474struct is_nonnegative {
475  bool isValue(const APInt &C) { return C.isNonNegative(); }
476};
477/// Match an integer or vector of non-negative values.
478/// For vectors, this includes constants with undefined elements.
479inline cst_pred_ty<is_nonnegative> m_NonNegative() {
480  return cst_pred_ty<is_nonnegative>();
481}
482inline api_pred_ty<is_nonnegative> m_NonNegative(const APInt *&V) {
483  return V;
484}
485 
486struct is_strictlypositive {
487  bool isValue(const APInt &C) { return C.isStrictlyPositive(); }
488};
489/// Match an integer or vector of strictly positive values.
490/// For vectors, this includes constants with undefined elements.
491inline cst_pred_ty<is_strictlypositive> m_StrictlyPositive() {
492  return cst_pred_ty<is_strictlypositive>();
493}
494inline api_pred_ty<is_strictlypositive> m_StrictlyPositive(const APInt *&V) {
495  return V;
496}
497 
498struct is_nonpositive {
499  bool isValue(const APInt &C) { return C.isNonPositive(); }
500};
501/// Match an integer or vector of non-positive values.
502/// For vectors, this includes constants with undefined elements.
503inline cst_pred_ty<is_nonpositive> m_NonPositive() {
504  return cst_pred_ty<is_nonpositive>();
505}
506inline api_pred_ty<is_nonpositive> m_NonPositive(const APInt *&V) { return V; }
507 
508struct is_one {
509  bool isValue(const APInt &C) { return C.isOneValue(); }
510};
511/// Match an integer 1 or a vector with all elements equal to 1.
512/// For vectors, this includes constants with undefined elements.
513inline cst_pred_ty<is_one> m_One() {
514  return cst_pred_ty<is_one>();
515}
516 
517struct is_zero_int {
518  bool isValue(const APInt &C) { return C.isNullValue(); }
519};
520/// Match an integer 0 or a vector with all elements equal to 0.
521/// For vectors, this includes constants with undefined elements.
522inline cst_pred_ty<is_zero_int> m_ZeroInt() {
523  return cst_pred_ty<is_zero_int>();
524}
525 
526struct is_zero {
527  template <typename ITy> bool match(ITy *V) {
528    auto *C = dyn_cast<Constant>(V);
529    // FIXME: this should be able to do something for scalable vectors
530    return C && (C->isNullValue() || cst_pred_ty<is_zero_int>().match(C));
531  }
532};
533/// Match any null constant or a vector with all elements equal to 0.
534/// For vectors, this includes constants with undefined elements.
535inline is_zero m_Zero() {
536  return is_zero();
537}
538 
539struct is_power2 {
540  bool isValue(const APInt &C) { return C.isPowerOf2(); }
541};
542/// Match an integer or vector power-of-2.
543/// For vectors, this includes constants with undefined elements.
544inline cst_pred_ty<is_power2> m_Power2() {
545  return cst_pred_ty<is_power2>();
546}
547inline api_pred_ty<is_power2> m_Power2(const APInt *&V) {
548  return V;
549}
550 
551struct is_negated_power2 {
552  bool isValue(const APInt &C) { return (-C).isPowerOf2(); }
553};
554/// Match a integer or vector negated power-of-2.
555/// For vectors, this includes constants with undefined elements.
556inline cst_pred_ty<is_negated_power2> m_NegatedPower2() {
557  return cst_pred_ty<is_negated_power2>();
558}
559inline api_pred_ty<is_negated_power2> m_NegatedPower2(const APInt *&V) {
560  return V;
561}
562 
563struct is_power2_or_zero {
564  bool isValue(const APInt &C) { return !C || C.isPowerOf2(); }
565};
566/// Match an integer or vector of 0 or power-of-2 values.
567/// For vectors, this includes constants with undefined elements.
568inline cst_pred_ty<is_power2_or_zero> m_Power2OrZero() {
569  return cst_pred_ty<is_power2_or_zero>();
570}
571inline api_pred_ty<is_power2_or_zero> m_Power2OrZero(const APInt *&V) {
572  return V;
573}
574 
575struct is_sign_mask {
576  bool isValue(const APInt &C) { return C.isSignMask(); }
577};
578/// Match an integer or vector with only the sign bit(s) set.
579/// For vectors, this includes constants with undefined elements.
580inline cst_pred_ty<is_sign_mask> m_SignMask() {
581  return cst_pred_ty<is_sign_mask>();
582}
583 
584struct is_lowbit_mask {
585  bool isValue(const APInt &C) { return C.isMask(); }
586};
587/// Match an integer or vector with only the low bit(s) set.
588/// For vectors, this includes constants with undefined elements.
589inline cst_pred_ty<is_lowbit_mask> m_LowBitMask() {
590  return cst_pred_ty<is_lowbit_mask>();
591}
592 
593struct icmp_pred_with_threshold {
594  ICmpInst::Predicate Pred;
595  const APInt *Thr;
596  bool isValue(const APInt &C) {
597    switch (Pred) {
598    case ICmpInst::Predicate::ICMP_EQ:
599      return C.eq(*Thr);
600    case ICmpInst::Predicate::ICMP_NE:
601      return C.ne(*Thr);
602    case ICmpInst::Predicate::ICMP_UGT:
603      return C.ugt(*Thr);
604    case ICmpInst::Predicate::ICMP_UGE:
605      return C.uge(*Thr);
606    case ICmpInst::Predicate::ICMP_ULT:
607      return C.ult(*Thr);
608    case ICmpInst::Predicate::ICMP_ULE:
609      return C.ule(*Thr);
610    case ICmpInst::Predicate::ICMP_SGT:
611      return C.sgt(*Thr);
612    case ICmpInst::Predicate::ICMP_SGE:
613      return C.sge(*Thr);
614    case ICmpInst::Predicate::ICMP_SLT:
615      return C.slt(*Thr);
616    case ICmpInst::Predicate::ICMP_SLE:
617      return C.sle(*Thr);
618    default:
619      llvm_unreachable("Unhandled ICmp predicate")__builtin_unreachable();
620    }
621  }
622};
623/// Match an integer or vector with every element comparing 'pred' (eg/ne/...)
624/// to Threshold. For vectors, this includes constants with undefined elements.
625inline cst_pred_ty<icmp_pred_with_threshold>
626m_SpecificInt_ICMP(ICmpInst::Predicate Predicate, const APInt &Threshold) {
627  cst_pred_ty<icmp_pred_with_threshold> P;
628  P.Pred = Predicate;
629  P.Thr = &Threshold;
630  return P;
631}
632 
633struct is_nan {
634  bool isValue(const APFloat &C) { return C.isNaN(); }
635};
636/// Match an arbitrary NaN constant. This includes quiet and signalling nans.
637/// For vectors, this includes constants with undefined elements.
638inline cstfp_pred_ty<is_nan> m_NaN() {
639  return cstfp_pred_ty<is_nan>();
640}
641 
642struct is_nonnan {
643  bool isValue(const APFloat &C) { return !C.isNaN(); }
644};
645/// Match a non-NaN FP constant.
646/// For vectors, this includes constants with undefined elements.
647inline cstfp_pred_ty<is_nonnan> m_NonNaN() {
648  return cstfp_pred_ty<is_nonnan>();
649}
650 
651struct is_inf {
652  bool isValue(const APFloat &C) { return C.isInfinity(); }
653};
654/// Match a positive or negative infinity FP constant.
655/// For vectors, this includes constants with undefined elements.
656inline cstfp_pred_ty<is_inf> m_Inf() {
657  return cstfp_pred_ty<is_inf>();
658}
659 
660struct is_noninf {
661  bool isValue(const APFloat &C) { return !C.isInfinity(); }
662};
663/// Match a non-infinity FP constant, i.e. finite or NaN.
664/// For vectors, this includes constants with undefined elements.
665inline cstfp_pred_ty<is_noninf> m_NonInf() {
666  return cstfp_pred_ty<is_noninf>();
667}
668 
669struct is_finite {
670  bool isValue(const APFloat &C) { return C.isFinite(); }
671};
672/// Match a finite FP constant, i.e. not infinity or NaN.
673/// For vectors, this includes constants with undefined elements.
674inline cstfp_pred_ty<is_finite> m_Finite() {
675  return cstfp_pred_ty<is_finite>();
676}
677inline apf_pred_ty<is_finite> m_Finite(const APFloat *&V) { return V; }
678 
679struct is_finitenonzero {
680  bool isValue(const APFloat &C) { return C.isFiniteNonZero(); }
681};
682/// Match a finite non-zero FP constant.
683/// For vectors, this includes constants with undefined elements.
684inline cstfp_pred_ty<is_finitenonzero> m_FiniteNonZero() {
685  return cstfp_pred_ty<is_finitenonzero>();
686}
687inline apf_pred_ty<is_finitenonzero> m_FiniteNonZero(const APFloat *&V) {
688  return V;
689}
690 
691struct is_any_zero_fp {
692  bool isValue(const APFloat &C) { return C.isZero(); }
693};
694/// Match a floating-point negative zero or positive zero.
695/// For vectors, this includes constants with undefined elements.
696inline cstfp_pred_ty<is_any_zero_fp> m_AnyZeroFP() {
697  return cstfp_pred_ty<is_any_zero_fp>();
698}
699 
700struct is_pos_zero_fp {
701  bool isValue(const APFloat &C) { return C.isPosZero(); }
702};
703/// Match a floating-point positive zero.
704/// For vectors, this includes constants with undefined elements.
705inline cstfp_pred_ty<is_pos_zero_fp> m_PosZeroFP() {
706  return cstfp_pred_ty<is_pos_zero_fp>();
707}
708 
709struct is_neg_zero_fp {
710  bool isValue(const APFloat &C) { return C.isNegZero(); }
711};
712/// Match a floating-point negative zero.
713/// For vectors, this includes constants with undefined elements.
714inline cstfp_pred_ty<is_neg_zero_fp> m_NegZeroFP() {
715  return cstfp_pred_ty<is_neg_zero_fp>();
716}
717 
718struct is_non_zero_fp {
719  bool isValue(const APFloat &C) { return C.isNonZero(); }
720};
721/// Match a floating-point non-zero.
722/// For vectors, this includes constants with undefined elements.
723inline cstfp_pred_ty<is_non_zero_fp> m_NonZeroFP() {
724  return cstfp_pred_ty<is_non_zero_fp>();
725}
726 
727///////////////////////////////////////////////////////////////////////////////
728 
729template <typename Class> struct bind_ty {
730  Class *&VR;
731 
732  bind_ty(Class *&V) : VR(V) {}
733 
734  template <typename ITy> bool match(ITy *V) {
735    if (auto *CV = dyn_cast<Class>(V)) {
736      VR = CV;
737      return true;
738    }
739    return false;
740  }
741};
742 
743/// Match a value, capturing it if we match.
744inline bind_ty<Value> m_Value(Value *&V) { return V; }
745inline bind_ty<const Value> m_Value(const Value *&V) { return V; }
746 
747/// Match an instruction, capturing it if we match.
748inline bind_ty<Instruction> m_Instruction(Instruction *&I) { return I; }
749/// Match a unary operator, capturing it if we match.
750inline bind_ty<UnaryOperator> m_UnOp(UnaryOperator *&I) { return I; }
751/// Match a binary operator, capturing it if we match.
752inline bind_ty<BinaryOperator> m_BinOp(BinaryOperator *&I) { return I; }
753/// Match a with overflow intrinsic, capturing it if we match.
754inline bind_ty<WithOverflowInst> m_WithOverflowInst(WithOverflowInst *&I) { return I; }
755inline bind_ty<const WithOverflowInst>
756m_WithOverflowInst(const WithOverflowInst *&I) {
757  return I;
758}
759 
760/// Match a Constant, capturing the value if we match.
761inline bind_ty<Constant> m_Constant(Constant *&C) { return C; }
762 
763/// Match a ConstantInt, capturing the value if we match.
764inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
765 
766/// Match a ConstantFP, capturing the value if we match.
767inline bind_ty<ConstantFP> m_ConstantFP(ConstantFP *&C) { return C; }
768 
769/// Match a ConstantExpr, capturing the value if we match.
770inline bind_ty<ConstantExpr> m_ConstantExpr(ConstantExpr *&C) { return C; }
771 
772/// Match a basic block value, capturing it if we match.
773inline bind_ty<BasicBlock> m_BasicBlock(BasicBlock *&V) { return V; }
774inline bind_ty<const BasicBlock> m_BasicBlock(const BasicBlock *&V) {
775  return V;
776}
777 
778/// Match an arbitrary immediate Constant and ignore it.
779inline match_combine_and<class_match<Constant>,
780                         match_unless<class_match<ConstantExpr>>>
781m_ImmConstant() {
782  return m_CombineAnd(m_Constant(), m_Unless(m_ConstantExpr()));
783}
784 
785/// Match an immediate Constant, capturing the value if we match.
786inline match_combine_and<bind_ty<Constant>,
787                         match_unless<class_match<ConstantExpr>>>
788m_ImmConstant(Constant *&C) {
789  return m_CombineAnd(m_Constant(C), m_Unless(m_ConstantExpr()));
790}
791 
792/// Match a specified Value*.
793struct specificval_ty {
794  const Value *Val;
795 
796  specificval_ty(const Value *V) : Val(V) {}
797 
798  template <typename ITy> bool match(ITy *V) { return V == Val; }
799};
800 
801/// Match if we have a specific specified value.
802inline specificval_ty m_Specific(const Value *V) { return V; }
803 
804/// Stores a reference to the Value *, not the Value * itself,
805/// thus can be used in commutative matchers.
806template <typename Class> struct deferredval_ty {
807  Class *const &Val;
808 
809  deferredval_ty(Class *const &V) : Val(V) {}
810 
811  template <typename ITy> bool match(ITy *const V) { return V == Val; }
812};
813 
814/// Like m_Specific(), but works if the specific value to match is determined
815/// as part of the same match() expression. For example:
816/// m_Add(m_Value(X), m_Specific(X)) is incorrect, because m_Specific() will
817/// bind X before the pattern match starts.
818/// m_Add(m_Value(X), m_Deferred(X)) is correct, and will check against
819/// whichever value m_Value(X) populated.
820inline deferredval_ty<Value> m_Deferred(Value *const &V) { return V; }
821inline deferredval_ty<const Value> m_Deferred(const Value *const &V) {
822  return V;
823}
824 
825/// Match a specified floating point value or vector of all elements of
826/// that value.
827struct specific_fpval {
828  double Val;
829 
830  specific_fpval(double V) : Val(V) {}
831 
832  template <typename ITy> bool match(ITy *V) {
833    if (const auto *CFP = dyn_cast<ConstantFP>(V))
834      return CFP->isExactlyValue(Val);
835    if (V->getType()->isVectorTy())
836      if (const auto *C = dyn_cast<Constant>(V))
837        if (auto *CFP = dyn_cast_or_null<ConstantFP>(C->getSplatValue()))
838          return CFP->isExactlyValue(Val);
839    return false;
840  }
841};
842 
843/// Match a specific floating point value or vector with all elements
844/// equal to the value.
845inline specific_fpval m_SpecificFP(double V) { return specific_fpval(V); }
846 
847/// Match a float 1.0 or vector with all elements equal to 1.0.
848inline specific_fpval m_FPOne() { return m_SpecificFP(1.0); }
849 
850struct bind_const_intval_ty {
851  uint64_t &VR;
852 
853  bind_const_intval_ty(uint64_t &V) : VR(V) {}
854 
855  template <typename ITy> bool match(ITy *V) {
856    if (const auto *CV = dyn_cast<ConstantInt>(V))
857      if (CV->getValue().ule(UINT64_MAX(18446744073709551615UL))) {
858        VR = CV->getZExtValue();
859        return true;
860      }
861    return false;
862  }
863};
864 
865/// Match a specified integer value or vector of all elements of that
866/// value.
867template <bool AllowUndefs>
868struct specific_intval {
869  APInt Val;
870 
871  specific_intval(APInt V) : Val(std::move(V)) {}
872 
873  template <typename ITy> bool match(ITy *V) {
874    const auto *CI = dyn_cast<ConstantInt>(V);
875    if (!CI && V->getType()->isVectorTy())
876      if (const auto *C = dyn_cast<Constant>(V))
877        CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue(AllowUndefs));
878 
879    return CI && APInt::isSameValue(CI->getValue(), Val);
880  }
881};
882 
883/// Match a specific integer value or vector with all elements equal to
884/// the value.
885inline specific_intval<false> m_SpecificInt(APInt V) {
886  return specific_intval<false>(std::move(V));
887}
888 
889inline specific_intval<false> m_SpecificInt(uint64_t V) {
890  return m_SpecificInt(APInt(64, V));
891}
892 
893inline specific_intval<true> m_SpecificIntAllowUndef(APInt V) {
894  return specific_intval<true>(std::move(V));
895}
896 
897inline specific_intval<true> m_SpecificIntAllowUndef(uint64_t V) {
898  return m_SpecificIntAllowUndef(APInt(64, V));
899}
900 
901/// Match a ConstantInt and bind to its value.  This does not match
902/// ConstantInts wider than 64-bits.
903inline bind_const_intval_ty m_ConstantInt(uint64_t &V) { return V; }
904 
905/// Match a specified basic block value.
906struct specific_bbval {
907  BasicBlock *Val;
908 
909  specific_bbval(BasicBlock *Val) : Val(Val) {}
910 
911  template <typename ITy> bool match(ITy *V) {
912    const auto *BB = dyn_cast<BasicBlock>(V);
913    return BB && BB == Val;
914  }
915};
916 
917/// Match a specific basic block value.
918inline specific_bbval m_SpecificBB(BasicBlock *BB) {
919  return specific_bbval(BB);
920}
921 
922/// A commutative-friendly version of m_Specific().
923inline deferredval_ty<BasicBlock> m_Deferred(BasicBlock *const &BB) {
924  return BB;
925}
926inline deferredval_ty<const BasicBlock>
927m_Deferred(const BasicBlock *const &BB) {
928  return BB;
929}
930 
931//===----------------------------------------------------------------------===//
932// Matcher for any binary operator.
933//
934template <typename LHS_t, typename RHS_t, bool Commutable = false>
935struct AnyBinaryOp_match {
936  LHS_t L;
937  RHS_t R;
938 
939  // The evaluation order is always stable, regardless of Commutability.
940  // The LHS is always matched first.
941  AnyBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
942 
943  template <typename OpTy> bool match(OpTy *V) {
944    if (auto *I = dyn_cast<BinaryOperator>(V))
945      return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
946             (Commutable && L.match(I->getOperand(1)) &&
947              R.match(I->getOperand(0)));
948    return false;
949  }
950};
951 
952template <typename LHS, typename RHS>
953inline AnyBinaryOp_match<LHS, RHS> m_BinOp(const LHS &L, const RHS &R) {
954  return AnyBinaryOp_match<LHS, RHS>(L, R);
955}
956 
957//===----------------------------------------------------------------------===//
958// Matcher for any unary operator.
959// TODO fuse unary, binary matcher into n-ary matcher
960//
961template <typename OP_t> struct AnyUnaryOp_match {
962  OP_t X;
963 
964  AnyUnaryOp_match(const OP_t &X) : X(X) {}
965 
966  template <typename OpTy> bool match(OpTy *V) {
967    if (auto *I = dyn_cast<UnaryOperator>(V))
968      return X.match(I->getOperand(0));
969    return false;
970  }
971};
972 
973template <typename OP_t> inline AnyUnaryOp_match<OP_t> m_UnOp(const OP_t &X) {
974  return AnyUnaryOp_match<OP_t>(X);
975}
976 
977//===----------------------------------------------------------------------===//
978// Matchers for specific binary operators.
979//
980 
981template <typename LHS_t, typename RHS_t, unsigned Opcode,
982          bool Commutable = false>
983struct BinaryOp_match {
984  LHS_t L;
985  RHS_t R;
986 
987  // The evaluation order is always stable, regardless of Commutability.
988  // The LHS is always matched first.
989  BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
990 
991  template <typename OpTy> bool match(OpTy *V) {
992    if (V->getValueID() == Value::InstructionVal + Opcode) {
5
←
Assuming the condition is false→
6
←
Taking false branch→
993      auto *I = cast<BinaryOperator>(V);
994      return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
995             (Commutable && L.match(I->getOperand(1)) &&
996              R.match(I->getOperand(0)));
997    }
998    if (auto *CE7.1
'CE' is null
7.1
'CE' is null
 = dyn_cast<ConstantExpr>(V))
7
←
Assuming 'V' is not a 'ConstantExpr'→
8
←
Taking false branch→
999      return CE->getOpcode() == Opcode &&
1000             ((L.match(CE->getOperand(0)) && R.match(CE->getOperand(1))) ||
1001              (Commutable && L.match(CE->getOperand(1)) &&
1002               R.match(CE->getOperand(0))));
1003    return false;
9
←
Returning zero, which participates in a condition later→
1004  }
1005};
1006 
1007template <typename LHS, typename RHS>
1008inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
1009                                                        const RHS &R) {
1010  return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
1011}
1012 
1013template <typename LHS, typename RHS>
1014inline BinaryOp_match<LHS, RHS, Instruction::FAdd> m_FAdd(const LHS &L,
1015                                                          const RHS &R) {
1016  return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R);
1017}
1018 
1019template <typename LHS, typename RHS>
1020inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L,
1021                                                        const RHS &R) {
1022  return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
1023}
1024 
1025template <typename LHS, typename RHS>
1026inline BinaryOp_match<LHS, RHS, Instruction::FSub> m_FSub(const LHS &L,
1027                                                          const RHS &R) {
1028  return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R);
1029}
1030 
1031template <typename Op_t> struct FNeg_match {
1032  Op_t X;
1033 
1034  FNeg_match(const Op_t &Op) : X(Op) {}
1035  template <typename OpTy> bool match(OpTy *V) {
1036    auto *FPMO = dyn_cast<FPMathOperator>(V);
1037    if (!FPMO) return false;
1038 
1039    if (FPMO->getOpcode() == Instruction::FNeg)
1040      return X.match(FPMO->getOperand(0));
1041 
1042    if (FPMO->getOpcode() == Instruction::FSub) {
1043      if (FPMO->hasNoSignedZeros()) {
1044        // With 'nsz', any zero goes.
1045        if (!cstfp_pred_ty<is_any_zero_fp>().match(FPMO->getOperand(0)))
1046          return false;
1047      } else {
1048        // Without 'nsz', we need fsub -0.0, X exactly.
1049        if (!cstfp_pred_ty<is_neg_zero_fp>().match(FPMO->getOperand(0)))
1050          return false;
1051      }
1052 
1053      return X.match(FPMO->getOperand(1));
1054    }
1055 
1056    return false;
1057  }
1058};
1059 
1060/// Match 'fneg X' as 'fsub -0.0, X'.
1061template <typename OpTy>
1062inline FNeg_match<OpTy>
1063m_FNeg(const OpTy &X) {
1064  return FNeg_match<OpTy>(X);
1065}
1066 
1067/// Match 'fneg X' as 'fsub +-0.0, X'.
1068template <typename RHS>
1069inline BinaryOp_match<cstfp_pred_ty<is_any_zero_fp>, RHS, Instruction::FSub>
1070m_FNegNSZ(const RHS &X) {
1071  return m_FSub(m_AnyZeroFP(), X);
1072}
1073 
1074template <typename LHS, typename RHS>
1075inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L,
1076                                                        const RHS &R) {
1077  return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
1078}
1079 
1080template <typename LHS, typename RHS>
1081inline BinaryOp_match<LHS, RHS, Instruction::FMul> m_FMul(const LHS &L,
1082                                                          const RHS &R) {
1083  return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R);
1084}
1085 
1086template <typename LHS, typename RHS>
1087inline BinaryOp_match<LHS, RHS, Instruction::UDiv> m_UDiv(const LHS &L,
1088                                                          const RHS &R) {
1089  return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R);
1090}
1091 
1092template <typename LHS, typename RHS>
1093inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L,
1094                                                          const RHS &R) {
1095  return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R);
1096}
1097 
1098template <typename LHS, typename RHS>
1099inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L,
1100                                                          const RHS &R) {
1101  return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R);
1102}
1103 
1104template <typename LHS, typename RHS>
1105inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L,
1106                                                          const RHS &R) {
1107  return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R);
1108}
1109 
1110template <typename LHS, typename RHS>
1111inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L,
1112                                                          const RHS &R) {
1113  return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R);
1114}
1115 
1116template <typename LHS, typename RHS>
1117inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L,
1118                                                          const RHS &R) {
1119  return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R);
1120}
1121 
1122template <typename LHS, typename RHS>
1123inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
1124                                                        const RHS &R) {
1125  return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
1126}
1127 
1128template <typename LHS, typename RHS>
1129inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L,
1130                                                      const RHS &R) {
1131  return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
1132}
1133 
1134template <typename LHS, typename RHS>
1135inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
1136                                                        const RHS &R) {
1137  return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
1138}
1139 
1140template <typename LHS, typename RHS>
1141inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L,
1142                                                        const RHS &R) {
1143  return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
1144}
1145 
1146template <typename LHS, typename RHS>
1147inline BinaryOp_match<LHS, RHS, Instruction::LShr> m_LShr(const LHS &L,
1148                                                          const RHS &R) {
1149  return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
1150}
1151 
1152template <typename LHS, typename RHS>
1153inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L,
1154                                                          const RHS &R) {
1155  return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R);
1156}
1157 
1158template <typename LHS_t, typename RHS_t, unsigned Opcode,
1159          unsigned WrapFlags = 0>
1160struct OverflowingBinaryOp_match {
1161  LHS_t L;
1162  RHS_t R;
1163 
1164  OverflowingBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS)
1165      : L(LHS), R(RHS) {}
1166 
1167  template <typename OpTy> bool match(OpTy *V) {
1168    if (auto *Op = dyn_cast<OverflowingBinaryOperator>(V)) {
1169      if (Op->getOpcode() != Opcode)
1170        return false;
1171      if ((WrapFlags & OverflowingBinaryOperator::NoUnsignedWrap) &&
1172          !Op->hasNoUnsignedWrap())
1173        return false;
1174      if ((WrapFlags & OverflowingBinaryOperator::NoSignedWrap) &&
1175          !Op->hasNoSignedWrap())
1176        return false;
1177      return L.match(Op->getOperand(0)) && R.match(Op->getOperand(1));
1178    }
1179    return false;
1180  }
1181};
1182 
1183template <typename LHS, typename RHS>
1184inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
1185                                 OverflowingBinaryOperator::NoSignedWrap>
1186m_NSWAdd(const LHS &L, const RHS &R) {
1187  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
1188                                   OverflowingBinaryOperator::NoSignedWrap>(
1189      L, R);
1190}
1191template <typename LHS, typename RHS>
1192inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1193                                 OverflowingBinaryOperator::NoSignedWrap>
1194m_NSWSub(const LHS &L, const RHS &R) {
1195  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1196                                   OverflowingBinaryOperator::NoSignedWrap>(
1197      L, R);
1198}
1199template <typename LHS, typename RHS>
1200inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1201                                 OverflowingBinaryOperator::NoSignedWrap>
1202m_NSWMul(const LHS &L, const RHS &R) {
1203  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1204                                   OverflowingBinaryOperator::NoSignedWrap>(
1205      L, R);
1206}
1207template <typename LHS, typename RHS>
1208inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1209                                 OverflowingBinaryOperator::NoSignedWrap>
1210m_NSWShl(const LHS &L, const RHS &R) {
1211  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1212                                   OverflowingBinaryOperator::NoSignedWrap>(
1213      L, R);
1214}
1215 
1216template <typename LHS, typename RHS>
1217inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
1218                                 OverflowingBinaryOperator::NoUnsignedWrap>
1219m_NUWAdd(const LHS &L, const RHS &R) {
1220  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
1221                                   OverflowingBinaryOperator::NoUnsignedWrap>(
1222      L, R);
1223}
1224template <typename LHS, typename RHS>
1225inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1226                                 OverflowingBinaryOperator::NoUnsignedWrap>
1227m_NUWSub(const LHS &L, const RHS &R) {
1228  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1229                                   OverflowingBinaryOperator::NoUnsignedWrap>(
1230      L, R);
1231}
1232template <typename LHS, typename RHS>
1233inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1234                                 OverflowingBinaryOperator::NoUnsignedWrap>
1235m_NUWMul(const LHS &L, const RHS &R) {
1236  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1237                                   OverflowingBinaryOperator::NoUnsignedWrap>(
1238      L, R);
1239}
1240template <typename LHS, typename RHS>
1241inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1242                                 OverflowingBinaryOperator::NoUnsignedWrap>
1243m_NUWShl(const LHS &L, const RHS &R) {
1244  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1245                                   OverflowingBinaryOperator::NoUnsignedWrap>(
1246      L, R);
1247}
1248 
1249//===----------------------------------------------------------------------===//
1250// Class that matches a group of binary opcodes.
1251//
1252template <typename LHS_t, typename RHS_t, typename Predicate>
1253struct BinOpPred_match : Predicate {
1254  LHS_t L;
1255  RHS_t R;
1256 
1257  BinOpPred_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
1258 
1259  template <typename OpTy> bool match(OpTy *V) {
1260    if (auto *I = dyn_cast<Instruction>(V))
1261      return this->isOpType(I->getOpcode()) && L.match(I->getOperand(0)) &&
1262             R.match(I->getOperand(1));
1263    if (auto *CE = dyn_cast<ConstantExpr>(V))
1264      return this->isOpType(CE->getOpcode()) && L.match(CE->getOperand(0)) &&
1265             R.match(CE->getOperand(1));
1266    return false;
1267  }
1268};
1269 
1270struct is_shift_op {
1271  bool isOpType(unsigned Opcode) { return Instruction::isShift(Opcode); }
1272};
1273 
1274struct is_right_shift_op {
1275  bool isOpType(unsigned Opcode) {
1276    return Opcode == Instruction::LShr || Opcode == Instruction::AShr;
1277  }
1278};
1279 
1280struct is_logical_shift_op {
1281  bool isOpType(unsigned Opcode) {
1282    return Opcode == Instruction::LShr || Opcode == Instruction::Shl;
1283  }
1284};
1285 
1286struct is_bitwiselogic_op {
1287  bool isOpType(unsigned Opcode) {
1288    return Instruction::isBitwiseLogicOp(Opcode);
1289  }
1290};
1291 
1292struct is_idiv_op {
1293  bool isOpType(unsigned Opcode) {
1294    return Opcode == Instruction::SDiv || Opcode == Instruction::UDiv;
1295  }
1296};
1297 
1298struct is_irem_op {
1299  bool isOpType(unsigned Opcode) {
1300    return Opcode == Instruction::SRem || Opcode == Instruction::URem;
1301  }
1302};
1303 
1304/// Matches shift operations.
1305template <typename LHS, typename RHS>
1306inline BinOpPred_match<LHS, RHS, is_shift_op> m_Shift(const LHS &L,
1307                                                      const RHS &R) {
1308  return BinOpPred_match<LHS, RHS, is_shift_op>(L, R);
1309}
1310 
1311/// Matches logical shift operations.
1312template <typename LHS, typename RHS>
1313inline BinOpPred_match<LHS, RHS, is_right_shift_op> m_Shr(const LHS &L,
1314                                                          const RHS &R) {
1315  return BinOpPred_match<LHS, RHS, is_right_shift_op>(L, R);
1316}
1317 
1318/// Matches logical shift operations.
1319template <typename LHS, typename RHS>
1320inline BinOpPred_match<LHS, RHS, is_logical_shift_op>
1321m_LogicalShift(const LHS &L, const RHS &R) {
1322  return BinOpPred_match<LHS, RHS, is_logical_shift_op>(L, R);
1323}
1324 
1325/// Matches bitwise logic operations.
1326template <typename LHS, typename RHS>
1327inline BinOpPred_match<LHS, RHS, is_bitwiselogic_op>
1328m_BitwiseLogic(const LHS &L, const RHS &R) {
1329  return BinOpPred_match<LHS, RHS, is_bitwiselogic_op>(L, R);
1330}
1331 
1332/// Matches integer division operations.
1333template <typename LHS, typename RHS>
1334inline BinOpPred_match<LHS, RHS, is_idiv_op> m_IDiv(const LHS &L,
1335                                                    const RHS &R) {
1336  return BinOpPred_match<LHS, RHS, is_idiv_op>(L, R);
1337}
1338 
1339/// Matches integer remainder operations.
1340template <typename LHS, typename RHS>
1341inline BinOpPred_match<LHS, RHS, is_irem_op> m_IRem(const LHS &L,
1342                                                    const RHS &R) {
1343  return BinOpPred_match<LHS, RHS, is_irem_op>(L, R);
1344}
1345 
1346//===----------------------------------------------------------------------===//
1347// Class that matches exact binary ops.
1348//
1349template <typename SubPattern_t> struct Exact_match {
1350  SubPattern_t SubPattern;
1351 
1352  Exact_match(const SubPattern_t &SP) : SubPattern(SP) {}
1353 
1354  template <typename OpTy> bool match(OpTy *V) {
1355    if (auto *PEO = dyn_cast<PossiblyExactOperator>(V))
1356      return PEO->isExact() && SubPattern.match(V);
1357    return false;
1358  }
1359};
1360 
1361template <typename T> inline Exact_match<T> m_Exact(const T &SubPattern) {
1362  return SubPattern;
1363}
1364 
1365//===----------------------------------------------------------------------===//
1366// Matchers for CmpInst classes
1367//
1368 
1369template <typename LHS_t, typename RHS_t, typename Class, typename PredicateTy,
1370          bool Commutable = false>
1371struct CmpClass_match {
1372  PredicateTy &Predicate;
1373  LHS_t L;
1374  RHS_t R;
1375 
1376  // The evaluation order is always stable, regardless of Commutability.
1377  // The LHS is always matched first.
1378  CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS)
1379      : Predicate(Pred), L(LHS), R(RHS) {}
1380 
1381  template <typename OpTy> bool match(OpTy *V) {
1382    if (auto *I = dyn_cast<Class>(V)) {
1383      if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
1384        Predicate = I->getPredicate();
1385        return true;
1386      } else if (Commutable && L.match(I->getOperand(1)) &&
1387           R.match(I->getOperand(0))) {
1388        Predicate = I->getSwappedPredicate();
1389        return true;
1390      }
1391    }
1392    return false;
1393  }
1394};
1395 
1396template <typename LHS, typename RHS>
1397inline CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>
1398m_Cmp(CmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1399  return CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>(Pred, L, R);
1400}
1401 
1402template <typename LHS, typename RHS>
1403inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>
1404m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1405  return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>(Pred, L, R);
1406}
1407 
1408template <typename LHS, typename RHS>
1409inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>
1410m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1411  return CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>(Pred, L, R);
1412}
1413 
1414//===----------------------------------------------------------------------===//
1415// Matchers for instructions with a given opcode and number of operands.
1416//
1417 
1418/// Matches instructions with Opcode and three operands.
1419template <typename T0, unsigned Opcode> struct OneOps_match {
1420  T0 Op1;
1421 
1422  OneOps_match(const T0 &Op1) : Op1(Op1) {}
1423 
1424  template <typename OpTy> bool match(OpTy *V) {
1425    if (V->getValueID() == Value::InstructionVal + Opcode) {
1426      auto *I = cast<Instruction>(V);
1427      return Op1.match(I->getOperand(0));
1428    }
1429    return false;
1430  }
1431};
1432 
1433/// Matches instructions with Opcode and three operands.
1434template <typename T0, typename T1, unsigned Opcode> struct TwoOps_match {
1435  T0 Op1;
1436  T1 Op2;
1437 
1438  TwoOps_match(const T0 &Op1, const T1 &Op2) : Op1(Op1), Op2(Op2) {}
1439 
1440  template <typename OpTy> bool match(OpTy *V) {
1441    if (V->getValueID() == Value::InstructionVal + Opcode) {
1442      auto *I = cast<Instruction>(V);
1443      return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1));
1444    }
1445    return false;
1446  }
1447};
1448 
1449/// Matches instructions with Opcode and three operands.
1450template <typename T0, typename T1, typename T2, unsigned Opcode>
1451struct ThreeOps_match {
1452  T0 Op1;
1453  T1 Op2;
1454  T2 Op3;
1455 
1456  ThreeOps_match(const T0 &Op1, const T1 &Op2, const T2 &Op3)
1457      : Op1(Op1), Op2(Op2), Op3(Op3) {}
1458 
1459  template <typename OpTy> bool match(OpTy *V) {
1460    if (V->getValueID() == Value::InstructionVal + Opcode) {
1461      auto *I = cast<Instruction>(V);
1462      return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) &&
1463             Op3.match(I->getOperand(2));
1464    }
1465    return false;
1466  }
1467};
1468 
1469/// Matches SelectInst.
1470template <typename Cond, typename LHS, typename RHS>
1471inline ThreeOps_match<Cond, LHS, RHS, Instruction::Select>
1472m_Select(const Cond &C, const LHS &L, const RHS &R) {
1473  return ThreeOps_match<Cond, LHS, RHS, Instruction::Select>(C, L, R);
1474}
1475 
1476/// This matches a select of two constants, e.g.:
1477/// m_SelectCst<-1, 0>(m_Value(V))
1478template <int64_t L, int64_t R, typename Cond>
1479inline ThreeOps_match<Cond, constantint_match<L>, constantint_match<R>,
1480                      Instruction::Select>
1481m_SelectCst(const Cond &C) {
1482  return m_Select(C, m_ConstantInt<L>(), m_ConstantInt<R>());
1483}
1484 
1485/// Matches FreezeInst.
1486template <typename OpTy>
1487inline OneOps_match<OpTy, Instruction::Freeze> m_Freeze(const OpTy &Op) {
1488  return OneOps_match<OpTy, Instruction::Freeze>(Op);
1489}
1490 
1491/// Matches InsertElementInst.
1492template <typename Val_t, typename Elt_t, typename Idx_t>
1493inline ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement>
1494m_InsertElt(const Val_t &Val, const Elt_t &Elt, const Idx_t &Idx) {
1495  return ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement>(
1496      Val, Elt, Idx);
1497}
1498 
1499/// Matches ExtractElementInst.
1500template <typename Val_t, typename Idx_t>
1501inline TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement>
1502m_ExtractElt(const Val_t &Val, const Idx_t &Idx) {
1503  return TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement>(Val, Idx);
1504}
1505 
1506/// Matches shuffle.
1507template <typename T0, typename T1, typename T2> struct Shuffle_match {
1508  T0 Op1;
1509  T1 Op2;
1510  T2 Mask;
1511 
1512  Shuffle_match(const T0 &Op1, const T1 &Op2, const T2 &Mask)
1513      : Op1(Op1), Op2(Op2), Mask(Mask) {}
1514 
1515  template <typename OpTy> bool match(OpTy *V) {
1516    if (auto *I = dyn_cast<ShuffleVectorInst>(V)) {
1517      return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) &&
1518             Mask.match(I->getShuffleMask());
1519    }
1520    return false;
1521  }
1522};
1523 
1524struct m_Mask {
1525  ArrayRef<int> &MaskRef;
1526  m_Mask(ArrayRef<int> &MaskRef) : MaskRef(MaskRef) {}
1527  bool match(ArrayRef<int> Mask) {
1528    MaskRef = Mask;
1529    return true;
1530  }
1531};
1532 
1533struct m_ZeroMask {
1534  bool match(ArrayRef<int> Mask) {
1535    return all_of(Mask, [](int Elem) { return Elem == 0 || Elem == -1; });
1536  }
1537};
1538 
1539struct m_SpecificMask {
1540  ArrayRef<int> &MaskRef;
1541  m_SpecificMask(ArrayRef<int> &MaskRef) : MaskRef(MaskRef) {}
1542  bool match(ArrayRef<int> Mask) { return MaskRef == Mask; }
1543};
1544 
1545struct m_SplatOrUndefMask {
1546  int &SplatIndex;
1547  m_SplatOrUndefMask(int &SplatIndex) : SplatIndex(SplatIndex) {}
1548  bool match(ArrayRef<int> Mask) {
1549    auto First = find_if(Mask, [](int Elem) { return Elem != -1; });
1550    if (First == Mask.end())
1551      return false;
1552    SplatIndex = *First;
1553    return all_of(Mask,
1554                  [First](int Elem) { return Elem == *First || Elem == -1; });
1555  }
1556};
1557 
1558/// Matches ShuffleVectorInst independently of mask value.
1559template <typename V1_t, typename V2_t>
1560inline TwoOps_match<V1_t, V2_t, Instruction::ShuffleVector>
1561m_Shuffle(const V1_t &v1, const V2_t &v2) {
1562  return TwoOps_match<V1_t, V2_t, Instruction::ShuffleVector>(v1, v2);
1563}
1564 
1565template <typename V1_t, typename V2_t, typename Mask_t>
1566inline Shuffle_match<V1_t, V2_t, Mask_t>
1567m_Shuffle(const V1_t &v1, const V2_t &v2, const Mask_t &mask) {
1568  return Shuffle_match<V1_t, V2_t, Mask_t>(v1, v2, mask);
1569}
1570 
1571/// Matches LoadInst.
1572template <typename OpTy>
1573inline OneOps_match<OpTy, Instruction::Load> m_Load(const OpTy &Op) {
1574  return OneOps_match<OpTy, Instruction::Load>(Op);
1575}
1576 
1577/// Matches StoreInst.
1578template <typename ValueOpTy, typename PointerOpTy>
1579inline TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store>
1580m_Store(const ValueOpTy &ValueOp, const PointerOpTy &PointerOp) {
1581  return TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store>(ValueOp,
1582                                                                  PointerOp);
1583}
1584 
1585//===----------------------------------------------------------------------===//
1586// Matchers for CastInst classes
1587//
1588 
1589template <typename Op_t, unsigned Opcode> struct CastClass_match {
1590  Op_t Op;
1591 
1592  CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
1593 
1594  template <typename OpTy> bool match(OpTy *V) {
1595    if (auto *O = dyn_cast<Operator>(V))
1596      return O->getOpcode() == Opcode && Op.match(O->getOperand(0));
1597    return false;
1598  }
1599};
1600 
1601/// Matches BitCast.
1602template <typename OpTy>
1603inline CastClass_match<OpTy, Instruction::BitCast> m_BitCast(const OpTy &Op) {
1604  return CastClass_match<OpTy, Instruction::BitCast>(Op);
1605}
1606 
1607/// Matches PtrToInt.
1608template <typename OpTy>
1609inline CastClass_match<OpTy, Instruction::PtrToInt> m_PtrToInt(const OpTy &Op) {
1610  return CastClass_match<OpTy, Instruction::PtrToInt>(Op);
1611}
1612 
1613/// Matches IntToPtr.
1614template <typename OpTy>
1615inline CastClass_match<OpTy, Instruction::IntToPtr> m_IntToPtr(const OpTy &Op) {
1616  return CastClass_match<OpTy, Instruction::IntToPtr>(Op);
1617}
1618 
1619/// Matches Trunc.
1620template <typename OpTy>
1621inline CastClass_match<OpTy, Instruction::Trunc> m_Trunc(const OpTy &Op) {
1622  return CastClass_match<OpTy, Instruction::Trunc>(Op);
1623}
1624 
1625template <typename OpTy>
1626inline match_combine_or<CastClass_match<OpTy, Instruction::Trunc>, OpTy>
1627m_TruncOrSelf(const OpTy &Op) {
1628  return m_CombineOr(m_Trunc(Op), Op);
1629}
1630 
1631/// Matches SExt.
1632template <typename OpTy>
1633inline CastClass_match<OpTy, Instruction::SExt> m_SExt(const OpTy &Op) {
1634  return CastClass_match<OpTy, Instruction::SExt>(Op);
1635}
1636 
1637/// Matches ZExt.
1638template <typename OpTy>
1639inline CastClass_match<OpTy, Instruction::ZExt> m_ZExt(const OpTy &Op) {
1640  return CastClass_match<OpTy, Instruction::ZExt>(Op);
1641}
1642 
1643template <typename OpTy>
1644inline match_combine_or<CastClass_match<OpTy, Instruction::ZExt>, OpTy>
1645m_ZExtOrSelf(const OpTy &Op) {
1646  return m_CombineOr(m_ZExt(Op), Op);
1647}
1648 
1649template <typename OpTy>
1650inline match_combine_or<CastClass_match<OpTy, Instruction::SExt>, OpTy>
1651m_SExtOrSelf(const OpTy &Op) {
1652  return m_CombineOr(m_SExt(Op), Op);
1653}
1654 
1655template <typename OpTy>
1656inline match_combine_or<CastClass_match<OpTy, Instruction::ZExt>,
1657                        CastClass_match<OpTy, Instruction::SExt>>
1658m_ZExtOrSExt(const OpTy &Op) {
1659  return m_CombineOr(m_ZExt(Op), m_SExt(Op));
1660}
1661 
1662template <typename OpTy>
1663inline match_combine_or<
1664    match_combine_or<CastClass_match<OpTy, Instruction::ZExt>,
1665                     CastClass_match<OpTy, Instruction::SExt>>,
1666    OpTy>
1667m_ZExtOrSExtOrSelf(const OpTy &Op) {
1668  return m_CombineOr(m_ZExtOrSExt(Op), Op);
1669}
1670 
1671template <typename OpTy>
1672inline CastClass_match<OpTy, Instruction::UIToFP> m_UIToFP(const OpTy &Op) {
1673  return CastClass_match<OpTy, Instruction::UIToFP>(Op);
1674}
1675 
1676template <typename OpTy>
1677inline CastClass_match<OpTy, Instruction::SIToFP> m_SIToFP(const OpTy &Op) {
1678  return CastClass_match<OpTy, Instruction::SIToFP>(Op);
1679}
1680 
1681template <typename OpTy>
1682inline CastClass_match<OpTy, Instruction::FPToUI> m_FPToUI(const OpTy &Op) {
1683  return CastClass_match<OpTy, Instruction::FPToUI>(Op);
1684}
1685 
1686template <typename OpTy>
1687inline CastClass_match<OpTy, Instruction::FPToSI> m_FPToSI(const OpTy &Op) {
1688  return CastClass_match<OpTy, Instruction::FPToSI>(Op);
1689}
1690 
1691template <typename OpTy>
1692inline CastClass_match<OpTy, Instruction::FPTrunc> m_FPTrunc(const OpTy &Op) {
1693  return CastClass_match<OpTy, Instruction::FPTrunc>(Op);
1694}
1695 
1696template <typename OpTy>
1697inline CastClass_match<OpTy, Instruction::FPExt> m_FPExt(const OpTy &Op) {
1698  return CastClass_match<OpTy, Instruction::FPExt>(Op);
1699}
1700 
1701//===----------------------------------------------------------------------===//
1702// Matchers for control flow.
1703//
1704 
1705struct br_match {
1706  BasicBlock *&Succ;
1707 
1708  br_match(BasicBlock *&Succ) : Succ(Succ) {}
1709 
1710  template <typename OpTy> bool match(OpTy *V) {
1711    if (auto *BI = dyn_cast<BranchInst>(V))
1712      if (BI->isUnconditional()) {
1713        Succ = BI->getSuccessor(0);
1714        return true;
1715      }
1716    return false;
1717  }
1718};
1719 
1720inline br_match m_UnconditionalBr(BasicBlock *&Succ) { return br_match(Succ); }
1721 
1722template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t>
1723struct brc_match {
1724  Cond_t Cond;
1725  TrueBlock_t T;
1726  FalseBlock_t F;
1727 
1728  brc_match(const Cond_t &C, const TrueBlock_t &t, const FalseBlock_t &f)
1729      : Cond(C), T(t), F(f) {}
1730 
1731  template <typename OpTy> bool match(OpTy *V) {
1732    if (auto *BI = dyn_cast<BranchInst>(V))
1733      if (BI->isConditional() && Cond.match(BI->getCondition()))
1734        return T.match(BI->getSuccessor(0)) && F.match(BI->getSuccessor(1));
1735    return false;
1736  }
1737};
1738 
1739template <typename Cond_t>
1740inline brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>>
1741m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
1742  return brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>>(
1743      C, m_BasicBlock(T), m_BasicBlock(F));
1744}
1745 
1746template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t>
1747inline brc_match<Cond_t, TrueBlock_t, FalseBlock_t>
1748m_Br(const Cond_t &C, const TrueBlock_t &T, const FalseBlock_t &F) {
1749  return brc_match<Cond_t, TrueBlock_t, FalseBlock_t>(C, T, F);
1750}
1751 
1752//===----------------------------------------------------------------------===//
1753// Matchers for max/min idioms, eg: "select (sgt x, y), x, y" -> smax(x,y).
1754//
1755 
1756template <typename CmpInst_t, typename LHS_t, typename RHS_t, typename Pred_t,
1757          bool Commutable = false>
1758struct MaxMin_match {
1759  using PredType = Pred_t;
1760  LHS_t L;
1761  RHS_t R;
1762 
1763  // The evaluation order is always stable, regardless of Commutability.
1764  // The LHS is always matched first.
1765  MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
1766 
1767  template <typename OpTy> bool match(OpTy *V) {
1768    if (auto *II = dyn_cast<IntrinsicInst>(V)) {
1769      Intrinsic::ID IID = II->getIntrinsicID();
1770      if ((IID == Intrinsic::smax && Pred_t::match(ICmpInst::ICMP_SGT)) ||
1771          (IID == Intrinsic::smin && Pred_t::match(ICmpInst::ICMP_SLT)) ||
1772          (IID == Intrinsic::umax && Pred_t::match(ICmpInst::ICMP_UGT)) ||
1773          (IID == Intrinsic::umin && Pred_t::match(ICmpInst::ICMP_ULT))) {
1774        Value *LHS = II->getOperand(0), *RHS = II->getOperand(1);
1775        return (L.match(LHS) && R.match(RHS)) ||
1776               (Commutable && L.match(RHS) && R.match(LHS));
1777      }
1778    }
1779    // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x".
1780    auto *SI = dyn_cast<SelectInst>(V);
1781    if (!SI)
1782      return false;
1783    auto *Cmp = dyn_cast<CmpInst_t>(SI->getCondition());
1784    if (!Cmp)
1785      return false;
1786    // At this point we have a select conditioned on a comparison.  Check that
1787    // it is the values returned by the select that are being compared.
1788    auto *TrueVal = SI->getTrueValue();
1789    auto *FalseVal = SI->getFalseValue();
1790    auto *LHS = Cmp->getOperand(0);
1791    auto *RHS = Cmp->getOperand(1);
1792    if ((TrueVal != LHS || FalseVal != RHS) &&
1793        (TrueVal != RHS || FalseVal != LHS))
1794      return false;
1795    typename CmpInst_t::Predicate Pred =
1796        LHS == TrueVal ? Cmp->getPredicate() : Cmp->getInversePredicate();
1797    // Does "(x pred y) ? x : y" represent the desired max/min operation?
1798    if (!Pred_t::match(Pred))
1799      return false;
1800    // It does!  Bind the operands.
1801    return (L.match(LHS) && R.match(RHS)) ||
1802           (Commutable && L.match(RHS) && R.match(LHS));
1803  }
1804};
1805 
1806/// Helper class for identifying signed max predicates.
1807struct smax_pred_ty {
1808  static bool match(ICmpInst::Predicate Pred) {
1809    return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE;
1810  }
1811};
1812 
1813/// Helper class for identifying signed min predicates.
1814struct smin_pred_ty {
1815  static bool match(ICmpInst::Predicate Pred) {
1816    return Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE;
1817  }
1818};
1819 
1820/// Helper class for identifying unsigned max predicates.
1821struct umax_pred_ty {
1822  static bool match(ICmpInst::Predicate Pred) {
1823    return Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE;
1824  }
1825};
1826 
1827/// Helper class for identifying unsigned min predicates.
1828struct umin_pred_ty {
1829  static bool match(ICmpInst::Predicate Pred) {
1830    return Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE;
1831  }
1832};
1833 
1834/// Helper class for identifying ordered max predicates.
1835struct ofmax_pred_ty {
1836  static bool match(FCmpInst::Predicate Pred) {
1837    return Pred == CmpInst::FCMP_OGT || Pred == CmpInst::FCMP_OGE;
1838  }
1839};
1840 
1841/// Helper class for identifying ordered min predicates.
1842struct ofmin_pred_ty {
1843  static bool match(FCmpInst::Predicate Pred) {
1844    return Pred == CmpInst::FCMP_OLT || Pred == CmpInst::FCMP_OLE;
1845  }
1846};
1847 
1848/// Helper class for identifying unordered max predicates.
1849struct ufmax_pred_ty {
1850  static bool match(FCmpInst::Predicate Pred) {
1851    return Pred == CmpInst::FCMP_UGT || Pred == CmpInst::FCMP_UGE;
1852  }
1853};
1854 
1855/// Helper class for identifying unordered min predicates.
1856struct ufmin_pred_ty {
1857  static bool match(FCmpInst::Predicate Pred) {
1858    return Pred == CmpInst::FCMP_ULT || Pred == CmpInst::FCMP_ULE;
1859  }
1860};
1861 
1862template <typename LHS, typename RHS>
1863inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty> m_SMax(const LHS &L,
1864                                                             const RHS &R) {
1865  return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty>(L, R);
1866}
1867 
1868template <typename LHS, typename RHS>
1869inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty> m_SMin(const LHS &L,
1870                                                             const RHS &R) {
1871  return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty>(L, R);
1872}
1873 
1874template <typename LHS, typename RHS>
1875inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty> m_UMax(const LHS &L,
1876                                                             const RHS &R) {
1877  return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty>(L, R);
1878}
1879 
1880template <typename LHS, typename RHS>
1881inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty> m_UMin(const LHS &L,
1882                                                             const RHS &R) {
1883  return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty>(L, R);
1884}
1885 
1886template <typename LHS, typename RHS>
1887inline match_combine_or<
1888    match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty>,
1889                     MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty>>,
1890    match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty>,
1891                     MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty>>>
1892m_MaxOrMin(const LHS &L, const RHS &R) {
1893  return m_CombineOr(m_CombineOr(m_SMax(L, R), m_SMin(L, R)),
1894                     m_CombineOr(m_UMax(L, R), m_UMin(L, R)));
1895}
1896 
1897/// Match an 'ordered' floating point maximum function.
1898/// Floating point has one special value 'NaN'. Therefore, there is no total
1899/// order. However, if we can ignore the 'NaN' value (for example, because of a
1900/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
1901/// semantics. In the presence of 'NaN' we have to preserve the original
1902/// select(fcmp(ogt/ge, L, R), L, R) semantics matched by this predicate.
1903///
1904///                         max(L, R)  iff L and R are not NaN
1905///  m_OrdFMax(L, R) =      R          iff L or R are NaN
1906template <typename LHS, typename RHS>
1907inline MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty> m_OrdFMax(const LHS &L,
1908                                                                 const RHS &R) {
1909  return MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty>(L, R);
1910}
1911 
1912/// Match an 'ordered' floating point minimum function.
1913/// Floating point has one special value 'NaN'. Therefore, there is no total
1914/// order. However, if we can ignore the 'NaN' value (for example, because of a
1915/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
1916/// semantics. In the presence of 'NaN' we have to preserve the original
1917/// select(fcmp(olt/le, L, R), L, R) semantics matched by this predicate.
1918///
1919///                         min(L, R)  iff L and R are not NaN
1920///  m_OrdFMin(L, R) =      R          iff L or R are NaN
1921template <typename LHS, typename RHS>
1922inline MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty> m_OrdFMin(const LHS &L,
1923                                                                 const RHS &R) {
1924  return MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty>(L, R);
1925}
1926 
1927/// Match an 'unordered' floating point maximum function.
1928/// Floating point has one special value 'NaN'. Therefore, there is no total
1929/// order. However, if we can ignore the 'NaN' value (for example, because of a
1930/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
1931/// semantics. In the presence of 'NaN' we have to preserve the original
1932/// select(fcmp(ugt/ge, L, R), L, R) semantics matched by this predicate.
1933///
1934///                         max(L, R)  iff L and R are not NaN
1935///  m_UnordFMax(L, R) =    L          iff L or R are NaN
1936template <typename LHS, typename RHS>
1937inline MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>
1938m_UnordFMax(const LHS &L, const RHS &R) {
1939  return MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>(L, R);
1940}
1941 
1942/// Match an 'unordered' floating point minimum function.
1943/// Floating point has one special value 'NaN'. Therefore, there is no total
1944/// order. However, if we can ignore the 'NaN' value (for example, because of a
1945/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
1946/// semantics. In the presence of 'NaN' we have to preserve the original
1947/// select(fcmp(ult/le, L, R), L, R) semantics matched by this predicate.
1948///
1949///                          min(L, R)  iff L and R are not NaN
1950///  m_UnordFMin(L, R) =     L          iff L or R are NaN
1951template <typename LHS, typename RHS>
1952inline MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>
1953m_UnordFMin(const LHS &L, const RHS &R) {
1954  return MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>(L, R);
1955}
1956 
1957//===----------------------------------------------------------------------===//
1958// Matchers for overflow check patterns: e.g. (a + b) u< a, (a ^ -1) <u b
1959// Note that S might be matched to other instructions than AddInst.
1960//
1961 
1962template <typename LHS_t, typename RHS_t, typename Sum_t>
1963struct UAddWithOverflow_match {
1964  LHS_t L;
1965  RHS_t R;
1966  Sum_t S;
1967 
1968  UAddWithOverflow_match(const LHS_t &L, const RHS_t &R, const Sum_t &S)
1969      : L(L), R(R), S(S) {}
1970 
1971  template <typename OpTy> bool match(OpTy *V) {
1972    Value *ICmpLHS, *ICmpRHS;
1973    ICmpInst::Predicate Pred;
1974    if (!m_ICmp(Pred, m_Value(ICmpLHS), m_Value(ICmpRHS)).match(V))
1975      return false;
1976 
1977    Value *AddLHS, *AddRHS;
1978    auto AddExpr = m_Add(m_Value(AddLHS), m_Value(AddRHS));
1979 
1980    // (a + b) u< a, (a + b) u< b
1981    if (Pred == ICmpInst::ICMP_ULT)
1982      if (AddExpr.match(ICmpLHS) && (ICmpRHS == AddLHS || ICmpRHS == AddRHS))
1983        return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
1984 
1985    // a >u (a + b), b >u (a + b)
1986    if (Pred == ICmpInst::ICMP_UGT)
1987      if (AddExpr.match(ICmpRHS) && (ICmpLHS == AddLHS || ICmpLHS == AddRHS))
1988        return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
1989 
1990    Value *Op1;
1991    auto XorExpr = m_OneUse(m_Xor(m_Value(Op1), m_AllOnes()));
1992    // (a ^ -1) <u b
1993    if (Pred == ICmpInst::ICMP_ULT) {
1994      if (XorExpr.match(ICmpLHS))
1995        return L.match(Op1) && R.match(ICmpRHS) && S.match(ICmpLHS);
1996    }
1997    //  b > u (a ^ -1)
1998    if (Pred == ICmpInst::ICMP_UGT) {
1999      if (XorExpr.match(ICmpRHS))
2000        return L.match(Op1) && R.match(ICmpLHS) && S.match(ICmpRHS);
2001    }
2002 
2003    // Match special-case for increment-by-1.
2004    if (Pred == ICmpInst::ICMP_EQ) {
2005      // (a + 1) == 0
2006      // (1 + a) == 0
2007      if (AddExpr.match(ICmpLHS) && m_ZeroInt().match(ICmpRHS) &&
2008          (m_One().match(AddLHS) || m_One().match(AddRHS)))
2009        return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
2010      // 0 == (a + 1)
2011      // 0 == (1 + a)
2012      if (m_ZeroInt().match(ICmpLHS) && AddExpr.match(ICmpRHS) &&
2013          (m_One().match(AddLHS) || m_One().match(AddRHS)))
2014        return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
2015    }
2016 
2017    return false;
2018  }
2019};
2020 
2021/// Match an icmp instruction checking for unsigned overflow on addition.
2022///
2023/// S is matched to the addition whose result is being checked for overflow, and
2024/// L and R are matched to the LHS and RHS of S.
2025template <typename LHS_t, typename RHS_t, typename Sum_t>
2026UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>
2027m_UAddWithOverflow(const LHS_t &L, const RHS_t &R, const Sum_t &S) {
2028  return UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>(L, R, S);
2029}
2030 
2031template <typename Opnd_t> struct Argument_match {
2032  unsigned OpI;
2033  Opnd_t Val;
2034 
2035  Argument_match(unsigned OpIdx, const Opnd_t &V) : OpI(OpIdx), Val(V) {}
2036 
2037  template <typename OpTy> bool match(OpTy *V) {
2038    // FIXME: Should likely be switched to use `CallBase`.
2039    if (const auto *CI = dyn_cast<CallInst>(V))
2040      return Val.match(CI->getArgOperand(OpI));
2041    return false;
2042  }
2043};
2044 
2045/// Match an argument.
2046template <unsigned OpI, typename Opnd_t>
2047inline Argument_match<Opnd_t> m_Argument(const Opnd_t &Op) {
2048  return Argument_match<Opnd_t>(OpI, Op);
2049}
2050 
2051/// Intrinsic matchers.
2052struct IntrinsicID_match {
2053  unsigned ID;
2054 
2055  IntrinsicID_match(Intrinsic::ID IntrID) : ID(IntrID) {}
2056 
2057  template <typename OpTy> bool match(OpTy *V) {
2058    if (const auto *CI = dyn_cast<CallInst>(V))
2059      if (const auto *F = CI->getCalledFunction())
2060        return F->getIntrinsicID() == ID;
2061    return false;
2062  }
2063};
2064 
2065/// Intrinsic matches are combinations of ID matchers, and argument
2066/// matchers. Higher arity matcher are defined recursively in terms of and-ing
2067/// them with lower arity matchers. Here's some convenient typedefs for up to
2068/// several arguments, and more can be added as needed
2069template <typename T0 = void, typename T1 = void, typename T2 = void,
2070          typename T3 = void, typename T4 = void, typename T5 = void,
2071          typename T6 = void, typename T7 = void, typename T8 = void,
2072          typename T9 = void, typename T10 = void>
2073struct m_Intrinsic_Ty;
2074template <typename T0> struct m_Intrinsic_Ty<T0> {
2075  using Ty = match_combine_and<IntrinsicID_match, Argument_match<T0>>;
2076};
2077template <typename T0, typename T1> struct m_Intrinsic_Ty<T0, T1> {
2078  using Ty =
2079      match_combine_and<typename m_Intrinsic_Ty<T0>::Ty, Argument_match<T1>>;
2080};
2081template <typename T0, typename T1, typename T2>
2082struct m_Intrinsic_Ty<T0, T1, T2> {
2083  using Ty =
2084      match_combine_and<typename m_Intrinsic_Ty<T0, T1>::Ty,
2085                        Argument_match<T2>>;
2086};
2087template <typename T0, typename T1, typename T2, typename T3>
2088struct m_Intrinsic_Ty<T0, T1, T2, T3> {
2089  using Ty =
2090      match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2>::Ty,
2091                        Argument_match<T3>>;
2092};
2093 
2094template <typename T0, typename T1, typename T2, typename T3, typename T4>
2095struct m_Intrinsic_Ty<T0, T1, T2, T3, T4> {
2096  using Ty = match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty,
2097                               Argument_match<T4>>;
2098};
2099 
2100template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5>
2101struct m_Intrinsic_Ty<T0, T1, T2, T3, T4, T5> {
2102  using Ty = match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2, T3, T4>::Ty,
2103                               Argument_match<T5>>;
2104};
2105 
2106/// Match intrinsic calls like this:
2107/// m_Intrinsic<Intrinsic::fabs>(m_Value(X))
2108template <Intrinsic::ID IntrID> inline IntrinsicID_match m_Intrinsic() {
2109  return IntrinsicID_match(IntrID);
2110}
2111 
2112/// Matches MaskedLoad Intrinsic.
2113template <typename Opnd0, typename Opnd1, typename Opnd2, typename Opnd3>
2114inline typename m_Intrinsic_Ty<Opnd0, Opnd1, Opnd2, Opnd3>::Ty
2115m_MaskedLoad(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2,
2116             const Opnd3 &Op3) {
2117  return m_Intrinsic<Intrinsic::masked_load>(Op0, Op1, Op2, Op3);
2118}
2119 
2120template <Intrinsic::ID IntrID, typename T0>
2121inline typename m_Intrinsic_Ty<T0>::Ty m_Intrinsic(const T0 &Op0) {
2122  return m_CombineAnd(m_Intrinsic<IntrID>(), m_Argument<0>(Op0));
2123}
2124 
2125template <Intrinsic::ID IntrID, typename T0, typename T1>
2126inline typename m_Intrinsic_Ty<T0, T1>::Ty m_Intrinsic(const T0 &Op0,
2127                                                       const T1 &Op1) {
2128  return m_CombineAnd(m_Intrinsic<IntrID>(Op0), m_Argument<1>(Op1));
2129}
2130 
2131template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2>
2132inline typename m_Intrinsic_Ty<T0, T1, T2>::Ty
2133m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2) {
2134  return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1), m_Argument<2>(Op2));
2135}
2136 
2137template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
2138          typename T3>
2139inline typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty
2140m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3) {
2141  return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2), m_Argument<3>(Op3));
2142}
2143 
2144template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
2145          typename T3, typename T4>
2146inline typename m_Intrinsic_Ty<T0, T1, T2, T3, T4>::Ty
2147m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3,
2148            const T4 &Op4) {
2149  return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2, Op3),
2150                      m_Argument<4>(Op4));
2151}
2152 
2153template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
2154          typename T3, typename T4, typename T5>
2155inline typename m_Intrinsic_Ty<T0, T1, T2, T3, T4, T5>::Ty
2156m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3,
2157            const T4 &Op4, const T5 &Op5) {
2158  return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2, Op3, Op4),
2159                      m_Argument<5>(Op5));
2160}
2161 
2162// Helper intrinsic matching specializations.
2163template <typename Opnd0>
2164inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BitReverse(const Opnd0 &Op0) {
2165  return m_Intrinsic<Intrinsic::bitreverse>(Op0);
2166}
2167 
2168template <typename Opnd0>
2169inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BSwap(const Opnd0 &Op0) {
2170  return m_Intrinsic<Intrinsic::bswap>(Op0);
2171}
2172 
2173template <typename Opnd0>
2174inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FAbs(const Opnd0 &Op0) {
2175  return m_Intrinsic<Intrinsic::fabs>(Op0);
2176}
2177 
2178template <typename Opnd0>
2179inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FCanonicalize(const Opnd0 &Op0) {
2180  return m_Intrinsic<Intrinsic::canonicalize>(Op0);
2181}
2182 
2183template <typename Opnd0, typename Opnd1>
2184inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMin(const Opnd0 &Op0,
2185                                                        const Opnd1 &Op1) {
2186  return m_Intrinsic<Intrinsic::minnum>(Op0, Op1);
2187}
2188 
2189template <typename Opnd0, typename Opnd1>
2190inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMax(const Opnd0 &Op0,
2191                                                        const Opnd1 &Op1) {
2192  return m_Intrinsic<Intrinsic::maxnum>(Op0, Op1);
2193}
2194 
2195template <typename Opnd0, typename Opnd1, typename Opnd2>
2196inline typename m_Intrinsic_Ty<Opnd0, Opnd1, Opnd2>::Ty
2197m_FShl(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2) {
2198  return m_Intrinsic<Intrinsic::fshl>(Op0, Op1, Op2);
2199}
2200 
2201template <typename Opnd0, typename Opnd1, typename Opnd2>
2202inline typename m_Intrinsic_Ty<Opnd0, Opnd1, Opnd2>::Ty
2203m_FShr(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2) {
2204  return m_Intrinsic<Intrinsic::fshr>(Op0, Op1, Op2);
2205}
2206 
2207//===----------------------------------------------------------------------===//
2208// Matchers for two-operands operators with the operators in either order
2209//
2210 
2211/// Matches a BinaryOperator with LHS and RHS in either order.
2212template <typename LHS, typename RHS>
2213inline AnyBinaryOp_match<LHS, RHS, true> m_c_BinOp(const LHS &L, const RHS &R) {
2214  return AnyBinaryOp_match<LHS, RHS, true>(L, R);
2215}
2216 
2217/// Matches an ICmp with a predicate over LHS and RHS in either order.
2218/// Swaps the predicate if operands are commuted.
2219template <typename LHS, typename RHS>
2220inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>
2221m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
2222  return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>(Pred, L,
2223                                                                       R);
2224}
2225 
2226/// Matches a Add with LHS and RHS in either order.
2227template <typename LHS, typename RHS>
2228inline BinaryOp_match<LHS, RHS, Instruction::Add, true> m_c_Add(const LHS &L,
2229                                                                const RHS &R) {
2230  return BinaryOp_match<LHS, RHS, Instruction::Add, true>(L, R);
2231}
2232 
2233/// Matches a Mul with LHS and RHS in either order.
2234template <typename LHS, typename RHS>
2235inline BinaryOp_match<LHS, RHS, Instruction::Mul, true> m_c_Mul(const LHS &L,
2236                                                                const RHS &R) {
2237  return BinaryOp_match<LHS, RHS, Instruction::Mul, true>(L, R);
2238}
2239 
2240/// Matches an And with LHS and RHS in either order.
2241template <typename LHS, typename RHS>
2242inline BinaryOp_match<LHS, RHS, Instruction::And, true> m_c_And(const LHS &L,
2243                                                                const RHS &R) {
2244  return BinaryOp_match<LHS, RHS, Instruction::And, true>(L, R);
2245}
2246 
2247/// Matches an Or with LHS and RHS in either order.
2248template <typename LHS, typename RHS>
2249inline BinaryOp_match<LHS, RHS, Instruction::Or, true> m_c_Or(const LHS &L,
2250                                                              const RHS &R) {
2251  return BinaryOp_match<LHS, RHS, Instruction::Or, true>(L, R);
2252}
2253 
2254/// Matches an Xor with LHS and RHS in either order.
2255template <typename LHS, typename RHS>
2256inline BinaryOp_match<LHS, RHS, Instruction::Xor, true> m_c_Xor(const LHS &L,
2257                                                                const RHS &R) {
2258  return BinaryOp_match<LHS, RHS, Instruction::Xor, true>(L, R);
2259}
2260 
2261/// Matches a 'Neg' as 'sub 0, V'.
2262template <typename ValTy>
2263inline BinaryOp_match<cst_pred_ty<is_zero_int>, ValTy, Instruction::Sub>
2264m_Neg(const ValTy &V) {
2265  return m_Sub(m_ZeroInt(), V);
2266}
2267 
2268/// Matches a 'Neg' as 'sub nsw 0, V'.
2269template <typename ValTy>
2270inline OverflowingBinaryOp_match<cst_pred_ty<is_zero_int>, ValTy,
2271                                 Instruction::Sub,
2272                                 OverflowingBinaryOperator::NoSignedWrap>
2273m_NSWNeg(const ValTy &V) {
2274  return m_NSWSub(m_ZeroInt(), V);
2275}
2276 
2277/// Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
2278template <typename ValTy>
2279inline BinaryOp_match<ValTy, cst_pred_ty<is_all_ones>, Instruction::Xor, true>
2280m_Not(const ValTy &V) {
2281  return m_c_Xor(V, m_AllOnes());
2282}
2283 
2284/// Matches an SMin with LHS and RHS in either order.
2285template <typename LHS, typename RHS>
2286inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>
2287m_c_SMin(const LHS &L, const RHS &R) {
2288  return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>(L, R);
2289}
2290/// Matches an SMax with LHS and RHS in either order.
2291template <typename LHS, typename RHS>
2292inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>
2293m_c_SMax(const LHS &L, const RHS &R) {
2294  return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>(L, R);
2295}
2296/// Matches a UMin with LHS and RHS in either order.
2297template <typename LHS, typename RHS>
2298inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>
2299m_c_UMin(const LHS &L, const RHS &R) {
2300  return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>(L, R);
2301}
2302/// Matches a UMax with LHS and RHS in either order.
2303template <typename LHS, typename RHS>
2304inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>
2305m_c_UMax(const LHS &L, const RHS &R) {
2306  return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>(L, R);
2307}
2308 
2309template <typename LHS, typename RHS>
2310inline match_combine_or<
2311    match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>,
2312                     MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>>,
2313    match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>,
2314                     MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>>>
2315m_c_MaxOrMin(const LHS &L, const RHS &R) {
2316  return m_CombineOr(m_CombineOr(m_c_SMax(L, R), m_c_SMin(L, R)),
2317                     m_CombineOr(m_c_UMax(L, R), m_c_UMin(L, R)));
2318}
2319 
2320/// Matches FAdd with LHS and RHS in either order.
2321template <typename LHS, typename RHS>
2322inline BinaryOp_match<LHS, RHS, Instruction::FAdd, true>
2323m_c_FAdd(const LHS &L, const RHS &R) {
2324  return BinaryOp_match<LHS, RHS, Instruction::FAdd, true>(L, R);
2325}
2326 
2327/// Matches FMul with LHS and RHS in either order.
2328template <typename LHS, typename RHS>
2329inline BinaryOp_match<LHS, RHS, Instruction::FMul, true>
2330m_c_FMul(const LHS &L, const RHS &R) {
2331  return BinaryOp_match<LHS, RHS, Instruction::FMul, true>(L, R);
2332}
2333 
2334template <typename Opnd_t> struct Signum_match {
2335  Opnd_t Val;
2336  Signum_match(const Opnd_t &V) : Val(V) {}
2337 
2338  template <typename OpTy> bool match(OpTy *V) {
2339    unsigned TypeSize = V->getType()->getScalarSizeInBits();
2340    if (TypeSize == 0)
2341      return false;
2342 
2343    unsigned ShiftWidth = TypeSize - 1;
2344    Value *OpL = nullptr, *OpR = nullptr;
2345 
2346    // This is the representation of signum we match:
2347    //
2348    //  signum(x) == (x >> 63) | (-x >>u 63)
2349    //
2350    // An i1 value is its own signum, so it's correct to match
2351    //
2352    //  signum(x) == (x >> 0)  | (-x >>u 0)
2353    //
2354    // for i1 values.
2355 
2356    auto LHS = m_AShr(m_Value(OpL), m_SpecificInt(ShiftWidth));
2357    auto RHS = m_LShr(m_Neg(m_Value(OpR)), m_SpecificInt(ShiftWidth));
2358    auto Signum = m_Or(LHS, RHS);
2359 
2360    return Signum.match(V) && OpL == OpR && Val.match(OpL);
2361  }
2362};
2363 
2364/// Matches a signum pattern.
2365///
2366/// signum(x) =
2367///      x >  0  ->  1
2368///      x == 0  ->  0
2369///      x <  0  -> -1
2370template <typename Val_t> inline Signum_match<Val_t> m_Signum(const Val_t &V) {
2371  return Signum_match<Val_t>(V);
2372}
2373 
2374template <int Ind, typename Opnd_t> struct ExtractValue_match {
2375  Opnd_t Val;
2376  ExtractValue_match(const Opnd_t &V) : Val(V) {}
2377 
2378  template <typename OpTy> bool match(OpTy *V) {
2379    if (auto *I = dyn_cast<ExtractValueInst>(V)) {
2380      // If Ind is -1, don't inspect indices
2381      if (Ind != -1 &&
2382          !(I->getNumIndices() == 1 && I->getIndices()[0] == (unsigned)Ind))
2383        return false;
2384      return Val.match(I->getAggregateOperand());
2385    }
2386    return false;
2387  }
2388};
2389 
2390/// Match a single index ExtractValue instruction.
2391/// For example m_ExtractValue<1>(...)
2392template <int Ind, typename Val_t>
2393inline ExtractValue_match<Ind, Val_t> m_ExtractValue(const Val_t &V) {
2394  return ExtractValue_match<Ind, Val_t>(V);
2395}
2396 
2397/// Match an ExtractValue instruction with any index.
2398/// For example m_ExtractValue(...)
2399template <typename Val_t>
2400inline ExtractValue_match<-1, Val_t> m_ExtractValue(const Val_t &V) {
2401  return ExtractValue_match<-1, Val_t>(V);
2402}
2403 
2404/// Matcher for a single index InsertValue instruction.
2405template <int Ind, typename T0, typename T1> struct InsertValue_match {
2406  T0 Op0;
2407  T1 Op1;
2408 
2409  InsertValue_match(const T0 &Op0, const T1 &Op1) : Op0(Op0), Op1(Op1) {}
2410 
2411  template <typename OpTy> bool match(OpTy *V) {
2412    if (auto *I = dyn_cast<InsertValueInst>(V)) {
2413      return Op0.match(I->getOperand(0)) && Op1.match(I->getOperand(1)) &&
2414             I->getNumIndices() == 1 && Ind == I->getIndices()[0];
2415    }
2416    return false;
2417  }
2418};
2419 
2420/// Matches a single index InsertValue instruction.
2421template <int Ind, typename Val_t, typename Elt_t>
2422inline InsertValue_match<Ind, Val_t, Elt_t> m_InsertValue(const Val_t &Val,
2423                                                          const Elt_t &Elt) {
2424  return InsertValue_match<Ind, Val_t, Elt_t>(Val, Elt);
2425}
2426 
2427/// Matches patterns for `vscale`. This can either be a call to `llvm.vscale` or
2428/// the constant expression
2429///  `ptrtoint(gep <vscale x 1 x i8>, <vscale x 1 x i8>* null, i32 1>`
2430/// under the right conditions determined by DataLayout.
2431struct VScaleVal_match {
2432  const DataLayout &DL;
2433  VScaleVal_match(const DataLayout &DL) : DL(DL) {}
2434 
2435  template <typename ITy> bool match(ITy *V) {
2436    if (m_Intrinsic<Intrinsic::vscale>().match(V))
2437      return true;
2438 
2439    Value *Ptr;
2440    if (m_PtrToInt(m_Value(Ptr)).match(V)) {
2441      if (auto *GEP = dyn_cast<GEPOperator>(Ptr)) {
2442        auto *DerefTy = GEP->getSourceElementType();
2443        if (GEP->getNumIndices() == 1 && isa<ScalableVectorType>(DerefTy) &&
2444            m_Zero().match(GEP->getPointerOperand()) &&
2445            m_SpecificInt(1).match(GEP->idx_begin()->get()) &&
2446            DL.getTypeAllocSizeInBits(DerefTy).getKnownMinSize() == 8)
2447          return true;
2448      }
2449    }
2450 
2451    return false;
2452  }
2453};
2454 
2455inline VScaleVal_match m_VScale(const DataLayout &DL) {
2456  return VScaleVal_match(DL);
2457}
2458 
2459template <typename LHS, typename RHS, unsigned Opcode>
2460struct LogicalOp_match {
2461  LHS L;
2462  RHS R;
2463 
2464  LogicalOp_match(const LHS &L, const RHS &R) : L(L), R(R) {}
2465 
2466  template <typename T> bool match(T *V) {
2467    if (auto *I = dyn_cast<Instruction>(V)) {
2468      if (!I->getType()->isIntOrIntVectorTy(1))
2469        return false;
2470 
2471      if (I->getOpcode() == Opcode && L.match(I->getOperand(0)) &&
2472          R.match(I->getOperand(1)))
2473        return true;
2474 
2475      if (auto *SI = dyn_cast<SelectInst>(I)) {
2476        if (Opcode == Instruction::And) {
2477          if (const auto *C = dyn_cast<Constant>(SI->getFalseValue()))
2478            if (C->isNullValue() && L.match(SI->getCondition()) &&
2479                R.match(SI->getTrueValue()))
2480              return true;
2481        } else {
2482          assert(Opcode == Instruction::Or)(static_cast<void> (0));
2483          if (const auto *C = dyn_cast<Constant>(SI->getTrueValue()))
2484            if (C->isOneValue() && L.match(SI->getCondition()) &&
2485                R.match(SI->getFalseValue()))
2486              return true;
2487        }
2488      }
2489    }
2490 
2491    return false;
2492  }
2493};
2494 
2495/// Matches L && R either in the form of L & R or L ? R : false.
2496/// Note that the latter form is poison-blocking.
2497template <typename LHS, typename RHS>
2498inline LogicalOp_match<LHS, RHS, Instruction::And>
2499m_LogicalAnd(const LHS &L, const RHS &R) {
2500  return LogicalOp_match<LHS, RHS, Instruction::And>(L, R);
2501}
2502 
2503/// Matches L && R where L and R are arbitrary values.
2504inline auto m_LogicalAnd() { return m_LogicalAnd(m_Value(), m_Value()); }
2505 
2506/// Matches L || R either in the form of L | R or L ? true : R.
2507/// Note that the latter form is poison-blocking.
2508template <typename LHS, typename RHS>
2509inline LogicalOp_match<LHS, RHS, Instruction::Or>
2510m_LogicalOr(const LHS &L, const RHS &R) {
2511  return LogicalOp_match<LHS, RHS, Instruction::Or>(L, R);
2512}
2513 
2514/// Matches L || R where L and R are arbitrary values.
2515inline auto m_LogicalOr() {
2516  return m_LogicalOr(m_Value(), m_Value());
2517}
2518 
2519} // end namespace PatternMatch
2520} // end namespace llvm
2521 
2522#endif // LLVM_IR_PATTERNMATCH_H