[LLVMdev] SCEV update problem

[Shuxin Yang]

Hi,

   We come across a ScalarEvolution (SE) problem the other day. It seems to
be a fundamental design problem. I don't think I have a clean and cheap 
fix to
this problem. I talked with Andy in the phone yesterday, he told me it is a
known fundamental problem. But I don't see any discussion on this 
problem on the
list, so I post the problem here, soliciting your insightful comment.

  Tons thanks in advance!

Shuxin


   I don't know for sure if I can post the reduced *.ll (2k+ lines) to
the list. Let me try my best to describe this problem without  *.ll.

   Let me start from 5k feet high.
==================================
   The relevant aspect of SCEV regarding to the problem are:

   a1) SCEV is *NOT* self-contained.
       At least SCEVUnknown points to an llvm::Instruction.

   a2) SCEV must be in sync with IR.

         One way to sync them is to delete invalidate SCEV, and force SE 
to recompute
      based on most recent IR. SCEVUnknonw is invalidated if its 
corresponding
       llvm::Instruction is deleted. However, it dose not invalidate 
those SCEVs that
       depends on it as well.

   a3) SCEV is hierarchically structured.

       So, if a SCEVUnknown is invalidated, the compiler needs to figure 
out who depends
       on this invalidated SCEVUnknown, and invalidate them accordingly.

  To enforce the consistency between SCEV and IR, currently compiler:
    ec1) Reset SCEVUnknown::ThePtr via callback function if the Instruciton
         corresponding to the SCEVUnknown in question.

    ec2) it is up to the optimizer, which change the IR, update the SCEV
         at once.

  However, there are flaws:
    ec1.f):
      for ec1), it only invalidate an SCEVUnknown. The SCEVs that depends on
      this SCEVUnknown are not autotmatically invalidated.

    ec2.f1)
      for ec2), sometimes optimizer are difficult to (efficiently) 
figure out
      which SCEVs need to be invalidated.

    ec2.f2)
      If the transformation take place in common utility functions, the
      optimizer has no control at all. If we change the utility functions
      to be fully SCEV-aware, we might as well promote SE as essential
      part of IR (Yuck!)

    ec1.f is hard to be fixed with negligible cost, and ec2.f1 and ec2.f2
render it hard to provide even a nasty hack.

Okay, let descend from 5k' down to the ground:-)
================================================

  Let us consider this snippet

   ----------------------
   E1 = ...
   E2 = expression of E1  // sext/zext/trunc or other simple expression 
of E1.
   loop1(...) {
      r1 = phi1(..., E2)
          = r1    // use 1
   }

   loop2(...) {
       r2 = phi2(... r1)
           = r2   // use 2;
  ---------------------

   o. At beginning,  both SCEVs of use1 and use-2 are in the form of
       SCEV(use1) = ... E2 ...
       SCEV(use2) = ... E2 ...

      SE dose not dig into E2 because the relationship between E1 and E2
     is obscured by some instructions.

   o. loop2 is bit dull, and loop1 is more interesting. So, the SCEVs 
corresponding to the expression
      defined in loop1 are invalidated/updated frequently.  On the other 
hand, as optimization progress,
      the compiler now realize that the SCEV(r1) can be represented 
using E1. Now, we have
        SCEV(use1) = ... E1 ...
        SCEV(use2) = ... E2 ...

    o.  LSR redefines phi1, and replace all r1 occurrences, making phi1 
and E2 dead; both
         are deleted.

       However, SCEV(use2) is still "... E2 ...". The only different is that
       the SCEVUnknown corresponding to E2 has its pointer invalidated.

    o. Following loop-pass query SCEV(use2), and try to deference the 
E2, and
       get segmentation fault.