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

[Wei Mi via llvm-dev]

On Mon, Aug 29, 2016 at 12:30 PM, Daniel Berlin <dberlin at dberlin.org> wrote:
>>
>> By the way, to answer Andy's question. I did some experiment using the
>> testcase in PR29065 to see if we regenerate SCEV for existing and
>> expanded IR, whether it will be easier to check equivalence suppose we
>> have SCEV cse rules. The reassociated order of generated SCEVs seems
>> more consistent. For C= A1 + A2 + B above, the SCEV corresponding to
>> A1 + A2 has the same computation sequence with the SCEV corresponding
>> to A (A1, A2 and A are all complex SCEV themselves). However, during
>> expansion, the cost of searching existing IR, convert them to SCEV and
>> see if they are equivalent with the SCEV to be expanded looks
>> expensive.
>
>
> Is this the cost of processing every instruction, or just things that look
> like recurrences?
>

Both: the cost of creating SCEV for every existing instruction + the
cost of searching recursively the elements of SCEV expanded and
comparing each element with SCEV for existing instruction.

> I ask mainly because i'm curious if the cost decreases if you limit this
> part to recurrences, and did something like have VN just take recurrences
> (which are cheap to find as SCC's in the SSA graph), if you have >1
> recurrence, and see if they are SCEVable.
>
> You'd still need to define equivalence, of course.
>