/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/CodeGen/AtomicExpandPass.cpp

Bug Summary

File:	src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/CodeGen/AtomicExpandPass.cpp
Warning:	line 1742, column 8 1st function call argument is an uninitialized value

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name AtomicExpandPass.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 -mrelocation-model static -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Analysis -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ASMParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/BinaryFormat -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitstream -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /include/llvm/CodeGen -I /include/llvm/CodeGen/PBQP -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Coroutines -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData/Coverage -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/CodeView -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/DWARF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/MSF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/PDB -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Demangle -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/JITLink -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/Orc -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenACC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenMP -I /include/llvm/CodeGen/GlobalISel -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IRReader -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/LTO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Linker -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC/MCParser -I /include/llvm/CodeGen/MIRParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Object -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Option -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Passes -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Scalar -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ADT -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/Symbolize -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Target -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Utils -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Vectorize -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/IPO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include -I /usr/src/gnu/usr.bin/clang/libLLVM/../include -I /usr/src/gnu/usr.bin/clang/libLLVM/obj -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include -D NDEBUG -D __STDC_LIMIT_MACROS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D LLVM_PREFIX="/usr" -internal-isystem /usr/include/c++/v1 -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -ferror-limit 19 -fvisibility-inlines-hidden -fwrapv -stack-protector 2 -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c++ /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/CodeGen/AtomicExpandPass.cpp

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/CodeGen/AtomicExpandPass.cpp

→

1//===- AtomicExpandPass.cpp - Expand atomic instructions ------------------===//
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 contains a pass (at IR level) to replace atomic instructions with
10// __atomic_* library calls, or target specific instruction which implement the
11// same semantics in a way which better fits the target backend.  This can
12// include the use of (intrinsic-based) load-linked/store-conditional loops,
13// AtomicCmpXchg, or type coercions.
14//
15//===----------------------------------------------------------------------===//

17#include "llvm/ADT/ArrayRef.h"
18#include "llvm/ADT/STLExtras.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/CodeGen/AtomicExpandUtils.h"
21#include "llvm/CodeGen/RuntimeLibcalls.h"
22#include "llvm/CodeGen/TargetLowering.h"
23#include "llvm/CodeGen/TargetPassConfig.h"
24#include "llvm/CodeGen/TargetSubtargetInfo.h"
25#include "llvm/CodeGen/ValueTypes.h"
26#include "llvm/IR/Attributes.h"
27#include "llvm/IR/BasicBlock.h"
28#include "llvm/IR/Constant.h"
29#include "llvm/IR/Constants.h"
30#include "llvm/IR/DataLayout.h"
31#include "llvm/IR/DerivedTypes.h"
32#include "llvm/IR/Function.h"
33#include "llvm/IR/IRBuilder.h"
34#include "llvm/IR/InstIterator.h"
35#include "llvm/IR/Instruction.h"
36#include "llvm/IR/Instructions.h"
37#include "llvm/IR/Module.h"
38#include "llvm/IR/Type.h"
39#include "llvm/IR/User.h"
40#include "llvm/IR/Value.h"
41#include "llvm/InitializePasses.h"
42#include "llvm/Pass.h"
43#include "llvm/Support/AtomicOrdering.h"
44#include "llvm/Support/Casting.h"
45#include "llvm/Support/Debug.h"
46#include "llvm/Support/ErrorHandling.h"
47#include "llvm/Support/raw_ostream.h"
48#include "llvm/Target/TargetMachine.h"
49#include <cassert>
50#include <cstdint>
51#include <iterator>

53using namespace llvm;

55#define DEBUG_TYPE"atomic-expand" "atomic-expand"

57namespace {

class AtomicExpand: public FunctionPass {
  const TargetLowering *TLI = nullptr;

public:
  static char ID; // Pass identification, replacement for typeid

  AtomicExpand() : FunctionPass(ID) {
    initializeAtomicExpandPass(*PassRegistry::getPassRegistry());
  }

  bool runOnFunction(Function &F) override;

private:
  bool bracketInstWithFences(Instruction *I, AtomicOrdering Order);
  IntegerType *getCorrespondingIntegerType(Type *T, const DataLayout &DL);
  LoadInst *convertAtomicLoadToIntegerType(LoadInst *LI);
  bool tryExpandAtomicLoad(LoadInst *LI);
  bool expandAtomicLoadToLL(LoadInst *LI);
  bool expandAtomicLoadToCmpXchg(LoadInst *LI);
  StoreInst *convertAtomicStoreToIntegerType(StoreInst *SI);
  bool expandAtomicStore(StoreInst *SI);
  bool tryExpandAtomicRMW(AtomicRMWInst *AI);
  AtomicRMWInst *convertAtomicXchgToIntegerType(AtomicRMWInst *RMWI);
  Value *
  insertRMWLLSCLoop(IRBuilder<> &Builder, Type *ResultTy, Value *Addr,
                    Align AddrAlign, AtomicOrdering MemOpOrder,
                    function_ref<Value *(IRBuilder<> &, Value *)> PerformOp);
  void expandAtomicOpToLLSC(
      Instruction *I, Type *ResultTy, Value *Addr, Align AddrAlign,
      AtomicOrdering MemOpOrder,
      function_ref<Value *(IRBuilder<> &, Value *)> PerformOp);
  void expandPartwordAtomicRMW(
      AtomicRMWInst *I,
      TargetLoweringBase::AtomicExpansionKind ExpansionKind);
  AtomicRMWInst *widenPartwordAtomicRMW(AtomicRMWInst *AI);
  bool expandPartwordCmpXchg(AtomicCmpXchgInst *I);
  void expandAtomicRMWToMaskedIntrinsic(AtomicRMWInst *AI);
  void expandAtomicCmpXchgToMaskedIntrinsic(AtomicCmpXchgInst *CI);

  AtomicCmpXchgInst *convertCmpXchgToIntegerType(AtomicCmpXchgInst *CI);
  static Value *insertRMWCmpXchgLoop(
      IRBuilder<> &Builder, Type *ResultType, Value *Addr, Align AddrAlign,
      AtomicOrdering MemOpOrder, SyncScope::ID SSID,
      function_ref<Value *(IRBuilder<> &, Value *)> PerformOp,
      CreateCmpXchgInstFun CreateCmpXchg);
  bool tryExpandAtomicCmpXchg(AtomicCmpXchgInst *CI);

  bool expandAtomicCmpXchg(AtomicCmpXchgInst *CI);
  bool isIdempotentRMW(AtomicRMWInst *RMWI);
  bool simplifyIdempotentRMW(AtomicRMWInst *RMWI);

  bool expandAtomicOpToLibcall(Instruction *I, unsigned Size, Align Alignment,
                               Value *PointerOperand, Value *ValueOperand,
                               Value *CASExpected, AtomicOrdering Ordering,
                               AtomicOrdering Ordering2,
                               ArrayRef<RTLIB::Libcall> Libcalls);
  void expandAtomicLoadToLibcall(LoadInst *LI);
  void expandAtomicStoreToLibcall(StoreInst *LI);
  void expandAtomicRMWToLibcall(AtomicRMWInst *I);
  void expandAtomicCASToLibcall(AtomicCmpXchgInst *I);

  friend bool
  llvm::expandAtomicRMWToCmpXchg(AtomicRMWInst *AI,
                                 CreateCmpXchgInstFun CreateCmpXchg);
};

125} // end anonymous namespace

127char AtomicExpand::ID = 0;

129char &llvm::AtomicExpandID = AtomicExpand::ID;

131INITIALIZE_PASS(AtomicExpand, DEBUG_TYPE, "Expand Atomic instructions",static void *initializeAtomicExpandPassOnce(PassRegistry &
Registry) { PassInfo *PI = new PassInfo( "Expand Atomic instructions"
, "atomic-expand", &AtomicExpand::ID, PassInfo::NormalCtor_t
(callDefaultCtor<AtomicExpand>), false, false); Registry
.registerPass(*PI, true); return PI; } static llvm::once_flag
 InitializeAtomicExpandPassFlag; void llvm::initializeAtomicExpandPass
(PassRegistry &Registry) { llvm::call_once(InitializeAtomicExpandPassFlag
, initializeAtomicExpandPassOnce, std::ref(Registry)); }
              false, false)static void *initializeAtomicExpandPassOnce(PassRegistry &
Registry) { PassInfo *PI = new PassInfo( "Expand Atomic instructions"
, "atomic-expand", &AtomicExpand::ID, PassInfo::NormalCtor_t
(callDefaultCtor<AtomicExpand>), false, false); Registry
.registerPass(*PI, true); return PI; } static llvm::once_flag
 InitializeAtomicExpandPassFlag; void llvm::initializeAtomicExpandPass
(PassRegistry &Registry) { llvm::call_once(InitializeAtomicExpandPassFlag
, initializeAtomicExpandPassOnce, std::ref(Registry)); }

134FunctionPass *llvm::createAtomicExpandPass() { return new AtomicExpand(); }

136// Helper functions to retrieve the size of atomic instructions.
137static unsigned getAtomicOpSize(LoadInst *LI) {
const DataLayout &DL = LI->getModule()->getDataLayout();
return DL.getTypeStoreSize(LI->getType());
140}

142static unsigned getAtomicOpSize(StoreInst *SI) {
const DataLayout &DL = SI->getModule()->getDataLayout();
return DL.getTypeStoreSize(SI->getValueOperand()->getType());
145}

147static unsigned getAtomicOpSize(AtomicRMWInst *RMWI) {
const DataLayout &DL = RMWI->getModule()->getDataLayout();
return DL.getTypeStoreSize(RMWI->getValOperand()->getType());
150}

152static unsigned getAtomicOpSize(AtomicCmpXchgInst *CASI) {
const DataLayout &DL = CASI->getModule()->getDataLayout();
return DL.getTypeStoreSize(CASI->getCompareOperand()->getType());
155}

157// Determine if a particular atomic operation has a supported size,
158// and is of appropriate alignment, to be passed through for target
159// lowering. (Versus turning into a __atomic libcall)
160template <typename Inst>
161static bool atomicSizeSupported(const TargetLowering *TLI, Inst *I) {
unsigned Size = getAtomicOpSize(I);
Align Alignment = I->getAlign();
return Alignment >= Size &&
       Size <= TLI->getMaxAtomicSizeInBitsSupported() / 8;
166}

168bool AtomicExpand::runOnFunction(Function &F) {
auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
if (!TPC)
1
Assuming 'TPC' is non-null→
2
←
Taking false branch→
  return false;

auto &TM = TPC->getTM<TargetMachine>();
if (!TM.getSubtargetImpl(F)->enableAtomicExpand())
3
←
Assuming the condition is false→
4
←
Taking false branch→
  return false;
TLI = TM.getSubtargetImpl(F)->getTargetLowering();

SmallVector<Instruction *, 1> AtomicInsts;

// Changing control-flow while iterating through it is a bad idea, so gather a
// list of all atomic instructions before we start.
for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
5
←
Loop condition is false. Execution continues on line 188→
  Instruction *I = &*II;
  if (I->isAtomic() && !isa<FenceInst>(I))
    AtomicInsts.push_back(I);
}

bool MadeChange = false;
for (auto I : AtomicInsts) {
6
←
Assuming '__begin1' is not equal to '__end1'→
  auto LI = dyn_cast<LoadInst>(I);
7
←
Assuming 'I' is not a 'LoadInst'→
  auto SI = dyn_cast<StoreInst>(I);
8
←
Assuming 'I' is not a 'StoreInst'→
  auto RMWI = dyn_cast<AtomicRMWInst>(I);
9
←
Assuming 'I' is a 'AtomicRMWInst'→
  auto CASI = dyn_cast<AtomicCmpXchgInst>(I);
10
←
Assuming 'I' is not a 'AtomicCmpXchgInst'→
  assert((LI || SI || RMWI || CASI) && "Unknown atomic instruction")((void)0);

  // If the Size/Alignment is not supported, replace with a libcall.
  if (LI10.1
'LI' is null
1
'LI' is null
) {
11
←
Taking false branch→
    if (!atomicSizeSupported(TLI, LI)) {
      expandAtomicLoadToLibcall(LI);
      MadeChange = true;
      continue;
    }
  } else if (SI11.1
'SI' is null
1
'SI' is null
) {
12
←
Taking false branch→
    if (!atomicSizeSupported(TLI, SI)) {
      expandAtomicStoreToLibcall(SI);
      MadeChange = true;
      continue;
    }
  } else if (RMWI12.1
'RMWI' is non-null
1
'RMWI' is non-null
) {
13
←
Taking true branch→
    if (!atomicSizeSupported(TLI, RMWI)) {
14
←
Taking true branch→
      expandAtomicRMWToLibcall(RMWI);
15
←
Calling 'AtomicExpand::expandAtomicRMWToLibcall'→
      MadeChange = true;
      continue;
    }
  } else if (CASI) {
    if (!atomicSizeSupported(TLI, CASI)) {
      expandAtomicCASToLibcall(CASI);
      MadeChange = true;
      continue;
    }
  }

  if (TLI->shouldInsertFencesForAtomic(I)) {
    auto FenceOrdering = AtomicOrdering::Monotonic;
    if (LI && isAcquireOrStronger(LI->getOrdering())) {
      FenceOrdering = LI->getOrdering();
      LI->setOrdering(AtomicOrdering::Monotonic);
    } else if (SI && isReleaseOrStronger(SI->getOrdering())) {
      FenceOrdering = SI->getOrdering();
      SI->setOrdering(AtomicOrdering::Monotonic);
    } else if (RMWI && (isReleaseOrStronger(RMWI->getOrdering()) ||
                        isAcquireOrStronger(RMWI->getOrdering()))) {
      FenceOrdering = RMWI->getOrdering();
      RMWI->setOrdering(AtomicOrdering::Monotonic);
    } else if (CASI &&
               TLI->shouldExpandAtomicCmpXchgInIR(CASI) ==
                   TargetLoweringBase::AtomicExpansionKind::None &&
               (isReleaseOrStronger(CASI->getSuccessOrdering()) ||
                isAcquireOrStronger(CASI->getSuccessOrdering()) ||
                isAcquireOrStronger(CASI->getFailureOrdering()))) {
      // If a compare and swap is lowered to LL/SC, we can do smarter fence
      // insertion, with a stronger one on the success path than on the
      // failure path. As a result, fence insertion is directly done by
      // expandAtomicCmpXchg in that case.
      FenceOrdering = CASI->getMergedOrdering();
      CASI->setSuccessOrdering(AtomicOrdering::Monotonic);
      CASI->setFailureOrdering(AtomicOrdering::Monotonic);
    }

    if (FenceOrdering != AtomicOrdering::Monotonic) {
      MadeChange |= bracketInstWithFences(I, FenceOrdering);
    }
  }

  if (LI) {
    if (LI->getType()->isFloatingPointTy()) {
      // TODO: add a TLI hook to control this so that each target can
      // convert to lowering the original type one at a time.
      LI = convertAtomicLoadToIntegerType(LI);
      assert(LI->getType()->isIntegerTy() && "invariant broken")((void)0);
      MadeChange = true;
    }

    MadeChange |= tryExpandAtomicLoad(LI);
  } else if (SI) {
    if (SI->getValueOperand()->getType()->isFloatingPointTy()) {
      // TODO: add a TLI hook to control this so that each target can
      // convert to lowering the original type one at a time.
      SI = convertAtomicStoreToIntegerType(SI);
      assert(SI->getValueOperand()->getType()->isIntegerTy() &&((void)0)
             "invariant broken")((void)0);
      MadeChange = true;
    }

    if (TLI->shouldExpandAtomicStoreInIR(SI))
      MadeChange |= expandAtomicStore(SI);
  } else if (RMWI) {
    // There are two different ways of expanding RMW instructions:
    // - into a load if it is idempotent
    // - into a Cmpxchg/LL-SC loop otherwise
    // we try them in that order.

    if (isIdempotentRMW(RMWI) && simplifyIdempotentRMW(RMWI)) {
      MadeChange = true;
    } else {
      AtomicRMWInst::BinOp Op = RMWI->getOperation();
      if (Op == AtomicRMWInst::Xchg &&
          RMWI->getValOperand()->getType()->isFloatingPointTy()) {
        // TODO: add a TLI hook to control this so that each target can
        // convert to lowering the original type one at a time.
        RMWI = convertAtomicXchgToIntegerType(RMWI);
        assert(RMWI->getValOperand()->getType()->isIntegerTy() &&((void)0)
               "invariant broken")((void)0);
        MadeChange = true;
      }
      unsigned MinCASSize = TLI->getMinCmpXchgSizeInBits() / 8;
      unsigned ValueSize = getAtomicOpSize(RMWI);
      if (ValueSize < MinCASSize &&
          (Op == AtomicRMWInst::Or || Op == AtomicRMWInst::Xor ||
           Op == AtomicRMWInst::And)) {
        RMWI = widenPartwordAtomicRMW(RMWI);
        MadeChange = true;
      }

      MadeChange |= tryExpandAtomicRMW(RMWI);
    }
  } else if (CASI) {
    // TODO: when we're ready to make the change at the IR level, we can
    // extend convertCmpXchgToInteger for floating point too.
    assert(!CASI->getCompareOperand()->getType()->isFloatingPointTy() &&((void)0)
           "unimplemented - floating point not legal at IR level")((void)0);
    if (CASI->getCompareOperand()->getType()->isPointerTy() ) {
      // TODO: add a TLI hook to control this so that each target can
      // convert to lowering the original type one at a time.
      CASI = convertCmpXchgToIntegerType(CASI);
      assert(CASI->getCompareOperand()->getType()->isIntegerTy() &&((void)0)
             "invariant broken")((void)0);
      MadeChange = true;
    }

    MadeChange |= tryExpandAtomicCmpXchg(CASI);
  }
}
return MadeChange;
325}

327bool AtomicExpand::bracketInstWithFences(Instruction *I, AtomicOrdering Order) {
IRBuilder<> Builder(I);

auto LeadingFence = TLI->emitLeadingFence(Builder, I, Order);

auto TrailingFence = TLI->emitTrailingFence(Builder, I, Order);
// We have a guard here because not every atomic operation generates a
// trailing fence.
if (TrailingFence)
  TrailingFence->moveAfter(I);

return (LeadingFence || TrailingFence);
339}

341/// Get the iX type with the same bitwidth as T.
342IntegerType *AtomicExpand::getCorrespondingIntegerType(Type *T,
                                                     const DataLayout &DL) {
EVT VT = TLI->getMemValueType(DL, T);
unsigned BitWidth = VT.getStoreSizeInBits();
assert(BitWidth == VT.getSizeInBits() && "must be a power of two")((void)0);
return IntegerType::get(T->getContext(), BitWidth);
348}

350/// Convert an atomic load of a non-integral type to an integer load of the
351/// equivalent bitwidth.  See the function comment on
352/// convertAtomicStoreToIntegerType for background.
353LoadInst *AtomicExpand::convertAtomicLoadToIntegerType(LoadInst *LI) {
auto *M = LI->getModule();
Type *NewTy = getCorrespondingIntegerType(LI->getType(),
                                          M->getDataLayout());

IRBuilder<> Builder(LI);

Value *Addr = LI->getPointerOperand();
Type *PT = PointerType::get(NewTy,
                            Addr->getType()->getPointerAddressSpace());
Value *NewAddr = Builder.CreateBitCast(Addr, PT);

auto *NewLI = Builder.CreateLoad(NewTy, NewAddr);
NewLI->setAlignment(LI->getAlign());
NewLI->setVolatile(LI->isVolatile());
NewLI->setAtomic(LI->getOrdering(), LI->getSyncScopeID());
LLVM_DEBUG(dbgs() << "Replaced " << *LI << " with " << *NewLI << "\n")do { } while (false);

Value *NewVal = Builder.CreateBitCast(NewLI, LI->getType());
LI->replaceAllUsesWith(NewVal);
LI->eraseFromParent();
return NewLI;
375}

377AtomicRMWInst *
378AtomicExpand::convertAtomicXchgToIntegerType(AtomicRMWInst *RMWI) {
auto *M = RMWI->getModule();
Type *NewTy =
    getCorrespondingIntegerType(RMWI->getType(), M->getDataLayout());

IRBuilder<> Builder(RMWI);

Value *Addr = RMWI->getPointerOperand();
Value *Val = RMWI->getValOperand();
Type *PT = PointerType::get(NewTy, RMWI->getPointerAddressSpace());
Value *NewAddr = Builder.CreateBitCast(Addr, PT);
Value *NewVal = Builder.CreateBitCast(Val, NewTy);

auto *NewRMWI =
    Builder.CreateAtomicRMW(AtomicRMWInst::Xchg, NewAddr, NewVal,
                            RMWI->getAlign(), RMWI->getOrdering());
NewRMWI->setVolatile(RMWI->isVolatile());
LLVM_DEBUG(dbgs() << "Replaced " << *RMWI << " with " << *NewRMWI << "\n")do { } while (false);

Value *NewRVal = Builder.CreateBitCast(NewRMWI, RMWI->getType());
RMWI->replaceAllUsesWith(NewRVal);
RMWI->eraseFromParent();
return NewRMWI;
401}

403bool AtomicExpand::tryExpandAtomicLoad(LoadInst *LI) {
switch (TLI->shouldExpandAtomicLoadInIR(LI)) {
case TargetLoweringBase::AtomicExpansionKind::None:
  return false;
case TargetLoweringBase::AtomicExpansionKind::LLSC:
  expandAtomicOpToLLSC(
      LI, LI->getType(), LI->getPointerOperand(), LI->getAlign(),
      LI->getOrdering(),
      [](IRBuilder<> &Builder, Value *Loaded) { return Loaded; });
  return true;
case TargetLoweringBase::AtomicExpansionKind::LLOnly:
  return expandAtomicLoadToLL(LI);
case TargetLoweringBase::AtomicExpansionKind::CmpXChg:
  return expandAtomicLoadToCmpXchg(LI);
default:
  llvm_unreachable("Unhandled case in tryExpandAtomicLoad")__builtin_unreachable();
}
420}

