path: root/polly/lib/Analysis/ScopBuilder.cpp

//===- ScopBuilder.cpp ---------------------------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Create a polyhedral description for a static control flow region.
//
// The pass creates a polyhedral description of the Scops detected by the SCoP
// detection derived from their LLVM-IR code.
//
//===----------------------------------------------------------------------===//

#include "polly/ScopBuilder.h"
#include "polly/Options.h"
#include "polly/Support/GICHelper.h"
#include "polly/Support/SCEVValidator.h"
#include "llvm/Analysis/RegionIterator.h"
#include "llvm/IR/DiagnosticInfo.h"

using namespace llvm;
using namespace polly;

#define DEBUG_TYPE "polly-scops"

STATISTIC(ScopFound, "Number of valid Scops");
STATISTIC(RichScopFound, "Number of Scops containing a loop");

// If the loop is nonaffine/boxed, return the first non-boxed surrounding loop
// for Polly. If the loop is affine, return the loop itself. Do not call
// `getSCEVAtScope()` on the result of `getFirstNonBoxedLoopFor()`, as we need
// to analyze the memory accesses of the nonaffine/boxed loops.
static Loop *getFirstNonBoxedLoopFor(Loop *L, LoopInfo &LI,
                                     const BoxedLoopsSetTy &BoxedLoops) {
  while (BoxedLoops.count(L))
    L = L->getParentLoop();
  return L;
}

static cl::opt<bool> ModelReadOnlyScalars(
    "polly-analyze-read-only-scalars",
    cl::desc("Model read-only scalar values in the scop description"),
    cl::Hidden, cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory));

void ScopBuilder::buildPHIAccesses(PHINode *PHI, Region *NonAffineSubRegion,
                                   bool IsExitBlock) {

  // PHI nodes that are in the exit block of the region, hence if IsExitBlock is
  // true, are not modeled as ordinary PHI nodes as they are not part of the
  // region. However, we model the operands in the predecessor blocks that are
  // part of the region as regular scalar accesses.

  // If we can synthesize a PHI we can skip it, however only if it is in
  // the region. If it is not it can only be in the exit block of the region.
  // In this case we model the operands but not the PHI itself.
  auto *Scope = LI.getLoopFor(PHI->getParent());
  if (!IsExitBlock && canSynthesize(PHI, *scop, &LI, &SE, Scope))
    return;

  // PHI nodes are modeled as if they had been demoted prior to the SCoP
  // detection. Hence, the PHI is a load of a new memory location in which the
  // incoming value was written at the end of the incoming basic block.
  bool OnlyNonAffineSubRegionOperands = true;
  for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) {
    Value *Op = PHI->getIncomingValue(u);
    BasicBlock *OpBB = PHI->getIncomingBlock(u);

    // Do not build scalar dependences inside a non-affine subregion.
    if (NonAffineSubRegion && NonAffineSubRegion->contains(OpBB))
      continue;

    OnlyNonAffineSubRegionOperands = false;
    ensurePHIWrite(PHI, OpBB, Op, IsExitBlock);
  }

  if (!OnlyNonAffineSubRegionOperands && !IsExitBlock) {
    addPHIReadAccess(PHI);
  }
}

void ScopBuilder::buildScalarDependences(Instruction *Inst) {
  assert(!isa<PHINode>(Inst));

  // Pull-in required operands.
  for (Use &Op : Inst->operands())
    ensureValueRead(Op.get(), Inst->getParent());
}

