/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/polly/lib/CodeGen/BlockGenerators.cpp

Bug Summary

File:	polly/lib/CodeGen/BlockGenerators.cpp
Warning:	line 1164, column 40 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 BlockGenerators.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/tools/polly/lib -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/tools/polly/lib -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/polly/lib -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/tools/polly/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/polly/lib/External -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/polly/lib/External/pet/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/polly/include -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 -Wno-long-long -Wno-unused-parameter -Wwrite-strings -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/tools/polly/lib -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fno-rtti -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/polly/lib/CodeGen/BlockGenerators.cpp

/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/polly/lib/CodeGen/BlockGenerators.cpp

→

1//===--- BlockGenerators.cpp - Generate code for statements -----*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the BlockGenerator and VectorBlockGenerator classes,
10// which generate sequential code and vectorized code for a polyhedral
11// statement, respectively.
12//
13//===----------------------------------------------------------------------===//

15#include "polly/CodeGen/BlockGenerators.h"
16#include "polly/CodeGen/IslExprBuilder.h"
17#include "polly/CodeGen/RuntimeDebugBuilder.h"
18#include "polly/Options.h"
19#include "polly/ScopInfo.h"
20#include "polly/Support/ScopHelper.h"
21#include "polly/Support/VirtualInstruction.h"
22#include "llvm/Analysis/LoopInfo.h"
23#include "llvm/Analysis/RegionInfo.h"
24#include "llvm/Analysis/ScalarEvolution.h"
25#include "llvm/Transforms/Utils/BasicBlockUtils.h"
26#include "llvm/Transforms/Utils/Local.h"
27#include "isl/ast.h"
28#include <deque>

30using namespace llvm;
31using namespace polly;

33static cl::opt<bool> Aligned("enable-polly-aligned",
                           cl::desc("Assumed aligned memory accesses."),
                           cl::Hidden, cl::init(false), cl::ZeroOrMore,
                           cl::cat(PollyCategory));

38bool PollyDebugPrinting;
39static cl::opt<bool, true> DebugPrintingX(
  "polly-codegen-add-debug-printing",
  cl::desc("Add printf calls that show the values loaded/stored."),
  cl::location(PollyDebugPrinting), cl::Hidden, cl::init(false),
  cl::ZeroOrMore, cl::cat(PollyCategory));

45static cl::opt<bool> TraceStmts(
  "polly-codegen-trace-stmts",
  cl::desc("Add printf calls that print the statement being executed"),
  cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));

50static cl::opt<bool> TraceScalars(
  "polly-codegen-trace-scalars",
  cl::desc("Add printf calls that print the values of all scalar values "
           "used in a statement. Requires -polly-codegen-trace-stmts."),
  cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));

56BlockGenerator::BlockGenerator(
  PollyIRBuilder &B, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT,
  AllocaMapTy &ScalarMap, EscapeUsersAllocaMapTy &EscapeMap,
  ValueMapT &GlobalMap, IslExprBuilder *ExprBuilder, BasicBlock *StartBlock)
  : Builder(B), LI(LI), SE(SE), ExprBuilder(ExprBuilder), DT(DT),
    EntryBB(nullptr), ScalarMap(ScalarMap), EscapeMap(EscapeMap),
    GlobalMap(GlobalMap), StartBlock(StartBlock) {}

64Value *BlockGenerator::trySynthesizeNewValue(ScopStmt &Stmt, Value *Old,
                                           ValueMapT &BBMap,
                                           LoopToScevMapT &LTS,
                                           Loop *L) const {
if (!SE.isSCEVable(Old->getType()))
  return nullptr;

const SCEV *Scev = SE.getSCEVAtScope(Old, L);
if (!Scev)
  return nullptr;

if (isa<SCEVCouldNotCompute>(Scev))
  return nullptr;

const SCEV *NewScev = SCEVLoopAddRecRewriter::rewrite(Scev, LTS, SE);
ValueMapT VTV;
VTV.insert(BBMap.begin(), BBMap.end());
VTV.insert(GlobalMap.begin(), GlobalMap.end());

Scop &S = *Stmt.getParent();
const DataLayout &DL = S.getFunction().getParent()->getDataLayout();
auto IP = Builder.GetInsertPoint();

assert(IP != Builder.GetInsertBlock()->end() &&(static_cast<void> (0))
       "Only instructions can be insert points for SCEVExpander")(static_cast<void> (0));
Value *Expanded =
    expandCodeFor(S, SE, DL, "polly", NewScev, Old->getType(), &*IP, &VTV,
                  StartBlock->getSinglePredecessor());

BBMap[Old] = Expanded;
return Expanded;
95}

97Value *BlockGenerator::getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap,
                                 LoopToScevMapT &LTS, Loop *L) const {

auto lookupGlobally = [this](Value *Old) -> Value * {
  Value *New = GlobalMap.lookup(Old);
  if (!New)
    return nullptr;

  // Required by:
  // * Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded.ll
  // * Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded_different_bb.ll
  // * Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded_pass_only_needed.ll
  // * Isl/CodeGen/OpenMP/invariant_base_pointers_preloaded.ll
  // * Isl/CodeGen/OpenMP/loop-body-references-outer-values-3.ll
  // * Isl/CodeGen/OpenMP/single_loop_with_loop_invariant_baseptr.ll
  // GlobalMap should be a mapping from (value in original SCoP) to (copied
  // value in generated SCoP), without intermediate mappings, which might
  // easily require transitiveness as well.
  if (Value *NewRemapped = GlobalMap.lookup(New))
    New = NewRemapped;

  // No test case for this code.
  if (Old->getType()->getScalarSizeInBits() <
      New->getType()->getScalarSizeInBits())
    New = Builder.CreateTruncOrBitCast(New, Old->getType());

  return New;
};

Value *New = nullptr;
auto VUse = VirtualUse::create(&Stmt, L, Old, true);
switch (VUse.getKind()) {
case VirtualUse::Block:
  // BasicBlock are constants, but the BlockGenerator copies them.
  New = BBMap.lookup(Old);
  break;

case VirtualUse::Constant:
  // Used by:
  // * Isl/CodeGen/OpenMP/reference-argument-from-non-affine-region.ll
  // Constants should not be redefined. In this case, the GlobalMap just
  // contains a mapping to the same constant, which is unnecessary, but
  // harmless.
  if ((New = lookupGlobally(Old)))
    break;

  assert(!BBMap.count(Old))(static_cast<void> (0));
  New = Old;
  break;

case VirtualUse::ReadOnly:
  assert(!GlobalMap.count(Old))(static_cast<void> (0));

  // Required for:
  // * Isl/CodeGen/MemAccess/create_arrays.ll
  // * Isl/CodeGen/read-only-scalars.ll
  // * ScheduleOptimizer/pattern-matching-based-opts_10.ll
  // For some reason these reload a read-only value. The reloaded value ends
  // up in BBMap, buts its value should be identical.
  //
  // Required for:
  // * Isl/CodeGen/OpenMP/single_loop_with_param.ll
  // The parallel subfunctions need to reference the read-only value from the
  // parent function, this is done by reloading them locally.
  if ((New = BBMap.lookup(Old)))
    break;

  New = Old;
  break;

case VirtualUse::Synthesizable:
  // Used by:
  // * Isl/CodeGen/OpenMP/loop-body-references-outer-values-3.ll
  // * Isl/CodeGen/OpenMP/recomputed-srem.ll
  // * Isl/CodeGen/OpenMP/reference-other-bb.ll
  // * Isl/CodeGen/OpenMP/two-parallel-loops-reference-outer-indvar.ll
  // For some reason synthesizable values end up in GlobalMap. Their values
  // are the same as trySynthesizeNewValue would return. The legacy
  // implementation prioritized GlobalMap, so this is what we do here as well.
  // Ideally, synthesizable values should not end up in GlobalMap.
  if ((New = lookupGlobally(Old)))
    break;

  // Required for:
  // * Isl/CodeGen/RuntimeDebugBuilder/combine_different_values.ll
  // * Isl/CodeGen/getNumberOfIterations.ll
  // * Isl/CodeGen/non_affine_float_compare.ll
  // * ScheduleOptimizer/pattern-matching-based-opts_10.ll
  // Ideally, synthesizable values are synthesized by trySynthesizeNewValue,
  // not precomputed (SCEVExpander has its own caching mechanism).
  // These tests fail without this, but I think trySynthesizeNewValue would
  // just re-synthesize the same instructions.
  if ((New = BBMap.lookup(Old)))
    break;

  New = trySynthesizeNewValue(Stmt, Old, BBMap, LTS, L);
  break;

case VirtualUse::Hoisted:
  // TODO: Hoisted invariant loads should be found in GlobalMap only, but not
  // redefined locally (which will be ignored anyway). That is, the following
  // assertion should apply: assert(!BBMap.count(Old))

  New = lookupGlobally(Old);
  break;

case VirtualUse::Intra:
case VirtualUse::Inter:
  assert(!GlobalMap.count(Old) &&(static_cast<void> (0))
         "Intra and inter-stmt values are never global")(static_cast<void> (0));
  New = BBMap.lookup(Old);
  break;
}
assert(New && "Unexpected scalar dependence in region!")(static_cast<void> (0));
return New;
212}

214void BlockGenerator::copyInstScalar(ScopStmt &Stmt, Instruction *Inst,
                                  ValueMapT &BBMap, LoopToScevMapT &LTS) {
// We do not generate debug intrinsics as we did not investigate how to
// copy them correctly. At the current state, they just crash the code
// generation as the meta-data operands are not correctly copied.
if (isa<DbgInfoIntrinsic>(Inst))
  return;

Instruction *NewInst = Inst->clone();

// Replace old operands with the new ones.
for (Value *OldOperand : Inst->operands()) {
  Value *NewOperand =
      getNewValue(Stmt, OldOperand, BBMap, LTS, getLoopForStmt(Stmt));

  if (!NewOperand) {
    assert(!isa<StoreInst>(NewInst) &&(static_cast<void> (0))
           "Store instructions are always needed!")(static_cast<void> (0));
    NewInst->deleteValue();
    return;
  }

  NewInst->replaceUsesOfWith(OldOperand, NewOperand);
}

Builder.Insert(NewInst);
BBMap[Inst] = NewInst;

// When copying the instruction onto the Module meant for the GPU,
// debug metadata attached to an instruction causes all related
// metadata to be pulled into the Module. This includes the DICompileUnit,
// which will not be listed in llvm.dbg.cu of the Module since the Module
// doesn't contain one. This fails the verification of the Module and the
// subsequent generation of the ASM string.
if (NewInst->getModule() != Inst->getModule())
  NewInst->setDebugLoc(llvm::DebugLoc());

if (!NewInst->getType()->isVoidTy())
  NewInst->setName("p_" + Inst->getName());
253}

255Value *
256BlockGenerator::generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst,
                                       ValueMapT &BBMap, LoopToScevMapT &LTS,
                                       isl_id_to_ast_expr *NewAccesses) {
const MemoryAccess &MA = Stmt.getArrayAccessFor(Inst);
return generateLocationAccessed(
    Stmt, getLoopForStmt(Stmt),
    Inst.isNull() ? nullptr : Inst.getPointerOperand(), BBMap, LTS,
    NewAccesses, MA.getId().release(), MA.getAccessValue()->getType());
264}

266Value *BlockGenerator::generateLocationAccessed(
  ScopStmt &Stmt, Loop *L, Value *Pointer, ValueMapT &BBMap,
  LoopToScevMapT &LTS, isl_id_to_ast_expr *NewAccesses, __isl_take isl_id *Id,
  Type *ExpectedType) {
isl_ast_expr *AccessExpr = isl_id_to_ast_expr_get(NewAccesses, Id);

if (AccessExpr) {
  AccessExpr = isl_ast_expr_address_of(AccessExpr);
  auto Address = ExprBuilder->create(AccessExpr);

  // Cast the address of this memory access to a pointer type that has the
  // same element type as the original access, but uses the address space of
  // the newly generated pointer.
  auto OldPtrTy = ExpectedType->getPointerTo();
  auto NewPtrTy = Address->getType();
  OldPtrTy = PointerType::getWithSamePointeeType(
      OldPtrTy, NewPtrTy->getPointerAddressSpace());

  if (OldPtrTy != NewPtrTy)
    Address = Builder.CreateBitOrPointerCast(Address, OldPtrTy);
  return Address;
}
assert((static_cast<void> (0))
    Pointer &&(static_cast<void> (0))
    "If expression was not generated, must use the original pointer value")(static_cast<void> (0));
return getNewValue(Stmt, Pointer, BBMap, LTS, L);
292}

294Value *
295BlockGenerator::getImplicitAddress(MemoryAccess &Access, Loop *L,
                                 LoopToScevMapT &LTS, ValueMapT &BBMap,
                                 __isl_keep isl_id_to_ast_expr *NewAccesses) {
if (Access.isLatestArrayKind())
  return generateLocationAccessed(*Access.getStatement(), L, nullptr, BBMap,
                                  LTS, NewAccesses, Access.getId().release(),
                                  Access.getAccessValue()->getType());

return getOrCreateAlloca(Access);
304}

306Loop *BlockGenerator::getLoopForStmt(const ScopStmt &Stmt) const {
auto *StmtBB = Stmt.getEntryBlock();
return LI.getLoopFor(StmtBB);
309}

311Value *BlockGenerator::generateArrayLoad(ScopStmt &Stmt, LoadInst *Load,
                                       ValueMapT &BBMap, LoopToScevMapT &LTS,
                                       isl_id_to_ast_expr *NewAccesses) {
if (Value *PreloadLoad = GlobalMap.lookup(Load))
  return PreloadLoad;

Value *NewPointer =
    generateLocationAccessed(Stmt, Load, BBMap, LTS, NewAccesses);
Value *ScalarLoad =
    Builder.CreateAlignedLoad(Load->getType(), NewPointer, Load->getAlign(),
                              Load->getName() + "_p_scalar_");

if (PollyDebugPrinting)
  RuntimeDebugBuilder::createCPUPrinter(Builder, "Load from ", NewPointer,
                                        ": ", ScalarLoad, "\n");

return ScalarLoad;
328}

330void BlockGenerator::generateArrayStore(ScopStmt &Stmt, StoreInst *Store,
                                      ValueMapT &BBMap, LoopToScevMapT &LTS,
                                      isl_id_to_ast_expr *NewAccesses) {
MemoryAccess &MA = Stmt.getArrayAccessFor(Store);
isl::set AccDom = MA.getAccessRelation().domain();
std::string Subject = MA.getId().get_name();

generateConditionalExecution(Stmt, AccDom, Subject.c_str(), [&, this]() {
  Value *NewPointer =
      generateLocationAccessed(Stmt, Store, BBMap, LTS, NewAccesses);
  Value *ValueOperand = getNewValue(Stmt, Store->getValueOperand(), BBMap,
                                    LTS, getLoopForStmt(Stmt));

  if (PollyDebugPrinting)
    RuntimeDebugBuilder::createCPUPrinter(Builder, "Store to  ", NewPointer,
                                          ": ", ValueOperand, "\n");

  Builder.CreateAlignedStore(ValueOperand, NewPointer, Store->getAlign());
});
349}

351bool BlockGenerator::canSyntheziseInStmt(ScopStmt &Stmt, Instruction *Inst) {
Loop *L = getLoopForStmt(Stmt);
return (Stmt.isBlockStmt() || !Stmt.getRegion()->contains(L)) &&
       canSynthesize(Inst, *Stmt.getParent(), &SE, L);
355}

