Index: include/polly/CodeGen/IRBuilder.h =================================================================== --- include/polly/CodeGen/IRBuilder.h +++ include/polly/CodeGen/IRBuilder.h @@ -84,6 +84,16 @@ /// Get the base pointer for the instruction @p I. llvm::Value *getBasePointer(llvm::Instruction *Inst); + /// 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 pointer + /// operands marked with "polly.no.inter.iteration.aliasing". + /// + /// @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; @@ -103,6 +113,14 @@ 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; + llvm::DenseMap, llvm::AssertingVH> AlternativeAliasBases; }; Index: lib/CodeGen/BlockGenerators.cpp =================================================================== --- lib/CodeGen/BlockGenerators.cpp +++ lib/CodeGen/BlockGenerators.cpp @@ -170,10 +170,16 @@ ValueMapT &BBMap, LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses) { const MemoryAccess &MA = Stmt.getArrayAccessFor(Inst); - return generateLocationAccessed( - Stmt, getLoopForStmt(Stmt), - Inst.isNull() ? nullptr : Inst.getPointerOperand(), BBMap, LTS, - NewAccesses, MA.getId(), MA.getAccessValue()->getType()); + auto *PointerOperand = Inst.isNull() ? nullptr : Inst.getPointerOperand(); + auto *LocAcc = generateLocationAccessed( + Stmt, getLoopForStmt(Stmt), PointerOperand, BBMap, LTS, NewAccesses, + MA.getId(), MA.getAccessValue()->getType()); + if (auto *PointerOperandInst = dyn_cast(PointerOperand)) + if (auto *NoInterItAliasing = PointerOperandInst->getMetadata( + "polly.no.inter.iteration.aliasing")) + cast(LocAcc)->setMetadata( + "polly.no.inter.iteration.aliasing", NoInterItAliasing); + return LocAcc; } Value *BlockGenerator::generateLocationAccessed( Index: lib/CodeGen/IRBuilder.cpp =================================================================== --- lib/CodeGen/IRBuilder.cpp +++ lib/CodeGen/IRBuilder.cpp @@ -115,12 +115,21 @@ B->setMetadata("llvm.loop", Id); } -llvm::Value *ScopAnnotator::getBasePointer(Instruction *Inst) { +/// 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; - auto *Ptr = MemInst.getPointerOperand(); + return MemInst.getPointerOperand(); +} + +llvm::Value *ScopAnnotator::getBasePointer(Instruction *Inst) { + auto *Ptr = getMemAccInstPointerOperand(Inst); if (!Ptr) return nullptr; @@ -134,6 +143,36 @@ return SU->getValue(); } +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; @@ -171,6 +210,13 @@ "BasePtr either expected in AliasScopeMap and OtherAlias...Map"); auto *OtherAliasScopeList = OtherAliasScopeListMap[BasePtr]; + if (auto *PointerOperandInst = + dyn_cast(getMemAccInstPointerOperand(Inst))) + if (PointerOperandInst->getMetadata("polly.no.inter.iteration.aliasing")) { + annotateSecondLevel(Inst, BasePtr); + return; + } + Inst->setMetadata("alias.scope", AliasScope); Inst->setMetadata("noalias", OtherAliasScopeList); } Index: lib/Transform/ScheduleOptimizer.cpp =================================================================== --- lib/Transform/ScheduleOptimizer.cpp +++ lib/Transform/ScheduleOptimizer.cpp @@ -54,6 +54,7 @@ #include "polly/ScopInfo.h" #include "polly/Support/GICHelper.h" #include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/IR/Metadata.h" #include "llvm/Support/Debug.h" #include "isl/aff.h" #include "isl/band.h" @@ -1226,6 +1227,24 @@ return Node; } +/// Mark the pointer operand of the access to the matrix C +/// +/// Mark the pointer operand of the access to the matrix C with +/// "polly.no.inter.iteration.aliasing" metadata. +/// +/// @param MMI Parameters of the matrix multiplication operands. +static void markAccessToC(MatMulInfoTy &MMI) { + auto MemInst = MemAccInst::dyn_cast(MMI.WriteToC->getAccessInstruction()); + if (!MemInst) + return; + auto *PointerOperand = MemInst.getPointerOperand(); + auto *getElemPtrInst = dyn_cast(PointerOperand); + if (!getElemPtrInst) + return; + auto *EmptyMDNode = MDNode::get(getElemPtrInst->getContext(), None); + getElemPtrInst->setMetadata("polly.no.inter.iteration.aliasing", EmptyMDNode); +} + __isl_give isl_schedule_node *ScheduleTreeOptimizer::optimizeMatMulPattern( __isl_take isl_schedule_node *Node, const llvm::TargetTransformInfo *TTI, MatMulInfoTy &MMI) { @@ -1252,6 +1271,7 @@ if (!MapOldIndVar) return Node; Node = isolateAndUnrollMatMulInnerLoops(Node, MicroKernelParams); + markAccessToC(MMI); return optimizeDataLayoutMatrMulPattern(Node, MapOldIndVar, MicroKernelParams, MacroKernelParams, MMI); } Index: test/ScheduleOptimizer/pattern-matching-based-opts_10.ll =================================================================== --- /dev/null +++ test/ScheduleOptimizer/pattern-matching-based-opts_10.ll @@ -0,0 +1,86 @@ +; 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=8 \ +; 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 +; polly.no.inter.iteration.aliasing along with second level alias metadata +; in case the ublas gemm kernel. +; +; CHECK: !polly.no.inter.iteration.aliasing +; CHECK: !"second level alias metadata" + +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 +}