harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Vijay Menon <...@google.com>
Subject Re: Is it necessary to improve the current SSA destruction algorithm?
Date Tue, 12 May 2009 18:54:25 GMT
I don't quite see the connection SSA live range overlap and what you are
proposing to do.  If you allow SSA live ranges of the same "var" to overlap,
you typically need *more* copy operations when you de-ssa.  This is because
you now need different operands for what used to be multiple versions of the
same variable.
Getting rid of ldvar and stvar is an orthogonal matter.  It'd be a very
intrusive change as the high-level optimizer assumes that most instructions
(e.g., add) generate unique definitions (operands whose name starts with a
"t").

Either way, I suspect better coalescing in the backend / register allocation
is the answer.

Cheers,

Vijay

p.s., I worked on StarJIT back in the day which evolved into Jitrino & I
have occasionally been lurking on this list.  :-)

2009/5/11 Nie, Jiu Tao <niejiutao@gmail.com>

> Hi,all
>
> I recently digged some source code of Jitrino.OPT and checked its output
> with some simple programs.  I find there are many ldvar/stvar instructions
> in the dumped HIR of SSA form.  They are  essentially copy instructions and
> cannot be eliminated due to the restriction of current SSA destruction
> algorithm, which requires that live ranges of SSA variables shall not
> overlap.  Negatives of some of them can be eliminated by some phases (copy
> propagation on LIR, coalescing of RA etc.), but others, like the following
> example will remain in the final code.  For complex real programs, this
> problem may be more serious (resulting in more unnecessary MOV instructions
> and higher register pressure).  The following example may help to clarify
> this problem.
>
> Test.java:
> public class Test
> {
>    public static void main (String args[])
>    {
>        int i ,sum = 0, n = Integer.parseInt (args[0]);
>        int a[] = new_int (n);
>
>        for (i = 0; i < n; i++)
>            sum = sum + a[i];
>
>        System.out.println ("sum=" + sum);
>    }
>
>    public static int[] new_int (int n)
>    {
>        int a[] = new int[n];
>
>        for (int i = 0; i < n; i++)
>            a[i] = i;
>
>        return a;
>    }
> }
>
> Compiled with OpenJDK-1.6.0
> Harmony revision: 761593
> Command line for Harmony:
> java -Xem:server_static -XX:jit.p.filter=.main -XX:jit.p.arg.log=irdump
> Test
> 100
>
> In ct.log, the final generated code contains the following fragment:
>
> BB_17
>  PersistentId = 46
>  ExecCnt = 8100
>  Loop: Depth=1, !hdr, hdr=BB_16
>  Predcessors: BB_16
>  Successors:  BB_52 [Prob=1e-07](Br=I125) BB_16 [Prob=1](backedge)(Br=I125)
> Layout Succ: BB_52 Block code address: 0xe9a197
> *       0xe9a197 I299: MOV s123(EBP):I_32,v2(EBX):I_32
>        0xe9a199 I85: (ID:s12(EFLGS):U_32) =ADD
> s123(EBP):I_32,t121[v25(EAX)+v0(EDI)*t119(4)+t42(12)]:I_32
> *       0xe9a19d I298: MOV v2(EBX):I_32,s123(EBP):I_32
>        0xdeadbeef I169: (AD:s125(EDI):I_32) =CopyPseudoInst/MOV
> (AU:v0(EDI):I_32)
>        0xe9a19f I87: (ID:s12(EFLGS):U_32) =ADD s125(EDI):I_32,t124(1):I_32
>        0xdeadbeef I88: (AD:v0(EDI):I_32) =CopyPseudoInst/MOV
> (AU:s125(EDI):I_32)
>        0xe9a1a5 I124: (ID:s12(EFLGS):U_32) =CMP
> t206[t203(ESI)+t212(4)]:I_32,t207(0):I_32
>        0xe9a1ac I125: JZ BB_16 t279(-27):I_8 (IU:s12(EFLGS):U_32)
>
> The two MOV instructions marked with '*' are not necessary.  They also
> increase register pressure by one (EBP).  Before hir2lir, the corresponding
> HIR is
>
> Block L49:
>  Predecessors: L50 L74
>  Successors: L3 L50
>  I249:L49: bcmap:unknown
> * I250:ldvar     v5 -) t144:I_32
>  I251:if cge.i4  t144, g16 goto L3
>  GOTO L50
>
> Block L50:
>  Predecessors: L49
>  Successors: L49
>  I252:L50: bcmap:22
>  I253:ldvar     v1 -) t145:I_32
>  I254:taupoint() -) t146:tau
>  I256:addindex  g100, t144 -) t148:ref:I_32
>  I257:ldind.unc:i4  [t148] ((g84,t146)) -) t149:I_32
>  I258:add   t145, t149 -) t150:I_32
>  I259:stvar     t150 -) v1:I_32
>  I261:add   t144, g76 -) t152:I_32
> * I265:stvar     t152 -) v5:I_32
>  GOTO L49
>
> The two lines marked with '*' are the source of the unnecessary MOV
> instructions.  If t152, t144 and v5 are coalesced to one variable, the
> back-end will avoid the problem immediately.  Continue to trace the HIR
> backward, this code is resulted by the restriction of SSA destruction
> algorithm (no live range overlaps).  We can see many ldvar/stvar in all
> phases working on SSA form.
>
> I think we should improve the SSA destruction algorithm according to [1]
>  to
> remove this restriction.  This will enable a more complete copy propagation
> and many other aggressive optimizations.  We can also treat all SSA
> variables equally (able to directly access) rather than treat those derived
> from original variables specially (must access through ldvar/stvar).
>
> Reference:
> [1] Preston Briggs, Keith D. Cooper, Timothy J. Harvey, L. Taylor
> Simpson. Practical Improvements to the Construction and Destruction of
> Static Single Assignment Form. SOFTWARE|PRACTICE AND EXPERIENCE, VOL.
> 28(8), 1{28 (July 1998)
>
> Best Regards,
> Jiutao
>
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message