[llvm-dev] InductiveRangeCheckElimination and BranchProbabilityInfo

[Fedor Sergeev via llvm-dev]

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