[SCEV] Support single-cond range check idiom in applyLoopGuards.
authorFlorian Hahn <flo@fhahn.com>
Fri, 25 Jun 2021 08:29:47 +0000 (09:29 +0100)
committerFlorian Hahn <flo@fhahn.com>
Fri, 25 Jun 2021 09:24:40 +0000 (10:24 +0100)
commit6478f3fb78b3e7cddb642dce0f39d5d4a976af1e
tree3644f0808e6155220a33b7b0b25994478d4747aa
parent7206ad04d585fd5300020f883debaef4429e03ee
[SCEV] Support single-cond range check idiom in applyLoopGuards.

This patch extends applyLoopGuards to detect a single-cond range check
idiom that InstCombine generates.

It extends applyLoopGuards to detect conditions of the form
(-C1 + X < C2). InstCombine will create this form when combining two
checks of the form (X u< C2 + C1) and (X >=u C1).

In practice, this enables us to correctly compute a tight trip count
bounds for code as in the function below. InstCombine will fold the
minimum iteration check created by LoopRotate with the user check (< 8).

    void unsigned_check(short *pred, unsigned width) {
        if (width < 8) {
            for (int x = 0; x < width; x++)
                pred[x] = pred[x] * pred[x];
        }
    }

As a consequence, LLVM creates dead vector loops for the code above,
e.g. see https://godbolt.org/z/cb8eTcqET

https://alive2.llvm.org/ce/z/SHHW4d

Reviewed By: nikic

Differential Revision: https://reviews.llvm.org/D104741
llvm/lib/Analysis/ScalarEvolution.cpp
llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll