/usr/src/gnu/usr.bin/clang/libclangCodeGen/../../../llvm/llvm/include/llvm/Support/MathExtras.h

Bug Summary

File:	src/gnu/usr.bin/clang/libclangCodeGen/../../../llvm/llvm/include/llvm/Support/MathExtras.h
Warning:	line 730, column 8 Division by zero

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 CGBlocks.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/libclangCodeGen/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/gnu/usr.bin/clang/libclangCodeGen/../../../llvm/clang/include -I /usr/src/gnu/usr.bin/clang/libclangCodeGen/../../../llvm/llvm/include -I /usr/src/gnu/usr.bin/clang/libclangCodeGen/../include -I /usr/src/gnu/usr.bin/clang/libclangCodeGen/obj -I /usr/src/gnu/usr.bin/clang/libclangCodeGen/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/libclangCodeGen/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/libclangCodeGen/../../../llvm/clang/lib/CodeGen/CGBlocks.cpp

/usr/src/gnu/usr.bin/clang/libclangCodeGen/../../../llvm/clang/lib/CodeGen/CGBlocks.cpp

→

1//===--- CGBlocks.cpp - Emit LLVM Code for declarations ---------*- 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 contains code to emit blocks.
10//
11//===----------------------------------------------------------------------===//

13#include "CGBlocks.h"
14#include "CGCXXABI.h"
15#include "CGDebugInfo.h"
16#include "CGObjCRuntime.h"
17#include "CGOpenCLRuntime.h"
18#include "CodeGenFunction.h"
19#include "CodeGenModule.h"
20#include "ConstantEmitter.h"
21#include "TargetInfo.h"
22#include "clang/AST/Attr.h"
23#include "clang/AST/DeclObjC.h"
24#include "clang/CodeGen/ConstantInitBuilder.h"
25#include "llvm/ADT/SmallSet.h"
26#include "llvm/IR/DataLayout.h"
27#include "llvm/IR/Module.h"
28#include "llvm/Support/ScopedPrinter.h"
29#include <algorithm>
30#include <cstdio>

32using namespace clang;
33using namespace CodeGen;

35CGBlockInfo::CGBlockInfo(const BlockDecl *block, StringRef name)
: Name(name), CXXThisIndex(0), CanBeGlobal(false), NeedsCopyDispose(false),
  HasCXXObject(false), UsesStret(false), HasCapturedVariableLayout(false),
  CapturesNonExternalType(false), LocalAddress(Address::invalid()),
  StructureType(nullptr), Block(block) {

// Skip asm prefix, if any.  'name' is usually taken directly from
// the mangled name of the enclosing function.
if (!name.empty() && name[0] == '\01')
  name = name.substr(1);
45}

47// Anchor the vtable to this translation unit.
48BlockByrefHelpers::~BlockByrefHelpers() {}

50/// Build the given block as a global block.
51static llvm::Constant *buildGlobalBlock(CodeGenModule &CGM,
                                      const CGBlockInfo &blockInfo,
                                      llvm::Constant *blockFn);

55/// Build the helper function to copy a block.
56static llvm::Constant *buildCopyHelper(CodeGenModule &CGM,
                                     const CGBlockInfo &blockInfo) {
return CodeGenFunction(CGM).GenerateCopyHelperFunction(blockInfo);
59}

61/// Build the helper function to dispose of a block.
62static llvm::Constant *buildDisposeHelper(CodeGenModule &CGM,
                                        const CGBlockInfo &blockInfo) {
return CodeGenFunction(CGM).GenerateDestroyHelperFunction(blockInfo);
65}

67namespace {

69/// Represents a type of copy/destroy operation that should be performed for an
70/// entity that's captured by a block.
71enum class BlockCaptureEntityKind {
CXXRecord, // Copy or destroy
ARCWeak,
ARCStrong,
NonTrivialCStruct,
BlockObject, // Assign or release
None
78};

80/// Represents a captured entity that requires extra operations in order for
81/// this entity to be copied or destroyed correctly.
82struct BlockCaptureManagedEntity {
BlockCaptureEntityKind CopyKind, DisposeKind;
BlockFieldFlags CopyFlags, DisposeFlags;
const BlockDecl::Capture *CI;
const CGBlockInfo::Capture *Capture;

BlockCaptureManagedEntity(BlockCaptureEntityKind CopyType,
                          BlockCaptureEntityKind DisposeType,
                          BlockFieldFlags CopyFlags,
                          BlockFieldFlags DisposeFlags,
                          const BlockDecl::Capture &CI,
                          const CGBlockInfo::Capture &Capture)
    : CopyKind(CopyType), DisposeKind(DisposeType), CopyFlags(CopyFlags),
      DisposeFlags(DisposeFlags), CI(&CI), Capture(&Capture) {}

bool operator<(const BlockCaptureManagedEntity &Other) const {
  return Capture->getOffset() < Other.Capture->getOffset();
}
100};

102enum class CaptureStrKind {
// String for the copy helper.
CopyHelper,
// String for the dispose helper.
DisposeHelper,
// Merge the strings for the copy helper and dispose helper.
Merged
109};

111} // end anonymous namespace

113static void findBlockCapturedManagedEntities(
  const CGBlockInfo &BlockInfo, const LangOptions &LangOpts,
  SmallVectorImpl<BlockCaptureManagedEntity> &ManagedCaptures);

117static std::string getBlockCaptureStr(const BlockCaptureManagedEntity &E,
                                    CaptureStrKind StrKind,
                                    CharUnits BlockAlignment,
                                    CodeGenModule &CGM);

122static std::string getBlockDescriptorName(const CGBlockInfo &BlockInfo,
                                        CodeGenModule &CGM) {
std::string Name = "__block_descriptor_";
Name += llvm::to_string(BlockInfo.BlockSize.getQuantity()) + "_";

if (BlockInfo.needsCopyDisposeHelpers()) {
  if (CGM.getLangOpts().Exceptions)
    Name += "e";
  if (CGM.getCodeGenOpts().ObjCAutoRefCountExceptions)
    Name += "a";
  Name += llvm::to_string(BlockInfo.BlockAlign.getQuantity()) + "_";

  SmallVector<BlockCaptureManagedEntity, 4> ManagedCaptures;
  findBlockCapturedManagedEntities(BlockInfo, CGM.getContext().getLangOpts(),
                                   ManagedCaptures);

  for (const BlockCaptureManagedEntity &E : ManagedCaptures) {
    Name += llvm::to_string(E.Capture->getOffset().getQuantity());

    if (E.CopyKind == E.DisposeKind) {
      // If CopyKind and DisposeKind are the same, merge the capture
      // information.
      assert(E.CopyKind != BlockCaptureEntityKind::None &&((void)0)
             "shouldn't see BlockCaptureManagedEntity that is None")((void)0);
      Name += getBlockCaptureStr(E, CaptureStrKind::Merged,
                                 BlockInfo.BlockAlign, CGM);
    } else {
      // If CopyKind and DisposeKind are not the same, which can happen when
      // either Kind is None or the captured object is a __strong block,
      // concatenate the copy and dispose strings.
      Name += getBlockCaptureStr(E, CaptureStrKind::CopyHelper,
                                 BlockInfo.BlockAlign, CGM);
      Name += getBlockCaptureStr(E, CaptureStrKind::DisposeHelper,
                                 BlockInfo.BlockAlign, CGM);
    }
  }
  Name += "_";
}

std::string TypeAtEncoding =
    CGM.getContext().getObjCEncodingForBlock(BlockInfo.getBlockExpr());
/// Replace occurrences of '@' with '\1'. '@' is reserved on ELF platforms as
/// a separator between symbol name and symbol version.
std::replace(TypeAtEncoding.begin(), TypeAtEncoding.end(), '@', '\1');
Name += "e" + llvm::to_string(TypeAtEncoding.size()) + "_" + TypeAtEncoding;
Name += "l" + CGM.getObjCRuntime().getRCBlockLayoutStr(CGM, BlockInfo);
return Name;
169}

171/// buildBlockDescriptor - Build the block descriptor meta-data for a block.
172/// buildBlockDescriptor is accessed from 5th field of the Block_literal
173/// meta-data and contains stationary information about the block literal.
174/// Its definition will have 4 (or optionally 6) words.
175/// \code
176/// struct Block_descriptor {
177///   unsigned long reserved;
178///   unsigned long size;  // size of Block_literal metadata in bytes.
179///   void *copy_func_helper_decl;  // optional copy helper.
180///   void *destroy_func_decl; // optional destructor helper.
181///   void *block_method_encoding_address; // @encode for block literal signature.
182///   void *block_layout_info; // encoding of captured block variables.
183/// };
184/// \endcode
185static llvm::Constant *buildBlockDescriptor(CodeGenModule &CGM,
                                          const CGBlockInfo &blockInfo) {
ASTContext &C = CGM.getContext();

llvm::IntegerType *ulong =
  cast<llvm::IntegerType>(CGM.getTypes().ConvertType(C.UnsignedLongTy));
llvm::PointerType *i8p = nullptr;
if (CGM.getLangOpts().OpenCL)
  i8p =
    llvm::Type::getInt8PtrTy(
         CGM.getLLVMContext(), C.getTargetAddressSpace(LangAS::opencl_constant));
else
  i8p = CGM.VoidPtrTy;

std::string descName;

// If an equivalent block descriptor global variable exists, return it.
if (C.getLangOpts().ObjC &&
    CGM.getLangOpts().getGC() == LangOptions::NonGC) {
  descName = getBlockDescriptorName(blockInfo, CGM);
  if (llvm::GlobalValue *desc = CGM.getModule().getNamedValue(descName))
    return llvm::ConstantExpr::getBitCast(desc,
                                          CGM.getBlockDescriptorType());
}

// If there isn't an equivalent block descriptor global variable, create a new
// one.
ConstantInitBuilder builder(CGM);
auto elements = builder.beginStruct();

// reserved
elements.addInt(ulong, 0);

// Size
// FIXME: What is the right way to say this doesn't fit?  We should give
// a user diagnostic in that case.  Better fix would be to change the
// API to size_t.
elements.addInt(ulong, blockInfo.BlockSize.getQuantity());

// Optional copy/dispose helpers.
bool hasInternalHelper = false;
if (blockInfo.needsCopyDisposeHelpers()) {
  // copy_func_helper_decl
  llvm::Constant *copyHelper = buildCopyHelper(CGM, blockInfo);
  elements.add(copyHelper);

  // destroy_func_decl
  llvm::Constant *disposeHelper = buildDisposeHelper(CGM, blockInfo);
  elements.add(disposeHelper);

  if (cast<llvm::Function>(copyHelper->getOperand(0))->hasInternalLinkage() ||
      cast<llvm::Function>(disposeHelper->getOperand(0))
          ->hasInternalLinkage())
    hasInternalHelper = true;
}

// Signature.  Mandatory ObjC-style method descriptor @encode sequence.
std::string typeAtEncoding =
  CGM.getContext().getObjCEncodingForBlock(blockInfo.getBlockExpr());
elements.add(llvm::ConstantExpr::getBitCast(
  CGM.GetAddrOfConstantCString(typeAtEncoding).getPointer(), i8p));

// GC layout.
if (C.getLangOpts().ObjC) {
  if (CGM.getLangOpts().getGC() != LangOptions::NonGC)
    elements.add(CGM.getObjCRuntime().BuildGCBlockLayout(CGM, blockInfo));
  else
    elements.add(CGM.getObjCRuntime().BuildRCBlockLayout(CGM, blockInfo));
}
else
  elements.addNullPointer(i8p);

unsigned AddrSpace = 0;
if (C.getLangOpts().OpenCL)
  AddrSpace = C.getTargetAddressSpace(LangAS::opencl_constant);

llvm::GlobalValue::LinkageTypes linkage;
if (descName.empty()) {
  linkage = llvm::GlobalValue::InternalLinkage;
  descName = "__block_descriptor_tmp";
} else if (hasInternalHelper) {
  // If either the copy helper or the dispose helper has internal linkage,
  // the block descriptor must have internal linkage too.
  linkage = llvm::GlobalValue::InternalLinkage;
} else {
  linkage = llvm::GlobalValue::LinkOnceODRLinkage;
}

llvm::GlobalVariable *global =
    elements.finishAndCreateGlobal(descName, CGM.getPointerAlign(),
                                   /*constant*/ true, linkage, AddrSpace);

if (linkage == llvm::GlobalValue::LinkOnceODRLinkage) {
  if (CGM.supportsCOMDAT())
    global->setComdat(CGM.getModule().getOrInsertComdat(descName));
  global->setVisibility(llvm::GlobalValue::HiddenVisibility);
  global->setUnnamedAddr(llvm::GlobalValue::UnnamedAddr::Global);
}

return llvm::ConstantExpr::getBitCast(global, CGM.getBlockDescriptorType());
285}

287/*
Purely notional variadic template describing the layout of a block.

template <class _ResultType, class... _ParamTypes, class... _CaptureTypes>
struct Block_literal {
  /// Initialized to one of:
  ///   extern void *_NSConcreteStackBlock[];
  ///   extern void *_NSConcreteGlobalBlock[];
  ///
  /// In theory, we could start one off malloc'ed by setting
  /// BLOCK_NEEDS_FREE, giving it a refcount of 1, and using
  /// this isa:
  ///   extern void *_NSConcreteMallocBlock[];
  struct objc_class *isa;

  /// These are the flags (with corresponding bit number) that the
  /// compiler is actually supposed to know about.
  ///  23. BLOCK_IS_NOESCAPE - indicates that the block is non-escaping
  ///  25. BLOCK_HAS_COPY_DISPOSE - indicates that the block
  ///   descriptor provides copy and dispose helper functions
  ///  26. BLOCK_HAS_CXX_OBJ - indicates that there's a captured
  ///   object with a nontrivial destructor or copy constructor
  ///  28. BLOCK_IS_GLOBAL - indicates that the block is allocated
  ///   as global memory
  ///  29. BLOCK_USE_STRET - indicates that the block function
  ///   uses stret, which objc_msgSend needs to know about
  ///  30. BLOCK_HAS_SIGNATURE - indicates that the block has an
  ///   @encoded signature string
  /// And we're not supposed to manipulate these:
  ///  24. BLOCK_NEEDS_FREE - indicates that the block has been moved
  ///   to malloc'ed memory
  ///  27. BLOCK_IS_GC - indicates that the block has been moved to
  ///   to GC-allocated memory
  /// Additionally, the bottom 16 bits are a reference count which
  /// should be zero on the stack.
  int flags;

  /// Reserved;  should be zero-initialized.
  int reserved;

  /// Function pointer generated from block literal.
  _ResultType (*invoke)(Block_literal *, _ParamTypes...);

  /// Block description metadata generated from block literal.
  struct Block_descriptor *block_descriptor;

  /// Captured values follow.
  _CapturesTypes captures...;
};
*/

338namespace {
/// A chunk of data that we actually have to capture in the block.
struct BlockLayoutChunk {
  CharUnits Alignment;
  CharUnits Size;
  Qualifiers::ObjCLifetime Lifetime;
  const BlockDecl::Capture *Capture; // null for 'this'
  llvm::Type *Type;
  QualType FieldType;

  BlockLayoutChunk(CharUnits align, CharUnits size,
                   Qualifiers::ObjCLifetime lifetime,
                   const BlockDecl::Capture *capture,
                   llvm::Type *type, QualType fieldType)
    : Alignment(align), Size(size), Lifetime(lifetime),
      Capture(capture), Type(type), FieldType(fieldType) {}

  /// Tell the block info that this chunk has the given field index.
  void setIndex(CGBlockInfo &info, unsigned index, CharUnits offset) {
    if (!Capture) {
      info.CXXThisIndex = index;
      info.CXXThisOffset = offset;
    } else {
      auto C = CGBlockInfo::Capture::makeIndex(index, offset, FieldType);
      info.Captures.insert({Capture->getVariable(), C});
    }
  }
};

/// Order by 1) all __strong together 2) next, all byfref together 3) next,
/// all __weak together. Preserve descending alignment in all situations.
bool operator<(const BlockLayoutChunk &left, const BlockLayoutChunk &right) {
  if (left.Alignment != right.Alignment)
    return left.Alignment > right.Alignment;

  auto getPrefOrder = [](const BlockLayoutChunk &chunk) {
    if (chunk.Capture && chunk.Capture->isByRef())
      return 1;
    if (chunk.Lifetime == Qualifiers::OCL_Strong)
      return 0;
    if (chunk.Lifetime == Qualifiers::OCL_Weak)
      return 2;
    return 3;
  };

  return getPrefOrder(left) < getPrefOrder(right);
}
385} // end anonymous namespace

387/// Determines if the given type is safe for constant capture in C++.
388static bool isSafeForCXXConstantCapture(QualType type) {
const RecordType *recordType =
  type->getBaseElementTypeUnsafe()->getAs<RecordType>();

// Only records can be unsafe.
if (!recordType) return true;

const auto *record = cast<CXXRecordDecl>(recordType->getDecl());

// Maintain semantics for classes with non-trivial dtors or copy ctors.
if (!record->hasTrivialDestructor()) return false;
if (record->hasNonTrivialCopyConstructor()) return false;

// Otherwise, we just have to make sure there aren't any mutable
// fields that might have changed since initialization.
return !record->hasMutableFields();
404}

406/// It is illegal to modify a const object after initialization.
407/// Therefore, if a const object has a constant initializer, we don't
408/// actually need to keep storage for it in the block; we'll just
409/// rematerialize it at the start of the block function.  This is
410/// acceptable because we make no promises about address stability of
411/// captured variables.
412static llvm::Constant *tryCaptureAsConstant(CodeGenModule &CGM,
                                          CodeGenFunction *CGF,
                                          const VarDecl *var) {
// Return if this is a function parameter. We shouldn't try to
// rematerialize default arguments of function parameters.
if (isa<ParmVarDecl>(var))
  return nullptr;

QualType type = var->getType();

// We can only do this if the variable is const.
if (!type.isConstQualified()) return nullptr;

// Furthermore, in C++ we have to worry about mutable fields:
// C++ [dcl.type.cv]p4:
//   Except that any class member declared mutable can be
//   modified, any attempt to modify a const object during its
//   lifetime results in undefined behavior.
if (CGM.getLangOpts().CPlusPlus && !isSafeForCXXConstantCapture(type))
  return nullptr;

// If the variable doesn't have any initializer (shouldn't this be
// invalid?), it's not clear what we should do.  Maybe capture as
// zero?
const Expr *init = var->getInit();
if (!init) return nullptr;

return ConstantEmitter(CGM, CGF).tryEmitAbstractForInitializer(*var);
440}

442/// Get the low bit of a nonzero character count.  This is the
443/// alignment of the nth byte if the 0th byte is universally aligned.
444static CharUnits getLowBit(CharUnits v) {
return CharUnits::fromQuantity(v.getQuantity() & (~v.getQuantity() + 1));
446}

448static void initializeForBlockHeader(CodeGenModule &CGM, CGBlockInfo &info,
                           SmallVectorImpl<llvm::Type*> &elementTypes) {

assert(elementTypes.empty())((void)0);
if (CGM.getLangOpts().OpenCL) {
  // The header is basically 'struct { int; int; generic void *;
  // custom_fields; }'. Assert that struct is packed.
  auto GenericAS =
      CGM.getContext().getTargetAddressSpace(LangAS::opencl_generic);
  auto GenPtrAlign =
      CharUnits::fromQuantity(CGM.getTarget().getPointerAlign(GenericAS) / 8);
  auto GenPtrSize =
      CharUnits::fromQuantity(CGM.getTarget().getPointerWidth(GenericAS) / 8);
  assert(CGM.getIntSize() <= GenPtrSize)((void)0);
  assert(CGM.getIntAlign() <= GenPtrAlign)((void)0);
  assert((2 * CGM.getIntSize()).isMultipleOf(GenPtrAlign))((void)0);
  elementTypes.push_back(CGM.IntTy); /* total size */
  elementTypes.push_back(CGM.IntTy); /* align */
  elementTypes.push_back(
      CGM.getOpenCLRuntime()
          .getGenericVoidPointerType()); /* invoke function */
  unsigned Offset =
      2 * CGM.getIntSize().getQuantity() + GenPtrSize.getQuantity();
  unsigned BlockAlign = GenPtrAlign.getQuantity();
  if (auto *Helper =
          CGM.getTargetCodeGenInfo().getTargetOpenCLBlockHelper()) {
    for (auto I : Helper->getCustomFieldTypes()) /* custom fields */ {
      // TargetOpenCLBlockHelp needs to make sure the struct is packed.
      // If necessary, add padding fields to the custom fields.
      unsigned Align = CGM.getDataLayout().getABITypeAlignment(I);
      if (BlockAlign < Align)
        BlockAlign = Align;
      assert(Offset % Align == 0)((void)0);
      Offset += CGM.getDataLayout().getTypeAllocSize(I);
      elementTypes.push_back(I);
    }
  }
  info.BlockAlign = CharUnits::fromQuantity(BlockAlign);
  info.BlockSize = CharUnits::fromQuantity(Offset);
} else {
  // The header is basically 'struct { void *; int; int; void *; void *; }'.
  // Assert that the struct is packed.
  assert(CGM.getIntSize() <= CGM.getPointerSize())((void)0);
  assert(CGM.getIntAlign() <= CGM.getPointerAlign())((void)0);
  assert((2 * CGM.getIntSize()).isMultipleOf(CGM.getPointerAlign()))((void)0);
  info.BlockAlign = CGM.getPointerAlign();
  info.BlockSize = 3 * CGM.getPointerSize() + 2 * CGM.getIntSize();
  elementTypes.push_back(CGM.VoidPtrTy);
  elementTypes.push_back(CGM.IntTy);
  elementTypes.push_back(CGM.IntTy);
  elementTypes.push_back(CGM.VoidPtrTy);
  elementTypes.push_back(CGM.getBlockDescriptorType());
}
501}