357void BlockGenerator::copyInstruction(ScopStmt &Stmt, Instruction *Inst,
                                   ValueMapT &BBMap, LoopToScevMapT &LTS,
                                   isl_id_to_ast_expr *NewAccesses) {
// Terminator instructions control the control flow. They are explicitly
// expressed in the clast and do not need to be copied.
if (Inst->isTerminator())
  return;

// Synthesizable statements will be generated on-demand.
if (canSyntheziseInStmt(Stmt, Inst))
  return;

if (auto *Load = dyn_cast<LoadInst>(Inst)) {
  Value *NewLoad = generateArrayLoad(Stmt, Load, BBMap, LTS, NewAccesses);
  // Compute NewLoad before its insertion in BBMap to make the insertion
  // deterministic.
  BBMap[Load] = NewLoad;
  return;
}

if (auto *Store = dyn_cast<StoreInst>(Inst)) {
  // Identified as redundant by -polly-simplify.
  if (!Stmt.getArrayAccessOrNULLFor(Store))
    return;

  generateArrayStore(Stmt, Store, BBMap, LTS, NewAccesses);
  return;
}

if (auto *PHI = dyn_cast<PHINode>(Inst)) {
  copyPHIInstruction(Stmt, PHI, BBMap, LTS);
  return;
}

// Skip some special intrinsics for which we do not adjust the semantics to
// the new schedule. All others are handled like every other instruction.
if (isIgnoredIntrinsic(Inst))
  return;

copyInstScalar(Stmt, Inst, BBMap, LTS);
397}

399void BlockGenerator::removeDeadInstructions(BasicBlock *BB, ValueMapT &BBMap) {
auto NewBB = Builder.GetInsertBlock();
for (auto I = NewBB->rbegin(); I != NewBB->rend(); I++) {
  Instruction *NewInst = &*I;

  if (!isInstructionTriviallyDead(NewInst))
    continue;

  for (auto Pair : BBMap)
    if (Pair.second == NewInst) {
      BBMap.erase(Pair.first);
    }

  NewInst->eraseFromParent();
  I = NewBB->rbegin();
}
415}

417void BlockGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
                            isl_id_to_ast_expr *NewAccesses) {
assert(Stmt.isBlockStmt() &&(static_cast<void> (0))
       "Only block statements can be copied by the block generator")(static_cast<void> (0));

ValueMapT BBMap;

BasicBlock *BB = Stmt.getBasicBlock();
copyBB(Stmt, BB, BBMap, LTS, NewAccesses);
removeDeadInstructions(BB, BBMap);
427}

429BasicBlock *BlockGenerator::splitBB(BasicBlock *BB) {
BasicBlock *CopyBB = SplitBlock(Builder.GetInsertBlock(),
                                &*Builder.GetInsertPoint(), &DT, &LI);
CopyBB->setName("polly.stmt." + BB->getName());
return CopyBB;
434}

436BasicBlock *BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB,
                                 ValueMapT &BBMap, LoopToScevMapT &LTS,
                                 isl_id_to_ast_expr *NewAccesses) {
BasicBlock *CopyBB = splitBB(BB);
Builder.SetInsertPoint(&CopyBB->front());
generateScalarLoads(Stmt, LTS, BBMap, NewAccesses);
generateBeginStmtTrace(Stmt, LTS, BBMap);

copyBB(Stmt, BB, CopyBB, BBMap, LTS, NewAccesses);

// After a basic block was copied store all scalars that escape this block in
// their alloca.
generateScalarStores(Stmt, LTS, BBMap, NewAccesses);
return CopyBB;
450}

452void BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *CopyBB,
                          ValueMapT &BBMap, LoopToScevMapT &LTS,
                          isl_id_to_ast_expr *NewAccesses) {
EntryBB = &CopyBB->getParent()->getEntryBlock();

// Block statements and the entry blocks of region statement are code
// generated from instruction lists. This allow us to optimize the
// instructions that belong to a certain scop statement. As the code
// structure of region statements might be arbitrary complex, optimizing the
// instruction list is not yet supported.
if (Stmt.isBlockStmt() || (Stmt.isRegionStmt() && Stmt.getEntryBlock() == BB))
  for (Instruction *Inst : Stmt.getInstructions())
    copyInstruction(Stmt, Inst, BBMap, LTS, NewAccesses);
else
  for (Instruction &Inst : *BB)
    copyInstruction(Stmt, &Inst, BBMap, LTS, NewAccesses);
468}

470Value *BlockGenerator::getOrCreateAlloca(const MemoryAccess &Access) {
assert(!Access.isLatestArrayKind() && "Trying to get alloca for array kind")(static_cast<void> (0));

return getOrCreateAlloca(Access.getLatestScopArrayInfo());
474}

476Value *BlockGenerator::getOrCreateAlloca(const ScopArrayInfo *Array) {
assert(!Array->isArrayKind() && "Trying to get alloca for array kind")(static_cast<void> (0));

auto &Addr = ScalarMap[Array];

if (Addr) {
  // Allow allocas to be (temporarily) redirected once by adding a new
  // old-alloca-addr to new-addr mapping to GlobalMap. This functionality
  // is used for example by the OpenMP code generation where a first use
  // of a scalar while still in the host code allocates a normal alloca with
  // getOrCreateAlloca. When the values of this scalar are accessed during
  // the generation of the parallel subfunction, these values are copied over
  // to the parallel subfunction and each request for a scalar alloca slot
  // must be forwarded to the temporary in-subfunction slot. This mapping is
  // removed when the subfunction has been generated and again normal host
  // code is generated. Due to the following reasons it is not possible to
  // perform the GlobalMap lookup right after creating the alloca below, but
  // instead we need to check GlobalMap at each call to getOrCreateAlloca:
  //
  //   1) GlobalMap may be changed multiple times (for each parallel loop),
  //   2) The temporary mapping is commonly only known after the initial
  //      alloca has already been generated, and
  //   3) The original alloca value must be restored after leaving the
  //      sub-function.
  if (Value *NewAddr = GlobalMap.lookup(&*Addr))
    return NewAddr;
  return Addr;
}

Type *Ty = Array->getElementType();
Value *ScalarBase = Array->getBasePtr();
std::string NameExt;
if (Array->isPHIKind())
  NameExt = ".phiops";
else
  NameExt = ".s2a";

const DataLayout &DL = Builder.GetInsertBlock()->getModule()->getDataLayout();

Addr =
    new AllocaInst(Ty, DL.getAllocaAddrSpace(), nullptr,
                   DL.getPrefTypeAlign(Ty), ScalarBase->getName() + NameExt);
EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock();
Addr->insertBefore(&*EntryBB->getFirstInsertionPt());

return Addr;
522}

524void BlockGenerator::handleOutsideUsers(const Scop &S, ScopArrayInfo *Array) {
Instruction *Inst = cast<Instruction>(Array->getBasePtr());

// If there are escape users we get the alloca for this instruction and put it
// in the EscapeMap for later finalization. Lastly, if the instruction was
// copied multiple times we already did this and can exit.
if (EscapeMap.count(Inst))
  return;

EscapeUserVectorTy EscapeUsers;
for (User *U : Inst->users()) {

  // Non-instruction user will never escape.
  Instruction *UI = dyn_cast<Instruction>(U);
  if (!UI)
    continue;

  if (S.contains(UI))
    continue;

  EscapeUsers.push_back(UI);
}

// Exit if no escape uses were found.
if (EscapeUsers.empty())
  return;

// Get or create an escape alloca for this instruction.
auto *ScalarAddr = getOrCreateAlloca(Array);

// Remember that this instruction has escape uses and the escape alloca.
EscapeMap[Inst] = std::make_pair(ScalarAddr, std::move(EscapeUsers));
556}

558void BlockGenerator::generateScalarLoads(
  ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMap,
  __isl_keep isl_id_to_ast_expr *NewAccesses) {
for (MemoryAccess *MA : Stmt) {
  if (MA->isOriginalArrayKind() || MA->isWrite())
    continue;

565#ifndef NDEBUG1
  auto StmtDom =
      Stmt.getDomain().intersect_params(Stmt.getParent()->getContext());
  auto AccDom = MA->getAccessRelation().domain();
  assert(!StmtDom.is_subset(AccDom).is_false() &&(static_cast<void> (0))
         "Scalar must be loaded in all statement instances")(static_cast<void> (0));
571#endif

  auto *Address =
      getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS, BBMap, NewAccesses);
  assert((!isa<Instruction>(Address) ||(static_cast<void> (0))
          DT.dominates(cast<Instruction>(Address)->getParent(),(static_cast<void> (0))
                       Builder.GetInsertBlock())) &&(static_cast<void> (0))
         "Domination violation")(static_cast<void> (0));
  BBMap[MA->getAccessValue()] = Builder.CreateLoad(
      MA->getElementType(), Address, Address->getName() + ".reload");
}
582}

584Value *BlockGenerator::buildContainsCondition(ScopStmt &Stmt,
                                            const isl::set &Subdomain) {
isl::ast_build AstBuild = Stmt.getAstBuild();
isl::set Domain = Stmt.getDomain();

isl::union_map USchedule = AstBuild.get_schedule();
USchedule = USchedule.intersect_domain(Domain);

assert(!USchedule.is_empty())(static_cast<void> (0));
isl::map Schedule = isl::map::from_union_map(USchedule);

isl::set ScheduledDomain = Schedule.range();
isl::set ScheduledSet = Subdomain.apply(Schedule);

isl::ast_build RestrictedBuild = AstBuild.restrict(ScheduledDomain);

isl::ast_expr IsInSet = RestrictedBuild.expr_from(ScheduledSet);
Value *IsInSetExpr = ExprBuilder->create(IsInSet.copy());
IsInSetExpr = Builder.CreateICmpNE(
    IsInSetExpr, ConstantInt::get(IsInSetExpr->getType(), 0));

return IsInSetExpr;
606}

608void BlockGenerator::generateConditionalExecution(
  ScopStmt &Stmt, const isl::set &Subdomain, StringRef Subject,
  const std::function<void()> &GenThenFunc) {
isl::set StmtDom = Stmt.getDomain();

// If the condition is a tautology, don't generate a condition around the
// code.
bool IsPartialWrite =
    !StmtDom.intersect_params(Stmt.getParent()->getContext())
         .is_subset(Subdomain);
if (!IsPartialWrite) {
  GenThenFunc();
  return;
}

// Generate the condition.
Value *Cond = buildContainsCondition(Stmt, Subdomain);

// Don't call GenThenFunc if it is never executed. An ast index expression
// might not be defined in this case.
if (auto *Const = dyn_cast<ConstantInt>(Cond))
  if (Const->isZero())
    return;

BasicBlock *HeadBlock = Builder.GetInsertBlock();
StringRef BlockName = HeadBlock->getName();

// Generate the conditional block.
SplitBlockAndInsertIfThen(Cond, &*Builder.GetInsertPoint(), false, nullptr,
                          &DT, &LI);
BranchInst *Branch = cast<BranchInst>(HeadBlock->getTerminator());
BasicBlock *ThenBlock = Branch->getSuccessor(0);
BasicBlock *TailBlock = Branch->getSuccessor(1);

// Assign descriptive names.
if (auto *CondInst = dyn_cast<Instruction>(Cond))
  CondInst->setName("polly." + Subject + ".cond");
ThenBlock->setName(BlockName + "." + Subject + ".partial");
TailBlock->setName(BlockName + ".cont");

// Put the client code into the conditional block and continue in the merge
// block afterwards.
Builder.SetInsertPoint(ThenBlock, ThenBlock->getFirstInsertionPt());
GenThenFunc();
Builder.SetInsertPoint(TailBlock, TailBlock->getFirstInsertionPt());
653}

655static std::string getInstName(Value *Val) {
std::string Result;
raw_string_ostream OS(Result);
Val->printAsOperand(OS, false);
return OS.str();
660}

662void BlockGenerator::generateBeginStmtTrace(ScopStmt &Stmt, LoopToScevMapT &LTS,
                                          ValueMapT &BBMap) {
if (!TraceStmts)
  return;

Scop *S = Stmt.getParent();
const char *BaseName = Stmt.getBaseName();

isl::ast_build AstBuild = Stmt.getAstBuild();
isl::set Domain = Stmt.getDomain();

isl::union_map USchedule = AstBuild.get_schedule().intersect_domain(Domain);
isl::map Schedule = isl::map::from_union_map(USchedule);
assert(Schedule.is_empty().is_false() &&(static_cast<void> (0))
       "The stmt must have a valid instance")(static_cast<void> (0));

isl::multi_pw_aff ScheduleMultiPwAff =
    isl::pw_multi_aff::from_map(Schedule.reverse());
isl::ast_build RestrictedBuild = AstBuild.restrict(Schedule.range());

// Sequence of strings to print.
SmallVector<llvm::Value *, 8> Values;

// Print the name of the statement.
// TODO: Indent by the depth of the statement instance in the schedule tree.
Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, BaseName));
Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, "("));

// Add the coordinate of the statement instance.
int DomDims = ScheduleMultiPwAff.dim(isl::dim::out).release();
for (int i = 0; i < DomDims; i += 1) {
  if (i > 0)
    Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, ","));

  isl::ast_expr IsInSet = RestrictedBuild.expr_from(ScheduleMultiPwAff.at(i));
  Values.push_back(ExprBuilder->create(IsInSet.copy()));
}

if (TraceScalars) {
  Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, ")"));
  DenseSet<Instruction *> Encountered;

  // Add the value of each scalar (and the result of PHIs) used in the
  // statement.
  // TODO: Values used in region-statements.
  for (Instruction *Inst : Stmt.insts()) {
    if (!RuntimeDebugBuilder::isPrintable(Inst->getType()))
      continue;

    if (isa<PHINode>(Inst)) {
      Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, " "));
      Values.push_back(RuntimeDebugBuilder::getPrintableString(
          Builder, getInstName(Inst)));
      Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, "="));
      Values.push_back(getNewValue(Stmt, Inst, BBMap, LTS,
                                   LI.getLoopFor(Inst->getParent())));
    } else {
      for (Value *Op : Inst->operand_values()) {
        // Do not print values that cannot change during the execution of the
        // SCoP.
        auto *OpInst = dyn_cast<Instruction>(Op);
        if (!OpInst)
          continue;
        if (!S->contains(OpInst))
          continue;

        // Print each scalar at most once, and exclude values defined in the
        // statement itself.
        if (Encountered.count(OpInst))
          continue;

        Values.push_back(
            RuntimeDebugBuilder::getPrintableString(Builder, " "));
        Values.push_back(RuntimeDebugBuilder::getPrintableString(
            Builder, getInstName(OpInst)));
        Values.push_back(
            RuntimeDebugBuilder::getPrintableString(Builder, "="));
        Values.push_back(getNewValue(Stmt, OpInst, BBMap, LTS,
                                     LI.getLoopFor(Inst->getParent())));
        Encountered.insert(OpInst);
      }
    }

    Encountered.insert(Inst);
  }

  Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, "\n"));
} else {
  Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, ")\n"));
}

RuntimeDebugBuilder::createCPUPrinter(Builder, ArrayRef<Value *>(Values));
754}

