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

Sanjoy Das via llvm-dev llvm-dev at lists.llvm.org
Mon Aug 29 14:01:56 PDT 2016

Hi Wei,

Wei Mi via llvm-dev 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. And we need to add complex rules to define SCEV equivalence
 > from CSE perspective. So I think the method provides me one more
 > alternative, but I am not going to persue it right away.

This is a _terrible_ idea, but I'm going to put it on the table
nevertheless: to avoid sinking time into creating new SCEV
expressions, add a tryGetSCEV(Value *V) returns a SCEV expression only
if there is already a SCEV cached for that V.  This is a bad idea
because it allows the state of SCEV's cache to affect optimization,
but we could do this as a last resort.

A somewhat cleaner idea is to allow _seeding_ a createSCEV call with
an existing SCEV expression, with the intent "I'm only looking for
something close to this SCEV expression S, so don't bother continuing
if what you'll return will be very different from S".  Some simple
heuristics for this may not be difficult to implement.

-- Sanjoy

More information about the llvm-dev mailing list