503static QualType getCaptureFieldType(const CodeGenFunction &CGF,
                                  const BlockDecl::Capture &CI) {
const VarDecl *VD = CI.getVariable();

// If the variable is captured by an enclosing block or lambda expression,
// use the type of the capture field.
if (CGF.BlockInfo && CI.isNested())
  return CGF.BlockInfo->getCapture(VD).fieldType();
if (auto *FD = CGF.LambdaCaptureFields.lookup(VD))
  return FD->getType();
// If the captured variable is a non-escaping __block variable, the field
// type is the reference type. If the variable is a __block variable that
// already has a reference type, the field type is the variable's type.
return VD->isNonEscapingByref() ?
       CGF.getContext().getLValueReferenceType(VD->getType()) : VD->getType();
518}

520/// Compute the layout of the given block.  Attempts to lay the block
521/// out with minimal space requirements.
522static void computeBlockInfo(CodeGenModule &CGM, CodeGenFunction *CGF,
                           CGBlockInfo &info) {
ASTContext &C = CGM.getContext();
const BlockDecl *block = info.getBlockDecl();

SmallVector<llvm::Type*, 8> elementTypes;
initializeForBlockHeader(CGM, info, elementTypes);
bool hasNonConstantCustomFields = false;
if (auto *OpenCLHelper =
4
←
Assuming 'OpenCLHelper' is null→
5
←
Taking false branch→
        CGM.getTargetCodeGenInfo().getTargetOpenCLBlockHelper())
  hasNonConstantCustomFields =
      !OpenCLHelper->areAllCustomFieldValuesConstant(info);
if (!block->hasCaptures() && !hasNonConstantCustomFields) {
  info.StructureType =
    llvm::StructType::get(CGM.getLLVMContext(), elementTypes, true);
  info.CanBeGlobal = true;
  return;
}
else if (C.getLangOpts().ObjC &&
6
←
Assuming field 'ObjC' is 0→
         CGM.getLangOpts().getGC() == LangOptions::NonGC)
  info.HasCapturedVariableLayout = true;

// Collect the layout chunks.
SmallVector<BlockLayoutChunk, 16> layout;
layout.reserve(block->capturesCXXThis() +
               (block->capture_end() - block->capture_begin()));

CharUnits maxFieldAlign;
7
←
Calling defaulted default constructor for 'CharUnits'→
9
←
Returning from default constructor for 'CharUnits'→

// First, 'this'.
if (block->capturesCXXThis()) {
10
←
Assuming the condition is false→
11
←
Taking false branch→
  assert(CGF && CGF->CurFuncDecl && isa<CXXMethodDecl>(CGF->CurFuncDecl) &&((void)0)
         "Can't capture 'this' outside a method")((void)0);
  QualType thisType = cast<CXXMethodDecl>(CGF->CurFuncDecl)->getThisType();

  // Theoretically, this could be in a different address space, so
  // don't assume standard pointer size/align.
  llvm::Type *llvmType = CGM.getTypes().ConvertType(thisType);
  auto TInfo = CGM.getContext().getTypeInfoInChars(thisType);
  maxFieldAlign = std::max(maxFieldAlign, TInfo.Align);

  layout.push_back(BlockLayoutChunk(TInfo.Align, TInfo.Width,
                                    Qualifiers::OCL_None,
                                    nullptr, llvmType, thisType));
}

// Next, all the block captures.
for (const auto &CI : block->captures()) {
12
←
Assuming '__begin1' is equal to '__end1'→
  const VarDecl *variable = CI.getVariable();

  if (CI.isEscapingByref()) {
    // We have to copy/dispose of the __block reference.
    info.NeedsCopyDispose = true;

    // Just use void* instead of a pointer to the byref type.
    CharUnits align = CGM.getPointerAlign();
    maxFieldAlign = std::max(maxFieldAlign, align);

    // Since a __block variable cannot be captured by lambdas, its type and
    // the capture field type should always match.
    assert(CGF && getCaptureFieldType(*CGF, CI) == variable->getType() &&((void)0)
           "capture type differs from the variable type")((void)0);
    layout.push_back(BlockLayoutChunk(align, CGM.getPointerSize(),
                                      Qualifiers::OCL_None, &CI,
                                      CGM.VoidPtrTy, variable->getType()));
    continue;
  }

  // Otherwise, build a layout chunk with the size and alignment of
  // the declaration.
  if (llvm::Constant *constant = tryCaptureAsConstant(CGM, CGF, variable)) {
    info.Captures[variable] = CGBlockInfo::Capture::makeConstant(constant);
    continue;
  }

  QualType VT = getCaptureFieldType(*CGF, CI);

  // If we have a lifetime qualifier, honor it for capture purposes.
  // That includes *not* copying it if it's __unsafe_unretained.
  Qualifiers::ObjCLifetime lifetime = VT.getObjCLifetime();
  if (lifetime) {
    switch (lifetime) {
    case Qualifiers::OCL_None: llvm_unreachable("impossible")__builtin_unreachable();
    case Qualifiers::OCL_ExplicitNone:
    case Qualifiers::OCL_Autoreleasing:
      break;

    case Qualifiers::OCL_Strong:
    case Qualifiers::OCL_Weak:
      info.NeedsCopyDispose = true;
    }

  // Block pointers require copy/dispose.  So do Objective-C pointers.
  } else if (VT->isObjCRetainableType()) {
    // But honor the inert __unsafe_unretained qualifier, which doesn't
    // actually make it into the type system.
     if (VT->isObjCInertUnsafeUnretainedType()) {
      lifetime = Qualifiers::OCL_ExplicitNone;
    } else {
      info.NeedsCopyDispose = true;
      // used for mrr below.
      lifetime = Qualifiers::OCL_Strong;
    }

  // So do types that require non-trivial copy construction.
  } else if (CI.hasCopyExpr()) {
    info.NeedsCopyDispose = true;
    info.HasCXXObject = true;
    if (!VT->getAsCXXRecordDecl()->isExternallyVisible())
      info.CapturesNonExternalType = true;

  // So do C structs that require non-trivial copy construction or
  // destruction.
  } else if (VT.isNonTrivialToPrimitiveCopy() == QualType::PCK_Struct ||
             VT.isDestructedType() == QualType::DK_nontrivial_c_struct) {
    info.NeedsCopyDispose = true;

  // And so do types with destructors.
  } else if (CGM.getLangOpts().CPlusPlus) {
    if (const CXXRecordDecl *record = VT->getAsCXXRecordDecl()) {
      if (!record->hasTrivialDestructor()) {
        info.HasCXXObject = true;
        info.NeedsCopyDispose = true;
        if (!record->isExternallyVisible())
          info.CapturesNonExternalType = true;
      }
    }
  }

  CharUnits size = C.getTypeSizeInChars(VT);
  CharUnits align = C.getDeclAlign(variable);

  maxFieldAlign = std::max(maxFieldAlign, align);

  llvm::Type *llvmType =
    CGM.getTypes().ConvertTypeForMem(VT);

  layout.push_back(
      BlockLayoutChunk(align, size, lifetime, &CI, llvmType, VT));
}

// If that was everything, we're done here.
if (layout.empty()) {
13
←
Taking false branch→
  info.StructureType =
    llvm::StructType::get(CGM.getLLVMContext(), elementTypes, true);
  info.CanBeGlobal = true;
  return;
}

// Sort the layout by alignment.  We have to use a stable sort here
// to get reproducible results.  There should probably be an
// llvm::array_pod_stable_sort.
llvm::stable_sort(layout);

// Needed for blocks layout info.
info.BlockHeaderForcedGapOffset = info.BlockSize;
info.BlockHeaderForcedGapSize = CharUnits::Zero();

CharUnits &blockSize = info.BlockSize;
info.BlockAlign = std::max(maxFieldAlign, info.BlockAlign);

// Assuming that the first byte in the header is maximally aligned,
// get the alignment of the first byte following the header.
CharUnits endAlign = getLowBit(blockSize);

// If the end of the header isn't satisfactorily aligned for the
// maximum thing, look for things that are okay with the header-end
// alignment, and keep appending them until we get something that's
// aligned right.  This algorithm is only guaranteed optimal if
// that condition is satisfied at some point; otherwise we can get
// things like:
//   header                 // next byte has alignment 4
//   something_with_size_5; // next byte has alignment 1
//   something_with_alignment_8;
// which has 7 bytes of padding, as opposed to the naive solution
// which might have less (?).
if (endAlign < maxFieldAlign) {
14
←
Taking true branch→
  SmallVectorImpl<BlockLayoutChunk>::iterator
    li = layout.begin() + 1, le = layout.end();

  // Look for something that the header end is already
  // satisfactorily aligned for.
  for (; li != le && endAlign < li->Alignment; ++li)
15
←
Assuming 'li' is equal to 'le'→
    ;

  // If we found something that's naturally aligned for the end of
  // the header, keep adding things...
  if (li != le) {
16
←
Assuming 'li' is equal to 'le'→
17
←
Taking false branch→
    SmallVectorImpl<BlockLayoutChunk>::iterator first = li;
    for (; li != le; ++li) {
      assert(endAlign >= li->Alignment)((void)0);

      li->setIndex(info, elementTypes.size(), blockSize);
      elementTypes.push_back(li->Type);
      blockSize += li->Size;
      endAlign = getLowBit(blockSize);

      // ...until we get to the alignment of the maximum field.
      if (endAlign >= maxFieldAlign) {
        break;
      }
    }
    // Don't re-append everything we just appended.
    layout.erase(first, li);
  }
}

assert(endAlign == getLowBit(blockSize))((void)0);

// At this point, we just have to add padding if the end align still
// isn't aligned right.
if (endAlign < maxFieldAlign) {
18
←
Taking true branch→
  CharUnits newBlockSize = blockSize.alignTo(maxFieldAlign);
19
←
Calling 'CharUnits::alignTo'→
  CharUnits padding = newBlockSize - blockSize;

  // If we haven't yet added any fields, remember that there was an
  // initial gap; this need to go into the block layout bit map.
  if (blockSize == info.BlockHeaderForcedGapOffset) {
    info.BlockHeaderForcedGapSize = padding;
  }

  elementTypes.push_back(llvm::ArrayType::get(CGM.Int8Ty,
                                              padding.getQuantity()));
  blockSize = newBlockSize;
  endAlign = getLowBit(blockSize); // might be > maxFieldAlign
}

assert(endAlign >= maxFieldAlign)((void)0);
assert(endAlign == getLowBit(blockSize))((void)0);
// Slam everything else on now.  This works because they have
// strictly decreasing alignment and we expect that size is always a
// multiple of alignment.
for (SmallVectorImpl<BlockLayoutChunk>::iterator
       li = layout.begin(), le = layout.end(); li != le; ++li) {
  if (endAlign < li->Alignment) {
    // size may not be multiple of alignment. This can only happen with
    // an over-aligned variable. We will be adding a padding field to
    // make the size be multiple of alignment.
    CharUnits padding = li->Alignment - endAlign;
    elementTypes.push_back(llvm::ArrayType::get(CGM.Int8Ty,
                                                padding.getQuantity()));
    blockSize += padding;
    endAlign = getLowBit(blockSize);
  }
  assert(endAlign >= li->Alignment)((void)0);
  li->setIndex(info, elementTypes.size(), blockSize);
  elementTypes.push_back(li->Type);
  blockSize += li->Size;
  endAlign = getLowBit(blockSize);
}

info.StructureType =
  llvm::StructType::get(CGM.getLLVMContext(), elementTypes, true);
775}

777/// Emit a block literal expression in the current function.
778llvm::Value *CodeGenFunction::EmitBlockLiteral(const BlockExpr *blockExpr) {
// If the block has no captures, we won't have a pre-computed
// layout for it.
if (!blockExpr->getBlockDecl()->hasCaptures())
  // The block literal is emitted as a global variable, and the block invoke
  // function has to be extracted from its initializer.
  if (llvm::Constant *Block = CGM.getAddrOfGlobalBlockIfEmitted(blockExpr))
    return Block;

CGBlockInfo blockInfo(blockExpr->getBlockDecl(), CurFn->getName());
computeBlockInfo(CGM, this, blockInfo);
blockInfo.BlockExpression = blockExpr;
if (!blockInfo.CanBeGlobal)
  blockInfo.LocalAddress = CreateTempAlloca(blockInfo.StructureType,
                                            blockInfo.BlockAlign, "block");
return EmitBlockLiteral(blockInfo);
794}

796llvm::Value *CodeGenFunction::EmitBlockLiteral(const CGBlockInfo &blockInfo) {
bool IsOpenCL = CGM.getContext().getLangOpts().OpenCL;
auto GenVoidPtrTy =
    IsOpenCL ? CGM.getOpenCLRuntime().getGenericVoidPointerType() : VoidPtrTy;
LangAS GenVoidPtrAddr = IsOpenCL ? LangAS::opencl_generic : LangAS::Default;
auto GenVoidPtrSize = CharUnits::fromQuantity(
    CGM.getTarget().getPointerWidth(
        CGM.getContext().getTargetAddressSpace(GenVoidPtrAddr)) /
    8);
// Using the computed layout, generate the actual block function.
bool isLambdaConv = blockInfo.getBlockDecl()->isConversionFromLambda();
CodeGenFunction BlockCGF{CGM, true};
BlockCGF.SanOpts = SanOpts;
auto *InvokeFn = BlockCGF.GenerateBlockFunction(
    CurGD, blockInfo, LocalDeclMap, isLambdaConv, blockInfo.CanBeGlobal);
auto *blockFn = llvm::ConstantExpr::getPointerCast(InvokeFn, GenVoidPtrTy);

// If there is nothing to capture, we can emit this as a global block.
if (blockInfo.CanBeGlobal)
  return CGM.getAddrOfGlobalBlockIfEmitted(blockInfo.BlockExpression);

// Otherwise, we have to emit this as a local block.

Address blockAddr = blockInfo.LocalAddress;
assert(blockAddr.isValid() && "block has no address!")((void)0);

llvm::Constant *isa;
llvm::Constant *descriptor;
BlockFlags flags;
if (!IsOpenCL) {
  // If the block is non-escaping, set field 'isa 'to NSConcreteGlobalBlock
  // and set the BLOCK_IS_GLOBAL bit of field 'flags'. Copying a non-escaping
  // block just returns the original block and releasing it is a no-op.
  llvm::Constant *blockISA = blockInfo.getBlockDecl()->doesNotEscape()
                                 ? CGM.getNSConcreteGlobalBlock()
                                 : CGM.getNSConcreteStackBlock();
  isa = llvm::ConstantExpr::getBitCast(blockISA, VoidPtrTy);

  // Build the block descriptor.
  descriptor = buildBlockDescriptor(CGM, blockInfo);

  // Compute the initial on-stack block flags.
  flags = BLOCK_HAS_SIGNATURE;
  if (blockInfo.HasCapturedVariableLayout)
    flags |= BLOCK_HAS_EXTENDED_LAYOUT;
  if (blockInfo.needsCopyDisposeHelpers())
    flags |= BLOCK_HAS_COPY_DISPOSE;
  if (blockInfo.HasCXXObject)
    flags |= BLOCK_HAS_CXX_OBJ;
  if (blockInfo.UsesStret)
    flags |= BLOCK_USE_STRET;
  if (blockInfo.getBlockDecl()->doesNotEscape())
    flags |= BLOCK_IS_NOESCAPE | BLOCK_IS_GLOBAL;
}

auto projectField = [&](unsigned index, const Twine &name) -> Address {
  return Builder.CreateStructGEP(blockAddr, index, name);
};
auto storeField = [&](llvm::Value *value, unsigned index, const Twine &name) {
  Builder.CreateStore(value, projectField(index, name));
};

// Initialize the block header.
{
  // We assume all the header fields are densely packed.
  unsigned index = 0;
  CharUnits offset;
  auto addHeaderField = [&](llvm::Value *value, CharUnits size,
                            const Twine &name) {
    storeField(value, index, name);
    offset += size;
    index++;
  };

  if (!IsOpenCL) {
    addHeaderField(isa, getPointerSize(), "block.isa");
    addHeaderField(llvm::ConstantInt::get(IntTy, flags.getBitMask()),
                   getIntSize(), "block.flags");
    addHeaderField(llvm::ConstantInt::get(IntTy, 0), getIntSize(),
                   "block.reserved");
  } else {
    addHeaderField(
        llvm::ConstantInt::get(IntTy, blockInfo.BlockSize.getQuantity()),
        getIntSize(), "block.size");
    addHeaderField(
        llvm::ConstantInt::get(IntTy, blockInfo.BlockAlign.getQuantity()),
        getIntSize(), "block.align");
  }
  addHeaderField(blockFn, GenVoidPtrSize, "block.invoke");
  if (!IsOpenCL)
    addHeaderField(descriptor, getPointerSize(), "block.descriptor");
  else if (auto *Helper =
               CGM.getTargetCodeGenInfo().getTargetOpenCLBlockHelper()) {
    for (auto I : Helper->getCustomFieldValues(*this, blockInfo)) {
      addHeaderField(
          I.first,
          CharUnits::fromQuantity(
              CGM.getDataLayout().getTypeAllocSize(I.first->getType())),
          I.second);
    }
  }
}

// Finally, capture all the values into the block.
const BlockDecl *blockDecl = blockInfo.getBlockDecl();

// First, 'this'.
if (blockDecl->capturesCXXThis()) {
  Address addr =
      projectField(blockInfo.CXXThisIndex, "block.captured-this.addr");
  Builder.CreateStore(LoadCXXThis(), addr);
}

// Next, captured variables.
for (const auto &CI : blockDecl->captures()) {
  const VarDecl *variable = CI.getVariable();
  const CGBlockInfo::Capture &capture = blockInfo.getCapture(variable);

  // Ignore constant captures.
  if (capture.isConstant()) continue;

  QualType type = capture.fieldType();

  // This will be a [[type]]*, except that a byref entry will just be
  // an i8**.
  Address blockField = projectField(capture.getIndex(), "block.captured");

  // Compute the address of the thing we're going to move into the
  // block literal.
  Address src = Address::invalid();

  if (blockDecl->isConversionFromLambda()) {
    // The lambda capture in a lambda's conversion-to-block-pointer is
    // special; we'll simply emit it directly.
    src = Address::invalid();
  } else if (CI.isEscapingByref()) {
    if (BlockInfo && CI.isNested()) {
      // We need to use the capture from the enclosing block.
      const CGBlockInfo::Capture &enclosingCapture =
          BlockInfo->getCapture(variable);

      // This is a [[type]]*, except that a byref entry will just be an i8**.
      src = Builder.CreateStructGEP(LoadBlockStruct(),
                                    enclosingCapture.getIndex(),
                                    "block.capture.addr");
    } else {
      auto I = LocalDeclMap.find(variable);
      assert(I != LocalDeclMap.end())((void)0);
      src = I->second;
    }
  } else {
    DeclRefExpr declRef(getContext(), const_cast<VarDecl *>(variable),
                        /*RefersToEnclosingVariableOrCapture*/ CI.isNested(),
                        type.getNonReferenceType(), VK_LValue,
                        SourceLocation());
    src = EmitDeclRefLValue(&declRef).getAddress(*this);
  };

  // For byrefs, we just write the pointer to the byref struct into
  // the block field.  There's no need to chase the forwarding
  // pointer at this point, since we're building something that will
  // live a shorter life than the stack byref anyway.
  if (CI.isEscapingByref()) {
    // Get a void* that points to the byref struct.
    llvm::Value *byrefPointer;
    if (CI.isNested())
      byrefPointer = Builder.CreateLoad(src, "byref.capture");
    else
      byrefPointer = Builder.CreateBitCast(src.getPointer(), VoidPtrTy);

    // Write that void* into the capture field.
    Builder.CreateStore(byrefPointer, blockField);

  // If we have a copy constructor, evaluate that into the block field.
  } else if (const Expr *copyExpr = CI.getCopyExpr()) {
    if (blockDecl->isConversionFromLambda()) {
      // If we have a lambda conversion, emit the expression
      // directly into the block instead.
      AggValueSlot Slot =
          AggValueSlot::forAddr(blockField, Qualifiers(),
                                AggValueSlot::IsDestructed,
                                AggValueSlot::DoesNotNeedGCBarriers,
                                AggValueSlot::IsNotAliased,
                                AggValueSlot::DoesNotOverlap);
      EmitAggExpr(copyExpr, Slot);
    } else {
      EmitSynthesizedCXXCopyCtor(blockField, src, copyExpr);
    }

  // If it's a reference variable, copy the reference into the block field.
  } else if (type->isReferenceType()) {
    Builder.CreateStore(src.getPointer(), blockField);

  // If type is const-qualified, copy the value into the block field.
  } else if (type.isConstQualified() &&
             type.getObjCLifetime() == Qualifiers::OCL_Strong &&
             CGM.getCodeGenOpts().OptimizationLevel != 0) {
    llvm::Value *value = Builder.CreateLoad(src, "captured");
    Builder.CreateStore(value, blockField);

  // If this is an ARC __strong block-pointer variable, don't do a
  // block copy.
  //
  // TODO: this can be generalized into the normal initialization logic:
  // we should never need to do a block-copy when initializing a local
  // variable, because the local variable's lifetime should be strictly
  // contained within the stack block's.
  } else if (type.getObjCLifetime() == Qualifiers::OCL_Strong &&
             type->isBlockPointerType()) {
    // Load the block and do a simple retain.
    llvm::Value *value = Builder.CreateLoad(src, "block.captured_block");
    value = EmitARCRetainNonBlock(value);

    // Do a primitive store to the block field.
    Builder.CreateStore(value, blockField);

  // Otherwise, fake up a POD copy into the block field.
  } else {
    // Fake up a new variable so that EmitScalarInit doesn't think
    // we're referring to the variable in its own initializer.
    ImplicitParamDecl BlockFieldPseudoVar(getContext(), type,
                                          ImplicitParamDecl::Other);

    // We use one of these or the other depending on whether the
    // reference is nested.
    DeclRefExpr declRef(getContext(), const_cast<VarDecl *>(variable),
                        /*RefersToEnclosingVariableOrCapture*/ CI.isNested(),
                        type, VK_LValue, SourceLocation());

    ImplicitCastExpr l2r(ImplicitCastExpr::OnStack, type, CK_LValueToRValue,
                         &declRef, VK_PRValue, FPOptionsOverride());
    // FIXME: Pass a specific location for the expr init so that the store is
    // attributed to a reasonable location - otherwise it may be attributed to
    // locations of subexpressions in the initialization.
    EmitExprAsInit(&l2r, &BlockFieldPseudoVar,
                   MakeAddrLValue(blockField, type, AlignmentSource::Decl),
                   /*captured by init*/ false);
  }

  // Push a cleanup for the capture if necessary.
  if (!blockInfo.NeedsCopyDispose)
    continue;

  // Ignore __block captures; there's nothing special in the on-stack block
  // that we need to do for them.
  if (CI.isByRef())
    continue;

  // Ignore objects that aren't destructed.
  QualType::DestructionKind dtorKind = type.isDestructedType();
  if (dtorKind == QualType::DK_none)
    continue;

  CodeGenFunction::Destroyer *destroyer;

  // Block captures count as local values and have imprecise semantics.
  // They also can't be arrays, so need to worry about that.
  //
  // For const-qualified captures, emit clang.arc.use to ensure the captured
  // object doesn't get released while we are still depending on its validity
  // within the block.
  if (type.isConstQualified() &&
      type.getObjCLifetime() == Qualifiers::OCL_Strong &&
      CGM.getCodeGenOpts().OptimizationLevel != 0) {
    assert(CGM.getLangOpts().ObjCAutoRefCount &&((void)0)
           "expected ObjC ARC to be enabled")((void)0);
    destroyer = emitARCIntrinsicUse;
  } else if (dtorKind == QualType::DK_objc_strong_lifetime) {
    destroyer = destroyARCStrongImprecise;
  } else {
    destroyer = getDestroyer(dtorKind);
  }

  CleanupKind cleanupKind = NormalCleanup;
  bool useArrayEHCleanup = needsEHCleanup(dtorKind);
  if (useArrayEHCleanup)
    cleanupKind = NormalAndEHCleanup;

  // Extend the lifetime of the capture to the end of the scope enclosing the
  // block expression except when the block decl is in the list of RetExpr's
  // cleanup objects, in which case its lifetime ends after the full
  // expression.
  auto IsBlockDeclInRetExpr = [&]() {
    auto *EWC = llvm::dyn_cast_or_null<ExprWithCleanups>(RetExpr);
    if (EWC)
      for (auto &C : EWC->getObjects())
        if (auto *BD = C.dyn_cast<BlockDecl *>())
          if (BD == blockDecl)
            return true;
    return false;
  };

  if (IsBlockDeclInRetExpr())
    pushDestroy(cleanupKind, blockField, type, destroyer, useArrayEHCleanup);
  else
    pushLifetimeExtendedDestroy(cleanupKind, blockField, type, destroyer,
                                useArrayEHCleanup);
}

// Cast to the converted block-pointer type, which happens (somewhat
// unfortunately) to be a pointer to function type.
llvm::Value *result = Builder.CreatePointerCast(
    blockAddr.getPointer(), ConvertType(blockInfo.getBlockExpr()->getType()));

if (IsOpenCL) {
  CGM.getOpenCLRuntime().recordBlockInfo(blockInfo.BlockExpression, InvokeFn,
                                         result);
}

return result;
1106}