756void BlockGenerator::generateScalarStores(
  ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMap,
  __isl_keep isl_id_to_ast_expr *NewAccesses) {
Loop *L = LI.getLoopFor(Stmt.getBasicBlock());

assert(Stmt.isBlockStmt() &&(static_cast<void> (0))
       "Region statements need to use the generateScalarStores() function in "(static_cast<void> (0))
       "the RegionGenerator")(static_cast<void> (0));

for (MemoryAccess *MA : Stmt) {
  if (MA->isOriginalArrayKind() || MA->isRead())
    continue;

  isl::set AccDom = MA->getAccessRelation().domain();
  std::string Subject = MA->getId().get_name();

  generateConditionalExecution(
      Stmt, AccDom, Subject.c_str(), [&, this, MA]() {
        Value *Val = MA->getAccessValue();
        if (MA->isAnyPHIKind()) {
          assert(MA->getIncoming().size() >= 1 &&(static_cast<void> (0))
                 "Block statements have exactly one exiting block, or "(static_cast<void> (0))
                 "multiple but "(static_cast<void> (0))
                 "with same incoming block and value")(static_cast<void> (0));
          assert(std::all_of(MA->getIncoming().begin(),(static_cast<void> (0))
                             MA->getIncoming().end(),(static_cast<void> (0))
                             [&](std::pair<BasicBlock *, Value *> p) -> bool {(static_cast<void> (0))
                               return p.first == Stmt.getBasicBlock();(static_cast<void> (0))
                             }) &&(static_cast<void> (0))
                 "Incoming block must be statement's block")(static_cast<void> (0));
          Val = MA->getIncoming()[0].second;
        }
        auto Address = getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS,
                                          BBMap, NewAccesses);

        Val = getNewValue(Stmt, Val, BBMap, LTS, L);
        assert((!isa<Instruction>(Val) ||(static_cast<void> (0))
                DT.dominates(cast<Instruction>(Val)->getParent(),(static_cast<void> (0))
                             Builder.GetInsertBlock())) &&(static_cast<void> (0))
               "Domination violation")(static_cast<void> (0));
        assert((!isa<Instruction>(Address) ||(static_cast<void> (0))
                DT.dominates(cast<Instruction>(Address)->getParent(),(static_cast<void> (0))
                             Builder.GetInsertBlock())) &&(static_cast<void> (0))
               "Domination violation")(static_cast<void> (0));

        // The new Val might have a different type than the old Val due to
        // ScalarEvolution looking through bitcasts.
        Address = Builder.CreateBitOrPointerCast(
            Address, Val->getType()->getPointerTo(
                         Address->getType()->getPointerAddressSpace()));

        Builder.CreateStore(Val, Address);
      });
}
810}

812void BlockGenerator::createScalarInitialization(Scop &S) {
BasicBlock *ExitBB = S.getExit();
BasicBlock *PreEntryBB = S.getEnteringBlock();

Builder.SetInsertPoint(&*StartBlock->begin());

for (auto &Array : S.arrays()) {
  if (Array->getNumberOfDimensions() != 0)
    continue;
  if (Array->isPHIKind()) {
    // For PHI nodes, the only values we need to store are the ones that
    // reach the PHI node from outside the region. In general there should
    // only be one such incoming edge and this edge should enter through
    // 'PreEntryBB'.
    auto PHI = cast<PHINode>(Array->getBasePtr());

    for (auto BI = PHI->block_begin(), BE = PHI->block_end(); BI != BE; BI++)
      if (!S.contains(*BI) && *BI != PreEntryBB)
        llvm_unreachable("Incoming edges from outside the scop should always "__builtin_unreachable()
                         "come from PreEntryBB")__builtin_unreachable();

    int Idx = PHI->getBasicBlockIndex(PreEntryBB);
    if (Idx < 0)
      continue;

    Value *ScalarValue = PHI->getIncomingValue(Idx);

    Builder.CreateStore(ScalarValue, getOrCreateAlloca(Array));
    continue;
  }

  auto *Inst = dyn_cast<Instruction>(Array->getBasePtr());

  if (Inst && S.contains(Inst))
    continue;

  // PHI nodes that are not marked as such in their SAI object are either exit
  // PHI nodes we model as common scalars but without initialization, or
  // incoming phi nodes that need to be initialized. Check if the first is the
  // case for Inst and do not create and initialize memory if so.
  if (auto *PHI = dyn_cast_or_null<PHINode>(Inst))
    if (!S.hasSingleExitEdge() && PHI->getBasicBlockIndex(ExitBB) >= 0)
      continue;

  Builder.CreateStore(Array->getBasePtr(), getOrCreateAlloca(Array));
}
858}

860void BlockGenerator::createScalarFinalization(Scop &S) {
// The exit block of the __unoptimized__ region.
BasicBlock *ExitBB = S.getExitingBlock();
// The merge block __just after__ the region and the optimized region.
BasicBlock *MergeBB = S.getExit();

// The exit block of the __optimized__ region.
BasicBlock *OptExitBB = *(pred_begin(MergeBB));
if (OptExitBB == ExitBB)
  OptExitBB = *(++pred_begin(MergeBB));

Builder.SetInsertPoint(OptExitBB->getTerminator());
for (const auto &EscapeMapping : EscapeMap) {
  // Extract the escaping instruction and the escaping users as well as the
  // alloca the instruction was demoted to.
  Instruction *EscapeInst = EscapeMapping.first;
  const auto &EscapeMappingValue = EscapeMapping.second;
  const EscapeUserVectorTy &EscapeUsers = EscapeMappingValue.second;
  auto *ScalarAddr = cast<AllocaInst>(&*EscapeMappingValue.first);

  // Reload the demoted instruction in the optimized version of the SCoP.
  Value *EscapeInstReload =
      Builder.CreateLoad(ScalarAddr->getAllocatedType(), ScalarAddr,
                         EscapeInst->getName() + ".final_reload");
  EscapeInstReload =
      Builder.CreateBitOrPointerCast(EscapeInstReload, EscapeInst->getType());

  // Create the merge PHI that merges the optimized and unoptimized version.
  PHINode *MergePHI = PHINode::Create(EscapeInst->getType(), 2,
                                      EscapeInst->getName() + ".merge");
  MergePHI->insertBefore(&*MergeBB->getFirstInsertionPt());

  // Add the respective values to the merge PHI.
  MergePHI->addIncoming(EscapeInstReload, OptExitBB);
  MergePHI->addIncoming(EscapeInst, ExitBB);

  // The information of scalar evolution about the escaping instruction needs
  // to be revoked so the new merged instruction will be used.
  if (SE.isSCEVable(EscapeInst->getType()))
    SE.forgetValue(EscapeInst);

  // Replace all uses of the demoted instruction with the merge PHI.
  for (Instruction *EUser : EscapeUsers)
    EUser->replaceUsesOfWith(EscapeInst, MergePHI);
}
905}

907void BlockGenerator::findOutsideUsers(Scop &S) {
for (auto &Array : S.arrays()) {

  if (Array->getNumberOfDimensions() != 0)
    continue;

  if (Array->isPHIKind())
    continue;

  auto *Inst = dyn_cast<Instruction>(Array->getBasePtr());

  if (!Inst)
    continue;

  // Scop invariant hoisting moves some of the base pointers out of the scop.
  // We can ignore these, as the invariant load hoisting already registers the
  // relevant outside users.
  if (!S.contains(Inst))
    continue;

  handleOutsideUsers(S, Array);
}
929}

931void BlockGenerator::createExitPHINodeMerges(Scop &S) {
if (S.hasSingleExitEdge())
  return;

auto *ExitBB = S.getExitingBlock();
auto *MergeBB = S.getExit();
auto *AfterMergeBB = MergeBB->getSingleSuccessor();
BasicBlock *OptExitBB = *(pred_begin(MergeBB));
if (OptExitBB == ExitBB)
  OptExitBB = *(++pred_begin(MergeBB));

Builder.SetInsertPoint(OptExitBB->getTerminator());

for (auto &SAI : S.arrays()) {
  auto *Val = SAI->getBasePtr();

  // Only Value-like scalars need a merge PHI. Exit block PHIs receive either
  // the original PHI's value or the reloaded incoming values from the
  // generated code. An llvm::Value is merged between the original code's
  // value or the generated one.
  if (!SAI->isExitPHIKind())
    continue;

  PHINode *PHI = dyn_cast<PHINode>(Val);
  if (!PHI)
    continue;

  if (PHI->getParent() != AfterMergeBB)
    continue;

  std::string Name = PHI->getName().str();
  Value *ScalarAddr = getOrCreateAlloca(SAI);
  Value *Reload = Builder.CreateLoad(SAI->getElementType(), ScalarAddr,
                                     Name + ".ph.final_reload");
  Reload = Builder.CreateBitOrPointerCast(Reload, PHI->getType());
  Value *OriginalValue = PHI->getIncomingValueForBlock(MergeBB);
  assert((!isa<Instruction>(OriginalValue) ||(static_cast<void> (0))
          cast<Instruction>(OriginalValue)->getParent() != MergeBB) &&(static_cast<void> (0))
         "Original value must no be one we just generated.")(static_cast<void> (0));
  auto *MergePHI = PHINode::Create(PHI->getType(), 2, Name + ".ph.merge");
  MergePHI->insertBefore(&*MergeBB->getFirstInsertionPt());
  MergePHI->addIncoming(Reload, OptExitBB);
  MergePHI->addIncoming(OriginalValue, ExitBB);
  int Idx = PHI->getBasicBlockIndex(MergeBB);
  PHI->setIncomingValue(Idx, MergePHI);
}
977}

979void BlockGenerator::invalidateScalarEvolution(Scop &S) {
for (auto &Stmt : S)
  if (Stmt.isCopyStmt())
    continue;
  else if (Stmt.isBlockStmt())
    for (auto &Inst : *Stmt.getBasicBlock())
      SE.forgetValue(&Inst);
  else if (Stmt.isRegionStmt())
    for (auto *BB : Stmt.getRegion()->blocks())
      for (auto &Inst : *BB)
        SE.forgetValue(&Inst);
  else
    llvm_unreachable("Unexpected statement type found")__builtin_unreachable();

// Invalidate SCEV of loops surrounding the EscapeUsers.
for (const auto &EscapeMapping : EscapeMap) {
  const EscapeUserVectorTy &EscapeUsers = EscapeMapping.second.second;
  for (Instruction *EUser : EscapeUsers) {
    if (Loop *L = LI.getLoopFor(EUser->getParent()))
      while (L) {
        SE.forgetLoop(L);
        L = L->getParentLoop();
      }
  }
}
1004}

1006void BlockGenerator::finalizeSCoP(Scop &S) {
findOutsideUsers(S);
createScalarInitialization(S);
createExitPHINodeMerges(S);
createScalarFinalization(S);
invalidateScalarEvolution(S);
1012}

1014VectorBlockGenerator::VectorBlockGenerator(BlockGenerator &BlockGen,
                                         std::vector<LoopToScevMapT> &VLTS,
                                         isl_map *Schedule)
  : BlockGenerator(BlockGen), VLTS(VLTS), Schedule(Schedule) {
assert(Schedule && "No statement domain provided")(static_cast<void> (0));
1019}

1021Value *VectorBlockGenerator::getVectorValue(ScopStmt &Stmt, Value *Old,
                                          ValueMapT &VectorMap,
                                          VectorValueMapT &ScalarMaps,
                                          Loop *L) {
if (Value *NewValue = VectorMap.lookup(Old))
  return NewValue;

int Width = getVectorWidth();

Value *Vector = UndefValue::get(FixedVectorType::get(Old->getType(), Width));

for (int Lane = 0; Lane < Width; Lane++)
  Vector = Builder.CreateInsertElement(
      Vector, getNewValue(Stmt, Old, ScalarMaps[Lane], VLTS[Lane], L),
      Builder.getInt32(Lane));

VectorMap[Old] = Vector;

return Vector;
1040}

1042Value *VectorBlockGenerator::generateStrideOneLoad(
  ScopStmt &Stmt, LoadInst *Load, VectorValueMapT &ScalarMaps,
  __isl_keep isl_id_to_ast_expr *NewAccesses, bool NegativeStride = false) {
unsigned VectorWidth = getVectorWidth();
Type *VectorType = FixedVectorType::get(Load->getType(), VectorWidth);
Type *VectorPtrType =
    PointerType::get(VectorType, Load->getPointerAddressSpace());
unsigned Offset = NegativeStride ? VectorWidth - 1 : 0;

Value *NewPointer = generateLocationAccessed(Stmt, Load, ScalarMaps[Offset],
                                             VLTS[Offset], NewAccesses);
Value *VectorPtr =
    Builder.CreateBitCast(NewPointer, VectorPtrType, "vector_ptr");
LoadInst *VecLoad = Builder.CreateLoad(VectorType, VectorPtr,
                                       Load->getName() + "_p_vec_full");
if (!Aligned)
  VecLoad->setAlignment(Align(8));

if (NegativeStride) {
  SmallVector<Constant *, 16> Indices;
  for (int i = VectorWidth - 1; i >= 0; i--)
    Indices.push_back(ConstantInt::get(Builder.getInt32Ty(), i));
  Constant *SV = llvm::ConstantVector::get(Indices);
  Value *RevVecLoad = Builder.CreateShuffleVector(
      VecLoad, VecLoad, SV, Load->getName() + "_reverse");
  return RevVecLoad;
}

return VecLoad;
1071}

1073Value *VectorBlockGenerator::generateStrideZeroLoad(
  ScopStmt &Stmt, LoadInst *Load, ValueMapT &BBMap,
  __isl_keep isl_id_to_ast_expr *NewAccesses) {
Type *VectorType = FixedVectorType::get(Load->getType(), 1);
Type *VectorPtrType =
    PointerType::get(VectorType, Load->getPointerAddressSpace());
Value *NewPointer =
    generateLocationAccessed(Stmt, Load, BBMap, VLTS[0], NewAccesses);
Value *VectorPtr = Builder.CreateBitCast(NewPointer, VectorPtrType,
                                         Load->getName() + "_p_vec_p");
LoadInst *ScalarLoad = Builder.CreateLoad(VectorType, VectorPtr,
                                          Load->getName() + "_p_splat_one");

if (!Aligned)
  ScalarLoad->setAlignment(Align(8));

Constant *SplatVector = Constant::getNullValue(
    FixedVectorType::get(Builder.getInt32Ty(), getVectorWidth()));

Value *VectorLoad = Builder.CreateShuffleVector(
    ScalarLoad, ScalarLoad, SplatVector, Load->getName() + "_p_splat");
return VectorLoad;
1095}

1097Value *VectorBlockGenerator::generateUnknownStrideLoad(
  ScopStmt &Stmt, LoadInst *Load, VectorValueMapT &ScalarMaps,
  __isl_keep isl_id_to_ast_expr *NewAccesses) {
int VectorWidth = getVectorWidth();
Type *ElemTy = Load->getType();
auto *FVTy = FixedVectorType::get(ElemTy, VectorWidth);

Value *Vector = UndefValue::get(FVTy);

for (int i = 0; i < VectorWidth; i++) {
  Value *NewPointer = generateLocationAccessed(Stmt, Load, ScalarMaps[i],
                                               VLTS[i], NewAccesses);
  Value *ScalarLoad =
      Builder.CreateLoad(ElemTy, NewPointer, Load->getName() + "_p_scalar_");
  Vector = Builder.CreateInsertElement(
      Vector, ScalarLoad, Builder.getInt32(i), Load->getName() + "_p_vec_");
}

return Vector;
1116}

