remove-unused

[Matthew Fluet]

> > or if type checking prevents us from making a non-tail call to
>                                                 ^^^^^^^^
> do you mean tail call?

Yes.

> > non-terminating, non-failing function (i.e., an infinite loop)) or a
> > tail call (if types match up)).
> 
> I am still confused about the fourth clause in the translation of Call.
> 
> 			    | (false, _, _)
> 			    => if Vector.forall
> 			          (returnsFunc f, 
> 				   fn (x, t) => not (isUsedVar x))
> 				 then call NONE
> 				 else call (SOME {cont = getBugContFunc 
> 						         (f, returnsFunc func), 
> 						  handler = NONE}))
> 
> I don't understand why ensuring that this function doesn't return any
> values means that the "types match up".  Don't we also have to check
> that the callee (i.e. func) doesn't return any values?

Yes.  I was almost right.  Here's the transfer for Call:

	     | Call {func, args, return}
	     => let

		in
		  flowVarTysVars(argsFunc func, args);
		  flowSideEffects(func, f);
		  case return
		    of SOME {cont, handler}
		     => (flowVarTysVarTys(argsLabel cont, returnsFunc func);
			 whenTerminatesFunc(func, visitLabelTh cont);
			 case handler
			   of SOME handler 
			    => (whenFailsFunc(func, fn () => catchLabel handler);
				whenFailsFunc(func, visitLabelTh handler))
			    | NONE => flowFails (func, f))
		     | NONE
		     => (flowVarTysVarTys(returnsFunc f, returnsFunc func);
			 flowTerminates(func, f);
			 flowFails(func, f));
		  visitFunc func
		end

If the non-terminating function is only ever non-tail called, then this
works out; we won't visit the return continuation until after we
establish that the called function terminates.  If the called function
doesn't terminate, we never visit the return continuation, we never use
the return continuation's formals, so nothing propagates on the flow from
the cont's formals to the callees returns.  If nothing flows there, then
all of the callee's returns are unused, so when we rewrite the type of the
called function, it will get a nullary return type.

This all flies out the window if the called function is also used in tail
position by some other function that might independently return along a
different control flow path, and whose returned values are used down some
return continuation.

If something like this got back to the ssa IL and removeUnused, it would
break under the current system.

fun main () =
   ...
   if b
     then L1 (f (b'))
     else L1 (g (b'))
   ...
   L1 (x) = ... use x ...

fun f (b') : int = if b'
                     then 1
                     else g (b')

fun g (b') : int = g (b')



Another problem:

fun f b' = if b' then 1 else g b'
and g b' = g b'

fun main () =
   let
     val w = MLton.Random.seed ()
     val _ = print (Word.toString w)
     val b = Word.andb(0wx1, w) = 0wx1
     val b' = Word.andb(0wx2, w) = 0wx2
     fun L1 i = print (Int.toString i)
   in
     if b
       then L1 (f b')
       else L1 (g b')
   end

val _ = main ()

compiled with

mlton -v3 -drop-pass removeUnused1 -drop-pass leafInline -drop-pass
raiseToJump1 -drop-pass contify1 -drop-pass localFlatten1 -drop-pass
useless -drop-pass removeUnused2 -drop-pass unusedArgs1 -drop-pass
simplifyTypes -drop-pass contify2 -drop-pass inline -drop-pass
localFlatten2 -drop-pass removeUnused3 -drop-pass raiseToJump2 -drop-pass
contify3 -drop-pass unusedArgs2 -drop-pass introduceLoops -drop-pass
loopInvariant -drop-pass flatten -drop-pass flatten -drop-pass
localFlatten3 -drop-pass commonSubexp -drop-pass commonBlock -drop-pass
redundantTests -drop-pass redudnant -drop-pass unusedArgs3 -drop-pass
removeUnused4 -keep-pass removeUnused5 -keep ssa -show-types true z.sml

exhibits another bug.  

fun x_17 (env_47: unit, x_545: (pointer * int)): (string) = L_462()
  makes a tail call to x_547
  but x_17's call points never make use of the return value

fun x_547 (env_62: unit, x_668: char array): (string) = L_577()
 is tail called from other functions besides x_17, some of which do make
use of the return value.

So, x_547's return type doesn't change, but x_17's does.

Can I turn x_17's tail call of x_547 into a non-tail call with a
continuation that does nothing but forget the arguments and return?
Essentially, in addition to bugCont we would have returnCont that does
nothing but return the right values and wrappers that coordinate between
callees that return extra stuff.  Nothing is live down the returnCont, so
I don't think there is a safe-for-space issue with introducing a non-tail
call.  We do waste a little space on stack because of the non-tail call.