void ScopBuilder::buildEscapingDependences(Instruction *Inst) {
  // Check for uses of this instruction outside the scop. Because we do not
  // iterate over such instructions and therefore did not "ensure" the existence
  // of a write, we must determine such use here.
  for (Use &U : Inst->uses()) {
    Instruction *UI = dyn_cast<Instruction>(U.getUser());
    if (!UI)
      continue;

    BasicBlock *UseParent = getUseBlock(U);
    BasicBlock *UserParent = UI->getParent();

    // An escaping value is either used by an instruction not within the scop,
    // or (when the scop region's exit needs to be simplified) by a PHI in the
    // scop's exit block. This is because region simplification before code
    // generation inserts new basic blocks before the PHI such that its incoming
    // blocks are not in the scop anymore.
    if (!scop->contains(UseParent) ||
        (isa<PHINode>(UI) && scop->isExit(UserParent) &&
         scop->hasSingleExitEdge())) {
      // At least one escaping use found.
      ensureValueWrite(Inst);
      break;
    }
  }
}

bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, Loop *L) {
  Value *Val = Inst.getValueOperand();
  Type *ElementType = Val->getType();
  Value *Address = Inst.getPointerOperand();
  const SCEV *AccessFunction = SE.getSCEVAtScope(Address, L);
  const SCEVUnknown *BasePointer =
      dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
  enum MemoryAccess::AccessType AccType =
      isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;

  if (auto *BitCast = dyn_cast<BitCastInst>(Address)) {
    auto *Src = BitCast->getOperand(0);
    auto *SrcTy = Src->getType();
    auto *DstTy = BitCast->getType();
    // Do not try to delinearize non-sized (opaque) pointers.
    if ((SrcTy->isPointerTy() && !SrcTy->getPointerElementType()->isSized()) ||
        (DstTy->isPointerTy() && !DstTy->getPointerElementType()->isSized())) {
      return false;
    }
    if (SrcTy->isPointerTy() && DstTy->isPointerTy() &&
        DL.getTypeAllocSize(SrcTy->getPointerElementType()) ==
            DL.getTypeAllocSize(DstTy->getPointerElementType()))
      Address = Src;
  }

  auto *GEP = dyn_cast<GetElementPtrInst>(Address);
  if (!GEP)
    return false;

  std::vector<const SCEV *> Subscripts;
  std::vector<int> Sizes;
  std::tie(Subscripts, Sizes) = getIndexExpressionsFromGEP(GEP, SE);
  auto *BasePtr = GEP->getOperand(0);

  if (auto *BasePtrCast = dyn_cast<BitCastInst>(BasePtr))
    BasePtr = BasePtrCast->getOperand(0);

  // Check for identical base pointers to ensure that we do not miss index
  // offsets that have been added before this GEP is applied.
  if (BasePtr != BasePointer->getValue())
    return false;

  std::vector<const SCEV *> SizesSCEV;

  const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();

  Loop *SurroundingLoop = getFirstNonBoxedLoopFor(L, LI, scop->getBoxedLoops());
  for (auto *Subscript : Subscripts) {
    InvariantLoadsSetTy AccessILS;
    if (!isAffineExpr(&scop->getRegion(), SurroundingLoop, Subscript, SE,
                      &AccessILS))
      return false;

    for (LoadInst *LInst : AccessILS)
      if (!ScopRIL.count(LInst))
        return false;
  }

  if (Sizes.empty())
    return false;

  for (auto V : Sizes)
    SizesSCEV.push_back(SE.getSCEV(
        ConstantInt::get(IntegerType::getInt64Ty(BasePtr->getContext()), V)));

  addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, true,
                 Subscripts, SizesSCEV, Val);
  return true;
}