422bool AtomicExpand::expandAtomicLoadToLL(LoadInst *LI) {
IRBuilder<> Builder(LI);

// On some architectures, load-linked instructions are atomic for larger
// sizes than normal loads. For example, the only 64-bit load guaranteed
// to be single-copy atomic by ARM is an ldrexd (A3.5.3).
Value *Val = TLI->emitLoadLinked(Builder, LI->getType(),
                                 LI->getPointerOperand(), LI->getOrdering());
TLI->emitAtomicCmpXchgNoStoreLLBalance(Builder);

LI->replaceAllUsesWith(Val);
LI->eraseFromParent();

return true;
436}

438bool AtomicExpand::expandAtomicLoadToCmpXchg(LoadInst *LI) {
IRBuilder<> Builder(LI);
AtomicOrdering Order = LI->getOrdering();
if (Order == AtomicOrdering::Unordered)
  Order = AtomicOrdering::Monotonic;

Value *Addr = LI->getPointerOperand();
Type *Ty = LI->getType();
Constant *DummyVal = Constant::getNullValue(Ty);

Value *Pair = Builder.CreateAtomicCmpXchg(
    Addr, DummyVal, DummyVal, LI->getAlign(), Order,
    AtomicCmpXchgInst::getStrongestFailureOrdering(Order));
Value *Loaded = Builder.CreateExtractValue(Pair, 0, "loaded");

LI->replaceAllUsesWith(Loaded);
LI->eraseFromParent();

return true;
457}

459/// Convert an atomic store of a non-integral type to an integer store of the
460/// equivalent bitwidth.  We used to not support floating point or vector
461/// atomics in the IR at all.  The backends learned to deal with the bitcast
462/// idiom because that was the only way of expressing the notion of a atomic
463/// float or vector store.  The long term plan is to teach each backend to
464/// instruction select from the original atomic store, but as a migration
465/// mechanism, we convert back to the old format which the backends understand.
466/// Each backend will need individual work to recognize the new format.
467StoreInst *AtomicExpand::convertAtomicStoreToIntegerType(StoreInst *SI) {
IRBuilder<> Builder(SI);
auto *M = SI->getModule();
Type *NewTy = getCorrespondingIntegerType(SI->getValueOperand()->getType(),
                                          M->getDataLayout());
Value *NewVal = Builder.CreateBitCast(SI->getValueOperand(), NewTy);

Value *Addr = SI->getPointerOperand();
Type *PT = PointerType::get(NewTy,
                            Addr->getType()->getPointerAddressSpace());
Value *NewAddr = Builder.CreateBitCast(Addr, PT);

StoreInst *NewSI = Builder.CreateStore(NewVal, NewAddr);
NewSI->setAlignment(SI->getAlign());
NewSI->setVolatile(SI->isVolatile());
NewSI->setAtomic(SI->getOrdering(), SI->getSyncScopeID());
LLVM_DEBUG(dbgs() << "Replaced " << *SI << " with " << *NewSI << "\n")do { } while (false);
SI->eraseFromParent();
return NewSI;
486}

488bool AtomicExpand::expandAtomicStore(StoreInst *SI) {
// This function is only called on atomic stores that are too large to be
// atomic if implemented as a native store. So we replace them by an
// atomic swap, that can be implemented for example as a ldrex/strex on ARM
// or lock cmpxchg8/16b on X86, as these are atomic for larger sizes.
// It is the responsibility of the target to only signal expansion via
// shouldExpandAtomicRMW in cases where this is required and possible.
IRBuilder<> Builder(SI);
AtomicRMWInst *AI = Builder.CreateAtomicRMW(
    AtomicRMWInst::Xchg, SI->getPointerOperand(), SI->getValueOperand(),
    SI->getAlign(), SI->getOrdering());
SI->eraseFromParent();

// Now we have an appropriate swap instruction, lower it as usual.
return tryExpandAtomicRMW(AI);
503}

505static void createCmpXchgInstFun(IRBuilder<> &Builder, Value *Addr,
                               Value *Loaded, Value *NewVal, Align AddrAlign,
                               AtomicOrdering MemOpOrder, SyncScope::ID SSID,
                               Value *&Success, Value *&NewLoaded) {
Type *OrigTy = NewVal->getType();

// This code can go away when cmpxchg supports FP types.
bool NeedBitcast = OrigTy->isFloatingPointTy();
if (NeedBitcast) {
  IntegerType *IntTy = Builder.getIntNTy(OrigTy->getPrimitiveSizeInBits());
  unsigned AS = Addr->getType()->getPointerAddressSpace();
  Addr = Builder.CreateBitCast(Addr, IntTy->getPointerTo(AS));
  NewVal = Builder.CreateBitCast(NewVal, IntTy);
  Loaded = Builder.CreateBitCast(Loaded, IntTy);
}

Value *Pair = Builder.CreateAtomicCmpXchg(
    Addr, Loaded, NewVal, AddrAlign, MemOpOrder,
    AtomicCmpXchgInst::getStrongestFailureOrdering(MemOpOrder), SSID);
Success = Builder.CreateExtractValue(Pair, 1, "success");
NewLoaded = Builder.CreateExtractValue(Pair, 0, "newloaded");

if (NeedBitcast)
  NewLoaded = Builder.CreateBitCast(NewLoaded, OrigTy);
529}

531/// Emit IR to implement the given atomicrmw operation on values in registers,
532/// returning the new value.
533static Value *performAtomicOp(AtomicRMWInst::BinOp Op, IRBuilder<> &Builder,
                            Value *Loaded, Value *Inc) {
Value *NewVal;
switch (Op) {
case AtomicRMWInst::Xchg:
  return Inc;
case AtomicRMWInst::Add:
  return Builder.CreateAdd(Loaded, Inc, "new");
case AtomicRMWInst::Sub:
  return Builder.CreateSub(Loaded, Inc, "new");
case AtomicRMWInst::And:
  return Builder.CreateAnd(Loaded, Inc, "new");
case AtomicRMWInst::Nand:
  return Builder.CreateNot(Builder.CreateAnd(Loaded, Inc), "new");
case AtomicRMWInst::Or:
  return Builder.CreateOr(Loaded, Inc, "new");
case AtomicRMWInst::Xor:
  return Builder.CreateXor(Loaded, Inc, "new");
case AtomicRMWInst::Max:
  NewVal = Builder.CreateICmpSGT(Loaded, Inc);
  return Builder.CreateSelect(NewVal, Loaded, Inc, "new");
case AtomicRMWInst::Min:
  NewVal = Builder.CreateICmpSLE(Loaded, Inc);
  return Builder.CreateSelect(NewVal, Loaded, Inc, "new");
case AtomicRMWInst::UMax:
  NewVal = Builder.CreateICmpUGT(Loaded, Inc);
  return Builder.CreateSelect(NewVal, Loaded, Inc, "new");
case AtomicRMWInst::UMin:
  NewVal = Builder.CreateICmpULE(Loaded, Inc);
  return Builder.CreateSelect(NewVal, Loaded, Inc, "new");
case AtomicRMWInst::FAdd:
  return Builder.CreateFAdd(Loaded, Inc, "new");
case AtomicRMWInst::FSub:
  return Builder.CreateFSub(Loaded, Inc, "new");
default:
  llvm_unreachable("Unknown atomic op")__builtin_unreachable();
}
570}

572bool AtomicExpand::tryExpandAtomicRMW(AtomicRMWInst *AI) {
switch (TLI->shouldExpandAtomicRMWInIR(AI)) {
case TargetLoweringBase::AtomicExpansionKind::None:
  return false;
case TargetLoweringBase::AtomicExpansionKind::LLSC: {
  unsigned MinCASSize = TLI->getMinCmpXchgSizeInBits() / 8;
  unsigned ValueSize = getAtomicOpSize(AI);
  if (ValueSize < MinCASSize) {
    expandPartwordAtomicRMW(AI,
                            TargetLoweringBase::AtomicExpansionKind::LLSC);
  } else {
    auto PerformOp = [&](IRBuilder<> &Builder, Value *Loaded) {
      return performAtomicOp(AI->getOperation(), Builder, Loaded,
                             AI->getValOperand());
    };
    expandAtomicOpToLLSC(AI, AI->getType(), AI->getPointerOperand(),
                         AI->getAlign(), AI->getOrdering(), PerformOp);
  }
  return true;
}
case TargetLoweringBase::AtomicExpansionKind::CmpXChg: {
  unsigned MinCASSize = TLI->getMinCmpXchgSizeInBits() / 8;
  unsigned ValueSize = getAtomicOpSize(AI);
  if (ValueSize < MinCASSize) {
    // TODO: Handle atomicrmw fadd/fsub
    if (AI->getType()->isFloatingPointTy())
      return false;

    expandPartwordAtomicRMW(AI,
                            TargetLoweringBase::AtomicExpansionKind::CmpXChg);
  } else {
    expandAtomicRMWToCmpXchg(AI, createCmpXchgInstFun);
  }
  return true;
}
case TargetLoweringBase::AtomicExpansionKind::MaskedIntrinsic: {
  expandAtomicRMWToMaskedIntrinsic(AI);
  return true;
}
default:
  llvm_unreachable("Unhandled case in tryExpandAtomicRMW")__builtin_unreachable();
}
614}

616namespace {

618struct PartwordMaskValues {
// These three fields are guaranteed to be set by createMaskInstrs.
Type *WordType = nullptr;
Type *ValueType = nullptr;
Value *AlignedAddr = nullptr;
Align AlignedAddrAlignment;
// The remaining fields can be null.
Value *ShiftAmt = nullptr;
Value *Mask = nullptr;
Value *Inv_Mask = nullptr;
628};

630LLVM_ATTRIBUTE_UNUSED__attribute__((__unused__))
631raw_ostream &operator<<(raw_ostream &O, const PartwordMaskValues &PMV) {
auto PrintObj = [&O](auto *V) {
  if (V)
    O << *V;
  else
    O << "nullptr";
  O << '\n';
};
O << "PartwordMaskValues {\n";
O << "  WordType: ";
PrintObj(PMV.WordType);
O << "  ValueType: ";
PrintObj(PMV.ValueType);
O << "  AlignedAddr: ";
PrintObj(PMV.AlignedAddr);
O << "  AlignedAddrAlignment: " << PMV.AlignedAddrAlignment.value() << '\n';
O << "  ShiftAmt: ";
PrintObj(PMV.ShiftAmt);
O << "  Mask: ";
PrintObj(PMV.Mask);
O << "  Inv_Mask: ";
PrintObj(PMV.Inv_Mask);
O << "}\n";
return O;
655}

657} // end anonymous namespace

659/// This is a helper function which builds instructions to provide
660/// values necessary for partword atomic operations. It takes an
661/// incoming address, Addr, and ValueType, and constructs the address,
662/// shift-amounts and masks needed to work with a larger value of size
663/// WordSize.
664///
665/// AlignedAddr: Addr rounded down to a multiple of WordSize
666///
667/// ShiftAmt: Number of bits to right-shift a WordSize value loaded
668///           from AlignAddr for it to have the same value as if
669///           ValueType was loaded from Addr.
670///
671/// Mask: Value to mask with the value loaded from AlignAddr to
672///       include only the part that would've been loaded from Addr.
673///
674/// Inv_Mask: The inverse of Mask.
675static PartwordMaskValues createMaskInstrs(IRBuilder<> &Builder, Instruction *I,
                                         Type *ValueType, Value *Addr,
                                         Align AddrAlign,
                                         unsigned MinWordSize) {
PartwordMaskValues PMV;

Module *M = I->getModule();
LLVMContext &Ctx = M->getContext();
const DataLayout &DL = M->getDataLayout();
unsigned ValueSize = DL.getTypeStoreSize(ValueType);

PMV.ValueType = ValueType;
PMV.WordType = MinWordSize > ValueSize ? Type::getIntNTy(Ctx, MinWordSize * 8)
                                       : ValueType;
if (PMV.ValueType == PMV.WordType) {
  PMV.AlignedAddr = Addr;
  PMV.AlignedAddrAlignment = AddrAlign;
  PMV.ShiftAmt = ConstantInt::get(PMV.ValueType, 0);
  PMV.Mask = ConstantInt::get(PMV.ValueType, ~0);
  return PMV;
}

assert(ValueSize < MinWordSize)((void)0);

Type *WordPtrType =
    PMV.WordType->getPointerTo(Addr->getType()->getPointerAddressSpace());

// TODO: we could skip some of this if AddrAlign >= MinWordSize.
Value *AddrInt = Builder.CreatePtrToInt(Addr, DL.getIntPtrType(Ctx));
PMV.AlignedAddr = Builder.CreateIntToPtr(
    Builder.CreateAnd(AddrInt, ~(uint64_t)(MinWordSize - 1)), WordPtrType,
    "AlignedAddr");
PMV.AlignedAddrAlignment = Align(MinWordSize);

Value *PtrLSB = Builder.CreateAnd(AddrInt, MinWordSize - 1, "PtrLSB");
if (DL.isLittleEndian()) {
  // turn bytes into bits
  PMV.ShiftAmt = Builder.CreateShl(PtrLSB, 3);
} else {
  // turn bytes into bits, and count from the other side.
  PMV.ShiftAmt = Builder.CreateShl(
      Builder.CreateXor(PtrLSB, MinWordSize - ValueSize), 3);
}

PMV.ShiftAmt = Builder.CreateTrunc(PMV.ShiftAmt, PMV.WordType, "ShiftAmt");
PMV.Mask = Builder.CreateShl(
    ConstantInt::get(PMV.WordType, (1 << (ValueSize * 8)) - 1), PMV.ShiftAmt,
    "Mask");
PMV.Inv_Mask = Builder.CreateNot(PMV.Mask, "Inv_Mask");
return PMV;
725}

727static Value *extractMaskedValue(IRBuilder<> &Builder, Value *WideWord,
                               const PartwordMaskValues &PMV) {
assert(WideWord->getType() == PMV.WordType && "Widened type mismatch")((void)0);
if (PMV.WordType == PMV.ValueType)
  return WideWord;

Value *Shift = Builder.CreateLShr(WideWord, PMV.ShiftAmt, "shifted");
Value *Trunc = Builder.CreateTrunc(Shift, PMV.ValueType, "extracted");
return Trunc;
736}

738static Value *insertMaskedValue(IRBuilder<> &Builder, Value *WideWord,
                              Value *Updated, const PartwordMaskValues &PMV) {
assert(WideWord->getType() == PMV.WordType && "Widened type mismatch")((void)0);
assert(Updated->getType() == PMV.ValueType && "Value type mismatch")((void)0);
if (PMV.WordType == PMV.ValueType)
  return Updated;

Value *ZExt = Builder.CreateZExt(Updated, PMV.WordType, "extended");
Value *Shift =
    Builder.CreateShl(ZExt, PMV.ShiftAmt, "shifted", /*HasNUW*/ true);
Value *And = Builder.CreateAnd(WideWord, PMV.Inv_Mask, "unmasked");
Value *Or = Builder.CreateOr(And, Shift, "inserted");
return Or;
751}

753/// Emit IR to implement a masked version of a given atomicrmw
754/// operation. (That is, only the bits under the Mask should be
755/// affected by the operation)
756static Value *performMaskedAtomicOp(AtomicRMWInst::BinOp Op,
                                  IRBuilder<> &Builder, Value *Loaded,
                                  Value *Shifted_Inc, Value *Inc,
                                  const PartwordMaskValues &PMV) {
// TODO: update to use
// https://graphics.stanford.edu/~seander/bithacks.html#MaskedMerge in order
// to merge bits from two values without requiring PMV.Inv_Mask.
switch (Op) {
case AtomicRMWInst::Xchg: {
  Value *Loaded_MaskOut = Builder.CreateAnd(Loaded, PMV.Inv_Mask);
  Value *FinalVal = Builder.CreateOr(Loaded_MaskOut, Shifted_Inc);
  return FinalVal;
}
case AtomicRMWInst::Or:
case AtomicRMWInst::Xor:
case AtomicRMWInst::And:
  llvm_unreachable("Or/Xor/And handled by widenPartwordAtomicRMW")__builtin_unreachable();
case AtomicRMWInst::Add:
case AtomicRMWInst::Sub:
case AtomicRMWInst::Nand: {
  // The other arithmetic ops need to be masked into place.
  Value *NewVal = performAtomicOp(Op, Builder, Loaded, Shifted_Inc);
  Value *NewVal_Masked = Builder.CreateAnd(NewVal, PMV.Mask);
  Value *Loaded_MaskOut = Builder.CreateAnd(Loaded, PMV.Inv_Mask);
  Value *FinalVal = Builder.CreateOr(Loaded_MaskOut, NewVal_Masked);
  return FinalVal;
}
case AtomicRMWInst::Max:
case AtomicRMWInst::Min:
case AtomicRMWInst::UMax:
case AtomicRMWInst::UMin: {
  // Finally, comparison ops will operate on the full value, so
  // truncate down to the original size, and expand out again after
  // doing the operation.
  Value *Loaded_Extract = extractMaskedValue(Builder, Loaded, PMV);
  Value *NewVal = performAtomicOp(Op, Builder, Loaded_Extract, Inc);
  Value *FinalVal = insertMaskedValue(Builder, Loaded, NewVal, PMV);
  return FinalVal;
}
default:
  llvm_unreachable("Unknown atomic op")__builtin_unreachable();
}
798}

800/// Expand a sub-word atomicrmw operation into an appropriate
801/// word-sized operation.
802///
803/// It will create an LL/SC or cmpxchg loop, as appropriate, the same
804/// way as a typical atomicrmw expansion. The only difference here is
805/// that the operation inside of the loop may operate upon only a
806/// part of the value.
807void AtomicExpand::expandPartwordAtomicRMW(
  AtomicRMWInst *AI, TargetLoweringBase::AtomicExpansionKind ExpansionKind) {
AtomicOrdering MemOpOrder = AI->getOrdering();
SyncScope::ID SSID = AI->getSyncScopeID();

IRBuilder<> Builder(AI);

PartwordMaskValues PMV =
    createMaskInstrs(Builder, AI, AI->getType(), AI->getPointerOperand(),
                     AI->getAlign(), TLI->getMinCmpXchgSizeInBits() / 8);

Value *ValOperand_Shifted =
    Builder.CreateShl(Builder.CreateZExt(AI->getValOperand(), PMV.WordType),
                      PMV.ShiftAmt, "ValOperand_Shifted");

auto PerformPartwordOp = [&](IRBuilder<> &Builder, Value *Loaded) {
  return performMaskedAtomicOp(AI->getOperation(), Builder, Loaded,
                               ValOperand_Shifted, AI->getValOperand(), PMV);
};

Value *OldResult;
if (ExpansionKind == TargetLoweringBase::AtomicExpansionKind::CmpXChg) {
  OldResult = insertRMWCmpXchgLoop(Builder, PMV.WordType, PMV.AlignedAddr,
                                   PMV.AlignedAddrAlignment, MemOpOrder,
                                   SSID, PerformPartwordOp,
                                   createCmpXchgInstFun);
} else {
  assert(ExpansionKind == TargetLoweringBase::AtomicExpansionKind::LLSC)((void)0);
  OldResult = insertRMWLLSCLoop(Builder, PMV.WordType, PMV.AlignedAddr,
                                PMV.AlignedAddrAlignment, MemOpOrder,
                                PerformPartwordOp);
}

Value *FinalOldResult = extractMaskedValue(Builder, OldResult, PMV);
AI->replaceAllUsesWith(FinalOldResult);
AI->eraseFromParent();
843}

845// Widen the bitwise atomicrmw (or/xor/and) to the minimum supported width.
846AtomicRMWInst *AtomicExpand::widenPartwordAtomicRMW(AtomicRMWInst *AI) {
IRBuilder<> Builder(AI);
AtomicRMWInst::BinOp Op = AI->getOperation();

assert((Op == AtomicRMWInst::Or || Op == AtomicRMWInst::Xor ||((void)0)
        Op == AtomicRMWInst::And) &&((void)0)
       "Unable to widen operation")((void)0);

PartwordMaskValues PMV =
    createMaskInstrs(Builder, AI, AI->getType(), AI->getPointerOperand(),
                     AI->getAlign(), TLI->getMinCmpXchgSizeInBits() / 8);

Value *ValOperand_Shifted =
    Builder.CreateShl(Builder.CreateZExt(AI->getValOperand(), PMV.WordType),
                      PMV.ShiftAmt, "ValOperand_Shifted");

Value *NewOperand;

if (Op == AtomicRMWInst::And)
  NewOperand =
      Builder.CreateOr(PMV.Inv_Mask, ValOperand_Shifted, "AndOperand");
else
  NewOperand = ValOperand_Shifted;

AtomicRMWInst *NewAI =
    Builder.CreateAtomicRMW(Op, PMV.AlignedAddr, NewOperand,
                            PMV.AlignedAddrAlignment, AI->getOrdering());

Value *FinalOldResult = extractMaskedValue(Builder, NewAI, PMV);
AI->replaceAllUsesWith(FinalOldResult);
AI->eraseFromParent();
return NewAI;
878}

