1395 lines · cpp
1//===--- BlockGenerators.cpp - Generate code for statements -----*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the BlockGenerator and VectorBlockGenerator classes,10// which generate sequential code and vectorized code for a polyhedral11// statement, respectively.12//13//===----------------------------------------------------------------------===//14 15#include "polly/CodeGen/BlockGenerators.h"16#include "polly/CodeGen/IslExprBuilder.h"17#include "polly/CodeGen/RuntimeDebugBuilder.h"18#include "polly/Options.h"19#include "polly/ScopInfo.h"20#include "polly/Support/ISLTools.h"21#include "polly/Support/ScopHelper.h"22#include "polly/Support/VirtualInstruction.h"23#include "llvm/Analysis/DomTreeUpdater.h"24#include "llvm/Analysis/LoopInfo.h"25#include "llvm/Analysis/RegionInfo.h"26#include "llvm/Analysis/ScalarEvolution.h"27#include "llvm/Transforms/Utils/BasicBlockUtils.h"28#include "llvm/Transforms/Utils/Local.h"29#include "isl/ast.h"30#include <deque>31 32using namespace llvm;33using namespace polly;34 35static cl::opt<bool> Aligned("enable-polly-aligned",36 cl::desc("Assumed aligned memory accesses."),37 cl::Hidden, cl::cat(PollyCategory));38 39bool PollyDebugPrinting;40static cl::opt<bool, true> DebugPrintingX(41 "polly-codegen-add-debug-printing",42 cl::desc("Add printf calls that show the values loaded/stored."),43 cl::location(PollyDebugPrinting), cl::Hidden, cl::cat(PollyCategory));44 45static cl::opt<bool> TraceStmts(46 "polly-codegen-trace-stmts",47 cl::desc("Add printf calls that print the statement being executed"),48 cl::Hidden, cl::cat(PollyCategory));49 50static cl::opt<bool> TraceScalars(51 "polly-codegen-trace-scalars",52 cl::desc("Add printf calls that print the values of all scalar values "53 "used in a statement. Requires -polly-codegen-trace-stmts."),54 cl::Hidden, cl::cat(PollyCategory));55 56BlockGenerator::BlockGenerator(57 PollyIRBuilder &B, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT,58 AllocaMapTy &ScalarMap, EscapeUsersAllocaMapTy &EscapeMap,59 ValueMapT &GlobalMap, IslExprBuilder *ExprBuilder, BasicBlock *StartBlock)60 : Builder(B), LI(LI), SE(SE), ExprBuilder(ExprBuilder), DT(DT), GenDT(&DT),61 GenLI(&LI), GenSE(&SE), ScalarMap(ScalarMap), EscapeMap(EscapeMap),62 GlobalMap(GlobalMap), StartBlock(StartBlock) {}63 64Value *BlockGenerator::trySynthesizeNewValue(ScopStmt &Stmt, Value *Old,65 ValueMapT &BBMap,66 LoopToScevMapT <S,67 Loop *L) const {68 if (!SE.isSCEVable(Old->getType()))69 return nullptr;70 71 const SCEV *Scev = SE.getSCEVAtScope(Old, L);72 if (!Scev)73 return nullptr;74 75 if (isa<SCEVCouldNotCompute>(Scev))76 return nullptr;77 78 ValueMapT VTV;79 VTV.insert_range(BBMap);80 VTV.insert_range(GlobalMap);81 82 Scop &S = *Stmt.getParent();83 const DataLayout &DL = S.getFunction().getDataLayout();84 auto IP = Builder.GetInsertPoint();85 86 assert(IP != Builder.GetInsertBlock()->end() &&87 "Only instructions can be insert points for SCEVExpander");88 Value *Expanded = expandCodeFor(89 S, SE, Builder.GetInsertBlock()->getParent(), *GenSE, DL, "polly", Scev,90 Old->getType(), IP, &VTV, <S, StartBlock->getSinglePredecessor());91 92 BBMap[Old] = Expanded;93 return Expanded;94}95 96Value *BlockGenerator::getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap,97 LoopToScevMapT <S, Loop *L) const {98 99 auto lookupGlobally = [this](Value *Old) -> Value * {100 Value *New = GlobalMap.lookup(Old);101 if (!New)102 return nullptr;103 104 // Required by:105 // * Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded.ll106 // * Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded_different_bb.ll107 // * Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded_pass_only_needed.ll108 // * Isl/CodeGen/OpenMP/invariant_base_pointers_preloaded.ll109 // * Isl/CodeGen/OpenMP/loop-body-references-outer-values-3.ll110 // * Isl/CodeGen/OpenMP/single_loop_with_loop_invariant_baseptr.ll111 // GlobalMap should be a mapping from (value in original SCoP) to (copied112 // value in generated SCoP), without intermediate mappings, which might113 // easily require transitiveness as well.114 if (Value *NewRemapped = GlobalMap.lookup(New))115 New = NewRemapped;116 117 // No test case for this code.118 if (Old->getType()->getScalarSizeInBits() <119 New->getType()->getScalarSizeInBits())120 New = Builder.CreateTruncOrBitCast(New, Old->getType());121 122 return New;123 };124 125 Value *New = nullptr;126 auto VUse = VirtualUse::create(&Stmt, L, Old, true);127 switch (VUse.getKind()) {128 case VirtualUse::Block:129 // BasicBlock are constants, but the BlockGenerator copies them.130 New = BBMap.lookup(Old);131 break;132 133 case VirtualUse::Constant:134 // Used by:135 // * Isl/CodeGen/OpenMP/reference-argument-from-non-affine-region.ll136 // Constants should not be redefined. In this case, the GlobalMap just137 // contains a mapping to the same constant, which is unnecessary, but138 // harmless.139 if ((New = lookupGlobally(Old)))140 break;141 142 assert(!BBMap.count(Old));143 New = Old;144 break;145 146 case VirtualUse::ReadOnly:147 assert(!GlobalMap.count(Old));148 149 // Required for:150 // * Isl/CodeGen/MemAccess/create_arrays.ll151 // * Isl/CodeGen/read-only-scalars.ll152 // * ScheduleOptimizer/pattern-matching-based-opts_10.ll153 // For some reason these reload a read-only value. The reloaded value ends154 // up in BBMap, buts its value should be identical.155 //156 // Required for:157 // * Isl/CodeGen/OpenMP/single_loop_with_param.ll158 // The parallel subfunctions need to reference the read-only value from the159 // parent function, this is done by reloading them locally.160 if ((New = BBMap.lookup(Old)))161 break;162 163 New = Old;164 break;165 166 case VirtualUse::Synthesizable:167 // Used by:168 // * Isl/CodeGen/OpenMP/loop-body-references-outer-values-3.ll169 // * Isl/CodeGen/OpenMP/recomputed-srem.ll170 // * Isl/CodeGen/OpenMP/reference-other-bb.ll171 // * Isl/CodeGen/OpenMP/two-parallel-loops-reference-outer-indvar.ll172 // For some reason synthesizable values end up in GlobalMap. Their values173 // are the same as trySynthesizeNewValue would return. The legacy174 // implementation prioritized GlobalMap, so this is what we do here as well.175 // Ideally, synthesizable values should not end up in GlobalMap.176 if ((New = lookupGlobally(Old)))177 break;178 179 // Required for:180 // * Isl/CodeGen/RuntimeDebugBuilder/combine_different_values.ll181 // * Isl/CodeGen/getNumberOfIterations.ll182 // * Isl/CodeGen/non_affine_float_compare.ll183 // * ScheduleOptimizer/pattern-matching-based-opts_10.ll184 // Ideally, synthesizable values are synthesized by trySynthesizeNewValue,185 // not precomputed (SCEVExpander has its own caching mechanism).186 // These tests fail without this, but I think trySynthesizeNewValue would187 // just re-synthesize the same instructions.188 if ((New = BBMap.lookup(Old)))189 break;190 191 New = trySynthesizeNewValue(Stmt, Old, BBMap, LTS, L);192 break;193 194 case VirtualUse::Hoisted:195 // TODO: Hoisted invariant loads should be found in GlobalMap only, but not196 // redefined locally (which will be ignored anyway). That is, the following197 // assertion should apply: assert(!BBMap.count(Old))198 199 New = lookupGlobally(Old);200 break;201 202 case VirtualUse::Intra:203 case VirtualUse::Inter:204 assert(!GlobalMap.count(Old) &&205 "Intra and inter-stmt values are never global");206 New = BBMap.lookup(Old);207 break;208 }209 assert(New && "Unexpected scalar dependence in region!");210 return New;211}212 213void BlockGenerator::copyInstScalar(ScopStmt &Stmt, Instruction *Inst,214 ValueMapT &BBMap, LoopToScevMapT <S) {215 // We do not generate debug intrinsics as we did not investigate how to216 // copy them correctly. At the current state, they just crash the code217 // generation as the meta-data operands are not correctly copied.218 if (isa<DbgInfoIntrinsic>(Inst))219 return;220 221 Instruction *NewInst = Inst->clone();222 223 // Replace old operands with the new ones.224 for (Value *OldOperand : Inst->operands()) {225 Value *NewOperand =226 getNewValue(Stmt, OldOperand, BBMap, LTS, getLoopForStmt(Stmt));227 228 if (!NewOperand) {229 assert(!isa<StoreInst>(NewInst) &&230 "Store instructions are always needed!");231 NewInst->deleteValue();232 return;233 }234 235 // FIXME: We will encounter "NewOperand" again if used twice. getNewValue()236 // is meant to be called on old values only.237 NewInst->replaceUsesOfWith(OldOperand, NewOperand);238 }239 240 Builder.Insert(NewInst);241 BBMap[Inst] = NewInst;242 243 assert(NewInst->getModule() == Inst->getModule() &&244 "Expecting instructions to be in the same module");245 246 if (!NewInst->getType()->isVoidTy())247 NewInst->setName("p_" + Inst->getName());248}249 250Value *251BlockGenerator::generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst,252 ValueMapT &BBMap, LoopToScevMapT <S,253 isl_id_to_ast_expr *NewAccesses) {254 const MemoryAccess &MA = Stmt.getArrayAccessFor(Inst);255 return generateLocationAccessed(256 Stmt, getLoopForStmt(Stmt),257 Inst.isNull() ? nullptr : Inst.getPointerOperand(), BBMap, LTS,258 NewAccesses, MA.getId().release(), MA.getAccessValue()->getType());259}260 261Value *BlockGenerator::generateLocationAccessed(262 ScopStmt &Stmt, Loop *L, Value *Pointer, ValueMapT &BBMap,263 LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses, __isl_take isl_id *Id,264 Type *ExpectedType) {265 isl_ast_expr *AccessExpr = isl_id_to_ast_expr_get(NewAccesses, Id);266 267 if (AccessExpr) {268 AccessExpr = isl_ast_expr_address_of(AccessExpr);269 return ExprBuilder->create(AccessExpr);270 }271 assert(272 Pointer &&273 "If expression was not generated, must use the original pointer value");274 return getNewValue(Stmt, Pointer, BBMap, LTS, L);275}276 277Value *278BlockGenerator::getImplicitAddress(MemoryAccess &Access, Loop *L,279 LoopToScevMapT <S, ValueMapT &BBMap,280 __isl_keep isl_id_to_ast_expr *NewAccesses) {281 if (Access.isLatestArrayKind())282 return generateLocationAccessed(*Access.getStatement(), L, nullptr, BBMap,283 LTS, NewAccesses, Access.getId().release(),284 Access.getAccessValue()->getType());285 286 return getOrCreateAlloca(Access);287}288 289Loop *BlockGenerator::getLoopForStmt(const ScopStmt &Stmt) const {290 auto *StmtBB = Stmt.getEntryBlock();291 return LI.getLoopFor(StmtBB);292}293 294Value *BlockGenerator::generateArrayLoad(ScopStmt &Stmt, LoadInst *Load,295 ValueMapT &BBMap, LoopToScevMapT <S,296 isl_id_to_ast_expr *NewAccesses) {297 if (Value *PreloadLoad = GlobalMap.lookup(Load))298 return PreloadLoad;299 300 Value *NewPointer =301 generateLocationAccessed(Stmt, Load, BBMap, LTS, NewAccesses);302 Value *ScalarLoad =303 Builder.CreateAlignedLoad(Load->getType(), NewPointer, Load->getAlign(),304 Load->getName() + "_p_scalar_");305 306 if (PollyDebugPrinting)307 RuntimeDebugBuilder::createCPUPrinter(Builder, "Load from ", NewPointer,308 ": ", ScalarLoad, "\n");309 310 return ScalarLoad;311}312 313void BlockGenerator::generateArrayStore(ScopStmt &Stmt, StoreInst *Store,314 ValueMapT &BBMap, LoopToScevMapT <S,315 isl_id_to_ast_expr *NewAccesses) {316 MemoryAccess &MA = Stmt.getArrayAccessFor(Store);317 isl::set AccDom = MA.getAccessRelation().domain();318 std::string Subject = MA.getId().get_name();319 320 generateConditionalExecution(Stmt, AccDom, Subject.c_str(), [&, this]() {321 Value *NewPointer =322 generateLocationAccessed(Stmt, Store, BBMap, LTS, NewAccesses);323 Value *ValueOperand = getNewValue(Stmt, Store->getValueOperand(), BBMap,324 LTS, getLoopForStmt(Stmt));325 326 if (PollyDebugPrinting)327 RuntimeDebugBuilder::createCPUPrinter(Builder, "Store to ", NewPointer,328 ": ", ValueOperand, "\n");329 330 Builder.CreateAlignedStore(ValueOperand, NewPointer, Store->getAlign());331 });332}333 334bool BlockGenerator::canSyntheziseInStmt(ScopStmt &Stmt, Instruction *Inst) {335 Loop *L = getLoopForStmt(Stmt);336 return (Stmt.isBlockStmt() || !Stmt.getRegion()->contains(L)) &&337 canSynthesize(Inst, *Stmt.getParent(), &SE, L);338}339 340void BlockGenerator::copyInstruction(ScopStmt &Stmt, Instruction *Inst,341 ValueMapT &BBMap, LoopToScevMapT <S,342 isl_id_to_ast_expr *NewAccesses) {343 // Terminator instructions control the control flow. They are explicitly344 // expressed in the clast and do not need to be copied.345 if (Inst->isTerminator())346 return;347 348 // Synthesizable statements will be generated on-demand.349 if (canSyntheziseInStmt(Stmt, Inst))350 return;351 352 if (auto *Load = dyn_cast<LoadInst>(Inst)) {353 Value *NewLoad = generateArrayLoad(Stmt, Load, BBMap, LTS, NewAccesses);354 // Compute NewLoad before its insertion in BBMap to make the insertion355 // deterministic.356 BBMap[Load] = NewLoad;357 return;358 }359 360 if (auto *Store = dyn_cast<StoreInst>(Inst)) {361 // Identified as redundant by -polly-simplify.362 if (!Stmt.getArrayAccessOrNULLFor(Store))363 return;364 365 generateArrayStore(Stmt, Store, BBMap, LTS, NewAccesses);366 return;367 }368 369 if (auto *PHI = dyn_cast<PHINode>(Inst)) {370 copyPHIInstruction(Stmt, PHI, BBMap, LTS);371 return;372 }373 374 // Skip some special intrinsics for which we do not adjust the semantics to375 // the new schedule. All others are handled like every other instruction.376 if (isIgnoredIntrinsic(Inst))377 return;378 379 copyInstScalar(Stmt, Inst, BBMap, LTS);380}381 382void BlockGenerator::removeDeadInstructions(BasicBlock *BB, ValueMapT &BBMap) {383 auto NewBB = Builder.GetInsertBlock();384 for (auto I = NewBB->rbegin(); I != NewBB->rend(); I++) {385 Instruction *NewInst = &*I;386 387 if (!isInstructionTriviallyDead(NewInst))388 continue;389 390 for (auto Pair : BBMap)391 if (Pair.second == NewInst) {392 BBMap.erase(Pair.first);393 }394 395 NewInst->eraseFromParent();396 I = NewBB->rbegin();397 }398}399 400void BlockGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT <S,401 __isl_keep isl_id_to_ast_expr *NewAccesses) {402 assert(Stmt.isBlockStmt() &&403 "Only block statements can be copied by the block generator");404 405 ValueMapT BBMap;406 407 BasicBlock *BB = Stmt.getBasicBlock();408 copyBB(Stmt, BB, BBMap, LTS, NewAccesses);409 removeDeadInstructions(BB, BBMap);410}411 412BasicBlock *BlockGenerator::splitBB(BasicBlock *BB) {413 BasicBlock *CopyBB = SplitBlock(Builder.GetInsertBlock(),414 Builder.GetInsertPoint(), GenDT, GenLI);415 CopyBB->setName("polly.stmt." + BB->getName());416 return CopyBB;417}418 419BasicBlock *BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB,420 ValueMapT &BBMap, LoopToScevMapT <S,421 isl_id_to_ast_expr *NewAccesses) {422 BasicBlock *CopyBB = splitBB(BB);423 Builder.SetInsertPoint(CopyBB, CopyBB->begin());424 generateScalarLoads(Stmt, LTS, BBMap, NewAccesses);425 generateBeginStmtTrace(Stmt, LTS, BBMap);426 427 copyBB(Stmt, BB, CopyBB, BBMap, LTS, NewAccesses);428 429 // After a basic block was copied store all scalars that escape this block in430 // their alloca.431 generateScalarStores(Stmt, LTS, BBMap, NewAccesses);432 return CopyBB;433}434 435void BlockGenerator::switchGeneratedFunc(Function *GenFn, DominatorTree *GenDT,436 LoopInfo *GenLI,437 ScalarEvolution *GenSE) {438 assert(GenFn == GenDT->getRoot()->getParent());439 assert(GenLI->getTopLevelLoops().empty() ||440 GenFn == GenLI->getTopLevelLoops().front()->getHeader()->getParent());441 this->GenDT = GenDT;442 this->GenLI = GenLI;443 this->GenSE = GenSE;444}445 446void BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *CopyBB,447 ValueMapT &BBMap, LoopToScevMapT <S,448 isl_id_to_ast_expr *NewAccesses) {449 // Block statements and the entry blocks of region statement are code450 // generated from instruction lists. This allow us to optimize the451 // instructions that belong to a certain scop statement. As the code452 // structure of region statements might be arbitrary complex, optimizing the453 // instruction list is not yet supported.454 if (Stmt.isBlockStmt() || (Stmt.isRegionStmt() && Stmt.getEntryBlock() == BB))455 for (Instruction *Inst : Stmt.getInstructions())456 copyInstruction(Stmt, Inst, BBMap, LTS, NewAccesses);457 else458 for (Instruction &Inst : *BB)459 copyInstruction(Stmt, &Inst, BBMap, LTS, NewAccesses);460}461 462Value *BlockGenerator::getOrCreateAlloca(const MemoryAccess &Access) {463 assert(!Access.isLatestArrayKind() && "Trying to get alloca for array kind");464 465 return getOrCreateAlloca(Access.getLatestScopArrayInfo());466}467 468Value *BlockGenerator::getOrCreateAlloca(const ScopArrayInfo *Array) {469 assert(!Array->isArrayKind() && "Trying to get alloca for array kind");470 471 auto &Addr = ScalarMap[Array];472 473 if (Addr) {474 // Allow allocas to be (temporarily) redirected once by adding a new475 // old-alloca-addr to new-addr mapping to GlobalMap. This functionality476 // is used for example by the OpenMP code generation where a first use477 // of a scalar while still in the host code allocates a normal alloca with478 // getOrCreateAlloca. When the values of this scalar are accessed during479 // the generation of the parallel subfunction, these values are copied over480 // to the parallel subfunction and each request for a scalar alloca slot481 // must be forwarded to the temporary in-subfunction slot. This mapping is482 // removed when the subfunction has been generated and again normal host483 // code is generated. Due to the following reasons it is not possible to484 // perform the GlobalMap lookup right after creating the alloca below, but485 // instead we need to check GlobalMap at each call to getOrCreateAlloca:486 //487 // 1) GlobalMap may be changed multiple times (for each parallel loop),488 // 2) The temporary mapping is commonly only known after the initial489 // alloca has already been generated, and490 // 3) The original alloca value must be restored after leaving the491 // sub-function.492 if (Value *NewAddr = GlobalMap.lookup(&*Addr))493 return NewAddr;494 return Addr;495 }496 497 Type *Ty = Array->getElementType();498 Value *ScalarBase = Array->getBasePtr();499 std::string NameExt;500 if (Array->isPHIKind())501 NameExt = ".phiops";502 else503 NameExt = ".s2a";504 505 const DataLayout &DL = Builder.GetInsertBlock()->getDataLayout();506 507 Addr =508 new AllocaInst(Ty, DL.getAllocaAddrSpace(), nullptr,509 DL.getPrefTypeAlign(Ty), ScalarBase->getName() + NameExt);510 BasicBlock *EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock();511 Addr->insertBefore(EntryBB->getFirstInsertionPt());512 513 return Addr;514}515 516void BlockGenerator::handleOutsideUsers(const Scop &S, ScopArrayInfo *Array) {517 Instruction *Inst = cast<Instruction>(Array->getBasePtr());518 519 // If there are escape users we get the alloca for this instruction and put it520 // in the EscapeMap for later finalization. Lastly, if the instruction was521 // copied multiple times we already did this and can exit.522 if (EscapeMap.count(Inst))523 return;524 525 EscapeUserVectorTy EscapeUsers;526 for (User *U : Inst->users()) {527 528 // Non-instruction user will never escape.529 Instruction *UI = dyn_cast<Instruction>(U);530 if (!UI)531 continue;532 533 if (S.contains(UI))534 continue;535 536 EscapeUsers.push_back(UI);537 }538 539 // Exit if no escape uses were found.540 if (EscapeUsers.empty())541 return;542 543 // Get or create an escape alloca for this instruction.544 auto *ScalarAddr = getOrCreateAlloca(Array);545 546 // Remember that this instruction has escape uses and the escape alloca.547 EscapeMap[Inst] = std::make_pair(ScalarAddr, std::move(EscapeUsers));548}549 550void BlockGenerator::generateScalarLoads(551 ScopStmt &Stmt, LoopToScevMapT <S, ValueMapT &BBMap,552 __isl_keep isl_id_to_ast_expr *NewAccesses) {553 for (MemoryAccess *MA : Stmt) {554 if (MA->isOriginalArrayKind() || MA->isWrite())555 continue;556 557#ifndef NDEBUG558 auto StmtDom =559 Stmt.getDomain().intersect_params(Stmt.getParent()->getContext());560 auto AccDom = MA->getAccessRelation().domain();561 assert(!StmtDom.is_subset(AccDom).is_false() &&562 "Scalar must be loaded in all statement instances");563#endif564 565 auto *Address =566 getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS, BBMap, NewAccesses);567 BBMap[MA->getAccessValue()] = Builder.CreateLoad(568 MA->getElementType(), Address, Address->getName() + ".reload");569 }570}571 572Value *BlockGenerator::buildContainsCondition(ScopStmt &Stmt,573 const isl::set &Subdomain) {574 isl::ast_build AstBuild = Stmt.getAstBuild();575 isl::set Domain = Stmt.getDomain();576 577 isl::union_map USchedule = AstBuild.get_schedule();578 USchedule = USchedule.intersect_domain(Domain);579 580 assert(!USchedule.is_empty());581 isl::map Schedule = isl::map::from_union_map(USchedule);582 583 isl::set ScheduledDomain = Schedule.range();584 isl::set ScheduledSet = Subdomain.apply(Schedule);585 586 isl::ast_build RestrictedBuild = AstBuild.restrict(ScheduledDomain);587 588 isl::ast_expr IsInSet = RestrictedBuild.expr_from(ScheduledSet);589 Value *IsInSetExpr = ExprBuilder->create(IsInSet.copy());590 IsInSetExpr = Builder.CreateICmpNE(591 IsInSetExpr, ConstantInt::get(IsInSetExpr->getType(), 0));592 593 return IsInSetExpr;594}595 596void BlockGenerator::generateConditionalExecution(597 ScopStmt &Stmt, const isl::set &Subdomain, StringRef Subject,598 const std::function<void()> &GenThenFunc) {599 isl::set StmtDom = Stmt.getDomain();600 601 // If the condition is a tautology, don't generate a condition around the602 // code.603 bool IsPartialWrite =604 !StmtDom.intersect_params(Stmt.getParent()->getContext())605 .is_subset(Subdomain);606 if (!IsPartialWrite) {607 GenThenFunc();608 return;609 }610 611 // Generate the condition.612 Value *Cond = buildContainsCondition(Stmt, Subdomain);613 614 // Don't call GenThenFunc if it is never executed. An ast index expression615 // might not be defined in this case.616 if (auto *Const = dyn_cast<ConstantInt>(Cond))617 if (Const->isZero())618 return;619 620 BasicBlock *HeadBlock = Builder.GetInsertBlock();621 StringRef BlockName = HeadBlock->getName();622 623 // Generate the conditional block.624 DomTreeUpdater DTU(GenDT, DomTreeUpdater::UpdateStrategy::Eager);625 SplitBlockAndInsertIfThen(Cond, Builder.GetInsertPoint(), false, nullptr,626 &DTU, GenLI);627 BranchInst *Branch = cast<BranchInst>(HeadBlock->getTerminator());628 BasicBlock *ThenBlock = Branch->getSuccessor(0);629 BasicBlock *TailBlock = Branch->getSuccessor(1);630 631 // Assign descriptive names.632 if (auto *CondInst = dyn_cast<Instruction>(Cond))633 CondInst->setName("polly." + Subject + ".cond");634 ThenBlock->setName(BlockName + "." + Subject + ".partial");635 TailBlock->setName(BlockName + ".cont");636 637 // Put the client code into the conditional block and continue in the merge638 // block afterwards.639 Builder.SetInsertPoint(ThenBlock, ThenBlock->getFirstInsertionPt());640 GenThenFunc();641 Builder.SetInsertPoint(TailBlock, TailBlock->getFirstInsertionPt());642}643 644static std::string getInstName(Value *Val) {645 std::string Result;646 raw_string_ostream OS(Result);647 Val->printAsOperand(OS, false);648 return Result;649}650 651void BlockGenerator::generateBeginStmtTrace(ScopStmt &Stmt, LoopToScevMapT <S,652 ValueMapT &BBMap) {653 if (!TraceStmts)654 return;655 656 Scop *S = Stmt.getParent();657 const char *BaseName = Stmt.getBaseName();658 659 isl::ast_build AstBuild = Stmt.getAstBuild();660 isl::set Domain = Stmt.getDomain();661 662 isl::union_map USchedule = AstBuild.get_schedule().intersect_domain(Domain);663 isl::map Schedule = isl::map::from_union_map(USchedule);664 assert(Schedule.is_empty().is_false() &&665 "The stmt must have a valid instance");666 667 isl::multi_pw_aff ScheduleMultiPwAff =668 isl::pw_multi_aff::from_map(Schedule.reverse());669 isl::ast_build RestrictedBuild = AstBuild.restrict(Schedule.range());670 671 // Sequence of strings to print.672 SmallVector<llvm::Value *, 8> Values;673 674 // Print the name of the statement.675 // TODO: Indent by the depth of the statement instance in the schedule tree.676 Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, BaseName));677 Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, "("));678 679 // Add the coordinate of the statement instance.680 for (unsigned i : rangeIslSize(0, ScheduleMultiPwAff.dim(isl::dim::out))) {681 if (i > 0)682 Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, ","));683 684 isl::ast_expr IsInSet = RestrictedBuild.expr_from(ScheduleMultiPwAff.at(i));685 Values.push_back(ExprBuilder->create(IsInSet.copy()));686 }687 688 if (TraceScalars) {689 Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, ")"));690 DenseSet<Instruction *> Encountered;691 692 // Add the value of each scalar (and the result of PHIs) used in the693 // statement.694 // TODO: Values used in region-statements.695 for (Instruction *Inst : Stmt.insts()) {696 if (!RuntimeDebugBuilder::isPrintable(Inst->getType()))697 continue;698 699 if (isa<PHINode>(Inst)) {700 Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, " "));701 Values.push_back(RuntimeDebugBuilder::getPrintableString(702 Builder, getInstName(Inst)));703 Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, "="));704 Values.push_back(getNewValue(Stmt, Inst, BBMap, LTS,705 LI.getLoopFor(Inst->getParent())));706 } else {707 for (Value *Op : Inst->operand_values()) {708 // Do not print values that cannot change during the execution of the709 // SCoP.710 auto *OpInst = dyn_cast<Instruction>(Op);711 if (!OpInst)712 continue;713 if (!S->contains(OpInst))714 continue;715 716 // Print each scalar at most once, and exclude values defined in the717 // statement itself.718 if (Encountered.count(OpInst))719 continue;720 721 Values.push_back(722 RuntimeDebugBuilder::getPrintableString(Builder, " "));723 Values.push_back(RuntimeDebugBuilder::getPrintableString(724 Builder, getInstName(OpInst)));725 Values.push_back(726 RuntimeDebugBuilder::getPrintableString(Builder, "="));727 Values.push_back(getNewValue(Stmt, OpInst, BBMap, LTS,728 LI.getLoopFor(Inst->getParent())));729 Encountered.insert(OpInst);730 }731 }732 733 Encountered.insert(Inst);734 }735 736 Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, "\n"));737 } else {738 Values.push_back(RuntimeDebugBuilder::getPrintableString(Builder, ")\n"));739 }740 741 RuntimeDebugBuilder::createCPUPrinter(Builder, ArrayRef<Value *>(Values));742}743 744void BlockGenerator::generateScalarStores(745 ScopStmt &Stmt, LoopToScevMapT <S, ValueMapT &BBMap,746 __isl_keep isl_id_to_ast_expr *NewAccesses) {747 Loop *L = LI.getLoopFor(Stmt.getBasicBlock());748 749 assert(Stmt.isBlockStmt() &&750 "Region statements need to use the generateScalarStores() function in "751 "the RegionGenerator");752 753 for (MemoryAccess *MA : Stmt) {754 if (MA->isOriginalArrayKind() || MA->isRead())755 continue;756 757 isl::set AccDom = MA->getAccessRelation().domain();758 std::string Subject = MA->getId().get_name();759 760 generateConditionalExecution(761 Stmt, AccDom, Subject.c_str(), [&, this, MA]() {762 Value *Val = MA->getAccessValue();763 if (MA->isAnyPHIKind()) {764 assert(MA->getIncoming().size() >= 1 &&765 "Block statements have exactly one exiting block, or "766 "multiple but "767 "with same incoming block and value");768 assert(std::all_of(MA->getIncoming().begin(),769 MA->getIncoming().end(),770 [&](std::pair<BasicBlock *, Value *> p) -> bool {771 return p.first == Stmt.getBasicBlock();772 }) &&773 "Incoming block must be statement's block");774 Val = MA->getIncoming()[0].second;775 }776 auto Address = getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS,777 BBMap, NewAccesses);778 779 Val = getNewValue(Stmt, Val, BBMap, LTS, L);780 assert((!isa<Instruction>(Val) ||781 DT.dominates(cast<Instruction>(Val)->getParent(),782 Builder.GetInsertBlock())) &&783 "Domination violation");784 assert((!isa<Instruction>(Address) ||785 DT.dominates(cast<Instruction>(Address)->getParent(),786 Builder.GetInsertBlock())) &&787 "Domination violation");788 789 Builder.CreateStore(Val, Address);790 });791 }792}793 794void BlockGenerator::createScalarInitialization(Scop &S) {795 BasicBlock *ExitBB = S.getExit();796 BasicBlock *PreEntryBB = S.getEnteringBlock();797 798 Builder.SetInsertPoint(StartBlock, StartBlock->begin());799 800 for (auto &Array : S.arrays()) {801 if (Array->getNumberOfDimensions() != 0)802 continue;803 if (Array->isPHIKind()) {804 // For PHI nodes, the only values we need to store are the ones that805 // reach the PHI node from outside the region. In general there should806 // only be one such incoming edge and this edge should enter through807 // 'PreEntryBB'.808 auto PHI = cast<PHINode>(Array->getBasePtr());809 810 for (auto BI = PHI->block_begin(), BE = PHI->block_end(); BI != BE; BI++)811 if (!S.contains(*BI) && *BI != PreEntryBB)812 llvm_unreachable("Incoming edges from outside the scop should always "813 "come from PreEntryBB");814 815 int Idx = PHI->getBasicBlockIndex(PreEntryBB);816 if (Idx < 0)817 continue;818 819 Value *ScalarValue = PHI->getIncomingValue(Idx);820 821 Builder.CreateStore(ScalarValue, getOrCreateAlloca(Array));822 continue;823 }824 825 auto *Inst = dyn_cast<Instruction>(Array->getBasePtr());826 827 if (Inst && S.contains(Inst))828 continue;829 830 // PHI nodes that are not marked as such in their SAI object are either exit831 // PHI nodes we model as common scalars but without initialization, or832 // incoming phi nodes that need to be initialized. Check if the first is the833 // case for Inst and do not create and initialize memory if so.834 if (auto *PHI = dyn_cast_or_null<PHINode>(Inst))835 if (!S.hasSingleExitEdge() && PHI->getBasicBlockIndex(ExitBB) >= 0)836 continue;837 838 Builder.CreateStore(Array->getBasePtr(), getOrCreateAlloca(Array));839 }840}841 842void BlockGenerator::createScalarFinalization(Scop &S) {843 // The exit block of the __unoptimized__ region.844 BasicBlock *ExitBB = S.getExitingBlock();845 // The merge block __just after__ the region and the optimized region.846 BasicBlock *MergeBB = S.getExit();847 848 // The exit block of the __optimized__ region.849 BasicBlock *OptExitBB = *(pred_begin(MergeBB));850 if (OptExitBB == ExitBB)851 OptExitBB = *(++pred_begin(MergeBB));852 853 Builder.SetInsertPoint(OptExitBB, OptExitBB->getTerminator()->getIterator());854 for (const auto &EscapeMapping : EscapeMap) {855 // Extract the escaping instruction and the escaping users as well as the856 // alloca the instruction was demoted to.857 Instruction *EscapeInst = EscapeMapping.first;858 const auto &EscapeMappingValue = EscapeMapping.second;859 const EscapeUserVectorTy &EscapeUsers = EscapeMappingValue.second;860 auto *ScalarAddr = cast<AllocaInst>(&*EscapeMappingValue.first);861 862 // Reload the demoted instruction in the optimized version of the SCoP.863 Value *EscapeInstReload =864 Builder.CreateLoad(ScalarAddr->getAllocatedType(), ScalarAddr,865 EscapeInst->getName() + ".final_reload");866 EscapeInstReload =867 Builder.CreateBitOrPointerCast(EscapeInstReload, EscapeInst->getType());868 869 // Create the merge PHI that merges the optimized and unoptimized version.870 PHINode *MergePHI = PHINode::Create(EscapeInst->getType(), 2,871 EscapeInst->getName() + ".merge");872 MergePHI->insertBefore(MergeBB->getFirstInsertionPt());873 874 // Add the respective values to the merge PHI.875 MergePHI->addIncoming(EscapeInstReload, OptExitBB);876 MergePHI->addIncoming(EscapeInst, ExitBB);877 878 // The information of scalar evolution about the escaping instruction needs879 // to be revoked so the new merged instruction will be used.880 if (SE.isSCEVable(EscapeInst->getType()))881 SE.forgetValue(EscapeInst);882 883 // Replace all uses of the demoted instruction with the merge PHI.884 for (Instruction *EUser : EscapeUsers)885 EUser->replaceUsesOfWith(EscapeInst, MergePHI);886 }887}888 889void BlockGenerator::findOutsideUsers(Scop &S) {890 for (auto &Array : S.arrays()) {891 892 if (Array->getNumberOfDimensions() != 0)893 continue;894 895 if (Array->isPHIKind())896 continue;897 898 auto *Inst = dyn_cast<Instruction>(Array->getBasePtr());899 900 if (!Inst)901 continue;902 903 // Scop invariant hoisting moves some of the base pointers out of the scop.904 // We can ignore these, as the invariant load hoisting already registers the905 // relevant outside users.906 if (!S.contains(Inst))907 continue;908 909 handleOutsideUsers(S, Array);910 }911}912 913void BlockGenerator::createExitPHINodeMerges(Scop &S) {914 if (S.hasSingleExitEdge())915 return;916 917 auto *ExitBB = S.getExitingBlock();918 auto *MergeBB = S.getExit();919 auto *AfterMergeBB = MergeBB->getSingleSuccessor();920 BasicBlock *OptExitBB = *(pred_begin(MergeBB));921 if (OptExitBB == ExitBB)922 OptExitBB = *(++pred_begin(MergeBB));923 924 Builder.SetInsertPoint(OptExitBB, OptExitBB->getTerminator()->getIterator());925 926 for (auto &SAI : S.arrays()) {927 auto *Val = SAI->getBasePtr();928 929 // Only Value-like scalars need a merge PHI. Exit block PHIs receive either930 // the original PHI's value or the reloaded incoming values from the931 // generated code. An llvm::Value is merged between the original code's932 // value or the generated one.933 if (!SAI->isExitPHIKind())934 continue;935 936 PHINode *PHI = dyn_cast<PHINode>(Val);937 if (!PHI)938 continue;939 940 if (PHI->getParent() != AfterMergeBB)941 continue;942 943 std::string Name = PHI->getName().str();944 Value *ScalarAddr = getOrCreateAlloca(SAI);945 Value *Reload = Builder.CreateLoad(SAI->getElementType(), ScalarAddr,946 Name + ".ph.final_reload");947 Reload = Builder.CreateBitOrPointerCast(Reload, PHI->getType());948 Value *OriginalValue = PHI->getIncomingValueForBlock(MergeBB);949 assert((!isa<Instruction>(OriginalValue) ||950 cast<Instruction>(OriginalValue)->getParent() != MergeBB) &&951 "Original value must no be one we just generated.");952 auto *MergePHI = PHINode::Create(PHI->getType(), 2, Name + ".ph.merge");953 MergePHI->insertBefore(MergeBB->getFirstInsertionPt());954 MergePHI->addIncoming(Reload, OptExitBB);955 MergePHI->addIncoming(OriginalValue, ExitBB);956 int Idx = PHI->getBasicBlockIndex(MergeBB);957 PHI->setIncomingValue(Idx, MergePHI);958 }959}960 961void BlockGenerator::invalidateScalarEvolution(Scop &S) {962 for (auto &Stmt : S)963 if (Stmt.isCopyStmt())964 continue;965 else if (Stmt.isBlockStmt())966 for (auto &Inst : *Stmt.getBasicBlock())967 SE.forgetValue(&Inst);968 else if (Stmt.isRegionStmt())969 for (auto *BB : Stmt.getRegion()->blocks())970 for (auto &Inst : *BB)971 SE.forgetValue(&Inst);972 else973 llvm_unreachable("Unexpected statement type found");974 975 // Invalidate SCEV of loops surrounding the EscapeUsers.976 for (const auto &EscapeMapping : EscapeMap) {977 const EscapeUserVectorTy &EscapeUsers = EscapeMapping.second.second;978 for (Instruction *EUser : EscapeUsers) {979 if (Loop *L = LI.getLoopFor(EUser->getParent()))980 while (L) {981 SE.forgetLoop(L);982 L = L->getParentLoop();983 }984 }985 }986}987 988void BlockGenerator::finalizeSCoP(Scop &S) {989 findOutsideUsers(S);990 createScalarInitialization(S);991 createExitPHINodeMerges(S);992 createScalarFinalization(S);993 invalidateScalarEvolution(S);994}995 996BasicBlock *RegionGenerator::repairDominance(BasicBlock *BB,997 BasicBlock *BBCopy) {998 999 BasicBlock *BBIDom = DT.getNode(BB)->getIDom()->getBlock();1000 BasicBlock *BBCopyIDom = EndBlockMap.lookup(BBIDom);1001 1002 if (BBCopyIDom)1003 GenDT->changeImmediateDominator(BBCopy, BBCopyIDom);1004 1005 return StartBlockMap.lookup(BBIDom);1006}1007 1008// This is to determine whether an llvm::Value (defined in @p BB) is usable when1009// leaving a subregion. The straight-forward DT.dominates(BB, R->getExitBlock())1010// does not work in cases where the exit block has edges from outside the1011// region. In that case the llvm::Value would never be usable in in the exit1012// block. The RegionGenerator however creates an new exit block ('ExitBBCopy')1013// for the subregion's exiting edges only. We need to determine whether an1014// llvm::Value is usable in there. We do this by checking whether it dominates1015// all exiting blocks individually.1016static bool isDominatingSubregionExit(const DominatorTree &DT, Region *R,1017 BasicBlock *BB) {1018 for (auto ExitingBB : predecessors(R->getExit())) {1019 // Check for non-subregion incoming edges.1020 if (!R->contains(ExitingBB))1021 continue;1022 1023 if (!DT.dominates(BB, ExitingBB))1024 return false;1025 }1026 1027 return true;1028}1029 1030// Find the direct dominator of the subregion's exit block if the subregion was1031// simplified.1032static BasicBlock *findExitDominator(DominatorTree &DT, Region *R) {1033 BasicBlock *Common = nullptr;1034 for (auto ExitingBB : predecessors(R->getExit())) {1035 // Check for non-subregion incoming edges.1036 if (!R->contains(ExitingBB))1037 continue;1038 1039 // First exiting edge.1040 if (!Common) {1041 Common = ExitingBB;1042 continue;1043 }1044 1045 Common = DT.findNearestCommonDominator(Common, ExitingBB);1046 }1047 1048 assert(Common && R->contains(Common));1049 return Common;1050}1051 1052void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT <S,1053 __isl_keep isl_id_to_ast_expr *IdToAstExp) {1054 assert(Stmt.isRegionStmt() &&1055 "Only region statements can be copied by the region generator");1056 1057 // Forget all old mappings.1058 StartBlockMap.clear();1059 EndBlockMap.clear();1060 RegionMaps.clear();1061 IncompletePHINodeMap.clear();1062 1063 // Collection of all values related to this subregion.1064 ValueMapT ValueMap;1065 1066 // The region represented by the statement.1067 Region *R = Stmt.getRegion();1068 1069 // Create a dedicated entry for the region where we can reload all demoted1070 // inputs.1071 BasicBlock *EntryBB = R->getEntry();1072 BasicBlock *EntryBBCopy = SplitBlock(Builder.GetInsertBlock(),1073 Builder.GetInsertPoint(), GenDT, GenLI);1074 EntryBBCopy->setName("polly.stmt." + EntryBB->getName() + ".entry");1075 Builder.SetInsertPoint(EntryBBCopy, EntryBBCopy->begin());1076 1077 ValueMapT &EntryBBMap = RegionMaps[EntryBBCopy];1078 generateScalarLoads(Stmt, LTS, EntryBBMap, IdToAstExp);1079 generateBeginStmtTrace(Stmt, LTS, EntryBBMap);1080 1081 for (auto PI = pred_begin(EntryBB), PE = pred_end(EntryBB); PI != PE; ++PI)1082 if (!R->contains(*PI)) {1083 StartBlockMap[*PI] = EntryBBCopy;1084 EndBlockMap[*PI] = EntryBBCopy;1085 }1086 1087 // Iterate over all blocks in the region in a breadth-first search.1088 std::deque<BasicBlock *> Blocks;1089 SmallSetVector<BasicBlock *, 8> SeenBlocks;1090 Blocks.push_back(EntryBB);1091 SeenBlocks.insert(EntryBB);1092 1093 while (!Blocks.empty()) {1094 BasicBlock *BB = Blocks.front();1095 Blocks.pop_front();1096 1097 // First split the block and update dominance information.1098 BasicBlock *BBCopy = splitBB(BB);1099 BasicBlock *BBCopyIDom = repairDominance(BB, BBCopy);1100 1101 // Get the mapping for this block and initialize it with either the scalar1102 // loads from the generated entering block (which dominates all blocks of1103 // this subregion) or the maps of the immediate dominator, if part of the1104 // subregion. The latter necessarily includes the former.1105 ValueMapT *InitBBMap;1106 if (BBCopyIDom) {1107 assert(RegionMaps.count(BBCopyIDom));1108 InitBBMap = &RegionMaps[BBCopyIDom];1109 } else1110 InitBBMap = &EntryBBMap;1111 auto Inserted = RegionMaps.insert(std::make_pair(BBCopy, *InitBBMap));1112 ValueMapT &RegionMap = Inserted.first->second;1113 1114 // Copy the block with the BlockGenerator.1115 Builder.SetInsertPoint(BBCopy, BBCopy->begin());1116 copyBB(Stmt, BB, BBCopy, RegionMap, LTS, IdToAstExp);1117 1118 // In order to remap PHI nodes we store also basic block mappings.1119 StartBlockMap[BB] = BBCopy;1120 EndBlockMap[BB] = Builder.GetInsertBlock();1121 1122 // Add values to incomplete PHI nodes waiting for this block to be copied.1123 for (const PHINodePairTy &PHINodePair : IncompletePHINodeMap[BB])1124 addOperandToPHI(Stmt, PHINodePair.first, PHINodePair.second, BB, LTS);1125 IncompletePHINodeMap[BB].clear();1126 1127 // And continue with new successors inside the region.1128 for (auto SI = succ_begin(BB), SE = succ_end(BB); SI != SE; SI++)1129 if (R->contains(*SI) && SeenBlocks.insert(*SI))1130 Blocks.push_back(*SI);1131 1132 // Remember value in case it is visible after this subregion.1133 if (isDominatingSubregionExit(DT, R, BB))1134 ValueMap.insert_range(RegionMap);1135 }1136 1137 // Now create a new dedicated region exit block and add it to the region map.1138 BasicBlock *ExitBBCopy = SplitBlock(Builder.GetInsertBlock(),1139 Builder.GetInsertPoint(), GenDT, GenLI);1140 ExitBBCopy->setName("polly.stmt." + R->getExit()->getName() + ".exit");1141 StartBlockMap[R->getExit()] = ExitBBCopy;1142 EndBlockMap[R->getExit()] = ExitBBCopy;1143 1144 BasicBlock *ExitDomBBCopy = EndBlockMap.lookup(findExitDominator(DT, R));1145 assert(ExitDomBBCopy &&1146 "Common exit dominator must be within region; at least the entry node "1147 "must match");1148 GenDT->changeImmediateDominator(ExitBBCopy, ExitDomBBCopy);1149 1150 // As the block generator doesn't handle control flow we need to add the1151 // region control flow by hand after all blocks have been copied.1152 for (BasicBlock *BB : SeenBlocks) {1153 1154 BasicBlock *BBCopyStart = StartBlockMap[BB];1155 BasicBlock *BBCopyEnd = EndBlockMap[BB];1156 Instruction *TI = BB->getTerminator();1157 if (isa<UnreachableInst>(TI)) {1158 while (!BBCopyEnd->empty())1159 BBCopyEnd->begin()->eraseFromParent();1160 new UnreachableInst(BBCopyEnd->getContext(), BBCopyEnd);1161 continue;1162 }1163 1164 Instruction *BICopy = BBCopyEnd->getTerminator();1165 1166 ValueMapT &RegionMap = RegionMaps[BBCopyStart];1167 RegionMap.insert_range(StartBlockMap);1168 1169 Builder.SetInsertPoint(BBCopyEnd, BICopy->getIterator());1170 copyInstScalar(Stmt, TI, RegionMap, LTS);1171 BICopy->eraseFromParent();1172 }1173 1174 // Add counting PHI nodes to all loops in the region that can be used as1175 // replacement for SCEVs referring to the old loop.1176 for (BasicBlock *BB : SeenBlocks) {1177 Loop *L = LI.getLoopFor(BB);1178 if (L == nullptr || L->getHeader() != BB || !R->contains(L))1179 continue;1180 1181 BasicBlock *BBCopy = StartBlockMap[BB];1182 Value *NullVal = Builder.getInt32(0);1183 PHINode *LoopPHI =1184 PHINode::Create(Builder.getInt32Ty(), 2, "polly.subregion.iv");1185 Instruction *LoopPHIInc = BinaryOperator::CreateAdd(1186 LoopPHI, Builder.getInt32(1), "polly.subregion.iv.inc");1187 LoopPHI->insertBefore(BBCopy->begin());1188 LoopPHIInc->insertBefore(BBCopy->getTerminator()->getIterator());1189 1190 for (auto *PredBB : predecessors(BB)) {1191 if (!R->contains(PredBB))1192 continue;1193 if (L->contains(PredBB))1194 LoopPHI->addIncoming(LoopPHIInc, EndBlockMap[PredBB]);1195 else1196 LoopPHI->addIncoming(NullVal, EndBlockMap[PredBB]);1197 }1198 1199 for (auto *PredBBCopy : predecessors(BBCopy))1200 if (LoopPHI->getBasicBlockIndex(PredBBCopy) < 0)1201 LoopPHI->addIncoming(NullVal, PredBBCopy);1202 1203 LTS[L] = SE.getUnknown(LoopPHI);1204 }1205 1206 // Continue generating code in the exit block.1207 Builder.SetInsertPoint(ExitBBCopy, ExitBBCopy->getFirstInsertionPt());1208 1209 // Write values visible to other statements.1210 generateScalarStores(Stmt, LTS, ValueMap, IdToAstExp);1211 StartBlockMap.clear();1212 EndBlockMap.clear();1213 RegionMaps.clear();1214 IncompletePHINodeMap.clear();1215}1216 1217PHINode *RegionGenerator::buildExitPHI(MemoryAccess *MA, LoopToScevMapT <S,1218 ValueMapT &BBMap, Loop *L) {1219 ScopStmt *Stmt = MA->getStatement();1220 Region *SubR = Stmt->getRegion();1221 auto Incoming = MA->getIncoming();1222 1223 PollyIRBuilder::InsertPointGuard IPGuard(Builder);1224 PHINode *OrigPHI = cast<PHINode>(MA->getAccessInstruction());1225 BasicBlock *NewSubregionExit = Builder.GetInsertBlock();1226 1227 // This can happen if the subregion is simplified after the ScopStmts1228 // have been created; simplification happens as part of CodeGeneration.1229 if (OrigPHI->getParent() != SubR->getExit()) {1230 BasicBlock *FormerExit = SubR->getExitingBlock();1231 if (FormerExit)1232 NewSubregionExit = StartBlockMap.lookup(FormerExit);1233 }1234 1235 PHINode *NewPHI = PHINode::Create(OrigPHI->getType(), Incoming.size(),1236 "polly." + OrigPHI->getName(),1237 NewSubregionExit->getFirstNonPHIIt());1238 1239 // Add the incoming values to the PHI.1240 for (auto &Pair : Incoming) {1241 BasicBlock *OrigIncomingBlock = Pair.first;1242 BasicBlock *NewIncomingBlockStart = StartBlockMap.lookup(OrigIncomingBlock);1243 BasicBlock *NewIncomingBlockEnd = EndBlockMap.lookup(OrigIncomingBlock);1244 Builder.SetInsertPoint(NewIncomingBlockEnd,1245 NewIncomingBlockEnd->getTerminator()->getIterator());1246 assert(RegionMaps.count(NewIncomingBlockStart));1247 assert(RegionMaps.count(NewIncomingBlockEnd));1248 ValueMapT *LocalBBMap = &RegionMaps[NewIncomingBlockStart];1249 1250 Value *OrigIncomingValue = Pair.second;1251 Value *NewIncomingValue =1252 getNewValue(*Stmt, OrigIncomingValue, *LocalBBMap, LTS, L);1253 NewPHI->addIncoming(NewIncomingValue, NewIncomingBlockEnd);1254 }1255 1256 return NewPHI;1257}1258 1259Value *RegionGenerator::getExitScalar(MemoryAccess *MA, LoopToScevMapT <S,1260 ValueMapT &BBMap) {1261 ScopStmt *Stmt = MA->getStatement();1262 1263 // TODO: Add some test cases that ensure this is really the right choice.1264 Loop *L = LI.getLoopFor(Stmt->getRegion()->getExit());1265 1266 if (MA->isAnyPHIKind()) {1267 auto Incoming = MA->getIncoming();1268 assert(!Incoming.empty() &&1269 "PHI WRITEs must have originate from at least one incoming block");1270 1271 // If there is only one incoming value, we do not need to create a PHI.1272 if (Incoming.size() == 1) {1273 Value *OldVal = Incoming[0].second;1274 return getNewValue(*Stmt, OldVal, BBMap, LTS, L);1275 }1276 1277 return buildExitPHI(MA, LTS, BBMap, L);1278 }1279 1280 // MemoryKind::Value accesses leaving the subregion must dominate the exit1281 // block; just pass the copied value.1282 Value *OldVal = MA->getAccessValue();1283 return getNewValue(*Stmt, OldVal, BBMap, LTS, L);1284}1285 1286void RegionGenerator::generateScalarStores(1287 ScopStmt &Stmt, LoopToScevMapT <S, ValueMapT &BBMap,1288 __isl_keep isl_id_to_ast_expr *NewAccesses) {1289 assert(Stmt.getRegion() &&1290 "Block statements need to use the generateScalarStores() "1291 "function in the BlockGenerator");1292 1293 // Get the exit scalar values before generating the writes.1294 // This is necessary because RegionGenerator::getExitScalar may insert1295 // PHINodes that depend on the region's exiting blocks. But1296 // BlockGenerator::generateConditionalExecution may insert a new basic block1297 // such that the current basic block is not a direct successor of the exiting1298 // blocks anymore. Hence, build the PHINodes while the current block is still1299 // the direct successor.1300 SmallDenseMap<MemoryAccess *, Value *> NewExitScalars;1301 for (MemoryAccess *MA : Stmt) {1302 if (MA->isOriginalArrayKind() || MA->isRead())1303 continue;1304 1305 Value *NewVal = getExitScalar(MA, LTS, BBMap);1306 NewExitScalars[MA] = NewVal;1307 }1308 1309 for (MemoryAccess *MA : Stmt) {1310 if (MA->isOriginalArrayKind() || MA->isRead())1311 continue;1312 1313 isl::set AccDom = MA->getAccessRelation().domain();1314 std::string Subject = MA->getId().get_name();1315 generateConditionalExecution(1316 Stmt, AccDom, Subject.c_str(), [&, this, MA]() {1317 Value *NewVal = NewExitScalars.lookup(MA);1318 assert(NewVal && "The exit scalar must be determined before");1319 Value *Address = getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS,1320 BBMap, NewAccesses);1321 assert((!isa<Instruction>(NewVal) ||1322 DT.dominates(cast<Instruction>(NewVal)->getParent(),1323 Builder.GetInsertBlock())) &&1324 "Domination violation");1325 assert((!isa<Instruction>(Address) ||1326 DT.dominates(cast<Instruction>(Address)->getParent(),1327 Builder.GetInsertBlock())) &&1328 "Domination violation");1329 Builder.CreateStore(NewVal, Address);1330 });1331 }1332}1333 1334void RegionGenerator::addOperandToPHI(ScopStmt &Stmt, PHINode *PHI,1335 PHINode *PHICopy, BasicBlock *IncomingBB,1336 LoopToScevMapT <S) {1337 // If the incoming block was not yet copied mark this PHI as incomplete.1338 // Once the block will be copied the incoming value will be added.1339 BasicBlock *BBCopyStart = StartBlockMap[IncomingBB];1340 BasicBlock *BBCopyEnd = EndBlockMap[IncomingBB];1341 if (!BBCopyStart) {1342 assert(!BBCopyEnd);1343 assert(Stmt.represents(IncomingBB) &&1344 "Bad incoming block for PHI in non-affine region");1345 IncompletePHINodeMap[IncomingBB].push_back(std::make_pair(PHI, PHICopy));1346 return;1347 }1348 1349 assert(RegionMaps.count(BBCopyStart) &&1350 "Incoming PHI block did not have a BBMap");1351 ValueMapT &BBCopyMap = RegionMaps[BBCopyStart];1352 1353 Value *OpCopy = nullptr;1354 1355 if (Stmt.represents(IncomingBB)) {1356 Value *Op = PHI->getIncomingValueForBlock(IncomingBB);1357 1358 // If the current insert block is different from the PHIs incoming block1359 // change it, otherwise do not.1360 auto IP = Builder.GetInsertPoint();1361 if (IP->getParent() != BBCopyEnd)1362 Builder.SetInsertPoint(BBCopyEnd,1363 BBCopyEnd->getTerminator()->getIterator());1364 OpCopy = getNewValue(Stmt, Op, BBCopyMap, LTS, getLoopForStmt(Stmt));1365 if (IP->getParent() != BBCopyEnd)1366 Builder.SetInsertPoint(IP);1367 } else {1368 // All edges from outside the non-affine region become a single edge1369 // in the new copy of the non-affine region. Make sure to only add the1370 // corresponding edge the first time we encounter a basic block from1371 // outside the non-affine region.1372 if (PHICopy->getBasicBlockIndex(BBCopyEnd) >= 0)1373 return;1374 1375 // Get the reloaded value.1376 OpCopy = getNewValue(Stmt, PHI, BBCopyMap, LTS, getLoopForStmt(Stmt));1377 }1378 1379 assert(OpCopy && "Incoming PHI value was not copied properly");1380 PHICopy->addIncoming(OpCopy, BBCopyEnd);1381}1382 1383void RegionGenerator::copyPHIInstruction(ScopStmt &Stmt, PHINode *PHI,1384 ValueMapT &BBMap,1385 LoopToScevMapT <S) {1386 unsigned NumIncoming = PHI->getNumIncomingValues();1387 PHINode *PHICopy =1388 Builder.CreatePHI(PHI->getType(), NumIncoming, "polly." + PHI->getName());1389 PHICopy->moveBefore(PHICopy->getParent()->getFirstNonPHIIt());1390 BBMap[PHI] = PHICopy;1391 1392 for (BasicBlock *IncomingBB : PHI->blocks())1393 addOperandToPHI(Stmt, PHI, PHICopy, IncomingBB, LTS);1394}1395