1109llvm::Type *CodeGenModule::getBlockDescriptorType() {
if (BlockDescriptorType)
  return BlockDescriptorType;

llvm::Type *UnsignedLongTy =
  getTypes().ConvertType(getContext().UnsignedLongTy);

// struct __block_descriptor {
//   unsigned long reserved;
//   unsigned long block_size;
//
//   // later, the following will be added
//
//   struct {
//     void (*copyHelper)();
//     void (*copyHelper)();
//   } helpers;                // !!! optional
//
//   const char *signature;   // the block signature
//   const char *layout;      // reserved
// };
BlockDescriptorType = llvm::StructType::create(
    "struct.__block_descriptor", UnsignedLongTy, UnsignedLongTy);

// Now form a pointer to that.
unsigned AddrSpace = 0;
if (getLangOpts().OpenCL)
  AddrSpace = getContext().getTargetAddressSpace(LangAS::opencl_constant);
BlockDescriptorType = llvm::PointerType::get(BlockDescriptorType, AddrSpace);
return BlockDescriptorType;
1139}

1141llvm::Type *CodeGenModule::getGenericBlockLiteralType() {
if (GenericBlockLiteralType)
  return GenericBlockLiteralType;

llvm::Type *BlockDescPtrTy = getBlockDescriptorType();

if (getLangOpts().OpenCL) {
  // struct __opencl_block_literal_generic {
  //   int __size;
  //   int __align;
  //   __generic void *__invoke;
  //   /* custom fields */
  // };
  SmallVector<llvm::Type *, 8> StructFields(
      {IntTy, IntTy, getOpenCLRuntime().getGenericVoidPointerType()});
  if (auto *Helper = getTargetCodeGenInfo().getTargetOpenCLBlockHelper()) {
    for (auto I : Helper->getCustomFieldTypes())
      StructFields.push_back(I);
  }
  GenericBlockLiteralType = llvm::StructType::create(
      StructFields, "struct.__opencl_block_literal_generic");
} else {
  // struct __block_literal_generic {
  //   void *__isa;
  //   int __flags;
  //   int __reserved;
  //   void (*__invoke)(void *);
  //   struct __block_descriptor *__descriptor;
  // };
  GenericBlockLiteralType =
      llvm::StructType::create("struct.__block_literal_generic", VoidPtrTy,
                               IntTy, IntTy, VoidPtrTy, BlockDescPtrTy);
}

return GenericBlockLiteralType;
1176}

1178RValue CodeGenFunction::EmitBlockCallExpr(const CallExpr *E,
                                        ReturnValueSlot ReturnValue) {
const auto *BPT = E->getCallee()->getType()->castAs<BlockPointerType>();
llvm::Value *BlockPtr = EmitScalarExpr(E->getCallee());
llvm::Type *GenBlockTy = CGM.getGenericBlockLiteralType();
llvm::Value *Func = nullptr;
QualType FnType = BPT->getPointeeType();
ASTContext &Ctx = getContext();
CallArgList Args;

if (getLangOpts().OpenCL) {
  // For OpenCL, BlockPtr is already casted to generic block literal.

  // First argument of a block call is a generic block literal casted to
  // generic void pointer, i.e. i8 addrspace(4)*
  llvm::Type *GenericVoidPtrTy =
      CGM.getOpenCLRuntime().getGenericVoidPointerType();
  llvm::Value *BlockDescriptor = Builder.CreatePointerCast(
      BlockPtr, GenericVoidPtrTy);
  QualType VoidPtrQualTy = Ctx.getPointerType(
      Ctx.getAddrSpaceQualType(Ctx.VoidTy, LangAS::opencl_generic));
  Args.add(RValue::get(BlockDescriptor), VoidPtrQualTy);
  // And the rest of the arguments.
  EmitCallArgs(Args, FnType->getAs<FunctionProtoType>(), E->arguments());

  // We *can* call the block directly unless it is a function argument.
  if (!isa<ParmVarDecl>(E->getCalleeDecl()))
    Func = CGM.getOpenCLRuntime().getInvokeFunction(E->getCallee());
  else {
    llvm::Value *FuncPtr = Builder.CreateStructGEP(GenBlockTy, BlockPtr, 2);
    Func = Builder.CreateAlignedLoad(GenericVoidPtrTy, FuncPtr,
                                     getPointerAlign());
  }
} else {
  // Bitcast the block literal to a generic block literal.
  BlockPtr = Builder.CreatePointerCast(
      BlockPtr, llvm::PointerType::get(GenBlockTy, 0), "block.literal");
  // Get pointer to the block invoke function
  llvm::Value *FuncPtr = Builder.CreateStructGEP(GenBlockTy, BlockPtr, 3);

  // First argument is a block literal casted to a void pointer
  BlockPtr = Builder.CreatePointerCast(BlockPtr, VoidPtrTy);
  Args.add(RValue::get(BlockPtr), Ctx.VoidPtrTy);
  // And the rest of the arguments.
  EmitCallArgs(Args, FnType->getAs<FunctionProtoType>(), E->arguments());

  // Load the function.
  Func = Builder.CreateAlignedLoad(VoidPtrTy, FuncPtr, getPointerAlign());
}

const FunctionType *FuncTy = FnType->castAs<FunctionType>();
const CGFunctionInfo &FnInfo =
  CGM.getTypes().arrangeBlockFunctionCall(Args, FuncTy);

// Cast the function pointer to the right type.
llvm::Type *BlockFTy = CGM.getTypes().GetFunctionType(FnInfo);

llvm::Type *BlockFTyPtr = llvm::PointerType::getUnqual(BlockFTy);
Func = Builder.CreatePointerCast(Func, BlockFTyPtr);

// Prepare the callee.
CGCallee Callee(CGCalleeInfo(), Func);

// And call the block.
return EmitCall(FnInfo, Callee, ReturnValue, Args);
1243}

1245Address CodeGenFunction::GetAddrOfBlockDecl(const VarDecl *variable) {
assert(BlockInfo && "evaluating block ref without block information?")((void)0);
const CGBlockInfo::Capture &capture = BlockInfo->getCapture(variable);

// Handle constant captures.
if (capture.isConstant()) return LocalDeclMap.find(variable)->second;

Address addr = Builder.CreateStructGEP(LoadBlockStruct(), capture.getIndex(),
                                       "block.capture.addr");

if (variable->isEscapingByref()) {
  // addr should be a void** right now.  Load, then cast the result
  // to byref*.

  auto &byrefInfo = getBlockByrefInfo(variable);
  addr = Address(Builder.CreateLoad(addr), byrefInfo.ByrefAlignment);

  auto byrefPointerType = llvm::PointerType::get(byrefInfo.Type, 0);
  addr = Builder.CreateBitCast(addr, byrefPointerType, "byref.addr");

  addr = emitBlockByrefAddress(addr, byrefInfo, /*follow*/ true,
                               variable->getName());
}

assert((!variable->isNonEscapingByref() ||((void)0)
        capture.fieldType()->isReferenceType()) &&((void)0)
       "the capture field of a non-escaping variable should have a "((void)0)
       "reference type")((void)0);
if (capture.fieldType()->isReferenceType())
  addr = EmitLoadOfReference(MakeAddrLValue(addr, capture.fieldType()));

return addr;
1277}

1279void CodeGenModule::setAddrOfGlobalBlock(const BlockExpr *BE,
                                       llvm::Constant *Addr) {
bool Ok = EmittedGlobalBlocks.insert(std::make_pair(BE, Addr)).second;
(void)Ok;
assert(Ok && "Trying to replace an already-existing global block!")((void)0);
1284}

1286llvm::Constant *
1287CodeGenModule::GetAddrOfGlobalBlock(const BlockExpr *BE,
                                  StringRef Name) {
if (llvm::Constant *Block = getAddrOfGlobalBlockIfEmitted(BE))
1
Assuming 'Block' is null→
2
←
Taking false branch→
  return Block;

CGBlockInfo blockInfo(BE->getBlockDecl(), Name);
blockInfo.BlockExpression = BE;

// Compute information about the layout, etc., of this block.
computeBlockInfo(*this, nullptr, blockInfo);
3
←
Calling 'computeBlockInfo'→

// Using that metadata, generate the actual block function.
{
  CodeGenFunction::DeclMapTy LocalDeclMap;
  CodeGenFunction(*this).GenerateBlockFunction(
      GlobalDecl(), blockInfo, LocalDeclMap,
      /*IsLambdaConversionToBlock*/ false, /*BuildGlobalBlock*/ true);
}

return getAddrOfGlobalBlockIfEmitted(BE);
1307}

1309static llvm::Constant *buildGlobalBlock(CodeGenModule &CGM,
                                      const CGBlockInfo &blockInfo,
                                      llvm::Constant *blockFn) {
assert(blockInfo.CanBeGlobal)((void)0);
// Callers should detect this case on their own: calling this function
// generally requires computing layout information, which is a waste of time
// if we've already emitted this block.
assert(!CGM.getAddrOfGlobalBlockIfEmitted(blockInfo.BlockExpression) &&((void)0)
       "Refusing to re-emit a global block.")((void)0);

// Generate the constants for the block literal initializer.
ConstantInitBuilder builder(CGM);
auto fields = builder.beginStruct();

bool IsOpenCL = CGM.getLangOpts().OpenCL;
bool IsWindows = CGM.getTarget().getTriple().isOSWindows();
if (!IsOpenCL) {
  // isa
  if (IsWindows)
    fields.addNullPointer(CGM.Int8PtrPtrTy);
  else
    fields.add(CGM.getNSConcreteGlobalBlock());

  // __flags
  BlockFlags flags = BLOCK_IS_GLOBAL | BLOCK_HAS_SIGNATURE;
  if (blockInfo.UsesStret)
    flags |= BLOCK_USE_STRET;

  fields.addInt(CGM.IntTy, flags.getBitMask());

  // Reserved
  fields.addInt(CGM.IntTy, 0);
} else {
  fields.addInt(CGM.IntTy, blockInfo.BlockSize.getQuantity());
  fields.addInt(CGM.IntTy, blockInfo.BlockAlign.getQuantity());
}

// Function
fields.add(blockFn);

if (!IsOpenCL) {
  // Descriptor
  fields.add(buildBlockDescriptor(CGM, blockInfo));
} else if (auto *Helper =
               CGM.getTargetCodeGenInfo().getTargetOpenCLBlockHelper()) {
  for (auto I : Helper->getCustomFieldValues(CGM, blockInfo)) {
    fields.add(I);
  }
}

unsigned AddrSpace = 0;
if (CGM.getContext().getLangOpts().OpenCL)
  AddrSpace = CGM.getContext().getTargetAddressSpace(LangAS::opencl_global);

llvm::GlobalVariable *literal = fields.finishAndCreateGlobal(
    "__block_literal_global", blockInfo.BlockAlign,
    /*constant*/ !IsWindows, llvm::GlobalVariable::InternalLinkage, AddrSpace);

literal->addAttribute("objc_arc_inert");

// Windows does not allow globals to be initialised to point to globals in
// different DLLs.  Any such variables must run code to initialise them.
if (IsWindows) {
  auto *Init = llvm::Function::Create(llvm::FunctionType::get(CGM.VoidTy,
        {}), llvm::GlobalValue::InternalLinkage, ".block_isa_init",
      &CGM.getModule());
  llvm::IRBuilder<> b(llvm::BasicBlock::Create(CGM.getLLVMContext(), "entry",
        Init));
  b.CreateAlignedStore(CGM.getNSConcreteGlobalBlock(),
                       b.CreateStructGEP(literal->getValueType(), literal, 0),
                       CGM.getPointerAlign().getAsAlign());
  b.CreateRetVoid();
  // We can't use the normal LLVM global initialisation array, because we
  // need to specify that this runs early in library initialisation.
  auto *InitVar = new llvm::GlobalVariable(CGM.getModule(), Init->getType(),
      /*isConstant*/true, llvm::GlobalValue::InternalLinkage,
      Init, ".block_isa_init_ptr");
  InitVar->setSection(".CRT$XCLa");
  CGM.addUsedGlobal(InitVar);
}

// Return a constant of the appropriately-casted type.
llvm::Type *RequiredType =
  CGM.getTypes().ConvertType(blockInfo.getBlockExpr()->getType());
llvm::Constant *Result =
    llvm::ConstantExpr::getPointerCast(literal, RequiredType);
CGM.setAddrOfGlobalBlock(blockInfo.BlockExpression, Result);
if (CGM.getContext().getLangOpts().OpenCL)
  CGM.getOpenCLRuntime().recordBlockInfo(
      blockInfo.BlockExpression,
      cast<llvm::Function>(blockFn->stripPointerCasts()), Result);
return Result;
1401}

1403void CodeGenFunction::setBlockContextParameter(const ImplicitParamDecl *D,
                                             unsigned argNum,
                                             llvm::Value *arg) {
assert(BlockInfo && "not emitting prologue of block invocation function?!")((void)0);

// Allocate a stack slot like for any local variable to guarantee optimal
// debug info at -O0. The mem2reg pass will eliminate it when optimizing.
Address alloc = CreateMemTemp(D->getType(), D->getName() + ".addr");
Builder.CreateStore(arg, alloc);
if (CGDebugInfo *DI = getDebugInfo()) {
  if (CGM.getCodeGenOpts().hasReducedDebugInfo()) {
    DI->setLocation(D->getLocation());
    DI->EmitDeclareOfBlockLiteralArgVariable(
        *BlockInfo, D->getName(), argNum,
        cast<llvm::AllocaInst>(alloc.getPointer()), Builder);
  }
}

SourceLocation StartLoc = BlockInfo->getBlockExpr()->getBody()->getBeginLoc();
ApplyDebugLocation Scope(*this, StartLoc);

// Instead of messing around with LocalDeclMap, just set the value
// directly as BlockPointer.
BlockPointer = Builder.CreatePointerCast(
    arg,
    BlockInfo->StructureType->getPointerTo(
        getContext().getLangOpts().OpenCL
            ? getContext().getTargetAddressSpace(LangAS::opencl_generic)
            : 0),
    "block");
1433}

1435Address CodeGenFunction::LoadBlockStruct() {
assert(BlockInfo && "not in a block invocation function!")((void)0);
assert(BlockPointer && "no block pointer set!")((void)0);
return Address(BlockPointer, BlockInfo->BlockAlign);
1439}