880bool AtomicExpand::expandPartwordCmpXchg(AtomicCmpXchgInst *CI) {
// The basic idea here is that we're expanding a cmpxchg of a
// smaller memory size up to a word-sized cmpxchg. To do this, we
// need to add a retry-loop for strong cmpxchg, so that
// modifications to other parts of the word don't cause a spurious
// failure.

// This generates code like the following:
//     [[Setup mask values PMV.*]]
//     %NewVal_Shifted = shl i32 %NewVal, %PMV.ShiftAmt
//     %Cmp_Shifted = shl i32 %Cmp, %PMV.ShiftAmt
//     %InitLoaded = load i32* %addr
//     %InitLoaded_MaskOut = and i32 %InitLoaded, %PMV.Inv_Mask
//     br partword.cmpxchg.loop
// partword.cmpxchg.loop:
//     %Loaded_MaskOut = phi i32 [ %InitLoaded_MaskOut, %entry ],
//        [ %OldVal_MaskOut, %partword.cmpxchg.failure ]
//     %FullWord_NewVal = or i32 %Loaded_MaskOut, %NewVal_Shifted
//     %FullWord_Cmp = or i32 %Loaded_MaskOut, %Cmp_Shifted
//     %NewCI = cmpxchg i32* %PMV.AlignedAddr, i32 %FullWord_Cmp,
//        i32 %FullWord_NewVal success_ordering failure_ordering
//     %OldVal = extractvalue { i32, i1 } %NewCI, 0
//     %Success = extractvalue { i32, i1 } %NewCI, 1
//     br i1 %Success, label %partword.cmpxchg.end,
//        label %partword.cmpxchg.failure
// partword.cmpxchg.failure:
//     %OldVal_MaskOut = and i32 %OldVal, %PMV.Inv_Mask
//     %ShouldContinue = icmp ne i32 %Loaded_MaskOut, %OldVal_MaskOut
//     br i1 %ShouldContinue, label %partword.cmpxchg.loop,
//         label %partword.cmpxchg.end
// partword.cmpxchg.end:
//    %tmp1 = lshr i32 %OldVal, %PMV.ShiftAmt
//    %FinalOldVal = trunc i32 %tmp1 to i8
//    %tmp2 = insertvalue { i8, i1 } undef, i8 %FinalOldVal, 0
//    %Res = insertvalue { i8, i1 } %25, i1 %Success, 1

Value *Addr = CI->getPointerOperand();
Value *Cmp = CI->getCompareOperand();
Value *NewVal = CI->getNewValOperand();

BasicBlock *BB = CI->getParent();
Function *F = BB->getParent();
IRBuilder<> Builder(CI);
LLVMContext &Ctx = Builder.getContext();

BasicBlock *EndBB =
    BB->splitBasicBlock(CI->getIterator(), "partword.cmpxchg.end");
auto FailureBB =
    BasicBlock::Create(Ctx, "partword.cmpxchg.failure", F, EndBB);
auto LoopBB = BasicBlock::Create(Ctx, "partword.cmpxchg.loop", F, FailureBB);

// The split call above "helpfully" added a branch at the end of BB
// (to the wrong place).
std::prev(BB->end())->eraseFromParent();
Builder.SetInsertPoint(BB);

PartwordMaskValues PMV =
    createMaskInstrs(Builder, CI, CI->getCompareOperand()->getType(), Addr,
                     CI->getAlign(), TLI->getMinCmpXchgSizeInBits() / 8);

// Shift the incoming values over, into the right location in the word.
Value *NewVal_Shifted =
    Builder.CreateShl(Builder.CreateZExt(NewVal, PMV.WordType), PMV.ShiftAmt);
Value *Cmp_Shifted =
    Builder.CreateShl(Builder.CreateZExt(Cmp, PMV.WordType), PMV.ShiftAmt);

// Load the entire current word, and mask into place the expected and new
// values
LoadInst *InitLoaded = Builder.CreateLoad(PMV.WordType, PMV.AlignedAddr);
InitLoaded->setVolatile(CI->isVolatile());
Value *InitLoaded_MaskOut = Builder.CreateAnd(InitLoaded, PMV.Inv_Mask);
Builder.CreateBr(LoopBB);

// partword.cmpxchg.loop:
Builder.SetInsertPoint(LoopBB);
PHINode *Loaded_MaskOut = Builder.CreatePHI(PMV.WordType, 2);
Loaded_MaskOut->addIncoming(InitLoaded_MaskOut, BB);

// Mask/Or the expected and new values into place in the loaded word.
Value *FullWord_NewVal = Builder.CreateOr(Loaded_MaskOut, NewVal_Shifted);
Value *FullWord_Cmp = Builder.CreateOr(Loaded_MaskOut, Cmp_Shifted);
AtomicCmpXchgInst *NewCI = Builder.CreateAtomicCmpXchg(
    PMV.AlignedAddr, FullWord_Cmp, FullWord_NewVal, PMV.AlignedAddrAlignment,
    CI->getSuccessOrdering(), CI->getFailureOrdering(), CI->getSyncScopeID());
NewCI->setVolatile(CI->isVolatile());
// When we're building a strong cmpxchg, we need a loop, so you
// might think we could use a weak cmpxchg inside. But, using strong
// allows the below comparison for ShouldContinue, and we're
// expecting the underlying cmpxchg to be a machine instruction,
// which is strong anyways.
NewCI->setWeak(CI->isWeak());

Value *OldVal = Builder.CreateExtractValue(NewCI, 0);
Value *Success = Builder.CreateExtractValue(NewCI, 1);

if (CI->isWeak())
  Builder.CreateBr(EndBB);
else
  Builder.CreateCondBr(Success, EndBB, FailureBB);

// partword.cmpxchg.failure:
Builder.SetInsertPoint(FailureBB);
// Upon failure, verify that the masked-out part of the loaded value
// has been modified.  If it didn't, abort the cmpxchg, since the
// masked-in part must've.
Value *OldVal_MaskOut = Builder.CreateAnd(OldVal, PMV.Inv_Mask);
Value *ShouldContinue = Builder.CreateICmpNE(Loaded_MaskOut, OldVal_MaskOut);
Builder.CreateCondBr(ShouldContinue, LoopBB, EndBB);

// Add the second value to the phi from above
Loaded_MaskOut->addIncoming(OldVal_MaskOut, FailureBB);

// partword.cmpxchg.end:
Builder.SetInsertPoint(CI);

Value *FinalOldVal = extractMaskedValue(Builder, OldVal, PMV);
Value *Res = UndefValue::get(CI->getType());
Res = Builder.CreateInsertValue(Res, FinalOldVal, 0);
Res = Builder.CreateInsertValue(Res, Success, 1);

CI->replaceAllUsesWith(Res);
CI->eraseFromParent();
return true;
1003}

1005void AtomicExpand::expandAtomicOpToLLSC(
  Instruction *I, Type *ResultType, Value *Addr, Align AddrAlign,
  AtomicOrdering MemOpOrder,
  function_ref<Value *(IRBuilder<> &, Value *)> PerformOp) {
IRBuilder<> Builder(I);
Value *Loaded = insertRMWLLSCLoop(Builder, ResultType, Addr, AddrAlign,
                                  MemOpOrder, PerformOp);

I->replaceAllUsesWith(Loaded);
I->eraseFromParent();
1015}

1017void AtomicExpand::expandAtomicRMWToMaskedIntrinsic(AtomicRMWInst *AI) {
IRBuilder<> Builder(AI);

PartwordMaskValues PMV =
    createMaskInstrs(Builder, AI, AI->getType(), AI->getPointerOperand(),
                     AI->getAlign(), TLI->getMinCmpXchgSizeInBits() / 8);

// The value operand must be sign-extended for signed min/max so that the
// target's signed comparison instructions can be used. Otherwise, just
// zero-ext.
Instruction::CastOps CastOp = Instruction::ZExt;
AtomicRMWInst::BinOp RMWOp = AI->getOperation();
if (RMWOp == AtomicRMWInst::Max || RMWOp == AtomicRMWInst::Min)
  CastOp = Instruction::SExt;

Value *ValOperand_Shifted = Builder.CreateShl(
    Builder.CreateCast(CastOp, AI->getValOperand(), PMV.WordType),
    PMV.ShiftAmt, "ValOperand_Shifted");
Value *OldResult = TLI->emitMaskedAtomicRMWIntrinsic(
    Builder, AI, PMV.AlignedAddr, ValOperand_Shifted, PMV.Mask, PMV.ShiftAmt,
    AI->getOrdering());
Value *FinalOldResult = extractMaskedValue(Builder, OldResult, PMV);
AI->replaceAllUsesWith(FinalOldResult);
AI->eraseFromParent();
1041}

1043void AtomicExpand::expandAtomicCmpXchgToMaskedIntrinsic(AtomicCmpXchgInst *CI) {
IRBuilder<> Builder(CI);

PartwordMaskValues PMV = createMaskInstrs(
    Builder, CI, CI->getCompareOperand()->getType(), CI->getPointerOperand(),
    CI->getAlign(), TLI->getMinCmpXchgSizeInBits() / 8);

Value *CmpVal_Shifted = Builder.CreateShl(
    Builder.CreateZExt(CI->getCompareOperand(), PMV.WordType), PMV.ShiftAmt,
    "CmpVal_Shifted");
Value *NewVal_Shifted = Builder.CreateShl(
    Builder.CreateZExt(CI->getNewValOperand(), PMV.WordType), PMV.ShiftAmt,
    "NewVal_Shifted");
Value *OldVal = TLI->emitMaskedAtomicCmpXchgIntrinsic(
    Builder, CI, PMV.AlignedAddr, CmpVal_Shifted, NewVal_Shifted, PMV.Mask,
    CI->getMergedOrdering());
Value *FinalOldVal = extractMaskedValue(Builder, OldVal, PMV);
Value *Res = UndefValue::get(CI->getType());
Res = Builder.CreateInsertValue(Res, FinalOldVal, 0);
Value *Success = Builder.CreateICmpEQ(
    CmpVal_Shifted, Builder.CreateAnd(OldVal, PMV.Mask), "Success");
Res = Builder.CreateInsertValue(Res, Success, 1);

CI->replaceAllUsesWith(Res);
CI->eraseFromParent();
1068}

1070Value *AtomicExpand::insertRMWLLSCLoop(
  IRBuilder<> &Builder, Type *ResultTy, Value *Addr, Align AddrAlign,
  AtomicOrdering MemOpOrder,
  function_ref<Value *(IRBuilder<> &, Value *)> PerformOp) {
LLVMContext &Ctx = Builder.getContext();
BasicBlock *BB = Builder.GetInsertBlock();
Function *F = BB->getParent();

assert(AddrAlign >=((void)0)
           F->getParent()->getDataLayout().getTypeStoreSize(ResultTy) &&((void)0)
       "Expected at least natural alignment at this point.")((void)0);

// Given: atomicrmw some_op iN* %addr, iN %incr ordering
//
// The standard expansion we produce is:
//     [...]
// atomicrmw.start:
//     %loaded = @load.linked(%addr)
//     %new = some_op iN %loaded, %incr
//     %stored = @store_conditional(%new, %addr)
//     %try_again = icmp i32 ne %stored, 0
//     br i1 %try_again, label %loop, label %atomicrmw.end
// atomicrmw.end:
//     [...]
BasicBlock *ExitBB =
    BB->splitBasicBlock(Builder.GetInsertPoint(), "atomicrmw.end");
BasicBlock *LoopBB =  BasicBlock::Create(Ctx, "atomicrmw.start", F, ExitBB);

// The split call above "helpfully" added a branch at the end of BB (to the
// wrong place).
std::prev(BB->end())->eraseFromParent();
Builder.SetInsertPoint(BB);
Builder.CreateBr(LoopBB);

// Start the main loop block now that we've taken care of the preliminaries.
Builder.SetInsertPoint(LoopBB);
Value *Loaded = TLI->emitLoadLinked(Builder, ResultTy, Addr, MemOpOrder);

Value *NewVal = PerformOp(Builder, Loaded);

Value *StoreSuccess =
    TLI->emitStoreConditional(Builder, NewVal, Addr, MemOpOrder);
Value *TryAgain = Builder.CreateICmpNE(
    StoreSuccess, ConstantInt::get(IntegerType::get(Ctx, 32), 0), "tryagain");
Builder.CreateCondBr(TryAgain, LoopBB, ExitBB);

Builder.SetInsertPoint(ExitBB, ExitBB->begin());
return Loaded;
1118}

1120/// Convert an atomic cmpxchg of a non-integral type to an integer cmpxchg of
1121/// the equivalent bitwidth.  We used to not support pointer cmpxchg in the
1122/// IR.  As a migration step, we convert back to what use to be the standard
1123/// way to represent a pointer cmpxchg so that we can update backends one by
1124/// one.
1125AtomicCmpXchgInst *AtomicExpand::convertCmpXchgToIntegerType(AtomicCmpXchgInst *CI) {
auto *M = CI->getModule();
Type *NewTy = getCorrespondingIntegerType(CI->getCompareOperand()->getType(),
                                          M->getDataLayout());

IRBuilder<> Builder(CI);

Value *Addr = CI->getPointerOperand();
Type *PT = PointerType::get(NewTy,
                            Addr->getType()->getPointerAddressSpace());
Value *NewAddr = Builder.CreateBitCast(Addr, PT);

Value *NewCmp = Builder.CreatePtrToInt(CI->getCompareOperand(), NewTy);
Value *NewNewVal = Builder.CreatePtrToInt(CI->getNewValOperand(), NewTy);

auto *NewCI = Builder.CreateAtomicCmpXchg(
    NewAddr, NewCmp, NewNewVal, CI->getAlign(), CI->getSuccessOrdering(),
    CI->getFailureOrdering(), CI->getSyncScopeID());
NewCI->setVolatile(CI->isVolatile());
NewCI->setWeak(CI->isWeak());
LLVM_DEBUG(dbgs() << "Replaced " << *CI << " with " << *NewCI << "\n")do { } while (false);

Value *OldVal = Builder.CreateExtractValue(NewCI, 0);
Value *Succ = Builder.CreateExtractValue(NewCI, 1);

OldVal = Builder.CreateIntToPtr(OldVal, CI->getCompareOperand()->getType());

Value *Res = UndefValue::get(CI->getType());
Res = Builder.CreateInsertValue(Res, OldVal, 0);
Res = Builder.CreateInsertValue(Res, Succ, 1);

CI->replaceAllUsesWith(Res);
CI->eraseFromParent();
return NewCI;
1159}

1161bool AtomicExpand::expandAtomicCmpXchg(AtomicCmpXchgInst *CI) {
AtomicOrdering SuccessOrder = CI->getSuccessOrdering();
AtomicOrdering FailureOrder = CI->getFailureOrdering();
Value *Addr = CI->getPointerOperand();
BasicBlock *BB = CI->getParent();
Function *F = BB->getParent();
LLVMContext &Ctx = F->getContext();
// If shouldInsertFencesForAtomic() returns true, then the target does not
// want to deal with memory orders, and emitLeading/TrailingFence should take
// care of everything. Otherwise, emitLeading/TrailingFence are no-op and we
// should preserve the ordering.
bool ShouldInsertFencesForAtomic = TLI->shouldInsertFencesForAtomic(CI);
AtomicOrdering MemOpOrder = ShouldInsertFencesForAtomic
                                ? AtomicOrdering::Monotonic
                                : CI->getMergedOrdering();

// In implementations which use a barrier to achieve release semantics, we can
// delay emitting this barrier until we know a store is actually going to be
// attempted. The cost of this delay is that we need 2 copies of the block
// emitting the load-linked, affecting code size.
//
// Ideally, this logic would be unconditional except for the minsize check
// since in other cases the extra blocks naturally collapse down to the
// minimal loop. Unfortunately, this puts too much stress on later
// optimisations so we avoid emitting the extra logic in those cases too.
bool HasReleasedLoadBB = !CI->isWeak() && ShouldInsertFencesForAtomic &&
                         SuccessOrder != AtomicOrdering::Monotonic &&
                         SuccessOrder != AtomicOrdering::Acquire &&
                         !F->hasMinSize();

// There's no overhead for sinking the release barrier in a weak cmpxchg, so
// do it even on minsize.
bool UseUnconditionalReleaseBarrier = F->hasMinSize() && !CI->isWeak();

// Given: cmpxchg some_op iN* %addr, iN %desired, iN %new success_ord fail_ord
//
// The full expansion we produce is:
//     [...]
// %aligned.addr = ...
// cmpxchg.start:
//     %unreleasedload = @load.linked(%aligned.addr)
//     %unreleasedload.extract = extract value from %unreleasedload
//     %should_store = icmp eq %unreleasedload.extract, %desired
//     br i1 %should_store, label %cmpxchg.releasingstore,
//                          label %cmpxchg.nostore
// cmpxchg.releasingstore:
//     fence?
//     br label cmpxchg.trystore
// cmpxchg.trystore:
//     %loaded.trystore = phi [%unreleasedload, %cmpxchg.releasingstore],
//                            [%releasedload, %cmpxchg.releasedload]
//     %updated.new = insert %new into %loaded.trystore
//     %stored = @store_conditional(%updated.new, %aligned.addr)
//     %success = icmp eq i32 %stored, 0
//     br i1 %success, label %cmpxchg.success,
//                     label %cmpxchg.releasedload/%cmpxchg.failure
// cmpxchg.releasedload:
//     %releasedload = @load.linked(%aligned.addr)
//     %releasedload.extract = extract value from %releasedload
//     %should_store = icmp eq %releasedload.extract, %desired
//     br i1 %should_store, label %cmpxchg.trystore,
//                          label %cmpxchg.failure
// cmpxchg.success:
//     fence?
//     br label %cmpxchg.end
// cmpxchg.nostore:
//     %loaded.nostore = phi [%unreleasedload, %cmpxchg.start],
//                           [%releasedload,
//                               %cmpxchg.releasedload/%cmpxchg.trystore]
//     @load_linked_fail_balance()?
//     br label %cmpxchg.failure
// cmpxchg.failure:
//     fence?
//     br label %cmpxchg.end
// cmpxchg.end:
//     %loaded.exit = phi [%loaded.nostore, %cmpxchg.failure],
//                        [%loaded.trystore, %cmpxchg.trystore]
//     %success = phi i1 [true, %cmpxchg.success], [false, %cmpxchg.failure]
//     %loaded = extract value from %loaded.exit
//     %restmp = insertvalue { iN, i1 } undef, iN %loaded, 0
//     %res = insertvalue { iN, i1 } %restmp, i1 %success, 1
//     [...]
BasicBlock *ExitBB = BB->splitBasicBlock(CI->getIterator(), "cmpxchg.end");
auto FailureBB = BasicBlock::Create(Ctx, "cmpxchg.failure", F, ExitBB);
auto NoStoreBB = BasicBlock::Create(Ctx, "cmpxchg.nostore", F, FailureBB);
auto SuccessBB = BasicBlock::Create(Ctx, "cmpxchg.success", F, NoStoreBB);
auto ReleasedLoadBB =
    BasicBlock::Create(Ctx, "cmpxchg.releasedload", F, SuccessBB);
auto TryStoreBB =
    BasicBlock::Create(Ctx, "cmpxchg.trystore", F, ReleasedLoadBB);
auto ReleasingStoreBB =
    BasicBlock::Create(Ctx, "cmpxchg.fencedstore", F, TryStoreBB);
auto StartBB = BasicBlock::Create(Ctx, "cmpxchg.start", F, ReleasingStoreBB);

// This grabs the DebugLoc from CI
IRBuilder<> Builder(CI);

// The split call above "helpfully" added a branch at the end of BB (to the
// wrong place), but we might want a fence too. It's easiest to just remove
// the branch entirely.
std::prev(BB->end())->eraseFromParent();
Builder.SetInsertPoint(BB);
if (ShouldInsertFencesForAtomic && UseUnconditionalReleaseBarrier)
  TLI->emitLeadingFence(Builder, CI, SuccessOrder);

PartwordMaskValues PMV =
    createMaskInstrs(Builder, CI, CI->getCompareOperand()->getType(), Addr,
                     CI->getAlign(), TLI->getMinCmpXchgSizeInBits() / 8);
Builder.CreateBr(StartBB);

// Start the main loop block now that we've taken care of the preliminaries.
Builder.SetInsertPoint(StartBB);
Value *UnreleasedLoad =
    TLI->emitLoadLinked(Builder, PMV.WordType, PMV.AlignedAddr, MemOpOrder);
Value *UnreleasedLoadExtract =
    extractMaskedValue(Builder, UnreleasedLoad, PMV);
Value *ShouldStore = Builder.CreateICmpEQ(
    UnreleasedLoadExtract, CI->getCompareOperand(), "should_store");

// If the cmpxchg doesn't actually need any ordering when it fails, we can
// jump straight past that fence instruction (if it exists).
Builder.CreateCondBr(ShouldStore, ReleasingStoreBB, NoStoreBB);

Builder.SetInsertPoint(ReleasingStoreBB);
if (ShouldInsertFencesForAtomic && !UseUnconditionalReleaseBarrier)
  TLI->emitLeadingFence(Builder, CI, SuccessOrder);
Builder.CreateBr(TryStoreBB);

Builder.SetInsertPoint(TryStoreBB);
PHINode *LoadedTryStore =
    Builder.CreatePHI(PMV.WordType, 2, "loaded.trystore");
LoadedTryStore->addIncoming(UnreleasedLoad, ReleasingStoreBB);
Value *NewValueInsert =
    insertMaskedValue(Builder, LoadedTryStore, CI->getNewValOperand(), PMV);
Value *StoreSuccess =
    TLI->emitStoreConditional(Builder, NewValueInsert, PMV.AlignedAddr,
                              MemOpOrder);
StoreSuccess = Builder.CreateICmpEQ(
    StoreSuccess, ConstantInt::get(Type::getInt32Ty(Ctx), 0), "success");
BasicBlock *RetryBB = HasReleasedLoadBB ? ReleasedLoadBB : StartBB;
Builder.CreateCondBr(StoreSuccess, SuccessBB,
                     CI->isWeak() ? FailureBB : RetryBB);

Builder.SetInsertPoint(ReleasedLoadBB);
Value *SecondLoad;
if (HasReleasedLoadBB) {
  SecondLoad =
      TLI->emitLoadLinked(Builder, PMV.WordType, PMV.AlignedAddr, MemOpOrder);
  Value *SecondLoadExtract = extractMaskedValue(Builder, SecondLoad, PMV);
  ShouldStore = Builder.CreateICmpEQ(SecondLoadExtract,
                                     CI->getCompareOperand(), "should_store");

  // If the cmpxchg doesn't actually need any ordering when it fails, we can
  // jump straight past that fence instruction (if it exists).
  Builder.CreateCondBr(ShouldStore, TryStoreBB, NoStoreBB);
  // Update PHI node in TryStoreBB.
  LoadedTryStore->addIncoming(SecondLoad, ReleasedLoadBB);
} else
  Builder.CreateUnreachable();

// Make sure later instructions don't get reordered with a fence if
// necessary.
Builder.SetInsertPoint(SuccessBB);
if (ShouldInsertFencesForAtomic)
  TLI->emitTrailingFence(Builder, CI, SuccessOrder);
Builder.CreateBr(ExitBB);

Builder.SetInsertPoint(NoStoreBB);
PHINode *LoadedNoStore =
    Builder.CreatePHI(UnreleasedLoad->getType(), 2, "loaded.nostore");
LoadedNoStore->addIncoming(UnreleasedLoad, StartBB);
if (HasReleasedLoadBB)
  LoadedNoStore->addIncoming(SecondLoad, ReleasedLoadBB);

// In the failing case, where we don't execute the store-conditional, the
// target might want to balance out the load-linked with a dedicated
// instruction (e.g., on ARM, clearing the exclusive monitor).
TLI->emitAtomicCmpXchgNoStoreLLBalance(Builder);
Builder.CreateBr(FailureBB);

Builder.SetInsertPoint(FailureBB);
PHINode *LoadedFailure =
    Builder.CreatePHI(UnreleasedLoad->getType(), 2, "loaded.failure");
LoadedFailure->addIncoming(LoadedNoStore, NoStoreBB);
if (CI->isWeak())
  LoadedFailure->addIncoming(LoadedTryStore, TryStoreBB);
if (ShouldInsertFencesForAtomic)
  TLI->emitTrailingFence(Builder, CI, FailureOrder);
Builder.CreateBr(ExitBB);

// Finally, we have control-flow based knowledge of whether the cmpxchg
// succeeded or not. We expose this to later passes by converting any
// subsequent "icmp eq/ne %loaded, %oldval" into a use of an appropriate
// PHI.
Builder.SetInsertPoint(ExitBB, ExitBB->begin());
PHINode *LoadedExit =
    Builder.CreatePHI(UnreleasedLoad->getType(), 2, "loaded.exit");
LoadedExit->addIncoming(LoadedTryStore, SuccessBB);
LoadedExit->addIncoming(LoadedFailure, FailureBB);
PHINode *Success = Builder.CreatePHI(Type::getInt1Ty(Ctx), 2, "success");
Success->addIncoming(ConstantInt::getTrue(Ctx), SuccessBB);
Success->addIncoming(ConstantInt::getFalse(Ctx), FailureBB);

// This is the "exit value" from the cmpxchg expansion. It may be of
// a type wider than the one in the cmpxchg instruction.
Value *LoadedFull = LoadedExit;

Builder.SetInsertPoint(ExitBB, std::next(Success->getIterator()));
Value *Loaded = extractMaskedValue(Builder, LoadedFull, PMV);

// Look for any users of the cmpxchg that are just comparing the loaded value
// against the desired one, and replace them with the CFG-derived version.
SmallVector<ExtractValueInst *, 2> PrunedInsts;
for (auto User : CI->users()) {
  ExtractValueInst *EV = dyn_cast<ExtractValueInst>(User);
  if (!EV)
    continue;

  assert(EV->getNumIndices() == 1 && EV->getIndices()[0] <= 1 &&((void)0)
         "weird extraction from { iN, i1 }")((void)0);

  if (EV->getIndices()[0] == 0)
    EV->replaceAllUsesWith(Loaded);
  else
    EV->replaceAllUsesWith(Success);

  PrunedInsts.push_back(EV);
}

// We can remove the instructions now we're no longer iterating through them.
for (auto EV : PrunedInsts)
  EV->eraseFromParent();

if (!CI->use_empty()) {
  // Some use of the full struct return that we don't understand has happened,
  // so we've got to reconstruct it properly.
  Value *Res;
  Res = Builder.CreateInsertValue(UndefValue::get(CI->getType()), Loaded, 0);
  Res = Builder.CreateInsertValue(Res, Success, 1);

  CI->replaceAllUsesWith(Res);
}

CI->eraseFromParent();
return true;
1406}

