llvm dev - Apr 2018 - InductiveRangeCheckElimination and BranchProbabilityInfo

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

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180409/ee963931/attachment.html>

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/20180410/d0597ee0/attachment.html>

On 04/09/2018 06:06 PM, Sam Parker via llvm-dev 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%.
Human eyes are all-seeing, machinery needs to help itself with tricks. :-)

If you compile this with PGO:
] cat split.c
extern int printf(const char*, ...);
static void do_something(int i) { printf("%d\n", i); }
static void do_something_else(int i) { printf("%d\n", -i); }

void split() {
   for (int i = 0; i < 100; ++i) {
     if (i < 99)
       do_something(i);
     else
       do_something_else(i);
   }
}
int main() {
   split();
}
] clang -fprofile-instr-generate split.c
] ./a.out >/dev/null
] llvm-profdata merge -output=default.profdata default.profraw
] clang -fprofile-instr-use split.c -emit-llvm -S -o - | bin/opt 
-branch-prob -print-bpi

---- Branch Probabilities ----
   edge  ->  probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
   edge  ->  probability is 0x7d83ba68 / 0x80000000 = 98.06% [HOT edge]
   edge  ->  probability is 0x027c4598 / 0x80000000 = 1.94%
   edge  ->  probability is 0x7d7d7d7d / 0x80000000 = 98.04% [HOT edge]
   edge  ->  probability is 0x02828283 / 0x80000000 = 1.96%
   edge  ->  probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
   edge  ->  probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
   edge  ->  probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
   edge  ->  probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
---- Branch Probabilities ----
---- Branch Probabilities ----
---- Branch Probabilities ----
]

See how it manages to find two cold edges instead of one.

regards,
   Fedor.
>
> 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
>
> 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
> http://lists.llvm.org/cgi-bin/mailman/listinfo/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>