1441llvm::Function *
1442CodeGenFunction::GenerateBlockFunction(GlobalDecl GD,
                                     const CGBlockInfo &blockInfo,
                                     const DeclMapTy &ldm,
                                     bool IsLambdaConversionToBlock,
                                     bool BuildGlobalBlock) {
const BlockDecl *blockDecl = blockInfo.getBlockDecl();

CurGD = GD;

CurEHLocation = blockInfo.getBlockExpr()->getEndLoc();

BlockInfo = &blockInfo;

// Arrange for local static and local extern declarations to appear
// to be local to this function as well, in case they're directly
// referenced in a block.
for (DeclMapTy::const_iterator i = ldm.begin(), e = ldm.end(); i != e; ++i) {
  const auto *var = dyn_cast<VarDecl>(i->first);
  if (var && !var->hasLocalStorage())
    setAddrOfLocalVar(var, i->second);
}

// Begin building the function declaration.

// Build the argument list.
FunctionArgList args;

// The first argument is the block pointer.  Just take it as a void*
// and cast it later.
QualType selfTy = getContext().VoidPtrTy;

// For OpenCL passed block pointer can be private AS local variable or
// global AS program scope variable (for the case with and without captures).
// Generic AS is used therefore to be able to accommodate both private and
// generic AS in one implementation.
if (getLangOpts().OpenCL)
  selfTy = getContext().getPointerType(getContext().getAddrSpaceQualType(
      getContext().VoidTy, LangAS::opencl_generic));

IdentifierInfo *II = &CGM.getContext().Idents.get(".block_descriptor");

ImplicitParamDecl SelfDecl(getContext(), const_cast<BlockDecl *>(blockDecl),
                           SourceLocation(), II, selfTy,
                           ImplicitParamDecl::ObjCSelf);
args.push_back(&SelfDecl);

// Now add the rest of the parameters.
args.append(blockDecl->param_begin(), blockDecl->param_end());

// Create the function declaration.
const FunctionProtoType *fnType = blockInfo.getBlockExpr()->getFunctionType();
const CGFunctionInfo &fnInfo =
  CGM.getTypes().arrangeBlockFunctionDeclaration(fnType, args);
if (CGM.ReturnSlotInterferesWithArgs(fnInfo))
  blockInfo.UsesStret = true;

llvm::FunctionType *fnLLVMType = CGM.getTypes().GetFunctionType(fnInfo);

StringRef name = CGM.getBlockMangledName(GD, blockDecl);
llvm::Function *fn = llvm::Function::Create(
    fnLLVMType, llvm::GlobalValue::InternalLinkage, name, &CGM.getModule());
CGM.SetInternalFunctionAttributes(blockDecl, fn, fnInfo);

if (BuildGlobalBlock) {
  auto GenVoidPtrTy = getContext().getLangOpts().OpenCL
                          ? CGM.getOpenCLRuntime().getGenericVoidPointerType()
                          : VoidPtrTy;
  buildGlobalBlock(CGM, blockInfo,
                   llvm::ConstantExpr::getPointerCast(fn, GenVoidPtrTy));
}

// Begin generating the function.
StartFunction(blockDecl, fnType->getReturnType(), fn, fnInfo, args,
              blockDecl->getLocation(),
              blockInfo.getBlockExpr()->getBody()->getBeginLoc());

// Okay.  Undo some of what StartFunction did.

// At -O0 we generate an explicit alloca for the BlockPointer, so the RA
// won't delete the dbg.declare intrinsics for captured variables.
llvm::Value *BlockPointerDbgLoc = BlockPointer;
if (CGM.getCodeGenOpts().OptimizationLevel == 0) {
  // Allocate a stack slot for it, so we can point the debugger to it
  Address Alloca = CreateTempAlloca(BlockPointer->getType(),
                                    getPointerAlign(),
                                    "block.addr");
  // Set the DebugLocation to empty, so the store is recognized as a
  // frame setup instruction by llvm::DwarfDebug::beginFunction().
  auto NL = ApplyDebugLocation::CreateEmpty(*this);
  Builder.CreateStore(BlockPointer, Alloca);
  BlockPointerDbgLoc = Alloca.getPointer();
}

// If we have a C++ 'this' reference, go ahead and force it into
// existence now.
if (blockDecl->capturesCXXThis()) {
  Address addr = Builder.CreateStructGEP(
      LoadBlockStruct(), blockInfo.CXXThisIndex, "block.captured-this");
  CXXThisValue = Builder.CreateLoad(addr, "this");
}

// Also force all the constant captures.
for (const auto &CI : blockDecl->captures()) {
  const VarDecl *variable = CI.getVariable();
  const CGBlockInfo::Capture &capture = blockInfo.getCapture(variable);
  if (!capture.isConstant()) continue;

  CharUnits align = getContext().getDeclAlign(variable);
  Address alloca =
    CreateMemTemp(variable->getType(), align, "block.captured-const");

  Builder.CreateStore(capture.getConstant(), alloca);

  setAddrOfLocalVar(variable, alloca);
}

// Save a spot to insert the debug information for all the DeclRefExprs.
llvm::BasicBlock *entry = Builder.GetInsertBlock();
llvm::BasicBlock::iterator entry_ptr = Builder.GetInsertPoint();
--entry_ptr;

if (IsLambdaConversionToBlock)
  EmitLambdaBlockInvokeBody();
else {
  PGO.assignRegionCounters(GlobalDecl(blockDecl), fn);
  incrementProfileCounter(blockDecl->getBody());
  EmitStmt(blockDecl->getBody());
}

// Remember where we were...
llvm::BasicBlock *resume = Builder.GetInsertBlock();

// Go back to the entry.
++entry_ptr;
Builder.SetInsertPoint(entry, entry_ptr);

// Emit debug information for all the DeclRefExprs.
// FIXME: also for 'this'
if (CGDebugInfo *DI = getDebugInfo()) {
  for (const auto &CI : blockDecl->captures()) {
    const VarDecl *variable = CI.getVariable();
    DI->EmitLocation(Builder, variable->getLocation());

    if (CGM.getCodeGenOpts().hasReducedDebugInfo()) {
      const CGBlockInfo::Capture &capture = blockInfo.getCapture(variable);
      if (capture.isConstant()) {
        auto addr = LocalDeclMap.find(variable)->second;
        (void)DI->EmitDeclareOfAutoVariable(variable, addr.getPointer(),
                                            Builder);
        continue;
      }

      DI->EmitDeclareOfBlockDeclRefVariable(
          variable, BlockPointerDbgLoc, Builder, blockInfo,
          entry_ptr == entry->end() ? nullptr : &*entry_ptr);
    }
  }
  // Recover location if it was changed in the above loop.
  DI->EmitLocation(Builder,
                   cast<CompoundStmt>(blockDecl->getBody())->getRBracLoc());
}

// And resume where we left off.
if (resume == nullptr)
  Builder.ClearInsertionPoint();
else
  Builder.SetInsertPoint(resume);

FinishFunction(cast<CompoundStmt>(blockDecl->getBody())->getRBracLoc());

return fn;
1613}

1615static std::pair<BlockCaptureEntityKind, BlockFieldFlags>
1616computeCopyInfoForBlockCapture(const BlockDecl::Capture &CI, QualType T,
                             const LangOptions &LangOpts) {
if (CI.getCopyExpr()) {
  assert(!CI.isByRef())((void)0);
  // don't bother computing flags
  return std::make_pair(BlockCaptureEntityKind::CXXRecord, BlockFieldFlags());
}
BlockFieldFlags Flags;
if (CI.isEscapingByref()) {
  Flags = BLOCK_FIELD_IS_BYREF;
  if (T.isObjCGCWeak())
    Flags |= BLOCK_FIELD_IS_WEAK;
  return std::make_pair(BlockCaptureEntityKind::BlockObject, Flags);
}

Flags = BLOCK_FIELD_IS_OBJECT;
bool isBlockPointer = T->isBlockPointerType();
if (isBlockPointer)
  Flags = BLOCK_FIELD_IS_BLOCK;

switch (T.isNonTrivialToPrimitiveCopy()) {
case QualType::PCK_Struct:
  return std::make_pair(BlockCaptureEntityKind::NonTrivialCStruct,
                        BlockFieldFlags());
case QualType::PCK_ARCWeak:
  // We need to register __weak direct captures with the runtime.
  return std::make_pair(BlockCaptureEntityKind::ARCWeak, Flags);
case QualType::PCK_ARCStrong:
  // We need to retain the copied value for __strong direct captures.
  // If it's a block pointer, we have to copy the block and assign that to
  // the destination pointer, so we might as well use _Block_object_assign.
  // Otherwise we can avoid that.
  return std::make_pair(!isBlockPointer ? BlockCaptureEntityKind::ARCStrong
                                        : BlockCaptureEntityKind::BlockObject,
                        Flags);
case QualType::PCK_Trivial:
case QualType::PCK_VolatileTrivial: {
  if (!T->isObjCRetainableType())
    // For all other types, the memcpy is fine.
    return std::make_pair(BlockCaptureEntityKind::None, BlockFieldFlags());

  // Special rules for ARC captures:
  Qualifiers QS = T.getQualifiers();

  // Non-ARC captures of retainable pointers are strong and
  // therefore require a call to _Block_object_assign.
  if (!QS.getObjCLifetime() && !LangOpts.ObjCAutoRefCount)
    return std::make_pair(BlockCaptureEntityKind::BlockObject, Flags);

  // Otherwise the memcpy is fine.
  return std::make_pair(BlockCaptureEntityKind::None, BlockFieldFlags());
}
}
llvm_unreachable("after exhaustive PrimitiveCopyKind switch")__builtin_unreachable();
1670}

1672static std::pair<BlockCaptureEntityKind, BlockFieldFlags>
1673computeDestroyInfoForBlockCapture(const BlockDecl::Capture &CI, QualType T,
                                const LangOptions &LangOpts);

1676/// Find the set of block captures that need to be explicitly copied or destroy.
1677static void findBlockCapturedManagedEntities(
  const CGBlockInfo &BlockInfo, const LangOptions &LangOpts,
  SmallVectorImpl<BlockCaptureManagedEntity> &ManagedCaptures) {
for (const auto &CI : BlockInfo.getBlockDecl()->captures()) {
  const VarDecl *Variable = CI.getVariable();
  const CGBlockInfo::Capture &Capture = BlockInfo.getCapture(Variable);
  if (Capture.isConstant())
    continue;

  QualType VT = Capture.fieldType();
  auto CopyInfo = computeCopyInfoForBlockCapture(CI, VT, LangOpts);
  auto DisposeInfo = computeDestroyInfoForBlockCapture(CI, VT, LangOpts);
  if (CopyInfo.first != BlockCaptureEntityKind::None ||
      DisposeInfo.first != BlockCaptureEntityKind::None)
    ManagedCaptures.emplace_back(CopyInfo.first, DisposeInfo.first,
                                 CopyInfo.second, DisposeInfo.second, CI,
                                 Capture);
}

// Sort the captures by offset.
llvm::sort(ManagedCaptures);
1698}

1700namespace {
1701/// Release a __block variable.
1702struct CallBlockRelease final : EHScopeStack::Cleanup {
Address Addr;
BlockFieldFlags FieldFlags;
bool LoadBlockVarAddr, CanThrow;

CallBlockRelease(Address Addr, BlockFieldFlags Flags, bool LoadValue,
                 bool CT)
    : Addr(Addr), FieldFlags(Flags), LoadBlockVarAddr(LoadValue),
      CanThrow(CT) {}

void Emit(CodeGenFunction &CGF, Flags flags) override {
  llvm::Value *BlockVarAddr;
  if (LoadBlockVarAddr) {
    BlockVarAddr = CGF.Builder.CreateLoad(Addr);
    BlockVarAddr = CGF.Builder.CreateBitCast(BlockVarAddr, CGF.VoidPtrTy);
  } else {
    BlockVarAddr = Addr.getPointer();
  }

  CGF.BuildBlockRelease(BlockVarAddr, FieldFlags, CanThrow);
}
1723};
1724} // end anonymous namespace

1726/// Check if \p T is a C++ class that has a destructor that can throw.
1727bool CodeGenFunction::cxxDestructorCanThrow(QualType T) {
if (const auto *RD = T->getAsCXXRecordDecl())
  if (const CXXDestructorDecl *DD = RD->getDestructor())
    return DD->getType()->castAs<FunctionProtoType>()->canThrow();
return false;
1732}

1734// Return a string that has the information about a capture.
1735static std::string getBlockCaptureStr(const BlockCaptureManagedEntity &E,
                                    CaptureStrKind StrKind,
                                    CharUnits BlockAlignment,
                                    CodeGenModule &CGM) {
std::string Str;
ASTContext &Ctx = CGM.getContext();
const BlockDecl::Capture &CI = *E.CI;
QualType CaptureTy = CI.getVariable()->getType();

BlockCaptureEntityKind Kind;
BlockFieldFlags Flags;

// CaptureStrKind::Merged should be passed only when the operations and the
// flags are the same for copy and dispose.
assert((StrKind != CaptureStrKind::Merged ||((void)0)
        (E.CopyKind == E.DisposeKind && E.CopyFlags == E.DisposeFlags)) &&((void)0)
       "different operations and flags")((void)0);

if (StrKind == CaptureStrKind::DisposeHelper) {
  Kind = E.DisposeKind;
  Flags = E.DisposeFlags;
} else {
  Kind = E.CopyKind;
  Flags = E.CopyFlags;
}

switch (Kind) {
case BlockCaptureEntityKind::CXXRecord: {
  Str += "c";
  SmallString<256> TyStr;
  llvm::raw_svector_ostream Out(TyStr);
  CGM.getCXXABI().getMangleContext().mangleTypeName(CaptureTy, Out);
  Str += llvm::to_string(TyStr.size()) + TyStr.c_str();
  break;
}
case BlockCaptureEntityKind::ARCWeak:
  Str += "w";
  break;
case BlockCaptureEntityKind::ARCStrong:
  Str += "s";
  break;
case BlockCaptureEntityKind::BlockObject: {
  const VarDecl *Var = CI.getVariable();
  unsigned F = Flags.getBitMask();
  if (F & BLOCK_FIELD_IS_BYREF) {
    Str += "r";
    if (F & BLOCK_FIELD_IS_WEAK)
      Str += "w";
    else {
      // If CaptureStrKind::Merged is passed, check both the copy expression
      // and the destructor.
      if (StrKind != CaptureStrKind::DisposeHelper) {
        if (Ctx.getBlockVarCopyInit(Var).canThrow())
          Str += "c";
      }
      if (StrKind != CaptureStrKind::CopyHelper) {
        if (CodeGenFunction::cxxDestructorCanThrow(CaptureTy))
          Str += "d";
      }
    }
  } else {
    assert((F & BLOCK_FIELD_IS_OBJECT) && "unexpected flag value")((void)0);
    if (F == BLOCK_FIELD_IS_BLOCK)
      Str += "b";
    else
      Str += "o";
  }
  break;
}
case BlockCaptureEntityKind::NonTrivialCStruct: {
  bool IsVolatile = CaptureTy.isVolatileQualified();
  CharUnits Alignment =
      BlockAlignment.alignmentAtOffset(E.Capture->getOffset());

  Str += "n";
  std::string FuncStr;
  if (StrKind == CaptureStrKind::DisposeHelper)
    FuncStr = CodeGenFunction::getNonTrivialDestructorStr(
        CaptureTy, Alignment, IsVolatile, Ctx);
  else
    // If CaptureStrKind::Merged is passed, use the copy constructor string.
    // It has all the information that the destructor string has.
    FuncStr = CodeGenFunction::getNonTrivialCopyConstructorStr(
        CaptureTy, Alignment, IsVolatile, Ctx);
  // The underscore is necessary here because non-trivial copy constructor
  // and destructor strings can start with a number.
  Str += llvm::to_string(FuncStr.size()) + "_" + FuncStr;
  break;
}
case BlockCaptureEntityKind::None:
  break;
}

return Str;
1829}

1831static std::string getCopyDestroyHelperFuncName(
  const SmallVectorImpl<BlockCaptureManagedEntity> &Captures,
  CharUnits BlockAlignment, CaptureStrKind StrKind, CodeGenModule &CGM) {
assert((StrKind == CaptureStrKind::CopyHelper ||((void)0)
        StrKind == CaptureStrKind::DisposeHelper) &&((void)0)
       "unexpected CaptureStrKind")((void)0);
std::string Name = StrKind == CaptureStrKind::CopyHelper
                       ? "__copy_helper_block_"
                       : "__destroy_helper_block_";
if (CGM.getLangOpts().Exceptions)
  Name += "e";
if (CGM.getCodeGenOpts().ObjCAutoRefCountExceptions)
  Name += "a";
Name += llvm::to_string(BlockAlignment.getQuantity()) + "_";

for (const BlockCaptureManagedEntity &E : Captures) {
  Name += llvm::to_string(E.Capture->getOffset().getQuantity());
  Name += getBlockCaptureStr(E, StrKind, BlockAlignment, CGM);
}

return Name;
1852}

1854static void pushCaptureCleanup(BlockCaptureEntityKind CaptureKind,
                             Address Field, QualType CaptureType,
                             BlockFieldFlags Flags, bool ForCopyHelper,
                             VarDecl *Var, CodeGenFunction &CGF) {
bool EHOnly = ForCopyHelper;

switch (CaptureKind) {
case BlockCaptureEntityKind::CXXRecord:
case BlockCaptureEntityKind::ARCWeak:
case BlockCaptureEntityKind::NonTrivialCStruct:
case BlockCaptureEntityKind::ARCStrong: {
  if (CaptureType.isDestructedType() &&
      (!EHOnly || CGF.needsEHCleanup(CaptureType.isDestructedType()))) {
    CodeGenFunction::Destroyer *Destroyer =
        CaptureKind == BlockCaptureEntityKind::ARCStrong
            ? CodeGenFunction::destroyARCStrongImprecise
            : CGF.getDestroyer(CaptureType.isDestructedType());
    CleanupKind Kind =
        EHOnly ? EHCleanup
               : CGF.getCleanupKind(CaptureType.isDestructedType());
    CGF.pushDestroy(Kind, Field, CaptureType, Destroyer, Kind & EHCleanup);
  }
  break;
}
case BlockCaptureEntityKind::BlockObject: {
  if (!EHOnly || CGF.getLangOpts().Exceptions) {
    CleanupKind Kind = EHOnly ? EHCleanup : NormalAndEHCleanup;
    // Calls to _Block_object_dispose along the EH path in the copy helper
    // function don't throw as newly-copied __block variables always have a
    // reference count of 2.
    bool CanThrow =
        !ForCopyHelper && CGF.cxxDestructorCanThrow(CaptureType);
    CGF.enterByrefCleanup(Kind, Field, Flags, /*LoadBlockVarAddr*/ true,
                          CanThrow);
  }
  break;
}
case BlockCaptureEntityKind::None:
  break;
}
1894}

1896static void setBlockHelperAttributesVisibility(bool CapturesNonExternalType,
                                             llvm::Function *Fn,
                                             const CGFunctionInfo &FI,
                                             CodeGenModule &CGM) {
if (CapturesNonExternalType) {
  CGM.SetInternalFunctionAttributes(GlobalDecl(), Fn, FI);
} else {
  Fn->setVisibility(llvm::GlobalValue::HiddenVisibility);
  Fn->setUnnamedAddr(llvm::GlobalValue::UnnamedAddr::Global);
  CGM.SetLLVMFunctionAttributes(GlobalDecl(), FI, Fn, /*IsThunk=*/false);
  CGM.SetLLVMFunctionAttributesForDefinition(nullptr, Fn);
}
1908}
1909/// Generate the copy-helper function for a block closure object:
1910///   static void block_copy_helper(block_t *dst, block_t *src);
1911/// The runtime will have previously initialized 'dst' by doing a
1912/// bit-copy of 'src'.
1913///
1914/// Note that this copies an entire block closure object to the heap;
1915/// it should not be confused with a 'byref copy helper', which moves
1916/// the contents of an individual __block variable to the heap.
1917llvm::Constant *
1918CodeGenFunction::GenerateCopyHelperFunction(const CGBlockInfo &blockInfo) {
SmallVector<BlockCaptureManagedEntity, 4> CopiedCaptures;
findBlockCapturedManagedEntities(blockInfo, getLangOpts(), CopiedCaptures);
std::string FuncName =
    getCopyDestroyHelperFuncName(CopiedCaptures, blockInfo.BlockAlign,
                                 CaptureStrKind::CopyHelper, CGM);

if (llvm::GlobalValue *Func = CGM.getModule().getNamedValue(FuncName))
  return llvm::ConstantExpr::getBitCast(Func, VoidPtrTy);

ASTContext &C = getContext();

QualType ReturnTy = C.VoidTy;

FunctionArgList args;
ImplicitParamDecl DstDecl(C, C.VoidPtrTy, ImplicitParamDecl::Other);
args.push_back(&DstDecl);
ImplicitParamDecl SrcDecl(C, C.VoidPtrTy, ImplicitParamDecl::Other);
args.push_back(&SrcDecl);

const CGFunctionInfo &FI =
    CGM.getTypes().arrangeBuiltinFunctionDeclaration(ReturnTy, args);

// FIXME: it would be nice if these were mergeable with things with
// identical semantics.
llvm::FunctionType *LTy = CGM.getTypes().GetFunctionType(FI);

llvm::Function *Fn =
  llvm::Function::Create(LTy, llvm::GlobalValue::LinkOnceODRLinkage,
                         FuncName, &CGM.getModule());
if (CGM.supportsCOMDAT())
  Fn->setComdat(CGM.getModule().getOrInsertComdat(FuncName));

SmallVector<QualType, 2> ArgTys;
ArgTys.push_back(C.VoidPtrTy);
ArgTys.push_back(C.VoidPtrTy);

setBlockHelperAttributesVisibility(blockInfo.CapturesNonExternalType, Fn, FI,
                                   CGM);
StartFunction(GlobalDecl(), ReturnTy, Fn, FI, args);
auto AL = ApplyDebugLocation::CreateArtificial(*this);

llvm::Type *structPtrTy = blockInfo.StructureType->getPointerTo();

Address src = GetAddrOfLocalVar(&SrcDecl);
src = Address(Builder.CreateLoad(src), blockInfo.BlockAlign);
src = Builder.CreateBitCast(src, structPtrTy, "block.source");

Address dst = GetAddrOfLocalVar(&DstDecl);
dst = Address(Builder.CreateLoad(dst), blockInfo.BlockAlign);
dst = Builder.CreateBitCast(dst, structPtrTy, "block.dest");

for (const auto &CopiedCapture : CopiedCaptures) {
  const BlockDecl::Capture &CI = *CopiedCapture.CI;
  const CGBlockInfo::Capture &capture = *CopiedCapture.Capture;
  QualType captureType = CI.getVariable()->getType();
  BlockFieldFlags flags = CopiedCapture.CopyFlags;

  unsigned index = capture.getIndex();
  Address srcField = Builder.CreateStructGEP(src, index);
  Address dstField = Builder.CreateStructGEP(dst, index);

  switch (CopiedCapture.CopyKind) {
  case BlockCaptureEntityKind::CXXRecord:
    // If there's an explicit copy expression, we do that.
    assert(CI.getCopyExpr() && "copy expression for variable is missing")((void)0);
    EmitSynthesizedCXXCopyCtor(dstField, srcField, CI.getCopyExpr());
    break;
  case BlockCaptureEntityKind::ARCWeak:
    EmitARCCopyWeak(dstField, srcField);
    break;
  case BlockCaptureEntityKind::NonTrivialCStruct: {
    // If this is a C struct that requires non-trivial copy construction,
    // emit a call to its copy constructor.
    QualType varType = CI.getVariable()->getType();
    callCStructCopyConstructor(MakeAddrLValue(dstField, varType),
                               MakeAddrLValue(srcField, varType));
    break;
  }
  case BlockCaptureEntityKind::ARCStrong: {
    llvm::Value *srcValue = Builder.CreateLoad(srcField, "blockcopy.src");
    // At -O0, store null into the destination field (so that the
    // storeStrong doesn't over-release) and then call storeStrong.
    // This is a workaround to not having an initStrong call.
    if (CGM.getCodeGenOpts().OptimizationLevel == 0) {
      auto *ty = cast<llvm::PointerType>(srcValue->getType());
      llvm::Value *null = llvm::ConstantPointerNull::get(ty);
      Builder.CreateStore(null, dstField);
      EmitARCStoreStrongCall(dstField, srcValue, true);

    // With optimization enabled, take advantage of the fact that
    // the blocks runtime guarantees a memcpy of the block data, and
    // just emit a retain of the src field.
    } else {
      EmitARCRetainNonBlock(srcValue);

      // Unless EH cleanup is required, we don't need this anymore, so kill
      // it. It's not quite worth the annoyance to avoid creating it in the
      // first place.
      if (!needsEHCleanup(captureType.isDestructedType()))
        cast<llvm::Instruction>(dstField.getPointer())->eraseFromParent();
    }
    break;
  }
  case BlockCaptureEntityKind::BlockObject: {
    llvm::Value *srcValue = Builder.CreateLoad(srcField, "blockcopy.src");
    srcValue = Builder.CreateBitCast(srcValue, VoidPtrTy);
    llvm::Value *dstAddr =
        Builder.CreateBitCast(dstField.getPointer(), VoidPtrTy);
    llvm::Value *args[] = {
      dstAddr, srcValue, llvm::ConstantInt::get(Int32Ty, flags.getBitMask())
    };

    if (CI.isByRef() && C.getBlockVarCopyInit(CI.getVariable()).canThrow())
      EmitRuntimeCallOrInvoke(CGM.getBlockObjectAssign(), args);
    else
      EmitNounwindRuntimeCall(CGM.getBlockObjectAssign(), args);
    break;
  }
  case BlockCaptureEntityKind::None:
    continue;
  }

  // Ensure that we destroy the copied object if an exception is thrown later
  // in the helper function.
  pushCaptureCleanup(CopiedCapture.CopyKind, dstField, captureType, flags,
                     /*ForCopyHelper*/ true, CI.getVariable(), *this);
}

FinishFunction();

return llvm::ConstantExpr::getBitCast(Fn, VoidPtrTy);
2050}