1118void VectorBlockGenerator::generateLoad(
  ScopStmt &Stmt, LoadInst *Load, ValueMapT &VectorMap,
  VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
if (Value *PreloadLoad = GlobalMap.lookup(Load)) {
  VectorMap[Load] = Builder.CreateVectorSplat(getVectorWidth(), PreloadLoad,
                                              Load->getName() + "_p");
  return;
}

if (!VectorType::isValidElementType(Load->getType())) {
  for (int i = 0; i < getVectorWidth(); i++)
    ScalarMaps[i][Load] =
        generateArrayLoad(Stmt, Load, ScalarMaps[i], VLTS[i], NewAccesses);
  return;
}

const MemoryAccess &Access = Stmt.getArrayAccessFor(Load);

// Make sure we have scalar values available to access the pointer to
// the data location.
extractScalarValues(Load, VectorMap, ScalarMaps);

Value *NewLoad;
if (Access.isStrideZero(isl::manage_copy(Schedule)))
  NewLoad = generateStrideZeroLoad(Stmt, Load, ScalarMaps[0], NewAccesses);
else if (Access.isStrideOne(isl::manage_copy(Schedule)))
  NewLoad = generateStrideOneLoad(Stmt, Load, ScalarMaps, NewAccesses);
else if (Access.isStrideX(isl::manage_copy(Schedule), -1))
  NewLoad = generateStrideOneLoad(Stmt, Load, ScalarMaps, NewAccesses, true);
else
  NewLoad = generateUnknownStrideLoad(Stmt, Load, ScalarMaps, NewAccesses);

VectorMap[Load] = NewLoad;
1151}

1153void VectorBlockGenerator::copyUnaryInst(ScopStmt &Stmt, UnaryInstruction *Inst,
                                       ValueMapT &VectorMap,
                                       VectorValueMapT &ScalarMaps) {
int VectorWidth = getVectorWidth();
Value *NewOperand = getVectorValue(Stmt, Inst->getOperand(0), VectorMap,
                                   ScalarMaps, getLoopForStmt(Stmt));

assert(isa<CastInst>(Inst) && "Can not generate vector code for instruction")(static_cast<void> (0));

const CastInst *Cast = dyn_cast<CastInst>(Inst);
12
←
Assuming 'Inst' is not a 'CastInst'→
13
←
'Cast' initialized to a null pointer value→
auto *DestType = FixedVectorType::get(Inst->getType(), VectorWidth);
VectorMap[Inst] = Builder.CreateCast(Cast->getOpcode(), NewOperand, DestType);
14
←
Called C++ object pointer is null
1165}

1167void VectorBlockGenerator::copyBinaryInst(ScopStmt &Stmt, BinaryOperator *Inst,
                                        ValueMapT &VectorMap,
                                        VectorValueMapT &ScalarMaps) {
Loop *L = getLoopForStmt(Stmt);
Value *OpZero = Inst->getOperand(0);
Value *OpOne = Inst->getOperand(1);

Value *NewOpZero, *NewOpOne;
NewOpZero = getVectorValue(Stmt, OpZero, VectorMap, ScalarMaps, L);
NewOpOne = getVectorValue(Stmt, OpOne, VectorMap, ScalarMaps, L);

Value *NewInst = Builder.CreateBinOp(Inst->getOpcode(), NewOpZero, NewOpOne,
                                     Inst->getName() + "p_vec");
VectorMap[Inst] = NewInst;
1181}

1183void VectorBlockGenerator::copyStore(
  ScopStmt &Stmt, StoreInst *Store, ValueMapT &VectorMap,
  VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
const MemoryAccess &Access = Stmt.getArrayAccessFor(Store);

Value *Vector = getVectorValue(Stmt, Store->getValueOperand(), VectorMap,
                               ScalarMaps, getLoopForStmt(Stmt));

// Make sure we have scalar values available to access the pointer to
// the data location.
extractScalarValues(Store, VectorMap, ScalarMaps);

if (Access.isStrideOne(isl::manage_copy(Schedule))) {
  Type *VectorType = FixedVectorType::get(Store->getValueOperand()->getType(),
                                          getVectorWidth());
  Type *VectorPtrType =
      PointerType::get(VectorType, Store->getPointerAddressSpace());
  Value *NewPointer = generateLocationAccessed(Stmt, Store, ScalarMaps[0],
                                               VLTS[0], NewAccesses);

  Value *VectorPtr =
      Builder.CreateBitCast(NewPointer, VectorPtrType, "vector_ptr");
  StoreInst *Store = Builder.CreateStore(Vector, VectorPtr);

  if (!Aligned)
    Store->setAlignment(Align(8));
} else {
  for (unsigned i = 0; i < ScalarMaps.size(); i++) {
    Value *Scalar = Builder.CreateExtractElement(Vector, Builder.getInt32(i));
    Value *NewPointer = generateLocationAccessed(Stmt, Store, ScalarMaps[i],
                                                 VLTS[i], NewAccesses);
    Builder.CreateStore(Scalar, NewPointer);
  }
}
1217}

1219bool VectorBlockGenerator::hasVectorOperands(const Instruction *Inst,
                                           ValueMapT &VectorMap) {
for (Value *Operand : Inst->operands())
  if (VectorMap.count(Operand))
    return true;
return false;
1225}

1227bool VectorBlockGenerator::extractScalarValues(const Instruction *Inst,
                                             ValueMapT &VectorMap,
                                             VectorValueMapT &ScalarMaps) {
bool HasVectorOperand = false;
int VectorWidth = getVectorWidth();

for (Value *Operand : Inst->operands()) {
  ValueMapT::iterator VecOp = VectorMap.find(Operand);

  if (VecOp == VectorMap.end())
    continue;

  HasVectorOperand = true;
  Value *NewVector = VecOp->second;

  for (int i = 0; i < VectorWidth; ++i) {
    ValueMapT &SM = ScalarMaps[i];

    // If there is one scalar extracted, all scalar elements should have
    // already been extracted by the code here. So no need to check for the
    // existence of all of them.
    if (SM.count(Operand))
      break;

    SM[Operand] =
        Builder.CreateExtractElement(NewVector, Builder.getInt32(i));
  }
}

return HasVectorOperand;
1257}

1259void VectorBlockGenerator::copyInstScalarized(
  ScopStmt &Stmt, Instruction *Inst, ValueMapT &VectorMap,
  VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
bool HasVectorOperand;
int VectorWidth = getVectorWidth();

HasVectorOperand = extractScalarValues(Inst, VectorMap, ScalarMaps);

for (int VectorLane = 0; VectorLane < getVectorWidth(); VectorLane++)
  BlockGenerator::copyInstruction(Stmt, Inst, ScalarMaps[VectorLane],
                                  VLTS[VectorLane], NewAccesses);

if (!VectorType::isValidElementType(Inst->getType()) || !HasVectorOperand)
  return;

// Make the result available as vector value.
auto *FVTy = FixedVectorType::get(Inst->getType(), VectorWidth);
Value *Vector = UndefValue::get(FVTy);

for (int i = 0; i < VectorWidth; i++)
  Vector = Builder.CreateInsertElement(Vector, ScalarMaps[i][Inst],
                                       Builder.getInt32(i));

VectorMap[Inst] = Vector;
1283}

1285int VectorBlockGenerator::getVectorWidth() { return VLTS.size(); }

1287void VectorBlockGenerator::copyInstruction(
  ScopStmt &Stmt, Instruction *Inst, ValueMapT &VectorMap,
  VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
// Terminator instructions control the control flow. They are explicitly
// expressed in the clast and do not need to be copied.
if (Inst->isTerminator())
2
←
Taking false branch→
  return;

if (canSyntheziseInStmt(Stmt, Inst))
3
←
Taking false branch→
  return;

if (auto *Load4.1
'Load' is null
1
'Load' is null
 = dyn_cast<LoadInst>(Inst)) {
4
←
Assuming 'Inst' is not a 'LoadInst'→
5
←
Taking false branch→
  generateLoad(Stmt, Load, VectorMap, ScalarMaps, NewAccesses);
  return;
}

if (hasVectorOperands(Inst, VectorMap)) {
6
←
Taking true branch→
  if (auto *Store7.1
'Store' is null
1
'Store' is null
 = dyn_cast<StoreInst>(Inst)) {
7
←
Assuming 'Inst' is not a 'StoreInst'→
8
←
Taking false branch→
    // Identified as redundant by -polly-simplify.
    if (!Stmt.getArrayAccessOrNULLFor(Store))
      return;

    copyStore(Stmt, Store, VectorMap, ScalarMaps, NewAccesses);
    return;
  }

  if (auto *Unary9.1
'Unary' is non-null
1
'Unary' is non-null
 = dyn_cast<UnaryInstruction>(Inst)) {
9
←
Assuming 'Inst' is a 'UnaryInstruction'→
10
←
Taking true branch→
    copyUnaryInst(Stmt, Unary, VectorMap, ScalarMaps);
11
←
Calling 'VectorBlockGenerator::copyUnaryInst'→
    return;
  }

  if (auto *Binary = dyn_cast<BinaryOperator>(Inst)) {
    copyBinaryInst(Stmt, Binary, VectorMap, ScalarMaps);
    return;
  }

  // Fallthrough: We generate scalar instructions, if we don't know how to
  // generate vector code.
}

copyInstScalarized(Stmt, Inst, VectorMap, ScalarMaps, NewAccesses);
1328}

1330void VectorBlockGenerator::generateScalarVectorLoads(
  ScopStmt &Stmt, ValueMapT &VectorBlockMap) {
for (MemoryAccess *MA : Stmt) {
  if (MA->isArrayKind() || MA->isWrite())
    continue;

  auto *Address = getOrCreateAlloca(*MA);
  Type *VectorType = FixedVectorType::get(MA->getElementType(), 1);
  Type *VectorPtrType = PointerType::get(
      VectorType, Address->getType()->getPointerAddressSpace());
  Value *VectorPtr = Builder.CreateBitCast(Address, VectorPtrType,
                                           Address->getName() + "_p_vec_p");
  auto *Val = Builder.CreateLoad(VectorType, VectorPtr,
                                 Address->getName() + ".reload");
  Constant *SplatVector = Constant::getNullValue(
      FixedVectorType::get(Builder.getInt32Ty(), getVectorWidth()));

  Value *VectorVal = Builder.CreateShuffleVector(
      Val, Val, SplatVector, Address->getName() + "_p_splat");
  VectorBlockMap[MA->getAccessValue()] = VectorVal;
}
1351}

1353void VectorBlockGenerator::verifyNoScalarStores(ScopStmt &Stmt) {
for (MemoryAccess *MA : Stmt) {
  if (MA->isArrayKind() || MA->isRead())
    continue;

  llvm_unreachable("Scalar stores not expected in vector loop")__builtin_unreachable();
}
1360}

1362void VectorBlockGenerator::copyStmt(
  ScopStmt &Stmt, __isl_keep isl_id_to_ast_expr *NewAccesses) {
assert(Stmt.isBlockStmt() &&(static_cast<void> (0))
       "TODO: Only block statements can be copied by the vector block "(static_cast<void> (0))
       "generator")(static_cast<void> (0));

BasicBlock *BB = Stmt.getBasicBlock();
BasicBlock *CopyBB = SplitBlock(Builder.GetInsertBlock(),
                                &*Builder.GetInsertPoint(), &DT, &LI);
CopyBB->setName("polly.stmt." + BB->getName());
Builder.SetInsertPoint(&CopyBB->front());

// Create two maps that store the mapping from the original instructions of
// the old basic block to their copies in the new basic block. Those maps
// are basic block local.
//
// As vector code generation is supported there is one map for scalar values
// and one for vector values.
//
// In case we just do scalar code generation, the vectorMap is not used and
// the scalarMap has just one dimension, which contains the mapping.
//
// In case vector code generation is done, an instruction may either appear
// in the vector map once (as it is calculating >vectorwidth< values at a
// time. Or (if the values are calculated using scalar operations), it
// appears once in every dimension of the scalarMap.
VectorValueMapT ScalarBlockMap(getVectorWidth());
ValueMapT VectorBlockMap;

generateScalarVectorLoads(Stmt, VectorBlockMap);

for (Instruction *Inst : Stmt.getInstructions())
  copyInstruction(Stmt, Inst, VectorBlockMap, ScalarBlockMap, NewAccesses);
1
Calling 'VectorBlockGenerator::copyInstruction'→

verifyNoScalarStores(Stmt);
1397}

1399BasicBlock *RegionGenerator::repairDominance(BasicBlock *BB,
                                           BasicBlock *BBCopy) {

BasicBlock *BBIDom = DT.getNode(BB)->getIDom()->getBlock();
BasicBlock *BBCopyIDom = EndBlockMap.lookup(BBIDom);

if (BBCopyIDom)
  DT.changeImmediateDominator(BBCopy, BBCopyIDom);

return StartBlockMap.lookup(BBIDom);
1409}

1411// This is to determine whether an llvm::Value (defined in @p BB) is usable when
1412// leaving a subregion. The straight-forward DT.dominates(BB, R->getExitBlock())
1413// does not work in cases where the exit block has edges from outside the
1414// region. In that case the llvm::Value would never be usable in in the exit
1415// block. The RegionGenerator however creates an new exit block ('ExitBBCopy')
1416// for the subregion's exiting edges only. We need to determine whether an
1417// llvm::Value is usable in there. We do this by checking whether it dominates
1418// all exiting blocks individually.
1419static bool isDominatingSubregionExit(const DominatorTree &DT, Region *R,
                                    BasicBlock *BB) {
for (auto ExitingBB : predecessors(R->getExit())) {
  // Check for non-subregion incoming edges.
  if (!R->contains(ExitingBB))
    continue;

  if (!DT.dominates(BB, ExitingBB))
    return false;
}

return true;
1431}

1433// Find the direct dominator of the subregion's exit block if the subregion was
1434// simplified.
1435static BasicBlock *findExitDominator(DominatorTree &DT, Region *R) {
BasicBlock *Common = nullptr;
for (auto ExitingBB : predecessors(R->getExit())) {
  // Check for non-subregion incoming edges.
  if (!R->contains(ExitingBB))
    continue;

  // First exiting edge.
  if (!Common) {
    Common = ExitingBB;
    continue;
  }

  Common = DT.findNearestCommonDominator(Common, ExitingBB);
}

assert(Common && R->contains(Common))(static_cast<void> (0));
return Common;
1453}

