property lists

[Matthew Fluet]

> > Second footnote:  The live variable lists are updated during the simplify
> > phase when I verify that the all of the liveness information is correct.
> > Previously, I hadn't needed to do this, I just assumed that the values
> > filled in in backend.fun were correct.  (Steve and I wrestled with this at
> > the end of the summer when we first added the liveness calculation to
> > backend.fun.  It's correct, although in some cases it overly conservative,
> > claiming that variables are live into a block when they don't need to be.)
> 
> Shoot.  If you let me know where it's still conservative, I'll look into it.

Here's where I found some differences in the liveness calculations.  These
programs were all run with  -detect-overflow false  to avoid all of the
overflow blocks.  Unfortunately, I don't see a common error in these
cases.

regression/real.sml

This one is due to a missed CPS optimization:

fun L_1055(x_14390) = 
    case x_14390 of
      false => L_889
    | true => L_889

In MachineOutput, this became a Switch, which was optimized at translation
to a single jump to L_889.  Thus, x_14390 (which became RI(0)) is no
longer live in.


benchmarks/barnes-hut.sml *

There were a number of differences in the liveness.

Here's the problematic CPS functions:

	    fun L_376(x_17179, x_17180) = 
	       let
		  val x_16282 = Word32_fromInt(x_15515)
		  val x_16283 = Word32_fromInt(x_17175)
		  val x_16284 = Word32_andb(x_16282, x_16283)
		  val x_16279 = MLton_eq(x_16284, global_82)
		  fun L_700() = 
		     let
			val x_16286 = Int_add(x_17179, global_12)
		     in
			x_17180
		     end
		  fun L_699() = 
		     let
			val x_16288 = Int_add(x_17179, global_12)
			val x_16289 = Word32_fromInt(env_126)
			val x_16290 = Word32_fromInt(x_16288)
			val x_16287 = Word32_lt(x_16290, global_79)
			fun L_703(x_16291) = 
			   let
			      val x_16293 = Word32_toIntX(x_16291)
			      fun L_704() = 
				 let
				    val x_16295 = Word32_toIntX(x_16291)
				    val x_16296 = Int_add(x_17180, x_16295)
				    val x_16297 = Int_add(x_17179, global_12)
				 in
				    x_16296
				 end
			      fun L_705() = 
				 raise [global_24]
			      val x_16292 = Int_lt(x_16293, global_9)
			   in
			      case x_16292 of
				false => L_704 | true => L_705
			   end
			fun L_701() = 
			   let
			      val x_16298 = Word32_arshift(x_16289, global_78)
			   in
			      L_703(x_16298)
			   end
			fun L_702() = 
			   let
			      val x_16299 = Word32_arshift(x_16289, x_16290)
			   in
			      L_703(x_16299)
			   end
		     in
			case x_16287 of
			  false => L_701 | true => L_702
		     end
	       in
		  case x_16279 of
		    false => L_699 | true => L_700
	       end

The basic issues seems to be with L_704, where barnes-hut.reg shows that
x_16297 is unused, but x_17179 is assigned to RI(5), and the backend
reports that RI(5) is live into L_704.  This is propagated back and the
backend reports that L_703, L_702, and L_701 all have RI(5) live in. 

The same error occurs with L_700, where x_16289 is unused.


benchmarks/mlyacc.sml

      fun L_7055() = 
	 let
	    val x_72292 = Array_length(data_36)
	    fun L_7056() = 
	       let
		  val x_72293 = Array_sub(data_36, x_65181)
	       in
		  L_5885(x_72293)
	       end
	    fun L_7057() = 
	       raise [global_39]
	    val x_72291 = Int_geu(x_65181, x_72292)
	 in
	    case x_72291 of
	      false => L_7056 | true => L_7057
	 end

The variable x_72292 is assigned to RI(2), which is reported as live
into L_7056.


benchmarks/zern.sml

The CPS is a little bit big for this one, so here's the C backend output:

L_278:
/* live: L_278 [RI(3),RI(4),RI(1),RI(2)] */
	RI(5) = Int_sub(RI(3), 1);
	RI(6) = Int_add(RI(4), 1000000);
L_279:
/* live: L_279 [RI(5),RI(2),RI(1)] */
	RI(6) = Int_lt(RI(5), 0);
	BZ(RI(6), L_280)

Note that RI(4) shouldn't really be live into L_278, because 
RI(6) = Int_add(RI(4), 1000000);
is dead code.

Here's the important part of the CPS:

fun L_279(x_5081, x_5082) = 
 let
   fun L_280() = ... (big function, neither x_5081 nor x_5082 is free) ...
   fun L_281() = 
    L_197(global_9)
   val x_5039 = Int_lt(x_5082, global_3)
 in
   case x_5039 of
    false => L_280 | true => L_281
 end
fun L_277() = L_279(x_5037, x_5036)
fun L_278() = 
 let
  val x_5075 = Int_sub(x_5036, global_5)
  val x_5076 = Int_add(x_5037, global_7)
 in
  L_279(x_5076, x_5075)
 end

The issue seems to be that x_5081 is really useless in L_279, but it
wasn't eliminated by the CPS shrinker.  On the otherhand, the register
allocator established that x_5039 and x_5081 could share the same
pseudo-register.