On Sun, Aug 06, 2017 at 07:01:29PM -0400, Christopher Li wrote:
> On Sun, Aug 6, 2017 at 4:26 PM, Luc Van Oostenryck
> <luc.vanoostenryck@xxxxxxxxx> wrote:
> > Since it seems to be some interest on the subject and
> > to avoid duplicated work, here is a rewrite of sparse's
> > construction of the SSA form.
> >
> > It's not using one of the classical algorithm but is
> > using something newer, simpler and often faster.
> > It's main advantage beyond the simplicity is that you don't
> > need to first build the whole CFG & linearized code to
> > to directly throw it away (or heavily transform it) as
> > it builds the SSA form directly during the linearization.
>
> OK, great.
>
> May I ask the question that, the SSA form you are building
> from this codes. Does it violate the SSA dominance property
Of course not. Unless there is a bug, that is.
> In other word, does it produce the "usage before
> define" IR similar to this?
>
> and.32 %r3 <- %r4, $-65
> or.32 %r4 <- %r3, $64
It gives the code as I showed as reply to Dibyendu's mail.
For example, his code gives:
foo:
.L0:
<entry-point>
and.32 %r2 <- UNDEF, $-65
or.32 %r3 <- %r2, $64
lsr.32 %r4 <- %r3, $6
cast.1 %r5 <- (32) %r4
cast.32 %r6 <- (1) %r5
setne.32 %r7 <- %r6, $1
ret.32 %r7
with UNDEF being a new type of pseudo.
On purpose, nothing is done yet with the UNDEFs.
> That I am very curios how it was done. See the above
> question.
IMO, the best is to read the article. My code is
still very close to the article's pseudo-code.
Basically, it's a lazy approach. Things are done
when possible and are delayed if not.
More specifically, you can do what is needed in a BB
once you have all the parents, otherwise you need to
delay things. The article call this 'BB is sealed'
and there is a 'seal' operation that need to be called
to process what was delayed.
Complications arise with gotos (and the article doesn't
talk about them) but I've added a solution for it
(but I would like to return to it later).
>From what I've seen/heard this algo have been pretty well
received. Personnaly, I'm very happy with its simplicity
and its result.
One thing that is missing is the more complex cases
with trivial phi-nodes.
Another thing I would like to change is the ptrmap
implementation I've added: it need to be hash-table based
(but it's only an implementation detail that matters
for performance on really big functions).
-- Luc
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
