/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Transforms/IPO/GlobalOpt.cpp

Bug Summary

File:	llvm/lib/Transforms/IPO/GlobalOpt.cpp
Warning:	line 1885, column 27 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~++20210903100615+fd66b44ec19e/build-llvm/lib/Transforms/IPO -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Transforms/IPO -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Transforms/IPO -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include -D NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/Transforms/IPO -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-09-04-040900-46481-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/Transforms/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<void> (0));
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<void> (0))
                                         Instruction::GetElementPtr) ||(static_cast<void> (0))
          isa<GetElementPtrInst>(GEP)) &&(static_cast<void> (0))
         "NonGEP CE's are not SRAable!")(static_cast<void> (0));

  // 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<void> (0));

  Type *ElTy = nullptr;
  if (StructType *STy = dyn_cast<StructType>(Ty))
    ElTy = STy->getElementType(ElementIdx);
  else
    ElTy = GetSRASequentialElementType(Ty);
  assert(ElTy)(static_cast<void> (0));

  Constant *In = Init->getAggregateElement(ElementIdx);
  assert(In && "Couldn't get element of initializer?")(static_cast<void> (0));

  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 { } 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<void> (0))
           cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)||(static_cast<void> (0))
          isa<GetElementPtrInst>(GEP)) && "NonGEP CE's are not SRAable!")(static_cast<void> (0));

  // 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<void> (0));

  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<void> (0));
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<void> (0))
                                ->getPointerOperand()(static_cast<void> (0))
                                ->stripPointerCasts()) &&(static_cast<void> (0))
           "Should be GlobalVariable")(static_cast<void> (0));
    // 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<void> (0))
           "Expect only load or store instructions")(static_cast<void> (0));
    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<void> (0))
           "Must be storing *to* the global")(static_cast<void> (0));
  } 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<void> (0))
            isa<ConstantExpr>(GlobalUser) || isa<CmpInst>(GlobalUser) ||(static_cast<void> (0))
            isa<BitCastInst>(GlobalUser) ||(static_cast<void> (0))
            isa<GetElementPtrInst>(GlobalUser)) &&(static_cast<void> (0))
           "Only expect load and stores!")(static_cast<void> (0));
  }
}

if (Changed) {
  LLVM_DEBUG(dbgs() << "OPTIMIZED LOADS FROM STORED ONCE POINTER: " << *GVdo { } while (false)
                    << "\n")do { } 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 { } 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 { } while (false)
                  << '\n')do { } 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!")__builtin_unreachable();
    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 { } 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<void> (0))
       "No reason to shrink to bool!")(static_cast<void> (0));

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<void> (0));
        // 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<void> (0))
               "This is not a form that we understand!")(static_cast<void> (0));
        StoreVal = StoredVal->getOperand(0);
        assert(isa<LoadInst>(StoreVal) && "Not a load of NewGV!")(static_cast<void> (0));
      }
    }
    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 { } 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<void> (0));

  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<void> (0))
        isa<Instruction>(U) &&(static_cast<void> (0))
        "Can't transform non-constantexpr non-instruction to instruction!")(static_cast<void> (0));
}

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 { } 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 { } 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 { } 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<void> (0));
    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 { } while (false)
                      << "all users and delete global!\n")do { } 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 { } while (false)
                        << "simplify all users and delete global!\n")do { } 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.removeAttributeAtIndex(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<void> (0))
           "Expected either CallBase or BlockAddress")(static_cast<void> (0));
    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) {
20
←
Assuming '__begin1' is not equal to '__end1'→
  CallBase *CB = dyn_cast<CallBase>(U);
21
←
Assuming 'U' is a 'CallBase'→
  if (!CB21.1
'CB' is non-null
)
22
←
Taking false branch→
    continue;

  assert((static_cast<void> (0))
      !CB->isMustTailCall() &&(static_cast<void> (0))
      "Shouldn't call RemotePreallocated() on a musttail preallocated call")(static_cast<void> (0));
  // Create copy of call without "preallocated" operand bundle.
  SmallVector<OperandBundleDef, 1> OpBundles;
  CB->getOperandBundlesAsDefs(OpBundles);
  CallBase *PreallocatedSetup = nullptr;
23
←
'PreallocatedSetup' initialized to a null pointer value→
  for (auto *It = OpBundles.begin(); It != OpBundles.end(); ++It) {
24
←
Assuming the condition is false→
25
←
Loop condition is false. Execution continues on line 1883→
    if (It->getTag() == "preallocated") {
      PreallocatedSetup = cast<CallBase>(*It->input_begin());
      OpBundles.erase(It);
      break;
    }
  }
  assert(PreallocatedSetup && "Did not find preallocated bundle")(static_cast<void> (0));
  uint64_t ArgCount =
      cast<ConstantInt>(PreallocatedSetup->getArgOperand(0))->getZExtValue();
26
←
Called C++ object pointer is null

  assert((isa<CallInst>(CB) || isa<InvokeInst>(CB)) &&(static_cast<void> (0))
         "Unknown indirect call type")(static_cast<void> (0));
  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<void> (0))
               Intrinsic::call_preallocated_arg &&(static_cast<void> (0))
           "preallocated token use was not a llvm.call.preallocated.arg")(static_cast<void> (0));
    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;) {
6
←
Loop condition is false. Execution continues on line 1959→
  Function *F = &*FI++;
  if (hasOnlyColdCalls(*F, GetBFI))
    AllCallsCold.push_back(F);
}

