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

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.

Adding Maxim

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. :slight_smile:

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]
---- Branch Probabilities ----
]

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

regards,
 Fedor.

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