From ffefff7c2a2390ef085711c5d7a73c084d3edb82 Mon Sep 17 00:00:00 2001 From: Whitney Tsang Date: Thu, 6 Jun 2019 15:12:49 +0000 Subject: [PATCH] [DA] Add an option to control delinearization validity checks Summary: Dependence Analysis performs static checks to confirm validity of delinearization. These checks often fail for 64-bit targets due to type conversions and integer wrapping that prevent simplification of the SCEV expressions. These checks would also fail at compile-time if the lower bound of the loops are compile-time unknown. For example: void foo(int n, int m, int a[][m]) { for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { a[i][j] = a[i+1][j-2]; } } opt -mem2reg -instcombine -indvars -loop-simplify -loop-rotate -inline -pass-remarks=.* -debug-pass=Arguments -da-permissive-validity-checks=false k3.ll -analyze -da will produce the following by default: da analyze - anti [* *|<]! but will produce the following expected dependence vector if the validity checks are disabled: da analyze - consistent anti [1 -2]! This revision will introduce a debug option that will leave the validity checks in place by default, but allow them to be turned off. New tests are added for cases where it cannot be proven at compile-time that the individual subscripts stay in-bound with respect to a particular dimension of an array. These tests enable the option to provide user guarantee that the subscripts do not over/under-flow into other dimensions, thereby producing more accurate dependence vectors. For prior discussion on this topic, leading to this change, please see the following thread: http://lists.llvm.org/pipermail/llvm-dev/2019-May/132372.html Reviewers: Meinersbur, jdoerfert, kbarton, dmgreen, fhahn Reviewed By: Meinersbur, jdoerfert, dmgreen Subscribers: fhahn, hiraditya, javed.absar, llvm-commits, Whitney, etiotto Tag: LLVM Differential Revision: https://reviews.llvm.org/D62610 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@362711 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/DependenceAnalysis.cpp | 29 +++++++++++++++++++---------- 1 file changed, 19 insertions(+), 10 deletions(-) diff --git a/lib/Analysis/DependenceAnalysis.cpp b/lib/Analysis/DependenceAnalysis.cpp index 8337b9b96ea..75f269e84f9 100644 --- a/lib/Analysis/DependenceAnalysis.cpp +++ b/lib/Analysis/DependenceAnalysis.cpp @@ -109,6 +109,14 @@ STATISTIC(BanerjeeSuccesses, "Banerjee successes"); static cl::opt Delinearize("da-delinearize", cl::init(true), cl::Hidden, cl::ZeroOrMore, cl::desc("Try to delinearize array references.")); +static cl::opt DisableDelinearizationChecks( + "da-disable-delinearization-checks", cl::init(false), cl::Hidden, + cl::ZeroOrMore, + cl::desc( + "Disable checks that try to statically verify validity of " + "delinearized subscripts. Enabling this option may result in incorrect " + "dependence vectors for languages that allow the subscript of one " + "dimension to underflow or overflow into another dimension.")); //===----------------------------------------------------------------------===// // basics @@ -3316,19 +3324,20 @@ bool DependenceInfo::tryDelinearize(Instruction *Src, Instruction *Dst, // and dst. // FIXME: It may be better to record these sizes and add them as constraints // to the dependency checks. - for (int i = 1; i < size; ++i) { - if (!isKnownNonNegative(SrcSubscripts[i], SrcPtr)) - return false; + if (!DisableDelinearizationChecks) + for (int i = 1; i < size; ++i) { + if (!isKnownNonNegative(SrcSubscripts[i], SrcPtr)) + return false; - if (!isKnownLessThan(SrcSubscripts[i], Sizes[i - 1])) - return false; + if (!isKnownLessThan(SrcSubscripts[i], Sizes[i - 1])) + return false; - if (!isKnownNonNegative(DstSubscripts[i], DstPtr)) - return false; + if (!isKnownNonNegative(DstSubscripts[i], DstPtr)) + return false; - if (!isKnownLessThan(DstSubscripts[i], Sizes[i - 1])) - return false; - } + if (!isKnownLessThan(DstSubscripts[i], Sizes[i - 1])) + return false; + } LLVM_DEBUG({ dbgs() << "\nSrcSubscripts: "; -- 2.40.0