bool ScopBuilder::buildAccessMultiDimParam(MemAccInst Inst, Loop *L) {
  if (!PollyDelinearize)
    return false;

  Value *Address = Inst.getPointerOperand();
  Value *Val = Inst.getValueOperand();
  Type *ElementType = Val->getType();
  unsigned ElementSize = DL.getTypeAllocSize(ElementType);
  enum MemoryAccess::AccessType AccType =
      isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;

  const SCEV *AccessFunction = SE.getSCEVAtScope(Address, L);
  const SCEVUnknown *BasePointer =
      dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));

  assert(BasePointer && "Could not find base pointer");

  auto &InsnToMemAcc = scop->getInsnToMemAccMap();
  auto AccItr = InsnToMemAcc.find(Inst);
  if (AccItr == InsnToMemAcc.end())
    return false;

  std::vector<const SCEV *> Sizes(
      AccItr->second.Shape->DelinearizedSizes.begin(),
      AccItr->second.Shape->DelinearizedSizes.end());
  // Remove the element size. This information is already provided by the
  // ElementSize parameter. In case the element size of this access and the
  // element size used for delinearization differs the delinearization is
  // incorrect. Hence, we invalidate the scop.
  //
  // TODO: Handle delinearization with differing element sizes.
  auto DelinearizedSize =
      cast<SCEVConstant>(Sizes.back())->getAPInt().getSExtValue();
  Sizes.pop_back();
  if (ElementSize != DelinearizedSize)
    scop->invalidate(DELINEARIZATION, Inst->getDebugLoc());

  addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, true,
                 AccItr->second.DelinearizedSubscripts, Sizes, Val);
  return true;
}

bool ScopBuilder::buildAccessMemIntrinsic(MemAccInst Inst, Loop *L) {
  auto *MemIntr = dyn_cast_or_null<MemIntrinsic>(Inst);

  if (MemIntr == nullptr)
    return false;

  auto *LengthVal = SE.getSCEVAtScope(MemIntr->getLength(), L);
  assert(LengthVal);

  // Check if the length val is actually affine or if we overapproximate it
  InvariantLoadsSetTy AccessILS;
  const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();

  Loop *SurroundingLoop = getFirstNonBoxedLoopFor(L, LI, scop->getBoxedLoops());
  bool LengthIsAffine = isAffineExpr(&scop->getRegion(), SurroundingLoop,
                                     LengthVal, SE, &AccessILS);
  for (LoadInst *LInst : AccessILS)
    if (!ScopRIL.count(LInst))
      LengthIsAffine = false;
  if (!LengthIsAffine)
    LengthVal = nullptr;

  auto *DestPtrVal = MemIntr->getDest();
  assert(DestPtrVal);

  auto *DestAccFunc = SE.getSCEVAtScope(DestPtrVal, L);
  assert(DestAccFunc);
  // Ignore accesses to "NULL".
  // TODO: We could use this to optimize the region further, e.g., intersect
  //       the context with
  //          isl_set_complement(isl_set_params(getDomain()))
  //       as we know it would be undefined to execute this instruction anyway.
  if (DestAccFunc->isZero())
    return true;

  auto *DestPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(DestAccFunc));
  assert(DestPtrSCEV);
  DestAccFunc = SE.getMinusSCEV(DestAccFunc, DestPtrSCEV);
  addArrayAccess(Inst, MemoryAccess::MUST_WRITE, DestPtrSCEV->getValue(),
                 IntegerType::getInt8Ty(DestPtrVal->getContext()), false,
                 {DestAccFunc, LengthVal}, {}, Inst.getValueOperand());

  auto *MemTrans = dyn_cast<MemTransferInst>(MemIntr);
  if (!MemTrans)
    return true;

  auto *SrcPtrVal = MemTrans->getSource();
  assert(SrcPtrVal);

  auto *SrcAccFunc = SE.getSCEVAtScope(SrcPtrVal, L);
  assert(SrcAccFunc);
  // Ignore accesses to "NULL".
  // TODO: See above TODO
  if (SrcAccFunc->isZero())
    return true;

  auto *SrcPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(SrcAccFunc));
  assert(SrcPtrSCEV);
  SrcAccFunc = SE.getMinusSCEV(SrcAccFunc, SrcPtrSCEV);
  addArrayAccess(Inst, MemoryAccess::READ, SrcPtrSCEV->getValue(),
                 IntegerType::getInt8Ty(SrcPtrVal->getContext()), false,
                 {SrcAccFunc, LengthVal}, {}, Inst.getValueOperand());

  return true;
}

