factorial: let's get ahead of jhc! :)

[Bulat Ziganshin]

Hello Simon,

Friday, February 24, 2006, 7:18:30 PM, you wrote:

>> 1) add for/if/while to the C-- statement types list (data CmmStmt)

SM> Please don't extend the C-- data type - it's very small and simple 
SM> because that makes it easy to manipulate and reason about.

SM> I don't see why you need to, either: you can already express for, if and
SM> while in C-- using conditional branches.  I don't think gcc cares 
SM> whether you write your code using labels and goto or while/for/if, it 
SM> generates the same code either way.

i tested gcc (3.4.2, included in ghc 6.4.1) and my tests show that gcc
unroll loops only when a loop variable modified directly. This loop
unrolls:

loop: ...
      i=i-1;
      if(i>1) goto loop;

and this loop don't unrolls:

loop: ...
      x=i-1;
      i=x;
      if(i>1) goto loop;

but using of while/goto don't matters. i attached fac.c that shows
this - here only fac() and fac3() are unrolled


>> 2) implement recognizer for such simple STG functions (leaf unboxed
>> procedures recognizer)
>> 
>> 3) implement the translation itself

SM> By all means try this.  What you want is to compile recursive functions
SM> like this:

SM>    f() {
SM>     x = arg1;
SM>     y = arg2;
SM>    L:
SM>     ... body of f, with args mapped to x & y,
SM>         and recursive calls jumping to L passing args in x & y.
SM>    }

SM> It's quite hard to do this as a C-- to C-- optimisation, at least 
SM> without implementing a lot of other optimisations that we don't already
SM> have.  I was hoping that gcc would do it for us, if we compile code like
SM> this:

SM>    f() {
SM>    L:
SM>     ... body of f ...
SM>     goto L;
SM>    }

SM> but sadly it doesn't do the whole job.  (see cmmLoopifyForC in 
SM> cmm/CmmOpt.hs, which I added today).

SM> So you might try the hacky way of doing this transformation at a higher
SM> level, when generating the C-- in the first place.  Putting the args in
SM> temporaries is the easy bit; generating different code for the recursive
SM> call will be more tricky.

i just downloaded fresh sources. cmmLoopifyForC may be not what we
need. the whole idea of transformation is to move f() parameters to
local variables, and then update contents of these local variables and
perform `goto` on each recursive call. why cmmLoopifyForC is not good
for this? only because before processing by this function the code
should look like this:

  f() {
   x = arg1;
   y = arg2;
  L:
   ... body of f, with args mapped to x & y,
       x = newarg1;
       y = newarg2
       jump f();
  }

what is just not proper code, especially if x&y is local f()
variables. so to use this function we should start from generating
improper code and anyway we should change STG->C-- code generation


i think that the discussed optimization can be done in another way:

1) in function mkFunEntryCode add check that f() is a "leaf" "unboxed"
function

2) if it's true then replace call to bindArgsToStack with generation
of "x=sp[0]; y=sp[4]; L:" assignments and bind corresponding args to
x&y (instead of binding them to sp[0]/sp[4])

3) in cgTailCall function check that it's a self-recursive call and
in this case generate sequence "x=newarg1; y=newarg2; goto L" instead
of "jump f()". i think that this check will require adding info about
f() to the FCode monad. so, the whole story should look like this:

CgClosure.lhs:
-  ; bindArgsToStack stk_args
+  ; if isLeafUnboxedFunction cl_info body
+      then do local_args <- makeNewLocals (length stk_args)  -- generate x&y locals
+              generateLoads local_args stk_args        -- generate "x=sp[0]; y=sp[4]" assignments
+              lbl <- generateNewLabel                  -- generate "L:"
+              bindStkArgstoLocals local_args stk_args  -- bind arguments to x&y local variables
+              modifyFCodeState (Just cl_info) lbl      -- put in FCode monad state info about
+                                                       --  now-processed leaf function and label
+                                                       --  marking start of its self-recursive cycle
+      else do bindArgsToStack stk_args
+              modifyFCodeState Nothing undefined

CgTailCall.lhs:
-  = do  { fun_info <- getCgIdInfo fun
+  = do  { fun_info <- getCgIdInfo fun
+        ; (optimized_fun, lbl) <- getFromFCodeState    -- optimized_fun/=Nothing only if we
+                                                       --  process "leaf" "unboxed" function

-          else -- Normal case, fun is boxed
+          else if (Just fun == optimized_fun) then
+               do generateAssignments    -- generate "x=newarg1; y=newarg2"
+                  generateGoto lbl       -- generate "goto L"
+          else -- Normal case, fun is boxed

-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com
-------------- next part --------------
A non-text attachment was scrubbed...
Name: fac.c
Type: application/octet-stream
Size: 779 bytes
Desc: not available
Url : http://www.haskell.org//pipermail/glasgow-haskell-users/attachments/20060302/4255e31d/fac.obj