// Optimize functions.
for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) {
7
←
Loop condition is true.  Entering loop body→
  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))
8
←
Assuming the condition is false→
    continue;

  // Functions without names cannot be referenced outside this module.
  if (!F->hasName() && !F->isDeclaration() && !F->hasLocalLinkage())
9
←
Assuming the condition is false→
    F->setLinkage(GlobalValue::InternalLinkage);

  if (deleteIfDead(*F, NotDiscardableComdats)) {
10
←
Taking false branch→
    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()) {
11
←
Assuming the condition is false→
12
←
Taking false branch→
    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) &&
13
←
Assuming the condition is false→
14
←
Taking false branch→
      !F->hasAddressTaken() && !hasMustTailCallers(F)) {
    RemoveAttribute(F, Attribute::InAlloca);
    Changed = true;
  }

  // FIXME: handle invokes
  // FIXME: handle musttail
  if (F->getAttributes().hasAttrSomewhere(Attribute::Preallocated)) {
15
←
Assuming the condition is true→
    if (!F->hasAddressTaken() && !hasMustTailCallers(F) &&
16
←
Assuming the condition is true→
18
←
Taking true branch→
        !hasInvokeCallers(F)) {
17
←
Assuming the condition is true→
      RemovePreallocated(F);
19
←
Calling 'RemovePreallocated'→
      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<void> (0));
  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<void> (0));
  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<void> (0));
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<void> (0));
  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)
  CommitValueTo(ComplexCE.second, ComplexCE.first);

for (auto GVPair : GVs) {
  assert(GVPair.first->hasInitializer())(static_cast<void> (0));
  GVPair.first->setInitializer(GVPair.second);
}

if (SimpleCEs.empty())
  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;

auto commitAndSetupCache = [&](GlobalVariable *GV, bool Update) {
  Constant *Init = GV->getInitializer();
  Type *Ty = Init->getType();
  if (Update) {
    if (CurrentGV) {
      assert(CurrentGV && "Expected a GV to commit to!")(static_cast<void> (0));
      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) {
  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);
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) {
  ++NumCtorsEvaluated;

  // We succeeded at evaluation: commit the result.
  LLVM_DEBUG(dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '"do { } while (false)
                    << F->getName() << "' to "do { } while (false)
                    << Eval.getMutatedMemory().size() << " stores.\n")do { } while (false);
  BatchCommitValueTo(Eval.getMutatedMemory());
  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<void> (0))
       "We should have removed the duplicated "(static_cast<void> (0))
       "element from llvm.compiler.used")(static_cast<void> (0));
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<void> (0))
       "We should have removed the duplicated "(static_cast<void> (0))
       "element from llvm.compiler.used")(static_cast<void> (0));
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) {
4
←
Loop condition is true.  Entering loop body→
  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,
5
←
Calling 'OptimizeFunctions'→
                                   NotDiscardableComdats);

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

  // 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))
1
Assuming the condition is false→
2
←
Taking false branch→
    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,
3
←
Calling 'optimizeGlobalsInModule'→
                                 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}