2052static BlockFieldFlags
2053getBlockFieldFlagsForObjCObjectPointer(const BlockDecl::Capture &CI,
                                     QualType T) {
BlockFieldFlags Flags = BLOCK_FIELD_IS_OBJECT;
if (T->isBlockPointerType())
  Flags = BLOCK_FIELD_IS_BLOCK;
return Flags;
2059}

2061static std::pair<BlockCaptureEntityKind, BlockFieldFlags>
2062computeDestroyInfoForBlockCapture(const BlockDecl::Capture &CI, QualType T,
                                const LangOptions &LangOpts) {
if (CI.isEscapingByref()) {
  BlockFieldFlags Flags = BLOCK_FIELD_IS_BYREF;
  if (T.isObjCGCWeak())
    Flags |= BLOCK_FIELD_IS_WEAK;
  return std::make_pair(BlockCaptureEntityKind::BlockObject, Flags);
}

switch (T.isDestructedType()) {
case QualType::DK_cxx_destructor:
  return std::make_pair(BlockCaptureEntityKind::CXXRecord, BlockFieldFlags());
case QualType::DK_objc_strong_lifetime:
  // Use objc_storeStrong for __strong direct captures; the
  // dynamic tools really like it when we do this.
  return std::make_pair(BlockCaptureEntityKind::ARCStrong,
                        getBlockFieldFlagsForObjCObjectPointer(CI, T));
case QualType::DK_objc_weak_lifetime:
  // Support __weak direct captures.
  return std::make_pair(BlockCaptureEntityKind::ARCWeak,
                        getBlockFieldFlagsForObjCObjectPointer(CI, T));
case QualType::DK_nontrivial_c_struct:
  return std::make_pair(BlockCaptureEntityKind::NonTrivialCStruct,
                        BlockFieldFlags());
case QualType::DK_none: {
  // Non-ARC captures are strong, and we need to use _Block_object_dispose.
  if (T->isObjCRetainableType() && !T.getQualifiers().hasObjCLifetime() &&
      !LangOpts.ObjCAutoRefCount)
    return std::make_pair(BlockCaptureEntityKind::BlockObject,
                          getBlockFieldFlagsForObjCObjectPointer(CI, T));
  // Otherwise, we have nothing to do.
  return std::make_pair(BlockCaptureEntityKind::None, BlockFieldFlags());
}
}
llvm_unreachable("after exhaustive DestructionKind switch")__builtin_unreachable();
2097}

2099/// Generate the destroy-helper function for a block closure object:
2100///   static void block_destroy_helper(block_t *theBlock);
2101///
2102/// Note that this destroys a heap-allocated block closure object;
2103/// it should not be confused with a 'byref destroy helper', which
2104/// destroys the heap-allocated contents of an individual __block
2105/// variable.
2106llvm::Constant *
2107CodeGenFunction::GenerateDestroyHelperFunction(const CGBlockInfo &blockInfo) {
SmallVector<BlockCaptureManagedEntity, 4> DestroyedCaptures;
findBlockCapturedManagedEntities(blockInfo, getLangOpts(), DestroyedCaptures);
std::string FuncName =
    getCopyDestroyHelperFuncName(DestroyedCaptures, blockInfo.BlockAlign,
                                 CaptureStrKind::DisposeHelper, CGM);

if (llvm::GlobalValue *Func = CGM.getModule().getNamedValue(FuncName))
  return llvm::ConstantExpr::getBitCast(Func, VoidPtrTy);

ASTContext &C = getContext();

QualType ReturnTy = C.VoidTy;

FunctionArgList args;
ImplicitParamDecl SrcDecl(C, C.VoidPtrTy, ImplicitParamDecl::Other);
args.push_back(&SrcDecl);

const CGFunctionInfo &FI =
    CGM.getTypes().arrangeBuiltinFunctionDeclaration(ReturnTy, args);

// FIXME: We'd like to put these into a mergable by content, with
// internal linkage.
llvm::FunctionType *LTy = CGM.getTypes().GetFunctionType(FI);

llvm::Function *Fn =
  llvm::Function::Create(LTy, llvm::GlobalValue::LinkOnceODRLinkage,
                         FuncName, &CGM.getModule());
if (CGM.supportsCOMDAT())
  Fn->setComdat(CGM.getModule().getOrInsertComdat(FuncName));

SmallVector<QualType, 1> ArgTys;
ArgTys.push_back(C.VoidPtrTy);

setBlockHelperAttributesVisibility(blockInfo.CapturesNonExternalType, Fn, FI,
                                   CGM);
StartFunction(GlobalDecl(), ReturnTy, Fn, FI, args);
markAsIgnoreThreadCheckingAtRuntime(Fn);

auto AL = ApplyDebugLocation::CreateArtificial(*this);

llvm::Type *structPtrTy = blockInfo.StructureType->getPointerTo();

Address src = GetAddrOfLocalVar(&SrcDecl);
src = Address(Builder.CreateLoad(src), blockInfo.BlockAlign);
src = Builder.CreateBitCast(src, structPtrTy, "block");

CodeGenFunction::RunCleanupsScope cleanups(*this);

for (const auto &DestroyedCapture : DestroyedCaptures) {
  const BlockDecl::Capture &CI = *DestroyedCapture.CI;
  const CGBlockInfo::Capture &capture = *DestroyedCapture.Capture;
  BlockFieldFlags flags = DestroyedCapture.DisposeFlags;

  Address srcField = Builder.CreateStructGEP(src, capture.getIndex());

  pushCaptureCleanup(DestroyedCapture.DisposeKind, srcField,
                     CI.getVariable()->getType(), flags,
                     /*ForCopyHelper*/ false, CI.getVariable(), *this);
}

cleanups.ForceCleanup();

FinishFunction();

return llvm::ConstantExpr::getBitCast(Fn, VoidPtrTy);
2173}

2175namespace {

2177/// Emits the copy/dispose helper functions for a __block object of id type.
2178class ObjectByrefHelpers final : public BlockByrefHelpers {
BlockFieldFlags Flags;

2181public:
ObjectByrefHelpers(CharUnits alignment, BlockFieldFlags flags)
  : BlockByrefHelpers(alignment), Flags(flags) {}

void emitCopy(CodeGenFunction &CGF, Address destField,
              Address srcField) override {
  destField = CGF.Builder.CreateBitCast(destField, CGF.VoidPtrTy);

  srcField = CGF.Builder.CreateBitCast(srcField, CGF.VoidPtrPtrTy);
  llvm::Value *srcValue = CGF.Builder.CreateLoad(srcField);

  unsigned flags = (Flags | BLOCK_BYREF_CALLER).getBitMask();

  llvm::Value *flagsVal = llvm::ConstantInt::get(CGF.Int32Ty, flags);
  llvm::FunctionCallee fn = CGF.CGM.getBlockObjectAssign();

  llvm::Value *args[] = { destField.getPointer(), srcValue, flagsVal };
  CGF.EmitNounwindRuntimeCall(fn, args);
}

void emitDispose(CodeGenFunction &CGF, Address field) override {
  field = CGF.Builder.CreateBitCast(field, CGF.Int8PtrTy->getPointerTo(0));
  llvm::Value *value = CGF.Builder.CreateLoad(field);

  CGF.BuildBlockRelease(value, Flags | BLOCK_BYREF_CALLER, false);
}

void profileImpl(llvm::FoldingSetNodeID &id) const override {
  id.AddInteger(Flags.getBitMask());
}
2211};

2213/// Emits the copy/dispose helpers for an ARC __block __weak variable.
2214class ARCWeakByrefHelpers final : public BlockByrefHelpers {
2215public:
ARCWeakByrefHelpers(CharUnits alignment) : BlockByrefHelpers(alignment) {}

void emitCopy(CodeGenFunction &CGF, Address destField,
              Address srcField) override {
  CGF.EmitARCMoveWeak(destField, srcField);
}

void emitDispose(CodeGenFunction &CGF, Address field) override {
  CGF.EmitARCDestroyWeak(field);
}

void profileImpl(llvm::FoldingSetNodeID &id) const override {
  // 0 is distinguishable from all pointers and byref flags
  id.AddInteger(0);
}
2231};

2233/// Emits the copy/dispose helpers for an ARC __block __strong variable
2234/// that's not of block-pointer type.
2235class ARCStrongByrefHelpers final : public BlockByrefHelpers {
2236public:
ARCStrongByrefHelpers(CharUnits alignment) : BlockByrefHelpers(alignment) {}

void emitCopy(CodeGenFunction &CGF, Address destField,
              Address srcField) override {
  // Do a "move" by copying the value and then zeroing out the old
  // variable.

  llvm::Value *value = CGF.Builder.CreateLoad(srcField);

  llvm::Value *null =
    llvm::ConstantPointerNull::get(cast<llvm::PointerType>(value->getType()));

  if (CGF.CGM.getCodeGenOpts().OptimizationLevel == 0) {
    CGF.Builder.CreateStore(null, destField);
    CGF.EmitARCStoreStrongCall(destField, value, /*ignored*/ true);
    CGF.EmitARCStoreStrongCall(srcField, null, /*ignored*/ true);
    return;
  }
  CGF.Builder.CreateStore(value, destField);
  CGF.Builder.CreateStore(null, srcField);
}

void emitDispose(CodeGenFunction &CGF, Address field) override {
  CGF.EmitARCDestroyStrong(field, ARCImpreciseLifetime);
}

void profileImpl(llvm::FoldingSetNodeID &id) const override {
  // 1 is distinguishable from all pointers and byref flags
  id.AddInteger(1);
}
2267};

2269/// Emits the copy/dispose helpers for an ARC __block __strong
2270/// variable that's of block-pointer type.
2271class ARCStrongBlockByrefHelpers final : public BlockByrefHelpers {
2272public:
ARCStrongBlockByrefHelpers(CharUnits alignment)
  : BlockByrefHelpers(alignment) {}

void emitCopy(CodeGenFunction &CGF, Address destField,
              Address srcField) override {
  // Do the copy with objc_retainBlock; that's all that
  // _Block_object_assign would do anyway, and we'd have to pass the
  // right arguments to make sure it doesn't get no-op'ed.
  llvm::Value *oldValue = CGF.Builder.CreateLoad(srcField);
  llvm::Value *copy = CGF.EmitARCRetainBlock(oldValue, /*mandatory*/ true);
  CGF.Builder.CreateStore(copy, destField);
}

void emitDispose(CodeGenFunction &CGF, Address field) override {
  CGF.EmitARCDestroyStrong(field, ARCImpreciseLifetime);
}

void profileImpl(llvm::FoldingSetNodeID &id) const override {
  // 2 is distinguishable from all pointers and byref flags
  id.AddInteger(2);
}
2294};

2296/// Emits the copy/dispose helpers for a __block variable with a
2297/// nontrivial copy constructor or destructor.
2298class CXXByrefHelpers final : public BlockByrefHelpers {
QualType VarType;
const Expr *CopyExpr;

2302public:
CXXByrefHelpers(CharUnits alignment, QualType type,
                const Expr *copyExpr)
  : BlockByrefHelpers(alignment), VarType(type), CopyExpr(copyExpr) {}

bool needsCopy() const override { return CopyExpr != nullptr; }
void emitCopy(CodeGenFunction &CGF, Address destField,
              Address srcField) override {
  if (!CopyExpr) return;
  CGF.EmitSynthesizedCXXCopyCtor(destField, srcField, CopyExpr);
}

void emitDispose(CodeGenFunction &CGF, Address field) override {
  EHScopeStack::stable_iterator cleanupDepth = CGF.EHStack.stable_begin();
  CGF.PushDestructorCleanup(VarType, field);
  CGF.PopCleanupBlocks(cleanupDepth);
}

void profileImpl(llvm::FoldingSetNodeID &id) const override {
  id.AddPointer(VarType.getCanonicalType().getAsOpaquePtr());
}
2323};

2325/// Emits the copy/dispose helpers for a __block variable that is a non-trivial
2326/// C struct.
2327class NonTrivialCStructByrefHelpers final : public BlockByrefHelpers {
QualType VarType;

2330public:
NonTrivialCStructByrefHelpers(CharUnits alignment, QualType type)
  : BlockByrefHelpers(alignment), VarType(type) {}

void emitCopy(CodeGenFunction &CGF, Address destField,
              Address srcField) override {
  CGF.callCStructMoveConstructor(CGF.MakeAddrLValue(destField, VarType),
                                 CGF.MakeAddrLValue(srcField, VarType));
}

bool needsDispose() const override {
  return VarType.isDestructedType();
}

void emitDispose(CodeGenFunction &CGF, Address field) override {
  EHScopeStack::stable_iterator cleanupDepth = CGF.EHStack.stable_begin();
  CGF.pushDestroy(VarType.isDestructedType(), field, VarType);
  CGF.PopCleanupBlocks(cleanupDepth);
}

void profileImpl(llvm::FoldingSetNodeID &id) const override {
  id.AddPointer(VarType.getCanonicalType().getAsOpaquePtr());
}
2353};
2354} // end anonymous namespace

2356static llvm::Constant *
2357generateByrefCopyHelper(CodeGenFunction &CGF, const BlockByrefInfo &byrefInfo,
                      BlockByrefHelpers &generator) {
ASTContext &Context = CGF.getContext();

QualType ReturnTy = Context.VoidTy;

FunctionArgList args;
ImplicitParamDecl Dst(Context, Context.VoidPtrTy, ImplicitParamDecl::Other);
args.push_back(&Dst);

ImplicitParamDecl Src(Context, Context.VoidPtrTy, ImplicitParamDecl::Other);
args.push_back(&Src);

const CGFunctionInfo &FI =
    CGF.CGM.getTypes().arrangeBuiltinFunctionDeclaration(ReturnTy, args);

llvm::FunctionType *LTy = CGF.CGM.getTypes().GetFunctionType(FI);

// FIXME: We'd like to put these into a mergable by content, with
// internal linkage.
llvm::Function *Fn =
  llvm::Function::Create(LTy, llvm::GlobalValue::InternalLinkage,
                         "__Block_byref_object_copy_", &CGF.CGM.getModule());

SmallVector<QualType, 2> ArgTys;
ArgTys.push_back(Context.VoidPtrTy);
ArgTys.push_back(Context.VoidPtrTy);

CGF.CGM.SetInternalFunctionAttributes(GlobalDecl(), Fn, FI);

CGF.StartFunction(GlobalDecl(), ReturnTy, Fn, FI, args);
  // Create a scope with an artificial location for the body of this function.
auto AL = ApplyDebugLocation::CreateArtificial(CGF);

if (generator.needsCopy()) {
  llvm::Type *byrefPtrType = byrefInfo.Type->getPointerTo(0);

  // dst->x
  Address destField = CGF.GetAddrOfLocalVar(&Dst);
  destField = Address(CGF.Builder.CreateLoad(destField),
                      byrefInfo.ByrefAlignment);
  destField = CGF.Builder.CreateBitCast(destField, byrefPtrType);
  destField = CGF.emitBlockByrefAddress(destField, byrefInfo, false,
                                        "dest-object");

  // src->x
  Address srcField = CGF.GetAddrOfLocalVar(&Src);
  srcField = Address(CGF.Builder.CreateLoad(srcField),
                     byrefInfo.ByrefAlignment);
  srcField = CGF.Builder.CreateBitCast(srcField, byrefPtrType);
  srcField = CGF.emitBlockByrefAddress(srcField, byrefInfo, false,
                                       "src-object");

  generator.emitCopy(CGF, destField, srcField);
}

CGF.FinishFunction();

return llvm::ConstantExpr::getBitCast(Fn, CGF.Int8PtrTy);
2416}

2418/// Build the copy helper for a __block variable.
2419static llvm::Constant *buildByrefCopyHelper(CodeGenModule &CGM,
                                          const BlockByrefInfo &byrefInfo,
                                          BlockByrefHelpers &generator) {
CodeGenFunction CGF(CGM);
return generateByrefCopyHelper(CGF, byrefInfo, generator);
2424}

2426/// Generate code for a __block variable's dispose helper.
2427static llvm::Constant *
2428generateByrefDisposeHelper(CodeGenFunction &CGF,
                         const BlockByrefInfo &byrefInfo,
                         BlockByrefHelpers &generator) {
ASTContext &Context = CGF.getContext();
QualType R = Context.VoidTy;

FunctionArgList args;
ImplicitParamDecl Src(CGF.getContext(), Context.VoidPtrTy,
                      ImplicitParamDecl::Other);
args.push_back(&Src);

const CGFunctionInfo &FI =
  CGF.CGM.getTypes().arrangeBuiltinFunctionDeclaration(R, args);

llvm::FunctionType *LTy = CGF.CGM.getTypes().GetFunctionType(FI);

// FIXME: We'd like to put these into a mergable by content, with
// internal linkage.
llvm::Function *Fn =
  llvm::Function::Create(LTy, llvm::GlobalValue::InternalLinkage,
                         "__Block_byref_object_dispose_",
                         &CGF.CGM.getModule());

SmallVector<QualType, 1> ArgTys;
ArgTys.push_back(Context.VoidPtrTy);

CGF.CGM.SetInternalFunctionAttributes(GlobalDecl(), Fn, FI);

CGF.StartFunction(GlobalDecl(), R, Fn, FI, args);
  // Create a scope with an artificial location for the body of this function.
auto AL = ApplyDebugLocation::CreateArtificial(CGF);

if (generator.needsDispose()) {
  Address addr = CGF.GetAddrOfLocalVar(&Src);
  addr = Address(CGF.Builder.CreateLoad(addr), byrefInfo.ByrefAlignment);
  auto byrefPtrType = byrefInfo.Type->getPointerTo(0);
  addr = CGF.Builder.CreateBitCast(addr, byrefPtrType);
  addr = CGF.emitBlockByrefAddress(addr, byrefInfo, false, "object");

  generator.emitDispose(CGF, addr);
}

CGF.FinishFunction();

return llvm::ConstantExpr::getBitCast(Fn, CGF.Int8PtrTy);
2473}

