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::findFADGlobalNonAlloc(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::findFADGlobalAlloc(MemAccInst Inst) {
 276   // match: 3
 277   if (!isa<LoadInst>(Inst) && !isa<StoreInst>(Inst))
 278     return nullptr;
 279
 280   // match: 3
 281   if (Inst.getAlignment() != 8)
 282     return nullptr;
 283
 284   Value *Slot = Inst.getPointerOperand();
 285
 286   LoadInst *MemLoad = nullptr;
 287   // [match: 2]
 288   if (auto *SlotGEP = dyn_cast<GetElementPtrInst>(Slot)) {
 289     // match: 1
 290     MemLoad = dyn_cast<LoadInst>(SlotGEP->getPointerOperand());
 291   } else {
 292     // match: 1
 293     MemLoad = dyn_cast<LoadInst>(Slot);
 294   }
 295
 296   if (!MemLoad)
 297     return nullptr;
 298
 299   auto *BitcastOperator =
 300       dyn_cast<BitCastOperator>(MemLoad->getPointerOperand());
 301   if (!BitcastOperator)
 302     return nullptr;
 303
 304   Value *Descriptor = dyn_cast<Value>(BitcastOperator->getOperand(0));
 305   if (!Descriptor)
 306     return nullptr;
 307
 308   if (!isFortranArrayDescriptor(Descriptor))
 309     return nullptr;
 310
 311   return Descriptor;
 312 }
 313
 314 Value *ScopBuilder::findFADLocalNonAlloc(MemAccInst Inst) {
 315   // match: 3
 316   if (!isa<LoadInst>(Inst) && !isa<StoreInst>(Inst))
 317     return nullptr;
 318
 319   // match: 3
 320   if (Inst.getAlignment() != 8)
 321     return nullptr;
 322
 323   Value *Slot = Inst.getPointerOperand();
 324
 325   BitCastOperator *MemBitcast = nullptr;
 326   // [match: 2]
 327   if (auto *SlotGEP = dyn_cast<GetElementPtrInst>(Slot)) {
 328     // match: 1
 329     MemBitcast = dyn_cast<BitCastOperator>(SlotGEP->getPointerOperand());
 330   } else {
 331     // match: 1
 332     MemBitcast = dyn_cast<BitCastOperator>(Slot);
 333   }
 334
 335   if (!MemBitcast)
 336     return nullptr;
 337
 338   Value *Descriptor = dyn_cast<Value>(MemBitcast->getOperand(0));
 339   if (!Descriptor)
 340     return nullptr;
 341
 342   if (!isFortranArrayDescriptor(Descriptor))
 343     return nullptr;
 344
 345   return Descriptor;
 346 }
 347
 348 bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt) {
 349   Value *Val = Inst.getValueOperand();
 350   Type *ElementType = Val->getType();
 351   Value *Address = Inst.getPointerOperand();
 352   const SCEV *AccessFunction =
 353       SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));
 354   const SCEVUnknown *BasePointer =
 355       dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
 356   enum MemoryAccess::AccessType AccType =
 357       isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
 358
 359   if (auto *BitCast = dyn_cast<BitCastInst>(Address)) {
 360     auto *Src = BitCast->getOperand(0);
 361     auto *SrcTy = Src->getType();
 362     auto *DstTy = BitCast->getType();
 363     // Do not try to delinearize non-sized (opaque) pointers.
 364     if ((SrcTy->isPointerTy() && !SrcTy->getPointerElementType()->isSized()) ||
 365         (DstTy->isPointerTy() && !DstTy->getPointerElementType()->isSized())) {
 366       return false;
 367     }
 368     if (SrcTy->isPointerTy() && DstTy->isPointerTy() &&
 369         DL.getTypeAllocSize(SrcTy->getPointerElementType()) ==
 370             DL.getTypeAllocSize(DstTy->getPointerElementType()))
 371       Address = Src;
 372   }
 373
 374   auto *GEP = dyn_cast<GetElementPtrInst>(Address);
 375   if (!GEP)
 376     return false;
 377
 378   std::vector<const SCEV *> Subscripts;
 379   std::vector<int> Sizes;
 380   std::tie(Subscripts, Sizes) = getIndexExpressionsFromGEP(GEP, SE);
 381   auto *BasePtr = GEP->getOperand(0);
 382
 383   if (auto *BasePtrCast = dyn_cast<BitCastInst>(BasePtr))
 384     BasePtr = BasePtrCast->getOperand(0);
 385
 386   // Check for identical base pointers to ensure that we do not miss index
 387   // offsets that have been added before this GEP is applied.
 388   if (BasePtr != BasePointer->getValue())
 389     return false;
 390
 391   std::vector<const SCEV *> SizesSCEV;
 392
 393   const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
 394
 395   Loop *SurroundingLoop = Stmt->getSurroundingLoop();
 396   for (auto *Subscript : Subscripts) {
 397     InvariantLoadsSetTy AccessILS;
 398     if (!isAffineExpr(&scop->getRegion(), SurroundingLoop, Subscript, SE,
 399                       &AccessILS))
 400       return false;
 401
 402     for (LoadInst *LInst : AccessILS)
 403       if (!ScopRIL.count(LInst))
 404         return false;
 405   }
 406
 407   if (Sizes.empty())
 408     return false;
 409
 410   SizesSCEV.push_back(nullptr);
 411
 412   for (auto V : Sizes)
 413     SizesSCEV.push_back(SE.getSCEV(
 414         ConstantInt::get(IntegerType::getInt64Ty(BasePtr->getContext()), V)));
 415
 416   addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, true,
 417                  Subscripts, SizesSCEV, Val);
 418   return true;
 419 }
 420
 421 bool ScopBuilder::buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt) {
 422   if (!PollyDelinearize)
 423     return false;
 424
 425   Value *Address = Inst.getPointerOperand();
 426   Value *Val = Inst.getValueOperand();
 427   Type *ElementType = Val->getType();
 428   unsigned ElementSize = DL.getTypeAllocSize(ElementType);
 429   enum MemoryAccess::AccessType AccType =
 430       isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
 431
 432   const SCEV *AccessFunction =
 433       SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));
 434   const SCEVUnknown *BasePointer =
 435       dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
 436
 437   assert(BasePointer && "Could not find base pointer");
 438
 439   auto &InsnToMemAcc = scop->getInsnToMemAccMap();
 440   auto AccItr = InsnToMemAcc.find(Inst);
 441   if (AccItr == InsnToMemAcc.end())
 442     return false;
 443
 444   std::vector<const SCEV *> Sizes = {nullptr};
 445
 446   Sizes.insert(Sizes.end(), AccItr->second.Shape->DelinearizedSizes.begin(),
 447                AccItr->second.Shape->DelinearizedSizes.end());
 448   // Remove the element size. This information is already provided by the
 449   // ElementSize parameter. In case the element size of this access and the
 450   // element size used for delinearization differs the delinearization is
 451   // incorrect. Hence, we invalidate the scop.
 452   //
 453   // TODO: Handle delinearization with differing element sizes.
 454   auto DelinearizedSize =
 455       cast<SCEVConstant>(Sizes.back())->getAPInt().getSExtValue();
 456   Sizes.pop_back();
 457   if (ElementSize != DelinearizedSize)
 458     scop->invalidate(DELINEARIZATION, Inst->getDebugLoc());
 459
 460   addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, true,
 461                  AccItr->second.DelinearizedSubscripts, Sizes, Val);
 462   return true;
 463 }
 464
 465 bool ScopBuilder::buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt) {
 466   auto *MemIntr = dyn_cast_or_null<MemIntrinsic>(Inst);
 467
 468   if (MemIntr == nullptr)
 469     return false;
 470
 471   auto *L = LI.getLoopFor(Inst->getParent());
 472   auto *LengthVal = SE.getSCEVAtScope(MemIntr->getLength(), L);
 473   assert(LengthVal);
 474
 475   // Check if the length val is actually affine or if we overapproximate it
 476   InvariantLoadsSetTy AccessILS;
 477   const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
 478
 479   Loop *SurroundingLoop = Stmt->getSurroundingLoop();
 480   bool LengthIsAffine = isAffineExpr(&scop->getRegion(), SurroundingLoop,
 481                                      LengthVal, SE, &AccessILS);
 482   for (LoadInst *LInst : AccessILS)
 483     if (!ScopRIL.count(LInst))
 484       LengthIsAffine = false;
 485   if (!LengthIsAffine)
 486     LengthVal = nullptr;
 487
 488   auto *DestPtrVal = MemIntr->getDest();
 489   assert(DestPtrVal);
 490
 491   auto *DestAccFunc = SE.getSCEVAtScope(DestPtrVal, L);
 492   assert(DestAccFunc);
 493   // Ignore accesses to "NULL".
 494   // TODO: We could use this to optimize the region further, e.g., intersect
 495   //       the context with
 496   //          isl_set_complement(isl_set_params(getDomain()))
 497   //       as we know it would be undefined to execute this instruction anyway.
 498   if (DestAccFunc->isZero())
 499     return true;
 500
 501   auto *DestPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(DestAccFunc));
 502   assert(DestPtrSCEV);
 503   DestAccFunc = SE.getMinusSCEV(DestAccFunc, DestPtrSCEV);
 504   addArrayAccess(Inst, MemoryAccess::MUST_WRITE, DestPtrSCEV->getValue(),
 505                  IntegerType::getInt8Ty(DestPtrVal->getContext()),
 506                  LengthIsAffine, {DestAccFunc, LengthVal}, {nullptr},
 507                  Inst.getValueOperand());
 508
 509   auto *MemTrans = dyn_cast<MemTransferInst>(MemIntr);
 510   if (!MemTrans)
 511     return true;
 512
 513   auto *SrcPtrVal = MemTrans->getSource();
 514   assert(SrcPtrVal);
 515
 516   auto *SrcAccFunc = SE.getSCEVAtScope(SrcPtrVal, L);
 517   assert(SrcAccFunc);
 518   // Ignore accesses to "NULL".
 519   // TODO: See above TODO
 520   if (SrcAccFunc->isZero())
 521     return true;
 522
 523   auto *SrcPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(SrcAccFunc));
 524   assert(SrcPtrSCEV);
 525   SrcAccFunc = SE.getMinusSCEV(SrcAccFunc, SrcPtrSCEV);
 526   addArrayAccess(Inst, MemoryAccess::READ, SrcPtrSCEV->getValue(),
 527                  IntegerType::getInt8Ty(SrcPtrVal->getContext()),
 528                  LengthIsAffine, {SrcAccFunc, LengthVal}, {nullptr},
 529                  Inst.getValueOperand());
 530
 531   return true;
 532 }
 533
 534 bool ScopBuilder::buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt) {
 535   auto *CI = dyn_cast_or_null<CallInst>(Inst);
 536
 537   if (CI == nullptr)
 538     return false;
 539
 540   if (CI->doesNotAccessMemory() || isIgnoredIntrinsic(CI))
 541     return true;
 542
 543   bool ReadOnly = false;
 544   auto *AF = SE.getConstant(IntegerType::getInt64Ty(CI->getContext()), 0);
 545   auto *CalledFunction = CI->getCalledFunction();
 546   switch (AA.getModRefBehavior(CalledFunction)) {
 547   case FMRB_UnknownModRefBehavior:
 548     llvm_unreachable("Unknown mod ref behaviour cannot be represented.");
 549   case FMRB_DoesNotAccessMemory:
 550     return true;
 551   case FMRB_DoesNotReadMemory:
 552   case FMRB_OnlyAccessesInaccessibleMem:
 553   case FMRB_OnlyAccessesInaccessibleOrArgMem:
 554     return false;
 555   case FMRB_OnlyReadsMemory:
 556     GlobalReads.push_back(CI);
 557     return true;
 558   case FMRB_OnlyReadsArgumentPointees:
 559     ReadOnly = true;
 560   // Fall through
 561   case FMRB_OnlyAccessesArgumentPointees:
 562     auto AccType = ReadOnly ? MemoryAccess::READ : MemoryAccess::MAY_WRITE;
 563     Loop *L = LI.getLoopFor(Inst->getParent());
 564     for (const auto &Arg : CI->arg_operands()) {
 565       if (!Arg->getType()->isPointerTy())
 566         continue;
 567
 568       auto *ArgSCEV = SE.getSCEVAtScope(Arg, L);
 569       if (ArgSCEV->isZero())
 570         continue;
 571
 572       auto *ArgBasePtr = cast<SCEVUnknown>(SE.getPointerBase(ArgSCEV));
 573       addArrayAccess(Inst, AccType, ArgBasePtr->getValue(),
 574                      ArgBasePtr->getType(), false, {AF}, {nullptr}, CI);
 575     }
 576     return true;
 577   }
 578
 579   return true;
 580 }
 581
 582 void ScopBuilder::buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt) {
 583   Value *Address = Inst.getPointerOperand();
 584   Value *Val = Inst.getValueOperand();
 585   Type *ElementType = Val->getType();
 586   enum MemoryAccess::AccessType AccType =
 587       isa<LoadInst>(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
 588
 589   const SCEV *AccessFunction =
 590       SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));
 591   const SCEVUnknown *BasePointer =
 592       dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
 593
 594   assert(BasePointer && "Could not find base pointer");
 595   AccessFunction = SE.getMinusSCEV(AccessFunction, BasePointer);
 596
 597   // Check if the access depends on a loop contained in a non-affine subregion.
 598   bool isVariantInNonAffineLoop = false;
 599   SetVector<const Loop *> Loops;
 600   findLoops(AccessFunction, Loops);
 601   for (const Loop *L : Loops)
 602     if (Stmt->contains(L)) {
 603       isVariantInNonAffineLoop = true;
 604       break;
 605     }
 606
 607   InvariantLoadsSetTy AccessILS;
 608
 609   Loop *SurroundingLoop = Stmt->getSurroundingLoop();
 610   bool IsAffine = !isVariantInNonAffineLoop &&
 611                   isAffineExpr(&scop->getRegion(), SurroundingLoop,
 612                                AccessFunction, SE, &AccessILS);
 613
 614   const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
 615   for (LoadInst *LInst : AccessILS)
 616     if (!ScopRIL.count(LInst))
 617       IsAffine = false;
 618
 619   if (!IsAffine && AccType == MemoryAccess::MUST_WRITE)
 620     AccType = MemoryAccess::MAY_WRITE;
 621
 622   addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, IsAffine,
 623                  {AccessFunction}, {nullptr}, Val);
 624 }
 625
 626 void ScopBuilder::buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt) {
 627
 628   if (buildAccessMemIntrinsic(Inst, Stmt))
 629     return;
 630
 631   if (buildAccessCallInst(Inst, Stmt))
 632     return;
 633
 634   if (buildAccessMultiDimFixed(Inst, Stmt))
 635     return;
 636
 637   if (buildAccessMultiDimParam(Inst, Stmt))
 638     return;
 639
 640   buildAccessSingleDim(Inst, Stmt);
 641 }
 642
 643 void ScopBuilder::buildAccessFunctions(Region &SR) {
 644
 645   if (scop->isNonAffineSubRegion(&SR)) {
 646     for (BasicBlock *BB : SR.blocks())
 647       buildAccessFunctions(*BB, &SR);
 648     return;
 649   }
 650
 651   for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
 652     if (I->isSubRegion())
 653       buildAccessFunctions(*I->getNodeAs<Region>());
 654     else
 655       buildAccessFunctions(*I->getNodeAs<BasicBlock>());
 656 }
 657
 658 void ScopBuilder::buildStmts(Region &SR) {
 659
 660   if (scop->isNonAffineSubRegion(&SR)) {
 661     Loop *SurroundingLoop = LI.getLoopFor(SR.getEntry());
 662     auto &BoxedLoops = scop->getBoxedLoops();
 663     while (BoxedLoops.count(SurroundingLoop))
 664       SurroundingLoop = SurroundingLoop->getParentLoop();
 665     scop->addScopStmt(&SR, SurroundingLoop);
 666     return;
 667   }
 668
 669   for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
 670     if (I->isSubRegion())
 671       buildStmts(*I->getNodeAs<Region>());
 672     else {
 673       Loop *SurroundingLoop = LI.getLoopFor(I->getNodeAs<BasicBlock>());
 674       scop->addScopStmt(I->getNodeAs<BasicBlock>(), SurroundingLoop);
 675     }
 676 }
 677
 678 void ScopBuilder::buildAccessFunctions(BasicBlock &BB,
 679                                        Region *NonAffineSubRegion,
 680                                        bool IsExitBlock) {
 681   // We do not build access functions for error blocks, as they may contain
 682   // instructions we can not model.
 683   if (isErrorBlock(BB, scop->getRegion(), LI, DT) && !IsExitBlock)
 684     return;
 685
 686   ScopStmt *Stmt = scop->getStmtFor(&BB);
 687
 688   for (Instruction &Inst : BB) {
 689     PHINode *PHI = dyn_cast<PHINode>(&Inst);
 690     if (PHI)
 691       buildPHIAccesses(PHI, NonAffineSubRegion, IsExitBlock);
 692
 693     // For the exit block we stop modeling after the last PHI node.
 694     if (!PHI && IsExitBlock)
 695       break;
 696
 697     if (auto MemInst = MemAccInst::dyn_cast(Inst)) {
 698       assert(Stmt && "Cannot build access function in non-existing statement");
 699       buildMemoryAccess(MemInst, Stmt);
 700     }
 701
 702     if (isIgnoredIntrinsic(&Inst))
 703       continue;
 704
 705     // PHI nodes have already been modeled above and TerminatorInsts that are
 706     // not part of a non-affine subregion are fully modeled and regenerated
 707     // from the polyhedral domains. Hence, they do not need to be modeled as
 708     // explicit data dependences.
 709     if (!PHI && (!isa<TerminatorInst>(&Inst) || NonAffineSubRegion))
 710       buildScalarDependences(&Inst);
 711
 712     if (!IsExitBlock)
 713       buildEscapingDependences(&Inst);
 714   }
 715 }
 716
 717 MemoryAccess *ScopBuilder::addMemoryAccess(
 718     BasicBlock *BB, Instruction *Inst, MemoryAccess::AccessType AccType,
 719     Value *BaseAddress, Type *ElementType, bool Affine, Value *AccessValue,
 720     ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,
 721     MemoryKind Kind) {
 722   ScopStmt *Stmt = scop->getStmtFor(BB);
 723
 724   // Do not create a memory access for anything not in the SCoP. It would be
 725   // ignored anyway.
 726   if (!Stmt)
 727     return nullptr;
 728
 729   bool isKnownMustAccess = false;
 730
 731   // Accesses in single-basic block statements are always excuted.
 732   if (Stmt->isBlockStmt())
 733     isKnownMustAccess = true;
 734
 735   if (Stmt->isRegionStmt()) {
 736     // Accesses that dominate the exit block of a non-affine region are always
 737     // executed. In non-affine regions there may exist MemoryKind::Values that
 738     // do not dominate the exit. MemoryKind::Values will always dominate the
 739     // exit and MemoryKind::PHIs only if there is at most one PHI_WRITE in the
 740     // non-affine region.
 741     if (DT.dominates(BB, Stmt->getRegion()->getExit()))
 742       isKnownMustAccess = true;
 743   }
 744
 745   // Non-affine PHI writes do not "happen" at a particular instruction, but
 746   // after exiting the statement. Therefore they are guaranteed to execute and
 747   // overwrite the old value.
 748   if (Kind == MemoryKind::PHI || Kind == MemoryKind::ExitPHI)
 749     isKnownMustAccess = true;
 750
 751   if (!isKnownMustAccess && AccType == MemoryAccess::MUST_WRITE)
 752     AccType = MemoryAccess::MAY_WRITE;
 753
 754   auto *Access = new MemoryAccess(Stmt, Inst, AccType, BaseAddress, ElementType,
 755                                   Affine, Subscripts, Sizes, AccessValue, Kind);
 756
 757   scop->addAccessFunction(Access);
 758   Stmt->addAccess(Access);
 759   return Access;
 760 }
 761
 762 void ScopBuilder::addArrayAccess(
 763     MemAccInst MemAccInst, MemoryAccess::AccessType AccType, Value *BaseAddress,
 764     Type *ElementType, bool IsAffine, ArrayRef<const SCEV *> Subscripts,
 765     ArrayRef<const SCEV *> Sizes, Value *AccessValue) {
 766   ArrayBasePointers.insert(BaseAddress);
 767   auto *MemAccess = addMemoryAccess(
 768       MemAccInst->getParent(), MemAccInst, AccType, BaseAddress, ElementType,
 769       IsAffine, AccessValue, Subscripts, Sizes, MemoryKind::Array);
 770
 771   if (!DetectFortranArrays)
 772     return;
 773
 774   if (Value *FAD = findFADGlobalNonAlloc(MemAccInst))
 775     MemAccess->setFortranArrayDescriptor(FAD);
 776   else if (Value *FAD = findFADGlobalAlloc(MemAccInst))
 777     MemAccess->setFortranArrayDescriptor(FAD);
 778   else if (Value *FAD = findFADLocalNonAlloc(MemAccInst))
 779     MemAccess->setFortranArrayDescriptor(FAD);
 780 }
 781
 782 void ScopBuilder::ensureValueWrite(Instruction *Inst) {
 783   ScopStmt *Stmt = scop->getStmtFor(Inst);
 784
 785   // Inst not defined within this SCoP.
 786   if (!Stmt)
 787     return;
 788
 789   // Do not process further if the instruction is already written.
 790   if (Stmt->lookupValueWriteOf(Inst))
 791     return;
 792
 793   addMemoryAccess(Inst->getParent(), Inst, MemoryAccess::MUST_WRITE, Inst,
 794                   Inst->getType(), true, Inst, ArrayRef<const SCEV *>(),
 795                   ArrayRef<const SCEV *>(), MemoryKind::Value);
 796 }
 797
 798 void ScopBuilder::ensureValueRead(Value *V, BasicBlock *UserBB) {
 799   ScopStmt *UserStmt = scop->getStmtFor(UserBB);
 800   auto *Scope = LI.getLoopFor(UserBB);
 801   auto VUse = VirtualUse::create(scop.get(), UserStmt, Scope, V, false);
 802   switch (VUse.getKind()) {
 803   case VirtualUse::Constant:
 804   case VirtualUse::Block:
 805   case VirtualUse::Synthesizable:
 806   case VirtualUse::Hoisted:
 807   case VirtualUse::Intra:
 808     // Uses of these kinds do not need a MemoryAccess.
 809     break;
 810
 811   case VirtualUse::ReadOnly:
 812     // Add MemoryAccess for invariant values only if requested.
 813     if (!ModelReadOnlyScalars)
 814       break;
 815
 816     LLVM_FALLTHROUGH;
 817   case VirtualUse::Inter:
 818
 819     // Do not create another MemoryAccess for reloading the value if one already
 820     // exists.
 821     if (UserStmt->lookupValueReadOf(V))
 822       break;
 823
 824     addMemoryAccess(UserBB, nullptr, MemoryAccess::READ, V, V->getType(), true,
 825                     V, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
 826                     MemoryKind::Value);
 827
 828     // Inter-statement uses need to write the value in their defining statement.
 829     if (VUse.isInter())
 830       ensureValueWrite(cast<Instruction>(V));
 831     break;
 832   }
 833 }
 834
 835 void ScopBuilder::ensurePHIWrite(PHINode *PHI, BasicBlock *IncomingBlock,
 836                                  Value *IncomingValue, bool IsExitBlock) {
 837   // As the incoming block might turn out to be an error statement ensure we
 838   // will create an exit PHI SAI object. It is needed during code generation
 839   // and would be created later anyway.
 840   if (IsExitBlock)
 841     scop->getOrCreateScopArrayInfo(PHI, PHI->getType(), {},
 842                                    MemoryKind::ExitPHI);
 843
 844   ScopStmt *IncomingStmt = scop->getStmtFor(IncomingBlock);
 845   if (!IncomingStmt)
 846     return;
 847
 848   // Take care for the incoming value being available in the incoming block.
 849   // This must be done before the check for multiple PHI writes because multiple
 850   // exiting edges from subregion each can be the effective written value of the
 851   // subregion. As such, all of them must be made available in the subregion
 852   // statement.
 853   ensureValueRead(IncomingValue, IncomingBlock);
 854
 855   // Do not add more than one MemoryAccess per PHINode and ScopStmt.
 856   if (MemoryAccess *Acc = IncomingStmt->lookupPHIWriteOf(PHI)) {
 857     assert(Acc->getAccessInstruction() == PHI);
 858     Acc->addIncoming(IncomingBlock, IncomingValue);
 859     return;
 860   }
 861
 862   MemoryAccess *Acc =
 863       addMemoryAccess(IncomingStmt->getEntryBlock(), PHI,
 864                       MemoryAccess::MUST_WRITE, PHI, PHI->getType(), true, PHI,
 865                       ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
 866                       IsExitBlock ? MemoryKind::ExitPHI : MemoryKind::PHI);
 867   assert(Acc);
 868   Acc->addIncoming(IncomingBlock, IncomingValue);
 869 }
 870
 871 void ScopBuilder::addPHIReadAccess(PHINode *PHI) {
 872   addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI,
 873                   PHI->getType(), true, PHI, ArrayRef<const SCEV *>(),
 874                   ArrayRef<const SCEV *>(), MemoryKind::PHI);
 875 }
 876
 877 #ifndef NDEBUG
 878 static void verifyUse(Scop *S, Use &Op, LoopInfo &LI) {
 879   auto PhysUse = VirtualUse::create(S, Op, &LI, false);
 880   auto VirtUse = VirtualUse::create(S, Op, &LI, true);
 881   assert(PhysUse.getKind() == VirtUse.getKind());
 882 }
 883
 884 /// Check the consistency of every statement's MemoryAccesses.
 885 ///
 886 /// The check is carried out by expecting the "physical" kind of use (derived
 887 /// from the BasicBlocks instructions resides in) to be same as the "virtual"
 888 /// kind of use (derived from a statement's MemoryAccess).
 889 ///
 890 /// The "physical" uses are taken by ensureValueRead to determine whether to
 891 /// create MemoryAccesses. When done, the kind of scalar access should be the
 892 /// same no matter which way it was derived.
 893 ///
 894 /// The MemoryAccesses might be changed by later SCoP-modifying passes and hence
 895 /// can intentionally influence on the kind of uses (not corresponding to the
 896 /// "physical" anymore, hence called "virtual"). The CodeGenerator therefore has
 897 /// to pick up the virtual uses. But here in the code generator, this has not
 898 /// happened yet, such that virtual and physical uses are equivalent.
 899 static void verifyUses(Scop *S, LoopInfo &LI, DominatorTree &DT) {
 900   for (auto *BB : S->getRegion().blocks()) {
 901     auto *Stmt = S->getStmtFor(BB);
 902     if (!Stmt)
 903       continue;
 904
 905     for (auto &Inst : *BB) {
 906       if (isIgnoredIntrinsic(&Inst))
 907         continue;
 908
 909       // Branch conditions are encoded in the statement domains.
 910       if (isa<TerminatorInst>(&Inst) && Stmt->isBlockStmt())
 911         continue;
 912
 913       // Verify all uses.
 914       for (auto &Op : Inst.operands())
 915         verifyUse(S, Op, LI);
 916
 917       // Stores do not produce values used by other statements.
 918       if (isa<StoreInst>(Inst))
 919         continue;
 920
 921       // For every value defined in the block, also check that a use of that
 922       // value in the same statement would not be an inter-statement use. It can
 923       // still be synthesizable or load-hoisted, but these kind of instructions
 924       // are not directly copied in code-generation.
 925       auto VirtDef =
 926           VirtualUse::create(S, Stmt, Stmt->getSurroundingLoop(), &Inst, true);
 927       assert(VirtDef.getKind() == VirtualUse::Synthesizable ||
 928              VirtDef.getKind() == VirtualUse::Intra ||
 929              VirtDef.getKind() == VirtualUse::Hoisted);
 930     }
 931   }
 932
 933   if (S->hasSingleExitEdge())
 934     return;
 935
 936   // PHINodes in the SCoP region's exit block are also uses to be checked.
 937   for (auto &Inst : *S->getRegion().getExit()) {
 938     if (!isa<PHINode>(Inst))
 939       break;
 940
 941     for (auto &Op : Inst.operands())
 942       verifyUse(S, Op, LI);
 943   }
 944 }
 945 #endif
 946
 947 void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) {
 948   scop.reset(new Scop(R, SE, LI, *SD.getDetectionContext(&R)));
 949
 950   buildStmts(R);
 951   buildAccessFunctions(R);
 952
 953   // In case the region does not have an exiting block we will later (during
 954   // code generation) split the exit block. This will move potential PHI nodes
 955   // from the current exit block into the new region exiting block. Hence, PHI
 956   // nodes that are at this point not part of the region will be.
 957   // To handle these PHI nodes later we will now model their operands as scalar
 958   // accesses. Note that we do not model anything in the exit block if we have
 959   // an exiting block in the region, as there will not be any splitting later.
 960   if (!scop->hasSingleExitEdge())
 961     buildAccessFunctions(*R.getExit(), nullptr,
 962                          /* IsExitBlock */ true);
 963
 964   // Create memory accesses for global reads since all arrays are now known.
 965   auto *AF = SE.getConstant(IntegerType::getInt64Ty(SE.getContext()), 0);
 966   for (auto *GlobalRead : GlobalReads)
 967     for (auto *BP : ArrayBasePointers)
 968       addArrayAccess(MemAccInst(GlobalRead), MemoryAccess::READ, BP,
 969                      BP->getType(), false, {AF}, {nullptr}, GlobalRead);
 970
 971   scop->buildInvariantEquivalenceClasses();
 972
 973   if (!scop->buildDomains(&R, DT, LI))
 974     return;
 975
 976   scop->addUserAssumptions(AC, DT, LI);
 977
 978   // Remove empty statements.
 979   // Exit early in case there are no executable statements left in this scop.
 980   scop->simplifySCoP(false);
 981   if (scop->isEmpty())
 982     return;
 983
 984   // The ScopStmts now have enough information to initialize themselves.
 985   for (ScopStmt &Stmt : *scop)
 986     Stmt.init(LI);
 987
 988   // Check early for a feasible runtime context.
 989   if (!scop->hasFeasibleRuntimeContext())
 990     return;
 991
 992   // Check early for profitability. Afterwards it cannot change anymore,
 993   // only the runtime context could become infeasible.
 994   if (!scop->isProfitable(UnprofitableScalarAccs)) {
 995     scop->invalidate(PROFITABLE, DebugLoc());
 996     return;
 997   }
 998
 999   scop->buildSchedule(LI);
1000
1001   scop->finalizeAccesses();
1002
1003   scop->realignParams();
1004   scop->addUserContext();
1005
1006   // After the context was fully constructed, thus all our knowledge about
1007   // the parameters is in there, we add all recorded assumptions to the
1008   // assumed/invalid context.
1009   scop->addRecordedAssumptions();
1010
1011   scop->simplifyContexts();
1012   if (!scop->buildAliasChecks(AA))
1013     return;
1014
1015   scop->hoistInvariantLoads();
1016   scop->canonicalizeDynamicBasePtrs();
1017   scop->verifyInvariantLoads();
1018   scop->simplifySCoP(true);
1019
1020   // Check late for a feasible runtime context because profitability did not
1021   // change.
1022   if (!scop->hasFeasibleRuntimeContext())
1023     return;
1024
1025 #ifndef NDEBUG
1026   verifyUses(scop.get(), LI, DT);
1027 #endif
1028 }
1029
1030 ScopBuilder::ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA,
1031                          const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
1032                          ScopDetection &SD, ScalarEvolution &SE)
1033     : AA(AA), DL(DL), DT(DT), LI(LI), SD(SD), SE(SE) {
1034
1035   Function *F = R->getEntry()->getParent();
1036
1037   DebugLoc Beg, End;
1038   getDebugLocations(getBBPairForRegion(R), Beg, End);
1039   std::string Msg = "SCoP begins here.";
1040   emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE, *F, Beg, Msg);
1041
1042   buildScop(*R, AC);
1043
1044   DEBUG(scop->print(dbgs()));
1045
1046   if (!scop->hasFeasibleRuntimeContext()) {
1047     InfeasibleScops++;
1048     Msg = "SCoP ends here but was dismissed.";
1049     scop.reset();
1050   } else {
1051     Msg = "SCoP ends here.";
1052     ++ScopFound;
1053     if (scop->getMaxLoopDepth() > 0)
1054       ++RichScopFound;
1055   }
1056
1057   emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE, *F, End, Msg);
1058 }