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_10.ll =================================================================== --- /dev/null +++ test/ScheduleOptimizer/pattern-matching-based-opts_10.ll @@ -0,0 +1,91 @@ +; RUN: opt %loadPolly -polly-opt-isl -polly-invariant-load-hoisting=true \ +; RUN: -polly-pattern-matching-based-opts=true \ +; RUN: -polly-target-throughput-vector-fma=1 \ +; RUN: -polly-target-latency-vector-fma=1 \ +; RUN: -polly-codegen -polly-target-1st-cache-level-associativity=8 \ +; RUN: -polly-target-2nd-cache-level-associativity=8 \ +; RUN: -polly-target-1st-cache-level-size=32768 \ +; RUN: -polly-target-vector-register-bitwidth=256 \ +; RUN: -polly-target-2nd-cache-level-size=262144 -S < %s \ +; RUN: | FileCheck %s +; +; This test case checks whether Polly generates second level alias metadata +; to distinguish the specific accesses in case of the ublas gemm kernel. +; +; CHECK: %tmp8_p_scalar_ = load double, double* %p_arrayidx.i.i.i, align 8, !alias.scope !13, !noalias !14 +; CHECK: store double %p_add, double* %p_arrayidx.i.i.i, align 8, !alias.scope !13, !noalias !14 +; CHECK: %tmp8_p_scalar_219 = load double, double* %p_arrayidx.i.i.i218, align 8, !alias.scope !15, !noalias !16 +; CHECK: store double %p_add220, double* %p_arrayidx.i.i.i218, align 8, !alias.scope !15, !noalias !16 +; CHECK: %tmp8_p_scalar_240 = load double, double* %p_arrayidx.i.i.i239, align 8, !alias.scope !17, !noalias !18 +; CHECK: store double %p_add241, double* %p_arrayidx.i.i.i239, align 8, !alias.scope !17, !noalias !18 +; CHECK: %tmp8_p_scalar_261 = load double, double* %p_arrayidx.i.i.i260, align 8, !alias.scope !19, !noalias !20 +; CHECK: store double %p_add262, double* %p_arrayidx.i.i.i260, align 8, !alias.scope !19, !noalias !20 +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +%"class.boost::numeric::ublas::matrix" = type { i64, i64, %"class.boost::numeric::ublas::unbounded_array" } +%"class.boost::numeric::ublas::unbounded_array" = type { %"class.std::allocator", i64, double* } +%"class.std::allocator" = type { i8 } + +define void @_Z4gemmRN5boost7numeric5ublas6matrixIdNS1_15basic_row_majorImlEENS1_15unbounded_arrayIdSaIdEEEEES9_S9_dd(%"class.boost::numeric::ublas::matrix"* dereferenceable(40) %C, %"class.boost::numeric::ublas::matrix"* dereferenceable(40) %A, %"class.boost::numeric::ublas::matrix"* dereferenceable(40) %B, double %alpha, double %beta) { +entry: + br label %entry.split + +entry.split: ; preds = %entry + br label %for.cond3.preheader + +for.cond3.preheader: ; preds = %for.cond.cleanup5, %entry.split + %i.040 = phi i64 [ 0, %entry.split ], [ %inc18, %for.cond.cleanup5 ] + br label %for.cond7.preheader + +for.cond.cleanup: ; preds = %for.cond.cleanup5 + ret void + +for.cond7.preheader: ; preds = %for.cond.cleanup9, %for.cond3.preheader + %j.039 = phi i64 [ 0, %for.cond3.preheader ], [ %inc15, %for.cond.cleanup9 ] + br label %for.body10 + +for.cond.cleanup5: ; preds = %for.cond.cleanup9 + %inc18 = add nuw nsw i64 %i.040, 1 + %exitcond53 = icmp ne i64 %inc18, 1024 + br i1 %exitcond53, label %for.cond3.preheader, label %for.cond.cleanup + +for.cond.cleanup9: ; preds = %for.body10 + %inc15 = add nuw nsw i64 %j.039, 1 + %exitcond52 = icmp ne i64 %inc15, 1024 + br i1 %exitcond52, label %for.cond7.preheader, label %for.cond.cleanup5 + +for.body10: ; preds = %for.body10, %for.cond7.preheader + %k.038 = phi i64 [ 0, %for.cond7.preheader ], [ %inc, %for.body10 ] + %size2_.i.i46 = getelementptr inbounds %"class.boost::numeric::ublas::matrix", %"class.boost::numeric::ublas::matrix"* %A, i64 0, i32 1 + %tmp = load i64, i64* %size2_.i.i46, align 8 + %mul.i.i.i47 = mul i64 %tmp, %i.040 + %add.i.i.i48 = add i64 %mul.i.i.i47, %k.038 + %data_.i4.i.i49 = getelementptr inbounds %"class.boost::numeric::ublas::matrix", %"class.boost::numeric::ublas::matrix"* %A, i64 0, i32 2, i32 2 + %tmp1 = load double*, double** %data_.i4.i.i49, align 8 + %arrayidx.i.i.i50 = getelementptr inbounds double, double* %tmp1, i64 %add.i.i.i48 + %tmp2 = load double, double* %arrayidx.i.i.i50, align 8 + %size2_.i.i41 = getelementptr inbounds %"class.boost::numeric::ublas::matrix", %"class.boost::numeric::ublas::matrix"* %B, i64 0, i32 1 + %tmp3 = load i64, i64* %size2_.i.i41, align 8 + %mul.i.i.i42 = mul i64 %tmp3, %k.038 + %add.i.i.i43 = add i64 %mul.i.i.i42, %j.039 + %data_.i4.i.i44 = getelementptr inbounds %"class.boost::numeric::ublas::matrix", %"class.boost::numeric::ublas::matrix"* %B, i64 0, i32 2, i32 2 + %tmp4 = load double*, double** %data_.i4.i.i44, align 8 + %arrayidx.i.i.i45 = getelementptr inbounds double, double* %tmp4, i64 %add.i.i.i43 + %tmp5 = load double, double* %arrayidx.i.i.i45, align 8 + %mul = fmul double %tmp2, %tmp5 + %size2_.i.i = getelementptr inbounds %"class.boost::numeric::ublas::matrix", %"class.boost::numeric::ublas::matrix"* %C, i64 0, i32 1 + %tmp6 = load i64, i64* %size2_.i.i, align 8 + %mul.i.i.i = mul i64 %tmp6, %i.040 + %add.i.i.i = add i64 %mul.i.i.i, %j.039 + %data_.i4.i.i = getelementptr inbounds %"class.boost::numeric::ublas::matrix", %"class.boost::numeric::ublas::matrix"* %C, i64 0, i32 2, i32 2 + %tmp7 = load double*, double** %data_.i4.i.i, align 8 + %arrayidx.i.i.i = getelementptr inbounds double, double* %tmp7, i64 %add.i.i.i + %tmp8 = load double, double* %arrayidx.i.i.i, align 8 + %add = fadd double %mul, %tmp8 + store double %add, double* %arrayidx.i.i.i, align 8 + %inc = add nuw nsw i64 %k.038, 1 + %exitcond = icmp ne i64 %inc, 1024 + br i1 %exitcond, label %for.body10, label %for.cond.cleanup9 +} 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) {