2475/// Build the dispose helper for a __block variable.
2476static llvm::Constant *buildByrefDisposeHelper(CodeGenModule &CGM,
                                             const BlockByrefInfo &byrefInfo,
                                             BlockByrefHelpers &generator) {
CodeGenFunction CGF(CGM);
return generateByrefDisposeHelper(CGF, byrefInfo, generator);
2481}

2483/// Lazily build the copy and dispose helpers for a __block variable
2484/// with the given information.
2485template <class T>
2486static T *buildByrefHelpers(CodeGenModule &CGM, const BlockByrefInfo &byrefInfo,
                          T &&generator) {
llvm::FoldingSetNodeID id;
generator.Profile(id);

void *insertPos;
BlockByrefHelpers *node
  = CGM.ByrefHelpersCache.FindNodeOrInsertPos(id, insertPos);
if (node) return static_cast<T*>(node);

generator.CopyHelper = buildByrefCopyHelper(CGM, byrefInfo, generator);
generator.DisposeHelper = buildByrefDisposeHelper(CGM, byrefInfo, generator);

T *copy = new (CGM.getContext()) T(std::forward<T>(generator));
CGM.ByrefHelpersCache.InsertNode(copy, insertPos);
return copy;
2502}

2504/// Build the copy and dispose helpers for the given __block variable
2505/// emission.  Places the helpers in the global cache.  Returns null
2506/// if no helpers are required.
2507BlockByrefHelpers *
2508CodeGenFunction::buildByrefHelpers(llvm::StructType &byrefType,
                                 const AutoVarEmission &emission) {
const VarDecl &var = *emission.Variable;
assert(var.isEscapingByref() &&((void)0)
       "only escaping __block variables need byref helpers")((void)0);

QualType type = var.getType();

auto &byrefInfo = getBlockByrefInfo(&var);

// The alignment we care about for the purposes of uniquing byref
// helpers is the alignment of the actual byref value field.
CharUnits valueAlignment =
  byrefInfo.ByrefAlignment.alignmentAtOffset(byrefInfo.FieldOffset);

if (const CXXRecordDecl *record = type->getAsCXXRecordDecl()) {
  const Expr *copyExpr =
      CGM.getContext().getBlockVarCopyInit(&var).getCopyExpr();
  if (!copyExpr && record->hasTrivialDestructor()) return nullptr;

  return ::buildByrefHelpers(
      CGM, byrefInfo, CXXByrefHelpers(valueAlignment, type, copyExpr));
}

// If type is a non-trivial C struct type that is non-trivial to
// destructly move or destroy, build the copy and dispose helpers.
if (type.isNonTrivialToPrimitiveDestructiveMove() == QualType::PCK_Struct ||
    type.isDestructedType() == QualType::DK_nontrivial_c_struct)
  return ::buildByrefHelpers(
      CGM, byrefInfo, NonTrivialCStructByrefHelpers(valueAlignment, type));

// Otherwise, if we don't have a retainable type, there's nothing to do.
// that the runtime does extra copies.
if (!type->isObjCRetainableType()) return nullptr;

Qualifiers qs = type.getQualifiers();

// If we have lifetime, that dominates.
if (Qualifiers::ObjCLifetime lifetime = qs.getObjCLifetime()) {
  switch (lifetime) {
  case Qualifiers::OCL_None: llvm_unreachable("impossible")__builtin_unreachable();

  // These are just bits as far as the runtime is concerned.
  case Qualifiers::OCL_ExplicitNone:
  case Qualifiers::OCL_Autoreleasing:
    return nullptr;

  // Tell the runtime that this is ARC __weak, called by the
  // byref routines.
  case Qualifiers::OCL_Weak:
    return ::buildByrefHelpers(CGM, byrefInfo,
                               ARCWeakByrefHelpers(valueAlignment));

  // ARC __strong __block variables need to be retained.
  case Qualifiers::OCL_Strong:
    // Block pointers need to be copied, and there's no direct
    // transfer possible.
    if (type->isBlockPointerType()) {
      return ::buildByrefHelpers(CGM, byrefInfo,
                                 ARCStrongBlockByrefHelpers(valueAlignment));

    // Otherwise, we transfer ownership of the retain from the stack
    // to the heap.
    } else {
      return ::buildByrefHelpers(CGM, byrefInfo,
                                 ARCStrongByrefHelpers(valueAlignment));
    }
  }
  llvm_unreachable("fell out of lifetime switch!")__builtin_unreachable();
}

BlockFieldFlags flags;
if (type->isBlockPointerType()) {
  flags |= BLOCK_FIELD_IS_BLOCK;
} else if (CGM.getContext().isObjCNSObjectType(type) ||
           type->isObjCObjectPointerType()) {
  flags |= BLOCK_FIELD_IS_OBJECT;
} else {
  return nullptr;
}

if (type.isObjCGCWeak())
  flags |= BLOCK_FIELD_IS_WEAK;

return ::buildByrefHelpers(CGM, byrefInfo,
                           ObjectByrefHelpers(valueAlignment, flags));
2594}

2596Address CodeGenFunction::emitBlockByrefAddress(Address baseAddr,
                                             const VarDecl *var,
                                             bool followForward) {
auto &info = getBlockByrefInfo(var);
return emitBlockByrefAddress(baseAddr, info, followForward, var->getName());
2601}

2603Address CodeGenFunction::emitBlockByrefAddress(Address baseAddr,
                                             const BlockByrefInfo &info,
                                             bool followForward,
                                             const llvm::Twine &name) {
// Chase the forwarding address if requested.
if (followForward) {
  Address forwardingAddr = Builder.CreateStructGEP(baseAddr, 1, "forwarding");
  baseAddr = Address(Builder.CreateLoad(forwardingAddr), info.ByrefAlignment);
}

return Builder.CreateStructGEP(baseAddr, info.FieldIndex, name);
2614}

2616/// BuildByrefInfo - This routine changes a __block variable declared as T x
2617///   into:
2618///
2619///      struct {
2620///        void *__isa;
2621///        void *__forwarding;
2622///        int32_t __flags;
2623///        int32_t __size;
2624///        void *__copy_helper;       // only if needed
2625///        void *__destroy_helper;    // only if needed
2626///        void *__byref_variable_layout;// only if needed
2627///        char padding[X];           // only if needed
2628///        T x;
2629///      } x
2630///
2631const BlockByrefInfo &CodeGenFunction::getBlockByrefInfo(const VarDecl *D) {
auto it = BlockByrefInfos.find(D);
if (it != BlockByrefInfos.end())
  return it->second;

llvm::StructType *byrefType =
  llvm::StructType::create(getLLVMContext(),
                           "struct.__block_byref_" + D->getNameAsString());

QualType Ty = D->getType();

CharUnits size;
SmallVector<llvm::Type *, 8> types;

// void *__isa;
types.push_back(Int8PtrTy);
size += getPointerSize();

// void *__forwarding;
types.push_back(llvm::PointerType::getUnqual(byrefType));
size += getPointerSize();

// int32_t __flags;
types.push_back(Int32Ty);
size += CharUnits::fromQuantity(4);

// int32_t __size;
types.push_back(Int32Ty);
size += CharUnits::fromQuantity(4);

// Note that this must match *exactly* the logic in buildByrefHelpers.
bool hasCopyAndDispose = getContext().BlockRequiresCopying(Ty, D);
if (hasCopyAndDispose) {
  /// void *__copy_helper;
  types.push_back(Int8PtrTy);
  size += getPointerSize();

  /// void *__destroy_helper;
  types.push_back(Int8PtrTy);
  size += getPointerSize();
}

bool HasByrefExtendedLayout = false;
Qualifiers::ObjCLifetime Lifetime = Qualifiers::OCL_None;
if (getContext().getByrefLifetime(Ty, Lifetime, HasByrefExtendedLayout) &&
    HasByrefExtendedLayout) {
  /// void *__byref_variable_layout;
  types.push_back(Int8PtrTy);
  size += CharUnits::fromQuantity(PointerSizeInBytes);
}

// T x;
llvm::Type *varTy = ConvertTypeForMem(Ty);

bool packed = false;
CharUnits varAlign = getContext().getDeclAlign(D);
CharUnits varOffset = size.alignTo(varAlign);

// We may have to insert padding.
if (varOffset != size) {
  llvm::Type *paddingTy =
    llvm::ArrayType::get(Int8Ty, (varOffset - size).getQuantity());

  types.push_back(paddingTy);
  size = varOffset;

// Conversely, we might have to prevent LLVM from inserting padding.
} else if (CGM.getDataLayout().getABITypeAlignment(varTy)
             > varAlign.getQuantity()) {
  packed = true;
}
types.push_back(varTy);

byrefType->setBody(types, packed);

BlockByrefInfo info;
info.Type = byrefType;
info.FieldIndex = types.size() - 1;
info.FieldOffset = varOffset;
info.ByrefAlignment = std::max(varAlign, getPointerAlign());

auto pair = BlockByrefInfos.insert({D, info});
assert(pair.second && "info was inserted recursively?")((void)0);
return pair.first->second;
2715}

2717/// Initialize the structural components of a __block variable, i.e.
2718/// everything but the actual object.
2719void CodeGenFunction::emitByrefStructureInit(const AutoVarEmission &emission) {
// Find the address of the local.
Address addr = emission.Addr;

// That's an alloca of the byref structure type.
llvm::StructType *byrefType = cast<llvm::StructType>(
  cast<llvm::PointerType>(addr.getPointer()->getType())->getElementType());

unsigned nextHeaderIndex = 0;
CharUnits nextHeaderOffset;
auto storeHeaderField = [&](llvm::Value *value, CharUnits fieldSize,
                            const Twine &name) {
  auto fieldAddr = Builder.CreateStructGEP(addr, nextHeaderIndex, name);
  Builder.CreateStore(value, fieldAddr);

  nextHeaderIndex++;
  nextHeaderOffset += fieldSize;
};

// Build the byref helpers if necessary.  This is null if we don't need any.
BlockByrefHelpers *helpers = buildByrefHelpers(*byrefType, emission);

const VarDecl &D = *emission.Variable;
QualType type = D.getType();

bool HasByrefExtendedLayout = false;
Qualifiers::ObjCLifetime ByrefLifetime = Qualifiers::OCL_None;
bool ByRefHasLifetime =
  getContext().getByrefLifetime(type, ByrefLifetime, HasByrefExtendedLayout);

llvm::Value *V;

// Initialize the 'isa', which is just 0 or 1.
int isa = 0;
if (type.isObjCGCWeak())
  isa = 1;
V = Builder.CreateIntToPtr(Builder.getInt32(isa), Int8PtrTy, "isa");
storeHeaderField(V, getPointerSize(), "byref.isa");

// Store the address of the variable into its own forwarding pointer.
storeHeaderField(addr.getPointer(), getPointerSize(), "byref.forwarding");

// Blocks ABI:
//   c) the flags field is set to either 0 if no helper functions are
//      needed or BLOCK_BYREF_HAS_COPY_DISPOSE if they are,
BlockFlags flags;
if (helpers) flags |= BLOCK_BYREF_HAS_COPY_DISPOSE;
if (ByRefHasLifetime) {
  if (HasByrefExtendedLayout) flags |= BLOCK_BYREF_LAYOUT_EXTENDED;
    else switch (ByrefLifetime) {
      case Qualifiers::OCL_Strong:
        flags |= BLOCK_BYREF_LAYOUT_STRONG;
        break;
      case Qualifiers::OCL_Weak:
        flags |= BLOCK_BYREF_LAYOUT_WEAK;
        break;
      case Qualifiers::OCL_ExplicitNone:
        flags |= BLOCK_BYREF_LAYOUT_UNRETAINED;
        break;
      case Qualifiers::OCL_None:
        if (!type->isObjCObjectPointerType() && !type->isBlockPointerType())
          flags |= BLOCK_BYREF_LAYOUT_NON_OBJECT;
        break;
      default:
        break;
    }
  if (CGM.getLangOpts().ObjCGCBitmapPrint) {
    printf("\n Inline flag for BYREF variable layout (%d):", flags.getBitMask());
    if (flags & BLOCK_BYREF_HAS_COPY_DISPOSE)
      printf(" BLOCK_BYREF_HAS_COPY_DISPOSE");
    if (flags & BLOCK_BYREF_LAYOUT_MASK) {
      BlockFlags ThisFlag(flags.getBitMask() & BLOCK_BYREF_LAYOUT_MASK);
      if (ThisFlag ==  BLOCK_BYREF_LAYOUT_EXTENDED)
        printf(" BLOCK_BYREF_LAYOUT_EXTENDED");
      if (ThisFlag ==  BLOCK_BYREF_LAYOUT_STRONG)
        printf(" BLOCK_BYREF_LAYOUT_STRONG");
      if (ThisFlag == BLOCK_BYREF_LAYOUT_WEAK)
        printf(" BLOCK_BYREF_LAYOUT_WEAK");
      if (ThisFlag == BLOCK_BYREF_LAYOUT_UNRETAINED)
        printf(" BLOCK_BYREF_LAYOUT_UNRETAINED");
      if (ThisFlag == BLOCK_BYREF_LAYOUT_NON_OBJECT)
        printf(" BLOCK_BYREF_LAYOUT_NON_OBJECT");
    }
    printf("\n");
  }
}
storeHeaderField(llvm::ConstantInt::get(IntTy, flags.getBitMask()),
                 getIntSize(), "byref.flags");

CharUnits byrefSize = CGM.GetTargetTypeStoreSize(byrefType);
V = llvm::ConstantInt::get(IntTy, byrefSize.getQuantity());
storeHeaderField(V, getIntSize(), "byref.size");

if (helpers) {
  storeHeaderField(helpers->CopyHelper, getPointerSize(),
                   "byref.copyHelper");
  storeHeaderField(helpers->DisposeHelper, getPointerSize(),
                   "byref.disposeHelper");
}

if (ByRefHasLifetime && HasByrefExtendedLayout) {
  auto layoutInfo = CGM.getObjCRuntime().BuildByrefLayout(CGM, type);
  storeHeaderField(layoutInfo, getPointerSize(), "byref.layout");
}
2823}

2825void CodeGenFunction::BuildBlockRelease(llvm::Value *V, BlockFieldFlags flags,
                                      bool CanThrow) {
llvm::FunctionCallee F = CGM.getBlockObjectDispose();
llvm::Value *args[] = {
  Builder.CreateBitCast(V, Int8PtrTy),
  llvm::ConstantInt::get(Int32Ty, flags.getBitMask())
};

if (CanThrow)
  EmitRuntimeCallOrInvoke(F, args);
else
  EmitNounwindRuntimeCall(F, args);
2837}

2839void CodeGenFunction::enterByrefCleanup(CleanupKind Kind, Address Addr,
                                      BlockFieldFlags Flags,
                                      bool LoadBlockVarAddr, bool CanThrow) {
EHStack.pushCleanup<CallBlockRelease>(Kind, Addr, Flags, LoadBlockVarAddr,
                                      CanThrow);
2844}

2846/// Adjust the declaration of something from the blocks API.
2847static void configureBlocksRuntimeObject(CodeGenModule &CGM,
                                       llvm::Constant *C) {
auto *GV = cast<llvm::GlobalValue>(C->stripPointerCasts());

if (CGM.getTarget().getTriple().isOSBinFormatCOFF()) {
  IdentifierInfo &II = CGM.getContext().Idents.get(C->getName());
  TranslationUnitDecl *TUDecl = CGM.getContext().getTranslationUnitDecl();
  DeclContext *DC = TranslationUnitDecl::castToDeclContext(TUDecl);

  assert((isa<llvm::Function>(C->stripPointerCasts()) ||((void)0)
          isa<llvm::GlobalVariable>(C->stripPointerCasts())) &&((void)0)
         "expected Function or GlobalVariable")((void)0);

  const NamedDecl *ND = nullptr;
  for (const auto *Result : DC->lookup(&II))
    if ((ND = dyn_cast<FunctionDecl>(Result)) ||
        (ND = dyn_cast<VarDecl>(Result)))
      break;

  // TODO: support static blocks runtime
  if (GV->isDeclaration() && (!ND || !ND->hasAttr<DLLExportAttr>())) {
    GV->setDLLStorageClass(llvm::GlobalValue::DLLImportStorageClass);
    GV->setLinkage(llvm::GlobalValue::ExternalLinkage);
  } else {
    GV->setDLLStorageClass(llvm::GlobalValue::DLLExportStorageClass);
    GV->setLinkage(llvm::GlobalValue::ExternalLinkage);
  }
}

if (CGM.getLangOpts().BlocksRuntimeOptional && GV->isDeclaration() &&
    GV->hasExternalLinkage())
  GV->setLinkage(llvm::GlobalValue::ExternalWeakLinkage);

CGM.setDSOLocal(GV);
2881}

2883llvm::FunctionCallee CodeGenModule::getBlockObjectDispose() {
if (BlockObjectDispose)
  return BlockObjectDispose;

llvm::Type *args[] = { Int8PtrTy, Int32Ty };
llvm::FunctionType *fty
  = llvm::FunctionType::get(VoidTy, args, false);
BlockObjectDispose = CreateRuntimeFunction(fty, "_Block_object_dispose");
configureBlocksRuntimeObject(
    *this, cast<llvm::Constant>(BlockObjectDispose.getCallee()));
return BlockObjectDispose;
2894}

2896llvm::FunctionCallee CodeGenModule::getBlockObjectAssign() {
if (BlockObjectAssign)
  return BlockObjectAssign;

llvm::Type *args[] = { Int8PtrTy, Int8PtrTy, Int32Ty };
llvm::FunctionType *fty
  = llvm::FunctionType::get(VoidTy, args, false);
BlockObjectAssign = CreateRuntimeFunction(fty, "_Block_object_assign");
configureBlocksRuntimeObject(
    *this, cast<llvm::Constant>(BlockObjectAssign.getCallee()));
return BlockObjectAssign;
2907}

2909llvm::Constant *CodeGenModule::getNSConcreteGlobalBlock() {
if (NSConcreteGlobalBlock)
  return NSConcreteGlobalBlock;

NSConcreteGlobalBlock =
    GetOrCreateLLVMGlobal("_NSConcreteGlobalBlock", Int8PtrTy, 0, nullptr);
configureBlocksRuntimeObject(*this, NSConcreteGlobalBlock);
return NSConcreteGlobalBlock;
2917}

2919llvm::Constant *CodeGenModule::getNSConcreteStackBlock() {
if (NSConcreteStackBlock)
  return NSConcreteStackBlock;

NSConcreteStackBlock =
    GetOrCreateLLVMGlobal("_NSConcreteStackBlock", Int8PtrTy, 0, nullptr);
configureBlocksRuntimeObject(*this, NSConcreteStackBlock);
return NSConcreteStackBlock;
2927}

←

/usr/src/gnu/usr.bin/clang/libclangCodeGen/../../../llvm/clang/include/clang/AST/CharUnits.h

→

1//===--- CharUnits.h - Character units for sizes and offsets ----*- 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 defines the CharUnits class
10//
11//===----------------------------------------------------------------------===//

13#ifndef LLVM_CLANG_AST_CHARUNITS_H
14#define LLVM_CLANG_AST_CHARUNITS_H

16#include "llvm/ADT/DenseMapInfo.h"
17#include "llvm/Support/Alignment.h"
18#include "llvm/Support/DataTypes.h"
19#include "llvm/Support/MathExtras.h"