bool ScopBuilder::buildAccessCallInst(MemAccInst Inst, Loop *L) {
  auto *CI = dyn_cast_or_null<CallInst>(Inst);

  if (CI == nullptr)
    return false;

  if (CI->doesNotAccessMemory() || isIgnoredIntrinsic(CI))
    return true;

  bool ReadOnly = false;
  auto *AF = SE.getConstant(IntegerType::getInt64Ty(CI->getContext()), 0);
  auto *CalledFunction = CI->getCalledFunction();
  switch (AA.getModRefBehavior(CalledFunction)) {
  case llvm::FMRB_UnknownModRefBehavior:
    llvm_unreachable("Unknown mod ref behaviour cannot be represented.");
  case llvm::FMRB_DoesNotAccessMemory:
    return true;
  case llvm::FMRB_OnlyReadsMemory:
    GlobalReads.push_back(CI);
    return true;
  case llvm::FMRB_OnlyReadsArgumentPointees:
    ReadOnly = true;
  // Fall through
  case llvm::FMRB_OnlyAccessesArgumentPointees:
    auto AccType = ReadOnly ? MemoryAccess::READ : MemoryAccess::MAY_WRITE;
    for (const auto &Arg : CI->arg_operands()) {
      if (!Arg->getType()->isPointerTy())
        continue;

      auto *ArgSCEV = SE.getSCEVAtScope(Arg, L);
      if (ArgSCEV->isZero())
        continue;

      auto *ArgBasePtr = cast<SCEVUnknown>(SE.getPointerBase(ArgSCEV));
      addArrayAccess(Inst, AccType, ArgBasePtr->getValue(),
                     ArgBasePtr->getType(), false, {AF}, {}, CI);
    }
    return true;
  }

  return true;
}

void ScopBuilder::buildAccessSingleDim(MemAccInst Inst, Loop *L) {
  Value *Address = Inst.getPointerOperand();
  Value *Val = Inst.getValueOperand();
  Type *ElementType = Val->getType();
  enum MemoryAccess::AccessType AccType =
      isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;

  const SCEV *AccessFunction = SE.getSCEVAtScope(Address, L);
  const SCEVUnknown *BasePointer =
      dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));

  assert(BasePointer && "Could not find base pointer");
  AccessFunction = SE.getMinusSCEV(AccessFunction, BasePointer);

  // Check if the access depends on a loop contained in a non-affine subregion.
  bool isVariantInNonAffineLoop = false;
  SetVector<const Loop *> Loops;
  auto &BoxedLoops = scop->getBoxedLoops();
  findLoops(AccessFunction, Loops);
  for (const Loop *L : Loops)
    if (BoxedLoops.count(L))
      isVariantInNonAffineLoop = true;

  InvariantLoadsSetTy AccessILS;

  Loop *SurroundingLoop = getFirstNonBoxedLoopFor(L, LI, BoxedLoops);
  bool IsAffine = !isVariantInNonAffineLoop &&
                  isAffineExpr(&scop->getRegion(), SurroundingLoop,
                               AccessFunction, SE, &AccessILS);

  const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
  for (LoadInst *LInst : AccessILS)
    if (!ScopRIL.count(LInst))
      IsAffine = false;

  if (!IsAffine && AccType == MemoryAccess::MUST_WRITE)
    AccType = MemoryAccess::MAY_WRITE;

  addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, IsAffine,
                 {AccessFunction}, {}, Val);
}

void ScopBuilder::buildMemoryAccess(MemAccInst Inst, Loop *L) {

  if (buildAccessMemIntrinsic(Inst, L))
    return;

  if (buildAccessCallInst(Inst, L))
    return;

  if (buildAccessMultiDimFixed(Inst, L))
    return;

  if (buildAccessMultiDimParam(Inst, L))
    return;

  buildAccessSingleDim(Inst, L);
}