1408bool AtomicExpand::isIdempotentRMW(AtomicRMWInst* RMWI) {
auto C = dyn_cast<ConstantInt>(RMWI->getValOperand());
if(!C)
  return false;

AtomicRMWInst::BinOp Op = RMWI->getOperation();
switch(Op) {
  case AtomicRMWInst::Add:
  case AtomicRMWInst::Sub:
  case AtomicRMWInst::Or:
  case AtomicRMWInst::Xor:
    return C->isZero();
  case AtomicRMWInst::And:
    return C->isMinusOne();
  // FIXME: we could also treat Min/Max/UMin/UMax by the INT_MIN/INT_MAX/...
  default:
    return false;
}
1426}

1428bool AtomicExpand::simplifyIdempotentRMW(AtomicRMWInst* RMWI) {
if (auto ResultingLoad = TLI->lowerIdempotentRMWIntoFencedLoad(RMWI)) {
  tryExpandAtomicLoad(ResultingLoad);
  return true;
}
return false;
1434}

1436Value *AtomicExpand::insertRMWCmpXchgLoop(
  IRBuilder<> &Builder, Type *ResultTy, Value *Addr, Align AddrAlign,
  AtomicOrdering MemOpOrder, SyncScope::ID SSID,
  function_ref<Value *(IRBuilder<> &, Value *)> PerformOp,
  CreateCmpXchgInstFun CreateCmpXchg) {
LLVMContext &Ctx = Builder.getContext();
BasicBlock *BB = Builder.GetInsertBlock();
Function *F = BB->getParent();

// Given: atomicrmw some_op iN* %addr, iN %incr ordering
//
// The standard expansion we produce is:
//     [...]
//     %init_loaded = load atomic iN* %addr
//     br label %loop
// loop:
//     %loaded = phi iN [ %init_loaded, %entry ], [ %new_loaded, %loop ]
//     %new = some_op iN %loaded, %incr
//     %pair = cmpxchg iN* %addr, iN %loaded, iN %new
//     %new_loaded = extractvalue { iN, i1 } %pair, 0
//     %success = extractvalue { iN, i1 } %pair, 1
//     br i1 %success, label %atomicrmw.end, label %loop
// atomicrmw.end:
//     [...]
BasicBlock *ExitBB =
    BB->splitBasicBlock(Builder.GetInsertPoint(), "atomicrmw.end");
BasicBlock *LoopBB = BasicBlock::Create(Ctx, "atomicrmw.start", F, ExitBB);

// The split call above "helpfully" added a branch at the end of BB (to the
// wrong place), but we want a load. It's easiest to just remove
// the branch entirely.
std::prev(BB->end())->eraseFromParent();
Builder.SetInsertPoint(BB);
LoadInst *InitLoaded = Builder.CreateAlignedLoad(ResultTy, Addr, AddrAlign);
Builder.CreateBr(LoopBB);

// Start the main loop block now that we've taken care of the preliminaries.
Builder.SetInsertPoint(LoopBB);
PHINode *Loaded = Builder.CreatePHI(ResultTy, 2, "loaded");
Loaded->addIncoming(InitLoaded, BB);

Value *NewVal = PerformOp(Builder, Loaded);

Value *NewLoaded = nullptr;
Value *Success = nullptr;

CreateCmpXchg(Builder, Addr, Loaded, NewVal, AddrAlign,
23
←
Calling 'function_ref::operator()'→
              MemOpOrder == AtomicOrdering::Unordered
21
←
Assuming 'MemOpOrder' is not equal to Unordered→
22
←
'?' condition is false→
                  ? AtomicOrdering::Monotonic
                  : MemOpOrder,
              SSID, Success, NewLoaded);
assert(Success && NewLoaded)((void)0);

Loaded->addIncoming(NewLoaded, LoopBB);

Builder.CreateCondBr(Success, ExitBB, LoopBB);

Builder.SetInsertPoint(ExitBB, ExitBB->begin());
return NewLoaded;
1495}

1497bool AtomicExpand::tryExpandAtomicCmpXchg(AtomicCmpXchgInst *CI) {
unsigned MinCASSize = TLI->getMinCmpXchgSizeInBits() / 8;
unsigned ValueSize = getAtomicOpSize(CI);

switch (TLI->shouldExpandAtomicCmpXchgInIR(CI)) {
default:
  llvm_unreachable("Unhandled case in tryExpandAtomicCmpXchg")__builtin_unreachable();
case TargetLoweringBase::AtomicExpansionKind::None:
  if (ValueSize < MinCASSize)
    return expandPartwordCmpXchg(CI);
  return false;
case TargetLoweringBase::AtomicExpansionKind::LLSC: {
  return expandAtomicCmpXchg(CI);
}
case TargetLoweringBase::AtomicExpansionKind::MaskedIntrinsic:
  expandAtomicCmpXchgToMaskedIntrinsic(CI);
  return true;
}
1515}

1517// Note: This function is exposed externally by AtomicExpandUtils.h
1518bool llvm::expandAtomicRMWToCmpXchg(AtomicRMWInst *AI,
                                  CreateCmpXchgInstFun CreateCmpXchg) {
IRBuilder<> Builder(AI);
Value *Loaded = AtomicExpand::insertRMWCmpXchgLoop(
20
←
Calling 'AtomicExpand::insertRMWCmpXchgLoop'→
    Builder, AI->getType(), AI->getPointerOperand(), AI->getAlign(),
    AI->getOrdering(), AI->getSyncScopeID(),
    [&](IRBuilder<> &Builder, Value *Loaded) {
      return performAtomicOp(AI->getOperation(), Builder, Loaded,
                             AI->getValOperand());
    },
    CreateCmpXchg);

AI->replaceAllUsesWith(Loaded);
AI->eraseFromParent();
return true;
1533}

1535// In order to use one of the sized library calls such as
1536// __atomic_fetch_add_4, the alignment must be sufficient, the size
1537// must be one of the potentially-specialized sizes, and the value
1538// type must actually exist in C on the target (otherwise, the
1539// function wouldn't actually be defined.)
1540static bool canUseSizedAtomicCall(unsigned Size, Align Alignment,
                                const DataLayout &DL) {
// TODO: "LargestSize" is an approximation for "largest type that
// you can express in C". It seems to be the case that int128 is
// supported on all 64-bit platforms, otherwise only up to 64-bit
// integers are supported. If we get this wrong, then we'll try to
// call a sized libcall that doesn't actually exist. There should
// really be some more reliable way in LLVM of determining integer
// sizes which are valid in the target's C ABI...
unsigned LargestSize = DL.getLargestLegalIntTypeSizeInBits() >= 64 ? 16 : 8;
return Alignment >= Size &&
       (Size == 1 || Size == 2 || Size == 4 || Size == 8 || Size == 16) &&
       Size <= LargestSize;
1553}

1555void AtomicExpand::expandAtomicLoadToLibcall(LoadInst *I) {
static const RTLIB::Libcall Libcalls[6] = {
    RTLIB::ATOMIC_LOAD,   RTLIB::ATOMIC_LOAD_1, RTLIB::ATOMIC_LOAD_2,
    RTLIB::ATOMIC_LOAD_4, RTLIB::ATOMIC_LOAD_8, RTLIB::ATOMIC_LOAD_16};
unsigned Size = getAtomicOpSize(I);

bool expanded = expandAtomicOpToLibcall(
    I, Size, I->getAlign(), I->getPointerOperand(), nullptr, nullptr,
    I->getOrdering(), AtomicOrdering::NotAtomic, Libcalls);
if (!expanded)
  report_fatal_error("expandAtomicOpToLibcall shouldn't fail for Load");
1566}

1568void AtomicExpand::expandAtomicStoreToLibcall(StoreInst *I) {
static const RTLIB::Libcall Libcalls[6] = {
    RTLIB::ATOMIC_STORE,   RTLIB::ATOMIC_STORE_1, RTLIB::ATOMIC_STORE_2,
    RTLIB::ATOMIC_STORE_4, RTLIB::ATOMIC_STORE_8, RTLIB::ATOMIC_STORE_16};
unsigned Size = getAtomicOpSize(I);

bool expanded = expandAtomicOpToLibcall(
    I, Size, I->getAlign(), I->getPointerOperand(), I->getValueOperand(),
    nullptr, I->getOrdering(), AtomicOrdering::NotAtomic, Libcalls);
if (!expanded)
  report_fatal_error("expandAtomicOpToLibcall shouldn't fail for Store");
1579}

1581void AtomicExpand::expandAtomicCASToLibcall(AtomicCmpXchgInst *I) {
static const RTLIB::Libcall Libcalls[6] = {
    RTLIB::ATOMIC_COMPARE_EXCHANGE,   RTLIB::ATOMIC_COMPARE_EXCHANGE_1,
    RTLIB::ATOMIC_COMPARE_EXCHANGE_2, RTLIB::ATOMIC_COMPARE_EXCHANGE_4,
    RTLIB::ATOMIC_COMPARE_EXCHANGE_8, RTLIB::ATOMIC_COMPARE_EXCHANGE_16};
unsigned Size = getAtomicOpSize(I);

bool expanded = expandAtomicOpToLibcall(
27
←
Calling 'AtomicExpand::expandAtomicOpToLibcall'→
    I, Size, I->getAlign(), I->getPointerOperand(), I->getNewValOperand(),
    I->getCompareOperand(), I->getSuccessOrdering(), I->getFailureOrdering(),
    Libcalls);
if (!expanded)
  report_fatal_error("expandAtomicOpToLibcall shouldn't fail for CAS");
1594}

1596static ArrayRef<RTLIB::Libcall> GetRMWLibcall(AtomicRMWInst::BinOp Op) {
static const RTLIB::Libcall LibcallsXchg[6] = {
    RTLIB::ATOMIC_EXCHANGE,   RTLIB::ATOMIC_EXCHANGE_1,
    RTLIB::ATOMIC_EXCHANGE_2, RTLIB::ATOMIC_EXCHANGE_4,
    RTLIB::ATOMIC_EXCHANGE_8, RTLIB::ATOMIC_EXCHANGE_16};
static const RTLIB::Libcall LibcallsAdd[6] = {
    RTLIB::UNKNOWN_LIBCALL,    RTLIB::ATOMIC_FETCH_ADD_1,
    RTLIB::ATOMIC_FETCH_ADD_2, RTLIB::ATOMIC_FETCH_ADD_4,
    RTLIB::ATOMIC_FETCH_ADD_8, RTLIB::ATOMIC_FETCH_ADD_16};
static const RTLIB::Libcall LibcallsSub[6] = {
    RTLIB::UNKNOWN_LIBCALL,    RTLIB::ATOMIC_FETCH_SUB_1,
    RTLIB::ATOMIC_FETCH_SUB_2, RTLIB::ATOMIC_FETCH_SUB_4,
    RTLIB::ATOMIC_FETCH_SUB_8, RTLIB::ATOMIC_FETCH_SUB_16};
static const RTLIB::Libcall LibcallsAnd[6] = {
    RTLIB::UNKNOWN_LIBCALL,    RTLIB::ATOMIC_FETCH_AND_1,
    RTLIB::ATOMIC_FETCH_AND_2, RTLIB::ATOMIC_FETCH_AND_4,
    RTLIB::ATOMIC_FETCH_AND_8, RTLIB::ATOMIC_FETCH_AND_16};
static const RTLIB::Libcall LibcallsOr[6] = {
    RTLIB::UNKNOWN_LIBCALL,   RTLIB::ATOMIC_FETCH_OR_1,
    RTLIB::ATOMIC_FETCH_OR_2, RTLIB::ATOMIC_FETCH_OR_4,
    RTLIB::ATOMIC_FETCH_OR_8, RTLIB::ATOMIC_FETCH_OR_16};
static const RTLIB::Libcall LibcallsXor[6] = {
    RTLIB::UNKNOWN_LIBCALL,    RTLIB::ATOMIC_FETCH_XOR_1,
    RTLIB::ATOMIC_FETCH_XOR_2, RTLIB::ATOMIC_FETCH_XOR_4,
    RTLIB::ATOMIC_FETCH_XOR_8, RTLIB::ATOMIC_FETCH_XOR_16};
static const RTLIB::Libcall LibcallsNand[6] = {
    RTLIB::UNKNOWN_LIBCALL,     RTLIB::ATOMIC_FETCH_NAND_1,
    RTLIB::ATOMIC_FETCH_NAND_2, RTLIB::ATOMIC_FETCH_NAND_4,
    RTLIB::ATOMIC_FETCH_NAND_8, RTLIB::ATOMIC_FETCH_NAND_16};

switch (Op) {
case AtomicRMWInst::BAD_BINOP:
  llvm_unreachable("Should not have BAD_BINOP.")__builtin_unreachable();
case AtomicRMWInst::Xchg:
  return makeArrayRef(LibcallsXchg);
case AtomicRMWInst::Add:
  return makeArrayRef(LibcallsAdd);
case AtomicRMWInst::Sub:
  return makeArrayRef(LibcallsSub);
case AtomicRMWInst::And:
  return makeArrayRef(LibcallsAnd);
case AtomicRMWInst::Or:
  return makeArrayRef(LibcallsOr);
case AtomicRMWInst::Xor:
  return makeArrayRef(LibcallsXor);
case AtomicRMWInst::Nand:
  return makeArrayRef(LibcallsNand);
case AtomicRMWInst::Max:
case AtomicRMWInst::Min:
case AtomicRMWInst::UMax:
case AtomicRMWInst::UMin:
case AtomicRMWInst::FAdd:
case AtomicRMWInst::FSub:
  // No atomic libcalls are available for max/min/umax/umin.
  return {};
}
llvm_unreachable("Unexpected AtomicRMW operation.")__builtin_unreachable();
1653}

1655void AtomicExpand::expandAtomicRMWToLibcall(AtomicRMWInst *I) {
ArrayRef<RTLIB::Libcall> Libcalls = GetRMWLibcall(I->getOperation());

unsigned Size = getAtomicOpSize(I);

bool Success = false;
if (!Libcalls.empty())
16
←
Assuming the condition is false→
17
←
Taking false branch→
  Success = expandAtomicOpToLibcall(
      I, Size, I->getAlign(), I->getPointerOperand(), I->getValOperand(),
      nullptr, I->getOrdering(), AtomicOrdering::NotAtomic, Libcalls);

// The expansion failed: either there were no libcalls at all for
// the operation (min/max), or there were only size-specialized
// libcalls (add/sub/etc) and we needed a generic. So, expand to a
// CAS libcall, via a CAS loop, instead.
if (!Success17.1
'Success' is false
1
'Success' is false
) {
18
←
Taking true branch→
  expandAtomicRMWToCmpXchg(
19
←
Calling 'expandAtomicRMWToCmpXchg'→
      I, [this](IRBuilder<> &Builder, Value *Addr, Value *Loaded,
                Value *NewVal, Align Alignment, AtomicOrdering MemOpOrder,
                SyncScope::ID SSID, Value *&Success, Value *&NewLoaded) {
        // Create the CAS instruction normally...
        AtomicCmpXchgInst *Pair = Builder.CreateAtomicCmpXchg(
            Addr, Loaded, NewVal, Alignment, MemOpOrder,
            AtomicCmpXchgInst::getStrongestFailureOrdering(MemOpOrder), SSID);
        Success = Builder.CreateExtractValue(Pair, 1, "success");
        NewLoaded = Builder.CreateExtractValue(Pair, 0, "newloaded");

        // ...and then expand the CAS into a libcall.
        expandAtomicCASToLibcall(Pair);
26
←
Calling 'AtomicExpand::expandAtomicCASToLibcall'→
      });
}
1686}

