[llvm-dev] InductiveRangeCheckElimination and BranchProbabilityInfo

[Maxim Kazantsev via llvm-dev]

Hi Sam,

I think BPI for this optimization is not an -enabling- factor, it is only used in a profitability heuristic. Reliance on that can be turned off by setting the flag irce-skip-profitability-checks to true. If you are using it in some static compiler without profiles available, it is very reasonable to set this flag. Personally I have been looking at this heuristic long ago and also did not clearly understand its purpose, the best guess I have is that because IRCE duplicates loops, we want to restrain it from doing that to every loop it sees.

As for extending the BPI, I'm not an expert in that area, but I think that in practice in most cases we just iterate to some N (which is, for example, a length of some array or size of some container) and also make range checks against some N1, N2, N3, for which we either know nothing or just know that they are non-negative. It is impossible to say whether I in [0..N] is likely to be greater or less than some N1 if you only know that N and N1 are non-negative. So I'm not sure if what you propose will have real impact.

Thanks,
Max

From: Daniel Neilson
Sent: Tuesday, April 10, 2018 8:00 PM
To: Sam Parker <Sam.Parker at arm.com>
Cc: llvm-dev at lists.llvm.org; junbuml at codeaurora.org; Maxim Kazantsev <max.kazantsev at azul.com>
Subject: Re: [llvm-dev] InductiveRangeCheckElimination and BranchProbabilityInfo

Adding Maxim


On Apr 9, 2018, at 10:06 AM, Sam Parker via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:

Hi,

extractRangeChecksFromBranch uses BranchProbabilityInfo to decide whether its worth trying the InductiveRangeCheckElimination transformation. For the following example:

void split() {
  for (int i = 0; i < 100; ++i) {
    if (i < 99)
      do_something()
    else
      do_something_else()
  }
}

But the reported BPI is reported as 50/50 to whether do_something will be called, but we can see with our human eyes that this should be 99%.

So two questions:
- why is BPI used to enable the transformation?
- would it not be more useful for BPI to use something like inductive range analyis to calculate the probability? And if so, what else could make use of it? To me, InductiveRangeCheckElimination feels like it should be separated out into an analysis and the transformation.
- or have I misunderstood how and what BPI does?

Thanks,
sam

Sam Parker
Compilation Tools Engineer | Arm
. . . . . . . . . . . . . . . . . . . . . . . . . . .
Arm.com<http://arm.com/>
IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you. _______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180411/d9bbe21f/attachment.html>