/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp

Bug Summary

File:	llvm/lib/Transforms/IPO/GlobalOpt.cpp
Warning:	line 2239, column 22 Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

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

/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp

→

1//===- GlobalOpt.cpp - Optimize Global Variables --------------------------===//
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 pass transforms simple global variables that never have their address
10// taken.  If obviously true, it marks read/write globals as constant, deletes
11// variables only stored to, etc.
12//
13//===----------------------------------------------------------------------===//

15#include "llvm/Transforms/IPO/GlobalOpt.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/ADT/SmallPtrSet.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/ADT/Statistic.h"
21#include "llvm/ADT/Twine.h"
22#include "llvm/ADT/iterator_range.h"
23#include "llvm/Analysis/BlockFrequencyInfo.h"
24#include "llvm/Analysis/ConstantFolding.h"
25#include "llvm/Analysis/MemoryBuiltins.h"
26#include "llvm/Analysis/TargetLibraryInfo.h"
27#include "llvm/Analysis/TargetTransformInfo.h"
28#include "llvm/BinaryFormat/Dwarf.h"
29#include "llvm/IR/Attributes.h"
30#include "llvm/IR/BasicBlock.h"
31#include "llvm/IR/CallingConv.h"
32#include "llvm/IR/Constant.h"
33#include "llvm/IR/Constants.h"
34#include "llvm/IR/DataLayout.h"
35#include "llvm/IR/DebugInfoMetadata.h"
36#include "llvm/IR/DerivedTypes.h"
37#include "llvm/IR/Dominators.h"
38#include "llvm/IR/Function.h"
39#include "llvm/IR/GetElementPtrTypeIterator.h"
40#include "llvm/IR/GlobalAlias.h"
41#include "llvm/IR/GlobalValue.h"
42#include "llvm/IR/GlobalVariable.h"
43#include "llvm/IR/IRBuilder.h"
44#include "llvm/IR/InstrTypes.h"
45#include "llvm/IR/Instruction.h"
46#include "llvm/IR/Instructions.h"
47#include "llvm/IR/IntrinsicInst.h"
48#include "llvm/IR/Module.h"
49#include "llvm/IR/Operator.h"
50#include "llvm/IR/Type.h"
51#include "llvm/IR/Use.h"
52#include "llvm/IR/User.h"
53#include "llvm/IR/Value.h"
54#include "llvm/IR/ValueHandle.h"
55#include "llvm/InitializePasses.h"
56#include "llvm/Pass.h"
57#include "llvm/Support/AtomicOrdering.h"
58#include "llvm/Support/Casting.h"
59#include "llvm/Support/CommandLine.h"
60#include "llvm/Support/Debug.h"
61#include "llvm/Support/ErrorHandling.h"
62#include "llvm/Support/MathExtras.h"
63#include "llvm/Support/raw_ostream.h"
64#include "llvm/Transforms/IPO.h"
65#include "llvm/Transforms/Utils/CtorUtils.h"
66#include "llvm/Transforms/Utils/Evaluator.h"
67#include "llvm/Transforms/Utils/GlobalStatus.h"
68#include "llvm/Transforms/Utils/Local.h"
69#include <cassert>
70#include <cstdint>
71#include <utility>
72#include <vector>

74using namespace llvm;

76#define DEBUG_TYPE"globalopt" "globalopt"

78STATISTIC(NumMarked    , "Number of globals marked constant")static llvm::Statistic NumMarked = {"globalopt", "NumMarked",
 "Number of globals marked constant"};
79STATISTIC(NumUnnamed   , "Number of globals marked unnamed_addr")static llvm::Statistic NumUnnamed = {"globalopt", "NumUnnamed"
, "Number of globals marked unnamed_addr"};
80STATISTIC(NumSRA       , "Number of aggregate globals broken into scalars")static llvm::Statistic NumSRA = {"globalopt", "NumSRA", "Number of aggregate globals broken into scalars"
};
81STATISTIC(NumSubstitute,"Number of globals with initializers stored into them")static llvm::Statistic NumSubstitute = {"globalopt", "NumSubstitute"
, "Number of globals with initializers stored into them"};
82STATISTIC(NumDeleted   , "Number of globals deleted")static llvm::Statistic NumDeleted = {"globalopt", "NumDeleted"
, "Number of globals deleted"};
83STATISTIC(NumGlobUses  , "Number of global uses devirtualized")static llvm::Statistic NumGlobUses = {"globalopt", "NumGlobUses"
, "Number of global uses devirtualized"};
84STATISTIC(NumLocalized , "Number of globals localized")static llvm::Statistic NumLocalized = {"globalopt", "NumLocalized"
, "Number of globals localized"};
85STATISTIC(NumShrunkToBool  , "Number of global vars shrunk to booleans")static llvm::Statistic NumShrunkToBool = {"globalopt", "NumShrunkToBool"
, "Number of global vars shrunk to booleans"};
86STATISTIC(NumFastCallFns   , "Number of functions converted to fastcc")static llvm::Statistic NumFastCallFns = {"globalopt", "NumFastCallFns"
, "Number of functions converted to fastcc"};
87STATISTIC(NumCtorsEvaluated, "Number of static ctors evaluated")static llvm::Statistic NumCtorsEvaluated = {"globalopt", "NumCtorsEvaluated"
, "Number of static ctors evaluated"};
88STATISTIC(NumNestRemoved   , "Number of nest attributes removed")static llvm::Statistic NumNestRemoved = {"globalopt", "NumNestRemoved"
, "Number of nest attributes removed"};
89STATISTIC(NumAliasesResolved, "Number of global aliases resolved")static llvm::Statistic NumAliasesResolved = {"globalopt", "NumAliasesResolved"
, "Number of global aliases resolved"};
90STATISTIC(NumAliasesRemoved, "Number of global aliases eliminated")static llvm::Statistic NumAliasesRemoved = {"globalopt", "NumAliasesRemoved"
, "Number of global aliases eliminated"};
91STATISTIC(NumCXXDtorsRemoved, "Number of global C++ destructors removed")static llvm::Statistic NumCXXDtorsRemoved = {"globalopt", "NumCXXDtorsRemoved"
, "Number of global C++ destructors removed"};
92STATISTIC(NumInternalFunc, "Number of internal functions")static llvm::Statistic NumInternalFunc = {"globalopt", "NumInternalFunc"
, "Number of internal functions"};
93STATISTIC(NumColdCC, "Number of functions marked coldcc")static llvm::Statistic NumColdCC = {"globalopt", "NumColdCC",
 "Number of functions marked coldcc"};

95static cl::opt<bool>
  EnableColdCCStressTest("enable-coldcc-stress-test",
                         cl::desc("Enable stress test of coldcc by adding "
                                  "calling conv to all internal functions."),
                         cl::init(false), cl::Hidden);

101static cl::opt<int> ColdCCRelFreq(
  "coldcc-rel-freq", cl::Hidden, cl::init(2), cl::ZeroOrMore,
  cl::desc(
      "Maximum block frequency, expressed as a percentage of caller's "
      "entry frequency, for a call site to be considered cold for enabling"
      "coldcc"));

108/// Is this global variable possibly used by a leak checker as a root?  If so,
109/// we might not really want to eliminate the stores to it.
110static bool isLeakCheckerRoot(GlobalVariable *GV) {
// A global variable is a root if it is a pointer, or could plausibly contain
// a pointer.  There are two challenges; one is that we could have a struct
// the has an inner member which is a pointer.  We recurse through the type to
// detect these (up to a point).  The other is that we may actually be a union
// of a pointer and another type, and so our LLVM type is an integer which
// gets converted into a pointer, or our type is an [i8 x #] with a pointer
// potentially contained here.

if (GV->hasPrivateLinkage())
  return false;

SmallVector<Type *, 4> Types;
Types.push_back(GV->getValueType());

unsigned Limit = 20;
do {
  Type *Ty = Types.pop_back_val();
  switch (Ty->getTypeID()) {
    default: break;
    case Type::PointerTyID:
      return true;
    case Type::FixedVectorTyID:
    case Type::ScalableVectorTyID:
      if (cast<VectorType>(Ty)->getElementType()->isPointerTy())
        return true;
      break;
    case Type::ArrayTyID:
      Types.push_back(cast<ArrayType>(Ty)->getElementType());
      break;
    case Type::StructTyID: {
      StructType *STy = cast<StructType>(Ty);
      if (STy->isOpaque()) return true;
      for (StructType::element_iterator I = STy->element_begin(),
               E = STy->element_end(); I != E; ++I) {
        Type *InnerTy = *I;
        if (isa<PointerType>(InnerTy)) return true;
        if (isa<StructType>(InnerTy) || isa<ArrayType>(InnerTy) ||
            isa<VectorType>(InnerTy))
          Types.push_back(InnerTy);
      }
      break;
    }
  }
  if (--Limit == 0) return true;
} while (!Types.empty());
return false;
157}

159/// Given a value that is stored to a global but never read, determine whether
160/// it's safe to remove the store and the chain of computation that feeds the
161/// store.
162static bool IsSafeComputationToRemove(
  Value *V, function_ref<TargetLibraryInfo &(Function &)> GetTLI) {
do {
  if (isa<Constant>(V))
    return true;
  if (!V->hasOneUse())
    return false;
  if (isa<LoadInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V) ||
      isa<GlobalValue>(V))
    return false;
  if (isAllocationFn(V, GetTLI))
    return true;

  Instruction *I = cast<Instruction>(V);
  if (I->mayHaveSideEffects())
    return false;
  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) {
    if (!GEP->hasAllConstantIndices())
      return false;
  } else if (I->getNumOperands() != 1) {
    return false;
  }

  V = I->getOperand(0);
} while (true);
187}

189/// This GV is a pointer root.  Loop over all users of the global and clean up
190/// any that obviously don't assign the global a value that isn't dynamically
191/// allocated.
192static bool
193CleanupPointerRootUsers(GlobalVariable *GV,
                      function_ref<TargetLibraryInfo &(Function &)> GetTLI) {
// A brief explanation of leak checkers.  The goal is to find bugs where
// pointers are forgotten, causing an accumulating growth in memory
// usage over time.  The common strategy for leak checkers is to explicitly
// allow the memory pointed to by globals at exit.  This is popular because it
// also solves another problem where the main thread of a C++ program may shut
// down before other threads that are still expecting to use those globals. To
// handle that case, we expect the program may create a singleton and never
// destroy it.

bool Changed = false;

// If Dead[n].first is the only use of a malloc result, we can delete its
// chain of computation and the store to the global in Dead[n].second.
SmallVector<std::pair<Instruction *, Instruction *>, 32> Dead;

// Constants can't be pointers to dynamically allocated memory.
for (Value::user_iterator UI = GV->user_begin(), E = GV->user_end();
     UI != E;) {
  User *U = *UI++;
  if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
    Value *V = SI->getValueOperand();
    if (isa<Constant>(V)) {
      Changed = true;
      SI->eraseFromParent();
    } else if (Instruction *I = dyn_cast<Instruction>(V)) {
      if (I->hasOneUse())
        Dead.push_back(std::make_pair(I, SI));
    }
  } else if (MemSetInst *MSI = dyn_cast<MemSetInst>(U)) {
    if (isa<Constant>(MSI->getValue())) {
      Changed = true;
      MSI->eraseFromParent();
    } else if (Instruction *I = dyn_cast<Instruction>(MSI->getValue())) {
      if (I->hasOneUse())
        Dead.push_back(std::make_pair(I, MSI));
    }
  } else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(U)) {
    GlobalVariable *MemSrc = dyn_cast<GlobalVariable>(MTI->getSource());
    if (MemSrc && MemSrc->isConstant()) {
      Changed = true;
      MTI->eraseFromParent();
    } else if (Instruction *I = dyn_cast<Instruction>(MemSrc)) {
      if (I->hasOneUse())
        Dead.push_back(std::make_pair(I, MTI));
    }
  } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
    if (CE->use_empty()) {
      CE->destroyConstant();
      Changed = true;
    }
  } else if (Constant *C = dyn_cast<Constant>(U)) {
    if (isSafeToDestroyConstant(C)) {
      C->destroyConstant();
      // This could have invalidated UI, start over from scratch.
      Dead.clear();
      CleanupPointerRootUsers(GV, GetTLI);
      return true;
    }
  }
}

for (int i = 0, e = Dead.size(); i != e; ++i) {
  if (IsSafeComputationToRemove(Dead[i].first, GetTLI)) {
    Dead[i].second->eraseFromParent();
    Instruction *I = Dead[i].first;
    do {
      if (isAllocationFn(I, GetTLI))
        break;
      Instruction *J = dyn_cast<Instruction>(I->getOperand(0));
      if (!J)
        break;
      I->eraseFromParent();
      I = J;
    } while (true);
    I->eraseFromParent();
    Changed = true;
  }
}

return Changed;
275}

277/// We just marked GV constant.  Loop over all users of the global, cleaning up
278/// the obvious ones.  This is largely just a quick scan over the use list to
279/// clean up the easy and obvious cruft.  This returns true if it made a change.
280static bool CleanupConstantGlobalUsers(
  Value *V, Constant *Init, const DataLayout &DL,
  function_ref<TargetLibraryInfo &(Function &)> GetTLI) {
bool Changed = false;
// Note that we need to use a weak value handle for the worklist items. When
// we delete a constant array, we may also be holding pointer to one of its
// elements (or an element of one of its elements if we're dealing with an
// array of arrays) in the worklist.
SmallVector<WeakTrackingVH, 8> WorkList(V->users());
while (!WorkList.empty()) {
  Value *UV = WorkList.pop_back_val();
  if (!UV)
    continue;

  User *U = cast<User>(UV);

  if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
    if (Init) {
      if (auto *Casted =
              ConstantFoldLoadThroughBitcast(Init, LI->getType(), DL)) {
        // Replace the load with the initializer.
        LI->replaceAllUsesWith(Casted);
        LI->eraseFromParent();
        Changed = true;
      }
    }
  } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
    // Store must be unreachable or storing Init into the global.
    SI->eraseFromParent();
    Changed = true;
  } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
    if (CE->getOpcode() == Instruction::GetElementPtr) {
      Constant *SubInit = nullptr;
      if (Init)
        SubInit = ConstantFoldLoadThroughGEPConstantExpr(
            Init, CE, V->getType()->getPointerElementType(), DL);
      Changed |= CleanupConstantGlobalUsers(CE, SubInit, DL, GetTLI);
    } else if ((CE->getOpcode() == Instruction::BitCast &&
                CE->getType()->isPointerTy()) ||
               CE->getOpcode() == Instruction::AddrSpaceCast) {
      // Pointer cast, delete any stores and memsets to the global.
      Changed |= CleanupConstantGlobalUsers(CE, nullptr, DL, GetTLI);
    }

    if (CE->use_empty()) {
      CE->destroyConstant();
      Changed = true;
    }
  } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) {
    // Do not transform "gepinst (gep constexpr (GV))" here, because forming
    // "gepconstexpr (gep constexpr (GV))" will cause the two gep's to fold
    // and will invalidate our notion of what Init is.
    Constant *SubInit = nullptr;
    if (!isa<ConstantExpr>(GEP->getOperand(0))) {
      ConstantExpr *CE = dyn_cast_or_null<ConstantExpr>(
          ConstantFoldInstruction(GEP, DL, &GetTLI(*GEP->getFunction())));
      if (Init && CE && CE->getOpcode() == Instruction::GetElementPtr)
        SubInit = ConstantFoldLoadThroughGEPConstantExpr(
            Init, CE, V->getType()->getPointerElementType(), DL);

      // If the initializer is an all-null value and we have an inbounds GEP,
      // we already know what the result of any load from that GEP is.
      // TODO: Handle splats.
      if (Init && isa<ConstantAggregateZero>(Init) && GEP->isInBounds())
        SubInit = Constant::getNullValue(GEP->getResultElementType());
    }
    Changed |= CleanupConstantGlobalUsers(GEP, SubInit, DL, GetTLI);

    if (GEP->use_empty()) {
      GEP->eraseFromParent();
      Changed = true;
    }
  } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(U)) { // memset/cpy/mv
    if (MI->getRawDest() == V) {
      MI->eraseFromParent();
      Changed = true;
    }

  } else if (Constant *C = dyn_cast<Constant>(U)) {
    // If we have a chain of dead constantexprs or other things dangling from
    // us, and if they are all dead, nuke them without remorse.
    if (isSafeToDestroyConstant(C)) {
      C->destroyConstant();
      CleanupConstantGlobalUsers(V, Init, DL, GetTLI);
      return true;
    }
  }
}
return Changed;
369}

371static bool isSafeSROAElementUse(Value *V);

373/// Return true if the specified GEP is a safe user of a derived
374/// expression from a global that we want to SROA.
375static bool isSafeSROAGEP(User *U) {
// Check to see if this ConstantExpr GEP is SRA'able.  In particular, we
// don't like < 3 operand CE's, and we don't like non-constant integer
// indices.  This enforces that all uses are 'gep GV, 0, C, ...' for some
// value of C.
if (U->getNumOperands() < 3 || !isa<Constant>(U->getOperand(1)) ||
    !cast<Constant>(U->getOperand(1))->isNullValue())
  return false;

gep_type_iterator GEPI = gep_type_begin(U), E = gep_type_end(U);
++GEPI; // Skip over the pointer index.

// For all other level we require that the indices are constant and inrange.
// In particular, consider: A[0][i].  We cannot know that the user isn't doing
// invalid things like allowing i to index an out-of-range subscript that
// accesses A[1]. This can also happen between different members of a struct
// in llvm IR.
for (; GEPI != E; ++GEPI) {
  if (GEPI.isStruct())
    continue;

  ConstantInt *IdxVal = dyn_cast<ConstantInt>(GEPI.getOperand());
  if (!IdxVal || (GEPI.isBoundedSequential() &&
                  IdxVal->getZExtValue() >= GEPI.getSequentialNumElements()))
    return false;
}

return llvm::all_of(U->users(),
                    [](User *UU) { return isSafeSROAElementUse(UU); });
404}

406/// Return true if the specified instruction is a safe user of a derived
407/// expression from a global that we want to SROA.
408static bool isSafeSROAElementUse(Value *V) {
// We might have a dead and dangling constant hanging off of here.
if (Constant *C = dyn_cast<Constant>(V))
  return isSafeToDestroyConstant(C);

Instruction *I = dyn_cast<Instruction>(V);
if (!I) return false;

// Loads are ok.
if (isa<LoadInst>(I)) return true;

// Stores *to* the pointer are ok.
if (StoreInst *SI = dyn_cast<StoreInst>(I))
  return SI->getOperand(0) != V;

// Otherwise, it must be a GEP. Check it and its users are safe to SRA.
return isa<GetElementPtrInst>(I) && isSafeSROAGEP(I);
425}

427/// Look at all uses of the global and decide whether it is safe for us to
428/// perform this transformation.
429static bool GlobalUsersSafeToSRA(GlobalValue *GV) {
for (User *U : GV->users()) {
  // The user of the global must be a GEP Inst or a ConstantExpr GEP.
  if (!isa<GetElementPtrInst>(U) &&
      (!isa<ConstantExpr>(U) ||
      cast<ConstantExpr>(U)->getOpcode() != Instruction::GetElementPtr))
    return false;

  // Check the gep and it's users are safe to SRA
  if (!isSafeSROAGEP(U))
    return false;
}

return true;
443}

445static bool IsSRASequential(Type *T) {
return isa<ArrayType>(T) || isa<VectorType>(T);
447}
448static uint64_t GetSRASequentialNumElements(Type *T) {
if (ArrayType *AT = dyn_cast<ArrayType>(T))
  return AT->getNumElements();
return cast<FixedVectorType>(T)->getNumElements();
452}
453static Type *GetSRASequentialElementType(Type *T) {
if (ArrayType *AT = dyn_cast<ArrayType>(T))
  return AT->getElementType();
return cast<VectorType>(T)->getElementType();
457}
458static bool CanDoGlobalSRA(GlobalVariable *GV) {
Constant *Init = GV->getInitializer();

if (isa<StructType>(Init->getType())) {
  // nothing to check
} else if (IsSRASequential(Init->getType())) {
  if (GetSRASequentialNumElements(Init->getType()) > 16 &&
      GV->hasNUsesOrMore(16))
    return false; // It's not worth it.
} else
  return false;

return GlobalUsersSafeToSRA(GV);
471}

473/// Copy over the debug info for a variable to its SRA replacements.
474static void transferSRADebugInfo(GlobalVariable *GV, GlobalVariable *NGV,
                               uint64_t FragmentOffsetInBits,
                               uint64_t FragmentSizeInBits,
                               uint64_t VarSize) {
SmallVector<DIGlobalVariableExpression *, 1> GVs;
GV->getDebugInfo(GVs);
for (auto *GVE : GVs) {
  DIVariable *Var = GVE->getVariable();
  DIExpression *Expr = GVE->getExpression();
  // If the FragmentSize is smaller than the variable,
  // emit a fragment expression.
  if (FragmentSizeInBits < VarSize) {
    if (auto E = DIExpression::createFragmentExpression(
            Expr, FragmentOffsetInBits, FragmentSizeInBits))
      Expr = *E;
    else
      return;
  }
  auto *NGVE = DIGlobalVariableExpression::get(GVE->getContext(), Var, Expr);
  NGV->addDebugInfo(NGVE);
}
495}