1688// A helper routine for the above expandAtomic*ToLibcall functions.
1689//
1690// 'Libcalls' contains an array of enum values for the particular
1691// ATOMIC libcalls to be emitted. All of the other arguments besides
1692// 'I' are extracted from the Instruction subclass by the
1693// caller. Depending on the particular call, some will be null.
1694bool AtomicExpand::expandAtomicOpToLibcall(
  Instruction *I, unsigned Size, Align Alignment, Value *PointerOperand,
  Value *ValueOperand, Value *CASExpected, AtomicOrdering Ordering,
  AtomicOrdering Ordering2, ArrayRef<RTLIB::Libcall> Libcalls) {
assert(Libcalls.size() == 6)((void)0);

LLVMContext &Ctx = I->getContext();
Module *M = I->getModule();
const DataLayout &DL = M->getDataLayout();
IRBuilder<> Builder(I);
IRBuilder<> AllocaBuilder(&I->getFunction()->getEntryBlock().front());

bool UseSizedLibcall = canUseSizedAtomicCall(Size, Alignment, DL);
Type *SizedIntTy = Type::getIntNTy(Ctx, Size * 8);

const Align AllocaAlignment = DL.getPrefTypeAlign(SizedIntTy);

// TODO: the "order" argument type is "int", not int32. So
// getInt32Ty may be wrong if the arch uses e.g. 16-bit ints.
ConstantInt *SizeVal64 = ConstantInt::get(Type::getInt64Ty(Ctx), Size);
assert(Ordering != AtomicOrdering::NotAtomic && "expect atomic MO")((void)0);
Constant *OrderingVal =
    ConstantInt::get(Type::getInt32Ty(Ctx), (int)toCABI(Ordering));
Constant *Ordering2Val = nullptr;
if (CASExpected27.1
'CASExpected' is non-null
1
'CASExpected' is non-null
) {
28
←
Taking true branch→
  assert(Ordering2 != AtomicOrdering::NotAtomic && "expect atomic MO")((void)0);
  Ordering2Val =
      ConstantInt::get(Type::getInt32Ty(Ctx), (int)toCABI(Ordering2));
}
bool HasResult = I->getType() != Type::getVoidTy(Ctx);
29
←
Assuming the condition is false→

RTLIB::Libcall RTLibType;
30
←
'RTLibType' declared without an initial value→
if (UseSizedLibcall) {
31
←
Assuming 'UseSizedLibcall' is true→
32
←
Taking true branch→
  switch (Size) {
33
←
'Default' branch taken. Execution continues on line 1742→
  case 1: RTLibType = Libcalls[1]; break;
  case 2: RTLibType = Libcalls[2]; break;
  case 4: RTLibType = Libcalls[3]; break;
  case 8: RTLibType = Libcalls[4]; break;
  case 16: RTLibType = Libcalls[5]; break;
  }
} else if (Libcalls[0] != RTLIB::UNKNOWN_LIBCALL) {
  RTLibType = Libcalls[0];
} else {
  // Can't use sized function, and there's no generic for this
  // operation, so give up.
  return false;
}

if (!TLI->getLibcallName(RTLibType)) {
34
←
1st function call argument is an uninitialized value
  // This target does not implement the requested atomic libcall so give up.
  return false;
}

// Build up the function call. There's two kinds. First, the sized
// variants.  These calls are going to be one of the following (with
// N=1,2,4,8,16):
//  iN    __atomic_load_N(iN *ptr, int ordering)
//  void  __atomic_store_N(iN *ptr, iN val, int ordering)
//  iN    __atomic_{exchange|fetch_*}_N(iN *ptr, iN val, int ordering)
//  bool  __atomic_compare_exchange_N(iN *ptr, iN *expected, iN desired,
//                                    int success_order, int failure_order)
//
// Note that these functions can be used for non-integer atomic
// operations, the values just need to be bitcast to integers on the
// way in and out.
//
// And, then, the generic variants. They look like the following:
//  void  __atomic_load(size_t size, void *ptr, void *ret, int ordering)
//  void  __atomic_store(size_t size, void *ptr, void *val, int ordering)
//  void  __atomic_exchange(size_t size, void *ptr, void *val, void *ret,
//                          int ordering)
//  bool  __atomic_compare_exchange(size_t size, void *ptr, void *expected,
//                                  void *desired, int success_order,
//                                  int failure_order)
//
// The different signatures are built up depending on the
// 'UseSizedLibcall', 'CASExpected', 'ValueOperand', and 'HasResult'
// variables.

AllocaInst *AllocaCASExpected = nullptr;
Value *AllocaCASExpected_i8 = nullptr;
AllocaInst *AllocaValue = nullptr;
Value *AllocaValue_i8 = nullptr;
AllocaInst *AllocaResult = nullptr;
Value *AllocaResult_i8 = nullptr;

Type *ResultTy;
SmallVector<Value *, 6> Args;
AttributeList Attr;

// 'size' argument.
if (!UseSizedLibcall) {
  // Note, getIntPtrType is assumed equivalent to size_t.
  Args.push_back(ConstantInt::get(DL.getIntPtrType(Ctx), Size));
}

// 'ptr' argument.
// note: This assumes all address spaces share a common libfunc
// implementation and that addresses are convertable.  For systems without
// that property, we'd need to extend this mechanism to support AS-specific
// families of atomic intrinsics.
auto PtrTypeAS = PointerOperand->getType()->getPointerAddressSpace();
Value *PtrVal = Builder.CreateBitCast(PointerOperand,
                                      Type::getInt8PtrTy(Ctx, PtrTypeAS));
PtrVal = Builder.CreateAddrSpaceCast(PtrVal, Type::getInt8PtrTy(Ctx));
Args.push_back(PtrVal);

// 'expected' argument, if present.
if (CASExpected) {
  AllocaCASExpected = AllocaBuilder.CreateAlloca(CASExpected->getType());
  AllocaCASExpected->setAlignment(AllocaAlignment);
  unsigned AllocaAS =  AllocaCASExpected->getType()->getPointerAddressSpace();

  AllocaCASExpected_i8 =
    Builder.CreateBitCast(AllocaCASExpected,
                          Type::getInt8PtrTy(Ctx, AllocaAS));
  Builder.CreateLifetimeStart(AllocaCASExpected_i8, SizeVal64);
  Builder.CreateAlignedStore(CASExpected, AllocaCASExpected, AllocaAlignment);
  Args.push_back(AllocaCASExpected_i8);
}

// 'val' argument ('desired' for cas), if present.
if (ValueOperand) {
  if (UseSizedLibcall) {
    Value *IntValue =
        Builder.CreateBitOrPointerCast(ValueOperand, SizedIntTy);
    Args.push_back(IntValue);
  } else {
    AllocaValue = AllocaBuilder.CreateAlloca(ValueOperand->getType());
    AllocaValue->setAlignment(AllocaAlignment);
    AllocaValue_i8 =
        Builder.CreateBitCast(AllocaValue, Type::getInt8PtrTy(Ctx));
    Builder.CreateLifetimeStart(AllocaValue_i8, SizeVal64);
    Builder.CreateAlignedStore(ValueOperand, AllocaValue, AllocaAlignment);
    Args.push_back(AllocaValue_i8);
  }
}

// 'ret' argument.
if (!CASExpected && HasResult && !UseSizedLibcall) {
  AllocaResult = AllocaBuilder.CreateAlloca(I->getType());
  AllocaResult->setAlignment(AllocaAlignment);
  unsigned AllocaAS =  AllocaResult->getType()->getPointerAddressSpace();
  AllocaResult_i8 =
    Builder.CreateBitCast(AllocaResult, Type::getInt8PtrTy(Ctx, AllocaAS));
  Builder.CreateLifetimeStart(AllocaResult_i8, SizeVal64);
  Args.push_back(AllocaResult_i8);
}

// 'ordering' ('success_order' for cas) argument.
Args.push_back(OrderingVal);

// 'failure_order' argument, if present.
if (Ordering2Val)
  Args.push_back(Ordering2Val);

// Now, the return type.
if (CASExpected) {
  ResultTy = Type::getInt1Ty(Ctx);
  Attr = Attr.addAttribute(Ctx, AttributeList::ReturnIndex, Attribute::ZExt);
} else if (HasResult && UseSizedLibcall)
  ResultTy = SizedIntTy;
else
  ResultTy = Type::getVoidTy(Ctx);

// Done with setting up arguments and return types, create the call:
SmallVector<Type *, 6> ArgTys;
for (Value *Arg : Args)
  ArgTys.push_back(Arg->getType());
FunctionType *FnType = FunctionType::get(ResultTy, ArgTys, false);
FunctionCallee LibcallFn =
    M->getOrInsertFunction(TLI->getLibcallName(RTLibType), FnType, Attr);
CallInst *Call = Builder.CreateCall(LibcallFn, Args);
Call->setAttributes(Attr);
Value *Result = Call;

// And then, extract the results...
if (ValueOperand && !UseSizedLibcall)
  Builder.CreateLifetimeEnd(AllocaValue_i8, SizeVal64);

if (CASExpected) {
  // The final result from the CAS is {load of 'expected' alloca, bool result
  // from call}
  Type *FinalResultTy = I->getType();
  Value *V = UndefValue::get(FinalResultTy);
  Value *ExpectedOut = Builder.CreateAlignedLoad(
      CASExpected->getType(), AllocaCASExpected, AllocaAlignment);
  Builder.CreateLifetimeEnd(AllocaCASExpected_i8, SizeVal64);
  V = Builder.CreateInsertValue(V, ExpectedOut, 0);
  V = Builder.CreateInsertValue(V, Result, 1);
  I->replaceAllUsesWith(V);
} else if (HasResult) {
  Value *V;
  if (UseSizedLibcall)
    V = Builder.CreateBitOrPointerCast(Result, I->getType());
  else {
    V = Builder.CreateAlignedLoad(I->getType(), AllocaResult,
                                  AllocaAlignment);
    Builder.CreateLifetimeEnd(AllocaResult_i8, SizeVal64);
  }
  I->replaceAllUsesWith(V);
}
I->eraseFromParent();
return true;
1898}

←

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ADT/STLExtras.h

