Index: include/polly/CodeGen/IRBuilder.h =================================================================== --- include/polly/CodeGen/IRBuilder.h +++ include/polly/CodeGen/IRBuilder.h @@ -80,7 +80,20 @@ /// Delete the set of alternative alias bases void resetAlternativeAliasBases() { AlternativeAliasBases.clear(); } + /// Add inter iteration alias-free base pointer @p BasePtr. + void addInterIterationAliasFreeBasePtr(llvm::Value *BasePtr); + private: + /// Annotate with the second level alias metadata + /// + /// Annotate the instruction @p I with the second level alias metadata + /// to distinguish the individual non-aliasing accesses that have inter + /// iteration alias-free base pointers. + /// + /// @param I The instruction to be annotated. + /// @param BasePtr The base pointer of @p I. + void annotateSecondLevel(llvm::Instruction *I, llvm::Value *BasePtr); + /// The ScalarEvolution analysis we use to find base pointers. llvm::ScalarEvolution *SE; @@ -100,6 +113,17 @@ llvm::DenseMap, llvm::MDNode *> OtherAliasScopeListMap; + /// A map from pointers to second level alias scopes. + llvm::DenseMap, llvm::MDNode *> + SecondLevelAliasScopeMap; + + /// A map from pointers to second level alias scope list of other pointers. + llvm::DenseMap, llvm::MDNode *> + SecondLevelOtherAliasScopeListMap; + + /// Inter iteration alias-free base pointers. + llvm::SmallPtrSet InterIterationAliasFreeBasePtrs; + llvm::DenseMap, llvm::AssertingVH> AlternativeAliasBases; }; Index: lib/CodeGen/IRBuilder.cpp =================================================================== --- lib/CodeGen/IRBuilder.cpp +++ lib/CodeGen/IRBuilder.cpp @@ -115,6 +115,49 @@ B->setMetadata("llvm.loop", Id); } +/// Get the pointer operand +/// +/// @param Inst The instruction to be analyzed. +/// @return the pointer operand in case @p Inst is a memory access +/// instruction and nullptr otherwise. +static llvm::Value *getMemAccInstPointerOperand(Instruction *Inst) { + auto MemInst = MemAccInst::dyn_cast(Inst); + if (!MemInst) + return nullptr; + + return MemInst.getPointerOperand(); +} + +void ScopAnnotator::annotateSecondLevel(llvm::Instruction *Inst, + llvm::Value *BasePtr) { + auto *Ptr = getMemAccInstPointerOperand(Inst); + if (!Ptr) + return; + auto SecondLevelAliasScope = SecondLevelAliasScopeMap.lookup(Ptr); + auto SecondLevelOtherAliasScopeList = + SecondLevelOtherAliasScopeListMap.lookup(Ptr); + if (!SecondLevelAliasScope) { + auto AliasScope = AliasScopeMap.lookup(BasePtr); + if (!AliasScope) + return; + LLVMContext &Ctx = SE->getContext(); + SecondLevelAliasScope = getID( + Ctx, AliasScope, MDString::get(Ctx, "second level alias metadata")); + SecondLevelAliasScopeMap[Ptr] = SecondLevelAliasScope; + Metadata *Args = {SecondLevelAliasScope}; + auto SecondLevelBasePtrAliasScopeList = + SecondLevelAliasScopeMap.lookup(BasePtr); + SecondLevelAliasScopeMap[BasePtr] = MDNode::concatenate( + SecondLevelBasePtrAliasScopeList, MDNode::get(Ctx, Args)); + auto OtherAliasScopeList = OtherAliasScopeListMap.lookup(BasePtr); + SecondLevelOtherAliasScopeList = MDNode::concatenate( + OtherAliasScopeList, SecondLevelBasePtrAliasScopeList); + SecondLevelOtherAliasScopeListMap[Ptr] = SecondLevelOtherAliasScopeList; + } + Inst->setMetadata("alias.scope", SecondLevelAliasScope); + Inst->setMetadata("noalias", SecondLevelOtherAliasScopeList); +} + void ScopAnnotator::annotate(Instruction *Inst) { if (!Inst->mayReadOrWriteMemory()) return; @@ -126,11 +169,7 @@ if (!AliasScopeDomain) return; - auto MemInst = MemAccInst::dyn_cast(Inst); - if (!MemInst) - return; - - auto *Ptr = MemInst.getPointerOperand(); + auto *Ptr = getMemAccInstPointerOperand(Inst); if (!Ptr) return; @@ -162,6 +201,18 @@ "BasePtr either expected in AliasScopeMap and OtherAlias...Map"); auto *OtherAliasScopeList = OtherAliasScopeListMap[BasePtr]; + if (InterIterationAliasFreeBasePtrs.count(BasePtr)) { + annotateSecondLevel(Inst, BasePtr); + return; + } + Inst->setMetadata("alias.scope", AliasScope); Inst->setMetadata("noalias", OtherAliasScopeList); } + +void ScopAnnotator::addInterIterationAliasFreeBasePtr(llvm::Value *BasePtr) { + if (!BasePtr) + return; + + InterIterationAliasFreeBasePtrs.insert(BasePtr); +} Index: lib/CodeGen/IslNodeBuilder.cpp =================================================================== --- lib/CodeGen/IslNodeBuilder.cpp +++ lib/CodeGen/IslNodeBuilder.cpp @@ -381,6 +381,10 @@ isl_id_free(Id); return; } + if (!strcmp(isl_id_get_name(Id), "Inter iteration alias-free")) { + auto *BasePtr = static_cast(isl_id_get_user(Id)); + Annotator.addInterIterationAliasFreeBasePtr(BasePtr); + } create(Child); isl_id_free(Id); } Index: lib/Transform/ScheduleOptimizer.cpp =================================================================== --- lib/Transform/ScheduleOptimizer.cpp +++ lib/Transform/ScheduleOptimizer.cpp @@ -1226,10 +1226,26 @@ return Node; } +/// Mark @p BasePtr with "Inter iteration alias-free" mark node. +/// +/// @param Node The child of the mark node to be inserted. +/// @param BasePtr The pointer to be marked. +/// @return The modified isl_schedule_node. +static isl_schedule_node *markInterIterationAliasFree(isl_schedule_node *Node, + llvm::Value *BasePtr) { + if (!BasePtr) + return Node; + + auto *Ctx = isl_schedule_node_get_ctx(Node); + auto *Id = isl_id_alloc(Ctx, "Inter iteration alias-free", BasePtr); + return isl_schedule_node_child(isl_schedule_node_insert_mark(Node, Id), 0); +} + __isl_give isl_schedule_node *ScheduleTreeOptimizer::optimizeMatMulPattern( __isl_take isl_schedule_node *Node, const llvm::TargetTransformInfo *TTI, MatMulInfoTy &MMI) { assert(TTI && "The target transform info should be provided."); + Node = markInterIterationAliasFree(Node, MMI.WriteToC->getLatestBaseAddr()); int DimOutNum = isl_schedule_node_band_n_member(Node); assert(DimOutNum > 2 && "In case of the matrix multiplication the loop nest " "and, consequently, the corresponding scheduling " Index: test/ScheduleOptimizer/mat_mul_pattern_data_layout_2.ll =================================================================== --- test/ScheduleOptimizer/mat_mul_pattern_data_layout_2.ll +++ test/ScheduleOptimizer/mat_mul_pattern_data_layout_2.ll @@ -27,6 +27,7 @@ ; CHECK-NEXT: for (int c3 = 0; c3 <= 31; c3 += 1) ; CHECK-NEXT: Stmt_bb9(32 * c0 + c2, 32 * c1 + c3); ; CHECK-NEXT: } +; CHECK-NEXT: // Inter iteration alias-free ; CHECK-NEXT: // 1st level tiling - Tiles ; CHECK-NEXT: for (int c1 = 0; c1 <= 3; c1 += 1) { ; CHECK-NEXT: for (int c3 = 0; c3 <= 1055; c3 += 1) Index: test/ScheduleOptimizer/pattern-matching-based-opts_3.ll =================================================================== --- test/ScheduleOptimizer/pattern-matching-based-opts_3.ll +++ test/ScheduleOptimizer/pattern-matching-based-opts_3.ll @@ -33,6 +33,7 @@ ; CHECK-NEXT: for (int c3 = 0; c3 <= 31; c3 += 1) ; CHECK-NEXT: Stmt_bb9(32 * c0 + c2, 32 * c1 + c3); ; CHECK-NEXT: } +; CHECK-NEXT: // Inter iteration alias-free ; CHECK-NEXT: // Register tiling - Tiles ; CHECK-NEXT: for (int c0 = 0; c0 <= 131; c0 += 1) ; CHECK-NEXT: for (int c1 = 0; c1 <= 263; c1 += 1) @@ -84,6 +85,7 @@ ; EXTRACTION-OF-MACRO-KERNEL-NEXT: for (int c3 = 0; c3 <= 31; c3 += 1) ; EXTRACTION-OF-MACRO-KERNEL-NEXT: Stmt_bb9(32 * c0 + c2, 32 * c1 + c3); ; EXTRACTION-OF-MACRO-KERNEL-NEXT: } +; EXTRACTION-OF-MACRO-KERNEL-NEXT: // Inter iteration alias-free ; EXTRACTION-OF-MACRO-KERNEL-NEXT: // 1st level tiling - Tiles ; EXTRACTION-OF-MACRO-KERNEL-NEXT: for (int c1 = 0; c1 <= 3; c1 += 1) { ; EXTRACTION-OF-MACRO-KERNEL-NEXT: for (int c3 = 0; c3 <= 1055; c3 += 1) Index: test/ScheduleOptimizer/pattern-matching-based-opts_5.ll =================================================================== --- test/ScheduleOptimizer/pattern-matching-based-opts_5.ll +++ test/ScheduleOptimizer/pattern-matching-based-opts_5.ll @@ -37,6 +37,7 @@ ; C[i][j] += A[i][k] * B[k][j]; ; ; CHECK: if (ni >= 1) { +; CHECK-NEXT: // Inter iteration alias-free ; CHECK-NEXT: // 1st level tiling - Tiles ; CHECK-NEXT: for (int c0 = 0; c0 <= floord(nj - 1, 2048); c0 += 1) ; CHECK-NEXT: for (int c1 = 0; c1 <= floord(nk - 1, 256); c1 += 1) {