[SCEV] recognize logical and/or pattern
authorJuneyoung Lee <aqjune@gmail.com>
Thu, 31 Dec 2020 19:33:18 +0000 (04:33 +0900)
committerJuneyoung Lee <aqjune@gmail.com>
Thu, 31 Dec 2020 19:37:57 +0000 (04:37 +0900)
commit509fa8e02e25a610574c0fc2cceea1d350c35a66
tree553a2a08ace3d3f2a655c2ab2f3722ab859a4647
parent1a65b8c739a09c587fb55ef4d2d7def13718111c
[SCEV] recognize logical and/or pattern

This patch makes SCEV recognize 'select A, B, false' and 'select A, true, B'.
This is a performance improvement that will be helpful after unsound select -> and/or transformation is removed, as discussed in D93065.

SCEV's answers for the select form should be a bit more conservative than the equivalent `and A, B` / `or A, B`.
Take this example: https://alive2.llvm.org/ce/z/NsP9ue .
To check whether it is valid for SCEV's computeExitLimit to return min(n, m) as ExactNotTaken value, I put llvm.assume at tgt.
It fails because the exit limit becomes poison if n is zero and m is poison. This is problematic if e.g. the exit value of i is replaced with min(n, m).
If either n or m is constant, we can revive the analysis again. I added relevant tests and put alive2 links there.

If and is used instead, this is okay: https://alive2.llvm.org/ce/z/K9rbJk . Hence the existing analysis is sound.

Reviewed By: nikic

Differential Revision: https://reviews.llvm.org/D93882
llvm/include/llvm/Analysis/ScalarEvolution.h
llvm/lib/Analysis/ScalarEvolution.cpp
llvm/test/Analysis/ScalarEvolution/exit-count-select.ll [new file with mode: 0644]
llvm/test/Analysis/ScalarEvolution/trip-count-andor-selectform.ll [new file with mode: 0644]