21namespace clang {

/// CharUnits - This is an opaque type for sizes expressed in character units.
/// Instances of this type represent a quantity as a multiple of the size
/// of the standard C type, char, on the target architecture. As an opaque
/// type, CharUnits protects you from accidentally combining operations on
/// quantities in bit units and character units.
///
/// In both C and C++, an object of type 'char', 'signed char', or 'unsigned
/// char' occupies exactly one byte, so 'character unit' and 'byte' refer to
/// the same quantity of storage. However, we use the term 'character unit'
/// rather than 'byte' to avoid an implication that a character unit is
/// exactly 8 bits.
///
/// For portability, never assume that a target character is 8 bits wide. Use
/// CharUnit values wherever you calculate sizes, offsets, or alignments
/// in character units.
class CharUnits {
  public:
    typedef int64_t QuantityType;

  private:
    QuantityType Quantity = 0;
8
←
The value 0 is assigned to 'maxFieldAlign.Quantity'→

    explicit CharUnits(QuantityType C) : Quantity(C) {}

  public:

    /// CharUnits - A default constructor.
    CharUnits() = default;

    /// Zero - Construct a CharUnits quantity of zero.
    static CharUnits Zero() {
      return CharUnits(0);
    }

    /// One - Construct a CharUnits quantity of one.
    static CharUnits One() {
      return CharUnits(1);
    }

    /// fromQuantity - Construct a CharUnits quantity from a raw integer type.
    static CharUnits fromQuantity(QuantityType Quantity) {
      return CharUnits(Quantity);
    }

    // Compound assignment.
    CharUnits& operator+= (const CharUnits &Other) {
      Quantity += Other.Quantity;
      return *this;
    }
    CharUnits& operator++ () {
      ++Quantity;
      return *this;
    }
    CharUnits operator++ (int) {
      return CharUnits(Quantity++);
    }
    CharUnits& operator-= (const CharUnits &Other) {
      Quantity -= Other.Quantity;
      return *this;
    }
    CharUnits& operator-- () {
      --Quantity;
      return *this;
    }
    CharUnits operator-- (int) {
      return CharUnits(Quantity--);
    }

    // Comparison operators.
    bool operator== (const CharUnits &Other) const {
      return Quantity == Other.Quantity;
    }
    bool operator!= (const CharUnits &Other) const {
      return Quantity != Other.Quantity;
    }

    // Relational operators.
    bool operator<  (const CharUnits &Other) const {
      return Quantity <  Other.Quantity;
    }
    bool operator<= (const CharUnits &Other) const {
      return Quantity <= Other.Quantity;
    }
    bool operator>  (const CharUnits &Other) const {
      return Quantity >  Other.Quantity;
    }
    bool operator>= (const CharUnits &Other) const {
      return Quantity >= Other.Quantity;
    }

    // Other predicates.

    /// isZero - Test whether the quantity equals zero.
    bool isZero() const     { return Quantity == 0; }

    /// isOne - Test whether the quantity equals one.
    bool isOne() const      { return Quantity == 1; }

    /// isPositive - Test whether the quantity is greater than zero.
    bool isPositive() const { return Quantity  > 0; }

    /// isNegative - Test whether the quantity is less than zero.
    bool isNegative() const { return Quantity  < 0; }

    /// isPowerOfTwo - Test whether the quantity is a power of two.
    /// Zero is not a power of two.
    bool isPowerOfTwo() const {
      return (Quantity & -Quantity) == Quantity;
    }

    /// Test whether this is a multiple of the other value.
    ///
    /// Among other things, this promises that
    /// self.alignTo(N) will just return self.
    bool isMultipleOf(CharUnits N) const {
      return (*this % N) == 0;
    }

    // Arithmetic operators.
    CharUnits operator* (QuantityType N) const {
      return CharUnits(Quantity * N);
    }
    CharUnits &operator*= (QuantityType N) {
      Quantity *= N;
      return *this;
    }
    CharUnits operator/ (QuantityType N) const {
      return CharUnits(Quantity / N);
    }
    CharUnits &operator/= (QuantityType N) {
      Quantity /= N;
      return *this;
    }
    QuantityType operator/ (const CharUnits &Other) const {
      return Quantity / Other.Quantity;
    }
    CharUnits operator% (QuantityType N) const {
      return CharUnits(Quantity % N);
    }
    QuantityType operator% (const CharUnits &Other) const {
      return Quantity % Other.Quantity;
    }
    CharUnits operator+ (const CharUnits &Other) const {
      return CharUnits(Quantity + Other.Quantity);
    }
    CharUnits operator- (const CharUnits &Other) const {
      return CharUnits(Quantity - Other.Quantity);
    }
    CharUnits operator- () const {
      return CharUnits(-Quantity);
    }


    // Conversions.

    /// getQuantity - Get the raw integer representation of this quantity.
    QuantityType getQuantity() const { return Quantity; }

    /// getAsAlign - Returns Quantity as a valid llvm::Align,
    /// Beware llvm::Align assumes power of two 8-bit bytes.
    llvm::Align getAsAlign() const { return llvm::Align(Quantity); }

    /// alignTo - Returns the next integer (mod 2**64) that is
    /// greater than or equal to this quantity and is a multiple of \p Align.
    /// Align must be non-zero.
    CharUnits alignTo(const CharUnits &Align) const {
      return CharUnits(llvm::alignTo(Quantity, Align.Quantity));
20
←
Passing the value 0 via 2nd parameter 'Align'→
21
←
Calling 'alignTo'→
    }

    /// Given that this is a non-zero alignment value, what is the
    /// alignment at the given offset?
    CharUnits alignmentAtOffset(CharUnits offset) const {
      assert(Quantity != 0 && "offsetting from unknown alignment?")((void)0);
      return CharUnits(llvm::MinAlign(Quantity, offset.Quantity));
    }

    /// Given that this is the alignment of the first element of an
    /// array, return the minimum alignment of any element in the array.
    CharUnits alignmentOfArrayElement(CharUnits elementSize) const {
      // Since we don't track offsetted alignments, the alignment of
      // the second element (or any odd element) will be minimally
      // aligned.
      return alignmentAtOffset(elementSize);
    }


}; // class CharUnit
210} // namespace clang

212inline clang::CharUnits operator* (clang::CharUnits::QuantityType Scale,
                                 const clang::CharUnits &CU) {
return CU * Scale;
215}

217namespace llvm {

219template<> struct DenseMapInfo<clang::CharUnits> {
static clang::CharUnits getEmptyKey() {
  clang::CharUnits::QuantityType Quantity =
    DenseMapInfo<clang::CharUnits::QuantityType>::getEmptyKey();

  return clang::CharUnits::fromQuantity(Quantity);
}

static clang::CharUnits getTombstoneKey() {
  clang::CharUnits::QuantityType Quantity =
    DenseMapInfo<clang::CharUnits::QuantityType>::getTombstoneKey();

  return clang::CharUnits::fromQuantity(Quantity);
}

static unsigned getHashValue(const clang::CharUnits &CU) {
  clang::CharUnits::QuantityType Quantity = CU.getQuantity();
  return DenseMapInfo<clang::CharUnits::QuantityType>::getHashValue(Quantity);
}

static bool isEqual(const clang::CharUnits &LHS,
                    const clang::CharUnits &RHS) {
  return LHS == RHS;
}
243};

245} // end namespace llvm

247#endif // LLVM_CLANG_AST_CHARUNITS_H

←

/usr/src/gnu/usr.bin/clang/libclangCodeGen/../../../llvm/llvm/include/llvm/Support/MathExtras.h

