[LSR] Fix "new use of poison" problem in lsr-term-fold
authorPhilip Reames <preames@rivosinc.com>
Tue, 21 Mar 2023 15:22:18 +0000 (08:22 -0700)
committerPhilip Reames <listmail@philipreames.com>
Tue, 21 Mar 2023 15:23:40 +0000 (08:23 -0700)
commit53e9a5ddc0a2bc983fc7dcf1cd0a108b8f91cd2f
treeec06e716d8db59ddc07d6e78330dab83d132992f
parentb4307437e51d3a400de21de624a1610aee23346b
[LSR] Fix "new use of poison" problem in lsr-term-fold

This models the approach used in LFTR. The short summary is that we need to prove the IV is not dead first, and then we have to either prove the poison flag is valid after the new user or delete it.

There are two key differences between this and LFTR.

First, I allow a non-concrete start to the IV. The goal of LFTR is to canonicalize and IVs with constant starts are canonical, so the very restrictive definition there is mostly okay. Here on the other hand, we're explicitly moving *away* from the canonical form, and thus need to handle non-constant starts.

Second, LFTR bails out instead of removing inbounds on a GEP. This is a pragmatic tradeoff since inbounds is hard to infer and assists aliasing. This pass runs very late, and I think the tradeoff runs the other way.

A different approach we could take for the post-inc check would be to perform a pre-inc check instead of a post-inc check. We would still have to check the pre-inc IV, but that would avoid the need to drop inbounds. Doing the pre-inc check would basically trade killing a whole IV for an extra register move in the loop. I'm open to suggestions on the right approach here.

Note that this analysis is quite expensive compile time wise. I have made no effort to optimize (yet).

Differential Revision: https://reviews.llvm.org/D146464
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
llvm/test/Transforms/LoopStrengthReduce/lsr-term-fold.ll