This is an archive of the discontinued LLVM Phabricator instance.

Use SCEV to avoid inserting some bounds checks.
ClosedPublic

Authored by jgalenson on Jul 20 2018, 8:23 AM.

Details

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.

Diff Detail

Event Timeline

jgalenson created this revision.Jul 20 2018, 8:23 AM

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?

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

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

233

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 marked 2 inline comments as done.

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

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.

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?

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.

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.

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++)?

Yes, something like that.

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 added inline comments.Jul 20 2018, 11:22 AM
test/Instrumentation/BoundsChecking/opt.ll
51

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

jgalenson updated this revision to Diff 156580.Jul 20 2018, 1:16 PM
jgalenson marked an inline comment as done.
This revision is now accepted and ready to land.Jul 23 2018, 12:53 PM
This revision was automatically updated to reflect the committed changes.