1455void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
                             isl_id_to_ast_expr *IdToAstExp) {
assert(Stmt.isRegionStmt() &&(static_cast<void> (0))
       "Only region statements can be copied by the region generator")(static_cast<void> (0));

// Forget all old mappings.
StartBlockMap.clear();
EndBlockMap.clear();
RegionMaps.clear();
IncompletePHINodeMap.clear();

// Collection of all values related to this subregion.
ValueMapT ValueMap;

// The region represented by the statement.
Region *R = Stmt.getRegion();

// Create a dedicated entry for the region where we can reload all demoted
// inputs.
BasicBlock *EntryBB = R->getEntry();
BasicBlock *EntryBBCopy = SplitBlock(Builder.GetInsertBlock(),
                                     &*Builder.GetInsertPoint(), &DT, &LI);
EntryBBCopy->setName("polly.stmt." + EntryBB->getName() + ".entry");
Builder.SetInsertPoint(&EntryBBCopy->front());

ValueMapT &EntryBBMap = RegionMaps[EntryBBCopy];
generateScalarLoads(Stmt, LTS, EntryBBMap, IdToAstExp);
generateBeginStmtTrace(Stmt, LTS, EntryBBMap);

for (auto PI = pred_begin(EntryBB), PE = pred_end(EntryBB); PI != PE; ++PI)
  if (!R->contains(*PI)) {
    StartBlockMap[*PI] = EntryBBCopy;
    EndBlockMap[*PI] = EntryBBCopy;
  }

// Iterate over all blocks in the region in a breadth-first search.
std::deque<BasicBlock *> Blocks;
SmallSetVector<BasicBlock *, 8> SeenBlocks;
Blocks.push_back(EntryBB);
SeenBlocks.insert(EntryBB);

while (!Blocks.empty()) {
  BasicBlock *BB = Blocks.front();
  Blocks.pop_front();

  // First split the block and update dominance information.
  BasicBlock *BBCopy = splitBB(BB);
  BasicBlock *BBCopyIDom = repairDominance(BB, BBCopy);

  // Get the mapping for this block and initialize it with either the scalar
  // loads from the generated entering block (which dominates all blocks of
  // this subregion) or the maps of the immediate dominator, if part of the
  // subregion. The latter necessarily includes the former.
  ValueMapT *InitBBMap;
  if (BBCopyIDom) {
    assert(RegionMaps.count(BBCopyIDom))(static_cast<void> (0));
    InitBBMap = &RegionMaps[BBCopyIDom];
  } else
    InitBBMap = &EntryBBMap;
  auto Inserted = RegionMaps.insert(std::make_pair(BBCopy, *InitBBMap));
  ValueMapT &RegionMap = Inserted.first->second;

  // Copy the block with the BlockGenerator.
  Builder.SetInsertPoint(&BBCopy->front());
  copyBB(Stmt, BB, BBCopy, RegionMap, LTS, IdToAstExp);

  // In order to remap PHI nodes we store also basic block mappings.
  StartBlockMap[BB] = BBCopy;
  EndBlockMap[BB] = Builder.GetInsertBlock();

  // Add values to incomplete PHI nodes waiting for this block to be copied.
  for (const PHINodePairTy &PHINodePair : IncompletePHINodeMap[BB])
    addOperandToPHI(Stmt, PHINodePair.first, PHINodePair.second, BB, LTS);
  IncompletePHINodeMap[BB].clear();

  // And continue with new successors inside the region.
  for (auto SI = succ_begin(BB), SE = succ_end(BB); SI != SE; SI++)
    if (R->contains(*SI) && SeenBlocks.insert(*SI))
      Blocks.push_back(*SI);

  // Remember value in case it is visible after this subregion.
  if (isDominatingSubregionExit(DT, R, BB))
    ValueMap.insert(RegionMap.begin(), RegionMap.end());
}

// Now create a new dedicated region exit block and add it to the region map.
BasicBlock *ExitBBCopy = SplitBlock(Builder.GetInsertBlock(),
                                    &*Builder.GetInsertPoint(), &DT, &LI);
ExitBBCopy->setName("polly.stmt." + R->getExit()->getName() + ".exit");
StartBlockMap[R->getExit()] = ExitBBCopy;
EndBlockMap[R->getExit()] = ExitBBCopy;

BasicBlock *ExitDomBBCopy = EndBlockMap.lookup(findExitDominator(DT, R));
assert(ExitDomBBCopy &&(static_cast<void> (0))
       "Common exit dominator must be within region; at least the entry node "(static_cast<void> (0))
       "must match")(static_cast<void> (0));
DT.changeImmediateDominator(ExitBBCopy, ExitDomBBCopy);

// As the block generator doesn't handle control flow we need to add the
// region control flow by hand after all blocks have been copied.
for (BasicBlock *BB : SeenBlocks) {

  BasicBlock *BBCopyStart = StartBlockMap[BB];
  BasicBlock *BBCopyEnd = EndBlockMap[BB];
  Instruction *TI = BB->getTerminator();
  if (isa<UnreachableInst>(TI)) {
    while (!BBCopyEnd->empty())
      BBCopyEnd->begin()->eraseFromParent();
    new UnreachableInst(BBCopyEnd->getContext(), BBCopyEnd);
    continue;
  }

  Instruction *BICopy = BBCopyEnd->getTerminator();

  ValueMapT &RegionMap = RegionMaps[BBCopyStart];
  RegionMap.insert(StartBlockMap.begin(), StartBlockMap.end());

  Builder.SetInsertPoint(BICopy);
  copyInstScalar(Stmt, TI, RegionMap, LTS);
  BICopy->eraseFromParent();
}

// Add counting PHI nodes to all loops in the region that can be used as
// replacement for SCEVs referring to the old loop.
for (BasicBlock *BB : SeenBlocks) {
  Loop *L = LI.getLoopFor(BB);
  if (L == nullptr || L->getHeader() != BB || !R->contains(L))
    continue;

  BasicBlock *BBCopy = StartBlockMap[BB];
  Value *NullVal = Builder.getInt32(0);
  PHINode *LoopPHI =
      PHINode::Create(Builder.getInt32Ty(), 2, "polly.subregion.iv");
  Instruction *LoopPHIInc = BinaryOperator::CreateAdd(
      LoopPHI, Builder.getInt32(1), "polly.subregion.iv.inc");
  LoopPHI->insertBefore(&BBCopy->front());
  LoopPHIInc->insertBefore(BBCopy->getTerminator());

  for (auto *PredBB : make_range(pred_begin(BB), pred_end(BB))) {
    if (!R->contains(PredBB))
      continue;
    if (L->contains(PredBB))
      LoopPHI->addIncoming(LoopPHIInc, EndBlockMap[PredBB]);
    else
      LoopPHI->addIncoming(NullVal, EndBlockMap[PredBB]);
  }

  for (auto *PredBBCopy : make_range(pred_begin(BBCopy), pred_end(BBCopy)))
    if (LoopPHI->getBasicBlockIndex(PredBBCopy) < 0)
      LoopPHI->addIncoming(NullVal, PredBBCopy);

  LTS[L] = SE.getUnknown(LoopPHI);
}

// Continue generating code in the exit block.
Builder.SetInsertPoint(&*ExitBBCopy->getFirstInsertionPt());

// Write values visible to other statements.
generateScalarStores(Stmt, LTS, ValueMap, IdToAstExp);
StartBlockMap.clear();
EndBlockMap.clear();
RegionMaps.clear();
IncompletePHINodeMap.clear();
1618}

1620PHINode *RegionGenerator::buildExitPHI(MemoryAccess *MA, LoopToScevMapT &LTS,
                                     ValueMapT &BBMap, Loop *L) {
ScopStmt *Stmt = MA->getStatement();
Region *SubR = Stmt->getRegion();
auto Incoming = MA->getIncoming();

PollyIRBuilder::InsertPointGuard IPGuard(Builder);
PHINode *OrigPHI = cast<PHINode>(MA->getAccessInstruction());
BasicBlock *NewSubregionExit = Builder.GetInsertBlock();

// This can happen if the subregion is simplified after the ScopStmts
// have been created; simplification happens as part of CodeGeneration.
if (OrigPHI->getParent() != SubR->getExit()) {
  BasicBlock *FormerExit = SubR->getExitingBlock();
  if (FormerExit)
    NewSubregionExit = StartBlockMap.lookup(FormerExit);
}

PHINode *NewPHI = PHINode::Create(OrigPHI->getType(), Incoming.size(),
                                  "polly." + OrigPHI->getName(),
                                  NewSubregionExit->getFirstNonPHI());

// Add the incoming values to the PHI.
for (auto &Pair : Incoming) {
  BasicBlock *OrigIncomingBlock = Pair.first;
  BasicBlock *NewIncomingBlockStart = StartBlockMap.lookup(OrigIncomingBlock);
  BasicBlock *NewIncomingBlockEnd = EndBlockMap.lookup(OrigIncomingBlock);
  Builder.SetInsertPoint(NewIncomingBlockEnd->getTerminator());
  assert(RegionMaps.count(NewIncomingBlockStart))(static_cast<void> (0));
  assert(RegionMaps.count(NewIncomingBlockEnd))(static_cast<void> (0));
  ValueMapT *LocalBBMap = &RegionMaps[NewIncomingBlockStart];

  Value *OrigIncomingValue = Pair.second;
  Value *NewIncomingValue =
      getNewValue(*Stmt, OrigIncomingValue, *LocalBBMap, LTS, L);
  NewPHI->addIncoming(NewIncomingValue, NewIncomingBlockEnd);
}

return NewPHI;
1659}

1661Value *RegionGenerator::getExitScalar(MemoryAccess *MA, LoopToScevMapT &LTS,
                                    ValueMapT &BBMap) {
ScopStmt *Stmt = MA->getStatement();

// TODO: Add some test cases that ensure this is really the right choice.
Loop *L = LI.getLoopFor(Stmt->getRegion()->getExit());

if (MA->isAnyPHIKind()) {
  auto Incoming = MA->getIncoming();
  assert(!Incoming.empty() &&(static_cast<void> (0))
         "PHI WRITEs must have originate from at least one incoming block")(static_cast<void> (0));

  // If there is only one incoming value, we do not need to create a PHI.
  if (Incoming.size() == 1) {
    Value *OldVal = Incoming[0].second;
    return getNewValue(*Stmt, OldVal, BBMap, LTS, L);
  }

  return buildExitPHI(MA, LTS, BBMap, L);
}

// MemoryKind::Value accesses leaving the subregion must dominate the exit
// block; just pass the copied value.
Value *OldVal = MA->getAccessValue();
return getNewValue(*Stmt, OldVal, BBMap, LTS, L);
1686}

1688void RegionGenerator::generateScalarStores(
  ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMap,
  __isl_keep isl_id_to_ast_expr *NewAccesses) {
assert(Stmt.getRegion() &&(static_cast<void> (0))
       "Block statements need to use the generateScalarStores() "(static_cast<void> (0))
       "function in the BlockGenerator")(static_cast<void> (0));

// Get the exit scalar values before generating the writes.
// This is necessary because RegionGenerator::getExitScalar may insert
// PHINodes that depend on the region's exiting blocks. But
// BlockGenerator::generateConditionalExecution may insert a new basic block
// such that the current basic block is not a direct successor of the exiting
// blocks anymore. Hence, build the PHINodes while the current block is still
// the direct successor.
SmallDenseMap<MemoryAccess *, Value *> NewExitScalars;
for (MemoryAccess *MA : Stmt) {
  if (MA->isOriginalArrayKind() || MA->isRead())
    continue;

  Value *NewVal = getExitScalar(MA, LTS, BBMap);
  NewExitScalars[MA] = NewVal;
}

for (MemoryAccess *MA : Stmt) {
  if (MA->isOriginalArrayKind() || MA->isRead())
    continue;

  isl::set AccDom = MA->getAccessRelation().domain();
  std::string Subject = MA->getId().get_name();
  generateConditionalExecution(
      Stmt, AccDom, Subject.c_str(), [&, this, MA]() {
        Value *NewVal = NewExitScalars.lookup(MA);
        assert(NewVal && "The exit scalar must be determined before")(static_cast<void> (0));
        Value *Address = getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS,
                                            BBMap, NewAccesses);
        assert((!isa<Instruction>(NewVal) ||(static_cast<void> (0))
                DT.dominates(cast<Instruction>(NewVal)->getParent(),(static_cast<void> (0))
                             Builder.GetInsertBlock())) &&(static_cast<void> (0))
               "Domination violation")(static_cast<void> (0));
        assert((!isa<Instruction>(Address) ||(static_cast<void> (0))
                DT.dominates(cast<Instruction>(Address)->getParent(),(static_cast<void> (0))
                             Builder.GetInsertBlock())) &&(static_cast<void> (0))
               "Domination violation")(static_cast<void> (0));
        Builder.CreateStore(NewVal, Address);
      });
}
1734}

1736void RegionGenerator::addOperandToPHI(ScopStmt &Stmt, PHINode *PHI,
                                    PHINode *PHICopy, BasicBlock *IncomingBB,
                                    LoopToScevMapT &LTS) {
// If the incoming block was not yet copied mark this PHI as incomplete.
// Once the block will be copied the incoming value will be added.
BasicBlock *BBCopyStart = StartBlockMap[IncomingBB];
BasicBlock *BBCopyEnd = EndBlockMap[IncomingBB];
if (!BBCopyStart) {
  assert(!BBCopyEnd)(static_cast<void> (0));
  assert(Stmt.represents(IncomingBB) &&(static_cast<void> (0))
         "Bad incoming block for PHI in non-affine region")(static_cast<void> (0));
  IncompletePHINodeMap[IncomingBB].push_back(std::make_pair(PHI, PHICopy));
  return;
}

assert(RegionMaps.count(BBCopyStart) &&(static_cast<void> (0))
       "Incoming PHI block did not have a BBMap")(static_cast<void> (0));
ValueMapT &BBCopyMap = RegionMaps[BBCopyStart];

Value *OpCopy = nullptr;

if (Stmt.represents(IncomingBB)) {
  Value *Op = PHI->getIncomingValueForBlock(IncomingBB);

  // If the current insert block is different from the PHIs incoming block
  // change it, otherwise do not.
  auto IP = Builder.GetInsertPoint();
  if (IP->getParent() != BBCopyEnd)
    Builder.SetInsertPoint(BBCopyEnd->getTerminator());
  OpCopy = getNewValue(Stmt, Op, BBCopyMap, LTS, getLoopForStmt(Stmt));
  if (IP->getParent() != BBCopyEnd)
    Builder.SetInsertPoint(&*IP);
} else {
  // All edges from outside the non-affine region become a single edge
  // in the new copy of the non-affine region. Make sure to only add the
  // corresponding edge the first time we encounter a basic block from
  // outside the non-affine region.
  if (PHICopy->getBasicBlockIndex(BBCopyEnd) >= 0)
    return;

  // Get the reloaded value.
  OpCopy = getNewValue(Stmt, PHI, BBCopyMap, LTS, getLoopForStmt(Stmt));
}

assert(OpCopy && "Incoming PHI value was not copied properly")(static_cast<void> (0));
PHICopy->addIncoming(OpCopy, BBCopyEnd);
1782}

1784void RegionGenerator::copyPHIInstruction(ScopStmt &Stmt, PHINode *PHI,
                                       ValueMapT &BBMap,
                                       LoopToScevMapT &LTS) {
unsigned NumIncoming = PHI->getNumIncomingValues();
PHINode *PHICopy =
    Builder.CreatePHI(PHI->getType(), NumIncoming, "polly." + PHI->getName());
PHICopy->moveBefore(PHICopy->getParent()->getFirstNonPHI());
BBMap[PHI] = PHICopy;

for (BasicBlock *IncomingBB : PHI->blocks())
  addOperandToPHI(Stmt, PHI, PHICopy, IncomingBB, LTS);
1795}

←

/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include/llvm/ADT/SmallVector.h