1//===-- llvm/Support/MathExtras.h - Useful math 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 functions that are useful for math stuff.
10//
11//===----------------------------------------------------------------------===//
12 
13#ifndef LLVM_SUPPORT_MATHEXTRAS_H
14#define LLVM_SUPPORT_MATHEXTRAS_H
15 
16#include "llvm/Support/Compiler.h"
17#include <cassert>
18#include <climits>
19#include <cmath>
20#include <cstdint>
21#include <cstring>
22#include <limits>
23#include <type_traits>
24 
25#ifdef __ANDROID_NDK__
26#include <android/api-level.h>
27#endif
28 
29#ifdef _MSC_VER
30// Declare these intrinsics manually rather including intrin.h. It's very
31// expensive, and MathExtras.h is popular.
32// #include <intrin.h>
33extern "C" {
34unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask);
35unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask);
36unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask);
37unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask);
38}
39#endif
40 
41namespace llvm {
42 
43/// The behavior an operation has on an input of 0.
44enum ZeroBehavior {
45  /// The returned value is undefined.
46  ZB_Undefined,
47  /// The returned value is numeric_limits<T>::max()
48  ZB_Max,
49  /// The returned value is numeric_limits<T>::digits
50  ZB_Width
51};
52 
53/// Mathematical constants.
54namespace numbers {
55// TODO: Track C++20 std::numbers.
56// TODO: Favor using the hexadecimal FP constants (requires C++17).
57constexpr double e          = 2.7182818284590452354, // (0x1.5bf0a8b145749P+1) https://oeis.org/A001113
58                 egamma     = .57721566490153286061, // (0x1.2788cfc6fb619P-1) https://oeis.org/A001620
59                 ln2        = .69314718055994530942, // (0x1.62e42fefa39efP-1) https://oeis.org/A002162
60                 ln10       = 2.3025850929940456840, // (0x1.24bb1bbb55516P+1) https://oeis.org/A002392
61                 log2e      = 1.4426950408889634074, // (0x1.71547652b82feP+0)
62                 log10e     = .43429448190325182765, // (0x1.bcb7b1526e50eP-2)
63                 pi         = 3.1415926535897932385, // (0x1.921fb54442d18P+1) https://oeis.org/A000796
64                 inv_pi     = .31830988618379067154, // (0x1.45f306bc9c883P-2) https://oeis.org/A049541
65                 sqrtpi     = 1.7724538509055160273, // (0x1.c5bf891b4ef6bP+0) https://oeis.org/A002161
66                 inv_sqrtpi = .56418958354775628695, // (0x1.20dd750429b6dP-1) https://oeis.org/A087197
67                 sqrt2      = 1.4142135623730950488, // (0x1.6a09e667f3bcdP+0) https://oeis.org/A00219
68                 inv_sqrt2  = .70710678118654752440, // (0x1.6a09e667f3bcdP-1)
69                 sqrt3      = 1.7320508075688772935, // (0x1.bb67ae8584caaP+0) https://oeis.org/A002194
70                 inv_sqrt3  = .57735026918962576451, // (0x1.279a74590331cP-1)
71                 phi        = 1.6180339887498948482; // (0x1.9e3779b97f4a8P+0) https://oeis.org/A001622
72constexpr float ef          = 2.71828183F, // (0x1.5bf0a8P+1) https://oeis.org/A001113
73                egammaf     = .577215665F, // (0x1.2788d0P-1) https://oeis.org/A001620
74                ln2f        = .693147181F, // (0x1.62e430P-1) https://oeis.org/A002162
75                ln10f       = 2.30258509F, // (0x1.26bb1cP+1) https://oeis.org/A002392
76                log2ef      = 1.44269504F, // (0x1.715476P+0)
77                log10ef     = .434294482F, // (0x1.bcb7b2P-2)
78                pif         = 3.14159265F, // (0x1.921fb6P+1) https://oeis.org/A000796
79                inv_pif     = .318309886F, // (0x1.45f306P-2) https://oeis.org/A049541
80                sqrtpif     = 1.77245385F, // (0x1.c5bf8aP+0) https://oeis.org/A002161
81                inv_sqrtpif = .564189584F, // (0x1.20dd76P-1) https://oeis.org/A087197
82                sqrt2f      = 1.41421356F, // (0x1.6a09e6P+0) https://oeis.org/A002193
83                inv_sqrt2f  = .707106781F, // (0x1.6a09e6P-1)
84                sqrt3f      = 1.73205081F, // (0x1.bb67aeP+0) https://oeis.org/A002194
85                inv_sqrt3f  = .577350269F, // (0x1.279a74P-1)
86                phif        = 1.61803399F; // (0x1.9e377aP+0) https://oeis.org/A001622
87} // namespace numbers
88 
89namespace detail {
90template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter {
91  static unsigned count(T Val, ZeroBehavior) {
92    if (!Val)
93      return std::numeric_limits<T>::digits;
94    if (Val & 0x1)
95      return 0;
96 
97    // Bisection method.
98    unsigned ZeroBits = 0;
99    T Shift = std::numeric_limits<T>::digits >> 1;
100    T Mask = std::numeric_limits<T>::max() >> Shift;
101    while (Shift) {
102      if ((Val & Mask) == 0) {
103        Val >>= Shift;
104        ZeroBits |= Shift;
105      }
106      Shift >>= 1;
107      Mask >>= Shift;
108    }
109    return ZeroBits;
110  }
111};
112 
113#if defined(__GNUC__4) || defined(_MSC_VER)
114template <typename T> struct TrailingZerosCounter<T, 4> {
115  static unsigned count(T Val, ZeroBehavior ZB) {
116    if (ZB != ZB_Undefined && Val == 0)
117      return 32;
118 
119#if __has_builtin(__builtin_ctz)1 || defined(__GNUC__4)
120    return __builtin_ctz(Val);
121#elif defined(_MSC_VER)
122    unsigned long Index;
123    _BitScanForward(&Index, Val);
124    return Index;
125#endif
126  }
127};
128 
129#if !defined(_MSC_VER) || defined(_M_X64)
130template <typename T> struct TrailingZerosCounter<T, 8> {
131  static unsigned count(T Val, ZeroBehavior ZB) {
132    if (ZB != ZB_Undefined && Val == 0)
133      return 64;
134 
135#if __has_builtin(__builtin_ctzll)1 || defined(__GNUC__4)
136    return __builtin_ctzll(Val);
137#elif defined(_MSC_VER)
138    unsigned long Index;
139    _BitScanForward64(&Index, Val);
140    return Index;
141#endif
142  }
143};
144#endif
145#endif
146} // namespace detail
147 
148/// Count number of 0's from the least significant bit to the most
149///   stopping at the first 1.
150///
151/// Only unsigned integral types are allowed.
152///
153/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
154///   valid arguments.
155template <typename T>
156unsigned countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
157  static_assert(std::numeric_limits<T>::is_integer &&
158                    !std::numeric_limits<T>::is_signed,
159                "Only unsigned integral types are allowed.");
160  return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
161}
162 
163namespace detail {
164template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter {
165  static unsigned count(T Val, ZeroBehavior) {
166    if (!Val)
167      return std::numeric_limits<T>::digits;
168 
169    // Bisection method.
170    unsigned ZeroBits = 0;
171    for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
172      T Tmp = Val >> Shift;
173      if (Tmp)
174        Val = Tmp;
175      else
176        ZeroBits |= Shift;
177    }
178    return ZeroBits;
179  }
180};
181 
182#if defined(__GNUC__4) || defined(_MSC_VER)
183template <typename T> struct LeadingZerosCounter<T, 4> {
184  static unsigned count(T Val, ZeroBehavior ZB) {
185    if (ZB != ZB_Undefined && Val == 0)
186      return 32;
187 
188#if __has_builtin(__builtin_clz)1 || defined(__GNUC__4)
189    return __builtin_clz(Val);
190#elif defined(_MSC_VER)
191    unsigned long Index;
192    _BitScanReverse(&Index, Val);
193    return Index ^ 31;
194#endif
195  }
196};
197 
198#if !defined(_MSC_VER) || defined(_M_X64)
199template <typename T> struct LeadingZerosCounter<T, 8> {
200  static unsigned count(T Val, ZeroBehavior ZB) {
201    if (ZB != ZB_Undefined && Val == 0)
202      return 64;
203 
204#if __has_builtin(__builtin_clzll)1 || defined(__GNUC__4)
205    return __builtin_clzll(Val);
206#elif defined(_MSC_VER)
207    unsigned long Index;
208    _BitScanReverse64(&Index, Val);
209    return Index ^ 63;
210#endif
211  }
212};
213#endif
214#endif
215} // namespace detail
216 
217/// Count number of 0's from the most significant bit to the least
218///   stopping at the first 1.
219///
220/// Only unsigned integral types are allowed.
221///
222/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
223///   valid arguments.
224template <typename T>
225unsigned countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
226  static_assert(std::numeric_limits<T>::is_integer &&
227                    !std::numeric_limits<T>::is_signed,
228                "Only unsigned integral types are allowed.");
229  return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val, ZB);
230}
231 
232/// Get the index of the first set bit starting from the least
233///   significant bit.
234///
235/// Only unsigned integral types are allowed.
236///
237/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
238///   valid arguments.
239template <typename T> T findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) {
240  if (ZB == ZB_Max && Val == 0)
241    return std::numeric_limits<T>::max();
242 
243  return countTrailingZeros(Val, ZB_Undefined);
244}
245 
246/// Create a bitmask with the N right-most bits set to 1, and all other
247/// bits set to 0.  Only unsigned types are allowed.
248template <typename T> T maskTrailingOnes(unsigned N) {
249  static_assert(std::is_unsigned<T>::value, "Invalid type!");
250  const unsigned Bits = CHAR_BIT8 * sizeof(T);
251  assert(N <= Bits && "Invalid bit index")((void)0);
252  return N == 0 ? 0 : (T(-1) >> (Bits - N));
253}
254 
255/// Create a bitmask with the N left-most bits set to 1, and all other
256/// bits set to 0.  Only unsigned types are allowed.
257template <typename T> T maskLeadingOnes(unsigned N) {
258  return ~maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
259}
260 
261/// Create a bitmask with the N right-most bits set to 0, and all other
262/// bits set to 1.  Only unsigned types are allowed.
263template <typename T> T maskTrailingZeros(unsigned N) {
264  return maskLeadingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
265}
266 
267/// Create a bitmask with the N left-most bits set to 0, and all other
268/// bits set to 1.  Only unsigned types are allowed.
269template <typename T> T maskLeadingZeros(unsigned N) {
270  return maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
271}
272 
273/// Get the index of the last set bit starting from the least
274///   significant bit.
275///
276/// Only unsigned integral types are allowed.
277///
278/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
279///   valid arguments.
280template <typename T> T findLastSet(T Val, ZeroBehavior ZB = ZB_Max) {
281  if (ZB == ZB_Max && Val == 0)
282    return std::numeric_limits<T>::max();
283 
284  // Use ^ instead of - because both gcc and llvm can remove the associated ^
285  // in the __builtin_clz intrinsic on x86.
286  return countLeadingZeros(Val, ZB_Undefined) ^
287         (std::numeric_limits<T>::digits - 1);
288}
289 
290/// Macro compressed bit reversal table for 256 bits.
291///
292/// http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
293static const unsigned char BitReverseTable256[256] = {
294#define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64
295#define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16)
296#define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4)
297  R6(0), R6(2), R6(1), R6(3)
298#undef R2
299#undef R4
300#undef R6
301};
302 
303/// Reverse the bits in \p Val.
304template <typename T>
305T reverseBits(T Val) {
306  unsigned char in[sizeof(Val)];
307  unsigned char out[sizeof(Val)];
308  std::memcpy(in, &Val, sizeof(Val));
309  for (unsigned i = 0; i < sizeof(Val); ++i)
310    out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
311  std::memcpy(&Val, out, sizeof(Val));
312  return Val;
313}
314 
315#if __has_builtin(__builtin_bitreverse8)1
316template<>
317inline uint8_t reverseBits<uint8_t>(uint8_t Val) {
318  return __builtin_bitreverse8(Val);
319}
320#endif
321 
322#if __has_builtin(__builtin_bitreverse16)1
323template<>
324inline uint16_t reverseBits<uint16_t>(uint16_t Val) {
325  return __builtin_bitreverse16(Val);
326}
327#endif
328 
329#if __has_builtin(__builtin_bitreverse32)1
330template<>
331inline uint32_t reverseBits<uint32_t>(uint32_t Val) {
332  return __builtin_bitreverse32(Val);
333}
334#endif
335 
336#if __has_builtin(__builtin_bitreverse64)1
337template<>
338inline uint64_t reverseBits<uint64_t>(uint64_t Val) {
339  return __builtin_bitreverse64(Val);
340}
341#endif
342 
343// NOTE: The following support functions use the _32/_64 extensions instead of
344// type overloading so that signed and unsigned integers can be used without
345// ambiguity.
346 
347/// Return the high 32 bits of a 64 bit value.
348constexpr inline uint32_t Hi_32(uint64_t Value) {
349  return static_cast<uint32_t>(Value >> 32);
350}
351 
352/// Return the low 32 bits of a 64 bit value.
353constexpr inline uint32_t Lo_32(uint64_t Value) {
354  return static_cast<uint32_t>(Value);
355}
356 
357/// Make a 64-bit integer from a high / low pair of 32-bit integers.
358constexpr inline uint64_t Make_64(uint32_t High, uint32_t Low) {
359  return ((uint64_t)High << 32) | (uint64_t)Low;
360}
361 
362/// Checks if an integer fits into the given bit width.
363template <unsigned N> constexpr inline bool isInt(int64_t x) {
364  return N >= 64 || (-(INT64_C(1)1LL<<(N-1)) <= x && x < (INT64_C(1)1LL<<(N-1)));
365}
366// Template specializations to get better code for common cases.
367template <> constexpr inline bool isInt<8>(int64_t x) {
368  return static_cast<int8_t>(x) == x;
369}
370template <> constexpr inline bool isInt<16>(int64_t x) {
371  return static_cast<int16_t>(x) == x;
372}
373template <> constexpr inline bool isInt<32>(int64_t x) {
374  return static_cast<int32_t>(x) == x;
375}
376 
377/// Checks if a signed integer is an N bit number shifted left by S.
378template <unsigned N, unsigned S>
379constexpr inline bool isShiftedInt(int64_t x) {
380  static_assert(
381      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
382  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
383  return isInt<N + S>(x) && (x % (UINT64_C(1)1ULL << S) == 0);
384}
385 
386/// Checks if an unsigned integer fits into the given bit width.
387///
388/// This is written as two functions rather than as simply
389///
390///   return N >= 64 || X < (UINT64_C(1) << N);
391///
392/// to keep MSVC from (incorrectly) warning on isUInt<64> that we're shifting
393/// left too many places.
394template <unsigned N>
395constexpr inline std::enable_if_t<(N < 64), bool> isUInt(uint64_t X) {
396  static_assert(N > 0, "isUInt<0> doesn't make sense");
397  return X < (UINT64_C(1)1ULL << (N));
398}
399template <unsigned N>
400constexpr inline std::enable_if_t<N >= 64, bool> isUInt(uint64_t) {
401  return true;
402}
403 
404// Template specializations to get better code for common cases.
405template <> constexpr inline bool isUInt<8>(uint64_t x) {
406  return static_cast<uint8_t>(x) == x;
407}
408template <> constexpr inline bool isUInt<16>(uint64_t x) {
409  return static_cast<uint16_t>(x) == x;
410}
411template <> constexpr inline bool isUInt<32>(uint64_t x) {
412  return static_cast<uint32_t>(x) == x;
413}
414 
415/// Checks if a unsigned integer is an N bit number shifted left by S.
416template <unsigned N, unsigned S>
417constexpr inline bool isShiftedUInt(uint64_t x) {
418  static_assert(
419      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
420  static_assert(N + S <= 64,
421                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
422  // Per the two static_asserts above, S must be strictly less than 64.  So
423  // 1 << S is not undefined behavior.
424  return isUInt<N + S>(x) && (x % (UINT64_C(1)1ULL << S) == 0);
425}
426 
427/// Gets the maximum value for a N-bit unsigned integer.
428inline uint64_t maxUIntN(uint64_t N) {
429  assert(N > 0 && N <= 64 && "integer width out of range")((void)0);
430 
431  // uint64_t(1) << 64 is undefined behavior, so we can't do
432  //   (uint64_t(1) << N) - 1
433  // without checking first that N != 64.  But this works and doesn't have a
434  // branch.
435  return UINT64_MAX0xffffffffffffffffULL >> (64 - N);
436}
437 
438/// Gets the minimum value for a N-bit signed integer.
439inline int64_t minIntN(int64_t N) {
440  assert(N > 0 && N <= 64 && "integer width out of range")((void)0);
441 
442  return UINT64_C(1)1ULL + ~(UINT64_C(1)1ULL << (N - 1));
443}
444 
445/// Gets the maximum value for a N-bit signed integer.
446inline int64_t maxIntN(int64_t N) {
447  assert(N > 0 && N <= 64 && "integer width out of range")((void)0);
448 
449  // This relies on two's complement wraparound when N == 64, so we convert to
450  // int64_t only at the very end to avoid UB.
451  return (UINT64_C(1)1ULL << (N - 1)) - 1;
452}
453 
454/// Checks if an unsigned integer fits into the given (dynamic) bit width.
455inline bool isUIntN(unsigned N, uint64_t x) {
456  return N >= 64 || x <= maxUIntN(N);
457}
458 
459/// Checks if an signed integer fits into the given (dynamic) bit width.
460inline bool isIntN(unsigned N, int64_t x) {
461  return N >= 64 || (minIntN(N) <= x && x <= maxIntN(N));
462}
463 
464/// Return true if the argument is a non-empty sequence of ones starting at the
465/// least significant bit with the remainder zero (32 bit version).
466/// Ex. isMask_32(0x0000FFFFU) == true.
467constexpr inline bool isMask_32(uint32_t Value) {
468  return Value && ((Value + 1) & Value) == 0;
469}
470 
471/// Return true if the argument is a non-empty sequence of ones starting at the
472/// least significant bit with the remainder zero (64 bit version).
473constexpr inline bool isMask_64(uint64_t Value) {
474  return Value && ((Value + 1) & Value) == 0;
475}
476 
477/// Return true if the argument contains a non-empty sequence of ones with the
478/// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true.
479constexpr inline bool isShiftedMask_32(uint32_t Value) {
480  return Value && isMask_32((Value - 1) | Value);
481}
482 
483/// Return true if the argument contains a non-empty sequence of ones with the
484/// remainder zero (64 bit version.)
485constexpr inline bool isShiftedMask_64(uint64_t Value) {
486  return Value && isMask_64((Value - 1) | Value);
487}
488 
489/// Return true if the argument is a power of two > 0.
490/// Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
491constexpr inline bool isPowerOf2_32(uint32_t Value) {
492  return Value && !(Value & (Value - 1));
493}
494 
495/// Return true if the argument is a power of two > 0 (64 bit edition.)
496constexpr inline bool isPowerOf2_64(uint64_t Value) {
497  return Value && !(Value & (Value - 1));
498}
499 
500/// Count the number of ones from the most significant bit to the first
501/// zero bit.
502///
503/// Ex. countLeadingOnes(0xFF0FFF00) == 8.
504/// Only unsigned integral types are allowed.
505///
506/// \param ZB the behavior on an input of all ones. Only ZB_Width and
507/// ZB_Undefined are valid arguments.
508template <typename T>
509unsigned countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
510  static_assert(std::numeric_limits<T>::is_integer &&
511                    !std::numeric_limits<T>::is_signed,
512                "Only unsigned integral types are allowed.");
513  return countLeadingZeros<T>(~Value, ZB);
514}
515 
516/// Count the number of ones from the least significant bit to the first
517/// zero bit.
518///
519/// Ex. countTrailingOnes(0x00FF00FF) == 8.
520/// Only unsigned integral types are allowed.
521///
522/// \param ZB the behavior on an input of all ones. Only ZB_Width and
523/// ZB_Undefined are valid arguments.
524template <typename T>
525unsigned countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
526  static_assert(std::numeric_limits<T>::is_integer &&
527                    !std::numeric_limits<T>::is_signed,
528                "Only unsigned integral types are allowed.");
529  return countTrailingZeros<T>(~Value, ZB);
530}
531 
532namespace detail {
533template <typename T, std::size_t SizeOfT> struct PopulationCounter {
534  static unsigned count(T Value) {
535    // Generic version, forward to 32 bits.
536    static_assert(SizeOfT <= 4, "Not implemented!");
537#if defined(__GNUC__4)
538    return __builtin_popcount(Value);
539#else
540    uint32_t v = Value;
541    v = v - ((v >> 1) & 0x55555555);
542    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
543    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
544#endif
545  }
546};
547 
548template <typename T> struct PopulationCounter<T, 8> {
549  static unsigned count(T Value) {
550#if defined(__GNUC__4)
551    return __builtin_popcountll(Value);
552#else
553    uint64_t v = Value;
554    v = v - ((v >> 1) & 0x5555555555555555ULL);
555    v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
556    v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
557    return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
558#endif
559  }
560};
561} // namespace detail
562 
563/// Count the number of set bits in a value.
564/// Ex. countPopulation(0xF000F000) = 8
565/// Returns 0 if the word is zero.
566template <typename T>
567inline unsigned countPopulation(T Value) {
568  static_assert(std::numeric_limits<T>::is_integer &&
569                    !std::numeric_limits<T>::is_signed,
570                "Only unsigned integral types are allowed.");
571  return detail::PopulationCounter<T, sizeof(T)>::count(Value);
572}
573 
574/// Compile time Log2.
575/// Valid only for positive powers of two.
576template <size_t kValue> constexpr inline size_t CTLog2() {
577  static_assert(kValue > 0 && llvm::isPowerOf2_64(kValue),
578                "Value is not a valid power of 2");
579  return 1 + CTLog2<kValue / 2>();
580}
581 
582template <> constexpr inline size_t CTLog2<1>() { return 0; }
583 
584/// Return the log base 2 of the specified value.
585inline double Log2(double Value) {
586#if defined(__ANDROID_API__) && __ANDROID_API__ < 18
587  return __builtin_log(Value) / __builtin_log(2.0);
588#else
589  return log2(Value);
590#endif
591}
592 
593/// Return the floor log base 2 of the specified value, -1 if the value is zero.
594/// (32 bit edition.)
595/// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
596inline unsigned Log2_32(uint32_t Value) {
597  return 31 - countLeadingZeros(Value);
598}
599 
600/// Return the floor log base 2 of the specified value, -1 if the value is zero.
601/// (64 bit edition.)
602inline unsigned Log2_64(uint64_t Value) {
603  return 63 - countLeadingZeros(Value);
604}
605 
606/// Return the ceil log base 2 of the specified value, 32 if the value is zero.
607/// (32 bit edition).
608/// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
609inline unsigned Log2_32_Ceil(uint32_t Value) {
610  return 32 - countLeadingZeros(Value - 1);
611}
612 
613/// Return the ceil log base 2 of the specified value, 64 if the value is zero.
614/// (64 bit edition.)
615inline unsigned Log2_64_Ceil(uint64_t Value) {
616  return 64 - countLeadingZeros(Value - 1);
617}
618 
619/// Return the greatest common divisor of the values using Euclid's algorithm.
620template <typename T>
621inline T greatestCommonDivisor(T A, T B) {
622  while (B) {
623    T Tmp = B;
624    B = A % B;
625    A = Tmp;
626  }
627  return A;
628}
629 
630inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
631  return greatestCommonDivisor<uint64_t>(A, B);
632}
633 
634/// This function takes a 64-bit integer and returns the bit equivalent double.
635inline double BitsToDouble(uint64_t Bits) {
636  double D;
637  static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
638  memcpy(&D, &Bits, sizeof(Bits));
639  return D;
640}
641 
642/// This function takes a 32-bit integer and returns the bit equivalent float.
643inline float BitsToFloat(uint32_t Bits) {
644  float F;
645  static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
646  memcpy(&F, &Bits, sizeof(Bits));
647  return F;
648}
649 
650/// This function takes a double and returns the bit equivalent 64-bit integer.
651/// Note that copying doubles around changes the bits of NaNs on some hosts,
652/// notably x86, so this routine cannot be used if these bits are needed.
653inline uint64_t DoubleToBits(double Double) {
654  uint64_t Bits;
655  static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
656  memcpy(&Bits, &Double, sizeof(Double));
657  return Bits;
658}
659 
660/// This function takes a float and returns the bit equivalent 32-bit integer.
661/// Note that copying floats around changes the bits of NaNs on some hosts,
662/// notably x86, so this routine cannot be used if these bits are needed.
663inline uint32_t FloatToBits(float Float) {
664  uint32_t Bits;
665  static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
666  memcpy(&Bits, &Float, sizeof(Float));
667  return Bits;
668}
669 
670/// A and B are either alignments or offsets. Return the minimum alignment that
671/// may be assumed after adding the two together.
672constexpr inline uint64_t MinAlign(uint64_t A, uint64_t B) {
673  // The largest power of 2 that divides both A and B.
674  //
675  // Replace "-Value" by "1+~Value" in the following commented code to avoid
676  // MSVC warning C4146
677  //    return (A | B) & -(A | B);
678  return (A | B) & (1 + ~(A | B));
679}
680 
681/// Returns the next power of two (in 64-bits) that is strictly greater than A.
682/// Returns zero on overflow.
683inline uint64_t NextPowerOf2(uint64_t A) {
684  A |= (A >> 1);
685  A |= (A >> 2);
686  A |= (A >> 4);
687  A |= (A >> 8);
688  A |= (A >> 16);
689  A |= (A >> 32);
690  return A + 1;
691}
692 
693/// Returns the power of two which is less than or equal to the given value.
694/// Essentially, it is a floor operation across the domain of powers of two.
695inline uint64_t PowerOf2Floor(uint64_t A) {
696  if (!A) return 0;
697  return 1ull << (63 - countLeadingZeros(A, ZB_Undefined));
698}
699 
700/// Returns the power of two which is greater than or equal to the given value.
701/// Essentially, it is a ceil operation across the domain of powers of two.
702inline uint64_t PowerOf2Ceil(uint64_t A) {
703  if (!A)
704    return 0;
705  return NextPowerOf2(A - 1);
706}
707 
708/// Returns the next integer (mod 2**64) that is greater than or equal to
709/// \p Value and is a multiple of \p Align. \p Align must be non-zero.
710///
711/// If non-zero \p Skew is specified, the return value will be a minimal
712/// integer that is greater than or equal to \p Value and equal to
713/// \p Align * N + \p Skew for some integer N. If \p Skew is larger than
714/// \p Align, its value is adjusted to '\p Skew mod \p Align'.
715///
716/// Examples:
717/// \code
718///   alignTo(5, 8) = 8
719///   alignTo(17, 8) = 24
720///   alignTo(~0LL, 8) = 0
721///   alignTo(321, 255) = 510
722///
723///   alignTo(5, 8, 7) = 7
724///   alignTo(17, 8, 1) = 17
725///   alignTo(~0LL, 8, 3) = 3
726///   alignTo(321, 255, 42) = 552
727/// \endcode
728inline uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
729  assert(Align != 0u && "Align can't be 0.")((void)0);
730  Skew %= Align;
22
←
Division by zero
731  return (Value + Align - 1 - Skew) / Align * Align + Skew;
732}
733 
734/// Returns the next integer (mod 2**64) that is greater than or equal to
735/// \p Value and is a multiple of \c Align. \c Align must be non-zero.
736template <uint64_t Align> constexpr inline uint64_t alignTo(uint64_t Value) {
737  static_assert(Align != 0u, "Align must be non-zero");
738  return (Value + Align - 1) / Align * Align;
739}
740 
741/// Returns the integer ceil(Numerator / Denominator).
742inline uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator) {
743  return alignTo(Numerator, Denominator) / Denominator;
744}
745 
746/// Returns the integer nearest(Numerator / Denominator).
747inline uint64_t divideNearest(uint64_t Numerator, uint64_t Denominator) {
748  return (Numerator + (Denominator / 2)) / Denominator;
749}
750 
751/// Returns the largest uint64_t less than or equal to \p Value and is
752/// \p Skew mod \p Align. \p Align must be non-zero
753inline uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
754  assert(Align != 0u && "Align can't be 0.")((void)0);
755  Skew %= Align;
756  return (Value - Skew) / Align * Align + Skew;
757}
758 
759/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
760/// Requires 0 < B <= 32.
761template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
762  static_assert(B > 0, "Bit width can't be 0.");
763  static_assert(B <= 32, "Bit width out of range.");
764  return int32_t(X << (32 - B)) >> (32 - B);
765}
766 
767/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
768/// Requires 0 < B <= 32.
769inline int32_t SignExtend32(uint32_t X, unsigned B) {
770  assert(B > 0 && "Bit width can't be 0.")((void)0);
771  assert(B <= 32 && "Bit width out of range.")((void)0);
772  return int32_t(X << (32 - B)) >> (32 - B);
773}
774 
775/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
776/// Requires 0 < B <= 64.
777template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
778  static_assert(B > 0, "Bit width can't be 0.");
779  static_assert(B <= 64, "Bit width out of range.");
780  return int64_t(x << (64 - B)) >> (64 - B);
781}
782 
783/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
784/// Requires 0 < B <= 64.
785inline int64_t SignExtend64(uint64_t X, unsigned B) {
786  assert(B > 0 && "Bit width can't be 0.")((void)0);
787  assert(B <= 64 && "Bit width out of range.")((void)0);
788  return int64_t(X << (64 - B)) >> (64 - B);
789}
790 
791/// Subtract two unsigned integers, X and Y, of type T and return the absolute
792/// value of the result.
793template <typename T>
794std::enable_if_t<std::is_unsigned<T>::value, T> AbsoluteDifference(T X, T Y) {
795  return X > Y ? (X - Y) : (Y - X);
796}
797 
798/// Add two unsigned integers, X and Y, of type T.  Clamp the result to the
799/// maximum representable value of T on overflow.  ResultOverflowed indicates if
800/// the result is larger than the maximum representable value of type T.
801template <typename T>
802std::enable_if_t<std::is_unsigned<T>::value, T>
803SaturatingAdd(T X, T Y, bool *ResultOverflowed = nullptr) {
804  bool Dummy;
805  bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
806  // Hacker's Delight, p. 29
807  T Z = X + Y;
808  Overflowed = (Z < X || Z < Y);
809  if (Overflowed)
810    return std::numeric_limits<T>::max();
811  else
812    return Z;
813}
814 
815/// Multiply two unsigned integers, X and Y, of type T.  Clamp the result to the
816/// maximum representable value of T on overflow.  ResultOverflowed indicates if
817/// the result is larger than the maximum representable value of type T.
818template <typename T>
819std::enable_if_t<std::is_unsigned<T>::value, T>
820SaturatingMultiply(T X, T Y, bool *ResultOverflowed = nullptr) {
821  bool Dummy;
822  bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
823 
824  // Hacker's Delight, p. 30 has a different algorithm, but we don't use that
825  // because it fails for uint16_t (where multiplication can have undefined
826  // behavior due to promotion to int), and requires a division in addition
827  // to the multiplication.
828 
829  Overflowed = false;
830 
831  // Log2(Z) would be either Log2Z or Log2Z + 1.
832  // Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z
833  // will necessarily be less than Log2Max as desired.
834  int Log2Z = Log2_64(X) + Log2_64(Y);
835  const T Max = std::numeric_limits<T>::max();
836  int Log2Max = Log2_64(Max);
837  if (Log2Z < Log2Max) {
838    return X * Y;
839  }
840  if (Log2Z > Log2Max) {
841    Overflowed = true;
842    return Max;
843  }
844 
845  // We're going to use the top bit, and maybe overflow one
846  // bit past it. Multiply all but the bottom bit then add
847  // that on at the end.
848  T Z = (X >> 1) * Y;
849  if (Z & ~(Max >> 1)) {
850    Overflowed = true;
851    return Max;
852  }
853  Z <<= 1;
854  if (X & 1)
855    return SaturatingAdd(Z, Y, ResultOverflowed);
856 
857  return Z;
858}
859 
860/// Multiply two unsigned integers, X and Y, and add the unsigned integer, A to
861/// the product. Clamp the result to the maximum representable value of T on
862/// overflow. ResultOverflowed indicates if the result is larger than the
863/// maximum representable value of type T.
864template <typename T>
865std::enable_if_t<std::is_unsigned<T>::value, T>
866SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed = nullptr) {
867  bool Dummy;
868  bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
869 
870  T Product = SaturatingMultiply(X, Y, &Overflowed);
871  if (Overflowed)
872    return Product;
873 
874  return SaturatingAdd(A, Product, &Overflowed);
875}
876 
877/// Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
878extern const float huge_valf;
879 
880 
881/// Add two signed integers, computing the two's complement truncated result,
882/// returning true if overflow occured.
883template <typename T>
884std::enable_if_t<std::is_signed<T>::value, T> AddOverflow(T X, T Y, T &Result) {
885#if __has_builtin(__builtin_add_overflow)1
886  return __builtin_add_overflow(X, Y, &Result);
887#else
888  // Perform the unsigned addition.
889  using U = std::make_unsigned_t<T>;
890  const U UX = static_cast<U>(X);
891  const U UY = static_cast<U>(Y);
892  const U UResult = UX + UY;
893 
894  // Convert to signed.
895  Result = static_cast<T>(UResult);
896 
897  // Adding two positive numbers should result in a positive number.
898  if (X > 0 && Y > 0)
899    return Result <= 0;
900  // Adding two negatives should result in a negative number.
901  if (X < 0 && Y < 0)
902    return Result >= 0;
903  return false;
904#endif
905}
906 
907/// Subtract two signed integers, computing the two's complement truncated
908/// result, returning true if an overflow ocurred.
909template <typename T>
910std::enable_if_t<std::is_signed<T>::value, T> SubOverflow(T X, T Y, T &Result) {
911#if __has_builtin(__builtin_sub_overflow)1
912  return __builtin_sub_overflow(X, Y, &Result);
913#else
914  // Perform the unsigned addition.
915  using U = std::make_unsigned_t<T>;
916  const U UX = static_cast<U>(X);
917  const U UY = static_cast<U>(Y);
918  const U UResult = UX - UY;
919 
920  // Convert to signed.
921  Result = static_cast<T>(UResult);
922 
923  // Subtracting a positive number from a negative results in a negative number.
924  if (X <= 0 && Y > 0)
925    return Result >= 0;
926  // Subtracting a negative number from a positive results in a positive number.
927  if (X >= 0 && Y < 0)
928    return Result <= 0;
929  return false;
930#endif
931}
932 
933/// Multiply two signed integers, computing the two's complement truncated
934/// result, returning true if an overflow ocurred.
935template <typename T>
936std::enable_if_t<std::is_signed<T>::value, T> MulOverflow(T X, T Y, T &Result) {
937  // Perform the unsigned multiplication on absolute values.
938  using U = std::make_unsigned_t<T>;
939  const U UX = X < 0 ? (0 - static_cast<U>(X)) : static_cast<U>(X);
940  const U UY = Y < 0 ? (0 - static_cast<U>(Y)) : static_cast<U>(Y);
941  const U UResult = UX * UY;
942 
943  // Convert to signed.
944  const bool IsNegative = (X < 0) ^ (Y < 0);
945  Result = IsNegative ? (0 - UResult) : UResult;
946 
947  // If any of the args was 0, result is 0 and no overflow occurs.
948  if (UX == 0 || UY == 0)
949    return false;
950 
951  // UX and UY are in [1, 2^n], where n is the number of digits.
952  // Check how the max allowed absolute value (2^n for negative, 2^(n-1) for
953  // positive) divided by an argument compares to the other.
954  if (IsNegative)
955    return UX > (static_cast<U>(std::numeric_limits<T>::max()) + U(1)) / UY;
956  else
957    return UX > (static_cast<U>(std::numeric_limits<T>::max())) / UY;
958}
959 
960} // End llvm namespace
961 
962#endif