497/// Perform scalar replacement of aggregates on the specified global variable.
498/// This opens the door for other optimizations by exposing the behavior of the
499/// program in a more fine-grained way.  We have determined that this
500/// transformation is safe already.  We return the first global variable we
501/// insert so that the caller can reprocess it.
502static GlobalVariable *SRAGlobal(GlobalVariable *GV, const DataLayout &DL) {
// Make sure this global only has simple uses that we can SRA.
if (!CanDoGlobalSRA(GV))
  return nullptr;

assert(GV->hasLocalLinkage())(static_cast <bool> (GV->hasLocalLinkage()) ? void (
0) : __assert_fail ("GV->hasLocalLinkage()", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 507, __extension__ __PRETTY_FUNCTION__));
Constant *Init = GV->getInitializer();
Type *Ty = Init->getType();
uint64_t VarSize = DL.getTypeSizeInBits(Ty);

std::map<unsigned, GlobalVariable *> NewGlobals;

// Get the alignment of the global, either explicit or target-specific.
Align StartAlignment =
    DL.getValueOrABITypeAlignment(GV->getAlign(), GV->getType());

// Loop over all users and create replacement variables for used aggregate
// elements.
for (User *GEP : GV->users()) {
  assert(((isa<ConstantExpr>(GEP) && cast<ConstantExpr>(GEP)->getOpcode() ==(static_cast <bool> (((isa<ConstantExpr>(GEP) &&
 cast<ConstantExpr>(GEP)->getOpcode() == Instruction
::GetElementPtr) || isa<GetElementPtrInst>(GEP)) &&
 "NonGEP CE's are not SRAable!") ? void (0) : __assert_fail (
"((isa<ConstantExpr>(GEP) && cast<ConstantExpr>(GEP)->getOpcode() == Instruction::GetElementPtr) || isa<GetElementPtrInst>(GEP)) && \"NonGEP CE's are not SRAable!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 524, __extension__ __PRETTY_FUNCTION__))
                                         Instruction::GetElementPtr) ||(static_cast <bool> (((isa<ConstantExpr>(GEP) &&
 cast<ConstantExpr>(GEP)->getOpcode() == Instruction
::GetElementPtr) || isa<GetElementPtrInst>(GEP)) &&
 "NonGEP CE's are not SRAable!") ? void (0) : __assert_fail (
"((isa<ConstantExpr>(GEP) && cast<ConstantExpr>(GEP)->getOpcode() == Instruction::GetElementPtr) || isa<GetElementPtrInst>(GEP)) && \"NonGEP CE's are not SRAable!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 524, __extension__ __PRETTY_FUNCTION__))
          isa<GetElementPtrInst>(GEP)) &&(static_cast <bool> (((isa<ConstantExpr>(GEP) &&
 cast<ConstantExpr>(GEP)->getOpcode() == Instruction
::GetElementPtr) || isa<GetElementPtrInst>(GEP)) &&
 "NonGEP CE's are not SRAable!") ? void (0) : __assert_fail (
"((isa<ConstantExpr>(GEP) && cast<ConstantExpr>(GEP)->getOpcode() == Instruction::GetElementPtr) || isa<GetElementPtrInst>(GEP)) && \"NonGEP CE's are not SRAable!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 524, __extension__ __PRETTY_FUNCTION__))
         "NonGEP CE's are not SRAable!")(static_cast <bool> (((isa<ConstantExpr>(GEP) &&
 cast<ConstantExpr>(GEP)->getOpcode() == Instruction
::GetElementPtr) || isa<GetElementPtrInst>(GEP)) &&
 "NonGEP CE's are not SRAable!") ? void (0) : __assert_fail (
"((isa<ConstantExpr>(GEP) && cast<ConstantExpr>(GEP)->getOpcode() == Instruction::GetElementPtr) || isa<GetElementPtrInst>(GEP)) && \"NonGEP CE's are not SRAable!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 524, __extension__ __PRETTY_FUNCTION__));

  // Ignore the 1th operand, which has to be zero or else the program is quite
  // broken (undefined).  Get the 2nd operand, which is the structure or array
  // index.
  unsigned ElementIdx = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue();
  if (NewGlobals.count(ElementIdx) == 1)
    continue; // we`ve already created replacement variable
  assert(NewGlobals.count(ElementIdx) == 0)(static_cast <bool> (NewGlobals.count(ElementIdx) == 0)
 ? void (0) : __assert_fail ("NewGlobals.count(ElementIdx) == 0"
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 532, __extension__ __PRETTY_FUNCTION__));

  Type *ElTy = nullptr;
  if (StructType *STy = dyn_cast<StructType>(Ty))
    ElTy = STy->getElementType(ElementIdx);
  else
    ElTy = GetSRASequentialElementType(Ty);
  assert(ElTy)(static_cast <bool> (ElTy) ? void (0) : __assert_fail (
"ElTy", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 539, __extension__ __PRETTY_FUNCTION__));

  Constant *In = Init->getAggregateElement(ElementIdx);
  assert(In && "Couldn't get element of initializer?")(static_cast <bool> (In && "Couldn't get element of initializer?"
) ? void (0) : __assert_fail ("In && \"Couldn't get element of initializer?\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 542, __extension__ __PRETTY_FUNCTION__));

  GlobalVariable *NGV = new GlobalVariable(
      ElTy, false, GlobalVariable::InternalLinkage, In,
      GV->getName() + "." + Twine(ElementIdx), GV->getThreadLocalMode(),
      GV->getType()->getAddressSpace());
  NGV->setExternallyInitialized(GV->isExternallyInitialized());
  NGV->copyAttributesFrom(GV);
  NewGlobals.insert(std::make_pair(ElementIdx, NGV));

  if (StructType *STy = dyn_cast<StructType>(Ty)) {
    const StructLayout &Layout = *DL.getStructLayout(STy);

    // Calculate the known alignment of the field.  If the original aggregate
    // had 256 byte alignment for example, something might depend on that:
    // propagate info to each field.
    uint64_t FieldOffset = Layout.getElementOffset(ElementIdx);
    Align NewAlign = commonAlignment(StartAlignment, FieldOffset);
    if (NewAlign > DL.getABITypeAlign(STy->getElementType(ElementIdx)))
      NGV->setAlignment(NewAlign);

    // Copy over the debug info for the variable.
    uint64_t Size = DL.getTypeAllocSizeInBits(NGV->getValueType());
    uint64_t FragmentOffsetInBits = Layout.getElementOffsetInBits(ElementIdx);
    transferSRADebugInfo(GV, NGV, FragmentOffsetInBits, Size, VarSize);
  } else {
    uint64_t EltSize = DL.getTypeAllocSize(ElTy);
    Align EltAlign = DL.getABITypeAlign(ElTy);
    uint64_t FragmentSizeInBits = DL.getTypeAllocSizeInBits(ElTy);

    // Calculate the known alignment of the field.  If the original aggregate
    // had 256 byte alignment for example, something might depend on that:
    // propagate info to each field.
    Align NewAlign = commonAlignment(StartAlignment, EltSize * ElementIdx);
    if (NewAlign > EltAlign)
      NGV->setAlignment(NewAlign);
    transferSRADebugInfo(GV, NGV, FragmentSizeInBits * ElementIdx,
                         FragmentSizeInBits, VarSize);
  }
}

if (NewGlobals.empty())
  return nullptr;

Module::GlobalListType &Globals = GV->getParent()->getGlobalList();
for (auto NewGlobalVar : NewGlobals)
  Globals.push_back(NewGlobalVar.second);

LLVM_DEBUG(dbgs() << "PERFORMING GLOBAL SRA ON: " << *GV << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "PERFORMING GLOBAL SRA ON: "
 << *GV << "\n"; } } while (false);

Constant *NullInt =Constant::getNullValue(Type::getInt32Ty(GV->getContext()));

// Loop over all of the uses of the global, replacing the constantexpr geps,
// with smaller constantexpr geps or direct references.
while (!GV->use_empty()) {
  User *GEP = GV->user_back();
  assert(((isa<ConstantExpr>(GEP) &&(static_cast <bool> (((isa<ConstantExpr>(GEP) &&
 cast<ConstantExpr>(GEP)->getOpcode()==Instruction::
GetElementPtr)|| isa<GetElementPtrInst>(GEP)) &&
 "NonGEP CE's are not SRAable!") ? void (0) : __assert_fail (
"((isa<ConstantExpr>(GEP) && cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)|| isa<GetElementPtrInst>(GEP)) && \"NonGEP CE's are not SRAable!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 600, __extension__ __PRETTY_FUNCTION__))
           cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)||(static_cast <bool> (((isa<ConstantExpr>(GEP) &&
 cast<ConstantExpr>(GEP)->getOpcode()==Instruction::
GetElementPtr)|| isa<GetElementPtrInst>(GEP)) &&
 "NonGEP CE's are not SRAable!") ? void (0) : __assert_fail (
"((isa<ConstantExpr>(GEP) && cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)|| isa<GetElementPtrInst>(GEP)) && \"NonGEP CE's are not SRAable!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 600, __extension__ __PRETTY_FUNCTION__))
          isa<GetElementPtrInst>(GEP)) && "NonGEP CE's are not SRAable!")(static_cast <bool> (((isa<ConstantExpr>(GEP) &&
 cast<ConstantExpr>(GEP)->getOpcode()==Instruction::
GetElementPtr)|| isa<GetElementPtrInst>(GEP)) &&
 "NonGEP CE's are not SRAable!") ? void (0) : __assert_fail (
"((isa<ConstantExpr>(GEP) && cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)|| isa<GetElementPtrInst>(GEP)) && \"NonGEP CE's are not SRAable!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 600, __extension__ __PRETTY_FUNCTION__));

  // Ignore the 1th operand, which has to be zero or else the program is quite
  // broken (undefined).  Get the 2nd operand, which is the structure or array
  // index.
  unsigned ElementIdx = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue();
  assert(NewGlobals.count(ElementIdx) == 1)(static_cast <bool> (NewGlobals.count(ElementIdx) == 1)
 ? void (0) : __assert_fail ("NewGlobals.count(ElementIdx) == 1"
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 606, __extension__ __PRETTY_FUNCTION__));

  Value *NewPtr = NewGlobals[ElementIdx];
  Type *NewTy = NewGlobals[ElementIdx]->getValueType();

  // Form a shorter GEP if needed.
  if (GEP->getNumOperands() > 3) {
    if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEP)) {
      SmallVector<Constant*, 8> Idxs;
      Idxs.push_back(NullInt);
      for (unsigned i = 3, e = CE->getNumOperands(); i != e; ++i)
        Idxs.push_back(CE->getOperand(i));
      NewPtr =
          ConstantExpr::getGetElementPtr(NewTy, cast<Constant>(NewPtr), Idxs);
    } else {
      GetElementPtrInst *GEPI = cast<GetElementPtrInst>(GEP);
      SmallVector<Value*, 8> Idxs;
      Idxs.push_back(NullInt);
      for (unsigned i = 3, e = GEPI->getNumOperands(); i != e; ++i)
        Idxs.push_back(GEPI->getOperand(i));
      NewPtr = GetElementPtrInst::Create(
          NewTy, NewPtr, Idxs, GEPI->getName() + "." + Twine(ElementIdx),
          GEPI);
    }
  }
  GEP->replaceAllUsesWith(NewPtr);

  // We changed the pointer of any memory access user. Recalculate alignments.
  for (User *U : NewPtr->users()) {
    if (auto *Load = dyn_cast<LoadInst>(U)) {
      Align PrefAlign = DL.getPrefTypeAlign(Load->getType());
      Align NewAlign = getOrEnforceKnownAlignment(Load->getPointerOperand(),
                                                  PrefAlign, DL, Load);
      Load->setAlignment(NewAlign);
    }
    if (auto *Store = dyn_cast<StoreInst>(U)) {
      Align PrefAlign =
          DL.getPrefTypeAlign(Store->getValueOperand()->getType());
      Align NewAlign = getOrEnforceKnownAlignment(Store->getPointerOperand(),
                                                  PrefAlign, DL, Store);
      Store->setAlignment(NewAlign);
    }
  }

  if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(GEP))
    GEPI->eraseFromParent();
  else
    cast<ConstantExpr>(GEP)->destroyConstant();
}

// Delete the old global, now that it is dead.
Globals.erase(GV);
++NumSRA;

assert(NewGlobals.size() > 0)(static_cast <bool> (NewGlobals.size() > 0) ? void (
0) : __assert_fail ("NewGlobals.size() > 0", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 660, __extension__ __PRETTY_FUNCTION__));
return NewGlobals.begin()->second;
662}

664/// Return true if all users of the specified value will trap if the value is
665/// dynamically null.  PHIs keeps track of any phi nodes we've seen to avoid
666/// reprocessing them.
667static bool AllUsesOfValueWillTrapIfNull(const Value *V,
                                      SmallPtrSetImpl<const PHINode*> &PHIs) {
for (const User *U : V->users()) {
  if (const Instruction *I = dyn_cast<Instruction>(U)) {
    // If null pointer is considered valid, then all uses are non-trapping.
    // Non address-space 0 globals have already been pruned by the caller.
    if (NullPointerIsDefined(I->getFunction()))
      return false;
  }
  if (isa<LoadInst>(U)) {
    // Will trap.
  } else if (const StoreInst *SI = dyn_cast<StoreInst>(U)) {
    if (SI->getOperand(0) == V) {
      //cerr << "NONTRAPPING USE: " << *U;
      return false;  // Storing the value.
    }
  } else if (const CallInst *CI = dyn_cast<CallInst>(U)) {
    if (CI->getCalledOperand() != V) {
      //cerr << "NONTRAPPING USE: " << *U;
      return false;  // Not calling the ptr
    }
  } else if (const InvokeInst *II = dyn_cast<InvokeInst>(U)) {
    if (II->getCalledOperand() != V) {
      //cerr << "NONTRAPPING USE: " << *U;
      return false;  // Not calling the ptr
    }
  } else if (const BitCastInst *CI = dyn_cast<BitCastInst>(U)) {
    if (!AllUsesOfValueWillTrapIfNull(CI, PHIs)) return false;
  } else if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) {
    if (!AllUsesOfValueWillTrapIfNull(GEPI, PHIs)) return false;
  } else if (const PHINode *PN = dyn_cast<PHINode>(U)) {
    // If we've already seen this phi node, ignore it, it has already been
    // checked.
    if (PHIs.insert(PN).second && !AllUsesOfValueWillTrapIfNull(PN, PHIs))
      return false;
  } else if (isa<ICmpInst>(U) &&
             !ICmpInst::isSigned(cast<ICmpInst>(U)->getPredicate()) &&
             isa<LoadInst>(U->getOperand(0)) &&
             isa<ConstantPointerNull>(U->getOperand(1))) {
    assert(isa<GlobalValue>(cast<LoadInst>(U->getOperand(0))(static_cast <bool> (isa<GlobalValue>(cast<LoadInst
>(U->getOperand(0)) ->getPointerOperand() ->stripPointerCasts
()) && "Should be GlobalVariable") ? void (0) : __assert_fail
 ("isa<GlobalValue>(cast<LoadInst>(U->getOperand(0)) ->getPointerOperand() ->stripPointerCasts()) && \"Should be GlobalVariable\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 709, __extension__ __PRETTY_FUNCTION__))
                                ->getPointerOperand()(static_cast <bool> (isa<GlobalValue>(cast<LoadInst
>(U->getOperand(0)) ->getPointerOperand() ->stripPointerCasts
()) && "Should be GlobalVariable") ? void (0) : __assert_fail
 ("isa<GlobalValue>(cast<LoadInst>(U->getOperand(0)) ->getPointerOperand() ->stripPointerCasts()) && \"Should be GlobalVariable\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 709, __extension__ __PRETTY_FUNCTION__))
                                ->stripPointerCasts()) &&(static_cast <bool> (isa<GlobalValue>(cast<LoadInst
>(U->getOperand(0)) ->getPointerOperand() ->stripPointerCasts
()) && "Should be GlobalVariable") ? void (0) : __assert_fail
 ("isa<GlobalValue>(cast<LoadInst>(U->getOperand(0)) ->getPointerOperand() ->stripPointerCasts()) && \"Should be GlobalVariable\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 709, __extension__ __PRETTY_FUNCTION__))
           "Should be GlobalVariable")(static_cast <bool> (isa<GlobalValue>(cast<LoadInst
>(U->getOperand(0)) ->getPointerOperand() ->stripPointerCasts
()) && "Should be GlobalVariable") ? void (0) : __assert_fail
 ("isa<GlobalValue>(cast<LoadInst>(U->getOperand(0)) ->getPointerOperand() ->stripPointerCasts()) && \"Should be GlobalVariable\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 709, __extension__ __PRETTY_FUNCTION__));
    // This and only this kind of non-signed ICmpInst is to be replaced with
    // the comparing of the value of the created global init bool later in
    // optimizeGlobalAddressOfMalloc for the global variable.
  } else {
    //cerr << "NONTRAPPING USE: " << *U;
    return false;
  }
}
return true;
719}

721/// Return true if all uses of any loads from GV will trap if the loaded value
722/// is null.  Note that this also permits comparisons of the loaded value
723/// against null, as a special case.
724static bool allUsesOfLoadedValueWillTrapIfNull(const GlobalVariable *GV) {
SmallVector<const Value *, 4> Worklist;
Worklist.push_back(GV);
while (!Worklist.empty()) {
  const Value *P = Worklist.pop_back_val();
  for (auto *U : P->users()) {
    if (auto *LI = dyn_cast<LoadInst>(U)) {
      SmallPtrSet<const PHINode *, 8> PHIs;
      if (!AllUsesOfValueWillTrapIfNull(LI, PHIs))
        return false;
    } else if (auto *SI = dyn_cast<StoreInst>(U)) {
      // Ignore stores to the global.
      if (SI->getPointerOperand() != P)
        return false;
    } else if (auto *CE = dyn_cast<ConstantExpr>(U)) {
      if (CE->stripPointerCasts() != GV)
        return false;
      // Check further the ConstantExpr.
      Worklist.push_back(CE);
    } else {
      // We don't know or understand this user, bail out.
      return false;
    }
  }
}

return true;
751}

753/// Get all the loads/store uses for global variable \p GV.
754static void allUsesOfLoadAndStores(GlobalVariable *GV,
                                 SmallVector<Value *, 4> &Uses) {
SmallVector<Value *, 4> Worklist;
Worklist.push_back(GV);
while (!Worklist.empty()) {
  auto *P = Worklist.pop_back_val();
  for (auto *U : P->users()) {
    if (auto *CE = dyn_cast<ConstantExpr>(U)) {
      Worklist.push_back(CE);
      continue;
    }

    assert((isa<LoadInst>(U) || isa<StoreInst>(U)) &&(static_cast <bool> ((isa<LoadInst>(U) || isa<
StoreInst>(U)) && "Expect only load or store instructions"
) ? void (0) : __assert_fail ("(isa<LoadInst>(U) || isa<StoreInst>(U)) && \"Expect only load or store instructions\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 767, __extension__ __PRETTY_FUNCTION__))
           "Expect only load or store instructions")(static_cast <bool> ((isa<LoadInst>(U) || isa<
StoreInst>(U)) && "Expect only load or store instructions"
) ? void (0) : __assert_fail ("(isa<LoadInst>(U) || isa<StoreInst>(U)) && \"Expect only load or store instructions\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 767, __extension__ __PRETTY_FUNCTION__));
    Uses.push_back(U);
  }
}
771}

773static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV) {
bool Changed = false;
for (auto UI = V->user_begin(), E = V->user_end(); UI != E; ) {
  Instruction *I = cast<Instruction>(*UI++);
  // Uses are non-trapping if null pointer is considered valid.
  // Non address-space 0 globals are already pruned by the caller.
  if (NullPointerIsDefined(I->getFunction()))
    return false;
  if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
    LI->setOperand(0, NewV);
    Changed = true;
  } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
    if (SI->getOperand(1) == V) {
      SI->setOperand(1, NewV);
      Changed = true;
    }
  } else if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
    CallBase *CB = cast<CallBase>(I);
    if (CB->getCalledOperand() == V) {
      // Calling through the pointer!  Turn into a direct call, but be careful
      // that the pointer is not also being passed as an argument.
      CB->setCalledOperand(NewV);
      Changed = true;
      bool PassedAsArg = false;
      for (unsigned i = 0, e = CB->arg_size(); i != e; ++i)
        if (CB->getArgOperand(i) == V) {
          PassedAsArg = true;
          CB->setArgOperand(i, NewV);
        }

      if (PassedAsArg) {
        // Being passed as an argument also.  Be careful to not invalidate UI!
        UI = V->user_begin();
      }
    }
  } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
    Changed |= OptimizeAwayTrappingUsesOfValue(CI,
                              ConstantExpr::getCast(CI->getOpcode(),
                                                    NewV, CI->getType()));
    if (CI->use_empty()) {
      Changed = true;
      CI->eraseFromParent();
    }
  } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
    // Should handle GEP here.
    SmallVector<Constant*, 8> Idxs;
    Idxs.reserve(GEPI->getNumOperands()-1);
    for (User::op_iterator i = GEPI->op_begin() + 1, e = GEPI->op_end();
         i != e; ++i)
      if (Constant *C = dyn_cast<Constant>(*i))
        Idxs.push_back(C);
      else
        break;
    if (Idxs.size() == GEPI->getNumOperands()-1)
      Changed |= OptimizeAwayTrappingUsesOfValue(
          GEPI, ConstantExpr::getGetElementPtr(GEPI->getSourceElementType(),
                                               NewV, Idxs));
    if (GEPI->use_empty()) {
      Changed = true;
      GEPI->eraseFromParent();
    }
  }
}

return Changed;
838}

840/// The specified global has only one non-null value stored into it.  If there
841/// are uses of the loaded value that would trap if the loaded value is
842/// dynamically null, then we know that they cannot be reachable with a null
843/// optimize away the load.
844static bool OptimizeAwayTrappingUsesOfLoads(
  GlobalVariable *GV, Constant *LV, const DataLayout &DL,
  function_ref<TargetLibraryInfo &(Function &)> GetTLI) {
bool Changed = false;

// Keep track of whether we are able to remove all the uses of the global
// other than the store that defines it.
bool AllNonStoreUsesGone = true;

// Replace all uses of loads with uses of uses of the stored value.
for (Value::user_iterator GUI = GV->user_begin(), E = GV->user_end(); GUI != E;){
  User *GlobalUser = *GUI++;
  if (LoadInst *LI = dyn_cast<LoadInst>(GlobalUser)) {
    Changed |= OptimizeAwayTrappingUsesOfValue(LI, LV);
    // If we were able to delete all uses of the loads
    if (LI->use_empty()) {
      LI->eraseFromParent();
      Changed = true;
    } else {
      AllNonStoreUsesGone = false;
    }
  } else if (isa<StoreInst>(GlobalUser)) {
    // Ignore the store that stores "LV" to the global.
    assert(GlobalUser->getOperand(1) == GV &&(static_cast <bool> (GlobalUser->getOperand(1) == GV
 && "Must be storing *to* the global") ? void (0) : __assert_fail
 ("GlobalUser->getOperand(1) == GV && \"Must be storing *to* the global\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 868, __extension__ __PRETTY_FUNCTION__))
           "Must be storing *to* the global")(static_cast <bool> (GlobalUser->getOperand(1) == GV
 && "Must be storing *to* the global") ? void (0) : __assert_fail
 ("GlobalUser->getOperand(1) == GV && \"Must be storing *to* the global\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 868, __extension__ __PRETTY_FUNCTION__));
  } else {
    AllNonStoreUsesGone = false;

    // If we get here we could have other crazy uses that are transitively
    // loaded.
    assert((isa<PHINode>(GlobalUser) || isa<SelectInst>(GlobalUser) ||(static_cast <bool> ((isa<PHINode>(GlobalUser) ||
 isa<SelectInst>(GlobalUser) || isa<ConstantExpr>
(GlobalUser) || isa<CmpInst>(GlobalUser) || isa<BitCastInst
>(GlobalUser) || isa<GetElementPtrInst>(GlobalUser))
 && "Only expect load and stores!") ? void (0) : __assert_fail
 ("(isa<PHINode>(GlobalUser) || isa<SelectInst>(GlobalUser) || isa<ConstantExpr>(GlobalUser) || isa<CmpInst>(GlobalUser) || isa<BitCastInst>(GlobalUser) || isa<GetElementPtrInst>(GlobalUser)) && \"Only expect load and stores!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 878, __extension__ __PRETTY_FUNCTION__))
            isa<ConstantExpr>(GlobalUser) || isa<CmpInst>(GlobalUser) ||(static_cast <bool> ((isa<PHINode>(GlobalUser) ||
 isa<SelectInst>(GlobalUser) || isa<ConstantExpr>
(GlobalUser) || isa<CmpInst>(GlobalUser) || isa<BitCastInst
>(GlobalUser) || isa<GetElementPtrInst>(GlobalUser))
 && "Only expect load and stores!") ? void (0) : __assert_fail
 ("(isa<PHINode>(GlobalUser) || isa<SelectInst>(GlobalUser) || isa<ConstantExpr>(GlobalUser) || isa<CmpInst>(GlobalUser) || isa<BitCastInst>(GlobalUser) || isa<GetElementPtrInst>(GlobalUser)) && \"Only expect load and stores!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 878, __extension__ __PRETTY_FUNCTION__))
            isa<BitCastInst>(GlobalUser) ||(static_cast <bool> ((isa<PHINode>(GlobalUser) ||
 isa<SelectInst>(GlobalUser) || isa<ConstantExpr>
(GlobalUser) || isa<CmpInst>(GlobalUser) || isa<BitCastInst
>(GlobalUser) || isa<GetElementPtrInst>(GlobalUser))
 && "Only expect load and stores!") ? void (0) : __assert_fail
 ("(isa<PHINode>(GlobalUser) || isa<SelectInst>(GlobalUser) || isa<ConstantExpr>(GlobalUser) || isa<CmpInst>(GlobalUser) || isa<BitCastInst>(GlobalUser) || isa<GetElementPtrInst>(GlobalUser)) && \"Only expect load and stores!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 878, __extension__ __PRETTY_FUNCTION__))
            isa<GetElementPtrInst>(GlobalUser)) &&(static_cast <bool> ((isa<PHINode>(GlobalUser) ||
 isa<SelectInst>(GlobalUser) || isa<ConstantExpr>
(GlobalUser) || isa<CmpInst>(GlobalUser) || isa<BitCastInst
>(GlobalUser) || isa<GetElementPtrInst>(GlobalUser))
 && "Only expect load and stores!") ? void (0) : __assert_fail
 ("(isa<PHINode>(GlobalUser) || isa<SelectInst>(GlobalUser) || isa<ConstantExpr>(GlobalUser) || isa<CmpInst>(GlobalUser) || isa<BitCastInst>(GlobalUser) || isa<GetElementPtrInst>(GlobalUser)) && \"Only expect load and stores!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 878, __extension__ __PRETTY_FUNCTION__))
           "Only expect load and stores!")(static_cast <bool> ((isa<PHINode>(GlobalUser) ||
 isa<SelectInst>(GlobalUser) || isa<ConstantExpr>
(GlobalUser) || isa<CmpInst>(GlobalUser) || isa<BitCastInst
>(GlobalUser) || isa<GetElementPtrInst>(GlobalUser))
 && "Only expect load and stores!") ? void (0) : __assert_fail
 ("(isa<PHINode>(GlobalUser) || isa<SelectInst>(GlobalUser) || isa<ConstantExpr>(GlobalUser) || isa<CmpInst>(GlobalUser) || isa<BitCastInst>(GlobalUser) || isa<GetElementPtrInst>(GlobalUser)) && \"Only expect load and stores!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 878, __extension__ __PRETTY_FUNCTION__));
  }
}

if (Changed) {
  LLVM_DEBUG(dbgs() << "OPTIMIZED LOADS FROM STORED ONCE POINTER: " << *GVdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "OPTIMIZED LOADS FROM STORED ONCE POINTER: "
 << *GV << "\n"; } } while (false)
                    << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "OPTIMIZED LOADS FROM STORED ONCE POINTER: "
 << *GV << "\n"; } } while (false);
  ++NumGlobUses;
}

// If we nuked all of the loads, then none of the stores are needed either,
// nor is the global.
if (AllNonStoreUsesGone) {
  if (isLeakCheckerRoot(GV)) {
    Changed |= CleanupPointerRootUsers(GV, GetTLI);
  } else {
    Changed = true;
    CleanupConstantGlobalUsers(GV, nullptr, DL, GetTLI);
  }
  if (GV->use_empty()) {
    LLVM_DEBUG(dbgs() << "  *** GLOBAL NOW DEAD!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "  *** GLOBAL NOW DEAD!\n"; }
 } while (false);
    Changed = true;
    GV->eraseFromParent();
    ++NumDeleted;
  }
}
return Changed;
905}

907/// Walk the use list of V, constant folding all of the instructions that are
908/// foldable.
909static void ConstantPropUsersOf(Value *V, const DataLayout &DL,
                              TargetLibraryInfo *TLI) {
for (Value::user_iterator UI = V->user_begin(), E = V->user_end(); UI != E; )
  if (Instruction *I = dyn_cast<Instruction>(*UI++))
    if (Constant *NewC = ConstantFoldInstruction(I, DL, TLI)) {
      I->replaceAllUsesWith(NewC);

      // Advance UI to the next non-I use to avoid invalidating it!
      // Instructions could multiply use V.
      while (UI != E && *UI == I)
        ++UI;
      if (isInstructionTriviallyDead(I, TLI))
        I->eraseFromParent();
    }
923}

925/// This function takes the specified global variable, and transforms the
926/// program as if it always contained the result of the specified malloc.
927/// Because it is always the result of the specified malloc, there is no reason
928/// to actually DO the malloc.  Instead, turn the malloc into a global, and any
929/// loads of GV as uses of the new global.
930static GlobalVariable *
931OptimizeGlobalAddressOfMalloc(GlobalVariable *GV, CallInst *CI, Type *AllocTy,
                            ConstantInt *NElements, const DataLayout &DL,
                            TargetLibraryInfo *TLI) {
LLVM_DEBUG(errs() << "PROMOTING GLOBAL: " << *GV << "  CALL = " << *CIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { errs() << "PROMOTING GLOBAL: " <<
 *GV << "  CALL = " << *CI << '\n'; } } while
 (false)
                  << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { errs() << "PROMOTING GLOBAL: " <<
 *GV << "  CALL = " << *CI << '\n'; } } while
 (false);

Type *GlobalType;
if (NElements->getZExtValue() == 1)
  GlobalType = AllocTy;
else
  // If we have an array allocation, the global variable is of an array.
  GlobalType = ArrayType::get(AllocTy, NElements->getZExtValue());

// Create the new global variable.  The contents of the malloc'd memory is
// undefined, so initialize with an undef value.
GlobalVariable *NewGV = new GlobalVariable(
    *GV->getParent(), GlobalType, false, GlobalValue::InternalLinkage,
    UndefValue::get(GlobalType), GV->getName() + ".body", nullptr,
    GV->getThreadLocalMode());

// If there are bitcast users of the malloc (which is typical, usually we have
// a malloc + bitcast) then replace them with uses of the new global.  Update
// other users to use the global as well.
BitCastInst *TheBC = nullptr;
while (!CI->use_empty()) {
  Instruction *User = cast<Instruction>(CI->user_back());
  if (BitCastInst *BCI = dyn_cast<BitCastInst>(User)) {
    if (BCI->getType() == NewGV->getType()) {
      BCI->replaceAllUsesWith(NewGV);
      BCI->eraseFromParent();
    } else {
      BCI->setOperand(0, NewGV);
    }
  } else {
    if (!TheBC)
      TheBC = new BitCastInst(NewGV, CI->getType(), "newgv", CI);
    User->replaceUsesOfWith(CI, TheBC);
  }
}

SmallPtrSet<Constant *, 1> RepValues;
RepValues.insert(NewGV);

// If there is a comparison against null, we will insert a global bool to
// keep track of whether the global was initialized yet or not.
GlobalVariable *InitBool =
  new GlobalVariable(Type::getInt1Ty(GV->getContext()), false,
                     GlobalValue::InternalLinkage,
                     ConstantInt::getFalse(GV->getContext()),
                     GV->getName()+".init", GV->getThreadLocalMode());
bool InitBoolUsed = false;

// Loop over all instruction uses of GV, processing them in turn.
SmallVector<Value *, 4> Guses;
allUsesOfLoadAndStores(GV, Guses);
for (auto *U : Guses) {
  if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
    // The global is initialized when the store to it occurs. If the stored
    // value is null value, the global bool is set to false, otherwise true.
    new StoreInst(ConstantInt::getBool(
                      GV->getContext(),
                      !isa<ConstantPointerNull>(SI->getValueOperand())),
                  InitBool, false, Align(1), SI->getOrdering(),
                  SI->getSyncScopeID(), SI);
    SI->eraseFromParent();
    continue;
  }

  LoadInst *LI = cast<LoadInst>(U);
  while (!LI->use_empty()) {
    Use &LoadUse = *LI->use_begin();
    ICmpInst *ICI = dyn_cast<ICmpInst>(LoadUse.getUser());
    if (!ICI) {
      auto *CE = ConstantExpr::getBitCast(NewGV, LI->getType());
      RepValues.insert(CE);
      LoadUse.set(CE);
      continue;
    }

    // Replace the cmp X, 0 with a use of the bool value.
    Value *LV = new LoadInst(InitBool->getValueType(), InitBool,
                             InitBool->getName() + ".val", false, Align(1),
                             LI->getOrdering(), LI->getSyncScopeID(), LI);
    InitBoolUsed = true;
    switch (ICI->getPredicate()) {
    default: llvm_unreachable("Unknown ICmp Predicate!")::llvm::llvm_unreachable_internal("Unknown ICmp Predicate!", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1016);
    case ICmpInst::ICMP_ULT: // X < null -> always false
      LV = ConstantInt::getFalse(GV->getContext());
      break;
    case ICmpInst::ICMP_UGE: // X >= null -> always true
      LV = ConstantInt::getTrue(GV->getContext());
      break;
    case ICmpInst::ICMP_ULE:
    case ICmpInst::ICMP_EQ:
      LV = BinaryOperator::CreateNot(LV, "notinit", ICI);
      break;
    case ICmpInst::ICMP_NE:
    case ICmpInst::ICMP_UGT:
      break;  // no change.
    }
    ICI->replaceAllUsesWith(LV);
    ICI->eraseFromParent();
  }
  LI->eraseFromParent();
}

// If the initialization boolean was used, insert it, otherwise delete it.
if (!InitBoolUsed) {
  while (!InitBool->use_empty())  // Delete initializations
    cast<StoreInst>(InitBool->user_back())->eraseFromParent();
  delete InitBool;
} else
  GV->getParent()->getGlobalList().insert(GV->getIterator(), InitBool);

// Now the GV is dead, nuke it and the malloc..
GV->eraseFromParent();
CI->eraseFromParent();

// To further other optimizations, loop over all users of NewGV and try to
// constant prop them.  This will promote GEP instructions with constant
// indices into GEP constant-exprs, which will allow global-opt to hack on it.
for (auto *CE : RepValues)
  ConstantPropUsersOf(CE, DL, TLI);

return NewGV;
1056}

1058/// Scan the use-list of GV checking to make sure that there are no complex uses
1059/// of GV.  We permit simple things like dereferencing the pointer, but not
1060/// storing through the address, unless it is to the specified global.
1061static bool
1062valueIsOnlyUsedLocallyOrStoredToOneGlobal(const CallInst *CI,
                                        const GlobalVariable *GV) {
SmallPtrSet<const Value *, 4> Visited;
SmallVector<const Value *, 4> Worklist;
Worklist.push_back(CI);

while (!Worklist.empty()) {
  const Value *V = Worklist.pop_back_val();
  if (!Visited.insert(V).second)
    continue;

  for (const Use &VUse : V->uses()) {
    const User *U = VUse.getUser();
    if (isa<LoadInst>(U) || isa<CmpInst>(U))
      continue; // Fine, ignore.

    if (auto *SI = dyn_cast<StoreInst>(U)) {
      if (SI->getValueOperand() == V &&
          SI->getPointerOperand()->stripPointerCasts() != GV)
        return false; // Storing the pointer not into GV... bad.
      continue; // Otherwise, storing through it, or storing into GV... fine.
    }

    if (auto *BCI = dyn_cast<BitCastInst>(U)) {
      Worklist.push_back(BCI);
      continue;
    }

    if (auto *GEPI = dyn_cast<GetElementPtrInst>(U)) {
      Worklist.push_back(GEPI);
      continue;
    }

    return false;
  }
}

return true;
1100}

1102/// This function is called when we see a pointer global variable with a single
1103/// value stored it that is a malloc or cast of malloc.
1104static bool tryToOptimizeStoreOfMallocToGlobal(GlobalVariable *GV, CallInst *CI,
                                             Type *AllocTy,
                                             AtomicOrdering Ordering,
                                             const DataLayout &DL,
                                             TargetLibraryInfo *TLI) {
// If this is a malloc of an abstract type, don't touch it.
if (!AllocTy->isSized())
  return false;

// We can't optimize this global unless all uses of it are *known* to be
// of the malloc value, not of the null initializer value (consider a use
// that compares the global's value against zero to see if the malloc has
// been reached).  To do this, we check to see if all uses of the global
// would trap if the global were null: this proves that they must all
// happen after the malloc.
if (!allUsesOfLoadedValueWillTrapIfNull(GV))
  return false;

// We can't optimize this if the malloc itself is used in a complex way,
// for example, being stored into multiple globals.  This allows the
// malloc to be stored into the specified global, loaded, gep, icmp'd.
// These are all things we could transform to using the global for.
if (!valueIsOnlyUsedLocallyOrStoredToOneGlobal(CI, GV))
  return false;

// If we have a global that is only initialized with a fixed size malloc,
// transform the program to use global memory instead of malloc'd memory.
// This eliminates dynamic allocation, avoids an indirection accessing the
// data, and exposes the resultant global to further GlobalOpt.
// We cannot optimize the malloc if we cannot determine malloc array size.
Value *NElems = getMallocArraySize(CI, DL, TLI, true);
if (!NElems)
  return false;

if (ConstantInt *NElements = dyn_cast<ConstantInt>(NElems))
  // Restrict this transformation to only working on small allocations
  // (2048 bytes currently), as we don't want to introduce a 16M global or
  // something.
  if (NElements->getZExtValue() * DL.getTypeAllocSize(AllocTy) < 2048) {
    OptimizeGlobalAddressOfMalloc(GV, CI, AllocTy, NElements, DL, TLI);
    return true;
  }

return false;
1148}

1150// Try to optimize globals based on the knowledge that only one value (besides
1151// its initializer) is ever stored to the global.
1152static bool
1153optimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal,
                       AtomicOrdering Ordering, const DataLayout &DL,
                       function_ref<TargetLibraryInfo &(Function &)> GetTLI) {
// Ignore no-op GEPs and bitcasts.
StoredOnceVal = StoredOnceVal->stripPointerCasts();

// If we are dealing with a pointer global that is initialized to null and
// only has one (non-null) value stored into it, then we can optimize any
// users of the loaded value (often calls and loads) that would trap if the
// value was null.
if (GV->getInitializer()->getType()->isPointerTy() &&
    GV->getInitializer()->isNullValue() &&
    StoredOnceVal->getType()->isPointerTy() &&
    !NullPointerIsDefined(
        nullptr /* F */,
        GV->getInitializer()->getType()->getPointerAddressSpace())) {
  if (Constant *SOVC = dyn_cast<Constant>(StoredOnceVal)) {
    if (GV->getInitializer()->getType() != SOVC->getType())
      SOVC = ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType());

    // Optimize away any trapping uses of the loaded value.
    if (OptimizeAwayTrappingUsesOfLoads(GV, SOVC, DL, GetTLI))
      return true;
  } else if (CallInst *CI = extractMallocCall(StoredOnceVal, GetTLI)) {
    auto *TLI = &GetTLI(*CI->getFunction());
    Type *MallocType = getMallocAllocatedType(CI, TLI);
    if (MallocType && tryToOptimizeStoreOfMallocToGlobal(GV, CI, MallocType,
                                                         Ordering, DL, TLI))
      return true;
  }
}

return false;
1186}

1188/// At this point, we have learned that the only two values ever stored into GV
1189/// are its initializer and OtherVal.  See if we can shrink the global into a
1190/// boolean and select between the two values whenever it is used.  This exposes
1191/// the values to other scalar optimizations.
1192static bool TryToShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) {
Type *GVElType = GV->getValueType();

// If GVElType is already i1, it is already shrunk.  If the type of the GV is
// an FP value, pointer or vector, don't do this optimization because a select
// between them is very expensive and unlikely to lead to later
// simplification.  In these cases, we typically end up with "cond ? v1 : v2"
// where v1 and v2 both require constant pool loads, a big loss.
if (GVElType == Type::getInt1Ty(GV->getContext()) ||
    GVElType->isFloatingPointTy() ||
    GVElType->isPointerTy() || GVElType->isVectorTy())
  return false;

// Walk the use list of the global seeing if all the uses are load or store.
// If there is anything else, bail out.
for (User *U : GV->users())
  if (!isa<LoadInst>(U) && !isa<StoreInst>(U))
    return false;

LLVM_DEBUG(dbgs() << "   *** SHRINKING TO BOOL: " << *GV << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "   *** SHRINKING TO BOOL: "
 << *GV << "\n"; } } while (false);

// Create the new global, initializing it to false.
GlobalVariable *NewGV = new GlobalVariable(Type::getInt1Ty(GV->getContext()),
                                           false,
                                           GlobalValue::InternalLinkage,
                                      ConstantInt::getFalse(GV->getContext()),
                                           GV->getName()+".b",
                                           GV->getThreadLocalMode(),
                                           GV->getType()->getAddressSpace());
NewGV->copyAttributesFrom(GV);
GV->getParent()->getGlobalList().insert(GV->getIterator(), NewGV);

Constant *InitVal = GV->getInitializer();
assert(InitVal->getType() != Type::getInt1Ty(GV->getContext()) &&(static_cast <bool> (InitVal->getType() != Type::getInt1Ty
(GV->getContext()) && "No reason to shrink to bool!"
) ? void (0) : __assert_fail ("InitVal->getType() != Type::getInt1Ty(GV->getContext()) && \"No reason to shrink to bool!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1226, __extension__ __PRETTY_FUNCTION__))
       "No reason to shrink to bool!")(static_cast <bool> (InitVal->getType() != Type::getInt1Ty
(GV->getContext()) && "No reason to shrink to bool!"
) ? void (0) : __assert_fail ("InitVal->getType() != Type::getInt1Ty(GV->getContext()) && \"No reason to shrink to bool!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1226, __extension__ __PRETTY_FUNCTION__));

SmallVector<DIGlobalVariableExpression *, 1> GVs;
GV->getDebugInfo(GVs);

// If initialized to zero and storing one into the global, we can use a cast
// instead of a select to synthesize the desired value.
bool IsOneZero = false;
bool EmitOneOrZero = true;
auto *CI = dyn_cast<ConstantInt>(OtherVal);
if (CI && CI->getValue().getActiveBits() <= 64) {
  IsOneZero = InitVal->isNullValue() && CI->isOne();

  auto *CIInit = dyn_cast<ConstantInt>(GV->getInitializer());
  if (CIInit && CIInit->getValue().getActiveBits() <= 64) {
    uint64_t ValInit = CIInit->getZExtValue();
    uint64_t ValOther = CI->getZExtValue();
    uint64_t ValMinus = ValOther - ValInit;

    for(auto *GVe : GVs){
      DIGlobalVariable *DGV = GVe->getVariable();
      DIExpression *E = GVe->getExpression();
      const DataLayout &DL = GV->getParent()->getDataLayout();
      unsigned SizeInOctets =
          DL.getTypeAllocSizeInBits(NewGV->getValueType()) / 8;

      // It is expected that the address of global optimized variable is on
      // top of the stack. After optimization, value of that variable will
      // be ether 0 for initial value or 1 for other value. The following
      // expression should return constant integer value depending on the
      // value at global object address:
      // val * (ValOther - ValInit) + ValInit:
      // DW_OP_deref DW_OP_constu <ValMinus>
      // DW_OP_mul DW_OP_constu <ValInit> DW_OP_plus DW_OP_stack_value
      SmallVector<uint64_t, 12> Ops = {
          dwarf::DW_OP_deref_size, SizeInOctets,
          dwarf::DW_OP_constu, ValMinus,
          dwarf::DW_OP_mul, dwarf::DW_OP_constu, ValInit,
          dwarf::DW_OP_plus};
      bool WithStackValue = true;
      E = DIExpression::prependOpcodes(E, Ops, WithStackValue);
      DIGlobalVariableExpression *DGVE =
        DIGlobalVariableExpression::get(NewGV->getContext(), DGV, E);
      NewGV->addDebugInfo(DGVE);
   }
   EmitOneOrZero = false;
  }
}

if (EmitOneOrZero) {
   // FIXME: This will only emit address for debugger on which will
   // be written only 0 or 1.
   for(auto *GV : GVs)
     NewGV->addDebugInfo(GV);
 }

while (!GV->use_empty()) {
  Instruction *UI = cast<Instruction>(GV->user_back());
  if (StoreInst *SI = dyn_cast<StoreInst>(UI)) {
    // Change the store into a boolean store.
    bool StoringOther = SI->getOperand(0) == OtherVal;
    // Only do this if we weren't storing a loaded value.
    Value *StoreVal;
    if (StoringOther || SI->getOperand(0) == InitVal) {
      StoreVal = ConstantInt::get(Type::getInt1Ty(GV->getContext()),
                                  StoringOther);
    } else {
      // Otherwise, we are storing a previously loaded copy.  To do this,
      // change the copy from copying the original value to just copying the
      // bool.
      Instruction *StoredVal = cast<Instruction>(SI->getOperand(0));

      // If we've already replaced the input, StoredVal will be a cast or
      // select instruction.  If not, it will be a load of the original
      // global.
      if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) {
        assert(LI->getOperand(0) == GV && "Not a copy!")(static_cast <bool> (LI->getOperand(0) == GV &&
 "Not a copy!") ? void (0) : __assert_fail ("LI->getOperand(0) == GV && \"Not a copy!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1302, __extension__ __PRETTY_FUNCTION__));
        // Insert a new load, to preserve the saved value.
        StoreVal = new LoadInst(NewGV->getValueType(), NewGV,
                                LI->getName() + ".b", false, Align(1),
                                LI->getOrdering(), LI->getSyncScopeID(), LI);
      } else {
        assert((isa<CastInst>(StoredVal) || isa<SelectInst>(StoredVal)) &&(static_cast <bool> ((isa<CastInst>(StoredVal) ||
 isa<SelectInst>(StoredVal)) && "This is not a form that we understand!"
) ? void (0) : __assert_fail ("(isa<CastInst>(StoredVal) || isa<SelectInst>(StoredVal)) && \"This is not a form that we understand!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1309, __extension__ __PRETTY_FUNCTION__))
               "This is not a form that we understand!")(static_cast <bool> ((isa<CastInst>(StoredVal) ||
 isa<SelectInst>(StoredVal)) && "This is not a form that we understand!"
) ? void (0) : __assert_fail ("(isa<CastInst>(StoredVal) || isa<SelectInst>(StoredVal)) && \"This is not a form that we understand!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1309, __extension__ __PRETTY_FUNCTION__));
        StoreVal = StoredVal->getOperand(0);
        assert(isa<LoadInst>(StoreVal) && "Not a load of NewGV!")(static_cast <bool> (isa<LoadInst>(StoreVal) &&
 "Not a load of NewGV!") ? void (0) : __assert_fail ("isa<LoadInst>(StoreVal) && \"Not a load of NewGV!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1311, __extension__ __PRETTY_FUNCTION__));
      }
    }
    StoreInst *NSI =
        new StoreInst(StoreVal, NewGV, false, Align(1), SI->getOrdering(),
                      SI->getSyncScopeID(), SI);
    NSI->setDebugLoc(SI->getDebugLoc());
  } else {
    // Change the load into a load of bool then a select.
    LoadInst *LI = cast<LoadInst>(UI);
    LoadInst *NLI = new LoadInst(NewGV->getValueType(), NewGV,
                                 LI->getName() + ".b", false, Align(1),
                                 LI->getOrdering(), LI->getSyncScopeID(), LI);
    Instruction *NSI;
    if (IsOneZero)
      NSI = new ZExtInst(NLI, LI->getType(), "", LI);
    else
      NSI = SelectInst::Create(NLI, OtherVal, InitVal, "", LI);
    NSI->takeName(LI);
    // Since LI is split into two instructions, NLI and NSI both inherit the
    // same DebugLoc
    NLI->setDebugLoc(LI->getDebugLoc());
    NSI->setDebugLoc(LI->getDebugLoc());
    LI->replaceAllUsesWith(NSI);
  }
  UI->eraseFromParent();
}

// Retain the name of the old global variable. People who are debugging their
// programs may expect these variables to be named the same.
NewGV->takeName(GV);
GV->eraseFromParent();
return true;
1344}

1346static bool deleteIfDead(
  GlobalValue &GV, SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) {
GV.removeDeadConstantUsers();

if (!GV.isDiscardableIfUnused() && !GV.isDeclaration())
  return false;

if (const Comdat *C = GV.getComdat())
  if (!GV.hasLocalLinkage() && NotDiscardableComdats.count(C))
    return false;

bool Dead;
if (auto *F = dyn_cast<Function>(&GV))
  Dead = (F->isDeclaration() && F->use_empty()) || F->isDefTriviallyDead();
else
  Dead = GV.use_empty();
if (!Dead)
  return false;

LLVM_DEBUG(dbgs() << "GLOBAL DEAD: " << GV << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "GLOBAL DEAD: " << GV <<
 "\n"; } } while (false);
GV.eraseFromParent();
++NumDeleted;
return true;
1369}

1371static bool isPointerValueDeadOnEntryToFunction(
  const Function *F, GlobalValue *GV,
  function_ref<DominatorTree &(Function &)> LookupDomTree) {
// Find all uses of GV. We expect them all to be in F, and if we can't
// identify any of the uses we bail out.
//
// On each of these uses, identify if the memory that GV points to is
// used/required/live at the start of the function. If it is not, for example
// if the first thing the function does is store to the GV, the GV can
// possibly be demoted.
//
// We don't do an exhaustive search for memory operations - simply look
// through bitcasts as they're quite common and benign.
const DataLayout &DL = GV->getParent()->getDataLayout();
SmallVector<LoadInst *, 4> Loads;
SmallVector<StoreInst *, 4> Stores;
for (auto *U : GV->users()) {
  if (Operator::getOpcode(U) == Instruction::BitCast) {
    for (auto *UU : U->users()) {
      if (auto *LI = dyn_cast<LoadInst>(UU))
        Loads.push_back(LI);
      else if (auto *SI = dyn_cast<StoreInst>(UU))
        Stores.push_back(SI);
      else
        return false;
    }
    continue;
  }

  Instruction *I = dyn_cast<Instruction>(U);
  if (!I)
    return false;
  assert(I->getParent()->getParent() == F)(static_cast <bool> (I->getParent()->getParent() ==
 F) ? void (0) : __assert_fail ("I->getParent()->getParent() == F"
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1403, __extension__ __PRETTY_FUNCTION__));

  if (auto *LI = dyn_cast<LoadInst>(I))
    Loads.push_back(LI);
  else if (auto *SI = dyn_cast<StoreInst>(I))
    Stores.push_back(SI);
  else
    return false;
}

// We have identified all uses of GV into loads and stores. Now check if all
// of them are known not to depend on the value of the global at the function
// entry point. We do this by ensuring that every load is dominated by at
// least one store.
auto &DT = LookupDomTree(*const_cast<Function *>(F));

// The below check is quadratic. Check we're not going to do too many tests.
// FIXME: Even though this will always have worst-case quadratic time, we
// could put effort into minimizing the average time by putting stores that
// have been shown to dominate at least one load at the beginning of the
// Stores array, making subsequent dominance checks more likely to succeed
// early.
//
// The threshold here is fairly large because global->local demotion is a
// very powerful optimization should it fire.
const unsigned Threshold = 100;
if (Loads.size() * Stores.size() > Threshold)
  return false;

for (auto *L : Loads) {
  auto *LTy = L->getType();
  if (none_of(Stores, [&](const StoreInst *S) {
        auto *STy = S->getValueOperand()->getType();
        // The load is only dominated by the store if DomTree says so
        // and the number of bits loaded in L is less than or equal to
        // the number of bits stored in S.
        return DT.dominates(S, L) &&
               DL.getTypeStoreSize(LTy).getFixedSize() <=
                   DL.getTypeStoreSize(STy).getFixedSize();
      }))
    return false;
}
// All loads have known dependences inside F, so the global can be localized.
return true;
1447}

1449/// C may have non-instruction users. Can all of those users be turned into
1450/// instructions?
1451static bool allNonInstructionUsersCanBeMadeInstructions(Constant *C) {
// We don't do this exhaustively. The most common pattern that we really need
// to care about is a constant GEP or constant bitcast - so just looking
// through one single ConstantExpr.
//
// The set of constants that this function returns true for must be able to be
// handled by makeAllConstantUsesInstructions.
for (auto *U : C->users()) {
  if (isa<Instruction>(U))
    continue;
  if (!isa<ConstantExpr>(U))
    // Non instruction, non-constantexpr user; cannot convert this.
    return false;
  for (auto *UU : U->users())
    if (!isa<Instruction>(UU))
      // A constantexpr used by another constant. We don't try and recurse any
      // further but just bail out at this point.
      return false;
}

return true;
1472}

1474/// C may have non-instruction users, and
1475/// allNonInstructionUsersCanBeMadeInstructions has returned true. Convert the
1476/// non-instruction users to instructions.
1477static void makeAllConstantUsesInstructions(Constant *C) {
SmallVector<ConstantExpr*,4> Users;
for (auto *U : C->users()) {
  if (isa<ConstantExpr>(U))
    Users.push_back(cast<ConstantExpr>(U));
  else
    // We should never get here; allNonInstructionUsersCanBeMadeInstructions
    // should not have returned true for C.
    assert((static_cast <bool> (isa<Instruction>(U) &&
 "Can't transform non-constantexpr non-instruction to instruction!"
) ? void (0) : __assert_fail ("isa<Instruction>(U) && \"Can't transform non-constantexpr non-instruction to instruction!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1487, __extension__ __PRETTY_FUNCTION__))
        isa<Instruction>(U) &&(static_cast <bool> (isa<Instruction>(U) &&
 "Can't transform non-constantexpr non-instruction to instruction!"
) ? void (0) : __assert_fail ("isa<Instruction>(U) && \"Can't transform non-constantexpr non-instruction to instruction!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1487, __extension__ __PRETTY_FUNCTION__))
        "Can't transform non-constantexpr non-instruction to instruction!")(static_cast <bool> (isa<Instruction>(U) &&
 "Can't transform non-constantexpr non-instruction to instruction!"
) ? void (0) : __assert_fail ("isa<Instruction>(U) && \"Can't transform non-constantexpr non-instruction to instruction!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1487, __extension__ __PRETTY_FUNCTION__));
}

SmallVector<Value*,4> UUsers;
for (auto *U : Users) {
  UUsers.clear();
  append_range(UUsers, U->users());
  for (auto *UU : UUsers) {
    Instruction *UI = cast<Instruction>(UU);
    Instruction *NewU = U->getAsInstruction();
    NewU->insertBefore(UI);
    UI->replaceUsesOfWith(U, NewU);
  }
  // We've replaced all the uses, so destroy the constant. (destroyConstant
  // will update value handles and metadata.)
  U->destroyConstant();
}
1504}

1506/// Analyze the specified global variable and optimize
1507/// it if possible.  If we make a change, return true.
1508static bool
1509processInternalGlobal(GlobalVariable *GV, const GlobalStatus &GS,
                    function_ref<TargetLibraryInfo &(Function &)> GetTLI,
                    function_ref<DominatorTree &(Function &)> LookupDomTree) {
auto &DL = GV->getParent()->getDataLayout();
// If this is a first class global and has only one accessing function and
// this function is non-recursive, we replace the global with a local alloca
// in this function.
//
// NOTE: It doesn't make sense to promote non-single-value types since we
// are just replacing static memory to stack memory.
//
// If the global is in different address space, don't bring it to stack.
if (!GS.HasMultipleAccessingFunctions &&
    GS.AccessingFunction &&
    GV->getValueType()->isSingleValueType() &&
    GV->getType()->getAddressSpace() == 0 &&
    !GV->isExternallyInitialized() &&
    allNonInstructionUsersCanBeMadeInstructions(GV) &&
    GS.AccessingFunction->doesNotRecurse() &&
    isPointerValueDeadOnEntryToFunction(GS.AccessingFunction, GV,
                                        LookupDomTree)) {
  const DataLayout &DL = GV->getParent()->getDataLayout();

  LLVM_DEBUG(dbgs() << "LOCALIZING GLOBAL: " << *GV << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "LOCALIZING GLOBAL: " <<
 *GV << "\n"; } } while (false);
  Instruction &FirstI = const_cast<Instruction&>(*GS.AccessingFunction
                                                 ->getEntryBlock().begin());
  Type *ElemTy = GV->getValueType();
  // FIXME: Pass Global's alignment when globals have alignment
  AllocaInst *Alloca = new AllocaInst(ElemTy, DL.getAllocaAddrSpace(), nullptr,
                                      GV->getName(), &FirstI);
  if (!isa<UndefValue>(GV->getInitializer()))
    new StoreInst(GV->getInitializer(), Alloca, &FirstI);

  makeAllConstantUsesInstructions(GV);

  GV->replaceAllUsesWith(Alloca);
  GV->eraseFromParent();
  ++NumLocalized;
  return true;
}

bool Changed = false;

// If the global is never loaded (but may be stored to), it is dead.
// Delete it now.
if (!GS.IsLoaded) {
  LLVM_DEBUG(dbgs() << "GLOBAL NEVER LOADED: " << *GV << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "GLOBAL NEVER LOADED: " <<
 *GV << "\n"; } } while (false);

  if (isLeakCheckerRoot(GV)) {
    // Delete any constant stores to the global.
    Changed = CleanupPointerRootUsers(GV, GetTLI);
  } else {
    // Delete any stores we can find to the global.  We may not be able to
    // make it completely dead though.
    Changed =
        CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, GetTLI);
  }

  // If the global is dead now, delete it.
  if (GV->use_empty()) {
    GV->eraseFromParent();
    ++NumDeleted;
    Changed = true;
  }
  return Changed;

}
if (GS.StoredType <= GlobalStatus::InitializerStored) {
  LLVM_DEBUG(dbgs() << "MARKING CONSTANT: " << *GV << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "MARKING CONSTANT: " <<
 *GV << "\n"; } } while (false);

  // Don't actually mark a global constant if it's atomic because atomic loads
  // are implemented by a trivial cmpxchg in some edge-cases and that usually
  // requires write access to the variable even if it's not actually changed.
  if (GS.Ordering == AtomicOrdering::NotAtomic) {
    assert(!GV->isConstant() && "Expected a non-constant global")(static_cast <bool> (!GV->isConstant() && "Expected a non-constant global"
) ? void (0) : __assert_fail ("!GV->isConstant() && \"Expected a non-constant global\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1583, __extension__ __PRETTY_FUNCTION__));
    GV->setConstant(true);
    Changed = true;
  }

  // Clean up any obviously simplifiable users now.
  Changed |= CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, GetTLI);

  // If the global is dead now, just nuke it.
  if (GV->use_empty()) {
    LLVM_DEBUG(dbgs() << "   *** Marking constant allowed us to simplify "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "   *** Marking constant allowed us to simplify "
 << "all users and delete global!\n"; } } while (false)
                      << "all users and delete global!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "   *** Marking constant allowed us to simplify "
 << "all users and delete global!\n"; } } while (false);
    GV->eraseFromParent();
    ++NumDeleted;
    return true;
  }

  // Fall through to the next check; see if we can optimize further.
  ++NumMarked;
}
if (!GV->getInitializer()->getType()->isSingleValueType()) {
  const DataLayout &DL = GV->getParent()->getDataLayout();
  if (SRAGlobal(GV, DL))
    return true;
}
if (GS.StoredType == GlobalStatus::StoredOnce && GS.StoredOnceValue) {
  // Avoid speculating constant expressions that might trap (div/rem).
  auto *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue);
  if (SOVConstant && SOVConstant->canTrap())
    return Changed;

  // If the initial value for the global was an undef value, and if only
  // one other value was stored into it, we can just change the
  // initializer to be the stored value, then delete all stores to the
  // global.  This allows us to mark it constant.
  if (SOVConstant && SOVConstant->getType() == GV->getValueType() &&
      isa<UndefValue>(GV->getInitializer())) {
    // Change the initial value here.
    GV->setInitializer(SOVConstant);

    // Clean up any obviously simplifiable users now.
    CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, GetTLI);

    if (GV->use_empty()) {
      LLVM_DEBUG(dbgs() << "   *** Substituting initializer allowed us to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "   *** Substituting initializer allowed us to "
 << "simplify all users and delete global!\n"; } } while
 (false)
                        << "simplify all users and delete global!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "   *** Substituting initializer allowed us to "
 << "simplify all users and delete global!\n"; } } while
 (false);
      GV->eraseFromParent();
      ++NumDeleted;
    }
    ++NumSubstitute;
    return true;
  }

  // Try to optimize globals based on the knowledge that only one value
  // (besides its initializer) is ever stored to the global.
  if (optimizeOnceStoredGlobal(GV, GS.StoredOnceValue, GS.Ordering, DL,
                               GetTLI))
    return true;

  // Otherwise, if the global was not a boolean, we can shrink it to be a
  // boolean.
  if (SOVConstant && GS.Ordering == AtomicOrdering::NotAtomic) {
    if (TryToShrinkGlobalToBoolean(GV, SOVConstant)) {
      ++NumShrunkToBool;
      return true;
    }
  }
}

return Changed;
1653}

1655/// Analyze the specified global variable and optimize it if possible.  If we
1656/// make a change, return true.
1657static bool
1658processGlobal(GlobalValue &GV,
            function_ref<TargetLibraryInfo &(Function &)> GetTLI,
            function_ref<DominatorTree &(Function &)> LookupDomTree) {
if (GV.getName().startswith("llvm."))
  return false;

GlobalStatus GS;

if (GlobalStatus::analyzeGlobal(&GV, GS))
  return false;

bool Changed = false;
if (!GS.IsCompared && !GV.hasGlobalUnnamedAddr()) {
  auto NewUnnamedAddr = GV.hasLocalLinkage() ? GlobalValue::UnnamedAddr::Global
                                             : GlobalValue::UnnamedAddr::Local;
  if (NewUnnamedAddr != GV.getUnnamedAddr()) {
    GV.setUnnamedAddr(NewUnnamedAddr);
    NumUnnamed++;
    Changed = true;
  }
}

// Do more involved optimizations if the global is internal.
if (!GV.hasLocalLinkage())
  return Changed;

auto *GVar = dyn_cast<GlobalVariable>(&GV);
if (!GVar)
  return Changed;

if (GVar->isConstant() || !GVar->hasInitializer())
  return Changed;

return processInternalGlobal(GVar, GS, GetTLI, LookupDomTree) || Changed;
1692}

1694/// Walk all of the direct calls of the specified function, changing them to
1695/// FastCC.
1696static void ChangeCalleesToFastCall(Function *F) {
for (User *U : F->users()) {
  if (isa<BlockAddress>(U))
    continue;
  cast<CallBase>(U)->setCallingConv(CallingConv::Fast);
}
1702}

1704static AttributeList StripAttr(LLVMContext &C, AttributeList Attrs,
                             Attribute::AttrKind A) {
unsigned AttrIndex;
if (Attrs.hasAttrSomewhere(A, &AttrIndex))
  return Attrs.removeAttribute(C, AttrIndex, A);
return Attrs;
1710}

1712static void RemoveAttribute(Function *F, Attribute::AttrKind A) {
F->setAttributes(StripAttr(F->getContext(), F->getAttributes(), A));
for (User *U : F->users()) {
  if (isa<BlockAddress>(U))
    continue;
  CallBase *CB = cast<CallBase>(U);
  CB->setAttributes(StripAttr(F->getContext(), CB->getAttributes(), A));
}
1720}

1722/// Return true if this is a calling convention that we'd like to change.  The
1723/// idea here is that we don't want to mess with the convention if the user
1724/// explicitly requested something with performance implications like coldcc,
1725/// GHC, or anyregcc.
1726static bool hasChangeableCC(Function *F) {
CallingConv::ID CC = F->getCallingConv();

// FIXME: Is it worth transforming x86_stdcallcc and x86_fastcallcc?
if (CC != CallingConv::C && CC != CallingConv::X86_ThisCall)
  return false;

// FIXME: Change CC for the whole chain of musttail calls when possible.
//
// Can't change CC of the function that either has musttail calls, or is a
// musttail callee itself
for (User *U : F->users()) {
  if (isa<BlockAddress>(U))
    continue;
  CallInst* CI = dyn_cast<CallInst>(U);
  if (!CI)
    continue;

  if (CI->isMustTailCall())
    return false;
}

for (BasicBlock &BB : *F)
  if (BB.getTerminatingMustTailCall())
    return false;

return true;
1753}

1755/// Return true if the block containing the call site has a BlockFrequency of
1756/// less than ColdCCRelFreq% of the entry block.
1757static bool isColdCallSite(CallBase &CB, BlockFrequencyInfo &CallerBFI) {
const BranchProbability ColdProb(ColdCCRelFreq, 100);
auto *CallSiteBB = CB.getParent();
auto CallSiteFreq = CallerBFI.getBlockFreq(CallSiteBB);
auto CallerEntryFreq =
    CallerBFI.getBlockFreq(&(CB.getCaller()->getEntryBlock()));
return CallSiteFreq < CallerEntryFreq * ColdProb;
1764}

1766// This function checks if the input function F is cold at all call sites. It
1767// also looks each call site's containing function, returning false if the
1768// caller function contains other non cold calls. The input vector AllCallsCold
1769// contains a list of functions that only have call sites in cold blocks.
1770static bool
1771isValidCandidateForColdCC(Function &F,
                        function_ref<BlockFrequencyInfo &(Function &)> GetBFI,
                        const std::vector<Function *> &AllCallsCold) {

if (F.user_empty())
  return false;

for (User *U : F.users()) {
  if (isa<BlockAddress>(U))
    continue;

  CallBase &CB = cast<CallBase>(*U);
  Function *CallerFunc = CB.getParent()->getParent();
  BlockFrequencyInfo &CallerBFI = GetBFI(*CallerFunc);
  if (!isColdCallSite(CB, CallerBFI))
    return false;
  if (!llvm::is_contained(AllCallsCold, CallerFunc))
    return false;
}
return true;
1791}

1793static void changeCallSitesToColdCC(Function *F) {
for (User *U : F->users()) {
  if (isa<BlockAddress>(U))
    continue;
  cast<CallBase>(U)->setCallingConv(CallingConv::Cold);
}
1799}

1801// This function iterates over all the call instructions in the input Function
1802// and checks that all call sites are in cold blocks and are allowed to use the
1803// coldcc calling convention.
1804static bool
1805hasOnlyColdCalls(Function &F,
               function_ref<BlockFrequencyInfo &(Function &)> GetBFI) {
for (BasicBlock &BB : F) {
  for (Instruction &I : BB) {
    if (CallInst *CI = dyn_cast<CallInst>(&I)) {
      // Skip over isline asm instructions since they aren't function calls.
      if (CI->isInlineAsm())
        continue;
      Function *CalledFn = CI->getCalledFunction();
      if (!CalledFn)
        return false;
      if (!CalledFn->hasLocalLinkage())
        return false;
      // Skip over instrinsics since they won't remain as function calls.
      if (CalledFn->getIntrinsicID() != Intrinsic::not_intrinsic)
        continue;
      // Check if it's valid to use coldcc calling convention.
      if (!hasChangeableCC(CalledFn) || CalledFn->isVarArg() ||
          CalledFn->hasAddressTaken())
        return false;
      BlockFrequencyInfo &CallerBFI = GetBFI(F);
      if (!isColdCallSite(*CI, CallerBFI))
        return false;
    }
  }
}
return true;
1832}

1834static bool hasMustTailCallers(Function *F) {
for (User *U : F->users()) {
  CallBase *CB = dyn_cast<CallBase>(U);
  if (!CB) {
    assert(isa<BlockAddress>(U) &&(static_cast <bool> (isa<BlockAddress>(U) &&
 "Expected either CallBase or BlockAddress") ? void (0) : __assert_fail
 ("isa<BlockAddress>(U) && \"Expected either CallBase or BlockAddress\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1839, __extension__ __PRETTY_FUNCTION__))
           "Expected either CallBase or BlockAddress")(static_cast <bool> (isa<BlockAddress>(U) &&
 "Expected either CallBase or BlockAddress") ? void (0) : __assert_fail
 ("isa<BlockAddress>(U) && \"Expected either CallBase or BlockAddress\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1839, __extension__ __PRETTY_FUNCTION__));
    continue;
  }
  if (CB->isMustTailCall())
    return true;
}
return false;
1846}

1848static bool hasInvokeCallers(Function *F) {
for (User *U : F->users())
  if (isa<InvokeInst>(U))
    return true;
return false;
1853}

1855static void RemovePreallocated(Function *F) {
RemoveAttribute(F, Attribute::Preallocated);

auto *M = F->getParent();

IRBuilder<> Builder(M->getContext());

// Cannot modify users() while iterating over it, so make a copy.
SmallVector<User *, 4> PreallocatedCalls(F->users());
for (User *U : PreallocatedCalls) {
  CallBase *CB = dyn_cast<CallBase>(U);
  if (!CB)
    continue;

  assert((static_cast <bool> (!CB->isMustTailCall() &&
 "Shouldn't call RemotePreallocated() on a musttail preallocated call"
) ? void (0) : __assert_fail ("!CB->isMustTailCall() && \"Shouldn't call RemotePreallocated() on a musttail preallocated call\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1871, __extension__ __PRETTY_FUNCTION__))
      !CB->isMustTailCall() &&(static_cast <bool> (!CB->isMustTailCall() &&
 "Shouldn't call RemotePreallocated() on a musttail preallocated call"
) ? void (0) : __assert_fail ("!CB->isMustTailCall() && \"Shouldn't call RemotePreallocated() on a musttail preallocated call\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1871, __extension__ __PRETTY_FUNCTION__))
      "Shouldn't call RemotePreallocated() on a musttail preallocated call")(static_cast <bool> (!CB->isMustTailCall() &&
 "Shouldn't call RemotePreallocated() on a musttail preallocated call"
) ? void (0) : __assert_fail ("!CB->isMustTailCall() && \"Shouldn't call RemotePreallocated() on a musttail preallocated call\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1871, __extension__ __PRETTY_FUNCTION__));
  // Create copy of call without "preallocated" operand bundle.
  SmallVector<OperandBundleDef, 1> OpBundles;
  CB->getOperandBundlesAsDefs(OpBundles);
  CallBase *PreallocatedSetup = nullptr;
  for (auto *It = OpBundles.begin(); It != OpBundles.end(); ++It) {
    if (It->getTag() == "preallocated") {
      PreallocatedSetup = cast<CallBase>(*It->input_begin());
      OpBundles.erase(It);
      break;
    }
  }
  assert(PreallocatedSetup && "Did not find preallocated bundle")(static_cast <bool> (PreallocatedSetup && "Did not find preallocated bundle"
) ? void (0) : __assert_fail ("PreallocatedSetup && \"Did not find preallocated bundle\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1883, __extension__ __PRETTY_FUNCTION__));
  uint64_t ArgCount =
      cast<ConstantInt>(PreallocatedSetup->getArgOperand(0))->getZExtValue();

  assert((isa<CallInst>(CB) || isa<InvokeInst>(CB)) &&(static_cast <bool> ((isa<CallInst>(CB) || isa<
InvokeInst>(CB)) && "Unknown indirect call type") ?
 void (0) : __assert_fail ("(isa<CallInst>(CB) || isa<InvokeInst>(CB)) && \"Unknown indirect call type\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1888, __extension__ __PRETTY_FUNCTION__))
         "Unknown indirect call type")(static_cast <bool> ((isa<CallInst>(CB) || isa<
InvokeInst>(CB)) && "Unknown indirect call type") ?
 void (0) : __assert_fail ("(isa<CallInst>(CB) || isa<InvokeInst>(CB)) && \"Unknown indirect call type\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1888, __extension__ __PRETTY_FUNCTION__));
  CallBase *NewCB = CallBase::Create(CB, OpBundles, CB);
  CB->replaceAllUsesWith(NewCB);
  NewCB->takeName(CB);
  CB->eraseFromParent();

  Builder.SetInsertPoint(PreallocatedSetup);
  auto *StackSave =
      Builder.CreateCall(Intrinsic::getDeclaration(M, Intrinsic::stacksave));

  Builder.SetInsertPoint(NewCB->getNextNonDebugInstruction());
  Builder.CreateCall(Intrinsic::getDeclaration(M, Intrinsic::stackrestore),
                     StackSave);

  // Replace @llvm.call.preallocated.arg() with alloca.
  // Cannot modify users() while iterating over it, so make a copy.
  // @llvm.call.preallocated.arg() can be called with the same index multiple
  // times. So for each @llvm.call.preallocated.arg(), we see if we have
  // already created a Value* for the index, and if not, create an alloca and
  // bitcast right after the @llvm.call.preallocated.setup() so that it
  // dominates all uses.
  SmallVector<Value *, 2> ArgAllocas(ArgCount);
  SmallVector<User *, 2> PreallocatedArgs(PreallocatedSetup->users());
  for (auto *User : PreallocatedArgs) {
    auto *UseCall = cast<CallBase>(User);
    assert(UseCall->getCalledFunction()->getIntrinsicID() ==(static_cast <bool> (UseCall->getCalledFunction()->
getIntrinsicID() == Intrinsic::call_preallocated_arg &&
 "preallocated token use was not a llvm.call.preallocated.arg"
) ? void (0) : __assert_fail ("UseCall->getCalledFunction()->getIntrinsicID() == Intrinsic::call_preallocated_arg && \"preallocated token use was not a llvm.call.preallocated.arg\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1915, __extension__ __PRETTY_FUNCTION__))
               Intrinsic::call_preallocated_arg &&(static_cast <bool> (UseCall->getCalledFunction()->
getIntrinsicID() == Intrinsic::call_preallocated_arg &&
 "preallocated token use was not a llvm.call.preallocated.arg"
) ? void (0) : __assert_fail ("UseCall->getCalledFunction()->getIntrinsicID() == Intrinsic::call_preallocated_arg && \"preallocated token use was not a llvm.call.preallocated.arg\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1915, __extension__ __PRETTY_FUNCTION__))
           "preallocated token use was not a llvm.call.preallocated.arg")(static_cast <bool> (UseCall->getCalledFunction()->
getIntrinsicID() == Intrinsic::call_preallocated_arg &&
 "preallocated token use was not a llvm.call.preallocated.arg"
) ? void (0) : __assert_fail ("UseCall->getCalledFunction()->getIntrinsicID() == Intrinsic::call_preallocated_arg && \"preallocated token use was not a llvm.call.preallocated.arg\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1915, __extension__ __PRETTY_FUNCTION__));
    uint64_t AllocArgIndex =
        cast<ConstantInt>(UseCall->getArgOperand(1))->getZExtValue();
    Value *AllocaReplacement = ArgAllocas[AllocArgIndex];
    if (!AllocaReplacement) {
      auto AddressSpace = UseCall->getType()->getPointerAddressSpace();
      auto *ArgType =
          UseCall->getFnAttr(Attribute::Preallocated).getValueAsType();
      auto *InsertBefore = PreallocatedSetup->getNextNonDebugInstruction();
      Builder.SetInsertPoint(InsertBefore);
      auto *Alloca =
          Builder.CreateAlloca(ArgType, AddressSpace, nullptr, "paarg");
      auto *BitCast = Builder.CreateBitCast(
          Alloca, Type::getInt8PtrTy(M->getContext()), UseCall->getName());
      ArgAllocas[AllocArgIndex] = BitCast;
      AllocaReplacement = BitCast;
    }

    UseCall->replaceAllUsesWith(AllocaReplacement);
    UseCall->eraseFromParent();
  }
  // Remove @llvm.call.preallocated.setup().
  cast<Instruction>(PreallocatedSetup)->eraseFromParent();
}
1939}

1941static bool
1942OptimizeFunctions(Module &M,
                function_ref<TargetLibraryInfo &(Function &)> GetTLI,
                function_ref<TargetTransformInfo &(Function &)> GetTTI,
                function_ref<BlockFrequencyInfo &(Function &)> GetBFI,
                function_ref<DominatorTree &(Function &)> LookupDomTree,
                SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) {

bool Changed = false;

std::vector<Function *> AllCallsCold;
for (Module::iterator FI = M.begin(), E = M.end(); FI != E;) {
  Function *F = &*FI++;
  if (hasOnlyColdCalls(*F, GetBFI))
    AllCallsCold.push_back(F);
}

// Optimize functions.
for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) {
  Function *F = &*FI++;

  // Don't perform global opt pass on naked functions; we don't want fast
  // calling conventions for naked functions.
  if (F->hasFnAttribute(Attribute::Naked))
    continue;

  // Functions without names cannot be referenced outside this module.
  if (!F->hasName() && !F->isDeclaration() && !F->hasLocalLinkage())
    F->setLinkage(GlobalValue::InternalLinkage);

  if (deleteIfDead(*F, NotDiscardableComdats)) {
    Changed = true;
    continue;
  }

  // LLVM's definition of dominance allows instructions that are cyclic
  // in unreachable blocks, e.g.:
  // %pat = select i1 %condition, @global, i16* %pat
  // because any instruction dominates an instruction in a block that's
  // not reachable from entry.
  // So, remove unreachable blocks from the function, because a) there's
  // no point in analyzing them and b) GlobalOpt should otherwise grow
  // some more complicated logic to break these cycles.
  // Removing unreachable blocks might invalidate the dominator so we
  // recalculate it.
  if (!F->isDeclaration()) {
    if (removeUnreachableBlocks(*F)) {
      auto &DT = LookupDomTree(*F);
      DT.recalculate(*F);
      Changed = true;
    }
  }

  Changed |= processGlobal(*F, GetTLI, LookupDomTree);

  if (!F->hasLocalLinkage())
    continue;

  // If we have an inalloca parameter that we can safely remove the
  // inalloca attribute from, do so. This unlocks optimizations that
  // wouldn't be safe in the presence of inalloca.
  // FIXME: We should also hoist alloca affected by this to the entry
  // block if possible.
  if (F->getAttributes().hasAttrSomewhere(Attribute::InAlloca) &&
      !F->hasAddressTaken() && !hasMustTailCallers(F)) {
    RemoveAttribute(F, Attribute::InAlloca);
    Changed = true;
  }

  // FIXME: handle invokes
  // FIXME: handle musttail
  if (F->getAttributes().hasAttrSomewhere(Attribute::Preallocated)) {
    if (!F->hasAddressTaken() && !hasMustTailCallers(F) &&
        !hasInvokeCallers(F)) {
      RemovePreallocated(F);
      Changed = true;
    }
    continue;
  }

  if (hasChangeableCC(F) && !F->isVarArg() && !F->hasAddressTaken()) {
    NumInternalFunc++;
    TargetTransformInfo &TTI = GetTTI(*F);
    // Change the calling convention to coldcc if either stress testing is
    // enabled or the target would like to use coldcc on functions which are
    // cold at all call sites and the callers contain no other non coldcc
    // calls.
    if (EnableColdCCStressTest ||
        (TTI.useColdCCForColdCall(*F) &&
         isValidCandidateForColdCC(*F, GetBFI, AllCallsCold))) {
      F->setCallingConv(CallingConv::Cold);
      changeCallSitesToColdCC(F);
      Changed = true;
      NumColdCC++;
    }
  }

  if (hasChangeableCC(F) && !F->isVarArg() &&
      !F->hasAddressTaken()) {
    // If this function has a calling convention worth changing, is not a
    // varargs function, and is only called directly, promote it to use the
    // Fast calling convention.
    F->setCallingConv(CallingConv::Fast);
    ChangeCalleesToFastCall(F);
    ++NumFastCallFns;
    Changed = true;
  }

  if (F->getAttributes().hasAttrSomewhere(Attribute::Nest) &&
      !F->hasAddressTaken()) {
    // The function is not used by a trampoline intrinsic, so it is safe
    // to remove the 'nest' attribute.
    RemoveAttribute(F, Attribute::Nest);
    ++NumNestRemoved;
    Changed = true;
  }
}
return Changed;
2059}

2061static bool
2062OptimizeGlobalVars(Module &M,
                 function_ref<TargetLibraryInfo &(Function &)> GetTLI,
                 function_ref<DominatorTree &(Function &)> LookupDomTree,
                 SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) {
bool Changed = false;

for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
     GVI != E; ) {
  GlobalVariable *GV = &*GVI++;
  // Global variables without names cannot be referenced outside this module.
  if (!GV->hasName() && !GV->isDeclaration() && !GV->hasLocalLinkage())
    GV->setLinkage(GlobalValue::InternalLinkage);
  // Simplify the initializer.
  if (GV->hasInitializer())
    if (auto *C = dyn_cast<Constant>(GV->getInitializer())) {
      auto &DL = M.getDataLayout();
      // TLI is not used in the case of a Constant, so use default nullptr
      // for that optional parameter, since we don't have a Function to
      // provide GetTLI anyway.
      Constant *New = ConstantFoldConstant(C, DL, /*TLI*/ nullptr);
      if (New != C)
        GV->setInitializer(New);
    }

  if (deleteIfDead(*GV, NotDiscardableComdats)) {
    Changed = true;
    continue;
  }

  Changed |= processGlobal(*GV, GetTLI, LookupDomTree);
}
return Changed;
2094}

2096/// Evaluate a piece of a constantexpr store into a global initializer.  This
2097/// returns 'Init' modified to reflect 'Val' stored into it.  At this point, the
2098/// GEP operands of Addr [0, OpNo) have been stepped into.
2099static Constant *EvaluateStoreInto(Constant *Init, Constant *Val,
                                 ConstantExpr *Addr, unsigned OpNo) {
// Base case of the recursion.
if (OpNo == Addr->getNumOperands()) {
  assert(Val->getType() == Init->getType() && "Type mismatch!")(static_cast <bool> (Val->getType() == Init->getType
() && "Type mismatch!") ? void (0) : __assert_fail ("Val->getType() == Init->getType() && \"Type mismatch!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2103, __extension__ __PRETTY_FUNCTION__));
  return Val;
}

SmallVector<Constant*, 32> Elts;
if (StructType *STy = dyn_cast<StructType>(Init->getType())) {
  // Break up the constant into its elements.
  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
    Elts.push_back(Init->getAggregateElement(i));

  // Replace the element that we are supposed to.
  ConstantInt *CU = cast<ConstantInt>(Addr->getOperand(OpNo));
  unsigned Idx = CU->getZExtValue();
  assert(Idx < STy->getNumElements() && "Struct index out of range!")(static_cast <bool> (Idx < STy->getNumElements() &&
 "Struct index out of range!") ? void (0) : __assert_fail ("Idx < STy->getNumElements() && \"Struct index out of range!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2116, __extension__ __PRETTY_FUNCTION__));
  Elts[Idx] = EvaluateStoreInto(Elts[Idx], Val, Addr, OpNo+1);

  // Return the modified struct.
  return ConstantStruct::get(STy, Elts);
}

ConstantInt *CI = cast<ConstantInt>(Addr->getOperand(OpNo));
uint64_t NumElts;
if (ArrayType *ATy = dyn_cast<ArrayType>(Init->getType()))
  NumElts = ATy->getNumElements();
else
  NumElts = cast<FixedVectorType>(Init->getType())->getNumElements();

// Break up the array into elements.
for (uint64_t i = 0, e = NumElts; i != e; ++i)
  Elts.push_back(Init->getAggregateElement(i));

assert(CI->getZExtValue() < NumElts)(static_cast <bool> (CI->getZExtValue() < NumElts
) ? void (0) : __assert_fail ("CI->getZExtValue() < NumElts"
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2134, __extension__ __PRETTY_FUNCTION__));
Elts[CI->getZExtValue()] =
  EvaluateStoreInto(Elts[CI->getZExtValue()], Val, Addr, OpNo+1);

if (Init->getType()->isArrayTy())
  return ConstantArray::get(cast<ArrayType>(Init->getType()), Elts);
return ConstantVector::get(Elts);
2141}

2143/// We have decided that Addr (which satisfies the predicate
2144/// isSimpleEnoughPointerToCommit) should get Val as its value.  Make it happen.
2145static void CommitValueTo(Constant *Val, Constant *Addr) {
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
  assert(GV->hasInitializer())(static_cast <bool> (GV->hasInitializer()) ? void (0
) : __assert_fail ("GV->hasInitializer()", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2147, __extension__ __PRETTY_FUNCTION__));
  GV->setInitializer(Val);
  return;
}

ConstantExpr *CE = cast<ConstantExpr>(Addr);
GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
GV->setInitializer(EvaluateStoreInto(GV->getInitializer(), Val, CE, 2));
2155}

2157/// Given a map of address -> value, where addresses are expected to be some form
2158/// of either a global or a constant GEP, set the initializer for the address to
2159/// be the value. This performs mostly the same function as CommitValueTo()
2160/// and EvaluateStoreInto() but is optimized to be more efficient for the common
2161/// case where the set of addresses are GEPs sharing the same underlying global,
2162/// processing the GEPs in batches rather than individually.
2163///
2164/// To give an example, consider the following C++ code adapted from the clang
2165/// regression tests:
2166/// struct S {
2167///  int n = 10;
2168///  int m = 2 * n;
2169///  S(int a) : n(a) {}
2170/// };
2171///
2172/// template<typename T>
2173/// struct U {
2174///  T *r = &q;
2175///  T q = 42;
2176///  U *p = this;
2177/// };
2178///
2179/// U<S> e;
2180///
2181/// The global static constructor for 'e' will need to initialize 'r' and 'p' of
2182/// the outer struct, while also initializing the inner 'q' structs 'n' and 'm'
2183/// members. This batch algorithm will simply use general CommitValueTo() method
2184/// to handle the complex nested S struct initialization of 'q', before
2185/// processing the outermost members in a single batch. Using CommitValueTo() to
2186/// handle member in the outer struct is inefficient when the struct/array is
2187/// very large as we end up creating and destroy constant arrays for each
2188/// initialization.
2189/// For the above case, we expect the following IR to be generated:
2190///
2191/// %struct.U = type { %struct.S*, %struct.S, %struct.U* }
2192/// %struct.S = type { i32, i32 }
2193/// @e = global %struct.U { %struct.S* gep inbounds (%struct.U, %struct.U* @e,
2194///                                                  i64 0, i32 1),
2195///                         %struct.S { i32 42, i32 84 }, %struct.U* @e }
2196/// The %struct.S { i32 42, i32 84 } inner initializer is treated as a complex
2197/// constant expression, while the other two elements of @e are "simple".
2198static void BatchCommitValueTo(const DenseMap<Constant*, Constant*> &Mem) {
SmallVector<std::pair<GlobalVariable*, Constant*>, 32> GVs;
SmallVector<std::pair<ConstantExpr*, Constant*>, 32> ComplexCEs;
SmallVector<std::pair<ConstantExpr*, Constant*>, 32> SimpleCEs;
SimpleCEs.reserve(Mem.size());

for (const auto &I : Mem) {
  if (auto *GV = dyn_cast<GlobalVariable>(I.first)) {
    GVs.push_back(std::make_pair(GV, I.second));
  } else {
    ConstantExpr *GEP = cast<ConstantExpr>(I.first);
    // We don't handle the deeply recursive case using the batch method.
    if (GEP->getNumOperands() > 3)
      ComplexCEs.push_back(std::make_pair(GEP, I.second));
    else
      SimpleCEs.push_back(std::make_pair(GEP, I.second));
  }
}

// The algorithm below doesn't handle cases like nested structs, so use the
// slower fully general method if we have to.
for (auto ComplexCE : ComplexCEs)
7
←
Assuming '__begin1' is equal to '__end1'→
  CommitValueTo(ComplexCE.second, ComplexCE.first);

for (auto GVPair : GVs) {
8
←
Assuming '__begin1' is equal to '__end1'→
  assert(GVPair.first->hasInitializer())(static_cast <bool> (GVPair.first->hasInitializer())
 ? void (0) : __assert_fail ("GVPair.first->hasInitializer()"
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2223, __extension__ __PRETTY_FUNCTION__));
  GVPair.first->setInitializer(GVPair.second);
}

if (SimpleCEs.empty())
9
←
Calling 'SmallVectorBase::empty'→
12
←
Returning from 'SmallVectorBase::empty'→
13
←
Taking false branch→
  return;

// We cache a single global's initializer elements in the case where the
// subsequent address/val pair uses the same one. This avoids throwing away and
// rebuilding the constant struct/vector/array just because one element is
// modified at a time.
SmallVector<Constant *, 32> Elts;
Elts.reserve(SimpleCEs.size());
GlobalVariable *CurrentGV = nullptr;
14
←
'CurrentGV' initialized to a null pointer value→

auto commitAndSetupCache = [&](GlobalVariable *GV, bool Update) {
  Constant *Init = GV->getInitializer();
18
←
Called C++ object pointer is null
  Type *Ty = Init->getType();
  if (Update) {
    if (CurrentGV) {
      assert(CurrentGV && "Expected a GV to commit to!")(static_cast <bool> (CurrentGV && "Expected a GV to commit to!"
) ? void (0) : __assert_fail ("CurrentGV && \"Expected a GV to commit to!\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2243, __extension__ __PRETTY_FUNCTION__));
      Type *CurrentInitTy = CurrentGV->getInitializer()->getType();
      // We have a valid cache that needs to be committed.
      if (StructType *STy = dyn_cast<StructType>(CurrentInitTy))
        CurrentGV->setInitializer(ConstantStruct::get(STy, Elts));
      else if (ArrayType *ArrTy = dyn_cast<ArrayType>(CurrentInitTy))
        CurrentGV->setInitializer(ConstantArray::get(ArrTy, Elts));
      else
        CurrentGV->setInitializer(ConstantVector::get(Elts));
    }
    if (CurrentGV == GV)
      return;
    // Need to clear and set up cache for new initializer.
    CurrentGV = GV;
    Elts.clear();
    unsigned NumElts;
    if (auto *STy = dyn_cast<StructType>(Ty))
      NumElts = STy->getNumElements();
    else if (auto *ATy = dyn_cast<ArrayType>(Ty))
      NumElts = ATy->getNumElements();
    else
      NumElts = cast<FixedVectorType>(Ty)->getNumElements();
    for (unsigned i = 0, e = NumElts; i != e; ++i)
      Elts.push_back(Init->getAggregateElement(i));
  }
};

for (auto CEPair : SimpleCEs) {
15
←
Assuming '__begin1' is equal to '__end1'→
  ConstantExpr *GEP = CEPair.first;
  Constant *Val = CEPair.second;

  GlobalVariable *GV = cast<GlobalVariable>(GEP->getOperand(0));
  commitAndSetupCache(GV, GV != CurrentGV);
  ConstantInt *CI = cast<ConstantInt>(GEP->getOperand(2));
  Elts[CI->getZExtValue()] = Val;
}
// The last initializer in the list needs to be committed, others
// will be committed on a new initializer being processed.
commitAndSetupCache(CurrentGV, true);
16
←
Passing null pointer value via 1st parameter 'GV'→
17
←
Calling 'operator()'→
2282}

2284/// Evaluate static constructors in the function, if we can.  Return true if we
2285/// can, false otherwise.
2286static bool EvaluateStaticConstructor(Function *F, const DataLayout &DL,
                                    TargetLibraryInfo *TLI) {
// Call the function.
Evaluator Eval(DL, TLI);
Constant *RetValDummy;
bool EvalSuccess = Eval.EvaluateFunction(F, RetValDummy,
                                         SmallVector<Constant*, 0>());

if (EvalSuccess) {
2
←
Assuming 'EvalSuccess' is true→
3
←
Taking true branch→
  ++NumCtorsEvaluated;

  // We succeeded at evaluation: commit the result.
  LLVM_DEBUG(dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '"
 << F->getName() << "' to " << Eval.getMutatedMemory
().size() << " stores.\n"; } } while (false)
4
←
Assuming 'DebugFlag' is false→
5
←
Loop condition is false.  Exiting loop→
                    << F->getName() << "' to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '"
 << F->getName() << "' to " << Eval.getMutatedMemory
().size() << " stores.\n"; } } while (false)
                    << Eval.getMutatedMemory().size() << " stores.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '"
 << F->getName() << "' to " << Eval.getMutatedMemory
().size() << " stores.\n"; } } while (false);
  BatchCommitValueTo(Eval.getMutatedMemory());
6
←
Calling 'BatchCommitValueTo'→
  for (GlobalVariable *GV : Eval.getInvariants())
    GV->setConstant(true);
}

return EvalSuccess;
2307}

2309static int compareNames(Constant *const *A, Constant *const *B) {
Value *AStripped = (*A)->stripPointerCasts();
Value *BStripped = (*B)->stripPointerCasts();
return AStripped->getName().compare(BStripped->getName());
2313}

2315static void setUsedInitializer(GlobalVariable &V,
                             const SmallPtrSetImpl<GlobalValue *> &Init) {
if (Init.empty()) {
  V.eraseFromParent();
  return;
}

// Type of pointer to the array of pointers.
PointerType *Int8PtrTy = Type::getInt8PtrTy(V.getContext(), 0);

SmallVector<Constant *, 8> UsedArray;
for (GlobalValue *GV : Init) {
  Constant *Cast
    = ConstantExpr::getPointerBitCastOrAddrSpaceCast(GV, Int8PtrTy);
  UsedArray.push_back(Cast);
}
// Sort to get deterministic order.
array_pod_sort(UsedArray.begin(), UsedArray.end(), compareNames);
ArrayType *ATy = ArrayType::get(Int8PtrTy, UsedArray.size());

Module *M = V.getParent();
V.removeFromParent();
GlobalVariable *NV =
    new GlobalVariable(*M, ATy, false, GlobalValue::AppendingLinkage,
                       ConstantArray::get(ATy, UsedArray), "");
NV->takeName(&V);
NV->setSection("llvm.metadata");
delete &V;
2343}

2345namespace {

2347/// An easy to access representation of llvm.used and llvm.compiler.used.
2348class LLVMUsed {
SmallPtrSet<GlobalValue *, 4> Used;
SmallPtrSet<GlobalValue *, 4> CompilerUsed;
GlobalVariable *UsedV;
GlobalVariable *CompilerUsedV;

2354public:
LLVMUsed(Module &M) {
  SmallVector<GlobalValue *, 4> Vec;
  UsedV = collectUsedGlobalVariables(M, Vec, false);
  Used = {Vec.begin(), Vec.end()};
  Vec.clear();
  CompilerUsedV = collectUsedGlobalVariables(M, Vec, true);
  CompilerUsed = {Vec.begin(), Vec.end()};
}

using iterator = SmallPtrSet<GlobalValue *, 4>::iterator;
using used_iterator_range = iterator_range<iterator>;

iterator usedBegin() { return Used.begin(); }
iterator usedEnd() { return Used.end(); }

used_iterator_range used() {
  return used_iterator_range(usedBegin(), usedEnd());
}

iterator compilerUsedBegin() { return CompilerUsed.begin(); }
iterator compilerUsedEnd() { return CompilerUsed.end(); }

used_iterator_range compilerUsed() {
  return used_iterator_range(compilerUsedBegin(), compilerUsedEnd());
}

bool usedCount(GlobalValue *GV) const { return Used.count(GV); }

bool compilerUsedCount(GlobalValue *GV) const {
  return CompilerUsed.count(GV);
}

bool usedErase(GlobalValue *GV) { return Used.erase(GV); }
bool compilerUsedErase(GlobalValue *GV) { return CompilerUsed.erase(GV); }
bool usedInsert(GlobalValue *GV) { return Used.insert(GV).second; }

bool compilerUsedInsert(GlobalValue *GV) {
  return CompilerUsed.insert(GV).second;
}

void syncVariablesAndSets() {
  if (UsedV)
    setUsedInitializer(*UsedV, Used);
  if (CompilerUsedV)
    setUsedInitializer(*CompilerUsedV, CompilerUsed);
}
2401};

2403} // end anonymous namespace

2405static bool hasUseOtherThanLLVMUsed(GlobalAlias &GA, const LLVMUsed &U) {
if (GA.use_empty()) // No use at all.
  return false;

assert((!U.usedCount(&GA) || !U.compilerUsedCount(&GA)) &&(static_cast <bool> ((!U.usedCount(&GA) || !U.compilerUsedCount
(&GA)) && "We should have removed the duplicated "
 "element from llvm.compiler.used") ? void (0) : __assert_fail
 ("(!U.usedCount(&GA) || !U.compilerUsedCount(&GA)) && \"We should have removed the duplicated \" \"element from llvm.compiler.used\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2411, __extension__ __PRETTY_FUNCTION__))
       "We should have removed the duplicated "(static_cast <bool> ((!U.usedCount(&GA) || !U.compilerUsedCount
(&GA)) && "We should have removed the duplicated "
 "element from llvm.compiler.used") ? void (0) : __assert_fail
 ("(!U.usedCount(&GA) || !U.compilerUsedCount(&GA)) && \"We should have removed the duplicated \" \"element from llvm.compiler.used\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2411, __extension__ __PRETTY_FUNCTION__))
       "element from llvm.compiler.used")(static_cast <bool> ((!U.usedCount(&GA) || !U.compilerUsedCount
(&GA)) && "We should have removed the duplicated "
 "element from llvm.compiler.used") ? void (0) : __assert_fail
 ("(!U.usedCount(&GA) || !U.compilerUsedCount(&GA)) && \"We should have removed the duplicated \" \"element from llvm.compiler.used\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2411, __extension__ __PRETTY_FUNCTION__));
if (!GA.hasOneUse())
  // Strictly more than one use. So at least one is not in llvm.used and
  // llvm.compiler.used.
  return true;

// Exactly one use. Check if it is in llvm.used or llvm.compiler.used.
return !U.usedCount(&GA) && !U.compilerUsedCount(&GA);
2419}

2421static bool hasMoreThanOneUseOtherThanLLVMUsed(GlobalValue &V,
                                             const LLVMUsed &U) {
unsigned N = 2;
assert((!U.usedCount(&V) || !U.compilerUsedCount(&V)) &&(static_cast <bool> ((!U.usedCount(&V) || !U.compilerUsedCount
(&V)) && "We should have removed the duplicated "
 "element from llvm.compiler.used") ? void (0) : __assert_fail
 ("(!U.usedCount(&V) || !U.compilerUsedCount(&V)) && \"We should have removed the duplicated \" \"element from llvm.compiler.used\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2426, __extension__ __PRETTY_FUNCTION__))
       "We should have removed the duplicated "(static_cast <bool> ((!U.usedCount(&V) || !U.compilerUsedCount
(&V)) && "We should have removed the duplicated "
 "element from llvm.compiler.used") ? void (0) : __assert_fail
 ("(!U.usedCount(&V) || !U.compilerUsedCount(&V)) && \"We should have removed the duplicated \" \"element from llvm.compiler.used\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2426, __extension__ __PRETTY_FUNCTION__))
       "element from llvm.compiler.used")(static_cast <bool> ((!U.usedCount(&V) || !U.compilerUsedCount
(&V)) && "We should have removed the duplicated "
 "element from llvm.compiler.used") ? void (0) : __assert_fail
 ("(!U.usedCount(&V) || !U.compilerUsedCount(&V)) && \"We should have removed the duplicated \" \"element from llvm.compiler.used\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2426, __extension__ __PRETTY_FUNCTION__));
if (U.usedCount(&V) || U.compilerUsedCount(&V))
  ++N;
return V.hasNUsesOrMore(N);
2430}

2432static bool mayHaveOtherReferences(GlobalAlias &GA, const LLVMUsed &U) {
if (!GA.hasLocalLinkage())
  return true;

return U.usedCount(&GA) || U.compilerUsedCount(&GA);
2437}

2439static bool hasUsesToReplace(GlobalAlias &GA, const LLVMUsed &U,
                           bool &RenameTarget) {
RenameTarget = false;
bool Ret = false;
if (hasUseOtherThanLLVMUsed(GA, U))
  Ret = true;

// If the alias is externally visible, we may still be able to simplify it.
if (!mayHaveOtherReferences(GA, U))
  return Ret;

// If the aliasee has internal linkage, give it the name and linkage
// of the alias, and delete the alias.  This turns:
//   define internal ... @f(...)
//   @a = alias ... @f
// into:
//   define ... @a(...)
Constant *Aliasee = GA.getAliasee();
GlobalValue *Target = cast<GlobalValue>(Aliasee->stripPointerCasts());
if (!Target->hasLocalLinkage())
  return Ret;

// Do not perform the transform if multiple aliases potentially target the
// aliasee. This check also ensures that it is safe to replace the section
// and other attributes of the aliasee with those of the alias.
if (hasMoreThanOneUseOtherThanLLVMUsed(*Target, U))
  return Ret;

RenameTarget = true;
return true;
2469}

2471static bool
2472OptimizeGlobalAliases(Module &M,
                    SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) {
bool Changed = false;
LLVMUsed Used(M);

for (GlobalValue *GV : Used.used())
  Used.compilerUsedErase(GV);

for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end();
     I != E;) {
  GlobalAlias *J = &*I++;

  // Aliases without names cannot be referenced outside this module.
  if (!J->hasName() && !J->isDeclaration() && !J->hasLocalLinkage())
    J->setLinkage(GlobalValue::InternalLinkage);

  if (deleteIfDead(*J, NotDiscardableComdats)) {
    Changed = true;
    continue;
  }

  // If the alias can change at link time, nothing can be done - bail out.
  if (J->isInterposable())
    continue;

  Constant *Aliasee = J->getAliasee();
  GlobalValue *Target = dyn_cast<GlobalValue>(Aliasee->stripPointerCasts());
  // We can't trivially replace the alias with the aliasee if the aliasee is
  // non-trivial in some way. We also can't replace the alias with the aliasee
  // if the aliasee is interposable because aliases point to the local
  // definition.
  // TODO: Try to handle non-zero GEPs of local aliasees.
  if (!Target || Target->isInterposable())
    continue;
  Target->removeDeadConstantUsers();

  // Make all users of the alias use the aliasee instead.
  bool RenameTarget;
  if (!hasUsesToReplace(*J, Used, RenameTarget))
    continue;

  J->replaceAllUsesWith(ConstantExpr::getBitCast(Aliasee, J->getType()));
  ++NumAliasesResolved;
  Changed = true;

  if (RenameTarget) {
    // Give the aliasee the name, linkage and other attributes of the alias.
    Target->takeName(&*J);
    Target->setLinkage(J->getLinkage());
    Target->setDSOLocal(J->isDSOLocal());
    Target->setVisibility(J->getVisibility());
    Target->setDLLStorageClass(J->getDLLStorageClass());

    if (Used.usedErase(&*J))
      Used.usedInsert(Target);

    if (Used.compilerUsedErase(&*J))
      Used.compilerUsedInsert(Target);
  } else if (mayHaveOtherReferences(*J, Used))
    continue;

  // Delete the alias.
  M.getAliasList().erase(J);
  ++NumAliasesRemoved;
  Changed = true;
}

Used.syncVariablesAndSets();

return Changed;
2542}

2544static Function *
2545FindCXAAtExit(Module &M, function_ref<TargetLibraryInfo &(Function &)> GetTLI) {
// Hack to get a default TLI before we have actual Function.
auto FuncIter = M.begin();
if (FuncIter == M.end())
  return nullptr;
auto *TLI = &GetTLI(*FuncIter);

LibFunc F = LibFunc_cxa_atexit;
if (!TLI->has(F))
  return nullptr;

Function *Fn = M.getFunction(TLI->getName(F));
if (!Fn)
  return nullptr;

// Now get the actual TLI for Fn.
TLI = &GetTLI(*Fn);

// Make sure that the function has the correct prototype.
if (!TLI->getLibFunc(*Fn, F) || F != LibFunc_cxa_atexit)
  return nullptr;

return Fn;
2568}

2570/// Returns whether the given function is an empty C++ destructor and can
2571/// therefore be eliminated.
2572/// Note that we assume that other optimization passes have already simplified
2573/// the code so we simply check for 'ret'.
2574static bool cxxDtorIsEmpty(const Function &Fn) {
// FIXME: We could eliminate C++ destructors if they're readonly/readnone and
// nounwind, but that doesn't seem worth doing.
if (Fn.isDeclaration())
  return false;

for (auto &I : Fn.getEntryBlock()) {
  if (isa<DbgInfoIntrinsic>(I))
    continue;
  if (isa<ReturnInst>(I))
    return true;
  break;
}
return false;
2588}

2590static bool OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn) {
/// Itanium C++ ABI p3.3.5:
///
///   After constructing a global (or local static) object, that will require
///   destruction on exit, a termination function is registered as follows:
///
///   extern "C" int __cxa_atexit ( void (*f)(void *), void *p, void *d );
///
///   This registration, e.g. __cxa_atexit(f,p,d), is intended to cause the
///   call f(p) when DSO d is unloaded, before all such termination calls
///   registered before this one. It returns zero if registration is
///   successful, nonzero on failure.

// This pass will look for calls to __cxa_atexit where the function is trivial
// and remove them.
bool Changed = false;

for (auto I = CXAAtExitFn->user_begin(), E = CXAAtExitFn->user_end();
     I != E;) {
  // We're only interested in calls. Theoretically, we could handle invoke
  // instructions as well, but neither llvm-gcc nor clang generate invokes
  // to __cxa_atexit.
  CallInst *CI = dyn_cast<CallInst>(*I++);
  if (!CI)
    continue;

  Function *DtorFn =
    dyn_cast<Function>(CI->getArgOperand(0)->stripPointerCasts());
  if (!DtorFn || !cxxDtorIsEmpty(*DtorFn))
    continue;

  // Just remove the call.
  CI->replaceAllUsesWith(Constant::getNullValue(CI->getType()));
  CI->eraseFromParent();

  ++NumCXXDtorsRemoved;

  Changed |= true;
}

return Changed;
2631}

2633static bool optimizeGlobalsInModule(
  Module &M, const DataLayout &DL,
  function_ref<TargetLibraryInfo &(Function &)> GetTLI,
  function_ref<TargetTransformInfo &(Function &)> GetTTI,
  function_ref<BlockFrequencyInfo &(Function &)> GetBFI,
  function_ref<DominatorTree &(Function &)> LookupDomTree) {
SmallPtrSet<const Comdat *, 8> NotDiscardableComdats;
bool Changed = false;
bool LocalChange = true;
while (LocalChange) {
  LocalChange = false;

  NotDiscardableComdats.clear();
  for (const GlobalVariable &GV : M.globals())
    if (const Comdat *C = GV.getComdat())
      if (!GV.isDiscardableIfUnused() || !GV.use_empty())
        NotDiscardableComdats.insert(C);
  for (Function &F : M)
    if (const Comdat *C = F.getComdat())
      if (!F.isDefTriviallyDead())
        NotDiscardableComdats.insert(C);
  for (GlobalAlias &GA : M.aliases())
    if (const Comdat *C = GA.getComdat())
      if (!GA.isDiscardableIfUnused() || !GA.use_empty())
        NotDiscardableComdats.insert(C);

  // Delete functions that are trivially dead, ccc -> fastcc
  LocalChange |= OptimizeFunctions(M, GetTLI, GetTTI, GetBFI, LookupDomTree,
                                   NotDiscardableComdats);

  // Optimize global_ctors list.
  LocalChange |= optimizeGlobalCtorsList(M, [&](Function *F) {
    return EvaluateStaticConstructor(F, DL, &GetTLI(*F));
1
Calling 'EvaluateStaticConstructor'→
  });

  // Optimize non-address-taken globals.
  LocalChange |=
      OptimizeGlobalVars(M, GetTLI, LookupDomTree, NotDiscardableComdats);

  // Resolve aliases, when possible.
  LocalChange |= OptimizeGlobalAliases(M, NotDiscardableComdats);

  // Try to remove trivial global destructors if they are not removed
  // already.
  Function *CXAAtExitFn = FindCXAAtExit(M, GetTLI);
  if (CXAAtExitFn)
    LocalChange |= OptimizeEmptyGlobalCXXDtors(CXAAtExitFn);

  Changed |= LocalChange;
}

// TODO: Move all global ctors functions to the end of the module for code
// layout.

return Changed;
2688}

2690PreservedAnalyses GlobalOptPass::run(Module &M, ModuleAnalysisManager &AM) {
  auto &DL = M.getDataLayout();
  auto &FAM =
      AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
  auto LookupDomTree = [&FAM](Function &F) -> DominatorTree &{
    return FAM.getResult<DominatorTreeAnalysis>(F);
  };
  auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & {
    return FAM.getResult<TargetLibraryAnalysis>(F);
  };
  auto GetTTI = [&FAM](Function &F) -> TargetTransformInfo & {
    return FAM.getResult<TargetIRAnalysis>(F);
  };

  auto GetBFI = [&FAM](Function &F) -> BlockFrequencyInfo & {
    return FAM.getResult<BlockFrequencyAnalysis>(F);
  };

  if (!optimizeGlobalsInModule(M, DL, GetTLI, GetTTI, GetBFI, LookupDomTree))
    return PreservedAnalyses::all();
  return PreservedAnalyses::none();
2711}

2713namespace {

2715struct GlobalOptLegacyPass : public ModulePass {
static char ID; // Pass identification, replacement for typeid

GlobalOptLegacyPass() : ModulePass(ID) {
  initializeGlobalOptLegacyPassPass(*PassRegistry::getPassRegistry());
}

bool runOnModule(Module &M) override {
  if (skipModule(M))
    return false;

  auto &DL = M.getDataLayout();
  auto LookupDomTree = [this](Function &F) -> DominatorTree & {
    return this->getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
  };
  auto GetTLI = [this](Function &F) -> TargetLibraryInfo & {
    return this->getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
  };
  auto GetTTI = [this](Function &F) -> TargetTransformInfo & {
    return this->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
  };

  auto GetBFI = [this](Function &F) -> BlockFrequencyInfo & {
    return this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
  };

  return optimizeGlobalsInModule(M, DL, GetTLI, GetTTI, GetBFI,
                                 LookupDomTree);
}

void getAnalysisUsage(AnalysisUsage &AU) const override {
  AU.addRequired<TargetLibraryInfoWrapperPass>();
  AU.addRequired<TargetTransformInfoWrapperPass>();
  AU.addRequired<DominatorTreeWrapperPass>();
  AU.addRequired<BlockFrequencyInfoWrapperPass>();
}
2751};

2753} // end anonymous namespace

2755char GlobalOptLegacyPass::ID = 0;

2757INITIALIZE_PASS_BEGIN(GlobalOptLegacyPass, "globalopt",static void *initializeGlobalOptLegacyPassPassOnce(PassRegistry
 &Registry) {
                    "Global Variable Optimizer", false, false)static void *initializeGlobalOptLegacyPassPassOnce(PassRegistry
 &Registry) {
2759INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry);
2760INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)initializeTargetTransformInfoWrapperPassPass(Registry);
2761INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)initializeBlockFrequencyInfoWrapperPassPass(Registry);
2762INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
2763INITIALIZE_PASS_END(GlobalOptLegacyPass, "globalopt",PassInfo *PI = new PassInfo( "Global Variable Optimizer", "globalopt"
, &GlobalOptLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<GlobalOptLegacyPass>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeGlobalOptLegacyPassPassFlag
; void llvm::initializeGlobalOptLegacyPassPass(PassRegistry &
Registry) { llvm::call_once(InitializeGlobalOptLegacyPassPassFlag
, initializeGlobalOptLegacyPassPassOnce, std::ref(Registry));
 }
                  "Global Variable Optimizer", false, false)PassInfo *PI = new PassInfo( "Global Variable Optimizer", "globalopt"
, &GlobalOptLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<GlobalOptLegacyPass>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeGlobalOptLegacyPassPassFlag
; void llvm::initializeGlobalOptLegacyPassPass(PassRegistry &
Registry) { llvm::call_once(InitializeGlobalOptLegacyPassPassFlag
, initializeGlobalOptLegacyPassPassOnce, std::ref(Registry));
 }

2766ModulePass *llvm::createGlobalOptimizerPass() {
return new GlobalOptLegacyPass();
2768}

←

/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/SmallVector.h

1//===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- 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 SmallVector class.
10//
11//===----------------------------------------------------------------------===//

13#ifndef LLVM_ADT_SMALLVECTOR_H
14#define LLVM_ADT_SMALLVECTOR_H

16#include "llvm/ADT/iterator_range.h"
17#include "llvm/Support/Compiler.h"
18#include "llvm/Support/ErrorHandling.h"
19#include "llvm/Support/MemAlloc.h"
20#include "llvm/Support/type_traits.h"
21#include <algorithm>
22#include <cassert>
23#include <cstddef>
24#include <cstdlib>
25#include <cstring>
26#include <functional>
27#include <initializer_list>
28#include <iterator>
29#include <limits>
30#include <memory>
31#include <new>
32#include <type_traits>
33#include <utility>

35namespace llvm {

37/// This is all the stuff common to all SmallVectors.
38///
39/// The template parameter specifies the type which should be used to hold the
40/// Size and Capacity of the SmallVector, so it can be adjusted.
41/// Using 32 bit size is desirable to shrink the size of the SmallVector.
42/// Using 64 bit size is desirable for cases like SmallVector<char>, where a
43/// 32 bit size would limit the vector to ~4GB. SmallVectors are used for
44/// buffering bitcode output - which can exceed 4GB.
45template <class Size_T> class SmallVectorBase {
46protected:
void *BeginX;
Size_T Size = 0, Capacity;

/// The maximum value of the Size_T used.
static constexpr size_t SizeTypeMax() {
  return std::numeric_limits<Size_T>::max();
}

SmallVectorBase() = delete;
SmallVectorBase(void *FirstEl, size_t TotalCapacity)
    : BeginX(FirstEl), Capacity(TotalCapacity) {}

/// This is a helper for \a grow() that's out of line to reduce code
/// duplication.  This function will report a fatal error if it can't grow at
/// least to \p MinSize.
void *mallocForGrow(size_t MinSize, size_t TSize, size_t &NewCapacity);

/// This is an implementation of the grow() method which only works
/// on POD-like data types and is out of line to reduce code duplication.
/// This function will report a fatal error if it cannot increase capacity.
void grow_pod(void *FirstEl, size_t MinSize, size_t TSize);

69public:
size_t size() const { return Size; }
size_t capacity() const { return Capacity; }

LLVM_NODISCARD[[clang::warn_unused_result]] bool empty() const { return !Size; }
10
←
Assuming field 'Size' is not equal to 0→
11
←
Returning zero, which participates in a condition later→

/// Set the array size to \p N, which the current array must have enough
/// capacity for.
///
/// This does not construct or destroy any elements in the vector.
///
/// Clients can use this in conjunction with capacity() to write past the end
/// of the buffer when they know that more elements are available, and only
/// update the size later. This avoids the cost of value initializing elements
/// which will only be overwritten.
void set_size(size_t N) {
  assert(N <= capacity())(static_cast <bool> (N <= capacity()) ? void (0) : __assert_fail
 ("N <= capacity()", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/SmallVector.h"
, 85, __extension__ __PRETTY_FUNCTION__));
  Size = N;
}
88};

90template <class T>
91using SmallVectorSizeType =
  typename std::conditional<sizeof(T) < 4 && sizeof(void *) >= 8, uint64_t,
                            uint32_t>::type;

95/// Figure out the offset of the first element.
96template <class T, typename = void> struct SmallVectorAlignmentAndSize {
alignas(SmallVectorBase<SmallVectorSizeType<T>>) char Base[sizeof(
    SmallVectorBase<SmallVectorSizeType<T>>)];
alignas(T) char FirstEl[sizeof(T)];
100};

102/// This is the part of SmallVectorTemplateBase which does not depend on whether
103/// the type T is a POD. The extra dummy template argument is used by ArrayRef
104/// to avoid unnecessarily requiring T to be complete.
105template <typename T, typename = void>
106class SmallVectorTemplateCommon
  : public SmallVectorBase<SmallVectorSizeType<T>> {
using Base = SmallVectorBase<SmallVectorSizeType<T>>;

/// Find the address of the first element.  For this pointer math to be valid
/// with small-size of 0 for T with lots of alignment, it's important that
/// SmallVectorStorage is properly-aligned even for small-size of 0.
void *getFirstEl() const {
  return const_cast<void *>(reinterpret_cast<const void *>(
      reinterpret_cast<const char *>(this) +
      offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)__builtin_offsetof(SmallVectorAlignmentAndSize<T>, FirstEl
)));
}
// Space after 'FirstEl' is clobbered, do not add any instance vars after it.

120protected:
SmallVectorTemplateCommon(size_t Size) : Base(getFirstEl(), Size) {}

void grow_pod(size_t MinSize, size_t TSize) {
  Base::grow_pod(getFirstEl(), MinSize, TSize);
}

/// Return true if this is a smallvector which has not had dynamic
/// memory allocated for it.
bool isSmall() const { return this->BeginX == getFirstEl(); }

/// Put this vector in a state of being small.
void resetToSmall() {
  this->BeginX = getFirstEl();
  this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
}

/// Return true if V is an internal reference to the given range.
bool isReferenceToRange(const void *V, const void *First, const void *Last) const {
  // Use std::less to avoid UB.
  std::less<> LessThan;
  return !LessThan(V, First) && LessThan(V, Last);
}

/// Return true if V is an internal reference to this vector.
bool isReferenceToStorage(const void *V) const {
  return isReferenceToRange(V, this->begin(), this->end());
}

/// Return true if First and Last form a valid (possibly empty) range in this
/// vector's storage.
bool isRangeInStorage(const void *First, const void *Last) const {
  // Use std::less to avoid UB.
  std::less<> LessThan;
  return !LessThan(First, this->begin()) && !LessThan(Last, First) &&
         !LessThan(this->end(), Last);
}

/// Return true unless Elt will be invalidated by resizing the vector to
/// NewSize.
bool isSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
  // Past the end.
  if (LLVM_LIKELY(!isReferenceToStorage(Elt))__builtin_expect((bool)(!isReferenceToStorage(Elt)), true))
    return true;

  // Return false if Elt will be destroyed by shrinking.
  if (NewSize <= this->size())
    return Elt < this->begin() + NewSize;

  // Return false if we need to grow.
  return NewSize <= this->capacity();
}

/// Check whether Elt will be invalidated by resizing the vector to NewSize.
void assertSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
  assert(isSafeToReferenceAfterResize(Elt, NewSize) &&(static_cast <bool> (isSafeToReferenceAfterResize(Elt, NewSize
) && "Attempting to reference an element of the vector in an operation "
 "that invalidates it") ? void (0) : __assert_fail ("isSafeToReferenceAfterResize(Elt, NewSize) && \"Attempting to reference an element of the vector in an operation \" \"that invalidates it\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/SmallVector.h"
, 177, __extension__ __PRETTY_FUNCTION__))
         "Attempting to reference an element of the vector in an operation "(static_cast <bool> (isSafeToReferenceAfterResize(Elt, NewSize
) && "Attempting to reference an element of the vector in an operation "
 "that invalidates it") ? void (0) : __assert_fail ("isSafeToReferenceAfterResize(Elt, NewSize) && \"Attempting to reference an element of the vector in an operation \" \"that invalidates it\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/SmallVector.h"
, 177, __extension__ __PRETTY_FUNCTION__))
         "that invalidates it")(static_cast <bool> (isSafeToReferenceAfterResize(Elt, NewSize
) && "Attempting to reference an element of the vector in an operation "
 "that invalidates it") ? void (0) : __assert_fail ("isSafeToReferenceAfterResize(Elt, NewSize) && \"Attempting to reference an element of the vector in an operation \" \"that invalidates it\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/SmallVector.h"
, 177, __extension__ __PRETTY_FUNCTION__));
}

/// Check whether Elt will be invalidated by increasing the size of the
/// vector by N.
void assertSafeToAdd(const void *Elt, size_t N = 1) {
  this->assertSafeToReferenceAfterResize(Elt, this->size() + N);
}

/// Check whether any part of the range will be invalidated by clearing.
void assertSafeToReferenceAfterClear(const T *From, const T *To) {
  if (From == To)
    return;
  this->assertSafeToReferenceAfterResize(From, 0);
  this->assertSafeToReferenceAfterResize(To - 1, 0);
}
template <
    class ItTy,
    std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
                     bool> = false>
void assertSafeToReferenceAfterClear(ItTy, ItTy) {}

/// Check whether any part of the range will be invalidated by growing.
void assertSafeToAddRange(const T *From, const T *To) {
  if (From == To)
    return;
  this->assertSafeToAdd(From, To - From);
  this->assertSafeToAdd(To - 1, To - From);
}
template <
    class ItTy,
    std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
                     bool> = false>
void assertSafeToAddRange(ItTy, ItTy) {}

/// Reserve enough space to add one element, and return the updated element
/// pointer in case it was a reference to the storage.
template <class U>
static const T *reserveForParamAndGetAddressImpl(U *This, const T &Elt,
                                                 size_t N) {
  size_t NewSize = This->size() + N;
  if (LLVM_LIKELY(NewSize <= This->capacity())__builtin_expect((bool)(NewSize <= This->capacity()), true
))
    return &Elt;

  bool ReferencesStorage = false;
  int64_t Index = -1;
  if (!U::TakesParamByValue) {
    if (LLVM_UNLIKELY(This->isReferenceToStorage(&Elt))__builtin_expect((bool)(This->isReferenceToStorage(&Elt
)), false)) {
      ReferencesStorage = true;
      Index = &Elt - This->begin();
    }
  }
  This->grow(NewSize);
  return ReferencesStorage ? This->begin() + Index : &Elt;
}

233public:
using size_type = size_t;
using difference_type = ptrdiff_t;
using value_type = T;
using iterator = T *;
using const_iterator = const T *;

using const_reverse_iterator = std::reverse_iterator<const_iterator>;
using reverse_iterator = std::reverse_iterator<iterator>;

using reference = T &;
using const_reference = const T &;
using pointer = T *;
using const_pointer = const T *;

using Base::capacity;
using Base::empty;
using Base::size;

// forward iterator creation methods.
iterator begin() { return (iterator)this->BeginX; }
const_iterator begin() const { return (const_iterator)this->BeginX; }
iterator end() { return begin() + size(); }
const_iterator end() const { return begin() + size(); }

// reverse iterator creation methods.
reverse_iterator rbegin()            { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
reverse_iterator rend()              { return reverse_iterator(begin()); }
const_reverse_iterator rend() const { return const_reverse_iterator(begin());}

size_type size_in_bytes() const { return size() * sizeof(T); }
size_type max_size() const {
  return std::min(this->SizeTypeMax(), size_type(-1) / sizeof(T));
}

size_t capacity_in_bytes() const { return capacity() * sizeof(T); }

/// Return a pointer to the vector's buffer, even if empty().
pointer data() { return pointer(begin()); }
/// Return a pointer to the vector's buffer, even if empty().
const_pointer data() const { return const_pointer(begin()); }

reference operator[](size_type idx) {
  assert(idx < size())(static_cast <bool> (idx < size()) ? void (0) : __assert_fail
 ("idx < size()", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/SmallVector.h"
, 277, __extension__ __PRETTY_FUNCTION__));
  return begin()[idx];
}
const_reference operator[](size_type idx) const {
  assert(idx < size())(static_cast <bool> (idx < size()) ? void (0) : __assert_fail
 ("idx < size()", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/SmallVector.h"
, 281, __extension__ __PRETTY_FUNCTION__));
  return begin()[idx];
}

reference front() {
  assert(!empty())(static_cast <bool> (!empty()) ? void (0) : __assert_fail
 ("!empty()", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/SmallVector.h"
, 286, __extension__ __PRETTY_FUNCTION__));
  return begin()[0];
}
const_reference front() const {
  assert(!empty())(static_cast <bool> (!empty()) ? void (0) : __assert_fail
 ("!empty()", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/SmallVector.h"
, 290, __extension__ __PRETTY_FUNCTION__));
  return begin()[0];
}

reference back() {
  assert(!empty())(static_cast <bool> (!empty()) ? void (0) : __assert_fail
 ("!empty()", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/SmallVector.h"
, 295, __extension__ __PRETTY_FUNCTION__));
  return end()[-1];
}
const_reference back() const {
  assert(!empty())(static_cast <bool> (!empty()) ? void (0) : __assert_fail
 ("!empty()", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/SmallVector.h"
, 299, __extension__ __PRETTY_FUNCTION__));
  return end()[-1];
}
302};

304/// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put
305/// method implementations that are designed to work with non-trivial T's.
306///
307/// We approximate is_trivially_copyable with trivial move/copy construction and
308/// trivial destruction. While the standard doesn't specify that you're allowed
309/// copy these types with memcpy, there is no way for the type to observe this.
310/// This catches the important case of std::pair<POD, POD>, which is not
311/// trivially assignable.
312template <typename T, bool = (is_trivially_copy_constructible<T>::value) &&
                           (is_trivially_move_constructible<T>::value) &&
                           std::is_trivially_destructible<T>::value>
315class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
friend class SmallVectorTemplateCommon<T>;

318protected:
static constexpr bool TakesParamByValue = false;
using ValueParamT = const T &;

SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}

static void destroy_range(T *S, T *E) {
  while (S != E) {
    --E;
    E->~T();
  }
}

/// Move the range [I, E) into the uninitialized memory starting with "Dest",
/// constructing elements as needed.
template<typename It1, typename It2>
static void uninitialized_move(It1 I, It1 E, It2 Dest) {
  std::uninitialized_copy(std::make_move_iterator(I),
                          std::make_move_iterator(E), Dest);
}

/// Copy the range [I, E) onto the uninitialized memory starting with "Dest",
/// constructing elements as needed.
template<typename It1, typename It2>
static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
  std::uninitialized_copy(I, E, Dest);
}

/// Grow the allocated memory (without initializing new elements), doubling
/// the size of the allocated memory. Guarantees space for at least one more
/// element, or MinSize more elements if specified.
void grow(size_t MinSize = 0);

/// Create a new allocation big enough for \p MinSize and pass back its size
/// in \p NewCapacity. This is the first section of \a grow().
T *mallocForGrow(size_t MinSize, size_t &NewCapacity) {
  return static_cast<T *>(
      SmallVectorBase<SmallVectorSizeType<T>>::mallocForGrow(
          MinSize, sizeof(T), NewCapacity));
}

/// Move existing elements over to the new allocation \p NewElts, the middle
/// section of \a grow().
void moveElementsForGrow(T *NewElts);

/// Transfer ownership of the allocation, finishing up \a grow().
void takeAllocationForGrow(T *NewElts, size_t NewCapacity);

/// Reserve enough space to add one element, and return the updated element
/// pointer in case it was a reference to the storage.
const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
  return this->reserveForParamAndGetAddressImpl(this, Elt, N);
}

/// Reserve enough space to add one element, and return the updated element
/// pointer in case it was a reference to the storage.
T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
  return const_cast<T *>(
      this->reserveForParamAndGetAddressImpl(this, Elt, N));
}

static T &&forward_value_param(T &&V) { return std::move(V); }
static const T &forward_value_param(const T &V) { return V; }

void growAndAssign(size_t NumElts, const T &Elt) {
  // Grow manually in case Elt is an internal reference.
  size_t NewCapacity;
  T *NewElts = mallocForGrow(NumElts, NewCapacity);
  std::uninitialized_fill_n(NewElts, NumElts, Elt);
  this->destroy_range(this->begin(), this->end());
  takeAllocationForGrow(NewElts, NewCapacity);
  this->set_size(NumElts);
}

template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) {
  // Grow manually in case one of Args is an internal reference.
  size_t NewCapacity;
  T *NewElts = mallocForGrow(0, NewCapacity);
  ::new ((void *)(NewElts + this->size())) T(std::forward<ArgTypes>(Args)...);
  moveElementsForGrow(NewElts);
  takeAllocationForGrow(NewElts, NewCapacity);
  this->set_size(this->size() + 1);
  return this->back();
}

403public:
void push_back(const T &Elt) {
  const T *EltPtr = reserveForParamAndGetAddress(Elt);
  ::new ((void *)this->end()) T(*EltPtr);
  this->set_size(this->size() + 1);
}

void push_back(T &&Elt) {
  T *EltPtr = reserveForParamAndGetAddress(Elt);
  ::new ((void *)this->end()) T(::std::move(*EltPtr));
  this->set_size(this->size() + 1);
}

void pop_back() {
  this->set_size(this->size() - 1);
  this->end()->~T();
}
420};

422// Define this out-of-line to dissuade the C++ compiler from inlining it.
423template <typename T, bool TriviallyCopyable>
424void SmallVectorTemplateBase<T, TriviallyCopyable>::grow(size_t MinSize) {
size_t NewCapacity;
T *NewElts = mallocForGrow(MinSize, NewCapacity);
moveElementsForGrow(NewElts);
takeAllocationForGrow(NewElts, NewCapacity);
429}

431// Define this out-of-line to dissuade the C++ compiler from inlining it.
432template <typename T, bool TriviallyCopyable>
433void SmallVectorTemplateBase<T, TriviallyCopyable>::moveElementsForGrow(
  T *NewElts) {
// Move the elements over.
this->uninitialized_move(this->begin(), this->end(), NewElts);

// Destroy the original elements.
destroy_range(this->begin(), this->end());
440}

442// Define this out-of-line to dissuade the C++ compiler from inlining it.
443template <typename T, bool TriviallyCopyable>
444void SmallVectorTemplateBase<T, TriviallyCopyable>::takeAllocationForGrow(
  T *NewElts, size_t NewCapacity) {
// If this wasn't grown from the inline copy, deallocate the old space.
if (!this->isSmall())
  free(this->begin());

this->BeginX = NewElts;
this->Capacity = NewCapacity;
452}

454/// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put
455/// method implementations that are designed to work with trivially copyable
456/// T's. This allows using memcpy in place of copy/move construction and
457/// skipping destruction.
458template <typename T>
459class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
friend class SmallVectorTemplateCommon<T>;

462protected:
/// True if it's cheap enough to take parameters by value. Doing so avoids
/// overhead related to mitigations for reference invalidation.
static constexpr bool TakesParamByValue = sizeof(T) <= 2 * sizeof(void *);

/// Either const T& or T, depending on whether it's cheap enough to take
/// parameters by value.
using ValueParamT =
    typename std::conditional<TakesParamByValue, T, const T &>::type;

SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}

// No need to do a destroy loop for POD's.
static void destroy_range(T *, T *) {}

/// Move the range [I, E) onto the uninitialized memory
/// starting with "Dest", constructing elements into it as needed.
template<typename It1, typename It2>
static void uninitialized_move(It1 I, It1 E, It2 Dest) {
  // Just do a copy.
  uninitialized_copy(I, E, Dest);
}

/// Copy the range [I, E) onto the uninitialized memory
/// starting with "Dest", constructing elements into it as needed.
template<typename It1, typename It2>
static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
  // Arbitrary iterator types; just use the basic implementation.
  std::uninitialized_copy(I, E, Dest);
}

/// Copy the range [I, E) onto the uninitialized memory
/// starting with "Dest", constructing elements into it as needed.
template <typename T1, typename T2>
static void uninitialized_copy(
    T1 *I, T1 *E, T2 *Dest,
    std::enable_if_t<std::is_same<typename std::remove_const<T1>::type,
                                  T2>::value> * = nullptr) {
  // Use memcpy for PODs iterated by pointers (which includes SmallVector
  // iterators): std::uninitialized_copy optimizes to memmove, but we can
  // use memcpy here. Note that I and E are iterators and thus might be
  // invalid for memcpy if they are equal.
  if (I != E)
    memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T));
}

/// Double the size of the allocated memory, guaranteeing space for at
/// least one more element or MinSize if specified.
void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }

/// Reserve enough space to add one element, and return the updated element
/// pointer in case it was a reference to the storage.
const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
  return this->reserveForParamAndGetAddressImpl(this, Elt, N);
}

/// Reserve enough space to add one element, and return the updated element
/// pointer in case it was a reference to the storage.
T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
  return const_cast<T *>(
      this->reserveForParamAndGetAddressImpl(this, Elt, N));
}

/// Copy \p V or return a reference, depending on \a ValueParamT.
static ValueParamT forward_value_param(ValueParamT V) { return V; }

void growAndAssign(size_t NumElts, T Elt) {
  // Elt has been copied in case it's an internal reference, side-stepping
  // reference invalidation problems without losing the realloc optimization.
  this->set_size(0);
  this->grow(NumElts);
  std::uninitialized_fill_n(this->begin(), NumElts, Elt);
  this->set_size(NumElts);
}

template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) {
  // Use push_back with a copy in case Args has an internal reference,
  // side-stepping reference invalidation problems without losing the realloc
  // optimization.
  push_back(T(std::forward<ArgTypes>(Args)...));
  return this->back();
}

545public:
void push_back(ValueParamT Elt) {
  const T *EltPtr = reserveForParamAndGetAddress(Elt);
  memcpy(reinterpret_cast<void *>(this->end()), EltPtr, sizeof(T));
  this->set_size(this->size() + 1);
}

void pop_back() { this->set_size(this->size() - 1); }
553};

555/// This class consists of common code factored out of the SmallVector class to
556/// reduce code duplication based on the SmallVector 'N' template parameter.
557template <typename T>
558class SmallVectorImpl : public SmallVectorTemplateBase<T> {
using SuperClass = SmallVectorTemplateBase<T>;

561public:
using iterator = typename SuperClass::iterator;
using const_iterator = typename SuperClass::const_iterator;
using reference = typename SuperClass::reference;
using size_type = typename SuperClass::size_type;

567protected:
using SmallVectorTemplateBase<T>::TakesParamByValue;
using ValueParamT = typename SuperClass::ValueParamT;

// Default ctor - Initialize to empty.
explicit SmallVectorImpl(unsigned N)
    : SmallVectorTemplateBase<T>(N) {}

575public:
SmallVectorImpl(const SmallVectorImpl &) = delete;

~SmallVectorImpl() {
  // Subclass has already destructed this vector's elements.
  // If this wasn't grown from the inline copy, deallocate the old space.
  if (!this->isSmall())
    free(this->begin());
}

void clear() {
  this->destroy_range(this->begin(), this->end());
  this->Size = 0;
}

590private:
template <bool ForOverwrite> void resizeImpl(size_type N) {
  if (N < this->size()) {
    this->pop_back_n(this->size() - N);
  } else if (N > this->size()) {
    this->reserve(N);
    for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
      if (ForOverwrite)
        new (&*I) T;
      else
        new (&*I) T();
    this->set_size(N);
  }
}

605public:
void resize(size_type N) { resizeImpl<false>(N); }

/// Like resize, but \ref T is POD, the new values won't be initialized.
void resize_for_overwrite(size_type N) { resizeImpl<true>(N); }

void resize(size_type N, ValueParamT NV) {
  if (N == this->size())
    return;

  if (N < this->size()) {
    this->pop_back_n(this->size() - N);
    return;
  }

  // N > this->size(). Defer to append.
  this->append(N - this->size(), NV);
}

void reserve(size_type N) {
  if (this->capacity() < N)
    this->grow(N);
}

void pop_back_n(size_type NumItems) {
  assert(this->size() >= NumItems)(static_cast <bool> (this->size() >= NumItems) ? void
 (0) : __assert_fail ("this->size() >= NumItems", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/SmallVector.h"
, 630, __extension__ __PRETTY_FUNCTION__));
  this->destroy_range(this->end() - NumItems, this->end());
  this->set_size(this->size() - NumItems);
}

LLVM_NODISCARD[[clang::warn_unused_result]] T pop_back_val() {
  T Result = ::std::move(this->back());
  this->pop_back();
  return Result;
}

void swap(SmallVectorImpl &RHS);

/// Add the specified range to the end of the SmallVector.
template <typename in_iter,
          typename = std::enable_if_t<std::is_convertible<
              typename std::iterator_traits<in_iter>::iterator_category,
              std::input_iterator_tag>::value>>
void append(in_iter in_start, in_iter in_end) {
  this->assertSafeToAddRange(in_start, in_end);
  size_type NumInputs = std::distance(in_start, in_end);
  this->reserve(this->size() + NumInputs);
  this->uninitialized_copy(in_start, in_end, this->end());
  this->set_size(this->size() + NumInputs);
}

/// Append \p NumInputs copies of \p Elt to the end.
void append(size_type NumInputs, ValueParamT Elt) {
  const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumInputs);
  std::uninitialized_fill_n(this->end(), NumInputs, *EltPtr);
  this->set_size(this->size() + NumInputs);
}

void append(std::initializer_list<T> IL) {
  append(IL.begin(), IL.end());
}

void append(const SmallVectorImpl &RHS) { append(RHS.begin(), RHS.end()); }

void assign(size_type NumElts, ValueParamT Elt) {
  // Note that Elt could be an internal reference.
  if (NumElts > this->capacity()) {
    this->growAndAssign(NumElts, Elt);
    return;
  }

  // Assign over existing elements.
  std::fill_n(this->begin(), std::min(NumElts, this->size()), Elt);
  if (NumElts > this->size())
    std::uninitialized_fill_n(this->end(), NumElts - this->size(), Elt);
  else if (NumElts < this->size())
    this->destroy_range(this->begin() + NumElts, this->end());
  this->set_size(NumElts);
}

// FIXME: Consider assigning over existing elements, rather than clearing &
// re-initializing them - for all assign(...) variants.

template <typename in_iter,
          typename = std::enable_if_t<std::is_convertible<
              typename std::iterator_traits<in_iter>::iterator_category,
              std::input_iterator_tag>::value>>
void assign(in_iter in_start, in_iter in_end) {
  this->assertSafeToReferenceAfterClear(in_start, in_end);
  clear();
  append(in_start, in_end);
}

void assign(std::initializer_list<T> IL) {
  clear();
  append(IL);
}

void assign(const SmallVectorImpl &RHS) { assign(RHS.begin(), RHS.end()); }

iterator erase(const_iterator CI) {
  // Just cast away constness because this is a non-const member function.
  iterator I = const_cast<iterator>(CI);

  assert(this->isReferenceToStorage(CI) && "Iterator to erase is out of bounds.")(static_cast <bool> (this->isReferenceToStorage(CI) &&
 "Iterator to erase is out of bounds.") ? void (0) : __assert_fail
 ("this->isReferenceToStorage(CI) && \"Iterator to erase is out of bounds.\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/SmallVector.h"
, 709, __extension__ __PRETTY_FUNCTION__));

  iterator N = I;
  // Shift all elts down one.
  std::move(I+1, this->end(), I);
  // Drop the last elt.
  this->pop_back();
  return(N);
}

iterator erase(const_iterator CS, const_iterator CE) {
  // Just cast away constness because this is a non-const member function.
  iterator S = const_cast<iterator>(CS);
  iterator E = const_cast<iterator>(CE);

  assert(this->isRangeInStorage(S, E) && "Range to erase is out of bounds.")(static_cast <bool> (this->isRangeInStorage(S, E) &&
 "Range to erase is out of bounds.") ? void (0) : __assert_fail
 ("this->isRangeInStorage(S, E) && \"Range to erase is out of bounds.\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/SmallVector.h"
, 724, __extension__ __PRETTY_FUNCTION__));

  iterator N = S;
  // Shift all elts down.
  iterator I = std::move(E, this->end(), S);
  // Drop the last elts.
  this->destroy_range(I, this->end());
  this->set_size(I - this->begin());
  return(N);
}

735private:
template <class ArgType> iterator insert_one_impl(iterator I, ArgType &&Elt) {
  // Callers ensure that ArgType is derived from T.
  static_assert(
      std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>,
                   T>::value,
      "ArgType must be derived from T!");

  if (I == this->end()) {  // Important special case for empty vector.
    this->push_back(::std::forward<ArgType>(Elt));
    return this->end()-1;
  }

  assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")(static_cast <bool> (this->isReferenceToStorage(I) &&
 "Insertion iterator is out of bounds.") ? void (0) : __assert_fail
 ("this->isReferenceToStorage(I) && \"Insertion iterator is out of bounds.\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/SmallVector.h"
, 748, __extension__ __PRETTY_FUNCTION__));

  // Grow if necessary.
  size_t Index = I - this->begin();
  std::remove_reference_t<ArgType> *EltPtr =
      this->reserveForParamAndGetAddress(Elt);
  I = this->begin() + Index;

  ::new ((void*) this->end()) T(::std::move(this->back()));
  // Push everything else over.
  std::move_backward(I, this->end()-1, this->end());
  this->set_size(this->size() + 1);

  // If we just moved the element we're inserting, be sure to update
  // the reference (never happens if TakesParamByValue).
  static_assert(!TakesParamByValue || std::is_same<ArgType, T>::value,
                "ArgType must be 'T' when taking by value!");
  if (!TakesParamByValue && this->isReferenceToRange(EltPtr, I, this->end()))
    ++EltPtr;

  *I = ::std::forward<ArgType>(*EltPtr);
  return I;
}

772public:
iterator insert(iterator I, T &&Elt) {
  return insert_one_impl(I, this->forward_value_param(std::move(Elt)));
}

iterator insert(iterator I, const T &Elt) {
  return insert_one_impl(I, this->forward_value_param(Elt));
}

iterator insert(iterator I, size_type NumToInsert, ValueParamT Elt) {
  // Convert iterator to elt# to avoid invalidating iterator when we reserve()
  size_t InsertElt = I - this->begin();

  if (I == this->end()) {  // Important special case for empty vector.
    append(NumToInsert, Elt);
    return this->begin()+InsertElt;
  }

  assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")(static_cast <bool> (this->isReferenceToStorage(I) &&
 "Insertion iterator is out of bounds.") ? void (0) : __assert_fail
 ("this->isReferenceToStorage(I) && \"Insertion iterator is out of bounds.\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/SmallVector.h"
, 790, __extension__ __PRETTY_FUNCTION__));

  // Ensure there is enough space, and get the (maybe updated) address of
  // Elt.
  const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumToInsert);

  // Uninvalidate the iterator.
  I = this->begin()+InsertElt;

  // If there are more elements between the insertion point and the end of the
  // range than there are being inserted, we can use a simple approach to
  // insertion.  Since we already reserved space, we know that this won't
  // reallocate the vector.
  if (size_t(this->end()-I) >= NumToInsert) {
    T *OldEnd = this->end();
    append(std::move_iterator<iterator>(this->end() - NumToInsert),
           std::move_iterator<iterator>(this->end()));

    // Copy the existing elements that get replaced.
    std::move_backward(I, OldEnd-NumToInsert, OldEnd);

    // If we just moved the element we're inserting, be sure to update
    // the reference (never happens if TakesParamByValue).
    if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
      EltPtr += NumToInsert;

    std::fill_n(I, NumToInsert, *EltPtr);
    return I;
  }

  // Otherwise, we're inserting more elements than exist already, and we're
  // not inserting at the end.

  // Move over the elements that we're about to overwrite.
  T *OldEnd = this->end();
  this->set_size(this->size() + NumToInsert);
  size_t NumOverwritten = OldEnd-I;
  this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);

  // If we just moved the element we're inserting, be sure to update
  // the reference (never happens if TakesParamByValue).
  if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
    EltPtr += NumToInsert;

  // Replace the overwritten part.
  std::fill_n(I, NumOverwritten, *EltPtr);

  // Insert the non-overwritten middle part.
  std::uninitialized_fill_n(OldEnd, NumToInsert - NumOverwritten, *EltPtr);
  return I;
}

template <typename ItTy,
          typename = std::enable_if_t<std::is_convertible<
              typename std::iterator_traits<ItTy>::iterator_category,
              std::input_iterator_tag>::value>>
iterator insert(iterator I, ItTy From, ItTy To) {
  // Convert iterator to elt# to avoid invalidating iterator when we reserve()
  size_t InsertElt = I - this->begin();

  if (I == this->end()) {  // Important special case for empty vector.
    append(From, To);
    return this->begin()+InsertElt;
  }

  assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")(static_cast <bool> (this->isReferenceToStorage(I) &&
 "Insertion iterator is out of bounds.") ? void (0) : __assert_fail
 ("this->isReferenceToStorage(I) && \"Insertion iterator is out of bounds.\""
, "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/llvm/include/llvm/ADT/SmallVector.h"
, 855, __extension__ __PRETTY_FUNCTION__));

  // Check that the reserve that follows doesn't invalidate the iterators.
  this->assertSafeToAddRange(From, To);

  size_t NumToInsert = std::distance(From, To);

  // Ensure there is enough space.
  reserve(this->size() + NumToInsert);

  // Uninvalidate the iterator.
  I = this->begin()+InsertElt;

  // If there are more elements between the insertion point and the end of the
  // range than there are being inserted, we can use a simple approach to
  // insertion.  Since we already reserved space, we know that this won't
  // reallocate the vector.
  if (size_t(this->end()-I) >= NumToInsert) {
    T *OldEnd = this->end();
    append(std::move_iterator<iterator>(this->end() - NumToInsert),
           std::move_iterator<iterator>(this->end()));

    // Copy the existing elements that get replaced.
    std::move_backward(I, OldEnd-NumToInsert, OldEnd);

    std::copy(From, To, I);
    return I;
  }

  // Otherwise, we're inserting more elements than exist already, and we're
  // not inserting at the end.

  // Move over the elements that we're about to overwrite.
  T *OldEnd = this->end();
  this->set_size(this->size() + NumToInsert);
  size_t NumOverwritten = OldEnd-I;
  this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);

  // Replace the overwritten part.
  for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
    *J = *From;
    ++J; ++From;
  }

  // Insert the non-overwritten middle part.
  this->uninitialized_copy(From, To, OldEnd);
  return I;
}

void insert(iterator I, std::initializer_list<T> IL) {
  insert(I, IL.begin(), IL.end());
}

template <typename... ArgTypes> reference emplace_back(ArgTypes &&... Args) {
  if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity
()), false))
    return this->growAndEmplaceBack(std::forward<ArgTypes>(Args)...);

  ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
  this->set_size(this->size() + 1);
  return this->back();
}

SmallVectorImpl &operator=(const SmallVectorImpl &RHS);

SmallVectorImpl &operator=(SmallVectorImpl &&RHS);

bool operator==(const SmallVectorImpl &RHS) const {
  if (this->size() != RHS.size()) return false;
  return std::equal(this->begin(), this->end(), RHS.begin());
}
bool operator!=(const SmallVectorImpl &RHS) const {
  return !(*this == RHS);
}

bool operator<(const SmallVectorImpl &RHS) const {
  return std::lexicographical_compare(this->begin(), this->end(),
                                      RHS.begin(), RHS.end());
}
933};

935template <typename T>
936void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
if (this == &RHS) return;

// We can only avoid copying elements if neither vector is small.
if (!this->isSmall() && !RHS.isSmall()) {
  std::swap(this->BeginX, RHS.BeginX);
  std::swap(this->Size, RHS.Size);
  std::swap(this->Capacity, RHS.Capacity);
  return;
}
this->reserve(RHS.size());
RHS.reserve(this->size());

// Swap the shared elements.
size_t NumShared = this->size();
if (NumShared > RHS.size()) NumShared = RHS.size();
for (size_type i = 0; i != NumShared; ++i)
  std::swap((*this)[i], RHS[i]);

// Copy over the extra elts.
if (this->size() > RHS.size()) {
  size_t EltDiff = this->size() - RHS.size();
  this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
  RHS.set_size(RHS.size() + EltDiff);
  this->destroy_range(this->begin()+NumShared, this->end());
  this->set_size(NumShared);
} else if (RHS.size() > this->size()) {
  size_t EltDiff = RHS.size() - this->size();
  this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
  this->set_size(this->size() + EltDiff);
  this->destroy_range(RHS.begin()+NumShared, RHS.end());
  RHS.set_size(NumShared);
}
969}

971template <typename T>
972SmallVectorImpl<T> &SmallVectorImpl<T>::
operator=(const SmallVectorImpl<T> &RHS) {
// Avoid self-assignment.
if (this == &RHS) return *this;

// If we already have sufficient space, assign the common elements, then
// destroy any excess.
size_t RHSSize = RHS.size();
size_t CurSize = this->size();
if (CurSize >= RHSSize) {
  // Assign common elements.
  iterator NewEnd;
  if (RHSSize)
    NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
  else
    NewEnd = this->begin();

  // Destroy excess elements.
  this->destroy_range(NewEnd, this->end());

  // Trim.
  this->set_size(RHSSize);
  return *this;
}

// If we have to grow to have enough elements, destroy the current elements.
// This allows us to avoid copying them during the grow.
// FIXME: don't do this if they're efficiently moveable.
if (this->capacity() < RHSSize) {
  // Destroy current elements.
  this->clear();
  CurSize = 0;
  this->grow(RHSSize);
} else if (CurSize) {
  // Otherwise, use assignment for the already-constructed elements.
  std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
}

// Copy construct the new elements in place.
this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
                         this->begin()+CurSize);

// Set end.
this->set_size(RHSSize);
return *this;
1017}

1019template <typename T>
1020SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
// Avoid self-assignment.
if (this == &RHS) return *this;

// If the RHS isn't small, clear this vector and then steal its buffer.
if (!RHS.isSmall()) {
  this->destroy_range(this->begin(), this->end());
  if (!this->isSmall()) free(this->begin());
  this->BeginX = RHS.BeginX;
  this->Size = RHS.Size;
  this->Capacity = RHS.Capacity;
  RHS.resetToSmall();
  return *this;
}

// If we already have sufficient space, assign the common elements, then
// destroy any excess.
size_t RHSSize = RHS.size();
size_t CurSize = this->size();
if (CurSize >= RHSSize) {
  // Assign common elements.
  iterator NewEnd = this->begin();
  if (RHSSize)
    NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);

  // Destroy excess elements and trim the bounds.
  this->destroy_range(NewEnd, this->end());
  this->set_size(RHSSize);

  // Clear the RHS.
  RHS.clear();

  return *this;
}

// If we have to grow to have enough elements, destroy the current elements.
// This allows us to avoid copying them during the grow.
// FIXME: this may not actually make any sense if we can efficiently move
// elements.
if (this->capacity() < RHSSize) {
  // Destroy current elements.
  this->clear();
  CurSize = 0;
  this->grow(RHSSize);
} else if (CurSize) {
  // Otherwise, use assignment for the already-constructed elements.
  std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
}

// Move-construct the new elements in place.
this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
                         this->begin()+CurSize);

// Set end.
this->set_size(RHSSize);

RHS.clear();
return *this;
1078}

1080/// Storage for the SmallVector elements.  This is specialized for the N=0 case
1081/// to avoid allocating unnecessary storage.
1082template <typename T, unsigned N>
1083struct SmallVectorStorage {
alignas(T) char InlineElts[N * sizeof(T)];
1085};

1087/// We need the storage to be properly aligned even for small-size of 0 so that
1088/// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
1089/// well-defined.
1090template <typename T> struct alignas(T) SmallVectorStorage<T, 0> {};

1092/// Forward declaration of SmallVector so that
1093/// calculateSmallVectorDefaultInlinedElements can reference
1094/// `sizeof(SmallVector<T, 0>)`.
1095template <typename T, unsigned N> class LLVM_GSL_OWNER[[gsl::Owner]] SmallVector;

1097/// Helper class for calculating the default number of inline elements for
1098/// `SmallVector<T>`.
1099///
1100/// This should be migrated to a constexpr function when our minimum
1101/// compiler support is enough for multi-statement constexpr functions.
1102template <typename T> struct CalculateSmallVectorDefaultInlinedElements {
// Parameter controlling the default number of inlined elements
// for `SmallVector<T>`.
//
// The default number of inlined elements ensures that
// 1. There is at least one inlined element.
// 2. `sizeof(SmallVector<T>) <= kPreferredSmallVectorSizeof` unless
// it contradicts 1.
static constexpr size_t kPreferredSmallVectorSizeof = 64;

// static_assert that sizeof(T) is not "too big".
//
// Because our policy guarantees at least one inlined element, it is possible
// for an arbitrarily large inlined element to allocate an arbitrarily large
// amount of inline storage. We generally consider it an antipattern for a
// SmallVector to allocate an excessive amount of inline storage, so we want
// to call attention to these cases and make sure that users are making an
// intentional decision if they request a lot of inline storage.
//
// We want this assertion to trigger in pathological cases, but otherwise
// not be too easy to hit. To accomplish that, the cutoff is actually somewhat
// larger than kPreferredSmallVectorSizeof (otherwise,
// `SmallVector<SmallVector<T>>` would be one easy way to trip it, and that
// pattern seems useful in practice).
//
// One wrinkle is that this assertion is in theory non-portable, since
// sizeof(T) is in general platform-dependent. However, we don't expect this
// to be much of an issue, because most LLVM development happens on 64-bit
// hosts, and therefore sizeof(T) is expected to *decrease* when compiled for
// 32-bit hosts, dodging the issue. The reverse situation, where development
// happens on a 32-bit host and then fails due to sizeof(T) *increasing* on a
// 64-bit host, is expected to be very rare.
static_assert(
    sizeof(T) <= 256,
    "You are trying to use a default number of inlined elements for "
    "`SmallVector<T>` but `sizeof(T)` is really big! Please use an "
    "explicit number of inlined elements with `SmallVector<T, N>` to make "
    "sure you really want that much inline storage.");

// Discount the size of the header itself when calculating the maximum inline
// bytes.
static constexpr size_t PreferredInlineBytes =
    kPreferredSmallVectorSizeof - sizeof(SmallVector<T, 0>);
static constexpr size_t NumElementsThatFit = PreferredInlineBytes / sizeof(T);
static constexpr size_t value =
    NumElementsThatFit == 0 ? 1 : NumElementsThatFit;
1148};

1150/// This is a 'vector' (really, a variable-sized array), optimized
1151/// for the case when the array is small.  It contains some number of elements
1152/// in-place, which allows it to avoid heap allocation when the actual number of
1153/// elements is below that threshold.  This allows normal "small" cases to be
1154/// fast without losing generality for large inputs.
1155///
1156/// \note
1157/// In the absence of a well-motivated choice for the number of inlined
1158/// elements \p N, it is recommended to use \c SmallVector<T> (that is,
1159/// omitting the \p N). This will choose a default number of inlined elements
1160/// reasonable for allocation on the stack (for example, trying to keep \c
1161/// sizeof(SmallVector<T>) around 64 bytes).
1162///
1163/// \warning This does not attempt to be exception safe.
1164///
1165/// \see https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h
1166template <typename T,
        unsigned N = CalculateSmallVectorDefaultInlinedElements<T>::value>
1168class LLVM_GSL_OWNER[[gsl::Owner]] SmallVector : public SmallVectorImpl<T>,
                                 SmallVectorStorage<T, N> {
1170public:
SmallVector() : SmallVectorImpl<T>(N) {}

~SmallVector() {
  // Destroy the constructed elements in the vector.
  this->destroy_range(this->begin(), this->end());
}

explicit SmallVector(size_t Size, const T &Value = T())
  : SmallVectorImpl<T>(N) {
  this->assign(Size, Value);
}

template <typename ItTy,
          typename = std::enable_if_t<std::is_convertible<
              typename std::iterator_traits<ItTy>::iterator_category,
              std::input_iterator_tag>::value>>
SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
  this->append(S, E);
}

template <typename RangeTy>
explicit SmallVector(const iterator_range<RangeTy> &R)
    : SmallVectorImpl<T>(N) {
  this->append(R.begin(), R.end());
}

SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
  this->assign(IL);
}

SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
  if (!RHS.empty())
    SmallVectorImpl<T>::operator=(RHS);
}

SmallVector &operator=(const SmallVector &RHS) {
  SmallVectorImpl<T>::operator=(RHS);
  return *this;
}

SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
  if (!RHS.empty())
    SmallVectorImpl<T>::operator=(::std::move(RHS));
}

SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {
  if (!RHS.empty())
    SmallVectorImpl<T>::operator=(::std::move(RHS));
}

SmallVector &operator=(SmallVector &&RHS) {
  SmallVectorImpl<T>::operator=(::std::move(RHS));
  return *this;
}

SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
  SmallVectorImpl<T>::operator=(::std::move(RHS));
  return *this;
}

SmallVector &operator=(std::initializer_list<T> IL) {
  this->assign(IL);
  return *this;
}
1235};

1237template <typename T, unsigned N>
1238inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
return X.capacity_in_bytes();
1240}

1242/// Given a range of type R, iterate the entire range and return a
1243/// SmallVector with elements of the vector.  This is useful, for example,
1244/// when you want to iterate a range and then sort the results.
1245template <unsigned Size, typename R>
1246SmallVector<typename std::remove_const<typename std::remove_reference<
              decltype(*std::begin(std::declval<R &>()))>::type>::type,
          Size>
1249to_vector(R &&Range) {
return {std::begin(Range), std::end(Range)};
1251}

1253} // end namespace llvm

1255namespace std {

/// Implement std::swap in terms of SmallVector swap.
template<typename T>
inline void
swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
  LHS.swap(RHS);
}

/// Implement std::swap in terms of SmallVector swap.
template<typename T, unsigned N>
inline void
swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
  LHS.swap(RHS);
}

1271} // end namespace std

1273#endif // LLVM_ADT_SMALLVECTOR_H