1	//===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------- C++ --===//
2	//
3	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4	// See https://llvm.org/LICENSE.txt for license information.
5	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6	//
7	//===----------------------------------------------------------------------===//
8	//
9	// This file defines the SmallVector class.
10	//
11	//===----------------------------------------------------------------------===//
12
13	#ifndef LLVM_ADT_SMALLVECTOR_H
14	#define LLVM_ADT_SMALLVECTOR_H
15
16	#include "llvm/ADT/iterator_range.h"
17	#include "llvm/Support/Compiler.h"
18	#include "llvm/Support/ErrorHandling.h"
19	#include "llvm/Support/MemAlloc.h"
20	#include "llvm/Support/type_traits.h"
21	#include <algorithm>
22	#include <cassert>
23	#include <cstddef>
24	#include <cstdlib>
25	#include <cstring>
26	#include <functional>
27	#include <initializer_list>
28	#include <iterator>
29	#include <limits>
30	#include <memory>
31	#include <new>
32	#include <type_traits>
33	#include <utility>
34
35	namespace llvm {
36
37	/// This is all the stuff common to all SmallVectors.
38	///
39	/// The template parameter specifies the type which should be used to hold the
40	/// Size and Capacity of the SmallVector, so it can be adjusted.
41	/// Using 32 bit size is desirable to shrink the size of the SmallVector.
42	/// Using 64 bit size is desirable for cases like SmallVector<char>, where a
43	/// 32 bit size would limit the vector to ~4GB. SmallVectors are used for
44	/// buffering bitcode output - which can exceed 4GB.
45	template <class Size_T> class SmallVectorBase {
46	protected:
47	void *BeginX;
48	Size_T Size = 0, Capacity;
49
50	/// The maximum value of the Size_T used.
51	static constexpr size_t SizeTypeMax() {
52	return std::numeric_limits<Size_T>::max();
53	}
54
55	SmallVectorBase() = delete;
56	SmallVectorBase(void *FirstEl, size_t TotalCapacity)
57	: BeginX(FirstEl), Capacity(TotalCapacity) {}
58
59	/// This is a helper for \a grow() that's out of line to reduce code
60	/// duplication. This function will report a fatal error if it can't grow at
61	/// least to \p MinSize.
62	void *mallocForGrow(size_t MinSize, size_t TSize, size_t &NewCapacity);
63
64	/// This is an implementation of the grow() method which only works
65	/// on POD-like data types and is out of line to reduce code duplication.
66	/// This function will report a fatal error if it cannot increase capacity.
67	void grow_pod(void *FirstEl, size_t MinSize, size_t TSize);
68
69	public:
70	size_t size() const { return Size; }
71	size_t capacity() const { return Capacity; }
72
73	LLVM_NODISCARD[[clang::warn_unused_result]] bool empty() const { return !Size; }
74
75	/// Set the array size to \p N, which the current array must have enough
76	/// capacity for.
77	///
78	/// This does not construct or destroy any elements in the vector.
79	///
80	/// Clients can use this in conjunction with capacity() to write past the end
81	/// of the buffer when they know that more elements are available, and only
82	/// update the size later. This avoids the cost of value initializing elements
83	/// which will only be overwritten.
84	void set_size(size_t N) {
85	assert(N <= capacity())(static_cast<void> (0));
86	Size = N;
87	}
88	};
89
90	template <class T>
91	using SmallVectorSizeType =
92	typename std::conditional<sizeof(T) < 4 && sizeof(void *) >= 8, uint64_t,
93	uint32_t>::type;
94
95	/// Figure out the offset of the first element.
96	template <class T, typename = void> struct SmallVectorAlignmentAndSize {
97	alignas(SmallVectorBase<SmallVectorSizeType<T>>) char Base[sizeof(
98	SmallVectorBase<SmallVectorSizeType<T>>)];
99	alignas(T) char FirstEl[sizeof(T)];
100	};
101
102	/// This is the part of SmallVectorTemplateBase which does not depend on whether
103	/// the type T is a POD. The extra dummy template argument is used by ArrayRef
104	/// to avoid unnecessarily requiring T to be complete.
105	template <typename T, typename = void>
106	class SmallVectorTemplateCommon
107	: public SmallVectorBase<SmallVectorSizeType<T>> {
108	using Base = SmallVectorBase<SmallVectorSizeType<T>>;
109
110	/// Find the address of the first element. For this pointer math to be valid
111	/// with small-size of 0 for T with lots of alignment, it's important that
112	/// SmallVectorStorage is properly-aligned even for small-size of 0.
113	void *getFirstEl() const {
114	return const_cast<void >(reinterpret_cast<const void >(
115	reinterpret_cast<const char *>(this) +
116	offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)__builtin_offsetof(SmallVectorAlignmentAndSize<T>, FirstEl )));
117	}
118	// Space after 'FirstEl' is clobbered, do not add any instance vars after it.
119
120	protected:
121	SmallVectorTemplateCommon(size_t Size) : Base(getFirstEl(), Size) {}
122
123	void grow_pod(size_t MinSize, size_t TSize) {
124	Base::grow_pod(getFirstEl(), MinSize, TSize);
125	}
126
127	/// Return true if this is a smallvector which has not had dynamic
128	/// memory allocated for it.
129	bool isSmall() const { return this->BeginX == getFirstEl(); }
130
131	/// Put this vector in a state of being small.
132	void resetToSmall() {
133	this->BeginX = getFirstEl();
134	this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
135	}
136
137	/// Return true if V is an internal reference to the given range.
138	bool isReferenceToRange(const void V, const void First, const void *Last) const {
139	// Use std::less to avoid UB.
140	std::less<> LessThan;
141	return !LessThan(V, First) && LessThan(V, Last);
142	}
143
144	/// Return true if V is an internal reference to this vector.
145	bool isReferenceToStorage(const void *V) const {
146	return isReferenceToRange(V, this->begin(), this->end());
147	}
148
149	/// Return true if First and Last form a valid (possibly empty) range in this
150	/// vector's storage.
151	bool isRangeInStorage(const void First, const void Last) const {
152	// Use std::less to avoid UB.
153	std::less<> LessThan;
154	return !LessThan(First, this->begin()) && !LessThan(Last, First) &&
155	!LessThan(this->end(), Last);
156	}
157
158	/// Return true unless Elt will be invalidated by resizing the vector to
159	/// NewSize.
160	bool isSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
161	// Past the end.
162	if (LLVM_LIKELY(!isReferenceToStorage(Elt))__builtin_expect((bool)(!isReferenceToStorage(Elt)), true))
163	return true;
164
165	// Return false if Elt will be destroyed by shrinking.
166	if (NewSize <= this->size())
167	return Elt < this->begin() + NewSize;
168
169	// Return false if we need to grow.
170	return NewSize <= this->capacity();
171	}
172
173	/// Check whether Elt will be invalidated by resizing the vector to NewSize.
174	void assertSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
175	assert(isSafeToReferenceAfterResize(Elt, NewSize) &&(static_cast<void> (0))
176	"Attempting to reference an element of the vector in an operation "(static_cast<void> (0))
177	"that invalidates it")(static_cast<void> (0));
178	}
179
180	/// Check whether Elt will be invalidated by increasing the size of the
181	/// vector by N.
182	void assertSafeToAdd(const void *Elt, size_t N = 1) {
183	this->assertSafeToReferenceAfterResize(Elt, this->size() + N);
184	}
185
186	/// Check whether any part of the range will be invalidated by clearing.
187	void assertSafeToReferenceAfterClear(const T From, const T To) {
188	if (From == To)
189	return;
190	this->assertSafeToReferenceAfterResize(From, 0);
191	this->assertSafeToReferenceAfterResize(To - 1, 0);
192	}
193	template <
194	class ItTy,
195	std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
196	bool> = false>
197	void assertSafeToReferenceAfterClear(ItTy, ItTy) {}
198
199	/// Check whether any part of the range will be invalidated by growing.
200	void assertSafeToAddRange(const T From, const T To) {
201	if (From == To)
202	return;
203	this->assertSafeToAdd(From, To - From);
204	this->assertSafeToAdd(To - 1, To - From);
205	}
206	template <
207	class ItTy,
208	std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
209	bool> = false>
210	void assertSafeToAddRange(ItTy, ItTy) {}
211
212	/// Reserve enough space to add one element, and return the updated element
213	/// pointer in case it was a reference to the storage.
214	template <class U>
215	static const T reserveForParamAndGetAddressImpl(U This, const T &Elt,
216	size_t N) {
217	size_t NewSize = This->size() + N;
218	if (LLVM_LIKELY(NewSize <= This->capacity())__builtin_expect((bool)(NewSize <= This->capacity()), true ))
219	return &Elt;
220
221	bool ReferencesStorage = false;
222	int64_t Index = -1;
223	if (!U::TakesParamByValue) {
224	if (LLVM_UNLIKELY(This->isReferenceToStorage(&Elt))__builtin_expect((bool)(This->isReferenceToStorage(&Elt )), false)) {
225	ReferencesStorage = true;
226	Index = &Elt - This->begin();
227	}
228	}
229	This->grow(NewSize);
230	return ReferencesStorage ? This->begin() + Index : &Elt;
231	}
232
233	public:
234	using size_type = size_t;
235	using difference_type = ptrdiff_t;
236	using value_type = T;
237	using iterator = T *;
238	using const_iterator = const T *;
239
240	using const_reverse_iterator = std::reverse_iterator<const_iterator>;
241	using reverse_iterator = std::reverse_iterator<iterator>;
242
243	using reference = T &;
244	using const_reference = const T &;
245	using pointer = T *;
246	using const_pointer = const T *;
247
248	using Base::capacity;
249	using Base::empty;
250	using Base::size;
251
252	// forward iterator creation methods.
253	iterator begin() { return (iterator)this->BeginX; }
254	const_iterator begin() const { return (const_iterator)this->BeginX; }
255	iterator end() { return begin() + size(); }
256	const_iterator end() const { return begin() + size(); }
257
258	// reverse iterator creation methods.
259	reverse_iterator rbegin() { return reverse_iterator(end()); }
260	const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
261	reverse_iterator rend() { return reverse_iterator(begin()); }
262	const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
263
264	size_type size_in_bytes() const { return size() * sizeof(T); }
265	size_type max_size() const {
266	return std::min(this->SizeTypeMax(), size_type(-1) / sizeof(T));
267	}
268
269	size_t capacity_in_bytes() const { return capacity() * sizeof(T); }
270
271	/// Return a pointer to the vector's buffer, even if empty().
272	pointer data() { return pointer(begin()); }
273	/// Return a pointer to the vector's buffer, even if empty().
274	const_pointer data() const { return const_pointer(begin()); }
275
276	reference operator[](size_type idx) {
277	assert(idx < size())(static_cast<void> (0));
278	return begin()[idx];
279	}
280	const_reference operator[](size_type idx) const {
281	assert(idx < size())(static_cast<void> (0));
282	return begin()[idx];
283	}
284
285	reference front() {
286	assert(!empty())(static_cast<void> (0));
287	return begin()[0];
288	}
289	const_reference front() const {
290	assert(!empty())(static_cast<void> (0));
291	return begin()[0];
292	}
293
294	reference back() {
295	assert(!empty())(static_cast<void> (0));
296	return end()[-1];
297	}
298	const_reference back() const {
299	assert(!empty())(static_cast<void> (0));
300	return end()[-1];
301	}
302	};
303
304	/// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put
305	/// method implementations that are designed to work with non-trivial T's.
306	///
307	/// We approximate is_trivially_copyable with trivial move/copy construction and
308	/// trivial destruction. While the standard doesn't specify that you're allowed
309	/// copy these types with memcpy, there is no way for the type to observe this.
310	/// This catches the important case of std::pair<POD, POD>, which is not
311	/// trivially assignable.
312	template <typename T, bool = (is_trivially_copy_constructible<T>::value) &&
313	(is_trivially_move_constructible<T>::value) &&
314	std::is_trivially_destructible<T>::value>
315	class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
316	friend class SmallVectorTemplateCommon<T>;
317
318	protected:
319	static constexpr bool TakesParamByValue = false;
320	using ValueParamT = const T &;
321
322	SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
323
324	static void destroy_range(T S, T E) {
325	while (S != E) {
326	--E;
327	E->~T();
328	}
329	}
330
331	/// Move the range [I, E) into the uninitialized memory starting with "Dest",
332	/// constructing elements as needed.
333	template<typename It1, typename It2>
334	static void uninitialized_move(It1 I, It1 E, It2 Dest) {
335	std::uninitialized_copy(std::make_move_iterator(I),
336	std::make_move_iterator(E), Dest);
337	}
338
339	/// Copy the range [I, E) onto the uninitialized memory starting with "Dest",
340	/// constructing elements as needed.
341	template<typename It1, typename It2>
342	static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
343	std::uninitialized_copy(I, E, Dest);
344	}
345
346	/// Grow the allocated memory (without initializing new elements), doubling
347	/// the size of the allocated memory. Guarantees space for at least one more
348	/// element, or MinSize more elements if specified.
349	void grow(size_t MinSize = 0);
350
351	/// Create a new allocation big enough for \p MinSize and pass back its size
352	/// in \p NewCapacity. This is the first section of \a grow().
353	T *mallocForGrow(size_t MinSize, size_t &NewCapacity) {
354	return static_cast<T *>(
355	SmallVectorBase<SmallVectorSizeType<T>>::mallocForGrow(
356	MinSize, sizeof(T), NewCapacity));
357	}
358
359	/// Move existing elements over to the new allocation \p NewElts, the middle
360	/// section of \a grow().
361	void moveElementsForGrow(T *NewElts);
362
363	/// Transfer ownership of the allocation, finishing up \a grow().
364	void takeAllocationForGrow(T *NewElts, size_t NewCapacity);
365
366	/// Reserve enough space to add one element, and return the updated element
367	/// pointer in case it was a reference to the storage.
368	const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
369	return this->reserveForParamAndGetAddressImpl(this, Elt, N);
370	}
371
372	/// Reserve enough space to add one element, and return the updated element
373	/// pointer in case it was a reference to the storage.
374	T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
375	return const_cast<T *>(
376	this->reserveForParamAndGetAddressImpl(this, Elt, N));
377	}
378
379	static T &&forward_value_param(T &&V) { return std::move(V); }
380	static const T &forward_value_param(const T &V) { return V; }
381
382	void growAndAssign(size_t NumElts, const T &Elt) {
383	// Grow manually in case Elt is an internal reference.
384	size_t NewCapacity;
385	T *NewElts = mallocForGrow(NumElts, NewCapacity);
386	std::uninitialized_fill_n(NewElts, NumElts, Elt);
387	this->destroy_range(this->begin(), this->end());
388	takeAllocationForGrow(NewElts, NewCapacity);
389	this->set_size(NumElts);
390	}
391
392	template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) {
393	// Grow manually in case one of Args is an internal reference.
394	size_t NewCapacity;
395	T *NewElts = mallocForGrow(0, NewCapacity);
396	::new ((void *)(NewElts + this->size())) T(std::forward<ArgTypes>(Args)...);
397	moveElementsForGrow(NewElts);
398	takeAllocationForGrow(NewElts, NewCapacity);
399	this->set_size(this->size() + 1);
400	return this->back();
401	}
402
403	public:
404	void push_back(const T &Elt) {
405	const T *EltPtr = reserveForParamAndGetAddress(Elt);
406	::new ((void )this->end()) T(EltPtr);
407	this->set_size(this->size() + 1);
408	}
409
410	void push_back(T &&Elt) {
411	T *EltPtr = reserveForParamAndGetAddress(Elt);
412	::new ((void )this->end()) T(::std::move(EltPtr));
413	this->set_size(this->size() + 1);
414	}
415
416	void pop_back() {
417	this->set_size(this->size() - 1);
418	this->end()->~T();
419	}
420	};
421
422	// Define this out-of-line to dissuade the C++ compiler from inlining it.
423	template <typename T, bool TriviallyCopyable>
424	void SmallVectorTemplateBase<T, TriviallyCopyable>::grow(size_t MinSize) {
425	size_t NewCapacity;
426	T *NewElts = mallocForGrow(MinSize, NewCapacity);
427	moveElementsForGrow(NewElts);
428	takeAllocationForGrow(NewElts, NewCapacity);
429	}
430
431	// Define this out-of-line to dissuade the C++ compiler from inlining it.
432	template <typename T, bool TriviallyCopyable>
433	void SmallVectorTemplateBase<T, TriviallyCopyable>::moveElementsForGrow(
434	T *NewElts) {
435	// Move the elements over.
436	this->uninitialized_move(this->begin(), this->end(), NewElts);
437
438	// Destroy the original elements.
439	destroy_range(this->begin(), this->end());
440	}
441
442	// Define this out-of-line to dissuade the C++ compiler from inlining it.
443	template <typename T, bool TriviallyCopyable>
444	void SmallVectorTemplateBase<T, TriviallyCopyable>::takeAllocationForGrow(
445	T *NewElts, size_t NewCapacity) {
446	// If this wasn't grown from the inline copy, deallocate the old space.
447	if (!this->isSmall())
448	free(this->begin());
449
450	this->BeginX = NewElts;
451	this->Capacity = NewCapacity;
452	}
453
454	/// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put
455	/// method implementations that are designed to work with trivially copyable
456	/// T's. This allows using memcpy in place of copy/move construction and
457	/// skipping destruction.
458	template <typename T>
459	class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
460	friend class SmallVectorTemplateCommon<T>;
461
462	protected:
463	/// True if it's cheap enough to take parameters by value. Doing so avoids
464	/// overhead related to mitigations for reference invalidation.
465	static constexpr bool TakesParamByValue = sizeof(T) <= 2 * sizeof(void *);
466
467	/// Either const T& or T, depending on whether it's cheap enough to take
468	/// parameters by value.
469	using ValueParamT =
470	typename std::conditional<TakesParamByValue, T, const T &>::type;
471
472	SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
473
474	// No need to do a destroy loop for POD's.
475	static void destroy_range(T , T ) {}
476
477	/// Move the range [I, E) onto the uninitialized memory
478	/// starting with "Dest", constructing elements into it as needed.
479	template<typename It1, typename It2>
480	static void uninitialized_move(It1 I, It1 E, It2 Dest) {
481	// Just do a copy.
482	uninitialized_copy(I, E, Dest);
483	}
484
485	/// Copy the range [I, E) onto the uninitialized memory
486	/// starting with "Dest", constructing elements into it as needed.
487	template<typename It1, typename It2>
488	static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
489	// Arbitrary iterator types; just use the basic implementation.
490	std::uninitialized_copy(I, E, Dest);
491	}
492
493	/// Copy the range [I, E) onto the uninitialized memory
494	/// starting with "Dest", constructing elements into it as needed.
495	template <typename T1, typename T2>
496	static void uninitialized_copy(
497	T1 I, T1 E, T2 *Dest,
498	std::enable_if_t<std::is_same<typename std::remove_const<T1>::type,
499	T2>::value> * = nullptr) {
500	// Use memcpy for PODs iterated by pointers (which includes SmallVector
501	// iterators): std::uninitialized_copy optimizes to memmove, but we can
502	// use memcpy here. Note that I and E are iterators and thus might be
503	// invalid for memcpy if they are equal.
504	if (I != E)
505	memcpy(reinterpret_cast<void >(Dest), I, (E - I) sizeof(T));
506	}
507
508	/// Double the size of the allocated memory, guaranteeing space for at
509	/// least one more element or MinSize if specified.
510	void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }
511
512	/// Reserve enough space to add one element, and return the updated element
513	/// pointer in case it was a reference to the storage.
514	const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
515	return this->reserveForParamAndGetAddressImpl(this, Elt, N);
516	}
517
518	/// Reserve enough space to add one element, and return the updated element
519	/// pointer in case it was a reference to the storage.
520	T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
521	return const_cast<T *>(
522	this->reserveForParamAndGetAddressImpl(this, Elt, N));
523	}
524
525	/// Copy \p V or return a reference, depending on \a ValueParamT.
526	static ValueParamT forward_value_param(ValueParamT V) { return V; }
527
528	void growAndAssign(size_t NumElts, T Elt) {
529	// Elt has been copied in case it's an internal reference, side-stepping
530	// reference invalidation problems without losing the realloc optimization.
531	this->set_size(0);
532	this->grow(NumElts);
533	std::uninitialized_fill_n(this->begin(), NumElts, Elt);
534	this->set_size(NumElts);
535	}
536
537	template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) {
538	// Use push_back with a copy in case Args has an internal reference,
539	// side-stepping reference invalidation problems without losing the realloc
540	// optimization.
541	push_back(T(std::forward<ArgTypes>(Args)...));
542	return this->back();
543	}
544
545	public:
546	void push_back(ValueParamT Elt) {
547	const T *EltPtr = reserveForParamAndGetAddress(Elt);
548	memcpy(reinterpret_cast<void *>(this->end()), EltPtr, sizeof(T));
549	this->set_size(this->size() + 1);
550	}
551
552	void pop_back() { this->set_size(this->size() - 1); }
553	};
554
555	/// This class consists of common code factored out of the SmallVector class to
556	/// reduce code duplication based on the SmallVector 'N' template parameter.
557	template <typename T>
558	class SmallVectorImpl : public SmallVectorTemplateBase<T> {
559	using SuperClass = SmallVectorTemplateBase<T>;
560
561	public:
562	using iterator = typename SuperClass::iterator;
563	using const_iterator = typename SuperClass::const_iterator;
564	using reference = typename SuperClass::reference;
565	using size_type = typename SuperClass::size_type;
566
567	protected:
568	using SmallVectorTemplateBase<T>::TakesParamByValue;
569	using ValueParamT = typename SuperClass::ValueParamT;
570
571	// Default ctor - Initialize to empty.
572	explicit SmallVectorImpl(unsigned N)
573	: SmallVectorTemplateBase<T>(N) {}
574
575	public:
576	SmallVectorImpl(const SmallVectorImpl &) = delete;
577
578	~SmallVectorImpl() {
579	// Subclass has already destructed this vector's elements.
580	// If this wasn't grown from the inline copy, deallocate the old space.
581	if (!this->isSmall())
582	free(this->begin());
583	}
584
585	void clear() {
586	this->destroy_range(this->begin(), this->end());
587	this->Size = 0;
588	}
589
590	private:
591	template <bool ForOverwrite> void resizeImpl(size_type N) {
592	if (N < this->size()) {
593	this->pop_back_n(this->size() - N);
594	} else if (N > this->size()) {
595	this->reserve(N);
596	for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
597	if (ForOverwrite)
598	new (&*I) T;
599	else
600	new (&*I) T();
601	this->set_size(N);
602	}
603	}
604
605	public:
606	void resize(size_type N) { resizeImpl<false>(N); }
607
608	/// Like resize, but \ref T is POD, the new values won't be initialized.
609	void resize_for_overwrite(size_type N) { resizeImpl<true>(N); }
610
611	void resize(size_type N, ValueParamT NV) {
612	if (N == this->size())
613	return;
614
615	if (N < this->size()) {
616	this->pop_back_n(this->size() - N);
617	return;
618	}
619
620	// N > this->size(). Defer to append.
621	this->append(N - this->size(), NV);
622	}
623
624	void reserve(size_type N) {
625	if (this->capacity() < N)
626	this->grow(N);
627	}
628
629	void pop_back_n(size_type NumItems) {
630	assert(this->size() >= NumItems)(static_cast<void> (0));
631	this->destroy_range(this->end() - NumItems, this->end());
632	this->set_size(this->size() - NumItems);
633	}
634
635	LLVM_NODISCARD[[clang::warn_unused_result]] T pop_back_val() {
636	T Result = ::std::move(this->back());
637	this->pop_back();
638	return Result;
639	}
640
641	void swap(SmallVectorImpl &RHS);
642
643	/// Add the specified range to the end of the SmallVector.
644	template <typename in_iter,
645	typename = std::enable_if_t<std::is_convertible<
646	typename std::iterator_traits<in_iter>::iterator_category,
647	std::input_iterator_tag>::value>>
648	void append(in_iter in_start, in_iter in_end) {
649	this->assertSafeToAddRange(in_start, in_end);
650	size_type NumInputs = std::distance(in_start, in_end);
651	this->reserve(this->size() + NumInputs);
652	this->uninitialized_copy(in_start, in_end, this->end());
653	this->set_size(this->size() + NumInputs);
654	}
655
656	/// Append \p NumInputs copies of \p Elt to the end.
657	void append(size_type NumInputs, ValueParamT Elt) {
658	const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumInputs);
659	std::uninitialized_fill_n(this->end(), NumInputs, *EltPtr);
660	this->set_size(this->size() + NumInputs);
661	}
662
663	void append(std::initializer_list<T> IL) {
664	append(IL.begin(), IL.end());
665	}
666
667	void append(const SmallVectorImpl &RHS) { append(RHS.begin(), RHS.end()); }
668
669	void assign(size_type NumElts, ValueParamT Elt) {
670	// Note that Elt could be an internal reference.
671	if (NumElts > this->capacity()) {
672	this->growAndAssign(NumElts, Elt);
673	return;
674	}
675
676	// Assign over existing elements.
677	std::fill_n(this->begin(), std::min(NumElts, this->size()), Elt);
678	if (NumElts > this->size())
679	std::uninitialized_fill_n(this->end(), NumElts - this->size(), Elt);
680	else if (NumElts < this->size())
681	this->destroy_range(this->begin() + NumElts, this->end());
682	this->set_size(NumElts);
683	}
684
685	// FIXME: Consider assigning over existing elements, rather than clearing &
686	// re-initializing them - for all assign(...) variants.
687
688	template <typename in_iter,
689	typename = std::enable_if_t<std::is_convertible<
690	typename std::iterator_traits<in_iter>::iterator_category,
691	std::input_iterator_tag>::value>>
692	void assign(in_iter in_start, in_iter in_end) {
693	this->assertSafeToReferenceAfterClear(in_start, in_end);
694	clear();
695	append(in_start, in_end);
696	}
697
698	void assign(std::initializer_list<T> IL) {
699	clear();
700	append(IL);
701	}
702
703	void assign(const SmallVectorImpl &RHS) { assign(RHS.begin(), RHS.end()); }
704
705	iterator erase(const_iterator CI) {
706	// Just cast away constness because this is a non-const member function.
707	iterator I = const_cast<iterator>(CI);
708
709	assert(this->isReferenceToStorage(CI) && "Iterator to erase is out of bounds.")(static_cast<void> (0));
710
711	iterator N = I;
712	// Shift all elts down one.
713	std::move(I+1, this->end(), I);
714	// Drop the last elt.
715	this->pop_back();
716	return(N);
717	}
718
719	iterator erase(const_iterator CS, const_iterator CE) {
720	// Just cast away constness because this is a non-const member function.
721	iterator S = const_cast<iterator>(CS);
722	iterator E = const_cast<iterator>(CE);
723
724	assert(this->isRangeInStorage(S, E) && "Range to erase is out of bounds.")(static_cast<void> (0));
725
726	iterator N = S;
727	// Shift all elts down.
728	iterator I = std::move(E, this->end(), S);
729	// Drop the last elts.
730	this->destroy_range(I, this->end());
731	this->set_size(I - this->begin());
732	return(N);
733	}
734
735	private:
736	template <class ArgType> iterator insert_one_impl(iterator I, ArgType &&Elt) {
737	// Callers ensure that ArgType is derived from T.
738	static_assert(
739	std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>,
740	T>::value,
741	"ArgType must be derived from T!");
742
743	if (I == this->end()) { // Important special case for empty vector.
744	this->push_back(::std::forward<ArgType>(Elt));
745	return this->end()-1;
746	}
747
748	assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")(static_cast<void> (0));
749
750	// Grow if necessary.
751	size_t Index = I - this->begin();
752	std::remove_reference_t<ArgType> *EltPtr =
753	this->reserveForParamAndGetAddress(Elt);
754	I = this->begin() + Index;
755
756	::new ((void*) this->end()) T(::std::move(this->back()));
757	// Push everything else over.
758	std::move_backward(I, this->end()-1, this->end());
759	this->set_size(this->size() + 1);
760
761	// If we just moved the element we're inserting, be sure to update
762	// the reference (never happens if TakesParamByValue).
763	static_assert(!TakesParamByValue \|\| std::is_same<ArgType, T>::value,
764	"ArgType must be 'T' when taking by value!");
765	if (!TakesParamByValue && this->isReferenceToRange(EltPtr, I, this->end()))
766	++EltPtr;
767
768	I = ::std::forward<ArgType>(EltPtr);
769	return I;
770	}
771
772	public:
773	iterator insert(iterator I, T &&Elt) {
774	return insert_one_impl(I, this->forward_value_param(std::move(Elt)));
775	}
776
777	iterator insert(iterator I, const T &Elt) {
778	return insert_one_impl(I, this->forward_value_param(Elt));
779	}
780
781	iterator insert(iterator I, size_type NumToInsert, ValueParamT Elt) {
782	// Convert iterator to elt# to avoid invalidating iterator when we reserve()
783	size_t InsertElt = I - this->begin();
784
785	if (I == this->end()) { // Important special case for empty vector.
786	append(NumToInsert, Elt);
787	return this->begin()+InsertElt;
788	}
789
790	assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")(static_cast<void> (0));
791
792	// Ensure there is enough space, and get the (maybe updated) address of
793	// Elt.
794	const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumToInsert);
795
796	// Uninvalidate the iterator.
797	I = this->begin()+InsertElt;
798
799	// If there are more elements between the insertion point and the end of the
800	// range than there are being inserted, we can use a simple approach to
801	// insertion. Since we already reserved space, we know that this won't
802	// reallocate the vector.
803	if (size_t(this->end()-I) >= NumToInsert) {
804	T *OldEnd = this->end();
805	append(std::move_iterator<iterator>(this->end() - NumToInsert),
806	std::move_iterator<iterator>(this->end()));
807
808	// Copy the existing elements that get replaced.
809	std::move_backward(I, OldEnd-NumToInsert, OldEnd);
810
811	// If we just moved the element we're inserting, be sure to update
812	// the reference (never happens if TakesParamByValue).
813	if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
814	EltPtr += NumToInsert;
815
816	std::fill_n(I, NumToInsert, *EltPtr);
817	return I;
818	}
819
820	// Otherwise, we're inserting more elements than exist already, and we're
821	// not inserting at the end.
822
823	// Move over the elements that we're about to overwrite.
824	T *OldEnd = this->end();
825	this->set_size(this->size() + NumToInsert);
826	size_t NumOverwritten = OldEnd-I;
827	this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
828
829	// If we just moved the element we're inserting, be sure to update
830	// the reference (never happens if TakesParamByValue).
831	if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
832	EltPtr += NumToInsert;
833
834	// Replace the overwritten part.
835	std::fill_n(I, NumOverwritten, *EltPtr);
836
837	// Insert the non-overwritten middle part.
838	std::uninitialized_fill_n(OldEnd, NumToInsert - NumOverwritten, *EltPtr);
839	return I;
840	}
841
842	template <typename ItTy,
843	typename = std::enable_if_t<std::is_convertible<
844	typename std::iterator_traits<ItTy>::iterator_category,
845	std::input_iterator_tag>::value>>
846	iterator insert(iterator I, ItTy From, ItTy To) {
847	// Convert iterator to elt# to avoid invalidating iterator when we reserve()
848	size_t InsertElt = I - this->begin();
849
850	if (I == this->end()) { // Important special case for empty vector.
851	append(From, To);
852	return this->begin()+InsertElt;
853	}
854
855	assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")(static_cast<void> (0));
856
857	// Check that the reserve that follows doesn't invalidate the iterators.
858	this->assertSafeToAddRange(From, To);
859
860	size_t NumToInsert = std::distance(From, To);
861
862	// Ensure there is enough space.
863	reserve(this->size() + NumToInsert);
864
865	// Uninvalidate the iterator.
866	I = this->begin()+InsertElt;
867
868	// If there are more elements between the insertion point and the end of the
869	// range than there are being inserted, we can use a simple approach to
870	// insertion. Since we already reserved space, we know that this won't
871	// reallocate the vector.
872	if (size_t(this->end()-I) >= NumToInsert) {
873	T *OldEnd = this->end();
874	append(std::move_iterator<iterator>(this->end() - NumToInsert),
875	std::move_iterator<iterator>(this->end()));
876
877	// Copy the existing elements that get replaced.
878	std::move_backward(I, OldEnd-NumToInsert, OldEnd);
879
880	std::copy(From, To, I);
881	return I;
882	}
883
884	// Otherwise, we're inserting more elements than exist already, and we're
885	// not inserting at the end.
886
887	// Move over the elements that we're about to overwrite.
888	T *OldEnd = this->end();
889	this->set_size(this->size() + NumToInsert);
890	size_t NumOverwritten = OldEnd-I;
891	this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
892
893	// Replace the overwritten part.
894	for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
895	J = From;
896	++J; ++From;
897	}
898
899	// Insert the non-overwritten middle part.
900	this->uninitialized_copy(From, To, OldEnd);
901	return I;
902	}
903
904	void insert(iterator I, std::initializer_list<T> IL) {
905	insert(I, IL.begin(), IL.end());
906	}
907
908	template <typename... ArgTypes> reference emplace_back(ArgTypes &&... Args) {
909	if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity ()), false))
910	return this->growAndEmplaceBack(std::forward<ArgTypes>(Args)...);
911
912	::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
913	this->set_size(this->size() + 1);
914	return this->back();
915	}
916
917	SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
918
919	SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
920
921	bool operator==(const SmallVectorImpl &RHS) const {
922	if (this->size() != RHS.size()) return false;
923	return std::equal(this->begin(), this->end(), RHS.begin());
924	}
925	bool operator!=(const SmallVectorImpl &RHS) const {
926	return !(*this == RHS);
927	}
928
929	bool operator<(const SmallVectorImpl &RHS) const {
930	return std::lexicographical_compare(this->begin(), this->end(),
931	RHS.begin(), RHS.end());
932	}
933	};
934
935	template <typename T>
936	void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
937	if (this == &RHS) return;
938
939	// We can only avoid copying elements if neither vector is small.
940	if (!this->isSmall() && !RHS.isSmall()) {
941	std::swap(this->BeginX, RHS.BeginX);
942	std::swap(this->Size, RHS.Size);
943	std::swap(this->Capacity, RHS.Capacity);
944	return;
945	}
946	this->reserve(RHS.size());
947	RHS.reserve(this->size());
948
949	// Swap the shared elements.
950	size_t NumShared = this->size();
951	if (NumShared > RHS.size()) NumShared = RHS.size();
952	for (size_type i = 0; i != NumShared; ++i)
953	std::swap((*this)[i], RHS[i]);
954
955	// Copy over the extra elts.
956	if (this->size() > RHS.size()) {
957	size_t EltDiff = this->size() - RHS.size();
958	this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
959	RHS.set_size(RHS.size() + EltDiff);
960	this->destroy_range(this->begin()+NumShared, this->end());
961	this->set_size(NumShared);
962	} else if (RHS.size() > this->size()) {
963	size_t EltDiff = RHS.size() - this->size();
964	this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
965	this->set_size(this->size() + EltDiff);
966	this->destroy_range(RHS.begin()+NumShared, RHS.end());
967	RHS.set_size(NumShared);
968	}
969	}
970
971	template <typename T>
972	SmallVectorImpl<T> &SmallVectorImpl<T>::
973	operator=(const SmallVectorImpl<T> &RHS) {
974	// Avoid self-assignment.
975	if (this == &RHS) return *this;
976
977	// If we already have sufficient space, assign the common elements, then
978	// destroy any excess.
979	size_t RHSSize = RHS.size();
980	size_t CurSize = this->size();
981	if (CurSize >= RHSSize) {
982	// Assign common elements.
983	iterator NewEnd;
984	if (RHSSize)
985	NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
986	else
987	NewEnd = this->begin();
988
989	// Destroy excess elements.
990	this->destroy_range(NewEnd, this->end());
991
992	// Trim.
993	this->set_size(RHSSize);
994	return *this;
995	}
996
997	// If we have to grow to have enough elements, destroy the current elements.
998	// This allows us to avoid copying them during the grow.
999	// FIXME: don't do this if they're efficiently moveable.
1000	if (this->capacity() < RHSSize) {
1001	// Destroy current elements.
1002	this->clear();
1003	CurSize = 0;
1004	this->grow(RHSSize);
1005	} else if (CurSize) {
1006	// Otherwise, use assignment for the already-constructed elements.
1007	std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
1008	}
1009
1010	// Copy construct the new elements in place.
1011	this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
1012	this->begin()+CurSize);
1013
1014	// Set end.
1015	this->set_size(RHSSize);
1016	return *this;
1017	}
1018
1019	template <typename T>
1020	SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
1021	// Avoid self-assignment.
1022	if (this == &RHS) return *this;
1023
1024	// If the RHS isn't small, clear this vector and then steal its buffer.
1025	if (!RHS.isSmall()) {
1026	this->destroy_range(this->begin(), this->end());
1027	if (!this->isSmall()) free(this->begin());
1028	this->BeginX = RHS.BeginX;
1029	this->Size = RHS.Size;
1030	this->Capacity = RHS.Capacity;
1031	RHS.resetToSmall();
1032	return *this;
1033	}
1034
1035	// If we already have sufficient space, assign the common elements, then
1036	// destroy any excess.
1037	size_t RHSSize = RHS.size();
1038	size_t CurSize = this->size();
1039	if (CurSize >= RHSSize) {
1040	// Assign common elements.
1041	iterator NewEnd = this->begin();
1042	if (RHSSize)
1043	NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
1044
1045	// Destroy excess elements and trim the bounds.
1046	this->destroy_range(NewEnd, this->end());
1047	this->set_size(RHSSize);
1048
1049	// Clear the RHS.
1050	RHS.clear();
1051
1052	return *this;
1053	}
1054
1055	// If we have to grow to have enough elements, destroy the current elements.
1056	// This allows us to avoid copying them during the grow.
1057	// FIXME: this may not actually make any sense if we can efficiently move
1058	// elements.
1059	if (this->capacity() < RHSSize) {
1060	// Destroy current elements.
1061	this->clear();
1062	CurSize = 0;
1063	this->grow(RHSSize);
1064	} else if (CurSize) {
1065	// Otherwise, use assignment for the already-constructed elements.
1066	std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
1067	}
1068
1069	// Move-construct the new elements in place.
1070	this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
1071	this->begin()+CurSize);
1072
1073	// Set end.
1074	this->set_size(RHSSize);
1075
1076	RHS.clear();
1077	return *this;
1078	}
1079
1080	/// Storage for the SmallVector elements. This is specialized for the N=0 case
1081	/// to avoid allocating unnecessary storage.
1082	template <typename T, unsigned N>
1083	struct SmallVectorStorage {
1084	alignas(T) char InlineElts[N * sizeof(T)];
1085	};
1086
1087	/// We need the storage to be properly aligned even for small-size of 0 so that
1088	/// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
1089	/// well-defined.
1090	template <typename T> struct alignas(T) SmallVectorStorage<T, 0> {};
1091
1092	/// Forward declaration of SmallVector so that
1093	/// calculateSmallVectorDefaultInlinedElements can reference
1094	/// `sizeof(SmallVector<T, 0>)`.
1095	template <typename T, unsigned N> class LLVM_GSL_OWNER[[gsl::Owner]] SmallVector;
1096
1097	/// Helper class for calculating the default number of inline elements for
1098	/// `SmallVector<T>`.
1099	///
1100	/// This should be migrated to a constexpr function when our minimum
1101	/// compiler support is enough for multi-statement constexpr functions.
1102	template <typename T> struct CalculateSmallVectorDefaultInlinedElements {
1103	// Parameter controlling the default number of inlined elements
1104	// for `SmallVector<T>`.
1105	//
1106	// The default number of inlined elements ensures that
1107	// 1. There is at least one inlined element.
1108	// 2. `sizeof(SmallVector<T>) <= kPreferredSmallVectorSizeof` unless
1109	// it contradicts 1.
1110	static constexpr size_t kPreferredSmallVectorSizeof = 64;
1111
1112	// static_assert that sizeof(T) is not "too big".
1113	//
1114	// Because our policy guarantees at least one inlined element, it is possible
1115	// for an arbitrarily large inlined element to allocate an arbitrarily large
1116	// amount of inline storage. We generally consider it an antipattern for a
1117	// SmallVector to allocate an excessive amount of inline storage, so we want
1118	// to call attention to these cases and make sure that users are making an
1119	// intentional decision if they request a lot of inline storage.
1120	//
1121	// We want this assertion to trigger in pathological cases, but otherwise
1122	// not be too easy to hit. To accomplish that, the cutoff is actually somewhat
1123	// larger than kPreferredSmallVectorSizeof (otherwise,
1124	// `SmallVector<SmallVector<T>>` would be one easy way to trip it, and that
1125	// pattern seems useful in practice).
1126	//
1127	// One wrinkle is that this assertion is in theory non-portable, since
1128	// sizeof(T) is in general platform-dependent. However, we don't expect this
1129	// to be much of an issue, because most LLVM development happens on 64-bit
1130	// hosts, and therefore sizeof(T) is expected to decrease when compiled for
1131	// 32-bit hosts, dodging the issue. The reverse situation, where development
1132	// happens on a 32-bit host and then fails due to sizeof(T) increasing on a
1133	// 64-bit host, is expected to be very rare.
1134	static_assert(
1135	sizeof(T) <= 256,
1136	"You are trying to use a default number of inlined elements for "
1137	"`SmallVector<T>` but `sizeof(T)` is really big! Please use an "
1138	"explicit number of inlined elements with `SmallVector<T, N>` to make "
1139	"sure you really want that much inline storage.");
1140
1141	// Discount the size of the header itself when calculating the maximum inline
1142	// bytes.
1143	static constexpr size_t PreferredInlineBytes =
1144	kPreferredSmallVectorSizeof - sizeof(SmallVector<T, 0>);
1145	static constexpr size_t NumElementsThatFit = PreferredInlineBytes / sizeof(T);
1146	static constexpr size_t value =
1147	NumElementsThatFit == 0 ? 1 : NumElementsThatFit;
1148	};
1149
1150	/// This is a 'vector' (really, a variable-sized array), optimized
1151	/// for the case when the array is small. It contains some number of elements
1152	/// in-place, which allows it to avoid heap allocation when the actual number of
1153	/// elements is below that threshold. This allows normal "small" cases to be
1154	/// fast without losing generality for large inputs.
1155	///
1156	/// \note
1157	/// In the absence of a well-motivated choice for the number of inlined
1158	/// elements \p N, it is recommended to use \c SmallVector<T> (that is,
1159	/// omitting the \p N). This will choose a default number of inlined elements
1160	/// reasonable for allocation on the stack (for example, trying to keep \c
1161	/// sizeof(SmallVector<T>) around 64 bytes).
1162	///
1163	/// \warning This does not attempt to be exception safe.
1164	///
1165	/// \see https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h
1166	template <typename T,
1167	unsigned N = CalculateSmallVectorDefaultInlinedElements<T>::value>
1168	class LLVM_GSL_OWNER[[gsl::Owner]] SmallVector : public SmallVectorImpl<T>,
1169	SmallVectorStorage<T, N> {
1170	public:
1171	SmallVector() : SmallVectorImpl<T>(N) {}
1172
1173	~SmallVector() {
1174	// Destroy the constructed elements in the vector.
1175	this->destroy_range(this->begin(), this->end());
1176	}
1177
1178	explicit SmallVector(size_t Size, const T &Value = T())
1179	: SmallVectorImpl<T>(N) {
1180	this->assign(Size, Value);
1181	}
1182
1183	template <typename ItTy,
1184	typename = std::enable_if_t<std::is_convertible<
1185	typename std::iterator_traits<ItTy>::iterator_category,
1186	std::input_iterator_tag>::value>>
1187	SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
1188	this->append(S, E);
1189	}
1190
1191	template <typename RangeTy>
1192	explicit SmallVector(const iterator_range<RangeTy> &R)
1193	: SmallVectorImpl<T>(N) {
1194	this->append(R.begin(), R.end());
1195	}
1196
1197	SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
1198	this->assign(IL);
1199	}
1200
1201	SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
1202	if (!RHS.empty())
1203	SmallVectorImpl<T>::operator=(RHS);
1204	}
1205
1206	SmallVector &operator=(const SmallVector &RHS) {
1207	SmallVectorImpl<T>::operator=(RHS);
1208	return *this;
1209	}
1210
1211	SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
1212	if (!RHS.empty())
1213	SmallVectorImpl<T>::operator=(::std::move(RHS));
1214	}
1215
1216	SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {
1217	if (!RHS.empty())
1218	SmallVectorImpl<T>::operator=(::std::move(RHS));
1219	}
1220
1221	SmallVector &operator=(SmallVector &&RHS) {
1222	SmallVectorImpl<T>::operator=(::std::move(RHS));
1223	return *this;
1224	}
1225
1226	SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
1227	SmallVectorImpl<T>::operator=(::std::move(RHS));
1228	return *this;
1229	}
1230
1231	SmallVector &operator=(std::initializer_list<T> IL) {
1232	this->assign(IL);
1233	return *this;
1234	}
1235	};
1236
1237	template <typename T, unsigned N>
1238	inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
1239	return X.capacity_in_bytes();
1240	}
1241
1242	/// Given a range of type R, iterate the entire range and return a
1243	/// SmallVector with elements of the vector. This is useful, for example,
1244	/// when you want to iterate a range and then sort the results.
1245	template <unsigned Size, typename R>
1246	SmallVector<typename std::remove_const<typename std::remove_reference<
1247	decltype(*std::begin(std::declval<R &>()))>::type>::type,
1248	Size>
1249	to_vector(R &&Range) {
1250	return {std::begin(Range), std::end(Range)};
1251	}
1252
1253	} // end namespace llvm
1254
1255	namespace std {
1256
1257	/// Implement std::swap in terms of SmallVector swap.
1258	template<typename T>
1259	inline void
1260	swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
1261	LHS.swap(RHS);
1262	}
1263
1264	/// Implement std::swap in terms of SmallVector swap.
1265	template<typename T, unsigned N>
1266	inline void
1267	swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
1268	LHS.swap(RHS);
1269	}
1270
1271	} // end namespace std
1272
1273	#endif // LLVM_ADT_SMALLVECTOR_H