harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Nie, Jiu Tao" <niejiu...@gmail.com>
Subject Is it necessary to improve the current SSA destruction algorithm?
Date Mon, 11 May 2009 10:31:20 GMT

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.

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

In ct.log, the final generated code contains the following fragment:

  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
*	0xe9a19d I298: MOV v2(EBX):I_32,s123(EBP):I_32 
	0xdeadbeef I169: (AD:s125(EDI):I_32) =CopyPseudoInst/MOV
	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
	0xe9a1a5 I124: (ID:s12(EFLGS):U_32) =CMP
	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).

[1] Preston Briggs, Keith D. Cooper, Timothy J. Harvey, L. Taylor 
Simpson. Practical Improvements to the Construction and Destruction of 
28(8), 1{28 (July 1998)

Best Regards,

View raw message