1//===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- 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 contains some templates that are useful if you are working with the
10// STL at all.
11//
12// No library is required when using these functions.
13//
14//===----------------------------------------------------------------------===//
15 
16#ifndef LLVM_ADT_STLEXTRAS_H
17#define LLVM_ADT_STLEXTRAS_H
18 
19#include "llvm/ADT/Optional.h"
20#include "llvm/ADT/STLForwardCompat.h"
21#include "llvm/ADT/iterator.h"
22#include "llvm/ADT/iterator_range.h"
23#include "llvm/Config/abi-breaking.h"
24#include "llvm/Support/ErrorHandling.h"
25#include <algorithm>
26#include <cassert>
27#include <cstddef>
28#include <cstdint>
29#include <cstdlib>
30#include <functional>
31#include <initializer_list>
32#include <iterator>
33#include <limits>
34#include <memory>
35#include <tuple>
36#include <type_traits>
37#include <utility>
38 
39#ifdef EXPENSIVE_CHECKS
40#include <random> // for std::mt19937
41#endif
42 
43namespace llvm {
44 
45// Only used by compiler if both template types are the same.  Useful when
46// using SFINAE to test for the existence of member functions.
47template <typename T, T> struct SameType;
48 
49namespace detail {
50 
51template <typename RangeT>
52using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
53 
54template <typename RangeT>
55using ValueOfRange = typename std::remove_reference<decltype(
56    *std::begin(std::declval<RangeT &>()))>::type;
57 
58} // end namespace detail
59 
60//===----------------------------------------------------------------------===//
61//     Extra additions to <type_traits>
62//===----------------------------------------------------------------------===//
63 
64template <typename T> struct make_const_ptr {
65  using type =
66      typename std::add_pointer<typename std::add_const<T>::type>::type;
67};
68 
69template <typename T> struct make_const_ref {
70  using type = typename std::add_lvalue_reference<
71      typename std::add_const<T>::type>::type;
72};
73 
74namespace detail {
75template <typename...> using void_t = void;
76template <class, template <class...> class Op, class... Args> struct detector {
77  using value_t = std::false_type;
78};
79template <template <class...> class Op, class... Args>
80struct detector<void_t<Op<Args...>>, Op, Args...> {
81  using value_t = std::true_type;
82};
83} // end namespace detail
84 
85/// Detects if a given trait holds for some set of arguments 'Args'.
86/// For example, the given trait could be used to detect if a given type
87/// has a copy assignment operator:
88///   template<class T>
89///   using has_copy_assign_t = decltype(std::declval<T&>()
90///                                                 = std::declval<const T&>());
91///   bool fooHasCopyAssign = is_detected<has_copy_assign_t, FooClass>::value;
92template <template <class...> class Op, class... Args>
93using is_detected = typename detail::detector<void, Op, Args...>::value_t;
94 
95namespace detail {
96template <typename Callable, typename... Args>
97using is_invocable =
98    decltype(std::declval<Callable &>()(std::declval<Args>()...));
99} // namespace detail
100 
101/// Check if a Callable type can be invoked with the given set of arg types.
102template <typename Callable, typename... Args>
103using is_invocable = is_detected<detail::is_invocable, Callable, Args...>;
104 
105/// This class provides various trait information about a callable object.
106///   * To access the number of arguments: Traits::num_args
107///   * To access the type of an argument: Traits::arg_t<Index>
108///   * To access the type of the result:  Traits::result_t
109template <typename T, bool isClass = std::is_class<T>::value>
110struct function_traits : public function_traits<decltype(&T::operator())> {};
111 
112/// Overload for class function types.
113template <typename ClassType, typename ReturnType, typename... Args>
114struct function_traits<ReturnType (ClassType::*)(Args...) const, false> {
115  /// The number of arguments to this function.
116  enum { num_args = sizeof...(Args) };
117 
118  /// The result type of this function.
119  using result_t = ReturnType;
120 
121  /// The type of an argument to this function.
122  template <size_t Index>
123  using arg_t = typename std::tuple_element<Index, std::tuple<Args...>>::type;
124};
125/// Overload for class function types.
126template <typename ClassType, typename ReturnType, typename... Args>
127struct function_traits<ReturnType (ClassType::*)(Args...), false>
128    : function_traits<ReturnType (ClassType::*)(Args...) const> {};
129/// Overload for non-class function types.
130template <typename ReturnType, typename... Args>
131struct function_traits<ReturnType (*)(Args...), false> {
132  /// The number of arguments to this function.
133  enum { num_args = sizeof...(Args) };
134 
135  /// The result type of this function.
136  using result_t = ReturnType;
137 
138  /// The type of an argument to this function.
139  template <size_t i>
140  using arg_t = typename std::tuple_element<i, std::tuple<Args...>>::type;
141};
142/// Overload for non-class function type references.
143template <typename ReturnType, typename... Args>
144struct function_traits<ReturnType (&)(Args...), false>
145    : public function_traits<ReturnType (*)(Args...)> {};
146 
147//===----------------------------------------------------------------------===//
148//     Extra additions to <functional>
149//===----------------------------------------------------------------------===//
150 
151template <class Ty> struct identity {
152  using argument_type = Ty;
153 
154  Ty &operator()(Ty &self) const {
155    return self;
156  }
157  const Ty &operator()(const Ty &self) const {
158    return self;
159  }
160};
161 
162/// An efficient, type-erasing, non-owning reference to a callable. This is
163/// intended for use as the type of a function parameter that is not used
164/// after the function in question returns.
165///
166/// This class does not own the callable, so it is not in general safe to store
167/// a function_ref.
168template<typename Fn> class function_ref;
169 
170template<typename Ret, typename ...Params>
171class function_ref<Ret(Params...)> {
172  Ret (*callback)(intptr_t callable, Params ...params) = nullptr;
173  intptr_t callable;
174 
175  template<typename Callable>
176  static Ret callback_fn(intptr_t callable, Params ...params) {
177    return (*reinterpret_cast<Callable*>(callable))(
25
←
Calling 'operator()'→
178        std::forward<Params>(params)...);
179  }
180 
181public:
182  function_ref() = default;
183  function_ref(std::nullptr_t) {}
184 
185  template <typename Callable>
186  function_ref(
187      Callable &&callable,
188      // This is not the copy-constructor.
189      std::enable_if_t<!std::is_same<remove_cvref_t<Callable>,
190                                     function_ref>::value> * = nullptr,
191      // Functor must be callable and return a suitable type.
192      std::enable_if_t<std::is_void<Ret>::value ||
193                       std::is_convertible<decltype(std::declval<Callable>()(
194                                               std::declval<Params>()...)),
195                                           Ret>::value> * = nullptr)
196      : callback(callback_fn<typename std::remove_reference<Callable>::type>),
197        callable(reinterpret_cast<intptr_t>(&callable)) {}
198 
199  Ret operator()(Params ...params) const {
200    return callback(callable, std::forward<Params>(params)...);
24
←
Calling 'function_ref::callback_fn'→
201  }
202 
203  explicit operator bool() const { return callback; }
204};
205 
206//===----------------------------------------------------------------------===//
207//     Extra additions to <iterator>
208//===----------------------------------------------------------------------===//
209 
210namespace adl_detail {
211 
212using std::begin;
213 
214template <typename ContainerTy>
215decltype(auto) adl_begin(ContainerTy &&container) {
216  return begin(std::forward<ContainerTy>(container));
217}
218 
219using std::end;
220 
221template <typename ContainerTy>
222decltype(auto) adl_end(ContainerTy &&container) {
223  return end(std::forward<ContainerTy>(container));
224}
225 
226using std::swap;
227 
228template <typename T>
229void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
230                                                       std::declval<T>()))) {
231  swap(std::forward<T>(lhs), std::forward<T>(rhs));
232}
233 
234} // end namespace adl_detail
235 
236template <typename ContainerTy>
237decltype(auto) adl_begin(ContainerTy &&container) {
238  return adl_detail::adl_begin(std::forward<ContainerTy>(container));
239}
240 
241template <typename ContainerTy>
242decltype(auto) adl_end(ContainerTy &&container) {
243  return adl_detail::adl_end(std::forward<ContainerTy>(container));
244}
245 
246template <typename T>
247void adl_swap(T &&lhs, T &&rhs) noexcept(
248    noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {
249  adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));
250}
251 
252/// Test whether \p RangeOrContainer is empty. Similar to C++17 std::empty.
253template <typename T>
254constexpr bool empty(const T &RangeOrContainer) {
255  return adl_begin(RangeOrContainer) == adl_end(RangeOrContainer);
256}
257 
258/// Returns true if the given container only contains a single element.
259template <typename ContainerTy> bool hasSingleElement(ContainerTy &&C) {
260  auto B = std::begin(C), E = std::end(C);
261  return B != E && std::next(B) == E;
262}
263 
264/// Return a range covering \p RangeOrContainer with the first N elements
265/// excluded.
266template <typename T> auto drop_begin(T &&RangeOrContainer, size_t N = 1) {
267  return make_range(std::next(adl_begin(RangeOrContainer), N),
268                    adl_end(RangeOrContainer));
269}
270 
271// mapped_iterator - This is a simple iterator adapter that causes a function to
272// be applied whenever operator* is invoked on the iterator.
273 
274template <typename ItTy, typename FuncTy,
275          typename FuncReturnTy =
276            decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
277class mapped_iterator
278    : public iterator_adaptor_base<
279             mapped_iterator<ItTy, FuncTy>, ItTy,
280             typename std::iterator_traits<ItTy>::iterator_category,
281             typename std::remove_reference<FuncReturnTy>::type> {
282public:
283  mapped_iterator(ItTy U, FuncTy F)
284    : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {}
285 
286  ItTy getCurrent() { return this->I; }
287 
288  FuncReturnTy operator*() const { return F(*this->I); }
289 
290private:
291  FuncTy F;
292};
293 
294// map_iterator - Provide a convenient way to create mapped_iterators, just like
295// make_pair is useful for creating pairs...
296template <class ItTy, class FuncTy>
297inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) {
298  return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
299}
300 
301template <class ContainerTy, class FuncTy>
302auto map_range(ContainerTy &&C, FuncTy F) {
303  return make_range(map_iterator(C.begin(), F), map_iterator(C.end(), F));
304}
305 
306/// Helper to determine if type T has a member called rbegin().
307template <typename Ty> class has_rbegin_impl {
308  using yes = char[1];
309  using no = char[2];
310 
311  template <typename Inner>
312  static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);
313 
314  template <typename>
315  static no& test(...);
316 
317public:
318  static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
319};
320 
321/// Metafunction to determine if T& or T has a member called rbegin().
322template <typename Ty>
323struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> {
324};
325 
326// Returns an iterator_range over the given container which iterates in reverse.
327// Note that the container must have rbegin()/rend() methods for this to work.
328template <typename ContainerTy>
329auto reverse(ContainerTy &&C,
330             std::enable_if_t<has_rbegin<ContainerTy>::value> * = nullptr) {
331  return make_range(C.rbegin(), C.rend());
332}
333 
334// Returns a std::reverse_iterator wrapped around the given iterator.
335template <typename IteratorTy>
336std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
337  return std::reverse_iterator<IteratorTy>(It);
338}
339 
340// Returns an iterator_range over the given container which iterates in reverse.
341// Note that the container must have begin()/end() methods which return
342// bidirectional iterators for this to work.
343template <typename ContainerTy>
344auto reverse(ContainerTy &&C,
345             std::enable_if_t<!has_rbegin<ContainerTy>::value> * = nullptr) {
346  return make_range(llvm::make_reverse_iterator(std::end(C)),
347                    llvm::make_reverse_iterator(std::begin(C)));
348}
349 
350/// An iterator adaptor that filters the elements of given inner iterators.
351///
352/// The predicate parameter should be a callable object that accepts the wrapped
353/// iterator's reference type and returns a bool. When incrementing or
354/// decrementing the iterator, it will call the predicate on each element and
355/// skip any where it returns false.
356///
357/// \code
358///   int A[] = { 1, 2, 3, 4 };
359///   auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
360///   // R contains { 1, 3 }.
361/// \endcode
362///
363/// Note: filter_iterator_base implements support for forward iteration.
364/// filter_iterator_impl exists to provide support for bidirectional iteration,
365/// conditional on whether the wrapped iterator supports it.
366template <typename WrappedIteratorT, typename PredicateT, typename IterTag>
367class filter_iterator_base
368    : public iterator_adaptor_base<
369          filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
370          WrappedIteratorT,
371          typename std::common_type<
372              IterTag, typename std::iterator_traits<
373                           WrappedIteratorT>::iterator_category>::type> {
374  using BaseT = iterator_adaptor_base<
375      filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
376      WrappedIteratorT,
377      typename std::common_type<
378          IterTag, typename std::iterator_traits<
379                       WrappedIteratorT>::iterator_category>::type>;
380 
381protected:
382  WrappedIteratorT End;
383  PredicateT Pred;
384 
385  void findNextValid() {
386    while (this->I != End && !Pred(*this->I))
387      BaseT::operator++();
388  }
389 
390  // Construct the iterator. The begin iterator needs to know where the end
391  // is, so that it can properly stop when it gets there. The end iterator only
392  // needs the predicate to support bidirectional iteration.
393  filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End,
394                       PredicateT Pred)
395      : BaseT(Begin), End(End), Pred(Pred) {
396    findNextValid();
397  }
398 
399public:
400  using BaseT::operator++;
401 
402  filter_iterator_base &operator++() {
403    BaseT::operator++();
404    findNextValid();
405    return *this;
406  }
407};
408 
409/// Specialization of filter_iterator_base for forward iteration only.
410template <typename WrappedIteratorT, typename PredicateT,
411          typename IterTag = std::forward_iterator_tag>
412class filter_iterator_impl
413    : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> {
414  using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>;
415 
416public:
417  filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
418                       PredicateT Pred)
419      : BaseT(Begin, End, Pred) {}
420};
421 
422/// Specialization of filter_iterator_base for bidirectional iteration.
423template <typename WrappedIteratorT, typename PredicateT>
424class filter_iterator_impl<WrappedIteratorT, PredicateT,
425                           std::bidirectional_iterator_tag>
426    : public filter_iterator_base<WrappedIteratorT, PredicateT,
427                                  std::bidirectional_iterator_tag> {
428  using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT,
429                                     std::bidirectional_iterator_tag>;
430  void findPrevValid() {
431    while (!this->Pred(*this->I))
432      BaseT::operator--();
433  }
434 
435public:
436  using BaseT::operator--;
437 
438  filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
439                       PredicateT Pred)
440      : BaseT(Begin, End, Pred) {}
441 
442  filter_iterator_impl &operator--() {
443    BaseT::operator--();
444    findPrevValid();
445    return *this;
446  }
447};
448 
449namespace detail {
450 
451template <bool is_bidirectional> struct fwd_or_bidi_tag_impl {
452  using type = std::forward_iterator_tag;
453};
454 
455template <> struct fwd_or_bidi_tag_impl<true> {
456  using type = std::bidirectional_iterator_tag;
457};
458 
459/// Helper which sets its type member to forward_iterator_tag if the category
460/// of \p IterT does not derive from bidirectional_iterator_tag, and to
461/// bidirectional_iterator_tag otherwise.
462template <typename IterT> struct fwd_or_bidi_tag {
463  using type = typename fwd_or_bidi_tag_impl<std::is_base_of<
464      std::bidirectional_iterator_tag,
465      typename std::iterator_traits<IterT>::iterator_category>::value>::type;
466};
467 
468} // namespace detail
469 
470/// Defines filter_iterator to a suitable specialization of
471/// filter_iterator_impl, based on the underlying iterator's category.
472template <typename WrappedIteratorT, typename PredicateT>
473using filter_iterator = filter_iterator_impl<
474    WrappedIteratorT, PredicateT,
475    typename detail::fwd_or_bidi_tag<WrappedIteratorT>::type>;
476 
477/// Convenience function that takes a range of elements and a predicate,
478/// and return a new filter_iterator range.
479///
480/// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the
481/// lifetime of that temporary is not kept by the returned range object, and the
482/// temporary is going to be dropped on the floor after the make_iterator_range
483/// full expression that contains this function call.
484template <typename RangeT, typename PredicateT>
485iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>>
486make_filter_range(RangeT &&Range, PredicateT Pred) {
487  using FilterIteratorT =
488      filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
489  return make_range(
490      FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
491                      std::end(std::forward<RangeT>(Range)), Pred),
492      FilterIteratorT(std::end(std::forward<RangeT>(Range)),
493                      std::end(std::forward<RangeT>(Range)), Pred));
494}
495 
496/// A pseudo-iterator adaptor that is designed to implement "early increment"
497/// style loops.
498///
499/// This is *not a normal iterator* and should almost never be used directly. It
500/// is intended primarily to be used with range based for loops and some range
501/// algorithms.
502///
503/// The iterator isn't quite an `OutputIterator` or an `InputIterator` but
504/// somewhere between them. The constraints of these iterators are:
505///
506/// - On construction or after being incremented, it is comparable and
507///   dereferencable. It is *not* incrementable.
508/// - After being dereferenced, it is neither comparable nor dereferencable, it
509///   is only incrementable.
510///
511/// This means you can only dereference the iterator once, and you can only
512/// increment it once between dereferences.
513template <typename WrappedIteratorT>
514class early_inc_iterator_impl
515    : public iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
516                                   WrappedIteratorT, std::input_iterator_tag> {
517  using BaseT =
518      iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
519                            WrappedIteratorT, std::input_iterator_tag>;
520 
521  using PointerT = typename std::iterator_traits<WrappedIteratorT>::pointer;
522 
523protected:
524#if LLVM_ENABLE_ABI_BREAKING_CHECKS0
525  bool IsEarlyIncremented = false;
526#endif
527 
528public:
529  early_inc_iterator_impl(WrappedIteratorT I) : BaseT(I) {}
530 
531  using BaseT::operator*;
532  decltype(*std::declval<WrappedIteratorT>()) operator*() {
533#if LLVM_ENABLE_ABI_BREAKING_CHECKS0
534    assert(!IsEarlyIncremented && "Cannot dereference twice!")((void)0);
535    IsEarlyIncremented = true;
536#endif
537    return *(this->I)++;
538  }
539 
540  using BaseT::operator++;
541  early_inc_iterator_impl &operator++() {
542#if LLVM_ENABLE_ABI_BREAKING_CHECKS0
543    assert(IsEarlyIncremented && "Cannot increment before dereferencing!")((void)0);
544    IsEarlyIncremented = false;
545#endif
546    return *this;
547  }
548 
549  friend bool operator==(const early_inc_iterator_impl &LHS,
550                         const early_inc_iterator_impl &RHS) {
551#if LLVM_ENABLE_ABI_BREAKING_CHECKS0
552    assert(!LHS.IsEarlyIncremented && "Cannot compare after dereferencing!")((void)0);
553#endif
554    return (const BaseT &)LHS == (const BaseT &)RHS;
555  }
556};
557 
558/// Make a range that does early increment to allow mutation of the underlying
559/// range without disrupting iteration.
560///
561/// The underlying iterator will be incremented immediately after it is
562/// dereferenced, allowing deletion of the current node or insertion of nodes to
563/// not disrupt iteration provided they do not invalidate the *next* iterator --
564/// the current iterator can be invalidated.
565///
566/// This requires a very exact pattern of use that is only really suitable to
567/// range based for loops and other range algorithms that explicitly guarantee
568/// to dereference exactly once each element, and to increment exactly once each
569/// element.
570template <typename RangeT>
571iterator_range<early_inc_iterator_impl<detail::IterOfRange<RangeT>>>
572make_early_inc_range(RangeT &&Range) {
573  using EarlyIncIteratorT =
574      early_inc_iterator_impl<detail::IterOfRange<RangeT>>;
575  return make_range(EarlyIncIteratorT(std::begin(std::forward<RangeT>(Range))),
576                    EarlyIncIteratorT(std::end(std::forward<RangeT>(Range))));
577}
578 
579// forward declarations required by zip_shortest/zip_first/zip_longest
580template <typename R, typename UnaryPredicate>
581bool all_of(R &&range, UnaryPredicate P);
582template <typename R, typename UnaryPredicate>
583bool any_of(R &&range, UnaryPredicate P);
584 
585namespace detail {
586 
587using std::declval;
588 
589// We have to alias this since inlining the actual type at the usage site
590// in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.
591template<typename... Iters> struct ZipTupleType {
592  using type = std::tuple<decltype(*declval<Iters>())...>;
593};
594 
595template <typename ZipType, typename... Iters>
596using zip_traits = iterator_facade_base<
597    ZipType, typename std::common_type<std::bidirectional_iterator_tag,
598                                       typename std::iterator_traits<
599                                           Iters>::iterator_category...>::type,
600    // ^ TODO: Implement random access methods.
601    typename ZipTupleType<Iters...>::type,
602    typename std::iterator_traits<typename std::tuple_element<
603        0, std::tuple<Iters...>>::type>::difference_type,
604    // ^ FIXME: This follows boost::make_zip_iterator's assumption that all
605    // inner iterators have the same difference_type. It would fail if, for
606    // instance, the second field's difference_type were non-numeric while the
607    // first is.
608    typename ZipTupleType<Iters...>::type *,
609    typename ZipTupleType<Iters...>::type>;
610 
611template <typename ZipType, typename... Iters>
612struct zip_common : public zip_traits<ZipType, Iters...> {
613  using Base = zip_traits<ZipType, Iters...>;
614  using value_type = typename Base::value_type;
615 
616  std::tuple<Iters...> iterators;
617 
618protected:
619  template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const {
620    return value_type(*std::get<Ns>(iterators)...);
621  }
622 
623  template <size_t... Ns>
624  decltype(iterators) tup_inc(std::index_sequence<Ns...>) const {
625    return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
626  }
627 
628  template <size_t... Ns>
629  decltype(iterators) tup_dec(std::index_sequence<Ns...>) const {
630    return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
631  }
632 
633public:
634  zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
635 
636  value_type operator*() { return deref(std::index_sequence_for<Iters...>{}); }
637 
638  const value_type operator*() const {
639    return deref(std::index_sequence_for<Iters...>{});
640  }
641 
642  ZipType &operator++() {
643    iterators = tup_inc(std::index_sequence_for<Iters...>{});
644    return *reinterpret_cast<ZipType *>(this);
645  }
646 
647  ZipType &operator--() {
648    static_assert(Base::IsBidirectional,
649                  "All inner iterators must be at least bidirectional.");
650    iterators = tup_dec(std::index_sequence_for<Iters...>{});
651    return *reinterpret_cast<ZipType *>(this);
652  }
653};
654 
655template <typename... Iters>
656struct zip_first : public zip_common<zip_first<Iters...>, Iters...> {
657  using Base = zip_common<zip_first<Iters...>, Iters...>;
658 
659  bool operator==(const zip_first<Iters...> &other) const {
660    return std::get<0>(this->iterators) == std::get<0>(other.iterators);
661  }
662 
663  zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
664};
665 
666template <typename... Iters>
667class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> {
668  template <size_t... Ns>
669  bool test(const zip_shortest<Iters...> &other,
670            std::index_sequence<Ns...>) const {
671    return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
672                                              std::get<Ns>(other.iterators)...},
673                  identity<bool>{});
674  }
675 
676public:
677  using Base = zip_common<zip_shortest<Iters...>, Iters...>;
678 
679  zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
680 
681  bool operator==(const zip_shortest<Iters...> &other) const {
682    return !test(other, std::index_sequence_for<Iters...>{});
683  }
684};
685 
686template <template <typename...> class ItType, typename... Args> class zippy {
687public:
688  using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>;
689  using iterator_category = typename iterator::iterator_category;
690  using value_type = typename iterator::value_type;
691  using difference_type = typename iterator::difference_type;
692  using pointer = typename iterator::pointer;
693  using reference = typename iterator::reference;
694 
695private:
696  std::tuple<Args...> ts;
697 
698  template <size_t... Ns>
699  iterator begin_impl(std::index_sequence<Ns...>) const {
700    return iterator(std::begin(std::get<Ns>(ts))...);
701  }
702  template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) const {
703    return iterator(std::end(std::get<Ns>(ts))...);
704  }
705 
706public:
707  zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
708 
709  iterator begin() const {
710    return begin_impl(std::index_sequence_for<Args...>{});
711  }
712  iterator end() const { return end_impl(std::index_sequence_for<Args...>{}); }
713};
714 
715} // end namespace detail
716 
717/// zip iterator for two or more iteratable types.
718template <typename T, typename U, typename... Args>
719detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u,
720                                                       Args &&... args) {
721  return detail::zippy<detail::zip_shortest, T, U, Args...>(
722      std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
723}
724 
725/// zip iterator that, for the sake of efficiency, assumes the first iteratee to
726/// be the shortest.
727template <typename T, typename U, typename... Args>
728detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u,
729                                                          Args &&... args) {
730  return detail::zippy<detail::zip_first, T, U, Args...>(
731      std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
732}
733 
734namespace detail {
735template <typename Iter>
736Iter next_or_end(const Iter &I, const Iter &End) {
737  if (I == End)
738    return End;
739  return std::next(I);
740}
741 
742template <typename Iter>
743auto deref_or_none(const Iter &I, const Iter &End) -> llvm::Optional<
744    std::remove_const_t<std::remove_reference_t<decltype(*I)>>> {
745  if (I == End)
746    return None;
747  return *I;
748}
749 
750template <typename Iter> struct ZipLongestItemType {
751  using type =
752      llvm::Optional<typename std::remove_const<typename std::remove_reference<
753          decltype(*std::declval<Iter>())>::type>::type>;
754};
755 
756template <typename... Iters> struct ZipLongestTupleType {
757  using type = std::tuple<typename ZipLongestItemType<Iters>::type...>;
758};
759 
760template <typename... Iters>
761class zip_longest_iterator
762    : public iterator_facade_base<
763          zip_longest_iterator<Iters...>,
764          typename std::common_type<
765              std::forward_iterator_tag,
766              typename std::iterator_traits<Iters>::iterator_category...>::type,
767          typename ZipLongestTupleType<Iters...>::type,
768          typename std::iterator_traits<typename std::tuple_element<
769              0, std::tuple<Iters...>>::type>::difference_type,
770          typename ZipLongestTupleType<Iters...>::type *,
771          typename ZipLongestTupleType<Iters...>::type> {
772public:
773  using value_type = typename ZipLongestTupleType<Iters...>::type;
774 
775private:
776  std::tuple<Iters...> iterators;
777  std::tuple<Iters...> end_iterators;
778 
779  template <size_t... Ns>
780  bool test(const zip_longest_iterator<Iters...> &other,
781            std::index_sequence<Ns...>) const {
782    return llvm::any_of(
783        std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
784                                    std::get<Ns>(other.iterators)...},
785        identity<bool>{});
786  }
787 
788  template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const {
789    return value_type(
790        deref_or_none(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
791  }
792 
793  template <size_t... Ns>
794  decltype(iterators) tup_inc(std::index_sequence<Ns...>) const {
795    return std::tuple<Iters...>(
796        next_or_end(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
797  }
798 
799public:
800  zip_longest_iterator(std::pair<Iters &&, Iters &&>... ts)
801      : iterators(std::forward<Iters>(ts.first)...),
802        end_iterators(std::forward<Iters>(ts.second)...) {}
803 
804  value_type operator*() { return deref(std::index_sequence_for<Iters...>{}); }
805 
806  value_type operator*() const {
807    return deref(std::index_sequence_for<Iters...>{});
808  }
809 
810  zip_longest_iterator<Iters...> &operator++() {
811    iterators = tup_inc(std::index_sequence_for<Iters...>{});
812    return *this;
813  }
814 
815  bool operator==(const zip_longest_iterator<Iters...> &other) const {
816    return !test(other, std::index_sequence_for<Iters...>{});
817  }
818};
819 
820template <typename... Args> class zip_longest_range {
821public:
822  using iterator =
823      zip_longest_iterator<decltype(adl_begin(std::declval<Args>()))...>;
824  using iterator_category = typename iterator::iterator_category;
825  using value_type = typename iterator::value_type;
826  using difference_type = typename iterator::difference_type;
827  using pointer = typename iterator::pointer;
828  using reference = typename iterator::reference;
829 
830private:
831  std::tuple<Args...> ts;
832 
833  template <size_t... Ns>
834  iterator begin_impl(std::index_sequence<Ns...>) const {
835    return iterator(std::make_pair(adl_begin(std::get<Ns>(ts)),
836                                   adl_end(std::get<Ns>(ts)))...);
837  }
838 
839  template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) const {
840    return iterator(std::make_pair(adl_end(std::get<Ns>(ts)),
841                                   adl_end(std::get<Ns>(ts)))...);
842  }
843 
844public:
845  zip_longest_range(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
846 
847  iterator begin() const {
848    return begin_impl(std::index_sequence_for<Args...>{});
849  }
850  iterator end() const { return end_impl(std::index_sequence_for<Args...>{}); }
851};
852} // namespace detail
853 
854/// Iterate over two or more iterators at the same time. Iteration continues
855/// until all iterators reach the end. The llvm::Optional only contains a value
856/// if the iterator has not reached the end.
857template <typename T, typename U, typename... Args>
858detail::zip_longest_range<T, U, Args...> zip_longest(T &&t, U &&u,
859                                                     Args &&... args) {
860  return detail::zip_longest_range<T, U, Args...>(
861      std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
862}
863 
864/// Iterator wrapper that concatenates sequences together.
865///
866/// This can concatenate different iterators, even with different types, into
867/// a single iterator provided the value types of all the concatenated
868/// iterators expose `reference` and `pointer` types that can be converted to
869/// `ValueT &` and `ValueT *` respectively. It doesn't support more
870/// interesting/customized pointer or reference types.
871///
872/// Currently this only supports forward or higher iterator categories as
873/// inputs and always exposes a forward iterator interface.
874template <typename ValueT, typename... IterTs>
875class concat_iterator
876    : public iterator_facade_base<concat_iterator<ValueT, IterTs...>,
877                                  std::forward_iterator_tag, ValueT> {
878  using BaseT = typename concat_iterator::iterator_facade_base;
879 
880  /// We store both the current and end iterators for each concatenated
881  /// sequence in a tuple of pairs.
882  ///
883  /// Note that something like iterator_range seems nice at first here, but the
884  /// range properties are of little benefit and end up getting in the way
885  /// because we need to do mutation on the current iterators.
886  std::tuple<IterTs...> Begins;
887  std::tuple<IterTs...> Ends;
888 
889  /// Attempts to increment a specific iterator.
890  ///
891  /// Returns true if it was able to increment the iterator. Returns false if
892  /// the iterator is already at the end iterator.
893  template <size_t Index> bool incrementHelper() {
894    auto &Begin = std::get<Index>(Begins);
895    auto &End = std::get<Index>(Ends);
896    if (Begin == End)
897      return false;
898 
899    ++Begin;
900    return true;
901  }
902 
903  /// Increments the first non-end iterator.
904  ///
905  /// It is an error to call this with all iterators at the end.
906  template <size_t... Ns> void increment(std::index_sequence<Ns...>) {
907    // Build a sequence of functions to increment each iterator if possible.
908    bool (concat_iterator::*IncrementHelperFns[])() = {
909        &concat_iterator::incrementHelper<Ns>...};
910 
911    // Loop over them, and stop as soon as we succeed at incrementing one.
912    for (auto &IncrementHelperFn : IncrementHelperFns)
913      if ((this->*IncrementHelperFn)())
914        return;
915 
916    llvm_unreachable("Attempted to increment an end concat iterator!")__builtin_unreachable();
917  }
918 
919  /// Returns null if the specified iterator is at the end. Otherwise,
920  /// dereferences the iterator and returns the address of the resulting
921  /// reference.
922  template <size_t Index> ValueT *getHelper() const {
923    auto &Begin = std::get<Index>(Begins);
924    auto &End = std::get<Index>(Ends);
925    if (Begin == End)
926      return nullptr;
927 
928    return &*Begin;
929  }
930 
931  /// Finds the first non-end iterator, dereferences, and returns the resulting
932  /// reference.
933  ///
934  /// It is an error to call this with all iterators at the end.
935  template <size_t... Ns> ValueT &get(std::index_sequence<Ns...>) const {
936    // Build a sequence of functions to get from iterator if possible.
937    ValueT *(concat_iterator::*GetHelperFns[])() const = {
938        &concat_iterator::getHelper<Ns>...};
939 
940    // Loop over them, and return the first result we find.
941    for (auto &GetHelperFn : GetHelperFns)
942      if (ValueT *P = (this->*GetHelperFn)())
943        return *P;
944 
945    llvm_unreachable("Attempted to get a pointer from an end concat iterator!")__builtin_unreachable();
946  }
947 
948public:
949  /// Constructs an iterator from a sequence of ranges.
950  ///
951  /// We need the full range to know how to switch between each of the
952  /// iterators.
953  template <typename... RangeTs>
954  explicit concat_iterator(RangeTs &&... Ranges)
955      : Begins(std::begin(Ranges)...), Ends(std::end(Ranges)...) {}
956 
957  using BaseT::operator++;
958 
959  concat_iterator &operator++() {
960    increment(std::index_sequence_for<IterTs...>());
961    return *this;
962  }
963 
964  ValueT &operator*() const {
965    return get(std::index_sequence_for<IterTs...>());
966  }
967 
968  bool operator==(const concat_iterator &RHS) const {
969    return Begins == RHS.Begins && Ends == RHS.Ends;
970  }
971};
972 
973namespace detail {
974 
975/// Helper to store a sequence of ranges being concatenated and access them.
976///
977/// This is designed to facilitate providing actual storage when temporaries
978/// are passed into the constructor such that we can use it as part of range
979/// based for loops.
980template <typename ValueT, typename... RangeTs> class concat_range {
981public:
982  using iterator =
983      concat_iterator<ValueT,
984                      decltype(std::begin(std::declval<RangeTs &>()))...>;
985 
986private:
987  std::tuple<RangeTs...> Ranges;
988 
989  template <size_t... Ns> iterator begin_impl(std::index_sequence<Ns...>) {
990    return iterator(std::get<Ns>(Ranges)...);
991  }
992  template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) {
993    return iterator(make_range(std::end(std::get<Ns>(Ranges)),
994                               std::end(std::get<Ns>(Ranges)))...);
995  }
996 
997public:
998  concat_range(RangeTs &&... Ranges)
999      : Ranges(std::forward<RangeTs>(Ranges)...) {}
1000 
1001  iterator begin() { return begin_impl(std::index_sequence_for<RangeTs...>{}); }
1002  iterator end() { return end_impl(std::index_sequence_for<RangeTs...>{}); }
1003};
1004 
1005} // end namespace detail
1006 
1007/// Concatenated range across two or more ranges.
1008///
1009/// The desired value type must be explicitly specified.
1010template <typename ValueT, typename... RangeTs>
1011detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
1012  static_assert(sizeof...(RangeTs) > 1,
1013                "Need more than one range to concatenate!");
1014  return detail::concat_range<ValueT, RangeTs...>(
1015      std::forward<RangeTs>(Ranges)...);
1016}
1017 
1018/// A utility class used to implement an iterator that contains some base object
1019/// and an index. The iterator moves the index but keeps the base constant.
1020template <typename DerivedT, typename BaseT, typename T,
1021          typename PointerT = T *, typename ReferenceT = T &>
1022class indexed_accessor_iterator
1023    : public llvm::iterator_facade_base<DerivedT,
1024                                        std::random_access_iterator_tag, T,
1025                                        std::ptrdiff_t, PointerT, ReferenceT> {
1026public:
1027  ptrdiff_t operator-(const indexed_accessor_iterator &rhs) const {
1028    assert(base == rhs.base && "incompatible iterators")((void)0);
1029    return index - rhs.index;
1030  }
1031  bool operator==(const indexed_accessor_iterator &rhs) const {
1032    return base == rhs.base && index == rhs.index;
1033  }
1034  bool operator<(const indexed_accessor_iterator &rhs) const {
1035    assert(base == rhs.base && "incompatible iterators")((void)0);
1036    return index < rhs.index;
1037  }
1038 
1039  DerivedT &operator+=(ptrdiff_t offset) {
1040    this->index += offset;
1041    return static_cast<DerivedT &>(*this);
1042  }
1043  DerivedT &operator-=(ptrdiff_t offset) {
1044    this->index -= offset;
1045    return static_cast<DerivedT &>(*this);
1046  }
1047 
1048  /// Returns the current index of the iterator.
1049  ptrdiff_t getIndex() const { return index; }
1050 
1051  /// Returns the current base of the iterator.
1052  const BaseT &getBase() const { return base; }
1053 
1054protected:
1055  indexed_accessor_iterator(BaseT base, ptrdiff_t index)
1056      : base(base), index(index) {}
1057  BaseT base;
1058  ptrdiff_t index;
1059};
1060 
1061namespace detail {
1062/// The class represents the base of a range of indexed_accessor_iterators. It
1063/// provides support for many different range functionalities, e.g.
1064/// drop_front/slice/etc.. Derived range classes must implement the following
1065/// static methods:
1066///   * ReferenceT dereference_iterator(const BaseT &base, ptrdiff_t index)
1067///     - Dereference an iterator pointing to the base object at the given
1068///       index.
1069///   * BaseT offset_base(const BaseT &base, ptrdiff_t index)
1070///     - Return a new base that is offset from the provide base by 'index'
1071///       elements.
1072template <typename DerivedT, typename BaseT, typename T,
1073          typename PointerT = T *, typename ReferenceT = T &>
1074class indexed_accessor_range_base {
1075public:
1076  using RangeBaseT =
1077      indexed_accessor_range_base<DerivedT, BaseT, T, PointerT, ReferenceT>;
1078 
1079  /// An iterator element of this range.
1080  class iterator : public indexed_accessor_iterator<iterator, BaseT, T,
1081                                                    PointerT, ReferenceT> {
1082  public:
1083    // Index into this iterator, invoking a static method on the derived type.
1084    ReferenceT operator*() const {
1085      return DerivedT::dereference_iterator(this->getBase(), this->getIndex());
1086    }
1087 
1088  private:
1089    iterator(BaseT owner, ptrdiff_t curIndex)
1090        : indexed_accessor_iterator<iterator, BaseT, T, PointerT, ReferenceT>(
1091              owner, curIndex) {}
1092 
1093    /// Allow access to the constructor.
1094    friend indexed_accessor_range_base<DerivedT, BaseT, T, PointerT,
1095                                       ReferenceT>;
1096  };
1097 
1098  indexed_accessor_range_base(iterator begin, iterator end)
1099      : base(offset_base(begin.getBase(), begin.getIndex())),
1100        count(end.getIndex() - begin.getIndex()) {}
1101  indexed_accessor_range_base(const iterator_range<iterator> &range)
1102      : indexed_accessor_range_base(range.begin(), range.end()) {}
1103  indexed_accessor_range_base(BaseT base, ptrdiff_t count)
1104      : base(base), count(count) {}
1105 
1106  iterator begin() const { return iterator(base, 0); }
1107  iterator end() const { return iterator(base, count); }
1108  ReferenceT operator[](size_t Index) const {
1109    assert(Index < size() && "invalid index for value range")((void)0);
1110    return DerivedT::dereference_iterator(base, static_cast<ptrdiff_t>(Index));
1111  }
1112  ReferenceT front() const {
1113    assert(!empty() && "expected non-empty range")((void)0);
1114    return (*this)[0];
1115  }
1116  ReferenceT back() const {
1117    assert(!empty() && "expected non-empty range")((void)0);
1118    return (*this)[size() - 1];
1119  }
1120 
1121  /// Compare this range with another.
1122  template <typename OtherT> bool operator==(const OtherT &other) const {
1123    return size() ==
1124               static_cast<size_t>(std::distance(other.begin(), other.end())) &&
1125           std::equal(begin(), end(), other.begin());
1126  }
1127  template <typename OtherT> bool operator!=(const OtherT &other) const {
1128    return !(*this == other);
1129  }
1130 
1131  /// Return the size of this range.
1132  size_t size() const { return count; }
1133 
1134  /// Return if the range is empty.
1135  bool empty() const { return size() == 0; }
1136 
1137  /// Drop the first N elements, and keep M elements.
1138  DerivedT slice(size_t n, size_t m) const {
1139    assert(n + m <= size() && "invalid size specifiers")((void)0);
1140    return DerivedT(offset_base(base, n), m);
1141  }
1142 
1143  /// Drop the first n elements.
1144  DerivedT drop_front(size_t n = 1) const {
1145    assert(size() >= n && "Dropping more elements than exist")((void)0);
1146    return slice(n, size() - n);
1147  }
1148  /// Drop the last n elements.
1149  DerivedT drop_back(size_t n = 1) const {
1150    assert(size() >= n && "Dropping more elements than exist")((void)0);
1151    return DerivedT(base, size() - n);
1152  }
1153 
1154  /// Take the first n elements.
1155  DerivedT take_front(size_t n = 1) const {
1156    return n < size() ? drop_back(size() - n)
1157                      : static_cast<const DerivedT &>(*this);
1158  }
1159 
1160  /// Take the last n elements.
1161  DerivedT take_back(size_t n = 1) const {
1162    return n < size() ? drop_front(size() - n)
1163                      : static_cast<const DerivedT &>(*this);
1164  }
1165 
1166  /// Allow conversion to any type accepting an iterator_range.
1167  template <typename RangeT, typename = std::enable_if_t<std::is_constructible<
1168                                 RangeT, iterator_range<iterator>>::value>>
1169  operator RangeT() const {
1170    return RangeT(iterator_range<iterator>(*this));
1171  }
1172 
1173  /// Returns the base of this range.
1174  const BaseT &getBase() const { return base; }
1175 
1176private:
1177  /// Offset the given base by the given amount.
1178  static BaseT offset_base(const BaseT &base, size_t n) {
1179    return n == 0 ? base : DerivedT::offset_base(base, n);
1180  }
1181 
1182protected:
1183  indexed_accessor_range_base(const indexed_accessor_range_base &) = default;
1184  indexed_accessor_range_base(indexed_accessor_range_base &&) = default;
1185  indexed_accessor_range_base &
1186  operator=(const indexed_accessor_range_base &) = default;
1187 
1188  /// The base that owns the provided range of values.
1189  BaseT base;
1190  /// The size from the owning range.
1191  ptrdiff_t count;
1192};
1193} // end namespace detail
1194 
1195/// This class provides an implementation of a range of
1196/// indexed_accessor_iterators where the base is not indexable. Ranges with
1197/// bases that are offsetable should derive from indexed_accessor_range_base
1198/// instead. Derived range classes are expected to implement the following
1199/// static method:
1200///   * ReferenceT dereference(const BaseT &base, ptrdiff_t index)
1201///     - Dereference an iterator pointing to a parent base at the given index.
1202template <typename DerivedT, typename BaseT, typename T,
1203          typename PointerT = T *, typename ReferenceT = T &>
1204class indexed_accessor_range
1205    : public detail::indexed_accessor_range_base<
1206          DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT> {
1207public:
1208  indexed_accessor_range(BaseT base, ptrdiff_t startIndex, ptrdiff_t count)
1209      : detail::indexed_accessor_range_base<
1210            DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT>(
1211            std::make_pair(base, startIndex), count) {}
1212  using detail::indexed_accessor_range_base<
1213      DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT,
1214      ReferenceT>::indexed_accessor_range_base;
1215 
1216  /// Returns the current base of the range.
1217  const BaseT &getBase() const { return this->base.first; }
1218 
1219  /// Returns the current start index of the range.
1220  ptrdiff_t getStartIndex() const { return this->base.second; }
1221 
1222  /// See `detail::indexed_accessor_range_base` for details.
1223  static std::pair<BaseT, ptrdiff_t>
1224  offset_base(const std::pair<BaseT, ptrdiff_t> &base, ptrdiff_t index) {
1225    // We encode the internal base as a pair of the derived base and a start
1226    // index into the derived base.
1227    return std::make_pair(base.first, base.second + index);
1228  }
1229  /// See `detail::indexed_accessor_range_base` for details.
1230  static ReferenceT
1231  dereference_iterator(const std::pair<BaseT, ptrdiff_t> &base,
1232                       ptrdiff_t index) {
1233    return DerivedT::dereference(base.first, base.second + index);
1234  }
1235};
1236 
1237/// Given a container of pairs, return a range over the first elements.
1238template <typename ContainerTy> auto make_first_range(ContainerTy &&c) {
1239  return llvm::map_range(
1240      std::forward<ContainerTy>(c),
1241      [](decltype((*std::begin(c))) elt) -> decltype((elt.first)) {
1242        return elt.first;
1243      });
1244}
1245 
1246/// Given a container of pairs, return a range over the second elements.
1247template <typename ContainerTy> auto make_second_range(ContainerTy &&c) {
1248  return llvm::map_range(
1249      std::forward<ContainerTy>(c),
1250      [](decltype((*std::begin(c))) elt) -> decltype((elt.second)) {
1251        return elt.second;
1252      });
1253}
1254 
1255//===----------------------------------------------------------------------===//
1256//     Extra additions to <utility>
1257//===----------------------------------------------------------------------===//
1258 
1259/// Function object to check whether the first component of a std::pair
1260/// compares less than the first component of another std::pair.
1261struct less_first {
1262  template <typename T> bool operator()(const T &lhs, const T &rhs) const {
1263    return lhs.first < rhs.first;
1264  }
1265};
1266 
1267/// Function object to check whether the second component of a std::pair
1268/// compares less than the second component of another std::pair.
1269struct less_second {
1270  template <typename T> bool operator()(const T &lhs, const T &rhs) const {
1271    return lhs.second < rhs.second;
1272  }
1273};
1274 
1275/// \brief Function object to apply a binary function to the first component of
1276/// a std::pair.
1277template<typename FuncTy>
1278struct on_first {
1279  FuncTy func;
1280 
1281  template <typename T>
1282  decltype(auto) operator()(const T &lhs, const T &rhs) const {
1283    return func(lhs.first, rhs.first);
1284  }
1285};
1286 
1287/// Utility type to build an inheritance chain that makes it easy to rank
1288/// overload candidates.
1289template <int N> struct rank : rank<N - 1> {};
1290template <> struct rank<0> {};
1291 
1292/// traits class for checking whether type T is one of any of the given
1293/// types in the variadic list.
1294template <typename T, typename... Ts>
1295using is_one_of = disjunction<std::is_same<T, Ts>...>;
1296 
1297/// traits class for checking whether type T is a base class for all
1298///  the given types in the variadic list.
1299template <typename T, typename... Ts>
1300using are_base_of = conjunction<std::is_base_of<T, Ts>...>;
1301 
1302namespace detail {
1303template <typename... Ts> struct Visitor;
1304 
1305template <typename HeadT, typename... TailTs>
1306struct Visitor<HeadT, TailTs...> : remove_cvref_t<HeadT>, Visitor<TailTs...> {
1307  explicit constexpr Visitor(HeadT &&Head, TailTs &&...Tail)
1308      : remove_cvref_t<HeadT>(std::forward<HeadT>(Head)),
1309        Visitor<TailTs...>(std::forward<TailTs>(Tail)...) {}
1310  using remove_cvref_t<HeadT>::operator();
1311  using Visitor<TailTs...>::operator();
1312};
1313 
1314template <typename HeadT> struct Visitor<HeadT> : remove_cvref_t<HeadT> {
1315  explicit constexpr Visitor(HeadT &&Head)
1316      : remove_cvref_t<HeadT>(std::forward<HeadT>(Head)) {}
1317  using remove_cvref_t<HeadT>::operator();
1318};
1319} // namespace detail
1320 
1321/// Returns an opaquely-typed Callable object whose operator() overload set is
1322/// the sum of the operator() overload sets of each CallableT in CallableTs.
1323///
1324/// The type of the returned object derives from each CallableT in CallableTs.
1325/// The returned object is constructed by invoking the appropriate copy or move
1326/// constructor of each CallableT, as selected by overload resolution on the
1327/// corresponding argument to makeVisitor.
1328///
1329/// Example:
1330///
1331/// \code
1332/// auto visitor = makeVisitor([](auto) { return "unhandled type"; },
1333///                            [](int i) { return "int"; },
1334///                            [](std::string s) { return "str"; });
1335/// auto a = visitor(42);    // `a` is now "int".
1336/// auto b = visitor("foo"); // `b` is now "str".
1337/// auto c = visitor(3.14f); // `c` is now "unhandled type".
1338/// \endcode
1339///
1340/// Example of making a visitor with a lambda which captures a move-only type:
1341///
1342/// \code
1343/// std::unique_ptr<FooHandler> FH = /* ... */;
1344/// auto visitor = makeVisitor(
1345///     [FH{std::move(FH)}](Foo F) { return FH->handle(F); },
1346///     [](int i) { return i; },
1347///     [](std::string s) { return atoi(s); });
1348/// \endcode
1349template <typename... CallableTs>
1350constexpr decltype(auto) makeVisitor(CallableTs &&...Callables) {
1351  return detail::Visitor<CallableTs...>(std::forward<CallableTs>(Callables)...);
1352}
1353 
1354//===----------------------------------------------------------------------===//
1355//     Extra additions for arrays
1356//===----------------------------------------------------------------------===//
1357 
1358// We have a copy here so that LLVM behaves the same when using different
1359// standard libraries.
1360template <class Iterator, class RNG>
1361void shuffle(Iterator first, Iterator last, RNG &&g) {
1362  // It would be better to use a std::uniform_int_distribution,
1363  // but that would be stdlib dependent.
1364  typedef
1365      typename std::iterator_traits<Iterator>::difference_type difference_type;
1366  for (auto size = last - first; size > 1; ++first, (void)--size) {
1367    difference_type offset = g() % size;
1368    // Avoid self-assignment due to incorrect assertions in libstdc++
1369    // containers (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85828).
1370    if (offset != difference_type(0))
1371      std::iter_swap(first, first + offset);
1372  }
1373}
1374 
1375/// Find the length of an array.
1376template <class T, std::size_t N>
1377constexpr inline size_t array_lengthof(T (&)[N]) {
1378  return N;
1379}
1380 
1381/// Adapt std::less<T> for array_pod_sort.
1382template<typename T>
1383inline int array_pod_sort_comparator(const void *P1, const void *P2) {
1384  if (std::less<T>()(*reinterpret_cast<const T*>(P1),
1385                     *reinterpret_cast<const T*>(P2)))
1386    return -1;
1387  if (std::less<T>()(*reinterpret_cast<const T*>(P2),
1388                     *reinterpret_cast<const T*>(P1)))
1389    return 1;
1390  return 0;
1391}
1392 
1393/// get_array_pod_sort_comparator - This is an internal helper function used to
1394/// get type deduction of T right.
1395template<typename T>
1396inline int (*get_array_pod_sort_comparator(const T &))
1397             (const void*, const void*) {
1398  return array_pod_sort_comparator<T>;
1399}
1400 
1401#ifdef EXPENSIVE_CHECKS
1402namespace detail {
1403 
1404inline unsigned presortShuffleEntropy() {
1405  static unsigned Result(std::random_device{}());
1406  return Result;
1407}
1408 
1409template <class IteratorTy>
1410inline void presortShuffle(IteratorTy Start, IteratorTy End) {
1411  std::mt19937 Generator(presortShuffleEntropy());
1412  llvm::shuffle(Start, End, Generator);
1413}
1414 
1415} // end namespace detail
1416#endif
1417 
1418/// array_pod_sort - This sorts an array with the specified start and end
1419/// extent.  This is just like std::sort, except that it calls qsort instead of
1420/// using an inlined template.  qsort is slightly slower than std::sort, but
1421/// most sorts are not performance critical in LLVM and std::sort has to be
1422/// template instantiated for each type, leading to significant measured code
1423/// bloat.  This function should generally be used instead of std::sort where
1424/// possible.
1425///
1426/// This function assumes that you have simple POD-like types that can be
1427/// compared with std::less and can be moved with memcpy.  If this isn't true,
1428/// you should use std::sort.
1429///
1430/// NOTE: If qsort_r were portable, we could allow a custom comparator and
1431/// default to std::less.
1432template<class IteratorTy>
1433inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
1434  // Don't inefficiently call qsort with one element or trigger undefined
1435  // behavior with an empty sequence.
1436  auto NElts = End - Start;
1437  if (NElts <= 1) return;
1438#ifdef EXPENSIVE_CHECKS
1439  detail::presortShuffle<IteratorTy>(Start, End);
1440#endif
1441  qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
1442}
1443 
1444template <class IteratorTy>
1445inline void array_pod_sort(
1446    IteratorTy Start, IteratorTy End,
1447    int (*Compare)(
1448        const typename std::iterator_traits<IteratorTy>::value_type *,
1449        const typename std::iterator_traits<IteratorTy>::value_type *)) {
1450  // Don't inefficiently call qsort with one element or trigger undefined
1451  // behavior with an empty sequence.
1452  auto NElts = End - Start;
1453  if (NElts <= 1) return;
1454#ifdef EXPENSIVE_CHECKS
1455  detail::presortShuffle<IteratorTy>(Start, End);
1456#endif
1457  qsort(&*Start, NElts, sizeof(*Start),
1458        reinterpret_cast<int (*)(const void *, const void *)>(Compare));
1459}
1460 
1461namespace detail {
1462template <typename T>
1463// We can use qsort if the iterator type is a pointer and the underlying value
1464// is trivially copyable.
1465using sort_trivially_copyable = conjunction<
1466    std::is_pointer<T>,
1467    std::is_trivially_copyable<typename std::iterator_traits<T>::value_type>>;
1468} // namespace detail
1469 
1470// Provide wrappers to std::sort which shuffle the elements before sorting
1471// to help uncover non-deterministic behavior (PR35135).
1472template <typename IteratorTy,
1473          std::enable_if_t<!detail::sort_trivially_copyable<IteratorTy>::value,
1474                           int> = 0>
1475inline void sort(IteratorTy Start, IteratorTy End) {
1476#ifdef EXPENSIVE_CHECKS
1477  detail::presortShuffle<IteratorTy>(Start, End);
1478#endif
1479  std::sort(Start, End);
1480}
1481 
1482// Forward trivially copyable types to array_pod_sort. This avoids a large
1483// amount of code bloat for a minor performance hit.
1484template <typename IteratorTy,
1485          std::enable_if_t<detail::sort_trivially_copyable<IteratorTy>::value,
1486                           int> = 0>
1487inline void sort(IteratorTy Start, IteratorTy End) {
1488  array_pod_sort(Start, End);
1489}
1490 
1491template <typename Container> inline void sort(Container &&C) {
1492  llvm::sort(adl_begin(C), adl_end(C));
1493}
1494 
1495template <typename IteratorTy, typename Compare>
1496inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) {
1497#ifdef EXPENSIVE_CHECKS
1498  detail::presortShuffle<IteratorTy>(Start, End);
1499#endif
1500  std::sort(Start, End, Comp);
1501}
1502 
1503template <typename Container, typename Compare>
1504inline void sort(Container &&C, Compare Comp) {
1505  llvm::sort(adl_begin(C), adl_end(C), Comp);
1506}
1507 
1508//===----------------------------------------------------------------------===//
1509//     Extra additions to <algorithm>
1510//===----------------------------------------------------------------------===//
1511 
1512/// Get the size of a range. This is a wrapper function around std::distance
1513/// which is only enabled when the operation is O(1).
1514template <typename R>
1515auto size(R &&Range,
1516          std::enable_if_t<
1517              std::is_base_of<std::random_access_iterator_tag,
1518                              typename std::iterator_traits<decltype(
1519                                  Range.begin())>::iterator_category>::value,
1520              void> * = nullptr) {
1521  return std::distance(Range.begin(), Range.end());
1522}
1523 
1524/// Provide wrappers to std::for_each which take ranges instead of having to
1525/// pass begin/end explicitly.
1526template <typename R, typename UnaryFunction>
1527UnaryFunction for_each(R &&Range, UnaryFunction F) {
1528  return std::for_each(adl_begin(Range), adl_end(Range), F);
1529}
1530 
1531/// Provide wrappers to std::all_of which take ranges instead of having to pass
1532/// begin/end explicitly.
1533template <typename R, typename UnaryPredicate>
1534bool all_of(R &&Range, UnaryPredicate P) {
1535  return std::all_of(adl_begin(Range), adl_end(Range), P);
1536}
1537 
1538/// Provide wrappers to std::any_of which take ranges instead of having to pass
1539/// begin/end explicitly.
1540template <typename R, typename UnaryPredicate>
1541bool any_of(R &&Range, UnaryPredicate P) {
1542  return std::any_of(adl_begin(Range), adl_end(Range), P);
1543}
1544 
1545/// Provide wrappers to std::none_of which take ranges instead of having to pass
1546/// begin/end explicitly.
1547template <typename R, typename UnaryPredicate>
1548bool none_of(R &&Range, UnaryPredicate P) {
1549  return std::none_of(adl_begin(Range), adl_end(Range), P);
1550}
1551 
1552/// Provide wrappers to std::find which take ranges instead of having to pass
1553/// begin/end explicitly.
1554template <typename R, typename T> auto find(R &&Range, const T &Val) {
1555  return std::find(adl_begin(Range), adl_end(Range), Val);
1556}
1557 
1558/// Provide wrappers to std::find_if which take ranges instead of having to pass
1559/// begin/end explicitly.
1560template <typename R, typename UnaryPredicate>
1561auto find_if(R &&Range, UnaryPredicate P) {
1562  return std::find_if(adl_begin(Range), adl_end(Range), P);
1563}
1564 
1565template <typename R, typename UnaryPredicate>
1566auto find_if_not(R &&Range, UnaryPredicate P) {
1567  return std::find_if_not(adl_begin(Range), adl_end(Range), P);
1568}
1569 
1570/// Provide wrappers to std::remove_if which take ranges instead of having to
1571/// pass begin/end explicitly.
1572template <typename R, typename UnaryPredicate>
1573auto remove_if(R &&Range, UnaryPredicate P) {
1574  return std::remove_if(adl_begin(Range), adl_end(Range), P);
1575}
1576 
1577/// Provide wrappers to std::copy_if which take ranges instead of having to
1578/// pass begin/end explicitly.
1579template <typename R, typename OutputIt, typename UnaryPredicate>
1580OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
1581  return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
1582}
1583 
1584template <typename R, typename OutputIt>
1585OutputIt copy(R &&Range, OutputIt Out) {
1586  return std::copy(adl_begin(Range), adl_end(Range), Out);
1587}
1588 
1589/// Provide wrappers to std::move which take ranges instead of having to
1590/// pass begin/end explicitly.
1591template <typename R, typename OutputIt>
1592OutputIt move(R &&Range, OutputIt Out) {
1593  return std::move(adl_begin(Range), adl_end(Range), Out);
1594}
1595 
1596/// Wrapper function around std::find to detect if an element exists
1597/// in a container.
1598template <typename R, typename E>
1599bool is_contained(R &&Range, const E &Element) {
1600  return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
1601}
1602 
1603/// Wrapper function around std::is_sorted to check if elements in a range \p R
1604/// are sorted with respect to a comparator \p C.
1605template <typename R, typename Compare> bool is_sorted(R &&Range, Compare C) {
1606  return std::is_sorted(adl_begin(Range), adl_end(Range), C);
1607}
1608 
1609/// Wrapper function around std::is_sorted to check if elements in a range \p R
1610/// are sorted in non-descending order.
1611template <typename R> bool is_sorted(R &&Range) {
1612  return std::is_sorted(adl_begin(Range), adl_end(Range));
1613}
1614 
1615/// Wrapper function around std::count to count the number of times an element
1616/// \p Element occurs in the given range \p Range.
1617template <typename R, typename E> auto count(R &&Range, const E &Element) {
1618  return std::count(adl_begin(Range), adl_end(Range), Element);
1619}
1620 
1621/// Wrapper function around std::count_if to count the number of times an
1622/// element satisfying a given predicate occurs in a range.
1623template <typename R, typename UnaryPredicate>
1624auto count_if(R &&Range, UnaryPredicate P) {
1625  return std::count_if(adl_begin(Range), adl_end(Range), P);
1626}
1627 
1628/// Wrapper function around std::transform to apply a function to a range and
1629/// store the result elsewhere.
1630template <typename R, typename OutputIt, typename UnaryFunction>
1631OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F) {
1632  return std::transform(adl_begin(Range), adl_end(Range), d_first, F);
1633}
1634 
1635/// Provide wrappers to std::partition which take ranges instead of having to
1636/// pass begin/end explicitly.
1637template <typename R, typename UnaryPredicate>
1638auto partition(R &&Range, UnaryPredicate P) {
1639  return std::partition(adl_begin(Range), adl_end(Range), P);
1640}
1641 
1642/// Provide wrappers to std::lower_bound which take ranges instead of having to
1643/// pass begin/end explicitly.
1644template <typename R, typename T> auto lower_bound(R &&Range, T &&Value) {
1645  return std::lower_bound(adl_begin(Range), adl_end(Range),
1646                          std::forward<T>(Value));
1647}
1648 
1649template <typename R, typename T, typename Compare>
1650auto lower_bound(R &&Range, T &&Value, Compare C) {
1651  return std::lower_bound(adl_begin(Range), adl_end(Range),
1652                          std::forward<T>(Value), C);
1653}
1654 
1655/// Provide wrappers to std::upper_bound which take ranges instead of having to
1656/// pass begin/end explicitly.
1657template <typename R, typename T> auto upper_bound(R &&Range, T &&Value) {
1658  return std::upper_bound(adl_begin(Range), adl_end(Range),
1659                          std::forward<T>(Value));
1660}
1661 
1662template <typename R, typename T, typename Compare>
1663auto upper_bound(R &&Range, T &&Value, Compare C) {
1664  return std::upper_bound(adl_begin(Range), adl_end(Range),
1665                          std::forward<T>(Value), C);
1666}
1667 
1668template <typename R>
1669void stable_sort(R &&Range) {
1670  std::stable_sort(adl_begin(Range), adl_end(Range));
1671}
1672 
1673template <typename R, typename Compare>
1674void stable_sort(R &&Range, Compare C) {
1675  std::stable_sort(adl_begin(Range), adl_end(Range), C);
1676}
1677 
1678/// Binary search for the first iterator in a range where a predicate is false.
1679/// Requires that C is always true below some limit, and always false above it.
1680template <typename R, typename Predicate,
1681          typename Val = decltype(*adl_begin(std::declval<R>()))>
1682auto partition_point(R &&Range, Predicate P) {
1683  return std::partition_point(adl_begin(Range), adl_end(Range), P);
1684}
1685 
1686template<typename Range, typename Predicate>
1687auto unique(Range &&R, Predicate P) {
1688  return std::unique(adl_begin(R), adl_end(R), P);
1689}
1690 
1691/// Wrapper function around std::equal to detect if pair-wise elements between
1692/// two ranges are the same.
1693template <typename L, typename R> bool equal(L &&LRange, R &&RRange) {
1694  return std::equal(adl_begin(LRange), adl_end(LRange), adl_begin(RRange),
1695                    adl_end(RRange));
1696}
1697 
1698/// Wrapper function around std::equal to detect if all elements
1699/// in a container are same.
1700template <typename R>
1701bool is_splat(R &&Range) {
1702  size_t range_size = size(Range);
1703  return range_size != 0 && (range_size == 1 ||
1704         std::equal(adl_begin(Range) + 1, adl_end(Range), adl_begin(Range)));
1705}
1706 
1707/// Provide a container algorithm similar to C++ Library Fundamentals v2's
1708/// `erase_if` which is equivalent to:
1709///
1710///   C.erase(remove_if(C, pred), C.end());
1711///
1712/// This version works for any container with an erase method call accepting
1713/// two iterators.
1714template <typename Container, typename UnaryPredicate>
1715void erase_if(Container &C, UnaryPredicate P) {
1716  C.erase(remove_if(C, P), C.end());
1717}
1718 
1719/// Wrapper function to remove a value from a container:
1720///
1721/// C.erase(remove(C.begin(), C.end(), V), C.end());
1722template <typename Container, typename ValueType>
1723void erase_value(Container &C, ValueType V) {
1724  C.erase(std::remove(C.begin(), C.end(), V), C.end());
1725}
1726 
1727/// Wrapper function to append a range to a container.
1728///
1729/// C.insert(C.end(), R.begin(), R.end());
1730template <typename Container, typename Range>
1731inline void append_range(Container &C, Range &&R) {
1732  C.insert(C.end(), R.begin(), R.end());
1733}
1734 
1735/// Given a sequence container Cont, replace the range [ContIt, ContEnd) with
1736/// the range [ValIt, ValEnd) (which is not from the same container).
1737template<typename Container, typename RandomAccessIterator>
1738void replace(Container &Cont, typename Container::iterator ContIt,
1739             typename Container::iterator ContEnd, RandomAccessIterator ValIt,
1740             RandomAccessIterator ValEnd) {
1741  while (true) {
1742    if (ValIt == ValEnd) {
1743      Cont.erase(ContIt, ContEnd);
1744      return;
1745    } else if (ContIt == ContEnd) {
1746      Cont.insert(ContIt, ValIt, ValEnd);
1747      return;
1748    }
1749    *ContIt++ = *ValIt++;
1750  }
1751}
1752 
1753/// Given a sequence container Cont, replace the range [ContIt, ContEnd) with
1754/// the range R.
1755template<typename Container, typename Range = std::initializer_list<
1756                                 typename Container::value_type>>
1757void replace(Container &Cont, typename Container::iterator ContIt,
1758             typename Container::iterator ContEnd, Range R) {
1759  replace(Cont, ContIt, ContEnd, R.begin(), R.end());
1760}
1761 
1762/// An STL-style algorithm similar to std::for_each that applies a second
1763/// functor between every pair of elements.
1764///
1765/// This provides the control flow logic to, for example, print a
1766/// comma-separated list:
1767/// \code
1768///   interleave(names.begin(), names.end(),
1769///              [&](StringRef name) { os << name; },
1770///              [&] { os << ", "; });
1771/// \endcode
1772template <typename ForwardIterator, typename UnaryFunctor,
1773          typename NullaryFunctor,
1774          typename = typename std::enable_if<
1775              !std::is_constructible<StringRef, UnaryFunctor>::value &&
1776              !std::is_constructible<StringRef, NullaryFunctor>::value>::type>
1777inline void interleave(ForwardIterator begin, ForwardIterator end,
1778                       UnaryFunctor each_fn, NullaryFunctor between_fn) {
1779  if (begin == end)
1780    return;
1781  each_fn(*begin);
1782  ++begin;
1783  for (; begin != end; ++begin) {
1784    between_fn();
1785    each_fn(*begin);
1786  }
1787}
1788 
1789template <typename Container, typename UnaryFunctor, typename NullaryFunctor,
1790          typename = typename std::enable_if<
1791              !std::is_constructible<StringRef, UnaryFunctor>::value &&
1792              !std::is_constructible<StringRef, NullaryFunctor>::value>::type>
1793inline void interleave(const Container &c, UnaryFunctor each_fn,
1794                       NullaryFunctor between_fn) {
1795  interleave(c.begin(), c.end(), each_fn, between_fn);
1796}
1797 
1798/// Overload of interleave for the common case of string separator.
1799template <typename Container, typename UnaryFunctor, typename StreamT,
1800          typename T = detail::ValueOfRange<Container>>
1801inline void interleave(const Container &c, StreamT &os, UnaryFunctor each_fn,
1802                       const StringRef &separator) {
1803  interleave(c.begin(), c.end(), each_fn, [&] { os << separator; });
1804}
1805template <typename Container, typename StreamT,
1806          typename T = detail::ValueOfRange<Container>>
1807inline void interleave(const Container &c, StreamT &os,
1808                       const StringRef &separator) {
1809  interleave(
1810      c, os, [&](const T &a) { os << a; }, separator);
1811}
1812 
1813template <typename Container, typename UnaryFunctor, typename StreamT,
1814          typename T = detail::ValueOfRange<Container>>
1815inline void interleaveComma(const Container &c, StreamT &os,
1816                            UnaryFunctor each_fn) {
1817  interleave(c, os, each_fn, ", ");
1818}
1819template <typename Container, typename StreamT,
1820          typename T = detail::ValueOfRange<Container>>
1821inline void interleaveComma(const Container &c, StreamT &os) {
1822  interleaveComma(c, os, [&](const T &a) { os << a; });
1823}
1824 
1825//===----------------------------------------------------------------------===//
1826//     Extra additions to <memory>
1827//===----------------------------------------------------------------------===//
1828 
1829struct FreeDeleter {
1830  void operator()(void* v) {
1831    ::free(v);
1832  }
1833};
1834 
1835template<typename First, typename Second>
1836struct pair_hash {
1837  size_t operator()(const std::pair<First, Second> &P) const {
1838    return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
1839  }
1840};
1841 
1842/// Binary functor that adapts to any other binary functor after dereferencing
1843/// operands.
1844template <typename T> struct deref {
1845  T func;
1846 
1847  // Could be further improved to cope with non-derivable functors and
1848  // non-binary functors (should be a variadic template member function
1849  // operator()).
1850  template <typename A, typename B> auto operator()(A &lhs, B &rhs) const {
1851    assert(lhs)((void)0);
1852    assert(rhs)((void)0);
1853    return func(*lhs, *rhs);
1854  }
1855};
1856 
1857namespace detail {
1858 
1859template <typename R> class enumerator_iter;
1860 
1861template <typename R> struct result_pair {
1862  using value_reference =
1863      typename std::iterator_traits<IterOfRange<R>>::reference;
1864 
1865  friend class enumerator_iter<R>;
1866 
1867  result_pair() = default;
1868  result_pair(std::size_t Index, IterOfRange<R> Iter)
1869      : Index(Index), Iter(Iter) {}
1870 
1871  result_pair(const result_pair<R> &Other)
1872      : Index(Other.Index), Iter(Other.Iter) {}
1873  result_pair &operator=(const result_pair &Other) {
1874    Index = Other.Index;
1875    Iter = Other.Iter;
1876    return *this;
1877  }
1878 
1879  std::size_t index() const { return Index; }
1880  const value_reference value() const { return *Iter; }
1881  value_reference value() { return *Iter; }
1882 
1883private:
1884  std::size_t Index = std::numeric_limits<std::size_t>::max();
1885  IterOfRange<R> Iter;
1886};
1887 
1888template <typename R>
1889class enumerator_iter
1890    : public iterator_facade_base<
1891          enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>,
1892          typename std::iterator_traits<IterOfRange<R>>::difference_type,
1893          typename std::iterator_traits<IterOfRange<R>>::pointer,
1894          typename std::iterator_traits<IterOfRange<R>>::reference> {
1895  using result_type = result_pair<R>;
1896 
1897public:
1898  explicit enumerator_iter(IterOfRange<R> EndIter)
1899      : Result(std::numeric_limits<size_t>::max(), EndIter) {}
1900 
1901  enumerator_iter(std::size_t Index, IterOfRange<R> Iter)
1902      : Result(Index, Iter) {}
1903 
1904  result_type &operator*() { return Result; }
1905  const result_type &operator*() const { return Result; }
1906 
1907  enumerator_iter &operator++() {
1908    assert(Result.Index != std::numeric_limits<size_t>::max())((void)0);
1909    ++Result.Iter;
1910    ++Result.Index;
1911    return *this;
1912  }
1913 
1914  bool operator==(const enumerator_iter &RHS) const {
1915    // Don't compare indices here, only iterators.  It's possible for an end
1916    // iterator to have different indices depending on whether it was created
1917    // by calling std::end() versus incrementing a valid iterator.
1918    return Result.Iter == RHS.Result.Iter;
1919  }
1920 
1921  enumerator_iter(const enumerator_iter &Other) : Result(Other.Result) {}
1922  enumerator_iter &operator=(const enumerator_iter &Other) {
1923    Result = Other.Result;
1924    return *this;
1925  }
1926 
1927private:
1928  result_type Result;
1929};
1930 
1931template <typename R> class enumerator {
1932public:
1933  explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
1934 
1935  enumerator_iter<R> begin() {
1936    return enumerator_iter<R>(0, std::begin(TheRange));
1937  }
1938 
1939  enumerator_iter<R> end() {
1940    return enumerator_iter<R>(std::end(TheRange));
1941  }
1942 
1943private:
1944  R TheRange;
1945};
1946 
1947} // end namespace detail
1948 
1949/// Given an input range, returns a new range whose values are are pair (A,B)
1950/// such that A is the 0-based index of the item in the sequence, and B is
1951/// the value from the original sequence.  Example:
1952///
1953/// std::vector<char> Items = {'A', 'B', 'C', 'D'};
1954/// for (auto X : enumerate(Items)) {
1955///   printf("Item %d - %c\n", X.index(), X.value());
1956/// }
1957///
1958/// Output:
1959///   Item 0 - A
1960///   Item 1 - B
1961///   Item 2 - C
1962///   Item 3 - D
1963///
1964template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
1965  return detail::enumerator<R>(std::forward<R>(TheRange));
1966}
1967 
1968namespace detail {
1969 
1970template <typename F, typename Tuple, std::size_t... I>
1971decltype(auto) apply_tuple_impl(F &&f, Tuple &&t, std::index_sequence<I...>) {
1972  return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...);
1973}
1974 
1975} // end namespace detail
1976 
1977/// Given an input tuple (a1, a2, ..., an), pass the arguments of the
1978/// tuple variadically to f as if by calling f(a1, a2, ..., an) and
1979/// return the result.
1980template <typename F, typename Tuple>
1981decltype(auto) apply_tuple(F &&f, Tuple &&t) {
1982  using Indices = std::make_index_sequence<
1983      std::tuple_size<typename std::decay<Tuple>::type>::value>;
1984 
1985  return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t),
1986                                  Indices{});
1987}
1988 
1989/// Return true if the sequence [Begin, End) has exactly N items. Runs in O(N)
1990/// time. Not meant for use with random-access iterators.
1991/// Can optionally take a predicate to filter lazily some items.
1992template <typename IterTy,
1993          typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
1994bool hasNItems(
1995    IterTy &&Begin, IterTy &&End, unsigned N,
1996    Pred &&ShouldBeCounted =
1997        [](const decltype(*std::declval<IterTy>()) &) { return true; },
1998    std::enable_if_t<
1999        !std::is_base_of<std::random_access_iterator_tag,
2000                         typename std::iterator_traits<std::remove_reference_t<
2001                             decltype(Begin)>>::iterator_category>::value,
2002        void> * = nullptr) {
2003  for (; N; ++Begin) {
2004    if (Begin == End)
2005      return false; // Too few.
2006    N -= ShouldBeCounted(*Begin);
2007  }
2008  for (; Begin != End; ++Begin)
2009    if (ShouldBeCounted(*Begin))
2010      return false; // Too many.
2011  return true;
2012}
2013 
2014/// Return true if the sequence [Begin, End) has N or more items. Runs in O(N)
2015/// time. Not meant for use with random-access iterators.
2016/// Can optionally take a predicate to lazily filter some items.
2017template <typename IterTy,
2018          typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
2019bool hasNItemsOrMore(
2020    IterTy &&Begin, IterTy &&End, unsigned N,
2021    Pred &&ShouldBeCounted =
2022        [](const decltype(*std::declval<IterTy>()) &) { return true; },
2023    std::enable_if_t<
2024        !std::is_base_of<std::random_access_iterator_tag,
2025                         typename std::iterator_traits<std::remove_reference_t<
2026                             decltype(Begin)>>::iterator_category>::value,
2027        void> * = nullptr) {
2028  for (; N; ++Begin) {
2029    if (Begin == End)
2030      return false; // Too few.
2031    N -= ShouldBeCounted(*Begin);
2032  }
2033  return true;
2034}
2035 
2036/// Returns true if the sequence [Begin, End) has N or less items. Can
2037/// optionally take a predicate to lazily filter some items.
2038template <typename IterTy,
2039          typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
2040bool hasNItemsOrLess(
2041    IterTy &&Begin, IterTy &&End, unsigned N,
2042    Pred &&ShouldBeCounted = [](const decltype(*std::declval<IterTy>()) &) {
2043      return true;
2044    }) {
2045  assert(N != std::numeric_limits<unsigned>::max())((void)0);
2046  return !hasNItemsOrMore(Begin, End, N + 1, ShouldBeCounted);
2047}
2048 
2049/// Returns true if the given container has exactly N items
2050template <typename ContainerTy> bool hasNItems(ContainerTy &&C, unsigned N) {
2051  return hasNItems(std::begin(C), std::end(C), N);
2052}
2053 
2054/// Returns true if the given container has N or more items
2055template <typename ContainerTy>
2056bool hasNItemsOrMore(ContainerTy &&C, unsigned N) {
2057  return hasNItemsOrMore(std::begin(C), std::end(C), N);
2058}
2059 
2060/// Returns true if the given container has N or less items
2061template <typename ContainerTy>
2062bool hasNItemsOrLess(ContainerTy &&C, unsigned N) {
2063  return hasNItemsOrLess(std::begin(C), std::end(C), N);
2064}
2065 
2066/// Returns a raw pointer that represents the same address as the argument.
2067///
2068/// This implementation can be removed once we move to C++20 where it's defined
2069/// as std::to_address().
2070///
2071/// The std::pointer_traits<>::to_address(p) variations of these overloads has
2072/// not been implemented.
2073template <class Ptr> auto to_address(const Ptr &P) { return P.operator->(); }
2074template <class T> constexpr T *to_address(T *P) { return P; }
2075 
2076} // end namespace llvm
2077 
2078#endif // LLVM_ADT_STLEXTRAS_H