Pliant talk forum

Pliant talk forum

Discussion: constant optimization

There is a difference between a constant result and
a sequence of instructions having no side effect.
Message posted by pom on 2002/05/16 08:59:55
Optimizing constant mainly consists in removing code having no side effect
and constant result.
When the code has some side effect, it might be "sorted" into a removable and
a non removable part.

Moreover, (e constant X) is ambiguous. It actually means that e may be reduced
to a constant of type X, not that e has a constant result of type X.
Both aspects could have their own importance.
For instance: 
if cond
  expr1
else
  expr2

we know that if cond is a constant of type Bool equal to true, the whole if
may be compiled as expr1.
Now, if we only know that cond has a constant result equal to true, the "if"
is equivalent to (cond;expr1) . This last expression is a generalization of
the previous one (equivalent when cond is actually a constant), but handles
well the case where cond has some side effects.
Message posted by maybe Hubert Tonneau on 2002/05/16 09:45:18
> Moreover, (e constant X) is ambiguous. It actually means that e may be reduced
> to a constant of type X, not that e has a constant result of type X.

It's not ambiguous, it's what we truely need.
If a meta expects a constant 'Int', then it should work when let's say '3' is
provided. '3' is 'uInt', not 'Int' so it's important to enable casting.
Message posted by pom on 2002/05/16 09:51:48
That was not this ambiguity I was talking about: it was the fact that the
result of e may be a constant of type X, although (e constant X) will return
null because e has some side effects. For instance (I know you don't like this
kind of construction, but it is small and only here as a sample): if e is
the expression (x:=y; true). Then, e has a constant result which may be casted
to Bool, but has also a side effect. Hence, (e constant Bool)=null.
In this case, the constant value is independent of the side effect code, but
I don't know how to get this value without executing the side effect code.
Message posted by pom on 2002/05/16 10:14:12
I've found at to do it.
What do you think of the following implementation of if ?

meta if e
  strong_definition
  if e:size<2
    return
  var List lcond := new List
  var List lexpr := new List
  # check syntax and extracts conditions and expressions
  var Int i:=0
  part scan_to_else
    if i=e:size-1
      return
    lcond append (addressof e:i)
    lexpr append (addressof e:(i+1))
    i+=2
    if i<e:size-1 
      if not e:i:is_pure_ident
        return
      eif e:i:ident="eif"
        i+=1
        restart scan_to_else
      eif e:i:ident<>"else" or i<>e:size-2
        return
      else
        lexpr append (addressof e:(i+1))
  # build the control
  var Pointer:Arrow ccond :> lcond first
  var Pointer:Arrow cexpr :> lexpr first
  while ccond<>null
    var Link:Expression cond :> ccond map Expression
    var Link:Expression expr :> cexpr map Expression
    if not (cond cast CBool)
      return
    var Pointer:CBool res :> (cond constant CBool) map CBool
    if exists:res or (cond:access .and. access_constant<>0)
      if not exists:res
        cond uncast
        cond compile ?
        e suckup cond  # always add instruction list of cond
        var Link:Expression f :> new Expression
        f value := cond:result:constant
        f near e
        res :> (f constant CBool) map CBool
        if not exists:res
          console "argh!" eol
          return
      if res=true
        expr compile ?
        e suckup expr
        e set_void_result
        return
    else    
      e suckup cond
      var Link:Instruction next :> instruction the_function:'do nothing'
      e add (instruction (the_function 'jump if not' CBool) cond:result jump next)
      expr compile ?
      e suckup expr
      e add next
    ccond :> lcond next ccond
    cexpr :> lexpr next cexpr
  if cexpr<>null
    var Link:Expression expr :> cexpr map Expression
    expr compile ?
    e suckup expr
  e set_void_result
Message posted by maybe Hubert Tonneau on 2002/05/16 10:14:21
> I don't know how to get this value without executing the side effect code.

That's why it should not be considered as constant. What I mean by constant
is that you know the value at compile time.
Message posted by pom on 2002/05/16 10:21:54
> I don't know how to get this value without executing the side effect code
Actually, I could access it by e:result:constant
This should be valid at compile time, as it is the meaning of access_constant.

if e is the expression (x:=y; true) :
(e constant Bool)=null (e has side effects)
e has access_constant and constant value equal to Bool true
to recover a CBool, I have to cast the constant in a spearate expression:

var Link:Expression dummy :> new Expression
dummy value := e:result:constant
dummy near e
if (dummy constant CBool)<>null
  # the CBool value may be accessed through ((dummy constant CBool) map CBool)
