lib/CodeGen/BlockGenerators.cpp

   1 //===--- BlockGenerators.cpp - Generate code for statements -----*- C++ -*-===//
   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 // This file implements the BlockGenerator and VectorBlockGenerator classes,
  11 // which generate sequential code and vectorized code for a polyhedral
  12 // statement, respectively.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "polly/CodeGen/BlockGenerators.h"
  17 #include "polly/CodeGen/CodeGeneration.h"
  18 #include "polly/CodeGen/IslExprBuilder.h"
  19 #include "polly/CodeGen/RuntimeDebugBuilder.h"
  20 #include "polly/Options.h"
  21 #include "polly/ScopInfo.h"
  22 #include "polly/Support/GICHelper.h"
  23 #include "polly/Support/SCEVValidator.h"
  24 #include "polly/Support/ScopHelper.h"
  25 #include "llvm/Analysis/LoopInfo.h"
  26 #include "llvm/Analysis/RegionInfo.h"
  27 #include "llvm/Analysis/ScalarEvolution.h"
  28 #include "llvm/IR/IntrinsicInst.h"
  29 #include "llvm/IR/Module.h"
  30 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  31 #include "llvm/Transforms/Utils/Local.h"
  32 #include "isl/aff.h"
  33 #include "isl/ast.h"
  34 #include "isl/ast_build.h"
  35 #include "isl/set.h"
  36 #include <deque>
  37
  38 using namespace llvm;
  39 using namespace polly;
  40
  41 static cl::opt<bool> Aligned("enable-polly-aligned",
  42                              cl::desc("Assumed aligned memory accesses."),
  43                              cl::Hidden, cl::init(false), cl::ZeroOrMore,
  44                              cl::cat(PollyCategory));
  45
  46 static cl::opt<bool> DebugPrinting(
  47     "polly-codegen-add-debug-printing",
  48     cl::desc("Add printf calls that show the values loaded/stored."),
  49     cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
  50
  51 BlockGenerator::BlockGenerator(PollyIRBuilder &B, LoopInfo &LI,
  52                                ScalarEvolution &SE, DominatorTree &DT,
  53                                ScalarAllocaMapTy &ScalarMap,
  54                                ScalarAllocaMapTy &PHIOpMap,
  55                                EscapeUsersAllocaMapTy &EscapeMap,
  56                                ValueMapT &GlobalMap,
  57                                IslExprBuilder *ExprBuilder)
  58     : Builder(B), LI(LI), SE(SE), ExprBuilder(ExprBuilder), DT(DT),
  59       EntryBB(nullptr), PHIOpMap(PHIOpMap), ScalarMap(ScalarMap),
  60       EscapeMap(EscapeMap), GlobalMap(GlobalMap) {}
  61
  62 Value *BlockGenerator::trySynthesizeNewValue(ScopStmt &Stmt, Value *Old,
  63                                              ValueMapT &BBMap,
  64                                              LoopToScevMapT &LTS,
  65                                              Loop *L) const {
  66   if (!SE.isSCEVable(Old->getType()))
  67     return nullptr;
  68
  69   const SCEV *Scev = SE.getSCEVAtScope(Old, L);
  70   if (!Scev)
  71     return nullptr;
  72
  73   if (isa<SCEVCouldNotCompute>(Scev))
  74     return nullptr;
  75
  76   const SCEV *NewScev = SCEVLoopAddRecRewriter::rewrite(Scev, LTS, SE);
  77   ValueMapT VTV;
  78   VTV.insert(BBMap.begin(), BBMap.end());
  79   VTV.insert(GlobalMap.begin(), GlobalMap.end());
  80
  81   Scop &S = *Stmt.getParent();
  82   const DataLayout &DL = S.getFunction().getParent()->getDataLayout();
  83   auto IP = Builder.GetInsertPoint();
  84
  85   assert(IP != Builder.GetInsertBlock()->end() &&
  86          "Only instructions can be insert points for SCEVExpander");
  87   Value *Expanded =
  88       expandCodeFor(S, SE, DL, "polly", NewScev, Old->getType(), &*IP, &VTV);
  89
  90   BBMap[Old] = Expanded;
  91   return Expanded;
  92 }
  93
  94 Value *BlockGenerator::getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap,
  95                                    LoopToScevMapT &LTS, Loop *L) const {
  96   // Constants that do not reference any named value can always remain
  97   // unchanged. Handle them early to avoid expensive map lookups. We do not take
  98   // the fast-path for external constants which are referenced through globals
  99   // as these may need to be rewritten when distributing code accross different
 100   // LLVM modules.
 101   if (isa<Constant>(Old) && !isa<GlobalValue>(Old))
 102     return Old;
 103
 104   // Inline asm is like a constant to us.
 105   if (isa<InlineAsm>(Old))
 106     return Old;
 107
 108   if (Value *New = GlobalMap.lookup(Old)) {
 109     if (Value *NewRemapped = GlobalMap.lookup(New))
 110       New = NewRemapped;
 111     if (Old->getType()->getScalarSizeInBits() <
 112         New->getType()->getScalarSizeInBits())
 113       New = Builder.CreateTruncOrBitCast(New, Old->getType());
 114
 115     return New;
 116   }
 117
 118   if (Value *New = BBMap.lookup(Old))
 119     return New;
 120
 121   if (Value *New = trySynthesizeNewValue(Stmt, Old, BBMap, LTS, L))
 122     return New;
 123
 124   // A scop-constant value defined by a global or a function parameter.
 125   if (isa<GlobalValue>(Old) || isa<Argument>(Old))
 126     return Old;
 127
 128   // A scop-constant value defined by an instruction executed outside the scop.
 129   if (const Instruction *Inst = dyn_cast<Instruction>(Old))
 130     if (!Stmt.getParent()->contains(Inst->getParent()))
 131       return Old;
 132
 133   // The scalar dependence is neither available nor SCEVCodegenable.
 134   llvm_unreachable("Unexpected scalar dependence in region!");
 135   return nullptr;
 136 }
 137
 138 void BlockGenerator::copyInstScalar(ScopStmt &Stmt, Instruction *Inst,
 139                                     ValueMapT &BBMap, LoopToScevMapT &LTS) {
 140   // We do not generate debug intrinsics as we did not investigate how to
 141   // copy them correctly. At the current state, they just crash the code
 142   // generation as the meta-data operands are not correctly copied.
 143   if (isa<DbgInfoIntrinsic>(Inst))
 144     return;
 145
 146   Instruction *NewInst = Inst->clone();
 147
 148   // Replace old operands with the new ones.
 149   for (Value *OldOperand : Inst->operands()) {
 150     Value *NewOperand =
 151         getNewValue(Stmt, OldOperand, BBMap, LTS, getLoopForStmt(Stmt));
 152
 153     if (!NewOperand) {
 154       assert(!isa<StoreInst>(NewInst) &&
 155              "Store instructions are always needed!");
 156       delete NewInst;
 157       return;
 158     }
 159
 160     NewInst->replaceUsesOfWith(OldOperand, NewOperand);
 161   }
 162
 163   Builder.Insert(NewInst);
 164   BBMap[Inst] = NewInst;
 165
 166   if (!NewInst->getType()->isVoidTy())
 167     NewInst->setName("p_" + Inst->getName());
 168 }
 169
 170 Value *
 171 BlockGenerator::generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst,
 172                                          ValueMapT &BBMap, LoopToScevMapT &LTS,
 173                                          isl_id_to_ast_expr *NewAccesses) {
 174   const MemoryAccess &MA = Stmt.getArrayAccessFor(Inst);
 175
 176   isl_ast_expr *AccessExpr = isl_id_to_ast_expr_get(NewAccesses, MA.getId());
 177
 178   if (AccessExpr) {
 179     AccessExpr = isl_ast_expr_address_of(AccessExpr);
 180     auto Address = ExprBuilder->create(AccessExpr);
 181
 182     // Cast the address of this memory access to a pointer type that has the
 183     // same element type as the original access, but uses the address space of
 184     // the newly generated pointer.
 185     auto OldPtrTy = MA.getAccessValue()->getType()->getPointerTo();
 186     auto NewPtrTy = Address->getType();
 187     OldPtrTy = PointerType::get(OldPtrTy->getElementType(),
 188                                 NewPtrTy->getPointerAddressSpace());
 189
 190     if (OldPtrTy != NewPtrTy)
 191       Address = Builder.CreateBitOrPointerCast(Address, OldPtrTy);
 192     return Address;
 193   }
 194
 195   return getNewValue(Stmt, Inst.getPointerOperand(), BBMap, LTS,
 196                      getLoopForStmt(Stmt));
 197 }
 198
 199 Loop *BlockGenerator::getLoopForStmt(const ScopStmt &Stmt) const {
 200   auto *StmtBB = Stmt.getEntryBlock();
 201   return LI.getLoopFor(StmtBB);
 202 }
 203
 204 Value *BlockGenerator::generateScalarLoad(ScopStmt &Stmt, LoadInst *Load,
 205                                           ValueMapT &BBMap, LoopToScevMapT &LTS,
 206                                           isl_id_to_ast_expr *NewAccesses) {
 207   if (Value *PreloadLoad = GlobalMap.lookup(Load))
 208     return PreloadLoad;
 209
 210   Value *NewPointer =
 211       generateLocationAccessed(Stmt, Load, BBMap, LTS, NewAccesses);
 212   Value *ScalarLoad = Builder.CreateAlignedLoad(
 213       NewPointer, Load->getAlignment(), Load->getName() + "_p_scalar_");
 214
 215   if (DebugPrinting)
 216     RuntimeDebugBuilder::createCPUPrinter(Builder, "Load from ", NewPointer,
 217                                           ": ", ScalarLoad, "\n");
 218
 219   return ScalarLoad;
 220 }
 221
 222 void BlockGenerator::generateScalarStore(ScopStmt &Stmt, StoreInst *Store,
 223                                          ValueMapT &BBMap, LoopToScevMapT &LTS,
 224                                          isl_id_to_ast_expr *NewAccesses) {
 225   Value *NewPointer =
 226       generateLocationAccessed(Stmt, Store, BBMap, LTS, NewAccesses);
 227   Value *ValueOperand = getNewValue(Stmt, Store->getValueOperand(), BBMap, LTS,
 228                                     getLoopForStmt(Stmt));
 229
 230   if (DebugPrinting)
 231     RuntimeDebugBuilder::createCPUPrinter(Builder, "Store to  ", NewPointer,
 232                                           ": ", ValueOperand, "\n");
 233
 234   Builder.CreateAlignedStore(ValueOperand, NewPointer, Store->getAlignment());
 235 }
 236
 237 bool BlockGenerator::canSyntheziseInStmt(ScopStmt &Stmt, Instruction *Inst) {
 238   Loop *L = getLoopForStmt(Stmt);
 239   return (Stmt.isBlockStmt() || !Stmt.getRegion()->contains(L)) &&
 240          canSynthesize(Inst, *Stmt.getParent(), &LI, &SE, L);
 241 }
 242
 243 void BlockGenerator::copyInstruction(ScopStmt &Stmt, Instruction *Inst,
 244                                      ValueMapT &BBMap, LoopToScevMapT &LTS,
 245                                      isl_id_to_ast_expr *NewAccesses) {
 246   // Terminator instructions control the control flow. They are explicitly
 247   // expressed in the clast and do not need to be copied.
 248   if (Inst->isTerminator())
 249     return;
 250
 251   // Synthesizable statements will be generated on-demand.
 252   if (canSyntheziseInStmt(Stmt, Inst))
 253     return;
 254
 255   if (auto *Load = dyn_cast<LoadInst>(Inst)) {
 256     Value *NewLoad = generateScalarLoad(Stmt, Load, BBMap, LTS, NewAccesses);
 257     // Compute NewLoad before its insertion in BBMap to make the insertion
 258     // deterministic.
 259     BBMap[Load] = NewLoad;
 260     return;
 261   }
 262
 263   if (auto *Store = dyn_cast<StoreInst>(Inst)) {
 264     generateScalarStore(Stmt, Store, BBMap, LTS, NewAccesses);
 265     return;
 266   }
 267
 268   if (auto *PHI = dyn_cast<PHINode>(Inst)) {
 269     copyPHIInstruction(Stmt, PHI, BBMap, LTS);
 270     return;
 271   }
 272
 273   // Skip some special intrinsics for which we do not adjust the semantics to
 274   // the new schedule. All others are handled like every other instruction.
 275   if (isIgnoredIntrinsic(Inst))
 276     return;
 277
 278   copyInstScalar(Stmt, Inst, BBMap, LTS);
 279 }
 280
 281 void BlockGenerator::removeDeadInstructions(BasicBlock *BB, ValueMapT &BBMap) {
 282   for (auto I = BB->rbegin(), E = BB->rend(); I != E; I++) {
 283     Instruction *Inst = &*I;
 284     Value *NewVal = BBMap[Inst];
 285
 286     if (!NewVal)
 287       continue;
 288
 289     Instruction *NewInst = dyn_cast<Instruction>(NewVal);
 290
 291     if (!NewInst)
 292       continue;
 293
 294     if (!isInstructionTriviallyDead(NewInst))
 295       continue;
 296
 297     BBMap.erase(Inst);
 298     NewInst->eraseFromParent();
 299   }
 300 }
 301
 302 void BlockGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
 303                               isl_id_to_ast_expr *NewAccesses) {
 304   assert(Stmt.isBlockStmt() &&
 305          "Only block statements can be copied by the block generator");
 306
 307   ValueMapT BBMap;
 308
 309   BasicBlock *BB = Stmt.getBasicBlock();
 310   copyBB(Stmt, BB, BBMap, LTS, NewAccesses);
 311   removeDeadInstructions(BB, BBMap);
 312 }
 313
 314 BasicBlock *BlockGenerator::splitBB(BasicBlock *BB) {
 315   BasicBlock *CopyBB = SplitBlock(Builder.GetInsertBlock(),
 316                                   &*Builder.GetInsertPoint(), &DT, &LI);
 317   CopyBB->setName("polly.stmt." + BB->getName());
 318   return CopyBB;
 319 }
 320
 321 BasicBlock *BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB,
 322                                    ValueMapT &BBMap, LoopToScevMapT &LTS,
 323                                    isl_id_to_ast_expr *NewAccesses) {
 324   BasicBlock *CopyBB = splitBB(BB);
 325   Builder.SetInsertPoint(&CopyBB->front());
 326   generateScalarLoads(Stmt, BBMap);
 327
 328   copyBB(Stmt, BB, CopyBB, BBMap, LTS, NewAccesses);
 329
 330   // After a basic block was copied store all scalars that escape this block in
 331   // their alloca.
 332   generateScalarStores(Stmt, LTS, BBMap);
 333   return CopyBB;
 334 }
 335
 336 void BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *CopyBB,
 337                             ValueMapT &BBMap, LoopToScevMapT &LTS,
 338                             isl_id_to_ast_expr *NewAccesses) {
 339   EntryBB = &CopyBB->getParent()->getEntryBlock();
 340
 341   for (Instruction &Inst : *BB)
 342     copyInstruction(Stmt, &Inst, BBMap, LTS, NewAccesses);
 343 }
 344
 345 Value *BlockGenerator::getOrCreateAlloca(Value *ScalarBase,
 346                                          ScalarAllocaMapTy &Map,
 347                                          const char *NameExt) {
 348   // If no alloca was found create one and insert it in the entry block.
 349   if (!Map.count(ScalarBase)) {
 350     auto *Ty = ScalarBase->getType();
 351     auto NewAddr = new AllocaInst(Ty, ScalarBase->getName() + NameExt);
 352     EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock();
 353     NewAddr->insertBefore(&*EntryBB->getFirstInsertionPt());
 354     Map[ScalarBase] = NewAddr;
 355   }
 356
 357   auto Addr = Map[ScalarBase];
 358
 359   if (auto NewAddr = GlobalMap.lookup(Addr))
 360     return NewAddr;
 361
 362   return Addr;
 363 }
 364
 365 Value *BlockGenerator::getOrCreateAlloca(const MemoryAccess &Access) {
 366   if (Access.isPHIKind())
 367     return getOrCreatePHIAlloca(Access.getBaseAddr());
 368   else
 369     return getOrCreateScalarAlloca(Access.getBaseAddr());
 370 }
 371
 372 Value *BlockGenerator::getOrCreateAlloca(const ScopArrayInfo *Array) {
 373   if (Array->isPHIKind())
 374     return getOrCreatePHIAlloca(Array->getBasePtr());
 375   else
 376     return getOrCreateScalarAlloca(Array->getBasePtr());
 377 }
 378
 379 Value *BlockGenerator::getOrCreateScalarAlloca(Value *ScalarBase) {
 380   return getOrCreateAlloca(ScalarBase, ScalarMap, ".s2a");
 381 }
 382
 383 Value *BlockGenerator::getOrCreatePHIAlloca(Value *ScalarBase) {
 384   return getOrCreateAlloca(ScalarBase, PHIOpMap, ".phiops");
 385 }
 386
 387 void BlockGenerator::handleOutsideUsers(const Scop &S, Instruction *Inst) {
 388   // If there are escape users we get the alloca for this instruction and put it
 389   // in the EscapeMap for later finalization. Lastly, if the instruction was
 390   // copied multiple times we already did this and can exit.
 391   if (EscapeMap.count(Inst))
 392     return;
 393
 394   EscapeUserVectorTy EscapeUsers;
 395   for (User *U : Inst->users()) {
 396
 397     // Non-instruction user will never escape.
 398     Instruction *UI = dyn_cast<Instruction>(U);
 399     if (!UI)
 400       continue;
 401
 402     if (S.contains(UI))
 403       continue;
 404
 405     EscapeUsers.push_back(UI);
 406   }
 407
 408   // Exit if no escape uses were found.
 409   if (EscapeUsers.empty())
 410     return;
 411
 412   // Get or create an escape alloca for this instruction.
 413   auto *ScalarAddr = getOrCreateScalarAlloca(Inst);
 414
 415   // Remember that this instruction has escape uses and the escape alloca.
 416   EscapeMap[Inst] = std::make_pair(ScalarAddr, std::move(EscapeUsers));
 417 }
 418
 419 void BlockGenerator::generateScalarLoads(ScopStmt &Stmt, ValueMapT &BBMap) {
 420   for (MemoryAccess *MA : Stmt) {
 421     if (MA->isArrayKind() || MA->isWrite())
 422       continue;
 423
 424     auto *Address = getOrCreateAlloca(*MA);
 425     assert((!isa<Instruction>(Address) ||
 426             DT.dominates(cast<Instruction>(Address)->getParent(),
 427                          Builder.GetInsertBlock())) &&
 428            "Domination violation");
 429     BBMap[MA->getBaseAddr()] =
 430         Builder.CreateLoad(Address, Address->getName() + ".reload");
 431   }
 432 }
 433
 434 void BlockGenerator::generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
 435                                           ValueMapT &BBMap) {
 436   Loop *L = LI.getLoopFor(Stmt.getBasicBlock());
 437
 438   assert(Stmt.isBlockStmt() && "Region statements need to use the "
 439                                "generateScalarStores() function in the "
 440                                "RegionGenerator");
 441
 442   for (MemoryAccess *MA : Stmt) {
 443     if (MA->isArrayKind() || MA->isRead())
 444       continue;
 445
 446     Value *Val = MA->getAccessValue();
 447     if (MA->isAnyPHIKind()) {
 448       assert(MA->getIncoming().size() >= 1 &&
 449              "Block statements have exactly one exiting block, or multiple but "
 450              "with same incoming block and value");
 451       assert(std::all_of(MA->getIncoming().begin(), MA->getIncoming().end(),
 452                          [&](std::pair<BasicBlock *, Value *> p) -> bool {
 453                            return p.first == Stmt.getBasicBlock();
 454                          }) &&
 455              "Incoming block must be statement's block");
 456       Val = MA->getIncoming()[0].second;
 457     }
 458     auto *Address = getOrCreateAlloca(*MA);
 459
 460     Val = getNewValue(Stmt, Val, BBMap, LTS, L);
 461     assert((!isa<Instruction>(Val) ||
 462             DT.dominates(cast<Instruction>(Val)->getParent(),
 463                          Builder.GetInsertBlock())) &&
 464            "Domination violation");
 465     assert((!isa<Instruction>(Address) ||
 466             DT.dominates(cast<Instruction>(Address)->getParent(),
 467                          Builder.GetInsertBlock())) &&
 468            "Domination violation");
 469     Builder.CreateStore(Val, Address);
 470   }
 471 }
 472
 473 void BlockGenerator::createScalarInitialization(Scop &S) {
 474   BasicBlock *ExitBB = S.getExit();
 475
 476   // The split block __just before__ the region and optimized region.
 477   BasicBlock *SplitBB = S.getEnteringBlock();
 478   BranchInst *SplitBBTerm = cast<BranchInst>(SplitBB->getTerminator());
 479   assert(SplitBBTerm->getNumSuccessors() == 2 && "Bad region entering block!");
 480
 481   // Get the start block of the __optimized__ region.
 482   BasicBlock *StartBB = SplitBBTerm->getSuccessor(0);
 483   if (StartBB == S.getEntry())
 484     StartBB = SplitBBTerm->getSuccessor(1);
 485
 486   Builder.SetInsertPoint(StartBB->getTerminator());
 487
 488   for (auto &Array : S.arrays()) {
 489     if (Array->getNumberOfDimensions() != 0)
 490       continue;
 491     if (Array->isPHIKind()) {
 492       // For PHI nodes, the only values we need to store are the ones that
 493       // reach the PHI node from outside the region. In general there should
 494       // only be one such incoming edge and this edge should enter through
 495       // 'SplitBB'.
 496       auto PHI = cast<PHINode>(Array->getBasePtr());
 497
 498       for (auto BI = PHI->block_begin(), BE = PHI->block_end(); BI != BE; BI++)
 499         if (!S.contains(*BI) && *BI != SplitBB)
 500           llvm_unreachable("Incoming edges from outside the scop should always "
 501                            "come from SplitBB");
 502
 503       int Idx = PHI->getBasicBlockIndex(SplitBB);
 504       if (Idx < 0)
 505         continue;
 506
 507       Value *ScalarValue = PHI->getIncomingValue(Idx);
 508
 509       Builder.CreateStore(ScalarValue, getOrCreatePHIAlloca(PHI));
 510       continue;
 511     }
 512
 513     auto *Inst = dyn_cast<Instruction>(Array->getBasePtr());
 514
 515     if (Inst && S.contains(Inst))
 516       continue;
 517
 518     // PHI nodes that are not marked as such in their SAI object are either exit
 519     // PHI nodes we model as common scalars but without initialization, or
 520     // incoming phi nodes that need to be initialized. Check if the first is the
 521     // case for Inst and do not create and initialize memory if so.
 522     if (auto *PHI = dyn_cast_or_null<PHINode>(Inst))
 523       if (!S.hasSingleExitEdge() && PHI->getBasicBlockIndex(ExitBB) >= 0)
 524         continue;
 525
 526     Builder.CreateStore(Array->getBasePtr(),
 527                         getOrCreateScalarAlloca(Array->getBasePtr()));
 528   }
 529 }
 530
 531 void BlockGenerator::createScalarFinalization(Scop &S) {
 532   // The exit block of the __unoptimized__ region.
 533   BasicBlock *ExitBB = S.getExitingBlock();
 534   // The merge block __just after__ the region and the optimized region.
 535   BasicBlock *MergeBB = S.getExit();
 536
 537   // The exit block of the __optimized__ region.
 538   BasicBlock *OptExitBB = *(pred_begin(MergeBB));
 539   if (OptExitBB == ExitBB)
 540     OptExitBB = *(++pred_begin(MergeBB));
 541
 542   Builder.SetInsertPoint(OptExitBB->getTerminator());
 543   for (const auto &EscapeMapping : EscapeMap) {
 544     // Extract the escaping instruction and the escaping users as well as the
 545     // alloca the instruction was demoted to.
 546     Instruction *EscapeInst = EscapeMapping.getFirst();
 547     const auto &EscapeMappingValue = EscapeMapping.getSecond();
 548     const EscapeUserVectorTy &EscapeUsers = EscapeMappingValue.second;
 549     Value *ScalarAddr = EscapeMappingValue.first;
 550
 551     // Reload the demoted instruction in the optimized version of the SCoP.
 552     Value *EscapeInstReload =
 553         Builder.CreateLoad(ScalarAddr, EscapeInst->getName() + ".final_reload");
 554     EscapeInstReload =
 555         Builder.CreateBitOrPointerCast(EscapeInstReload, EscapeInst->getType());
 556
 557     // Create the merge PHI that merges the optimized and unoptimized version.
 558     PHINode *MergePHI = PHINode::Create(EscapeInst->getType(), 2,
 559                                         EscapeInst->getName() + ".merge");
 560     MergePHI->insertBefore(&*MergeBB->getFirstInsertionPt());
 561
 562     // Add the respective values to the merge PHI.
 563     MergePHI->addIncoming(EscapeInstReload, OptExitBB);
 564     MergePHI->addIncoming(EscapeInst, ExitBB);
 565
 566     // The information of scalar evolution about the escaping instruction needs
 567     // to be revoked so the new merged instruction will be used.
 568     if (SE.isSCEVable(EscapeInst->getType()))
 569       SE.forgetValue(EscapeInst);
 570
 571     // Replace all uses of the demoted instruction with the merge PHI.
 572     for (Instruction *EUser : EscapeUsers)
 573       EUser->replaceUsesOfWith(EscapeInst, MergePHI);
 574   }
 575 }
 576
 577 void BlockGenerator::findOutsideUsers(Scop &S) {
 578   for (auto &Array : S.arrays()) {
 579
 580     if (Array->getNumberOfDimensions() != 0)
 581       continue;
 582
 583     if (Array->isPHIKind())
 584       continue;
 585
 586     auto *Inst = dyn_cast<Instruction>(Array->getBasePtr());
 587
 588     if (!Inst)
 589       continue;
 590
 591     // Scop invariant hoisting moves some of the base pointers out of the scop.
 592     // We can ignore these, as the invariant load hoisting already registers the
 593     // relevant outside users.
 594     if (!S.contains(Inst))
 595       continue;
 596
 597     handleOutsideUsers(S, Inst);
 598   }
 599 }
 600
 601 void BlockGenerator::createExitPHINodeMerges(Scop &S) {
 602   if (S.hasSingleExitEdge())
 603     return;
 604
 605   auto *ExitBB = S.getExitingBlock();
 606   auto *MergeBB = S.getExit();
 607   auto *AfterMergeBB = MergeBB->getSingleSuccessor();
 608   BasicBlock *OptExitBB = *(pred_begin(MergeBB));
 609   if (OptExitBB == ExitBB)
 610     OptExitBB = *(++pred_begin(MergeBB));
 611
 612   Builder.SetInsertPoint(OptExitBB->getTerminator());
 613
 614   for (auto &SAI : S.arrays()) {
 615     auto *Val = SAI->getBasePtr();
 616
 617     // Only Value-like scalars need a merge PHI. Exit block PHIs receive either
 618     // the original PHI's value or the reloaded incoming values from the
 619     // generated code. An llvm::Value is merged between the original code's
 620     // value or the generated one.
 621     if (!SAI->isValueKind() && !SAI->isExitPHIKind())
 622       continue;
 623
 624     PHINode *PHI = dyn_cast<PHINode>(Val);
 625     if (!PHI)
 626       continue;
 627
 628     if (PHI->getParent() != AfterMergeBB)
 629       continue;
 630
 631     std::string Name = PHI->getName();
 632     Value *ScalarAddr = getOrCreateScalarAlloca(PHI);
 633     Value *Reload = Builder.CreateLoad(ScalarAddr, Name + ".ph.final_reload");
 634     Reload = Builder.CreateBitOrPointerCast(Reload, PHI->getType());
 635     Value *OriginalValue = PHI->getIncomingValueForBlock(MergeBB);
 636     assert((!isa<Instruction>(OriginalValue) ||
 637             cast<Instruction>(OriginalValue)->getParent() != MergeBB) &&
 638            "Original value must no be one we just generated.");
 639     auto *MergePHI = PHINode::Create(PHI->getType(), 2, Name + ".ph.merge");
 640     MergePHI->insertBefore(&*MergeBB->getFirstInsertionPt());
 641     MergePHI->addIncoming(Reload, OptExitBB);
 642     MergePHI->addIncoming(OriginalValue, ExitBB);
 643     int Idx = PHI->getBasicBlockIndex(MergeBB);
 644     PHI->setIncomingValue(Idx, MergePHI);
 645   }
 646 }
 647
 648 void BlockGenerator::finalizeSCoP(Scop &S) {
 649   findOutsideUsers(S);
 650   createScalarInitialization(S);
 651   createExitPHINodeMerges(S);
 652   createScalarFinalization(S);
 653 }
 654
 655 VectorBlockGenerator::VectorBlockGenerator(BlockGenerator &BlockGen,
 656                                            std::vector<LoopToScevMapT> &VLTS,
 657                                            isl_map *Schedule)
 658     : BlockGenerator(BlockGen), VLTS(VLTS), Schedule(Schedule) {
 659   assert(Schedule && "No statement domain provided");
 660 }
 661
 662 Value *VectorBlockGenerator::getVectorValue(ScopStmt &Stmt, Value *Old,
 663                                             ValueMapT &VectorMap,
 664                                             VectorValueMapT &ScalarMaps,
 665                                             Loop *L) {
 666   if (Value *NewValue = VectorMap.lookup(Old))
 667     return NewValue;
 668
 669   int Width = getVectorWidth();
 670
 671   Value *Vector = UndefValue::get(VectorType::get(Old->getType(), Width));
 672
 673   for (int Lane = 0; Lane < Width; Lane++)
 674     Vector = Builder.CreateInsertElement(
 675         Vector, getNewValue(Stmt, Old, ScalarMaps[Lane], VLTS[Lane], L),
 676         Builder.getInt32(Lane));
 677
 678   VectorMap[Old] = Vector;
 679
 680   return Vector;
 681 }
 682
 683 Type *VectorBlockGenerator::getVectorPtrTy(const Value *Val, int Width) {
 684   PointerType *PointerTy = dyn_cast<PointerType>(Val->getType());
 685   assert(PointerTy && "PointerType expected");
 686
 687   Type *ScalarType = PointerTy->getElementType();
 688   VectorType *VectorType = VectorType::get(ScalarType, Width);
 689
 690   return PointerType::getUnqual(VectorType);
 691 }
 692
 693 Value *VectorBlockGenerator::generateStrideOneLoad(
 694     ScopStmt &Stmt, LoadInst *Load, VectorValueMapT &ScalarMaps,
 695     __isl_keep isl_id_to_ast_expr *NewAccesses, bool NegativeStride = false) {
 696   unsigned VectorWidth = getVectorWidth();
 697   auto *Pointer = Load->getPointerOperand();
 698   Type *VectorPtrType = getVectorPtrTy(Pointer, VectorWidth);
 699   unsigned Offset = NegativeStride ? VectorWidth - 1 : 0;
 700
 701   Value *NewPointer = generateLocationAccessed(Stmt, Load, ScalarMaps[Offset],
 702                                                VLTS[Offset], NewAccesses);
 703   Value *VectorPtr =
 704       Builder.CreateBitCast(NewPointer, VectorPtrType, "vector_ptr");
 705   LoadInst *VecLoad =
 706       Builder.CreateLoad(VectorPtr, Load->getName() + "_p_vec_full");
 707   if (!Aligned)
 708     VecLoad->setAlignment(8);
 709
 710   if (NegativeStride) {
 711     SmallVector<Constant *, 16> Indices;
 712     for (int i = VectorWidth - 1; i >= 0; i--)
 713       Indices.push_back(ConstantInt::get(Builder.getInt32Ty(), i));
 714     Constant *SV = llvm::ConstantVector::get(Indices);
 715     Value *RevVecLoad = Builder.CreateShuffleVector(
 716         VecLoad, VecLoad, SV, Load->getName() + "_reverse");
 717     return RevVecLoad;
 718   }
 719
 720   return VecLoad;
 721 }
 722
 723 Value *VectorBlockGenerator::generateStrideZeroLoad(
 724     ScopStmt &Stmt, LoadInst *Load, ValueMapT &BBMap,
 725     __isl_keep isl_id_to_ast_expr *NewAccesses) {
 726   auto *Pointer = Load->getPointerOperand();
 727   Type *VectorPtrType = getVectorPtrTy(Pointer, 1);
 728   Value *NewPointer =
 729       generateLocationAccessed(Stmt, Load, BBMap, VLTS[0], NewAccesses);
 730   Value *VectorPtr = Builder.CreateBitCast(NewPointer, VectorPtrType,
 731                                            Load->getName() + "_p_vec_p");
 732   LoadInst *ScalarLoad =
 733       Builder.CreateLoad(VectorPtr, Load->getName() + "_p_splat_one");
 734
 735   if (!Aligned)
 736     ScalarLoad->setAlignment(8);
 737
 738   Constant *SplatVector = Constant::getNullValue(
 739       VectorType::get(Builder.getInt32Ty(), getVectorWidth()));
 740
 741   Value *VectorLoad = Builder.CreateShuffleVector(
 742       ScalarLoad, ScalarLoad, SplatVector, Load->getName() + "_p_splat");
 743   return VectorLoad;
 744 }
 745
 746 Value *VectorBlockGenerator::generateUnknownStrideLoad(
 747     ScopStmt &Stmt, LoadInst *Load, VectorValueMapT &ScalarMaps,
 748     __isl_keep isl_id_to_ast_expr *NewAccesses) {
 749   int VectorWidth = getVectorWidth();
 750   auto *Pointer = Load->getPointerOperand();
 751   VectorType *VectorType = VectorType::get(
 752       dyn_cast<PointerType>(Pointer->getType())->getElementType(), VectorWidth);
 753
 754   Value *Vector = UndefValue::get(VectorType);
 755
 756   for (int i = 0; i < VectorWidth; i++) {
 757     Value *NewPointer = generateLocationAccessed(Stmt, Load, ScalarMaps[i],
 758                                                  VLTS[i], NewAccesses);
 759     Value *ScalarLoad =
 760         Builder.CreateLoad(NewPointer, Load->getName() + "_p_scalar_");
 761     Vector = Builder.CreateInsertElement(
 762         Vector, ScalarLoad, Builder.getInt32(i), Load->getName() + "_p_vec_");
 763   }
 764
 765   return Vector;
 766 }
 767
 768 void VectorBlockGenerator::generateLoad(
 769     ScopStmt &Stmt, LoadInst *Load, ValueMapT &VectorMap,
 770     VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
 771   if (Value *PreloadLoad = GlobalMap.lookup(Load)) {
 772     VectorMap[Load] = Builder.CreateVectorSplat(getVectorWidth(), PreloadLoad,
 773                                                 Load->getName() + "_p");
 774     return;
 775   }
 776
 777   if (!VectorType::isValidElementType(Load->getType())) {
 778     for (int i = 0; i < getVectorWidth(); i++)
 779       ScalarMaps[i][Load] =
 780           generateScalarLoad(Stmt, Load, ScalarMaps[i], VLTS[i], NewAccesses);
 781     return;
 782   }
 783
 784   const MemoryAccess &Access = Stmt.getArrayAccessFor(Load);
 785
 786   // Make sure we have scalar values available to access the pointer to
 787   // the data location.
 788   extractScalarValues(Load, VectorMap, ScalarMaps);
 789
 790   Value *NewLoad;
 791   if (Access.isStrideZero(isl_map_copy(Schedule)))
 792     NewLoad = generateStrideZeroLoad(Stmt, Load, ScalarMaps[0], NewAccesses);
 793   else if (Access.isStrideOne(isl_map_copy(Schedule)))
 794     NewLoad = generateStrideOneLoad(Stmt, Load, ScalarMaps, NewAccesses);
 795   else if (Access.isStrideX(isl_map_copy(Schedule), -1))
 796     NewLoad = generateStrideOneLoad(Stmt, Load, ScalarMaps, NewAccesses, true);
 797   else
 798     NewLoad = generateUnknownStrideLoad(Stmt, Load, ScalarMaps, NewAccesses);
 799
 800   VectorMap[Load] = NewLoad;
 801 }
 802
 803 void VectorBlockGenerator::copyUnaryInst(ScopStmt &Stmt, UnaryInstruction *Inst,
 804                                          ValueMapT &VectorMap,
 805                                          VectorValueMapT &ScalarMaps) {
 806   int VectorWidth = getVectorWidth();
 807   Value *NewOperand = getVectorValue(Stmt, Inst->getOperand(0), VectorMap,
 808                                      ScalarMaps, getLoopForStmt(Stmt));
 809
 810   assert(isa<CastInst>(Inst) && "Can not generate vector code for instruction");
 811
 812   const CastInst *Cast = dyn_cast<CastInst>(Inst);
 813   VectorType *DestType = VectorType::get(Inst->getType(), VectorWidth);
 814   VectorMap[Inst] = Builder.CreateCast(Cast->getOpcode(), NewOperand, DestType);
 815 }
 816
 817 void VectorBlockGenerator::copyBinaryInst(ScopStmt &Stmt, BinaryOperator *Inst,
 818                                           ValueMapT &VectorMap,
 819                                           VectorValueMapT &ScalarMaps) {
 820   Loop *L = getLoopForStmt(Stmt);
 821   Value *OpZero = Inst->getOperand(0);
 822   Value *OpOne = Inst->getOperand(1);
 823
 824   Value *NewOpZero, *NewOpOne;
 825   NewOpZero = getVectorValue(Stmt, OpZero, VectorMap, ScalarMaps, L);
 826   NewOpOne = getVectorValue(Stmt, OpOne, VectorMap, ScalarMaps, L);
 827
 828   Value *NewInst = Builder.CreateBinOp(Inst->getOpcode(), NewOpZero, NewOpOne,
 829                                        Inst->getName() + "p_vec");
 830   VectorMap[Inst] = NewInst;
 831 }
 832
 833 void VectorBlockGenerator::copyStore(
 834     ScopStmt &Stmt, StoreInst *Store, ValueMapT &VectorMap,
 835     VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
 836   const MemoryAccess &Access = Stmt.getArrayAccessFor(Store);
 837
 838   auto *Pointer = Store->getPointerOperand();
 839   Value *Vector = getVectorValue(Stmt, Store->getValueOperand(), VectorMap,
 840                                  ScalarMaps, getLoopForStmt(Stmt));
 841
 842   // Make sure we have scalar values available to access the pointer to
 843   // the data location.
 844   extractScalarValues(Store, VectorMap, ScalarMaps);
 845
 846   if (Access.isStrideOne(isl_map_copy(Schedule))) {
 847     Type *VectorPtrType = getVectorPtrTy(Pointer, getVectorWidth());
 848     Value *NewPointer = generateLocationAccessed(Stmt, Store, ScalarMaps[0],
 849                                                  VLTS[0], NewAccesses);
 850
 851     Value *VectorPtr =
 852         Builder.CreateBitCast(NewPointer, VectorPtrType, "vector_ptr");
 853     StoreInst *Store = Builder.CreateStore(Vector, VectorPtr);
 854
 855     if (!Aligned)
 856       Store->setAlignment(8);
 857   } else {
 858     for (unsigned i = 0; i < ScalarMaps.size(); i++) {
 859       Value *Scalar = Builder.CreateExtractElement(Vector, Builder.getInt32(i));
 860       Value *NewPointer = generateLocationAccessed(Stmt, Store, ScalarMaps[i],
 861                                                    VLTS[i], NewAccesses);
 862       Builder.CreateStore(Scalar, NewPointer);
 863     }
 864   }
 865 }
 866
 867 bool VectorBlockGenerator::hasVectorOperands(const Instruction *Inst,
 868                                              ValueMapT &VectorMap) {
 869   for (Value *Operand : Inst->operands())
 870     if (VectorMap.count(Operand))
 871       return true;
 872   return false;
 873 }
 874
 875 bool VectorBlockGenerator::extractScalarValues(const Instruction *Inst,
 876                                                ValueMapT &VectorMap,
 877                                                VectorValueMapT &ScalarMaps) {
 878   bool HasVectorOperand = false;
 879   int VectorWidth = getVectorWidth();
 880
 881   for (Value *Operand : Inst->operands()) {
 882     ValueMapT::iterator VecOp = VectorMap.find(Operand);
 883
 884     if (VecOp == VectorMap.end())
 885       continue;
 886
 887     HasVectorOperand = true;
 888     Value *NewVector = VecOp->second;
 889
 890     for (int i = 0; i < VectorWidth; ++i) {
 891       ValueMapT &SM = ScalarMaps[i];
 892
 893       // If there is one scalar extracted, all scalar elements should have
 894       // already been extracted by the code here. So no need to check for the
 895       // existence of all of them.
 896       if (SM.count(Operand))
 897         break;
 898
 899       SM[Operand] =
 900           Builder.CreateExtractElement(NewVector, Builder.getInt32(i));
 901     }
 902   }
 903
 904   return HasVectorOperand;
 905 }
 906
 907 void VectorBlockGenerator::copyInstScalarized(
 908     ScopStmt &Stmt, Instruction *Inst, ValueMapT &VectorMap,
 909     VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
 910   bool HasVectorOperand;
 911   int VectorWidth = getVectorWidth();
 912
 913   HasVectorOperand = extractScalarValues(Inst, VectorMap, ScalarMaps);
 914
 915   for (int VectorLane = 0; VectorLane < getVectorWidth(); VectorLane++)
 916     BlockGenerator::copyInstruction(Stmt, Inst, ScalarMaps[VectorLane],
 917                                     VLTS[VectorLane], NewAccesses);
 918
 919   if (!VectorType::isValidElementType(Inst->getType()) || !HasVectorOperand)
 920     return;
 921
 922   // Make the result available as vector value.
 923   VectorType *VectorType = VectorType::get(Inst->getType(), VectorWidth);
 924   Value *Vector = UndefValue::get(VectorType);
 925
 926   for (int i = 0; i < VectorWidth; i++)
 927     Vector = Builder.CreateInsertElement(Vector, ScalarMaps[i][Inst],
 928                                          Builder.getInt32(i));
 929
 930   VectorMap[Inst] = Vector;
 931 }
 932
 933 int VectorBlockGenerator::getVectorWidth() { return VLTS.size(); }
 934
 935 void VectorBlockGenerator::copyInstruction(
 936     ScopStmt &Stmt, Instruction *Inst, ValueMapT &VectorMap,
 937     VectorValueMapT &ScalarMaps, __isl_keep isl_id_to_ast_expr *NewAccesses) {
 938   // Terminator instructions control the control flow. They are explicitly
 939   // expressed in the clast and do not need to be copied.
 940   if (Inst->isTerminator())
 941     return;
 942
 943   if (canSyntheziseInStmt(Stmt, Inst))
 944     return;
 945
 946   if (auto *Load = dyn_cast<LoadInst>(Inst)) {
 947     generateLoad(Stmt, Load, VectorMap, ScalarMaps, NewAccesses);
 948     return;
 949   }
 950
 951   if (hasVectorOperands(Inst, VectorMap)) {
 952     if (auto *Store = dyn_cast<StoreInst>(Inst)) {
 953       copyStore(Stmt, Store, VectorMap, ScalarMaps, NewAccesses);
 954       return;
 955     }
 956
 957     if (auto *Unary = dyn_cast<UnaryInstruction>(Inst)) {
 958       copyUnaryInst(Stmt, Unary, VectorMap, ScalarMaps);
 959       return;
 960     }
 961
 962     if (auto *Binary = dyn_cast<BinaryOperator>(Inst)) {
 963       copyBinaryInst(Stmt, Binary, VectorMap, ScalarMaps);
 964       return;
 965     }
 966
 967     // Falltrough: We generate scalar instructions, if we don't know how to
 968     // generate vector code.
 969   }
 970
 971   copyInstScalarized(Stmt, Inst, VectorMap, ScalarMaps, NewAccesses);
 972 }
 973
 974 void VectorBlockGenerator::generateScalarVectorLoads(
 975     ScopStmt &Stmt, ValueMapT &VectorBlockMap) {
 976   for (MemoryAccess *MA : Stmt) {
 977     if (MA->isArrayKind() || MA->isWrite())
 978       continue;
 979
 980     auto *Address = getOrCreateAlloca(*MA);
 981     Type *VectorPtrType = getVectorPtrTy(Address, 1);
 982     Value *VectorPtr = Builder.CreateBitCast(Address, VectorPtrType,
 983                                              Address->getName() + "_p_vec_p");
 984     auto *Val = Builder.CreateLoad(VectorPtr, Address->getName() + ".reload");
 985     Constant *SplatVector = Constant::getNullValue(
 986         VectorType::get(Builder.getInt32Ty(), getVectorWidth()));
 987
 988     Value *VectorVal = Builder.CreateShuffleVector(
 989         Val, Val, SplatVector, Address->getName() + "_p_splat");
 990     VectorBlockMap[MA->getBaseAddr()] = VectorVal;
 991   }
 992 }
 993
 994 void VectorBlockGenerator::verifyNoScalarStores(ScopStmt &Stmt) {
 995   for (MemoryAccess *MA : Stmt) {
 996     if (MA->isArrayKind() || MA->isRead())
 997       continue;
 998
 999     llvm_unreachable("Scalar stores not expected in vector loop");
1000   }
1001 }
1002
1003 void VectorBlockGenerator::copyStmt(
1004     ScopStmt &Stmt, __isl_keep isl_id_to_ast_expr *NewAccesses) {
1005   assert(Stmt.isBlockStmt() && "TODO: Only block statements can be copied by "
1006                                "the vector block generator");
1007
1008   BasicBlock *BB = Stmt.getBasicBlock();
1009   BasicBlock *CopyBB = SplitBlock(Builder.GetInsertBlock(),
1010                                   &*Builder.GetInsertPoint(), &DT, &LI);
1011   CopyBB->setName("polly.stmt." + BB->getName());
1012   Builder.SetInsertPoint(&CopyBB->front());
1013
1014   // Create two maps that store the mapping from the original instructions of
1015   // the old basic block to their copies in the new basic block. Those maps
1016   // are basic block local.
1017   //
1018   // As vector code generation is supported there is one map for scalar values
1019   // and one for vector values.
1020   //
1021   // In case we just do scalar code generation, the vectorMap is not used and
1022   // the scalarMap has just one dimension, which contains the mapping.
1023   //
1024   // In case vector code generation is done, an instruction may either appear
1025   // in the vector map once (as it is calculating >vectorwidth< values at a
1026   // time. Or (if the values are calculated using scalar operations), it
1027   // appears once in every dimension of the scalarMap.
1028   VectorValueMapT ScalarBlockMap(getVectorWidth());
1029   ValueMapT VectorBlockMap;
1030
1031   generateScalarVectorLoads(Stmt, VectorBlockMap);
1032
1033   for (Instruction &Inst : *BB)
1034     copyInstruction(Stmt, &Inst, VectorBlockMap, ScalarBlockMap, NewAccesses);
1035
1036   verifyNoScalarStores(Stmt);
1037 }
1038
1039 BasicBlock *RegionGenerator::repairDominance(BasicBlock *BB,
1040                                              BasicBlock *BBCopy) {
1041
1042   BasicBlock *BBIDom = DT.getNode(BB)->getIDom()->getBlock();
1043   BasicBlock *BBCopyIDom = BlockMap.lookup(BBIDom);
1044
1045   if (BBCopyIDom)
1046     DT.changeImmediateDominator(BBCopy, BBCopyIDom);
1047
1048   return BBCopyIDom;
1049 }
1050
1051 // This is to determine whether an llvm::Value (defined in @p BB) is usable when
1052 // leaving a subregion. The straight-forward DT.dominates(BB, R->getExitBlock())
1053 // does not work in cases where the exit block has edges from outside the
1054 // region. In that case the llvm::Value would never be usable in in the exit
1055 // block. The RegionGenerator however creates an new exit block ('ExitBBCopy')
1056 // for the subregion's exiting edges only. We need to determine whether an
1057 // llvm::Value is usable in there. We do this by checking whether it dominates
1058 // all exiting blocks individually.
1059 static bool isDominatingSubregionExit(const DominatorTree &DT, Region *R,
1060                                       BasicBlock *BB) {
1061   for (auto ExitingBB : predecessors(R->getExit())) {
1062     // Check for non-subregion incoming edges.
1063     if (!R->contains(ExitingBB))
1064       continue;
1065
1066     if (!DT.dominates(BB, ExitingBB))
1067       return false;
1068   }
1069
1070   return true;
1071 }
1072
1073 // Find the direct dominator of the subregion's exit block if the subregion was
1074 // simplified.
1075 static BasicBlock *findExitDominator(DominatorTree &DT, Region *R) {
1076   BasicBlock *Common = nullptr;
1077   for (auto ExitingBB : predecessors(R->getExit())) {
1078     // Check for non-subregion incoming edges.
1079     if (!R->contains(ExitingBB))
1080       continue;
1081
1082     // First exiting edge.
1083     if (!Common) {
1084       Common = ExitingBB;
1085       continue;
1086     }
1087
1088     Common = DT.findNearestCommonDominator(Common, ExitingBB);
1089   }
1090
1091   assert(Common && R->contains(Common));
1092   return Common;
1093 }
1094
1095 void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
1096                                isl_id_to_ast_expr *IdToAstExp) {
1097   assert(Stmt.isRegionStmt() &&
1098          "Only region statements can be copied by the region generator");
1099
1100   // Forget all old mappings.
1101   BlockMap.clear();
1102   RegionMaps.clear();
1103   IncompletePHINodeMap.clear();
1104
1105   // Collection of all values related to this subregion.
1106   ValueMapT ValueMap;
1107
1108   // The region represented by the statement.
1109   Region *R = Stmt.getRegion();
1110
1111   // Create a dedicated entry for the region where we can reload all demoted
1112   // inputs.
1113   BasicBlock *EntryBB = R->getEntry();
1114   BasicBlock *EntryBBCopy = SplitBlock(Builder.GetInsertBlock(),
1115                                        &*Builder.GetInsertPoint(), &DT, &LI);
1116   EntryBBCopy->setName("polly.stmt." + EntryBB->getName() + ".entry");
1117   Builder.SetInsertPoint(&EntryBBCopy->front());
1118
1119   ValueMapT &EntryBBMap = RegionMaps[EntryBBCopy];
1120   generateScalarLoads(Stmt, EntryBBMap);
1121
1122   for (auto PI = pred_begin(EntryBB), PE = pred_end(EntryBB); PI != PE; ++PI)
1123     if (!R->contains(*PI))
1124       BlockMap[*PI] = EntryBBCopy;
1125
1126   // Iterate over all blocks in the region in a breadth-first search.
1127   std::deque<BasicBlock *> Blocks;
1128   SmallPtrSet<BasicBlock *, 8> SeenBlocks;
1129   Blocks.push_back(EntryBB);
1130   SeenBlocks.insert(EntryBB);
1131
1132   while (!Blocks.empty()) {
1133     BasicBlock *BB = Blocks.front();
1134     Blocks.pop_front();
1135
1136     // First split the block and update dominance information.
1137     BasicBlock *BBCopy = splitBB(BB);
1138     BasicBlock *BBCopyIDom = repairDominance(BB, BBCopy);
1139
1140     // Get the mapping for this block and initialize it with either the scalar
1141     // loads from the generated entering block (which dominates all blocks of
1142     // this subregion) or the maps of the immediate dominator, if part of the
1143     // subregion. The latter necessarily includes the former.
1144     ValueMapT *InitBBMap;
1145     if (BBCopyIDom) {
1146       assert(RegionMaps.count(BBCopyIDom));
1147       InitBBMap = &RegionMaps[BBCopyIDom];
1148     } else
1149       InitBBMap = &EntryBBMap;
1150     auto Inserted = RegionMaps.insert(std::make_pair(BBCopy, *InitBBMap));
1151     ValueMapT &RegionMap = Inserted.first->second;
1152
1153     // Copy the block with the BlockGenerator.
1154     Builder.SetInsertPoint(&BBCopy->front());
1155     copyBB(Stmt, BB, BBCopy, RegionMap, LTS, IdToAstExp);
1156
1157     // In order to remap PHI nodes we store also basic block mappings.
1158     BlockMap[BB] = BBCopy;
1159
1160     // Add values to incomplete PHI nodes waiting for this block to be copied.
1161     for (const PHINodePairTy &PHINodePair : IncompletePHINodeMap[BB])
1162       addOperandToPHI(Stmt, PHINodePair.first, PHINodePair.second, BB, LTS);
1163     IncompletePHINodeMap[BB].clear();
1164
1165     // And continue with new successors inside the region.
1166     for (auto SI = succ_begin(BB), SE = succ_end(BB); SI != SE; SI++)
1167       if (R->contains(*SI) && SeenBlocks.insert(*SI).second)
1168         Blocks.push_back(*SI);
1169
1170     // Remember value in case it is visible after this subregion.
1171     if (isDominatingSubregionExit(DT, R, BB))
1172       ValueMap.insert(RegionMap.begin(), RegionMap.end());
1173   }
1174
1175   // Now create a new dedicated region exit block and add it to the region map.
1176   BasicBlock *ExitBBCopy = SplitBlock(Builder.GetInsertBlock(),
1177                                       &*Builder.GetInsertPoint(), &DT, &LI);
1178   ExitBBCopy->setName("polly.stmt." + R->getExit()->getName() + ".exit");
1179   BlockMap[R->getExit()] = ExitBBCopy;
1180
1181   BasicBlock *ExitDomBBCopy = BlockMap.lookup(findExitDominator(DT, R));
1182   assert(ExitDomBBCopy && "Common exit dominator must be within region; at "
1183                           "least the entry node must match");
1184   DT.changeImmediateDominator(ExitBBCopy, ExitDomBBCopy);
1185
1186   // As the block generator doesn't handle control flow we need to add the
1187   // region control flow by hand after all blocks have been copied.
1188   for (BasicBlock *BB : SeenBlocks) {
1189
1190     BasicBlock *BBCopy = BlockMap[BB];
1191     TerminatorInst *TI = BB->getTerminator();
1192     if (isa<UnreachableInst>(TI)) {
1193       while (!BBCopy->empty())
1194         BBCopy->begin()->eraseFromParent();
1195       new UnreachableInst(BBCopy->getContext(), BBCopy);
1196       continue;
1197     }
1198
1199     Instruction *BICopy = BBCopy->getTerminator();
1200
1201     ValueMapT &RegionMap = RegionMaps[BBCopy];
1202     RegionMap.insert(BlockMap.begin(), BlockMap.end());
1203
1204     Builder.SetInsertPoint(BICopy);
1205     copyInstScalar(Stmt, TI, RegionMap, LTS);
1206     BICopy->eraseFromParent();
1207   }
1208
1209   // Add counting PHI nodes to all loops in the region that can be used as
1210   // replacement for SCEVs refering to the old loop.
1211   for (BasicBlock *BB : SeenBlocks) {
1212     Loop *L = LI.getLoopFor(BB);
1213     if (L == nullptr || L->getHeader() != BB || !R->contains(L))
1214       continue;
1215
1216     BasicBlock *BBCopy = BlockMap[BB];
1217     Value *NullVal = Builder.getInt32(0);
1218     PHINode *LoopPHI =
1219         PHINode::Create(Builder.getInt32Ty(), 2, "polly.subregion.iv");
1220     Instruction *LoopPHIInc = BinaryOperator::CreateAdd(
1221         LoopPHI, Builder.getInt32(1), "polly.subregion.iv.inc");
1222     LoopPHI->insertBefore(&BBCopy->front());
1223     LoopPHIInc->insertBefore(BBCopy->getTerminator());
1224
1225     for (auto *PredBB : make_range(pred_begin(BB), pred_end(BB))) {
1226       if (!R->contains(PredBB))
1227         continue;
1228       if (L->contains(PredBB))
1229         LoopPHI->addIncoming(LoopPHIInc, BlockMap[PredBB]);
1230       else
1231         LoopPHI->addIncoming(NullVal, BlockMap[PredBB]);
1232     }
1233
1234     for (auto *PredBBCopy : make_range(pred_begin(BBCopy), pred_end(BBCopy)))
1235       if (LoopPHI->getBasicBlockIndex(PredBBCopy) < 0)
1236         LoopPHI->addIncoming(NullVal, PredBBCopy);
1237
1238     LTS[L] = SE.getUnknown(LoopPHI);
1239   }
1240
1241   // Continue generating code in the exit block.
1242   Builder.SetInsertPoint(&*ExitBBCopy->getFirstInsertionPt());
1243
1244   // Write values visible to other statements.
1245   generateScalarStores(Stmt, LTS, ValueMap);
1246   BlockMap.clear();
1247   RegionMaps.clear();
1248   IncompletePHINodeMap.clear();
1249 }
1250
1251 PHINode *RegionGenerator::buildExitPHI(MemoryAccess *MA, LoopToScevMapT &LTS,
1252                                        ValueMapT &BBMap, Loop *L) {
1253   ScopStmt *Stmt = MA->getStatement();
1254   Region *SubR = Stmt->getRegion();
1255   auto Incoming = MA->getIncoming();
1256
1257   PollyIRBuilder::InsertPointGuard IPGuard(Builder);
1258   PHINode *OrigPHI = cast<PHINode>(MA->getAccessInstruction());
1259   BasicBlock *NewSubregionExit = Builder.GetInsertBlock();
1260
1261   // This can happen if the subregion is simplified after the ScopStmts
1262   // have been created; simplification happens as part of CodeGeneration.
1263   if (OrigPHI->getParent() != SubR->getExit()) {
1264     BasicBlock *FormerExit = SubR->getExitingBlock();
1265     if (FormerExit)
1266       NewSubregionExit = BlockMap.lookup(FormerExit);
1267   }
1268
1269   PHINode *NewPHI = PHINode::Create(OrigPHI->getType(), Incoming.size(),
1270                                     "polly." + OrigPHI->getName(),
1271                                     NewSubregionExit->getFirstNonPHI());
1272
1273   // Add the incoming values to the PHI.
1274   for (auto &Pair : Incoming) {
1275     BasicBlock *OrigIncomingBlock = Pair.first;
1276     BasicBlock *NewIncomingBlock = BlockMap.lookup(OrigIncomingBlock);
1277     Builder.SetInsertPoint(NewIncomingBlock->getTerminator());
1278     assert(RegionMaps.count(NewIncomingBlock));
1279     ValueMapT *LocalBBMap = &RegionMaps[NewIncomingBlock];
1280
1281     Value *OrigIncomingValue = Pair.second;
1282     Value *NewIncomingValue =
1283         getNewValue(*Stmt, OrigIncomingValue, *LocalBBMap, LTS, L);
1284     NewPHI->addIncoming(NewIncomingValue, NewIncomingBlock);
1285   }
1286
1287   return NewPHI;
1288 }
1289
1290 Value *RegionGenerator::getExitScalar(MemoryAccess *MA, LoopToScevMapT &LTS,
1291                                       ValueMapT &BBMap) {
1292   ScopStmt *Stmt = MA->getStatement();
1293
1294   // TODO: Add some test cases that ensure this is really the right choice.
1295   Loop *L = LI.getLoopFor(Stmt->getRegion()->getExit());
1296
1297   if (MA->isAnyPHIKind()) {
1298     auto Incoming = MA->getIncoming();
1299     assert(!Incoming.empty() &&
1300            "PHI WRITEs must have originate from at least one incoming block");
1301
1302     // If there is only one incoming value, we do not need to create a PHI.
1303     if (Incoming.size() == 1) {
1304       Value *OldVal = Incoming[0].second;
1305       return getNewValue(*Stmt, OldVal, BBMap, LTS, L);
1306     }
1307
1308     return buildExitPHI(MA, LTS, BBMap, L);
1309   }
1310
1311   // MK_Value accesses leaving the subregion must dominate the exit block; just
1312   // pass the copied value
1313   Value *OldVal = MA->getAccessValue();
1314   return getNewValue(*Stmt, OldVal, BBMap, LTS, L);
1315 }
1316
1317 void RegionGenerator::generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
1318                                            ValueMapT &BBMap) {
1319   assert(Stmt.getRegion() &&
1320          "Block statements need to use the generateScalarStores() "
1321          "function in the BlockGenerator");
1322
1323   for (MemoryAccess *MA : Stmt) {
1324     if (MA->isArrayKind() || MA->isRead())
1325       continue;
1326
1327     Value *NewVal = getExitScalar(MA, LTS, BBMap);
1328     Value *Address = getOrCreateAlloca(*MA);
1329     assert((!isa<Instruction>(NewVal) ||
1330             DT.dominates(cast<Instruction>(NewVal)->getParent(),
1331                          Builder.GetInsertBlock())) &&
1332            "Domination violation");
1333     assert((!isa<Instruction>(Address) ||
1334             DT.dominates(cast<Instruction>(Address)->getParent(),
1335                          Builder.GetInsertBlock())) &&
1336            "Domination violation");
1337     Builder.CreateStore(NewVal, Address);
1338   }
1339 }
1340
1341 void RegionGenerator::addOperandToPHI(ScopStmt &Stmt, const PHINode *PHI,
1342                                       PHINode *PHICopy, BasicBlock *IncomingBB,
1343                                       LoopToScevMapT &LTS) {
1344   Region *StmtR = Stmt.getRegion();
1345
1346   // If the incoming block was not yet copied mark this PHI as incomplete.
1347   // Once the block will be copied the incoming value will be added.
1348   BasicBlock *BBCopy = BlockMap[IncomingBB];
1349   if (!BBCopy) {
1350     assert(StmtR->contains(IncomingBB) &&
1351            "Bad incoming block for PHI in non-affine region");
1352     IncompletePHINodeMap[IncomingBB].push_back(std::make_pair(PHI, PHICopy));
1353     return;
1354   }
1355
1356   Value *OpCopy = nullptr;
1357   if (StmtR->contains(IncomingBB)) {
1358     assert(RegionMaps.count(BBCopy) &&
1359            "Incoming PHI block did not have a BBMap");
1360     ValueMapT &BBCopyMap = RegionMaps[BBCopy];
1361
1362     Value *Op = PHI->getIncomingValueForBlock(IncomingBB);
1363
1364     // If the current insert block is different from the PHIs incoming block
1365     // change it, otherwise do not.
1366     auto IP = Builder.GetInsertPoint();
1367     if (IP->getParent() != BBCopy)
1368       Builder.SetInsertPoint(BBCopy->getTerminator());
1369     OpCopy = getNewValue(Stmt, Op, BBCopyMap, LTS, getLoopForStmt(Stmt));
1370     if (IP->getParent() != BBCopy)
1371       Builder.SetInsertPoint(&*IP);
1372   } else {
1373
1374     if (PHICopy->getBasicBlockIndex(BBCopy) >= 0)
1375       return;
1376
1377     Value *PHIOpAddr = getOrCreatePHIAlloca(const_cast<PHINode *>(PHI));
1378     OpCopy = new LoadInst(PHIOpAddr, PHIOpAddr->getName() + ".reload",
1379                           BlockMap[IncomingBB]->getTerminator());
1380   }
1381
1382   assert(OpCopy && "Incoming PHI value was not copied properly");
1383   assert(BBCopy && "Incoming PHI block was not copied properly");
1384   PHICopy->addIncoming(OpCopy, BBCopy);
1385 }
1386
1387 void RegionGenerator::copyPHIInstruction(ScopStmt &Stmt, PHINode *PHI,
1388                                          ValueMapT &BBMap,
1389                                          LoopToScevMapT &LTS) {
1390   unsigned NumIncoming = PHI->getNumIncomingValues();
1391   PHINode *PHICopy =
1392       Builder.CreatePHI(PHI->getType(), NumIncoming, "polly." + PHI->getName());
1393   PHICopy->moveBefore(PHICopy->getParent()->getFirstNonPHI());
1394   BBMap[PHI] = PHICopy;
1395
1396   for (unsigned u = 0; u < NumIncoming; u++)
1397     addOperandToPHI(Stmt, PHI, PHICopy, PHI->getIncomingBlock(u), LTS);
1398 }