TYPE

  VarLabelPair = Var * Label
  VarLabelPairSet = set(VarLabelPair)
  VarLabelPairSetLifted = lift(VarLabelPairSet)


PROBLEM Upwards_Exposed_Uses

  direction  : backward
  carrier    : VarLabelPairSetLifted
  init       : bot
  init_start : lift({})
  combine    : lub


TRANSFER

// NB!  In the following, I make the foolish assumption that I
// must be carefull about local and global variables overshadowing
// and whatnot.  This is not *really* a problem, since they are
// not compared as strings, and so never will occupy the same
// namespace...nevertheless, this doesn't really f*ck anything up,
// so I might as well do it the "safe" way.

  ASSIGN(var, exp) =  
    let entry <= @ in
      // add all variables used in the exp, but remove the var
      // we define here.
      lift((entry - { varlab | varlab in entry; varlab#1 = var })
             lub
	   { (var,label) | var in variables(exp) }
      )

  IF(exp) = 
    let entry <= @ in
      lift (entry lub { (var,label) | var in variables(exp) })

  WHILE(exp) =
    let entry <= @ in
      lift (entry lub { (var,label) | var in variables(exp) })

  RETURN(_, param, exp), local_edge = 
    let entry <= @ in
      // definitions in the proc body should be the valid
      // ones used after the proc, and definitions before the
      // proc should be overwritten.  So the short-cut (the local
      // edge) should only pass the uses of the global var, which
      // will be overshadowed by the local var.    
      lift({varlab | varlab in entry; varlab#1 = param })

  BEGIN(_, param) =
    let entry <= @ in
      // there param is a formal parameter, so it's kinda
      // defined here, ain't it?
      lift(entry - { varlab | varlab in entry; varlab#1 = param })

  END(_, param) =
    let entry <= @ in
      // the param is definitely not used *after* the function
      // so we do not the formal param usage up here.
      lift(entry - { varlab | varlab in entry; varlab#1 = param })

SUPPORT

  subExpressions :: Expression -> ExpressionSet
  subExpressions(expression) =
      case expType(expression) of
        "ARITH_BINARY" => subExpressions(expSubLeft(expression)) lub
                          subExpressions(expSubRight(expression));
        "ARITH_UNARY"  => subExpressions(expSub(expression));
        "BOOL_BINARY"  => subExpressions(expSubLeft(expression)) lub
                          subExpressions(expSubRight(expression));
        "BOOL_UNARY"   => subExpressions(expSub(expression));
        _              => {}; 
      endcase
      + expression

  variables :: Expression -> VarSet
  variables(expression) =
      { expVar(exp) | exp in subExpressions(expression);
                      expType(exp) = "VAR" }