Message posted by pom on 2002/05/16 10:30:43
Here is a sample test code for the if:

function toto i
  arg Int i
  var Int j := i
  if (j:=1;false)
    tata
  if (j+=1;true)
    console j eol
  else
    tutu
toto -2

#################

The value printed is 2 (as if no optimzation were made), but neither
'tata' nor 'tutu' is compiled.
Message posted by pom on 2002/05/16 11:18:29
Here is a 'constant_result' method for expression, which do not
need the expression to have no side effect:

method e constant_result t -> a
  arg_rw Expression e; arg Type t; arg Arrow a
  a := null
  if (e constant t)<>null # first try "full" constant
    a := e constant t
    return
  if (e:access .and. access_constant)=0
    return
  var Link:Expression f :> new Expression
  f value := e:result:constant
  f near e
  if (f constant t)=null
    return # no way !
  e uncast  # cast code probably useless, now
  a := f:result:constant
Message posted by pom on 2002/05/16 11:27:58
my "if" was buggy. Here is a fixed implementation with previous method:

meta if e
  strong_definition
  if e:size<2
    return
  var List lcond := new List
  var List lexpr := new List
  # check syntax and extracts conditions and expressions
  var Int i:=0
  part scan_to_else
    if i=e:size-1
      return
    lcond append (addressof e:i)
    lexpr append (addressof e:(i+1))
    i+=2
    if i<e:size-1 
      if not e:i:is_pure_ident
        return
      eif e:i:ident="eif"
        i+=1
        restart scan_to_else
      eif e:i:ident<>"else" or i<>e:size-2
        return
      else
        lexpr append (addressof e:(i+1))
  # build the control
  var Pointer:Arrow ccond :> lcond first
  var Pointer:Arrow cexpr :> lexpr first
  var Link:Instruction end :> instruction the_function:'do nothing'
  while ccond<>null
    var Link:Expression cond :> ccond map Expression
    var Link:Expression expr :> cexpr map Expression
    if not (cond cast CBool)
      return
    var Link:CBool res :> (cond constant_result CBool) map CBool
    if exists:res
        e suckup cond  # always add instruction list of cond
      if res=true
        expr compile ?
        e suckup expr
        e set_void_result
        return
    else    
      e suckup cond
      var Link:Instruction next :> instruction the_function:'do nothing'
      e add (instruction (the_function 'jump if not' CBool) cond:result jump next)
      expr compile ?
      e suckup expr
      e add (instruction (the_function 'jump anyway') jump end)
      e add next
    ccond :> lcond next ccond
    cexpr :> lexpr next cexpr
  if cexpr<>null
    var Link:Expression expr :> cexpr map Expression
    expr compile ?
    e suckup expr
  e add end
  e set_void_result
Message posted by pom on 2002/05/16 11:29:24
My "if" was buggy, here is a fixed implementation with previous method:

meta if e
  strong_definition
  if e:size<2
    return
  var List lcond := new List
  var List lexpr := new List
  # check syntax and extracts conditions and expressions
  var Int i:=0
  part scan_to_else
    if i=e:size-1
      return
    lcond append (addressof e:i)
    lexpr append (addressof e:(i+1))
    i+=2
    if i<e:size-1 
      if not e:i:is_pure_ident
        return
      eif e:i:ident="eif"
        i+=1
        restart scan_to_else
      eif e:i:ident<>"else" or i<>e:size-2
        return
      else
        lexpr append (addressof e:(i+1))
  # build the control
  var Pointer:Arrow ccond :> lcond first
  var Pointer:Arrow cexpr :> lexpr first
  var Link:Instruction end :> instruction the_function:'do nothing'
  while ccond<>null
    var Link:Expression cond :> ccond map Expression
    var Link:Expression expr :> cexpr map Expression
    if not (cond cast CBool)
      return
    var Link:CBool res :> (cond constant_result CBool) map CBool
    if exists:res
      e suckup cond  # always add instruction list of cond
      if res=true
        expr compile ?
        e suckup expr
        e set_void_result
        return
    else    
      e suckup cond
      var Link:Instruction next :> instruction the_function:'do nothing'
      e add (instruction (the_function 'jump if not' CBool) cond:result jump next)
      expr compile ?
      e suckup expr
      e add (instruction (the_function 'jump anyway') jump end)
      e add next
    ccond :> lcond next ccond
    cexpr :> lexpr next cexpr
  if cexpr<>null
    var Link:Expression expr :> cexpr map Expression
    expr compile ?
    e suckup expr
  e add end
  e set_void_result