lib/Analysis/ScopBuilder.cpp

   1 //===- ScopBuilder.cpp ---------------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Create a polyhedral description for a static control flow region.
  11 //
  12 // The pass creates a polyhedral description of the Scops detected by the SCoP
  13 // detection derived from their LLVM-IR code.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "polly/ScopBuilder.h"
  18 #include "polly/Options.h"
  19 #include "polly/Support/GICHelper.h"
  20 #include "polly/Support/SCEVValidator.h"
  21 #include "polly/Support/VirtualInstruction.h"
  22 #include "llvm/Analysis/RegionIterator.h"
  23 #include "llvm/IR/DiagnosticInfo.h"
  24
  25 using namespace llvm;
  26 using namespace polly;
  27
  28 #define DEBUG_TYPE "polly-scops"
  29
  30 STATISTIC(ScopFound, "Number of valid Scops");
  31 STATISTIC(RichScopFound, "Number of Scops containing a loop");
  32 STATISTIC(InfeasibleScops,
  33           "Number of SCoPs with statically infeasible context.");
  34
  35 static cl::opt<bool> ModelReadOnlyScalars(
  36     "polly-analyze-read-only-scalars",
  37     cl::desc("Model read-only scalar values in the scop description"),
  38     cl::Hidden, cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory));
  39
  40 static cl::opt<bool> UnprofitableScalarAccs(
  41     "polly-unprofitable-scalar-accs",
  42     cl::desc("Count statements with scalar accesses as not optimizable"),
  43     cl::Hidden, cl::init(false), cl::cat(PollyCategory));
  44
  45 static cl::opt<bool> DetectFortranArrays(
  46     "polly-detect-fortran-arrays",
  47     cl::desc("Detect Fortran arrays and use this for code generation"),
  48     cl::Hidden, cl::init(false), cl::cat(PollyCategory));
  49
  50 void ScopBuilder::buildPHIAccesses(PHINode *PHI, Region *NonAffineSubRegion,
  51                                    bool IsExitBlock) {
  52
  53   // PHI nodes that are in the exit block of the region, hence if IsExitBlock is
  54   // true, are not modeled as ordinary PHI nodes as they are not part of the
  55   // region. However, we model the operands in the predecessor blocks that are
  56   // part of the region as regular scalar accesses.
  57
  58   // If we can synthesize a PHI we can skip it, however only if it is in
  59   // the region. If it is not it can only be in the exit block of the region.
  60   // In this case we model the operands but not the PHI itself.
  61   auto *Scope = LI.getLoopFor(PHI->getParent());
  62   if (!IsExitBlock && canSynthesize(PHI, *scop, &SE, Scope))
  63     return;
  64
  65   // PHI nodes are modeled as if they had been demoted prior to the SCoP
  66   // detection. Hence, the PHI is a load of a new memory location in which the
  67   // incoming value was written at the end of the incoming basic block.
  68   bool OnlyNonAffineSubRegionOperands = true;
  69   for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) {
  70     Value *Op = PHI->getIncomingValue(u);
  71     BasicBlock *OpBB = PHI->getIncomingBlock(u);
  72
  73     // Do not build PHI dependences inside a non-affine subregion, but make
  74     // sure that the necessary scalar values are still made available.
  75     if (NonAffineSubRegion && NonAffineSubRegion->contains(OpBB)) {
  76       auto *OpInst = dyn_cast<Instruction>(Op);
  77       if (!OpInst || !NonAffineSubRegion->contains(OpInst))
  78         ensureValueRead(Op, OpBB);
  79       continue;
  80     }
  81
  82     OnlyNonAffineSubRegionOperands = false;
  83     ensurePHIWrite(PHI, OpBB, Op, IsExitBlock);
  84   }
  85
  86   if (!OnlyNonAffineSubRegionOperands && !IsExitBlock) {
  87     addPHIReadAccess(PHI);
  88   }
  89 }
  90
  91 void ScopBuilder::buildScalarDependences(Instruction *Inst) {
  92   assert(!isa<PHINode>(Inst));
  93
  94   // Pull-in required operands.
  95   for (Use &Op : Inst->operands())
  96     ensureValueRead(Op.get(), Inst->getParent());
  97 }
  98
  99 void ScopBuilder::buildEscapingDependences(Instruction *Inst) {
 100   // Check for uses of this instruction outside the scop. Because we do not
 101   // iterate over such instructions and therefore did not "ensure" the existence
 102   // of a write, we must determine such use here.
 103   for (Use &U : Inst->uses()) {
 104     Instruction *UI = dyn_cast<Instruction>(U.getUser());
 105     if (!UI)
 106       continue;
 107
 108     BasicBlock *UseParent = getUseBlock(U);
 109     BasicBlock *UserParent = UI->getParent();
 110
 111     // An escaping value is either used by an instruction not within the scop,
 112     // or (when the scop region's exit needs to be simplified) by a PHI in the
 113     // scop's exit block. This is because region simplification before code
 114     // generation inserts new basic blocks before the PHI such that its incoming
 115     // blocks are not in the scop anymore.
 116     if (!scop->contains(UseParent) ||
 117         (isa<PHINode>(UI) && scop->isExit(UserParent) &&
 118          scop->hasSingleExitEdge())) {
 119       // At least one escaping use found.
 120       ensureValueWrite(Inst);
 121       break;
 122     }
 123   }
 124 }
 125
 126 /// Check that a value is a Fortran Array descriptor.
 127 ///
 128 /// We check if V has the following structure:
 129 /// %"struct.array1_real(kind=8)" = type { i8*, i<zz>, i<zz>,
 130 ///                                   [<num> x %struct.descriptor_dimension] }
 131 ///
 132 ///
 133 /// %struct.descriptor_dimension = type { i<zz>, i<zz>, i<zz> }
 134 ///
 135 /// 1. V's type name starts with "struct.array"
 136 /// 2. V's type has layout as shown.
 137 /// 3. Final member of V's type has name "struct.descriptor_dimension",
 138 /// 4. "struct.descriptor_dimension" has layout as shown.
 139 /// 5. Consistent use of i<zz> where <zz> is some fixed integer number.
 140 ///
 141 /// We are interested in such types since this is the code that dragonegg
 142 /// generates for Fortran array descriptors.
 143 ///
 144 /// @param V the Value to be checked.
 145 ///
 146 /// @returns True if V is a Fortran array descriptor, False otherwise.
 147 bool isFortranArrayDescriptor(Value *V) {
 148   PointerType *PTy = dyn_cast<PointerType>(V->getType());
 149
 150   if (!PTy)
 151     return false;
 152
 153   Type *Ty = PTy->getElementType();
 154   assert(Ty && "Ty expected to be initialized");
 155   auto *StructArrTy = dyn_cast<StructType>(Ty);
 156
 157   if (!(StructArrTy && StructArrTy->hasName()))
 158     return false;
 159
 160   if (!StructArrTy->getName().startswith("struct.array"))
 161     return false;
 162
 163   if (StructArrTy->getNumElements() != 4)
 164     return false;
 165
 166   const ArrayRef<Type *> ArrMemberTys = StructArrTy->elements();
 167
 168   // i8* match
 169   if (ArrMemberTys[0] != Type::getInt8PtrTy(V->getContext()))
 170     return false;
 171
 172   // Get a reference to the int type and check that all the members
 173   // share the same int type
 174   Type *IntTy = ArrMemberTys[1];
 175   if (ArrMemberTys[2] != IntTy)
 176     return false;
 177
 178   // type: [<num> x %struct.descriptor_dimension]
 179   ArrayType *DescriptorDimArrayTy = dyn_cast<ArrayType>(ArrMemberTys[3]);
 180   if (!DescriptorDimArrayTy)
 181     return false;
 182
 183   // type: %struct.descriptor_dimension := type { ixx, ixx, ixx }
 184   StructType *DescriptorDimTy =
 185       dyn_cast<StructType>(DescriptorDimArrayTy->getElementType());
 186
 187   if (!(DescriptorDimTy && DescriptorDimTy->hasName()))
 188     return false;
 189
 190   if (DescriptorDimTy->getName() != "struct.descriptor_dimension")
 191     return false;
 192
 193   if (DescriptorDimTy->getNumElements() != 3)
 194     return false;
 195
 196   for (auto MemberTy : DescriptorDimTy->elements()) {
 197     if (MemberTy != IntTy)
 198       return false;
 199   }
 200
 201   return true;
 202 }
 203
 204 Value *ScopBuilder::findFADAllocationVisible(MemAccInst Inst) {
 205   // match: 4.1 & 4.2 store/load
 206   if (!isa<LoadInst>(Inst) && !isa<StoreInst>(Inst))
 207     return nullptr;
 208
 209   // match: 4
 210   if (Inst.getAlignment() != 8)
 211     return nullptr;
 212
 213   Value *Address = Inst.getPointerOperand();
 214
 215   const BitCastInst *Bitcast = nullptr;
 216   // [match: 3]
 217   if (auto *Slot = dyn_cast<GetElementPtrInst>(Address)) {
 218     Value *TypedMem = Slot->getPointerOperand();
 219     // match: 2
 220     Bitcast = dyn_cast<BitCastInst>(TypedMem);
 221   } else {
 222     // match: 2
 223     Bitcast = dyn_cast<BitCastInst>(Address);
 224   }
 225
 226   if (!Bitcast)
 227     return nullptr;
 228
 229   auto *MallocMem = Bitcast->getOperand(0);
 230
 231   // match: 1
 232   auto *MallocCall = dyn_cast<CallInst>(MallocMem);
 233   if (!MallocCall)
 234     return nullptr;
 235
 236   Function *MallocFn = MallocCall->getCalledFunction();
 237   if (!(MallocFn && MallocFn->hasName() && MallocFn->getName() == "malloc"))
 238     return nullptr;
 239
 240   // Find all uses the malloc'd memory.
 241   // We are looking for a "store" into a struct with the type being the Fortran
 242   // descriptor type
 243   for (auto user : MallocMem->users()) {
 244
 245     /// match: 5
 246     auto *MallocStore = dyn_cast<StoreInst>(user);
 247     if (!MallocStore)
 248       continue;
 249
 250     auto *DescriptorGEP =
 251         dyn_cast<GEPOperator>(MallocStore->getPointerOperand());
 252     if (!DescriptorGEP)
 253       continue;
 254
 255     // match: 5
 256     auto DescriptorType =
 257         dyn_cast<StructType>(DescriptorGEP->getSourceElementType());
 258     if (!(DescriptorType && DescriptorType->hasName()))
 259       continue;
 260
 261     Value *Descriptor = dyn_cast<Value>(DescriptorGEP->getPointerOperand());
 262
 263     if (!Descriptor)
 264       continue;
 265
 266     if (!isFortranArrayDescriptor(Descriptor))
 267       continue;
 268
 269     return Descriptor;
 270   }
 271
 272   return nullptr;
 273 }
 274
 275 Value *ScopBuilder::findFADAllocationInvisible(MemAccInst Inst) {
 276   // match: 3
 277   if (!isa<LoadInst>(Inst) && !isa<StoreInst>(Inst))
 278     return nullptr;
 279
 280   Value *Slot = Inst.getPointerOperand();
 281
 282   LoadInst *MemLoad = nullptr;
 283   // [match: 2]
 284   if (auto *SlotGEP = dyn_cast<GetElementPtrInst>(Slot)) {
 285     // match: 1
 286     MemLoad = dyn_cast<LoadInst>(SlotGEP->getPointerOperand());
 287   } else {
 288     // match: 1
 289     MemLoad = dyn_cast<LoadInst>(Slot);
 290   }
 291
 292   if (!MemLoad)
 293     return nullptr;
 294
 295   auto *BitcastOperator =
 296       dyn_cast<BitCastOperator>(MemLoad->getPointerOperand());
 297   if (!BitcastOperator)
 298     return nullptr;
 299
 300   Value *Descriptor = dyn_cast<Value>(BitcastOperator->getOperand(0));
 301   if (!Descriptor)
 302     return nullptr;
 303
 304   if (!isFortranArrayDescriptor(Descriptor))
 305     return nullptr;
 306
 307   return Descriptor;
 308 }
 309
 310 bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt) {
 311   Value *Val = Inst.getValueOperand();
 312   Type *ElementType = Val->getType();
 313   Value *Address = Inst.getPointerOperand();
 314   const SCEV *AccessFunction =
 315       SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));
 316   const SCEVUnknown *BasePointer =
 317       dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
 318   enum MemoryAccess::AccessType AccType =
 319       isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
 320
 321   if (auto *BitCast = dyn_cast<BitCastInst>(Address)) {
 322     auto *Src = BitCast->getOperand(0);
 323     auto *SrcTy = Src->getType();
 324     auto *DstTy = BitCast->getType();
 325     // Do not try to delinearize non-sized (opaque) pointers.
 326     if ((SrcTy->isPointerTy() && !SrcTy->getPointerElementType()->isSized()) ||
 327         (DstTy->isPointerTy() && !DstTy->getPointerElementType()->isSized())) {
 328       return false;
 329     }
 330     if (SrcTy->isPointerTy() && DstTy->isPointerTy() &&
 331         DL.getTypeAllocSize(SrcTy->getPointerElementType()) ==
 332             DL.getTypeAllocSize(DstTy->getPointerElementType()))
 333       Address = Src;
 334   }
 335
 336   auto *GEP = dyn_cast<GetElementPtrInst>(Address);
 337   if (!GEP)
 338     return false;
 339
 340   std::vector<const SCEV *> Subscripts;
 341   std::vector<int> Sizes;
 342   std::tie(Subscripts, Sizes) = getIndexExpressionsFromGEP(GEP, SE);
 343   auto *BasePtr = GEP->getOperand(0);
 344
 345   if (auto *BasePtrCast = dyn_cast<BitCastInst>(BasePtr))
 346     BasePtr = BasePtrCast->getOperand(0);
 347
 348   // Check for identical base pointers to ensure that we do not miss index
 349   // offsets that have been added before this GEP is applied.
 350   if (BasePtr != BasePointer->getValue())
 351     return false;
 352
 353   std::vector<const SCEV *> SizesSCEV;
 354
 355   const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
 356
 357   Loop *SurroundingLoop = Stmt->getSurroundingLoop();
 358   for (auto *Subscript : Subscripts) {
 359     InvariantLoadsSetTy AccessILS;
 360     if (!isAffineExpr(&scop->getRegion(), SurroundingLoop, Subscript, SE,
 361                       &AccessILS))
 362       return false;
 363
 364     for (LoadInst *LInst : AccessILS)
 365       if (!ScopRIL.count(LInst))
 366         return false;
 367   }
 368
 369   if (Sizes.empty())
 370     return false;
 371
 372   SizesSCEV.push_back(nullptr);
 373
 374   for (auto V : Sizes)
 375     SizesSCEV.push_back(SE.getSCEV(
 376         ConstantInt::get(IntegerType::getInt64Ty(BasePtr->getContext()), V)));
 377
 378   addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, true,
 379                  Subscripts, SizesSCEV, Val);
 380   return true;
 381 }
 382
 383 bool ScopBuilder::buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt) {
 384   if (!PollyDelinearize)
 385     return false;
 386
 387   Value *Address = Inst.getPointerOperand();
 388   Value *Val = Inst.getValueOperand();
 389   Type *ElementType = Val->getType();
 390   unsigned ElementSize = DL.getTypeAllocSize(ElementType);
 391   enum MemoryAccess::AccessType AccType =
 392       isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
 393
 394   const SCEV *AccessFunction =
 395       SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));
 396   const SCEVUnknown *BasePointer =
 397       dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
 398
 399   assert(BasePointer && "Could not find base pointer");
 400
 401   auto &InsnToMemAcc = scop->getInsnToMemAccMap();
 402   auto AccItr = InsnToMemAcc.find(Inst);
 403   if (AccItr == InsnToMemAcc.end())
 404     return false;
 405
 406   std::vector<const SCEV *> Sizes = {nullptr};
 407
 408   Sizes.insert(Sizes.end(), AccItr->second.Shape->DelinearizedSizes.begin(),
 409                AccItr->second.Shape->DelinearizedSizes.end());
 410
 411   // In case only the element size is contained in the 'Sizes' array, the
 412   // access does not access a real multi-dimensional array. Hence, we allow
 413   // the normal single-dimensional access construction to handle this.
 414   if (Sizes.size() == 1)
 415     return false;
 416
 417   // Remove the element size. This information is already provided by the
 418   // ElementSize parameter. In case the element size of this access and the
 419   // element size used for delinearization differs the delinearization is
 420   // incorrect. Hence, we invalidate the scop.
 421   //
 422   // TODO: Handle delinearization with differing element sizes.
 423   auto DelinearizedSize =
 424       cast<SCEVConstant>(Sizes.back())->getAPInt().getSExtValue();
 425   Sizes.pop_back();
 426   if (ElementSize != DelinearizedSize)
 427     scop->invalidate(DELINEARIZATION, Inst->getDebugLoc());
 428
 429   addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, true,
 430                  AccItr->second.DelinearizedSubscripts, Sizes, Val);
 431   return true;
 432 }
 433
 434 bool ScopBuilder::buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt) {
 435   auto *MemIntr = dyn_cast_or_null<MemIntrinsic>(Inst);
 436
 437   if (MemIntr == nullptr)
 438     return false;
 439
 440   auto *L = LI.getLoopFor(Inst->getParent());
 441   auto *LengthVal = SE.getSCEVAtScope(MemIntr->getLength(), L);
 442   assert(LengthVal);
 443
 444   // Check if the length val is actually affine or if we overapproximate it
 445   InvariantLoadsSetTy AccessILS;
 446   const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
 447
 448   Loop *SurroundingLoop = Stmt->getSurroundingLoop();
 449   bool LengthIsAffine = isAffineExpr(&scop->getRegion(), SurroundingLoop,
 450                                      LengthVal, SE, &AccessILS);
 451   for (LoadInst *LInst : AccessILS)
 452     if (!ScopRIL.count(LInst))
 453       LengthIsAffine = false;
 454   if (!LengthIsAffine)
 455     LengthVal = nullptr;
 456
 457   auto *DestPtrVal = MemIntr->getDest();
 458   assert(DestPtrVal);
 459
 460   auto *DestAccFunc = SE.getSCEVAtScope(DestPtrVal, L);
 461   assert(DestAccFunc);
 462   // Ignore accesses to "NULL".
 463   // TODO: We could use this to optimize the region further, e.g., intersect
 464   //       the context with
 465   //          isl_set_complement(isl_set_params(getDomain()))
 466   //       as we know it would be undefined to execute this instruction anyway.
 467   if (DestAccFunc->isZero())
 468     return true;
 469
 470   auto *DestPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(DestAccFunc));
 471   assert(DestPtrSCEV);
 472   DestAccFunc = SE.getMinusSCEV(DestAccFunc, DestPtrSCEV);
 473   addArrayAccess(Inst, MemoryAccess::MUST_WRITE, DestPtrSCEV->getValue(),
 474                  IntegerType::getInt8Ty(DestPtrVal->getContext()),
 475                  LengthIsAffine, {DestAccFunc, LengthVal}, {nullptr},
 476                  Inst.getValueOperand());
 477
 478   auto *MemTrans = dyn_cast<MemTransferInst>(MemIntr);
 479   if (!MemTrans)
 480     return true;
 481
 482   auto *SrcPtrVal = MemTrans->getSource();
 483   assert(SrcPtrVal);
 484
 485   auto *SrcAccFunc = SE.getSCEVAtScope(SrcPtrVal, L);
 486   assert(SrcAccFunc);
 487   // Ignore accesses to "NULL".
 488   // TODO: See above TODO
 489   if (SrcAccFunc->isZero())
 490     return true;
 491
 492   auto *SrcPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(SrcAccFunc));
 493   assert(SrcPtrSCEV);
 494   SrcAccFunc = SE.getMinusSCEV(SrcAccFunc, SrcPtrSCEV);
 495   addArrayAccess(Inst, MemoryAccess::READ, SrcPtrSCEV->getValue(),
 496                  IntegerType::getInt8Ty(SrcPtrVal->getContext()),
 497                  LengthIsAffine, {SrcAccFunc, LengthVal}, {nullptr},
 498                  Inst.getValueOperand());
 499
 500   return true;
 501 }
 502
 503 bool ScopBuilder::buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt) {
 504   auto *CI = dyn_cast_or_null<CallInst>(Inst);
 505
 506   if (CI == nullptr)
 507     return false;
 508
 509   if (CI->doesNotAccessMemory() || isIgnoredIntrinsic(CI))
 510     return true;
 511
 512   bool ReadOnly = false;
 513   auto *AF = SE.getConstant(IntegerType::getInt64Ty(CI->getContext()), 0);
 514   auto *CalledFunction = CI->getCalledFunction();
 515   switch (AA.getModRefBehavior(CalledFunction)) {
 516   case FMRB_UnknownModRefBehavior:
 517     llvm_unreachable("Unknown mod ref behaviour cannot be represented.");
 518   case FMRB_DoesNotAccessMemory:
 519     return true;
 520   case FMRB_DoesNotReadMemory:
 521   case FMRB_OnlyAccessesInaccessibleMem:
 522   case FMRB_OnlyAccessesInaccessibleOrArgMem:
 523     return false;
 524   case FMRB_OnlyReadsMemory:
 525     GlobalReads.push_back(CI);
 526     return true;
 527   case FMRB_OnlyReadsArgumentPointees:
 528     ReadOnly = true;
 529   // Fall through
 530   case FMRB_OnlyAccessesArgumentPointees:
 531     auto AccType = ReadOnly ? MemoryAccess::READ : MemoryAccess::MAY_WRITE;
 532     Loop *L = LI.getLoopFor(Inst->getParent());
 533     for (const auto &Arg : CI->arg_operands()) {
 534       if (!Arg->getType()->isPointerTy())
 535         continue;
 536
 537       auto *ArgSCEV = SE.getSCEVAtScope(Arg, L);
 538       if (ArgSCEV->isZero())
 539         continue;
 540
 541       auto *ArgBasePtr = cast<SCEVUnknown>(SE.getPointerBase(ArgSCEV));
 542       addArrayAccess(Inst, AccType, ArgBasePtr->getValue(),
 543                      ArgBasePtr->getType(), false, {AF}, {nullptr}, CI);
 544     }
 545     return true;
 546   }
 547
 548   return true;
 549 }
 550
 551 void ScopBuilder::buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt) {
 552   Value *Address = Inst.getPointerOperand();
 553   Value *Val = Inst.getValueOperand();
 554   Type *ElementType = Val->getType();
 555   enum MemoryAccess::AccessType AccType =
 556       isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
 557
 558   const SCEV *AccessFunction =
 559       SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));
 560   const SCEVUnknown *BasePointer =
 561       dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
 562
 563   assert(BasePointer && "Could not find base pointer");
 564   AccessFunction = SE.getMinusSCEV(AccessFunction, BasePointer);
 565
 566   // Check if the access depends on a loop contained in a non-affine subregion.
 567   bool isVariantInNonAffineLoop = false;
 568   SetVector<const Loop *> Loops;
 569   findLoops(AccessFunction, Loops);
 570   for (const Loop *L : Loops)
 571     if (Stmt->contains(L)) {
 572       isVariantInNonAffineLoop = true;
 573       break;
 574     }
 575
 576   InvariantLoadsSetTy AccessILS;
 577
 578   Loop *SurroundingLoop = Stmt->getSurroundingLoop();
 579   bool IsAffine = !isVariantInNonAffineLoop &&
 580                   isAffineExpr(&scop->getRegion(), SurroundingLoop,
 581                                AccessFunction, SE, &AccessILS);
 582
 583   const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
 584   for (LoadInst *LInst : AccessILS)
 585     if (!ScopRIL.count(LInst))
 586       IsAffine = false;
 587
 588   if (!IsAffine && AccType == MemoryAccess::MUST_WRITE)
 589     AccType = MemoryAccess::MAY_WRITE;
 590
 591   addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, IsAffine,
 592                  {AccessFunction}, {nullptr}, Val);
 593 }
 594
 595 void ScopBuilder::buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt) {
 596
 597   if (buildAccessMemIntrinsic(Inst, Stmt))
 598     return;
 599
 600   if (buildAccessCallInst(Inst, Stmt))
 601     return;
 602
 603   if (buildAccessMultiDimFixed(Inst, Stmt))
 604     return;
 605
 606   if (buildAccessMultiDimParam(Inst, Stmt))
 607     return;
 608
 609   buildAccessSingleDim(Inst, Stmt);
 610 }
 611
 612 void ScopBuilder::buildAccessFunctions(Region &SR) {
 613
 614   if (scop->isNonAffineSubRegion(&SR)) {
 615     for (BasicBlock *BB : SR.blocks())
 616       buildAccessFunctions(*BB, &SR);
 617     return;
 618   }
 619
 620   for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
 621     if (I->isSubRegion())
 622       buildAccessFunctions(*I->getNodeAs<Region>());
 623     else
 624       buildAccessFunctions(*I->getNodeAs<BasicBlock>());
 625 }
 626
 627 void ScopBuilder::buildStmts(Region &SR) {
 628
 629   if (scop->isNonAffineSubRegion(&SR)) {
 630     Loop *SurroundingLoop = LI.getLoopFor(SR.getEntry());
 631     auto &BoxedLoops = scop->getBoxedLoops();
 632     while (BoxedLoops.count(SurroundingLoop))
 633       SurroundingLoop = SurroundingLoop->getParentLoop();
 634     scop->addScopStmt(&SR, SurroundingLoop);
 635     return;
 636   }
 637
 638   for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
 639     if (I->isSubRegion())
 640       buildStmts(*I->getNodeAs<Region>());
 641     else {
 642       std::vector<Instruction *> Instructions;
 643       for (Instruction &Inst : *I->getNodeAs<BasicBlock>()) {
 644         Loop *L = LI.getLoopFor(Inst.getParent());
 645         if (!isa<TerminatorInst>(&Inst) && !isIgnoredIntrinsic(&Inst) &&
 646             !canSynthesize(&Inst, *scop, &SE, L))
 647           Instructions.push_back(&Inst);
 648       }
 649       Loop *SurroundingLoop = LI.getLoopFor(I->getNodeAs<BasicBlock>());
 650       scop->addScopStmt(I->getNodeAs<BasicBlock>(), SurroundingLoop,
 651                         Instructions);
 652     }
 653 }
 654
 655 void ScopBuilder::buildAccessFunctions(BasicBlock &BB,
 656                                        Region *NonAffineSubRegion,
 657                                        bool IsExitBlock) {
 658   // We do not build access functions for error blocks, as they may contain
 659   // instructions we can not model.
 660   if (isErrorBlock(BB, scop->getRegion(), LI, DT) && !IsExitBlock)
 661     return;
 662
 663   ScopStmt *Stmt = scop->getStmtFor(&BB);
 664
 665   for (Instruction &Inst : BB) {
 666     PHINode *PHI = dyn_cast<PHINode>(&Inst);
 667     if (PHI)
 668       buildPHIAccesses(PHI, NonAffineSubRegion, IsExitBlock);
 669
 670     // For the exit block we stop modeling after the last PHI node.
 671     if (!PHI && IsExitBlock)
 672       break;
 673
 674     if (auto MemInst = MemAccInst::dyn_cast(Inst)) {
 675       assert(Stmt && "Cannot build access function in non-existing statement");
 676       buildMemoryAccess(MemInst, Stmt);
 677     }
 678
 679     if (isIgnoredIntrinsic(&Inst))
 680       continue;
 681
 682     // PHI nodes have already been modeled above and TerminatorInsts that are
 683     // not part of a non-affine subregion are fully modeled and regenerated
 684     // from the polyhedral domains. Hence, they do not need to be modeled as
 685     // explicit data dependences.
 686     if (!PHI && (!isa<TerminatorInst>(&Inst) || NonAffineSubRegion))
 687       buildScalarDependences(&Inst);
 688
 689     if (!IsExitBlock)
 690       buildEscapingDependences(&Inst);
 691   }
 692 }
 693
 694 MemoryAccess *ScopBuilder::addMemoryAccess(
 695     BasicBlock *BB, Instruction *Inst, MemoryAccess::AccessType AccType,
 696     Value *BaseAddress, Type *ElementType, bool Affine, Value *AccessValue,
 697     ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,
 698     MemoryKind Kind) {
 699   ScopStmt *Stmt = scop->getStmtFor(BB);
 700
 701   // Do not create a memory access for anything not in the SCoP. It would be
 702   // ignored anyway.
 703   if (!Stmt)
 704     return nullptr;
 705
 706   bool isKnownMustAccess = false;
 707
 708   // Accesses in single-basic block statements are always excuted.
 709   if (Stmt->isBlockStmt())
 710     isKnownMustAccess = true;
 711
 712   if (Stmt->isRegionStmt()) {
 713     // Accesses that dominate the exit block of a non-affine region are always
 714     // executed. In non-affine regions there may exist MemoryKind::Values that
 715     // do not dominate the exit. MemoryKind::Values will always dominate the
 716     // exit and MemoryKind::PHIs only if there is at most one PHI_WRITE in the
 717     // non-affine region.
 718     if (DT.dominates(BB, Stmt->getRegion()->getExit()))
 719       isKnownMustAccess = true;
 720   }
 721
 722   // Non-affine PHI writes do not "happen" at a particular instruction, but
 723   // after exiting the statement. Therefore they are guaranteed to execute and
 724   // overwrite the old value.
 725   if (Kind == MemoryKind::PHI || Kind == MemoryKind::ExitPHI)
 726     isKnownMustAccess = true;
 727
 728   if (!isKnownMustAccess && AccType == MemoryAccess::MUST_WRITE)
 729     AccType = MemoryAccess::MAY_WRITE;
 730
 731   auto *Access = new MemoryAccess(Stmt, Inst, AccType, BaseAddress, ElementType,
 732                                   Affine, Subscripts, Sizes, AccessValue, Kind);
 733
 734   scop->addAccessFunction(Access);
 735   Stmt->addAccess(Access);
 736   return Access;
 737 }
 738
 739 void ScopBuilder::addArrayAccess(
 740     MemAccInst MemAccInst, MemoryAccess::AccessType AccType, Value *BaseAddress,
 741     Type *ElementType, bool IsAffine, ArrayRef<const SCEV *> Subscripts,
 742     ArrayRef<const SCEV *> Sizes, Value *AccessValue) {
 743   ArrayBasePointers.insert(BaseAddress);
 744   auto *MemAccess = addMemoryAccess(
 745       MemAccInst->getParent(), MemAccInst, AccType, BaseAddress, ElementType,
 746       IsAffine, AccessValue, Subscripts, Sizes, MemoryKind::Array);
 747
 748   if (!DetectFortranArrays)
 749     return;
 750
 751   if (Value *FAD = findFADAllocationInvisible(MemAccInst))
 752     MemAccess->setFortranArrayDescriptor(FAD);
 753   else if (Value *FAD = findFADAllocationVisible(MemAccInst))
 754     MemAccess->setFortranArrayDescriptor(FAD);
 755 }
 756
 757 void ScopBuilder::ensureValueWrite(Instruction *Inst) {
 758   ScopStmt *Stmt = scop->getStmtFor(Inst);
 759
 760   // Inst not defined within this SCoP.
 761   if (!Stmt)
 762     return;
 763
 764   // Do not process further if the instruction is already written.
 765   if (Stmt->lookupValueWriteOf(Inst))
 766     return;
 767
 768   addMemoryAccess(Inst->getParent(), Inst, MemoryAccess::MUST_WRITE, Inst,
 769                   Inst->getType(), true, Inst, ArrayRef<const SCEV *>(),
 770                   ArrayRef<const SCEV *>(), MemoryKind::Value);
 771 }
 772
 773 void ScopBuilder::ensureValueRead(Value *V, BasicBlock *UserBB) {
 774   ScopStmt *UserStmt = scop->getStmtFor(UserBB);
 775   auto *Scope = LI.getLoopFor(UserBB);
 776   auto VUse = VirtualUse::create(scop.get(), UserStmt, Scope, V, false);
 777   switch (VUse.getKind()) {
 778   case VirtualUse::Constant:
 779   case VirtualUse::Block:
 780   case VirtualUse::Synthesizable:
 781   case VirtualUse::Hoisted:
 782   case VirtualUse::Intra:
 783     // Uses of these kinds do not need a MemoryAccess.
 784     break;
 785
 786   case VirtualUse::ReadOnly:
 787     // Add MemoryAccess for invariant values only if requested.
 788     if (!ModelReadOnlyScalars)
 789       break;
 790
 791     LLVM_FALLTHROUGH;
 792   case VirtualUse::Inter:
 793
 794     // Do not create another MemoryAccess for reloading the value if one already
 795     // exists.
 796     if (UserStmt->lookupValueReadOf(V))
 797       break;
 798
 799     addMemoryAccess(UserBB, nullptr, MemoryAccess::READ, V, V->getType(), true,
 800                     V, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
 801                     MemoryKind::Value);
 802
 803     // Inter-statement uses need to write the value in their defining statement.
 804     if (VUse.isInter())
 805       ensureValueWrite(cast<Instruction>(V));
 806     break;
 807   }
 808 }
 809
 810 void ScopBuilder::ensurePHIWrite(PHINode *PHI, BasicBlock *IncomingBlock,
 811                                  Value *IncomingValue, bool IsExitBlock) {
 812   // As the incoming block might turn out to be an error statement ensure we
 813   // will create an exit PHI SAI object. It is needed during code generation
 814   // and would be created later anyway.
 815   if (IsExitBlock)
 816     scop->getOrCreateScopArrayInfo(PHI, PHI->getType(), {},
 817                                    MemoryKind::ExitPHI);
 818
 819   ScopStmt *IncomingStmt = scop->getStmtFor(IncomingBlock);
 820   if (!IncomingStmt)
 821     return;
 822
 823   // Take care for the incoming value being available in the incoming block.
 824   // This must be done before the check for multiple PHI writes because multiple
 825   // exiting edges from subregion each can be the effective written value of the
 826   // subregion. As such, all of them must be made available in the subregion
 827   // statement.
 828   ensureValueRead(IncomingValue, IncomingBlock);
 829
 830   // Do not add more than one MemoryAccess per PHINode and ScopStmt.
 831   if (MemoryAccess *Acc = IncomingStmt->lookupPHIWriteOf(PHI)) {
 832     assert(Acc->getAccessInstruction() == PHI);
 833     Acc->addIncoming(IncomingBlock, IncomingValue);
 834     return;
 835   }
 836
 837   MemoryAccess *Acc =
 838       addMemoryAccess(IncomingStmt->getEntryBlock(), PHI,
 839                       MemoryAccess::MUST_WRITE, PHI, PHI->getType(), true, PHI,
 840                       ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
 841                       IsExitBlock ? MemoryKind::ExitPHI : MemoryKind::PHI);
 842   assert(Acc);
 843   Acc->addIncoming(IncomingBlock, IncomingValue);
 844 }
 845
 846 void ScopBuilder::addPHIReadAccess(PHINode *PHI) {
 847   addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI,
 848                   PHI->getType(), true, PHI, ArrayRef<const SCEV *>(),
 849                   ArrayRef<const SCEV *>(), MemoryKind::PHI);
 850 }
 851
 852 #ifndef NDEBUG
 853 static void verifyUse(Scop *S, Use &Op, LoopInfo &LI) {
 854   auto PhysUse = VirtualUse::create(S, Op, &LI, false);
 855   auto VirtUse = VirtualUse::create(S, Op, &LI, true);
 856   assert(PhysUse.getKind() == VirtUse.getKind());
 857 }
 858
 859 /// Check the consistency of every statement's MemoryAccesses.
 860 ///
 861 /// The check is carried out by expecting the "physical" kind of use (derived
 862 /// from the BasicBlocks instructions resides in) to be same as the "virtual"
 863 /// kind of use (derived from a statement's MemoryAccess).
 864 ///
 865 /// The "physical" uses are taken by ensureValueRead to determine whether to
 866 /// create MemoryAccesses. When done, the kind of scalar access should be the
 867 /// same no matter which way it was derived.
 868 ///
 869 /// The MemoryAccesses might be changed by later SCoP-modifying passes and hence
 870 /// can intentionally influence on the kind of uses (not corresponding to the
 871 /// "physical" anymore, hence called "virtual"). The CodeGenerator therefore has
 872 /// to pick up the virtual uses. But here in the code generator, this has not
 873 /// happened yet, such that virtual and physical uses are equivalent.
 874 static void verifyUses(Scop *S, LoopInfo &LI, DominatorTree &DT) {
 875   for (auto *BB : S->getRegion().blocks()) {
 876     auto *Stmt = S->getStmtFor(BB);
 877     if (!Stmt)
 878       continue;
 879
 880     for (auto &Inst : *BB) {
 881       if (isIgnoredIntrinsic(&Inst))
 882         continue;
 883
 884       // Branch conditions are encoded in the statement domains.
 885       if (isa<TerminatorInst>(&Inst) && Stmt->isBlockStmt())
 886         continue;
 887
 888       // Verify all uses.
 889       for (auto &Op : Inst.operands())
 890         verifyUse(S, Op, LI);
 891
 892       // Stores do not produce values used by other statements.
 893       if (isa<StoreInst>(Inst))
 894         continue;
 895
 896       // For every value defined in the block, also check that a use of that
 897       // value in the same statement would not be an inter-statement use. It can
 898       // still be synthesizable or load-hoisted, but these kind of instructions
 899       // are not directly copied in code-generation.
 900       auto VirtDef =
 901           VirtualUse::create(S, Stmt, Stmt->getSurroundingLoop(), &Inst, true);
 902       assert(VirtDef.getKind() == VirtualUse::Synthesizable ||
 903              VirtDef.getKind() == VirtualUse::Intra ||
 904              VirtDef.getKind() == VirtualUse::Hoisted);
 905     }
 906   }
 907
 908   if (S->hasSingleExitEdge())
 909     return;
 910
 911   // PHINodes in the SCoP region's exit block are also uses to be checked.
 912   if (!S->getRegion().isTopLevelRegion()) {
 913     for (auto &Inst : *S->getRegion().getExit()) {
 914       if (!isa<PHINode>(Inst))
 915         break;
 916
 917       for (auto &Op : Inst.operands())
 918         verifyUse(S, Op, LI);
 919     }
 920   }
 921 }
 922 #endif
 923
 924 void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) {
 925   scop.reset(new Scop(R, SE, LI, *SD.getDetectionContext(&R)));
 926
 927   buildStmts(R);
 928   buildAccessFunctions(R);
 929
 930   // In case the region does not have an exiting block we will later (during
 931   // code generation) split the exit block. This will move potential PHI nodes
 932   // from the current exit block into the new region exiting block. Hence, PHI
 933   // nodes that are at this point not part of the region will be.
 934   // To handle these PHI nodes later we will now model their operands as scalar
 935   // accesses. Note that we do not model anything in the exit block if we have
 936   // an exiting block in the region, as there will not be any splitting later.
 937   if (!R.isTopLevelRegion() && !scop->hasSingleExitEdge())
 938     buildAccessFunctions(*R.getExit(), nullptr,
 939                          /* IsExitBlock */ true);
 940
 941   // Create memory accesses for global reads since all arrays are now known.
 942   auto *AF = SE.getConstant(IntegerType::getInt64Ty(SE.getContext()), 0);
 943   for (auto *GlobalRead : GlobalReads)
 944     for (auto *BP : ArrayBasePointers)
 945       addArrayAccess(MemAccInst(GlobalRead), MemoryAccess::READ, BP,
 946                      BP->getType(), false, {AF}, {nullptr}, GlobalRead);
 947
 948   scop->buildInvariantEquivalenceClasses();
 949
 950   if (!scop->buildDomains(&R, DT, LI))
 951     return;
 952
 953   scop->addUserAssumptions(AC, DT, LI);
 954
 955   // Remove empty statements.
 956   // Exit early in case there are no executable statements left in this scop.
 957   scop->simplifySCoP(false);
 958   if (scop->isEmpty())
 959     return;
 960
 961   // The ScopStmts now have enough information to initialize themselves.
 962   for (ScopStmt &Stmt : *scop)
 963     Stmt.init(LI);
 964
 965   // Check early for a feasible runtime context.
 966   if (!scop->hasFeasibleRuntimeContext())
 967     return;
 968
 969   // Check early for profitability. Afterwards it cannot change anymore,
 970   // only the runtime context could become infeasible.
 971   if (!scop->isProfitable(UnprofitableScalarAccs)) {
 972     scop->invalidate(PROFITABLE, DebugLoc());
 973     return;
 974   }
 975
 976   scop->buildSchedule(LI);
 977
 978   scop->finalizeAccesses();
 979
 980   scop->realignParams();
 981   scop->addUserContext();
 982
 983   // After the context was fully constructed, thus all our knowledge about
 984   // the parameters is in there, we add all recorded assumptions to the
 985   // assumed/invalid context.
 986   scop->addRecordedAssumptions();
 987
 988   scop->simplifyContexts();
 989   if (!scop->buildAliasChecks(AA))
 990     return;
 991
 992   scop->hoistInvariantLoads();
 993   scop->canonicalizeDynamicBasePtrs();
 994   scop->verifyInvariantLoads();
 995   scop->simplifySCoP(true);
 996
 997   // Check late for a feasible runtime context because profitability did not
 998   // change.
 999   if (!scop->hasFeasibleRuntimeContext())
1000     return;
1001
1002 #ifndef NDEBUG
1003   verifyUses(scop.get(), LI, DT);
1004 #endif
1005 }
1006
1007 ScopBuilder::ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA,
1008                          const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
1009                          ScopDetection &SD, ScalarEvolution &SE)
1010     : AA(AA), DL(DL), DT(DT), LI(LI), SD(SD), SE(SE) {
1011
1012   Function *F = R->getEntry()->getParent();
1013
1014   DebugLoc Beg, End;
1015   getDebugLocations(getBBPairForRegion(R), Beg, End);
1016   std::string Msg = "SCoP begins here.";
1017   emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE, *F, Beg, Msg);
1018
1019   buildScop(*R, AC);
1020
1021   DEBUG(scop->print(dbgs()));
1022
1023   if (!scop->hasFeasibleRuntimeContext()) {
1024     InfeasibleScops++;
1025     Msg = "SCoP ends here but was dismissed.";
1026     scop.reset();
1027   } else {
1028     Msg = "SCoP ends here.";
1029     ++ScopFound;
1030     if (scop->getMaxLoopDepth() > 0)
1031       ++RichScopFound;
1032   }
1033
1034   emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE, *F, End, Msg);
1035 }