[llvm-dev] Request suggestions about how to remove redundencies caused by SCEV expansion fundementally

[Wei Mi via llvm-dev]

On Wed, Aug 24, 2016 at 10:32 AM, Andrew Trick <atrick at apple.com> wrote:
>
> On Aug 24, 2016, at 10:27 AM, Wei Mi <wmi at google.com> wrote:
>
> SCEV is super useful as an analysis without SCEVExpander. The only real
> issue with SCEV itself is invalidating the expressions.
>
> I’ve always thought SCEVExpander is very dangerous to use directly. Ideally
> the SCEV expression should always be reformulated based on existing IR
> values before expanding. It would be nice if that was provided as a layer of
> functionality on top of SCEVExpander.
>
> -Andy
>
>
> Yes, it makes me think that the original idea in D12090 to try to
> reuse the existing value directly may not be the right way to solve
> the problem fundamentally. Reformulating SCEV to make it more
> consistent with cannonical IR form is more promising. If only the IR
> expanded is cannonical compared with existing IR, cleanup pass can
> have big chance to catch the reuse.
>
>
> I was thinking that the SCEV expression should be reformulated in terms of
> opaque nodes for existing IR values before expansion.
>
> -Andy

In D12090, ScalarEvolution::ExprValueMap is used to map a new SCEV to
existing IR values when the SCEV is created by
ScalarEvolution::getSCEV. But a problem is that not all SCEVs are
created via getSCEV. For example, ScalarEvolution::getAddExpr can
create a new SCEV "C" based on two existing SCEVs: "A" and "B".
If A is a SCEVAddExpr itself: "A = A1 + A2", C is formulated as three
operands SCEV: "A1 + A2 + B" without A being an operand. Then it is
impossible to reuse existing IR value recorded for A in ExprValueMap.

Before expansion, it is too late so is difficult to convert C from "A1
+ A2 + B"  back to "A + B" again. If we can afford to record more
information during ScalarEvolution::getAddExpr, we can keep the
information that C is "A + B" towards expansion. But I am not sure it
is an acceptable way -- adding more maps and more complexity.

Thanks,
Wei.