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"
35static cl::opt<bool>
Aligned(
"enable-polly-aligned",
36 cl::desc(
"Assumed aligned memory accesses."),
41 "polly-codegen-add-debug-printing",
42 cl::desc(
"Add printf calls that show the values loaded/stored."),
46 "polly-codegen-trace-stmts",
47 cl::desc(
"Add printf calls that print the statement being executed"),
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."),
57 PollyIRBuilder &
B, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT,
60 : Builder(
B), LI(LI), SE(SE), ExprBuilder(ExprBuilder), DT(DT),
61 EntryBB(nullptr), ScalarMap(ScalarMap), EscapeMap(EscapeMap),
62 GlobalMap(GlobalMap), StartBlock(StartBlock) {}
68 if (!
SE.isSCEVable(Old->getType()))
71 const SCEV *Scev =
SE.getSCEVAtScope(Old, L);
75 if (isa<SCEVCouldNotCompute>(Scev))
78 const SCEV *NewScev = SCEVLoopAddRecRewriter::rewrite(Scev, LTS,
SE);
80 VTV.insert(BBMap.begin(), BBMap.end());
84 const DataLayout &DL =
S.getFunction().getParent()->getDataLayout();
85 auto IP =
Builder.GetInsertPoint();
88 "Only instructions can be insert points for SCEVExpander");
93 BBMap[Old] = Expanded;
98 LoopToScevMapT <S, Loop *L)
const {
100 auto lookupGlobally = [
this](
Value *Old) ->
Value * {
119 if (Old->getType()->getScalarSizeInBits() <
120 New->getType()->getScalarSizeInBits())
121 New =
Builder.CreateTruncOrBitCast(New, Old->getType());
126 Value *New =
nullptr;
128 switch (VUse.getKind()) {
131 New = BBMap.lookup(Old);
140 if ((New = lookupGlobally(Old)))
143 assert(!BBMap.count(Old));
161 if ((New = BBMap.lookup(Old)))
177 if ((New = lookupGlobally(Old)))
189 if ((New = BBMap.lookup(Old)))
200 New = lookupGlobally(Old);
206 "Intra and inter-stmt values are never global");
207 New = BBMap.lookup(Old);
210 assert(New &&
"Unexpected scalar dependence in region!");
219 if (isa<DbgInfoIntrinsic>(Inst))
222 Instruction *NewInst = Inst->clone();
225 for (
Value *OldOperand : Inst->operands()) {
230 assert(!isa<StoreInst>(NewInst) &&
231 "Store instructions are always needed!");
232 NewInst->deleteValue();
236 NewInst->replaceUsesOfWith(OldOperand, NewOperand);
240 BBMap[Inst] = NewInst;
242 assert(NewInst->getModule() == Inst->getModule() &&
243 "Expecting instructions to be in the same module");
245 if (!NewInst->getType()->isVoidTy())
246 NewInst->setName(
"p_" + Inst->getName());
252 isl_id_to_ast_expr *NewAccesses) {
262 LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses,
__isl_take isl_id *Id,
263 Type *ExpectedType) {
264 isl_ast_expr *AccessExpr = isl_id_to_ast_expr_get(NewAccesses, Id);
272 "If expression was not generated, must use the original pointer value");
290 return LI.getLoopFor(StmtBB);
295 isl_id_to_ast_expr *NewAccesses) {
302 Builder.CreateAlignedLoad(Load->getType(), NewPointer, Load->getAlign(),
303 Load->getName() +
"_p_scalar_");
307 ": ", ScalarLoad,
"\n");
314 isl_id_to_ast_expr *NewAccesses) {
321 generateLocationAccessed(Stmt, Store, BBMap, LTS, NewAccesses);
322 Value *ValueOperand = getNewValue(Stmt, Store->getValueOperand(), BBMap,
323 LTS, getLoopForStmt(Stmt));
325 if (PollyDebugPrinting)
326 RuntimeDebugBuilder::createCPUPrinter(Builder,
"Store to ", NewPointer,
327 ": ", ValueOperand,
"\n");
329 Builder.CreateAlignedStore(ValueOperand, NewPointer, Store->getAlign());
341 isl_id_to_ast_expr *NewAccesses) {
344 if (Inst->isTerminator())
351 if (
auto *Load = dyn_cast<LoadInst>(Inst)) {
355 BBMap[Load] = NewLoad;
359 if (
auto *Store = dyn_cast<StoreInst>(Inst)) {
368 if (
auto *
PHI = dyn_cast<PHINode>(Inst)) {
382 auto NewBB =
Builder.GetInsertBlock();
383 for (
auto I = NewBB->rbegin(); I != NewBB->rend(); I++) {
384 Instruction *NewInst = &*I;
386 if (!isInstructionTriviallyDead(NewInst))
389 for (
auto Pair : BBMap)
390 if (
Pair.second == NewInst) {
391 BBMap.erase(
Pair.first);
394 NewInst->eraseFromParent();
402 "Only block statements can be copied by the block generator");
407 copyBB(Stmt, BB, BBMap, LTS, NewAccesses);
412 BasicBlock *CopyBB = SplitBlock(
Builder.GetInsertBlock(),
414 CopyBB->setName(
"polly.stmt." + BB->getName());
420 isl_id_to_ast_expr *NewAccesses) {
421 BasicBlock *CopyBB =
splitBB(BB);
422 Builder.SetInsertPoint(&CopyBB->front());
426 copyBB(Stmt, BB, CopyBB, BBMap, LTS, NewAccesses);
436 isl_id_to_ast_expr *NewAccesses) {
437 EntryBB = &CopyBB->getParent()->getEntryBlock();
448 for (Instruction &Inst : *BB)
459 assert(!
Array->isArrayKind() &&
"Trying to get alloca for array kind");
487 Type *Ty =
Array->getElementType();
490 if (
Array->isPHIKind())
495 const DataLayout &DL =
Builder.GetInsertBlock()->getModule()->getDataLayout();
498 new AllocaInst(Ty, DL.getAllocaAddrSpace(),
nullptr,
499 DL.getPrefTypeAlign(Ty), ScalarBase->getName() + NameExt);
500 EntryBB = &
Builder.GetInsertBlock()->getParent()->getEntryBlock();
501 Addr->insertBefore(&*
EntryBB->getFirstInsertionPt());
507 Instruction *Inst = cast<Instruction>(
Array->getBasePtr());
516 for (User *U : Inst->users()) {
519 Instruction *UI = dyn_cast<Instruction>(U);
526 EscapeUsers.push_back(UI);
530 if (EscapeUsers.empty())
537 EscapeMap[Inst] = std::make_pair(ScalarAddr, std::move(EscapeUsers));
544 if (MA->isOriginalArrayKind() || MA->isWrite())
550 auto AccDom = MA->getAccessRelation().domain();
551 assert(!StmtDom.is_subset(AccDom).is_false() &&
552 "Scalar must be loaded in all statement instances");
557 assert((!isa<Instruction>(Address) ||
558 DT.dominates(cast<Instruction>(Address)->getParent(),
560 "Domination violation");
561 BBMap[MA->getAccessValue()] =
Builder.CreateLoad(
562 MA->getElementType(), Address, Address->getName() +
".reload");
584 IsInSetExpr =
Builder.CreateICmpNE(
585 IsInSetExpr, ConstantInt::get(IsInSetExpr->getType(), 0));
592 const std::function<
void()> &GenThenFunc) {
597 bool IsPartialWrite =
600 if (!IsPartialWrite) {
610 if (
auto *Const = dyn_cast<ConstantInt>(Cond))
614 BasicBlock *HeadBlock =
Builder.GetInsertBlock();
615 StringRef BlockName = HeadBlock->getName();
618 DomTreeUpdater DTU(
DT, DomTreeUpdater::UpdateStrategy::Eager);
619 SplitBlockAndInsertIfThen(Cond, &*
Builder.GetInsertPoint(),
false,
nullptr,
621 BranchInst *Branch = cast<BranchInst>(HeadBlock->getTerminator());
622 BasicBlock *ThenBlock = Branch->getSuccessor(0);
623 BasicBlock *TailBlock = Branch->getSuccessor(1);
626 if (
auto *CondInst = dyn_cast<Instruction>(Cond))
627 CondInst->setName(
"polly." + Subject +
".cond");
628 ThenBlock->setName(BlockName +
"." + Subject +
".partial");
629 TailBlock->setName(BlockName +
".cont");
633 Builder.SetInsertPoint(ThenBlock, ThenBlock->getFirstInsertionPt());
635 Builder.SetInsertPoint(TailBlock, TailBlock->getFirstInsertionPt());
640 raw_string_ostream OS(Result);
641 Val->printAsOperand(OS,
false);
659 "The stmt must have a valid instance");
666 SmallVector<llvm::Value *, 8> Values;
684 DenseSet<Instruction *> Encountered;
689 for (Instruction *Inst : Stmt.
insts()) {
693 if (isa<PHINode>(Inst)) {
698 Values.push_back(
getNewValue(Stmt, Inst, BBMap, LTS,
699 LI.getLoopFor(Inst->getParent())));
701 for (
Value *Op : Inst->operand_values()) {
704 auto *OpInst = dyn_cast<Instruction>(Op);
707 if (!
S->contains(OpInst))
712 if (Encountered.count(OpInst))
721 Values.push_back(
getNewValue(Stmt, OpInst, BBMap, LTS,
722 LI.getLoopFor(Inst->getParent())));
723 Encountered.insert(OpInst);
727 Encountered.insert(Inst);
744 "Region statements need to use the generateScalarStores() function in "
745 "the RegionGenerator");
748 if (MA->isOriginalArrayKind() || MA->isRead())
751 isl::set AccDom = MA->getAccessRelation().domain();
752 std::string Subject = MA->getId().get_name();
755 Stmt, AccDom, Subject.c_str(), [&,
this, MA]() {
756 Value *Val = MA->getAccessValue();
757 if (MA->isAnyPHIKind()) {
758 assert(MA->getIncoming().size() >= 1 &&
759 "Block statements have exactly one exiting block, or "
761 "with same incoming block and value");
762 assert(std::all_of(MA->getIncoming().begin(),
763 MA->getIncoming().end(),
764 [&](std::pair<BasicBlock *, Value *> p) -> bool {
765 return p.first == Stmt.getBasicBlock();
767 "Incoming block must be statement's block");
768 Val = MA->getIncoming()[0].second;
774 assert((!isa<Instruction>(Val) ||
775 DT.dominates(cast<Instruction>(Val)->getParent(),
777 "Domination violation");
778 assert((!isa<Instruction>(Address) ||
779 DT.dominates(cast<Instruction>(Address)->getParent(),
781 "Domination violation");
785 Address =
Builder.CreateBitOrPointerCast(
786 Address, Val->getType()->getPointerTo(
787 Address->getType()->getPointerAddressSpace()));
789 Builder.CreateStore(Val, Address);
795 BasicBlock *ExitBB =
S.getExit();
796 BasicBlock *PreEntryBB =
S.getEnteringBlock();
800 for (
auto &
Array :
S.arrays()) {
801 if (
Array->getNumberOfDimensions() != 0)
803 if (
Array->isPHIKind()) {
808 auto PHI = cast<PHINode>(
Array->getBasePtr());
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");
815 int Idx =
PHI->getBasicBlockIndex(PreEntryBB);
819 Value *ScalarValue =
PHI->getIncomingValue(Idx);
825 auto *Inst = dyn_cast<Instruction>(
Array->getBasePtr());
827 if (Inst &&
S.contains(Inst))
834 if (
auto *
PHI = dyn_cast_or_null<PHINode>(Inst))
835 if (!
S.hasSingleExitEdge() &&
PHI->getBasicBlockIndex(ExitBB) >= 0)
844 BasicBlock *ExitBB =
S.getExitingBlock();
846 BasicBlock *MergeBB =
S.getExit();
849 BasicBlock *OptExitBB = *(pred_begin(MergeBB));
850 if (OptExitBB == ExitBB)
851 OptExitBB = *(++pred_begin(MergeBB));
853 Builder.SetInsertPoint(OptExitBB->getTerminator());
854 for (
const auto &EscapeMapping :
EscapeMap) {
857 Instruction *EscapeInst = EscapeMapping.first;
858 const auto &EscapeMappingValue = EscapeMapping.second;
860 auto *ScalarAddr = cast<AllocaInst>(&*EscapeMappingValue.first);
863 Value *EscapeInstReload =
864 Builder.CreateLoad(ScalarAddr->getAllocatedType(), ScalarAddr,
865 EscapeInst->getName() +
".final_reload");
867 Builder.CreateBitOrPointerCast(EscapeInstReload, EscapeInst->getType());
870 PHINode *MergePHI = PHINode::Create(EscapeInst->getType(), 2,
871 EscapeInst->getName() +
".merge");
872 MergePHI->insertBefore(&*MergeBB->getFirstInsertionPt());
875 MergePHI->addIncoming(EscapeInstReload, OptExitBB);
876 MergePHI->addIncoming(EscapeInst, ExitBB);
880 if (
SE.isSCEVable(EscapeInst->getType()))
881 SE.forgetValue(EscapeInst);
884 for (Instruction *EUser : EscapeUsers)
885 EUser->replaceUsesOfWith(EscapeInst, MergePHI);
890 for (
auto &
Array :
S.arrays()) {
892 if (
Array->getNumberOfDimensions() != 0)
895 if (
Array->isPHIKind())
898 auto *Inst = dyn_cast<Instruction>(
Array->getBasePtr());
906 if (!
S.contains(Inst))
914 if (
S.hasSingleExitEdge())
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));
924 Builder.SetInsertPoint(OptExitBB->getTerminator());
926 for (
auto &SAI :
S.arrays()) {
927 auto *Val = SAI->getBasePtr();
933 if (!SAI->isExitPHIKind())
936 PHINode *
PHI = dyn_cast<PHINode>(Val);
940 if (
PHI->getParent() != AfterMergeBB)
943 std::string Name =
PHI->getName().str();
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);
963 if (Stmt.isCopyStmt())
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);
973 llvm_unreachable(
"Unexpected statement type found");
976 for (
const auto &EscapeMapping :
EscapeMap) {
978 for (Instruction *EUser : EscapeUsers) {
979 if (Loop *L =
LI.getLoopFor(EUser->getParent()))
982 L = L->getParentLoop();
997 BasicBlock *BBCopy) {
999 BasicBlock *BBIDom =
DT.getNode(BB)->getIDom()->getBlock();
1000 BasicBlock *BBCopyIDom =
EndBlockMap.lookup(BBIDom);
1003 DT.changeImmediateDominator(BBCopy, BBCopyIDom);
1018 for (
auto ExitingBB : predecessors(R->getExit())) {
1020 if (!R->contains(ExitingBB))
1023 if (!DT.dominates(BB, ExitingBB))
1033 BasicBlock *Common =
nullptr;
1034 for (
auto ExitingBB : predecessors(R->getExit())) {
1036 if (!R->contains(ExitingBB))
1045 Common = DT.findNearestCommonDominator(Common, ExitingBB);
1048 assert(Common && R->contains(Common));
1055 "Only region statements can be copied by the region generator");
1071 BasicBlock *
EntryBB = R->getEntry();
1072 BasicBlock *EntryBBCopy = SplitBlock(
Builder.GetInsertBlock(),
1074 EntryBBCopy->setName(
"polly.stmt." +
EntryBB->getName() +
".entry");
1075 Builder.SetInsertPoint(&EntryBBCopy->front());
1081 for (
auto PI = pred_begin(
EntryBB), PE = pred_end(
EntryBB); PI != PE; ++PI)
1082 if (!R->contains(*PI)) {
1088 std::deque<BasicBlock *> Blocks;
1089 SmallSetVector<BasicBlock *, 8> SeenBlocks;
1093 while (!Blocks.empty()) {
1094 BasicBlock *BB = Blocks.front();
1098 BasicBlock *BBCopy =
splitBB(BB);
1110 InitBBMap = &EntryBBMap;
1111 auto Inserted =
RegionMaps.insert(std::make_pair(BBCopy, *InitBBMap));
1112 ValueMapT &RegionMap = Inserted.first->second;
1115 Builder.SetInsertPoint(&BBCopy->front());
1116 copyBB(Stmt, BB, BBCopy, RegionMap, LTS, IdToAstExp);
1124 addOperandToPHI(Stmt, PHINodePair.first, PHINodePair.second, BB, LTS);
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);
1134 ValueMap.insert(RegionMap.begin(), RegionMap.end());
1138 BasicBlock *ExitBBCopy = SplitBlock(
Builder.GetInsertBlock(),
1140 ExitBBCopy->setName(
"polly.stmt." + R->getExit()->getName() +
".exit");
1146 "Common exit dominator must be within region; at least the entry node "
1148 DT.changeImmediateDominator(ExitBBCopy, ExitDomBBCopy);
1152 for (BasicBlock *BB : SeenBlocks) {
1156 Instruction *TI = BB->getTerminator();
1157 if (isa<UnreachableInst>(TI)) {
1158 while (!BBCopyEnd->empty())
1159 BBCopyEnd->begin()->eraseFromParent();
1160 new UnreachableInst(BBCopyEnd->getContext(), BBCopyEnd);
1164 Instruction *BICopy = BBCopyEnd->getTerminator();
1169 Builder.SetInsertPoint(BICopy);
1171 BICopy->eraseFromParent();
1176 for (BasicBlock *BB : SeenBlocks) {
1177 Loop *L =
LI.getLoopFor(BB);
1178 if (L ==
nullptr || L->getHeader() != BB || !R->contains(L))
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->front());
1188 LoopPHIInc->insertBefore(BBCopy->getTerminator());
1190 for (
auto *PredBB : predecessors(BB)) {
1191 if (!R->contains(PredBB))
1193 if (L->contains(PredBB))
1194 LoopPHI->addIncoming(LoopPHIInc,
EndBlockMap[PredBB]);
1196 LoopPHI->addIncoming(NullVal,
EndBlockMap[PredBB]);
1199 for (
auto *PredBBCopy : predecessors(BBCopy))
1200 if (LoopPHI->getBasicBlockIndex(PredBBCopy) < 0)
1201 LoopPHI->addIncoming(NullVal, PredBBCopy);
1203 LTS[L] =
SE.getUnknown(LoopPHI);
1207 Builder.SetInsertPoint(&*ExitBBCopy->getFirstInsertionPt());
1223 PollyIRBuilder::InsertPointGuard IPGuard(
Builder);
1225 BasicBlock *NewSubregionExit =
Builder.GetInsertBlock();
1229 if (OrigPHI->getParent() != SubR->getExit()) {
1230 BasicBlock *FormerExit = SubR->getExitingBlock();
1235 PHINode *NewPHI = PHINode::Create(OrigPHI->getType(), Incoming.size(),
1236 "polly." + OrigPHI->getName(),
1237 NewSubregionExit->getFirstNonPHIIt());
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->getTerminator());
1250 Value *NewIncomingValue =
1251 getNewValue(*Stmt, OrigIncomingValue, *LocalBBMap, LTS, L);
1252 NewPHI->addIncoming(NewIncomingValue, NewIncomingBlockEnd);
1263 Loop *L =
LI.getLoopFor(Stmt->
getRegion()->getExit());
1267 assert(!Incoming.empty() &&
1268 "PHI WRITEs must have originate from at least one incoming block");
1271 if (Incoming.size() == 1) {
1272 Value *OldVal = Incoming[0].second;
1287 __isl_keep isl_id_to_ast_expr *NewAccesses) {
1289 "Block statements need to use the generateScalarStores() "
1290 "function in the BlockGenerator");
1299 SmallDenseMap<MemoryAccess *, Value *> NewExitScalars;
1301 if (MA->isOriginalArrayKind() || MA->isRead())
1305 NewExitScalars[MA] = NewVal;
1309 if (MA->isOriginalArrayKind() || MA->isRead())
1312 isl::set AccDom = MA->getAccessRelation().domain();
1313 std::string Subject = MA->getId().get_name();
1315 Stmt, AccDom, Subject.c_str(), [&,
this, MA]() {
1316 Value *NewVal = NewExitScalars.lookup(MA);
1317 assert(NewVal &&
"The exit scalar must be determined before");
1318 Value *Address = getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS,
1319 BBMap, NewAccesses);
1320 assert((!isa<Instruction>(NewVal) ||
1321 DT.dominates(cast<Instruction>(NewVal)->getParent(),
1322 Builder.GetInsertBlock())) &&
1323 "Domination violation");
1324 assert((!isa<Instruction>(Address) ||
1325 DT.dominates(cast<Instruction>(Address)->getParent(),
1326 Builder.GetInsertBlock())) &&
1327 "Domination violation");
1328 Builder.CreateStore(NewVal, Address);
1334 PHINode *PHICopy, BasicBlock *IncomingBB,
1335 LoopToScevMapT <S) {
1343 "Bad incoming block for PHI in non-affine region");
1349 "Incoming PHI block did not have a BBMap");
1352 Value *OpCopy =
nullptr;
1355 Value *Op =
PHI->getIncomingValueForBlock(IncomingBB);
1359 auto IP =
Builder.GetInsertPoint();
1360 if (IP->getParent() != BBCopyEnd)
1361 Builder.SetInsertPoint(BBCopyEnd->getTerminator());
1363 if (IP->getParent() != BBCopyEnd)
1370 if (PHICopy->getBasicBlockIndex(BBCopyEnd) >= 0)
1377 assert(OpCopy &&
"Incoming PHI value was not copied properly");
1378 PHICopy->addIncoming(OpCopy, BBCopyEnd);
1383 LoopToScevMapT <S) {
1384 unsigned NumIncoming =
PHI->getNumIncomingValues();
1386 Builder.CreatePHI(
PHI->getType(), NumIncoming,
"polly." +
PHI->getName());
1387 PHICopy->moveBefore(PHICopy->getParent()->getFirstNonPHI());
1388 BBMap[
PHI] = PHICopy;
1390 for (BasicBlock *IncomingBB :
PHI->blocks())
static cl::opt< bool > Aligned("enable-polly-aligned", cl::desc("Assumed aligned memory accesses."), cl::Hidden, cl::cat(PollyCategory))
static bool isDominatingSubregionExit(const DominatorTree &DT, Region *R, BasicBlock *BB)
static BasicBlock * findExitDominator(DominatorTree &DT, Region *R)
static cl::opt< bool, true > DebugPrintingX("polly-codegen-add-debug-printing", cl::desc("Add printf calls that show the values loaded/stored."), cl::location(PollyDebugPrinting), cl::Hidden, cl::cat(PollyCategory))
static std::string getInstName(Value *Val)
static cl::opt< bool > TraceStmts("polly-codegen-trace-stmts", cl::desc("Add printf calls that print the statement being executed"), cl::Hidden, cl::cat(PollyCategory))
static cl::opt< bool > TraceScalars("polly-codegen-trace-scalars", cl::desc("Add printf calls that print the values of all scalar values " "used in a statement. Requires -polly-codegen-trace-stmts."), cl::Hidden, cl::cat(PollyCategory))
llvm::cl::OptionCategory PollyCategory
__isl_give isl_ast_expr * isl_ast_expr_address_of(__isl_take isl_ast_expr *expr)
isl::ast_expr expr_from(isl::pw_aff pa) const
isl::union_map get_schedule() const
isl::ast_build restrict(isl::set set) const
__isl_give isl_ast_expr * copy() const &
__isl_give isl_id * release()
std::string get_name() const
static isl::map from_union_map(isl::union_map umap)
isl::pw_aff at(int pos) const
class size dim(isl::dim type) const
static isl::pw_multi_aff from_map(isl::map map)
boolean is_subset(const isl::set &set2) const
isl::set intersect_params(isl::set params) const
isl::set apply(isl::map map) const
isl::union_map intersect_domain(isl::space space) const
Loop * getLoopForStmt(const ScopStmt &Stmt) const
Get the innermost loop that surrounds the statement Stmt.
EscapeUsersAllocaMapTy & EscapeMap
Map from instructions to their escape users as well as the alloca.
Value * getImplicitAddress(MemoryAccess &Access, Loop *L, LoopToScevMapT <S, ValueMapT &BBMap, __isl_keep isl_id_to_ast_expr *NewAccesses)
Generate the pointer value that is accesses by Access.
DominatorTree & DT
The dominator tree of this function.
BasicBlock * splitBB(BasicBlock *BB)
Split BB to create a new one we can use to clone BB in.
void generateBeginStmtTrace(ScopStmt &Stmt, LoopToScevMapT <S, ValueMapT &BBMap)
When statement tracing is enabled, build the print instructions for printing the current statement in...
Value * trySynthesizeNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap, LoopToScevMapT <S, Loop *L) const
Try to synthesize a new value.
void generateScalarLoads(ScopStmt &Stmt, LoopToScevMapT <S, ValueMapT &BBMap, __isl_keep isl_id_to_ast_expr *NewAccesses)
Generate reload of scalars demoted to memory and needed by Stmt.
AllocaMapTy & ScalarMap
Map to resolve scalar dependences for PHI operands and scalars.
DenseMap< const ScopArrayInfo *, AssertingVH< AllocaInst > > AllocaMapTy
Map types to resolve scalar dependences.
void createExitPHINodeMerges(Scop &S)
Create exit PHI node merges for PHI nodes with more than two edges from inside the scop.
void copyInstScalar(ScopStmt &Stmt, Instruction *Inst, ValueMapT &BBMap, LoopToScevMapT <S)
Value * generateArrayLoad(ScopStmt &Stmt, LoadInst *load, ValueMapT &BBMap, LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses)
Value * buildContainsCondition(ScopStmt &Stmt, const isl::set &Subdomain)
Generate instructions that compute whether one instance of Set is executed.
void finalizeSCoP(Scop &S)
Finalize the code generation for the SCoP S.
void createScalarInitialization(Scop &S)
Initialize the memory of demoted scalars.
SmallVector< Instruction *, 4 > EscapeUserVectorTy
Simple vector of instructions to store escape users.
bool canSyntheziseInStmt(ScopStmt &Stmt, Instruction *Inst)
Helper to determine if Inst can be synthesized in Stmt.
virtual void generateScalarStores(ScopStmt &Stmt, LoopToScevMapT <S, ValueMapT &BBMap, __isl_keep isl_id_to_ast_expr *NewAccesses)
Generate the scalar stores for the given statement.
IslExprBuilder * ExprBuilder
void handleOutsideUsers(const Scop &S, ScopArrayInfo *Array)
Handle users of Array outside the SCoP.
void createScalarFinalization(Scop &S)
Promote the values of demoted scalars after the SCoP.
Value * getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap, LoopToScevMapT <S, Loop *L) const
Get the new version of a value.
ValueMapT & GlobalMap
A map from llvm::Values referenced in the old code to a new set of llvm::Values, which is used to rep...
void findOutsideUsers(Scop &S)
Find scalar statements that have outside users.
void generateArrayStore(ScopStmt &Stmt, StoreInst *store, ValueMapT &BBMap, LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses)
BasicBlock * copyBB(ScopStmt &Stmt, BasicBlock *BB, ValueMapT &BBMap, LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses)
Copy the given basic block.
MapVector< Instruction *, std::pair< AssertingVH< Value >, EscapeUserVectorTy > > EscapeUsersAllocaMapTy
Map type to resolve escaping users for scalar instructions.
virtual void copyPHIInstruction(ScopStmt &, PHINode *, ValueMapT &, LoopToScevMapT &)
Copy a single PHI instruction.
void copyStmt(ScopStmt &Stmt, LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses)
Copy the basic block.
BasicBlock * StartBlock
The first basic block after the RTC.
BasicBlock * EntryBB
The entry block of the current function.
void copyInstruction(ScopStmt &Stmt, Instruction *Inst, ValueMapT &BBMap, LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses)
Copy a single Instruction.
void invalidateScalarEvolution(Scop &S)
Invalidate the scalar evolution expressions for a scop.
BlockGenerator(PollyIRBuilder &Builder, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT, AllocaMapTy &ScalarMap, EscapeUsersAllocaMapTy &EscapeMap, ValueMapT &GlobalMap, IslExprBuilder *ExprBuilder, BasicBlock *StartBlock)
Create a generator for basic blocks.
void removeDeadInstructions(BasicBlock *BB, ValueMapT &BBMap)
Remove dead instructions generated for BB.
Value * generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst, ValueMapT &BBMap, LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses)
Generate the operand address.
Value * getOrCreateAlloca(const MemoryAccess &Access)
Return the alloca for Access.
void generateConditionalExecution(ScopStmt &Stmt, const isl::set &Subdomain, StringRef Subject, const std::function< void()> &GenThenFunc)
Generate code that executes in a subset of Stmt's domain.
LLVM-IR generator for isl_ast_expr[essions].
llvm::Value * create(__isl_take isl_ast_expr *Expr)
Create LLVM-IR for an isl_ast_expr[ession].
Utility proxy to wrap the common members of LoadInst and StoreInst.
llvm::Value * getPointerOperand() const
Represent memory accesses in statements.
const ScopArrayInfo * getLatestScopArrayInfo() const
Get the ScopArrayInfo object for the base address, or the one set by setNewAccessRelation().
bool isAnyPHIKind() const
Old name of isOriginalAnyPHIKind().
bool isLatestArrayKind() const
Whether storage memory is either an custom .s2a/.phiops alloca (false) or an existing pointer into an...
Instruction * getAccessInstruction() const
Return the access instruction of this memory access.
isl::id getId() const
Get identifier for the memory access.
ArrayRef< std::pair< BasicBlock *, Value * > > getIncoming() const
Return the list of possible PHI/ExitPHI values.
ScopStmt * getStatement() const
Get the statement that contains this memory access.
isl::map getAccessRelation() const
Old name of getLatestAccessRelation().
Value * getAccessValue() const
Return the access value of this memory access.
std::pair< PHINode *, PHINode * > PHINodePairTy
Mapping to remember PHI nodes that still need incoming values.
void copyStmt(ScopStmt &Stmt, LoopToScevMapT <S, __isl_keep isl_id_to_ast_expr *IdToAstExp)
Copy the region statement Stmt.
DenseMap< BasicBlock *, SmallVector< PHINodePairTy, 4 > > IncompletePHINodeMap
void addOperandToPHI(ScopStmt &Stmt, PHINode *PHI, PHINode *PHICopy, BasicBlock *IncomingBB, LoopToScevMapT <S)
Add the new operand from the copy of IncomingBB to PHICopy.
void copyPHIInstruction(ScopStmt &Stmt, PHINode *Inst, ValueMapT &BBMap, LoopToScevMapT <S) override
Copy a single PHI instruction.
DenseMap< BasicBlock *, BasicBlock * > EndBlockMap
A map from old to the last new block in the region, that was created to model the old basic block.
Value * getExitScalar(MemoryAccess *MA, LoopToScevMapT <S, ValueMapT &BBMap)
DenseMap< BasicBlock *, BasicBlock * > StartBlockMap
A map from old to the first new block in the region, that was created to model the old basic block.
void generateScalarStores(ScopStmt &Stmt, LoopToScevMapT <S, ValueMapT &BBMAp, __isl_keep isl_id_to_ast_expr *NewAccesses) override
Generate the scalar stores for the given statement.
DenseMap< BasicBlock *, ValueMapT > RegionMaps
The "BBMaps" for the whole region (one for each block).
PHINode * buildExitPHI(MemoryAccess *MA, LoopToScevMapT <S, ValueMapT &BBMap, Loop *L)
Create a PHI that combines the incoming values from all incoming blocks that are in the subregion.
BasicBlock * repairDominance(BasicBlock *BB, BasicBlock *BBCopy)
Repair the dominance tree after we created a copy block for BB.
A class to store information about arrays in the SCoP.
MemoryAccess & getArrayAccessFor(const Instruction *Inst) const
Return the only array access for Inst.
BasicBlock * getEntryBlock() const
Return a BasicBlock from this statement.
const std::vector< Instruction * > & getInstructions() const
bool isBlockStmt() const
Return true if this statement represents a single basic block.
Region * getRegion() const
Get the region represented by this ScopStmt (if any).
bool represents(BasicBlock *BB) const
Return whether this statement represents BB.
iterator_range< std::vector< Instruction * >::const_iterator > insts() const
The range of instructions in this statement.
BasicBlock * getBasicBlock() const
Get the BasicBlock represented by this ScopStmt (if any).
const char * getBaseName() const
isl::ast_build getAstBuild() const
Get the isl AST build.
MemoryAccess * getArrayAccessOrNULLFor(const Instruction *Inst) const
Return the only array access for Inst, if existing.
bool isRegionStmt() const
Return true if this statement represents a whole region.
isl::set getDomain() const
Get the iteration domain of this ScopStmt.
isl::set getContext() const
Get the constraint on parameter of this Scop.
static VirtualUse create(Scop *S, const Use &U, LoopInfo *LI, bool Virtual)
Get a VirtualUse for an llvm::Use.
This file contains the declaration of the PolyhedralInfo class, which will provide an interface to ex...
llvm::Value * expandCodeFor(Scop &S, llvm::ScalarEvolution &SE, const llvm::DataLayout &DL, const char *Name, const llvm::SCEV *E, llvm::Type *Ty, llvm::Instruction *IP, ValueMapT *VMap, llvm::BasicBlock *RTCBB)
Wrapper for SCEVExpander extended to all Polly features.
@ Array
MemoryKind::Array: Models a one or multi-dimensional array.
@ Value
MemoryKind::Value: Models an llvm::Value.
@ PHI
MemoryKind::PHI: Models PHI nodes within the SCoP.
llvm::iota_range< unsigned > rangeIslSize(unsigned Begin, isl::size End)
Check that End is valid and return an iterator from Begin to End.
llvm::IRBuilder< llvm::ConstantFolder, IRInserter > PollyIRBuilder
llvm::DenseMap< llvm::AssertingVH< llvm::Value >, llvm::AssertingVH< llvm::Value > > ValueMapT
Type to remap values.
bool isIgnoredIntrinsic(const llvm::Value *V)
Return true iff V is an intrinsic that we ignore during code generation.
bool canSynthesize(const llvm::Value *V, const Scop &S, llvm::ScalarEvolution *SE, llvm::Loop *Scope)
Check whether a value an be synthesized by the code generator.
static void createCPUPrinter(PollyIRBuilder &Builder, Args... args)
Print a set of LLVM-IR Values or StringRefs via printf.
static bool isPrintable(llvm::Type *Ty)
Return whether an llvm::Value of the type Ty is printable for debugging.
static llvm::Value * getPrintableString(PollyIRBuilder &Builder, llvm::StringRef Str)
Generate a constant string into the builder's llvm::Module which can be passed to createCPUPrinter().
static TupleKindPtr Domain("Domain")