Page MenuHomePhabricator

[IndVars] Fix a miscompile in off-by-default loop predication implementation
ClosedPublic

Authored by reames on Oct 14 2019, 3:21 PM.

Details

Summary

The problem is that we can have two loop exits, 'a' and 'b', where 'a' and 'b' would exit at the same iteration, 'a' precedes 'b' along some path, and 'b' is predicated while 'a' is not. In this case (see the previously submitted test case), we causing the loop to exit through 'b' whereas it should have exited through 'a'.

This only applies to loop exits where the exit counts are inequal, but that isn't as much of a restriction as it appears. If we could order the exit counts, we'd have already removed one of the two exits. In theory, we might be able to prove inequality w/o ordering, but I didn't really explore that piece. Instead, I went for the obvious restriction and ensured we didn't predicate exits following non-predicateable exits.

Credit goes to Evgeny Brevnov for figuring out the problematic case. Fuzzing probably also found it (lots of failures), but due to some silly infrastructure problems I hadn't gotten to the results before Evgeny hand reduced it from a benchmark (he manually enabled the transform). Once this is fixed, I'll try to filter through the fuzzer failures to see if there's anything additional lurking.

Diff Detail

Event Timeline

reames created this revision.Oct 14 2019, 3:21 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 14 2019, 3:21 PM
xbolva00 added inline comments.
lib/Transforms/Scalar/IndVarSimplify.cpp
2811

llvm::sort

2829

e = ExitingBlocks.size()

i < e

ebrevnov added inline comments.Oct 15 2019, 6:27 AM
lib/Transforms/Scalar/IndVarSimplify.cpp
2804

than->then

2825

This is not incorrect but too conservative. If for say last exit we are optimizing has index k, then it's enough to check that exit k dominates all consecutive blocks. Saying that I don't think it will make any difference in practice since back edge taken count won't be computed anyway.

reames updated this revision to Diff 225078.Oct 15 2019, 10:53 AM

Address review comments

reames marked 5 inline comments as done.Oct 15 2019, 10:55 AM
reames added inline comments.
lib/Transforms/Scalar/IndVarSimplify.cpp
2825

Completely agreed. I thought my comment indicated that, do I need to clarify something?

2829

Done, though, this is a micro-optimization at best. And with a decent compiler, not even that.

(It's common and idiomatic in LLVM code, just noting the reason I don't particularly like it for the record)

xbolva00 added inline comments.Oct 15 2019, 11:01 AM
lib/Transforms/Scalar/IndVarSimplify.cpp
2829

Yeah, but we should follow LLVM coding guidelines :)

ebrevnov accepted this revision.Oct 15 2019, 9:35 PM

LGTM

lib/Transforms/Scalar/IndVarSimplify.cpp
2825

After reading comment one more time I think it explains things well enough. Thanks.

This revision is now accepted and ready to land.Oct 15 2019, 9:35 PM
reames closed this revision.Oct 17 2019, 9:17 AM
reames marked an inline comment as done.

This was landed in rL375038. Looks like I got the tagging slightly wrong so the review didn't get auto-closed.