Re[3]: factorial: let's get ahead of jhc! :)

[Bulat Ziganshin]

Hello Bulat,

Friday, February 24, 2006, 6:37:42 PM, you wrote:

SPJ Perhaps you may consider doing this transformation on the C-- data type
SPJ only, without involving the (already very complicated) STG - C-- code
SPJ generator?

i have found my investiations in this area. that is the C-- code
generated for fac worker:

Fac_zdwfac_entry() {
c1C0:
_s1BD = I32[Sp + 0];
if (_s1BD != 1) goto c1C4;
R1 = I32[Sp + 4];
Sp = Sp + 8;
jump (I32[Sp + 0]);
c1C4:
_s1BI = _s1BD * I32[Sp + 4];
_s1BF = _s1BD - 1;
I32[Sp + 4] = _s1BI;
I32[Sp + 0] = _s1BF;
jump c1C0;
}

first, we convert jump to the explicit loop:

_s1BD = I32[Sp + 0];
while (_s1BD != 1) {
_s1BI = _s1BD * I32[Sp + 4];
_s1BF = _s1BD - 1;
I32[Sp + 4] = _s1BI;
I32[Sp + 0] = _s1BF;
_s1BD = I32[Sp + 0];
}
R1 = I32[Sp + 4];
Sp = Sp + 8;
jump (I32[Sp + 0]);

then, we cache contents of sp[*] variables in the local ones:

sp4 = I32[Sp + 4];
sp0 = I32[Sp + 0];
_s1BD = sp0;
while (_s1BD != 1) {
_s1BI = _s1BD * sp4;
_s1BF = _s1BD - 1;
sp4 = _s1BI;
sp0 = _s1BF;
_s1BD = sp0;
}
I32[Sp + 4] = sp4;
I32[Sp + 0] = sp0;
R1 = I32[Sp + 4];
Sp = Sp + 8;
jump (I32[Sp + 0]);

and then we wipe out all the superfluous variables:

sp4 = I32[Sp + 4];
sp0 = I32[Sp + 0];
while (sp0 != 1) {
sp4 = sp0 * sp4;
sp0 = sp0 - 1;
}
R1 = sp4;
Sp = Sp + 8;
jump (I32[Sp + 0]);

and it is even for simple fac() function!!! instead of straightforward
generation of code that we need we should make all these nontrivial
studying and hard transformations on already generated code. on the
other side, we can just generate the following code right from the
STG:

int fac () {
sp4 = I32[Sp + 4];
sp0 = I32[Sp + 0];
while (sp0 != 1) {
sp4 = sp0 * sp4;
sp0 = sp0 - 1;
}
R1 = sp4;
Sp = Sp + 8;
jump (I32[Sp + 0]);
}

i think that my way is 100x simpler

-- 
Best regards,
 Bulatmailto:[EMAIL PROTECTED]

___
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

RE: Re[3]: factorial: let's get ahead of jhc! :)

[Simon Peyton-Jones]

| i have found my investiations in this area. that is the C-- code
| generated for fac worker:
| 
| Fac_zdwfac_entry() {
| c1C0:
| _s1BD = I32[Sp + 0];
| if (_s1BD != 1) goto c1C4;
| R1 = I32[Sp + 4];
| Sp = Sp + 8;
| jump (I32[Sp + 0]);
| c1C4:
| _s1BI = _s1BD * I32[Sp + 4];
| _s1BF = _s1BD - 1;
| I32[Sp + 4] = _s1BI;
| I32[Sp + 0] = _s1BF;
| jump c1C0;
| }

Once we do the A/B split of the code generator that I referred to, we
should get something like this from the A part

fac(n,m) {
  if n!=1 goto L
  return(m)
L: jump fac( n-1, n*m ) 
}

The B part will introduce the Sp nonsense.

I think you'll find this a much easier optimisation target.

Simon
-users
___
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users