Optimisation (macro and/or) in Som v4.0
Beside simple peep hole optimisations such as:
get.a
put.b => mov.b.a
lit.n put.a => mov.a.n
not jf => jt
not jt => jf
lit.0 eqv.x jf => get.x
jt and its family
jmp.x to jmp.y => jmp.y ...
jmp.x to ret => ret
lit.1 jt => jmp (while 1)
There are a complex cascade jumps created by macro expansion of
and/or. Doing a good code optimisation here improve performance
significantly, for example, the 8-queen benchmark. The and/and
optimisation is already done in som v 3.0. However the or/or is
missing. We start the explanation with a simple case first.
:
and a b = if a b else 0
: or a b = if a 1 else b
- and a b
a
jf.1 b jmp.2 <1> lit.0 <2>
- and (and a b) c
<---
and a b ------------->
a jf.1 b jmp.2 <1> lit.0
<2> jf.3 c jmp.4 <3> lit.0 <4>
We recognise the pattern: jf.1
to lit.0 jf.3 => jf.3 ...
because lit.0 jf always jump.
We cannot do anything to jmp.2 to jf.3. If we move jf.3 left then
it will be incorrect when it does not jump. The ideal code is
a
jf.1 b jf.1 c jmp.2 <1> lit.0 <2>
But that require the code generator to be clever. Now the more
difficult case of or/or.
- or a b
a
jf.1 lit.1 jmp.2 <1> b <2>
- or (or a b) c
<-----
or a b ------------>
a jf.1 lit.1 jmp.2 <1> b
<2> jf.3 lit.1 jmp.4 <3> c <4>
Recognising that:
lit.1
jmp.2 to jf.3 lit.1 jmp.4 => lit.1 jmp.4
This requires one look back and three look forwards. Even with
different association the code sequence remains the same.
- or a (or b c)
<----- or b c --------------->
a jf.1 lit.1 jmp.2 <1> b
<2> jf.3 lit.1 jmp.4 <3> c <4>
If the cascade is mixed of and/or.
- and (or a b) c
<------
or a b ----------->
a jf.1 lit.1 jmp.2 <1> b
<2> jf.3 c jmp.4 <3> lit.0 <4>
The optimisable sequence is a difficult one.
lit.1
jmp.2 to jf.3 => jmp.3
Other situation of mixing does not have any new pattern. In
summary, there are 3 cases:
- cascade and: jx
to lit.0 jf.y => jx.y
- cascade or: lit.1 jmp to jf lit.1 jmp.y
=> lit.1 jmp.y
- or with other: lit.1 jmp
to jf <z> => jmp.z
These have been implemented in som v 4.0.
End