void ScopBuilder::buildAccessFunctions(Region &SR) {

  if (scop->isNonAffineSubRegion(&SR)) {
    for (BasicBlock *BB : SR.blocks())
      buildAccessFunctions(*BB, &SR);
    return;
  }

  for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
    if (I->isSubRegion())
      buildAccessFunctions(*I->getNodeAs<Region>());
    else
      buildAccessFunctions(*I->getNodeAs<BasicBlock>());
}

void ScopBuilder::buildStmts(Region &SR) {

  if (scop->isNonAffineSubRegion(&SR)) {
    scop->addScopStmt(nullptr, &SR);
    return;
  }

  for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
    if (I->isSubRegion())
      buildStmts(*I->getNodeAs<Region>());
    else
      scop->addScopStmt(I->getNodeAs<BasicBlock>(), nullptr);
}

void ScopBuilder::buildAccessFunctions(BasicBlock &BB,
                                       Region *NonAffineSubRegion,
                                       bool IsExitBlock) {
  // We do not build access functions for error blocks, as they may contain
  // instructions we can not model.
  if (isErrorBlock(BB, scop->getRegion(), LI, DT) && !IsExitBlock)
    return;

  Loop *L = LI.getLoopFor(&BB);

  for (Instruction &Inst : BB) {
    PHINode *PHI = dyn_cast<PHINode>(&Inst);
    if (PHI)
      buildPHIAccesses(PHI, NonAffineSubRegion, IsExitBlock);

    // For the exit block we stop modeling after the last PHI node.
    if (!PHI && IsExitBlock)
      break;

    if (auto MemInst = MemAccInst::dyn_cast(Inst))
      buildMemoryAccess(MemInst, L);

    if (isIgnoredIntrinsic(&Inst))
      continue;

    // PHI nodes have already been modeled above and TerminatorInsts that are
    // not part of a non-affine subregion are fully modeled and regenerated
    // from the polyhedral domains. Hence, they do not need to be modeled as
    // explicit data dependences.
    if (!PHI && (!isa<TerminatorInst>(&Inst) || NonAffineSubRegion))
      buildScalarDependences(&Inst);

    if (!IsExitBlock)
      buildEscapingDependences(&Inst);
  }
}

MemoryAccess *ScopBuilder::addMemoryAccess(
    BasicBlock *BB, Instruction *Inst, MemoryAccess::AccessType AccType,
    Value *BaseAddress, Type *ElementType, bool Affine, Value *AccessValue,
    ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,
    ScopArrayInfo::MemoryKind Kind) {
  ScopStmt *Stmt = scop->getStmtFor(BB);

  // Do not create a memory access for anything not in the SCoP. It would be
  // ignored anyway.
  if (!Stmt)
    return nullptr;

  AccFuncSetType &AccList = scop->getOrCreateAccessFunctions(BB);
  Value *BaseAddr = BaseAddress;
  std::string BaseName = getIslCompatibleName("MemRef_", BaseAddr, "");

  bool isKnownMustAccess = false;

  // Accesses in single-basic block statements are always excuted.
  if (Stmt->isBlockStmt())
    isKnownMustAccess = true;

  if (Stmt->isRegionStmt()) {
    // Accesses that dominate the exit block of a non-affine region are always
    // executed. In non-affine regions there may exist MK_Values that do not
    // dominate the exit. MK_Values will always dominate the exit and MK_PHIs
    // only if there is at most one PHI_WRITE in the non-affine region.
    if (DT.dominates(BB, Stmt->getRegion()->getExit()))
      isKnownMustAccess = true;
  }

  // Non-affine PHI writes do not "happen" at a particular instruction, but
  // after exiting the statement. Therefore they are guaranteed execute and
  // overwrite the old value.
  if (Kind == ScopArrayInfo::MK_PHI || Kind == ScopArrayInfo::MK_ExitPHI)
    isKnownMustAccess = true;

  if (!isKnownMustAccess && AccType == MemoryAccess::MUST_WRITE)
    AccType = MemoryAccess::MAY_WRITE;

  AccList.emplace_back(Stmt, Inst, AccType, BaseAddress, ElementType, Affine,
                       Subscripts, Sizes, AccessValue, Kind, BaseName);
  Stmt->addAccess(&AccList.back());
  return &AccList.back();
}

