Use SCEV to avoid inserting some bounds checks.

[jgalenson]

Summary

This patch uses SCEV to avoid inserting some bounds checks when they are not needed. This slightly improves the performance of code compiled with the bounds check sanitizer.

This approach was suggested in https://reviews.llvm.org/D49492.

[jgalenson]

I'm not very familiar with SCEV, so I'm not sure if I'm making the correct signed vs. unsigned ranges and comparisons here. What is the proper way to do that?

[eugenis]

This looks about right.
Do the tests cover cases where only one or two of the checks can be omitted, but not all of them? Does not look that way.

lib/Transforms/Instrumentation/BoundsChecking.cpp

211 ↗

(On Diff #156492)

Non-legacy pass should request ScalarEvolution from the analysis manager instead of recomputing it.

233 ↗

(On Diff #156492)

Legacy pass should also request SCEV with getAnalysis.

If you were looking at SafeStack, the difference is that SafeStack is added to the pipeline unconditionally and needs to avoid computing SCEV for functions without the attribute, while this pass is only added by the frontend when needed and runs on most functions it sees.

See SafeStack code prior to https://reviews.llvm.org/D31302

[jgalenson]

In D49602#1169952, @eugenis wrote:

Do the tests cover cases where only one or two of the checks can be omitted, but not all of them? Does not look that way.

I'm not quite sure what you mean. The test cases are essentially:

int foo[1000];
for (int i = 0; i < {1000,2000,n}; i++)

foo[i];

and

foo[2][2];
for (int i = 0; i < {2,3,n}; i++)

for (int j = 0; j < {2,3,n}; j++)
  foo[i][j[]

So they do cover the same where you iterate over the whole array and beyond it. I also just added a testcase that counts down to 0 or below 0.

lib/Transforms/Instrumentation/BoundsChecking.cpp

233 ↗

(On Diff #156492)

Thanks! I did in fact copy this code from SafeStack, and it seemed a bit strange. And thanks for the review link to the old code.

[lebedev.ri]

Out of general curiosity, why is this needed?
The optimization passes won't be able to/are not allowed to drop the extra unneeded checks?

[jgalenson]

In D49602#1170059, @lebedev.ri wrote:

Out of general curiosity, why is this needed?
The optimization passes won't be able to/are not allowed to drop the extra unneeded checks?

The goal is to improve the performance of code that uses the bounds checker.

Why can't other passes drop the unneeded checks? Once they're added, they're just comparisons and branches that can be removed if a pass can figure out that the path to a trap will never be taken. That said, the goal of this patch isn't to enable other passes to remove the checks (that was my old approach) but instead not to insert them when they're not needed.

[eugenis]

In D49602#1170033, @jgalenson wrote:

In D49602#1169952, @eugenis wrote:

Do the tests cover cases where only one or two of the checks can be omitted, but not all of them? Does not look that way.

I'm not quite sure what you mean. The test cases are essentially:

int foo[1000];
for (int i = 0; i < {1000,2000,n}; i++)

foo[i];

and

foo[2][2];
for (int i = 0; i < {2,3,n}; i++)

for (int j = 0; j < {2,3,n}; j++)
  foo[i][j[]

So they do cover the same where you iterate over the whole array and beyond it. I also just added a testcase that counts down to 0 or below 0.

Consider a loop where offset is always inbounds, but offset + access size may be not. Bounds checks is still needed, but it should be cheaper, because Size <= Offset will be constant false.

[jgalenson]

In D49602#1170109, @eugenis wrote:

Do the tests cover cases where only one or two of the checks can be omitted, but not all of them? Does not look that way.

Consider a loop where offset is always inbounds, but offset + access size may be not. Bounds checks is still needed, but it should be cheaper, because Size <= Offset will be constant false.

Do you mean something like an off-by-one test, e.g., for (int i = 0; i <= 1000; i++)?

[eugenis]

Yes, something like that.

[jgalenson]

Added a testcase that goes one off the end of the loop counting up (and the previous update added one that counts down one off the end).

[eugenis]

test/Instrumentation/BoundsChecking/opt.ll

50 ↗

(On Diff #156550)

Could you extend the test to show the actual check condition?

[eugenis]

LGTM