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.