void ScopBuilder::addArrayAccess(
    MemAccInst MemAccInst, MemoryAccess::AccessType AccType, Value *BaseAddress,
    Type *ElementType, bool IsAffine, ArrayRef<const SCEV *> Subscripts,
    ArrayRef<const SCEV *> Sizes, Value *AccessValue) {
  ArrayBasePointers.insert(BaseAddress);
  addMemoryAccess(MemAccInst->getParent(), MemAccInst, AccType, BaseAddress,
                  ElementType, IsAffine, AccessValue, Subscripts, Sizes,
                  ScopArrayInfo::MK_Array);
}

void ScopBuilder::ensureValueWrite(Instruction *Inst) {
  ScopStmt *Stmt = scop->getStmtFor(Inst);

  // Inst not defined within this SCoP.
  if (!Stmt)
    return;

  // Do not process further if the instruction is already written.
  if (Stmt->lookupValueWriteOf(Inst))
    return;

  addMemoryAccess(Inst->getParent(), Inst, MemoryAccess::MUST_WRITE, Inst,
                  Inst->getType(), true, Inst, ArrayRef<const SCEV *>(),
                  ArrayRef<const SCEV *>(), ScopArrayInfo::MK_Value);
}

void ScopBuilder::ensureValueRead(Value *V, BasicBlock *UserBB) {

  // There cannot be an "access" for literal constants. BasicBlock references
  // (jump destinations) also never change.
  if ((isa<Constant>(V) && !isa<GlobalVariable>(V)) || isa<BasicBlock>(V))
    return;

  // If the instruction can be synthesized and the user is in the region we do
  // not need to add a value dependences.
  auto *Scope = LI.getLoopFor(UserBB);
  if (canSynthesize(V, *scop, &LI, &SE, Scope))
    return;

  // Do not build scalar dependences for required invariant loads as we will
  // hoist them later on anyway or drop the SCoP if we cannot.
  auto &ScopRIL = scop->getRequiredInvariantLoads();
  if (ScopRIL.count(dyn_cast<LoadInst>(V)))
    return;

  // Determine the ScopStmt containing the value's definition and use. There is
  // no defining ScopStmt if the value is a function argument, a global value,
  // or defined outside the SCoP.
  Instruction *ValueInst = dyn_cast<Instruction>(V);
  ScopStmt *ValueStmt = ValueInst ? scop->getStmtFor(ValueInst) : nullptr;

  ScopStmt *UserStmt = scop->getStmtFor(UserBB);

  // We do not model uses outside the scop.
  if (!UserStmt)
    return;

  // Add MemoryAccess for invariant values only if requested.
  if (!ModelReadOnlyScalars && !ValueStmt)
    return;

  // Ignore use-def chains within the same ScopStmt.
  if (ValueStmt == UserStmt)
    return;

  // Do not create another MemoryAccess for reloading the value if one already
  // exists.
  if (UserStmt->lookupValueReadOf(V))
    return;

  // For exit PHIs use the MK_ExitPHI MemoryKind not MK_Value.
  ScopArrayInfo::MemoryKind Kind = ScopArrayInfo::MK_Value;
  if (!ValueStmt && isa<PHINode>(V))
    Kind = ScopArrayInfo::MK_ExitPHI;

  addMemoryAccess(UserBB, nullptr, MemoryAccess::READ, V, V->getType(), true, V,
                  ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(), Kind);
  if (ValueInst)
    ensureValueWrite(ValueInst);
}

