https://github.com/skachkov-sc updated https://github.com/llvm/llvm-project/pull/140721
>From 64a329ce099a2db1e5404a461069a7ce6827f57b Mon Sep 17 00:00:00 2001 From: Sergey Kachkov <[email protected]> Date: Thu, 23 Jan 2025 16:16:40 +0300 Subject: [PATCH 1/2] [LAA] Add pre-commit test --- .../LoopAccessAnalysis/monotonic-pointers.ll | 86 +++++++++++++++++++ 1 file changed, 86 insertions(+) create mode 100644 llvm/test/Analysis/LoopAccessAnalysis/monotonic-pointers.ll diff --git a/llvm/test/Analysis/LoopAccessAnalysis/monotonic-pointers.ll b/llvm/test/Analysis/LoopAccessAnalysis/monotonic-pointers.ll new file mode 100644 index 0000000000000..b13d79acc5ee4 --- /dev/null +++ b/llvm/test/Analysis/LoopAccessAnalysis/monotonic-pointers.ll @@ -0,0 +1,86 @@ +; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 5 +; RUN: opt -disable-output -passes='print<access-info>' %s 2>&1 | FileCheck %s + +target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128" + +define void @monotonic_ptr_simple(ptr writeonly %dst, ptr readonly %src, i32 %c, i32 %n) { +; CHECK-LABEL: 'monotonic_ptr_simple' +; CHECK-NEXT: for.body: +; CHECK-NEXT: Report: cannot identify array bounds +; CHECK-NEXT: Dependences: +; CHECK-NEXT: Run-time memory checks: +; CHECK-NEXT: Grouped accesses: +; CHECK-EMPTY: +; CHECK-NEXT: Non vectorizable stores to invariant address were not found in loop. +; CHECK-NEXT: SCEV assumptions: +; CHECK-EMPTY: +; CHECK-NEXT: Expressions re-written: +; +entry: + %wide.trip.count = zext nneg i32 %n to i64 + br label %for.body + +for.body: + %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.inc ] + %dst.addr.09 = phi ptr [ %dst, %entry ], [ %dst.addr.1, %for.inc ] + %arrayidx = getelementptr inbounds i32, ptr %src, i64 %indvars.iv + %0 = load i32, ptr %arrayidx, align 4 + %cmp1 = icmp slt i32 %0, %c + br i1 %cmp1, label %if.then, label %for.inc + +if.then: + %incdec.ptr = getelementptr inbounds i8, ptr %dst.addr.09, i64 4 + store i32 %0, ptr %dst.addr.09, align 4 + br label %for.inc + +for.inc: + %dst.addr.1 = phi ptr [ %incdec.ptr, %if.then ], [ %dst.addr.09, %for.body ] + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %exitcond.not = icmp eq i64 %indvars.iv.next, %wide.trip.count + br i1 %exitcond.not, label %exit, label %for.body + +exit: + ret void +} + +define void @monotonic_ptr_indexed(ptr writeonly %dst, ptr readonly %src, i32 %c, i32 %n) { +; CHECK-LABEL: 'monotonic_ptr_indexed' +; CHECK-NEXT: for.body: +; CHECK-NEXT: Report: cannot identify array bounds +; CHECK-NEXT: Dependences: +; CHECK-NEXT: Run-time memory checks: +; CHECK-NEXT: Grouped accesses: +; CHECK-EMPTY: +; CHECK-NEXT: Non vectorizable stores to invariant address were not found in loop. +; CHECK-NEXT: SCEV assumptions: +; CHECK-EMPTY: +; CHECK-NEXT: Expressions re-written: +; +entry: + %wide.trip.count = zext nneg i32 %n to i64 + br label %for.body + +for.body: + %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.inc ] + %idx.012 = phi i32 [ 0, %entry ], [ %idx.1, %for.inc ] + %arrayidx = getelementptr inbounds i32, ptr %src, i64 %indvars.iv + %0 = load i32, ptr %arrayidx, align 4 + %cmp1 = icmp slt i32 %0, %c + br i1 %cmp1, label %if.then, label %for.inc + +if.then: + %inc = add nsw i32 %idx.012, 1 + %idxprom4 = sext i32 %idx.012 to i64 + %arrayidx5 = getelementptr inbounds i32, ptr %dst, i64 %idxprom4 + store i32 %0, ptr %arrayidx5, align 4 + br label %for.inc + +for.inc: + %idx.1 = phi i32 [ %inc, %if.then ], [ %idx.012, %for.body ] + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %exitcond.not = icmp eq i64 %indvars.iv.next, %wide.trip.count + br i1 %exitcond.not, label %exit, label %for.body + +exit: + ret void +} >From 18aa00f7770f0ad79faa649232af57a5c06e407d Mon Sep 17 00:00:00 2001 From: Sergey Kachkov <[email protected]> Date: Wed, 29 Jan 2025 15:28:42 +0300 Subject: [PATCH 2/2] [LAA] Support monotonic pointers in LoopAccessAnalysis --- llvm/lib/Analysis/LoopAccessAnalysis.cpp | 23 +++++++++++++--- .../LoopAccessAnalysis/monotonic-pointers.ll | 26 +++++++++++++++++-- 2 files changed, 43 insertions(+), 6 deletions(-) diff --git a/llvm/lib/Analysis/LoopAccessAnalysis.cpp b/llvm/lib/Analysis/LoopAccessAnalysis.cpp index 5d88e5f54e3d6..4484c03f3b7c7 100644 --- a/llvm/lib/Analysis/LoopAccessAnalysis.cpp +++ b/llvm/lib/Analysis/LoopAccessAnalysis.cpp @@ -25,6 +25,7 @@ #include "llvm/Analysis/AliasSetTracker.h" #include "llvm/Analysis/AssumeBundleQueries.h" #include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/IVDescriptors.h" #include "llvm/Analysis/LoopAnalysisManager.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopIterator.h" @@ -1024,7 +1025,8 @@ static bool isNoWrap(PredicatedScalarEvolution &PSE, const SCEVAddRecExpr *AR, if (AR->getNoWrapFlags(SCEV::NoWrapMask)) return true; - if (Ptr && PSE.hasNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW)) + if (Ptr && isa<SCEVAddRecExpr>(PSE.getSCEV(Ptr)) && + PSE.hasNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW)) return true; // An nusw getelementptr that is an AddRec cannot wrap. If it would wrap, @@ -1256,6 +1258,20 @@ static void findForkedSCEVs( } } +// Conservatively replace SCEV of Ptr value if it can't be computed directly, +// e.g. for monotonic values (they can be treated as affine AddRecs that are +// updated under some predicate). +static const SCEV * +replacePtrSCEV(PredicatedScalarEvolution &PSE, Value *Ptr, + const DenseMap<Value *, const SCEV *> &StridesMap, + const Loop *L) { + ScalarEvolution *SE = PSE.getSE(); + if (MonotonicDescriptor MD; + MonotonicDescriptor::isMonotonicVal(Ptr, L, MD, *SE)) + return MD.getExpr(); + return replaceSymbolicStrideSCEV(PSE, StridesMap, Ptr); +} + bool AccessAnalysis::createCheckForAccess( RuntimePointerChecking &RtCheck, MemAccessInfo Access, Type *AccessTy, const DenseMap<Value *, const SCEV *> &StridesMap, @@ -1282,7 +1298,7 @@ bool AccessAnalysis::createCheckForAccess( for (const auto &[Idx, Q] : enumerate(RTCheckPtrs)) dbgs() << "\t(" << Idx << ") " << *Q.getPointer() << "\n"); } else { - RTCheckPtrs = {{replaceSymbolicStrideSCEV(PSE, StridesMap, Ptr), false}}; + RTCheckPtrs = {{replacePtrSCEV(PSE, Ptr, StridesMap, TheLoop), false}}; } /// Check whether all pointers can participate in a runtime bounds check. They @@ -1301,8 +1317,7 @@ bool AccessAnalysis::createCheckForAccess( // If there's only one option for Ptr, look it up after bounds and wrap // checking, because assumptions might have been added to PSE. if (RTCheckPtrs.size() == 1) { - AR = - cast<SCEVAddRecExpr>(replaceSymbolicStrideSCEV(PSE, StridesMap, Ptr)); + AR = cast<SCEVAddRecExpr>(replacePtrSCEV(PSE, Ptr, StridesMap, TheLoop)); P.setPointer(AR); } diff --git a/llvm/test/Analysis/LoopAccessAnalysis/monotonic-pointers.ll b/llvm/test/Analysis/LoopAccessAnalysis/monotonic-pointers.ll index b13d79acc5ee4..6c91a4e332573 100644 --- a/llvm/test/Analysis/LoopAccessAnalysis/monotonic-pointers.ll +++ b/llvm/test/Analysis/LoopAccessAnalysis/monotonic-pointers.ll @@ -6,10 +6,21 @@ target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128" define void @monotonic_ptr_simple(ptr writeonly %dst, ptr readonly %src, i32 %c, i32 %n) { ; CHECK-LABEL: 'monotonic_ptr_simple' ; CHECK-NEXT: for.body: -; CHECK-NEXT: Report: cannot identify array bounds +; CHECK-NEXT: Memory dependences are safe with run-time checks ; CHECK-NEXT: Dependences: ; CHECK-NEXT: Run-time memory checks: +; CHECK-NEXT: Check 0: +; CHECK-NEXT: Comparing group GRP0: +; CHECK-NEXT: %dst.addr.09 = phi ptr [ %dst, %entry ], [ %dst.addr.1, %for.inc ] +; CHECK-NEXT: Against group GRP1: +; CHECK-NEXT: %arrayidx = getelementptr inbounds i32, ptr %src, i64 %indvars.iv ; CHECK-NEXT: Grouped accesses: +; CHECK-NEXT: Group GRP0: +; CHECK-NEXT: (Low: %dst High: ((4 * (zext i32 %n to i64))<nuw><nsw> + %dst)) +; CHECK-NEXT: Member: {%dst,+,4}<nsw><%for.body> +; CHECK-NEXT: Group GRP1: +; CHECK-NEXT: (Low: %src High: ((4 * (zext i32 %n to i64))<nuw><nsw> + %src)) +; CHECK-NEXT: Member: {%src,+,4}<nuw><%for.body> ; CHECK-EMPTY: ; CHECK-NEXT: Non vectorizable stores to invariant address were not found in loop. ; CHECK-NEXT: SCEV assumptions: @@ -46,10 +57,21 @@ exit: define void @monotonic_ptr_indexed(ptr writeonly %dst, ptr readonly %src, i32 %c, i32 %n) { ; CHECK-LABEL: 'monotonic_ptr_indexed' ; CHECK-NEXT: for.body: -; CHECK-NEXT: Report: cannot identify array bounds +; CHECK-NEXT: Memory dependences are safe with run-time checks ; CHECK-NEXT: Dependences: ; CHECK-NEXT: Run-time memory checks: +; CHECK-NEXT: Check 0: +; CHECK-NEXT: Comparing group GRP0: +; CHECK-NEXT: %arrayidx5 = getelementptr inbounds i32, ptr %dst, i64 %idxprom4 +; CHECK-NEXT: Against group GRP1: +; CHECK-NEXT: %arrayidx = getelementptr inbounds i32, ptr %src, i64 %indvars.iv ; CHECK-NEXT: Grouped accesses: +; CHECK-NEXT: Group GRP0: +; CHECK-NEXT: (Low: %dst High: ((4 * (zext i32 %n to i64))<nuw><nsw> + %dst)) +; CHECK-NEXT: Member: {%dst,+,4}<%for.body> +; CHECK-NEXT: Group GRP1: +; CHECK-NEXT: (Low: %src High: ((4 * (zext i32 %n to i64))<nuw><nsw> + %src)) +; CHECK-NEXT: Member: {%src,+,4}<nuw><%for.body> ; CHECK-EMPTY: ; CHECK-NEXT: Non vectorizable stores to invariant address were not found in loop. ; CHECK-NEXT: SCEV assumptions: _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