void ScopBuilder::ensurePHIWrite(PHINode *PHI, BasicBlock *IncomingBlock,
                                 Value *IncomingValue, bool IsExitBlock) {
  // As the incoming block might turn out to be an error statement ensure we
  // will create an exit PHI SAI object. It is needed during code generation
  // and would be created later anyway.
  if (IsExitBlock)
    scop->getOrCreateScopArrayInfo(PHI, PHI->getType(), {},
                                   ScopArrayInfo::MK_ExitPHI);

  ScopStmt *IncomingStmt = scop->getStmtFor(IncomingBlock);
  if (!IncomingStmt)
    return;

  // Take care for the incoming value being available in the incoming block.
  // This must be done before the check for multiple PHI writes because multiple
  // exiting edges from subregion each can be the effective written value of the
  // subregion. As such, all of them must be made available in the subregion
  // statement.
  ensureValueRead(IncomingValue, IncomingBlock);

  // Do not add more than one MemoryAccess per PHINode and ScopStmt.
  if (MemoryAccess *Acc = IncomingStmt->lookupPHIWriteOf(PHI)) {
    assert(Acc->getAccessInstruction() == PHI);
    Acc->addIncoming(IncomingBlock, IncomingValue);
    return;
  }

  MemoryAccess *Acc = addMemoryAccess(
      IncomingStmt->getEntryBlock(), PHI, MemoryAccess::MUST_WRITE, PHI,
      PHI->getType(), true, PHI, ArrayRef<const SCEV *>(),
      ArrayRef<const SCEV *>(),
      IsExitBlock ? ScopArrayInfo::MK_ExitPHI : ScopArrayInfo::MK_PHI);
  assert(Acc);
  Acc->addIncoming(IncomingBlock, IncomingValue);
}

void ScopBuilder::addPHIReadAccess(PHINode *PHI) {
  addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI,
                  PHI->getType(), true, PHI, ArrayRef<const SCEV *>(),
                  ArrayRef<const SCEV *>(), ScopArrayInfo::MK_PHI);
}

void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) {
  scop.reset(new Scop(R, SE, LI, *SD.getDetectionContext(&R)));

  buildStmts(R);
  buildAccessFunctions(R);

  // In case the region does not have an exiting block we will later (during
  // code generation) split the exit block. This will move potential PHI nodes
  // from the current exit block into the new region exiting block. Hence, PHI
  // nodes that are at this point not part of the region will be.
  // To handle these PHI nodes later we will now model their operands as scalar
  // accesses. Note that we do not model anything in the exit block if we have
  // an exiting block in the region, as there will not be any splitting later.
  if (!scop->hasSingleExitEdge())
    buildAccessFunctions(*R.getExit(), nullptr,
                         /* IsExitBlock */ true);

  // Create memory accesses for global reads since all arrays are now known.
  auto *AF = SE.getConstant(IntegerType::getInt64Ty(SE.getContext()), 0);
  for (auto *GlobalRead : GlobalReads)
    for (auto *BP : ArrayBasePointers)
      addArrayAccess(MemAccInst(GlobalRead), MemoryAccess::READ, BP,
                     BP->getType(), false, {AF}, {}, GlobalRead);

  scop->init(AA, AC, DT, LI);
}

ScopBuilder::ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA,
                         const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
                         ScopDetection &SD, ScalarEvolution &SE)
    : AA(AA), DL(DL), DT(DT), LI(LI), SD(SD), SE(SE) {

  Function *F = R->getEntry()->getParent();

  DebugLoc Beg, End;
  getDebugLocations(getBBPairForRegion(R), Beg, End);
  std::string Msg = "SCoP begins here.";
  emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE, *F, Beg, Msg);

  buildScop(*R, AC);

  DEBUG(scop->print(dbgs()));

  if (!scop->hasFeasibleRuntimeContext()) {
    Msg = "SCoP ends here but was dismissed.";
    scop.reset();
  } else {
    Msg = "SCoP ends here.";
    ++ScopFound;
    if (scop->getMaxLoopDepth() > 0)
      ++RichScopFound;
  }

  emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE, *F, End, Msg);
}