here's a curio for compiler mavens...

Ah, I came up with a relatively explicit solution, but also quite
heavy in term of number of messages required to implement the
optimisation.
I'm curious to see your implementation :)

Also, I'm sure that multiple-jump-elimination proposed by Igor and
other kind of optimization would be a perfect subject for proving
concepts of NewCompiler IR infrastructure.

MessageNode>>doesEffectRequiresAPop: encoder
       special > 0
               ifTrue:
                       [^self perform: (MacroTesters at: special) with: encoder].
       ^super doesEffectRequiresAPop: encoder

MessageNode>>doesEffectForIfRequiresAPop: encoder
       "If both branch require a pop instruction, then the pop is factored
after the jump.
       In this case, the translation of this node also require a final pop
that can further be eliminated eventually."
       | thenExpr elseExpr |

       thenExpr := arguments at: 1.
       elseExpr := arguments at: 2.

       ^((thenExpr isJust: NodeNil) or: [elseExpr isJust: NodeNil]) not
               and: [(thenExpr doesEvaluatingEffectRequiresAPop: encoder) and:
[elseExpr doesEvaluatingEffectRequiresAPop: encoder]].

BlockNode>>doesEvaluatingEffectRequiresAPop: anEncoder
       "Test whether a pop instruction is required to skip the value on the
stack when this block is inlined."
       ^statements size > 0 and: [statements last doesEffectRequiresAPop: anEncoder]

AssigmentNode>>doesEffectRequiresAPop: anEncoder
       "Test whether a pop instruction is required to skip the value on the stack"
       ^(variable canStorePopInASingleInstruction: anEncoder) not

InstanceVariableNode>>canStorePopInASingleInstruction: anEncoder
       ^true

etc...

Le 14 février 2012 01:27, Eliot Miranda <[hidden email]> a écrit :

> OK, I fixed this (a pleasant Monday afternoon distraction) (at least I
> *think* I've fixed it; I still have to check the decompiler).  But... in
> doing so I realised I had to fix CompiledMethod>>#= since I needed to see
> exactly which methods the compiler change affected (just committed as
> Kernel-eem.669).  In doing this I noticed that recent compiler changes have
> not been applied by recompiling affected methods in the system.  If you look
> at Behavior>>#sourceMatchesBytecodeAt: it uses CompiledMethod>>#= to check
> that the compiler's output remains unchanged.  In the 4.3 trunk image with
> CompiledMethod>>#= fixed, sourceMatchesBytecodeAt: reports that some 19654
> methods need recompiling:
>
> (SystemNavigation new allSelect: [:m| (m methodClass
> sourceMatchesBytecodeAt: m selector) not]) size 19654
>
> Being selective in recompiling, via e.g.
>
> SystemNavigation new allSelect: [:m| (m methodClass sourceMatchesBytecodeAt:
> m selector) ifFalse: [m methodClass recompile: m selector]. false]
>
> one gets to the desired
>
> (SystemNavigation new allSelect: [:m| (m methodClass
> sourceMatchesBytecodeAt: m selector) not]) size 0
>
> So the question is should we add an update that does the selective
> recompile?  I think we should, e.g. by committing a version of Compiler that
> contains the selective recompile as a post-script.  Agreed?
>
> On Mon, Feb 13, 2012 at 11:58 AM, Eliot Miranda <[hidden email]>
> wrote:
>>
>> Hi All,
>>
>>     (whitewash alert)  I just had occasion to look at the bytecode
>> generated by the standard compiler for HashedCollection
>> class>>#goodPrimeAtLeast:.  Here's the source, with the issue in bold:
>>
>> goodPrimeAtLeast: lowerLimit
>> "Answer the next good prime >= lowerlimit.
>> If lowerLimit is larger than the largest known good prime,
>> just make it odd."
>> | primes low mid high prime |
>> primes := self goodPrimes.
>> low := 1.
>> high := primes size.
>> lowerLimit > (primes at: high) ifTrue: [
>> ^lowerLimit bitOr: 1 ].
>> [ high - low <= 1 ] whileFalse: [
>> mid := high + low // 2.
>> prime := primes at: mid.
>> prime = lowerLimit ifTrue: [ ^prime ].
>> prime < lowerLimit
>> ifTrue: [ low := mid ]
>> ifFalse: [ high := mid ] ].
>> (primes at: low) >= lowerLimit ifTrue: [ ^primes at: low ].
>> ^primes at: high
>>
>> The code for this sequence is
>> 58 <15> pushTemp: 5
>> 59 <10> pushTemp: 0
>> 60 <B2> send: <
>> 61 <9B> jumpFalse: 66
>> 62 <13> pushTemp: 3
>> 63 <81 42> storeIntoTemp: 2
>> 65 <92> jumpTo: 69
>> 66 <13> pushTemp: 3
>> 67 <81 44> storeIntoTemp: 4
>> 69 <87> pop
>>
>> where-as the following would be better:
>>
>> 58 <15> pushTemp: 5
>> 59 <10> pushTemp: 0
>> 60 <B2> send: <
>> 61 <9B> jumpFalse: 66
>> 62 <13> pushTemp: 3
>> 63 <82 42> popIntoTemp: 2
>> 65 <92> jumpTo: 69
>> 66 <13> pushTemp: 3
>> 67 <82 44> popIntoTemp: 4
>>
>> The reason is that the code generator favours using a single pop for both
>> arms of the if:
>>
>> MessageNode>>sizeCodeForIf: encoder value: forValue
>> | thenExpr elseExpr branchSize thenSize elseSize |
>> thenExpr := arguments at: 1.
>> elseExpr := arguments at: 2.
>> (forValue
>> or: [(thenExpr isJust: NodeNil)
>> or: [elseExpr isJust: NodeNil]]) not
>> "(...not ifTrue: avoids using ifFalse: alone during this compile)"
>> ifTrue:  "Two-armed IFs forEffect share a single pop"
>> [^super sizeCodeForEffect: encoder].
>> ...
>>
>> MessageNode>>emitCodeForIf: stack encoder: encoder value: forValue
>> | thenExpr thenSize elseExpr elseSize |
>> thenSize := sizes at: 1.
>> elseSize := sizes at: 2.
>> (forValue not and: [elseSize * thenSize > 0]) ifTrue:
>> "Two-armed IFs forEffect share a single pop"
>> [^super emitCodeForEffect: stack encoder: encoder].
>>
>> It would be nice if this only happened if doing so actually reduced the
>> size of the generated code.
>> --
>> best,
>> Eliot
>>
>
>
>
> --
> best,
> Eliot
>
>
>
>

On 15 February 2012 00:50, Nicolas Cellier

<[hidden email]> wrote:
> Le 14 février 2012 23:10, Eliot Miranda <[hidden email]> a écrit :
>> On Tue, Feb 14, 2012 at 5:30 AM, Nicolas Cellier
>> <[hidden email]> wrote:
>>>
>>> Ah, I came up with a relatively explicit solution, but also quite
>>> heavy in term of number of messages required to implement the
>>> optimisation.
>>> I'm curious to see your implementation :)
>>
>>
>> similar, but should I commit it? I think mine is fine since it is only
>> assignments that have storepop forms, so your generality doesn't win
>> anything.  but i could be wrong.
>>
>
> I was thinking of
>
> 1) nested ifTrue: ifFalse:
> cond1 ifTrue: [x1 := y] ifFalse: [cond2 ifTrue: [x2 := y] ifFalse: [x3 := y]]
>
> elseExpr statements last is a message, not an assignment, though we
> can factor the pop out...
>
> 2) inlined loop messages don't require a final pop...
>
> x <= y ifTrue: [x to: y do: [:i | (self at: i) doSome]] ifFalse: [y
> to: x do: [:i | (self at: i) doSome]].
>
> An encoder pushing a value in both branches just to pop it after
> wouldn't be that well behaved...
>
> I won't give any version publicly because I crashed several images in
> the bootstrap process, and don't know if the bug is in the bootstrap
> or in the code.
>

IMO, too much effort for such diminishing returns. :)

> Nicolas
>
>>  !MessageNode methodsFor: 'code generation' stamp: 'eem 2/13/2012 15:25'!
>> ifThenElseForEffectShouldSharePop
>>         | thenExpr elseExpr |
>>         thenExpr := arguments at: 1.
>>         elseExpr := arguments at: 2.
>>         ^((thenExpr isJust: NodeNil)
>>            or: [(elseExpr isJust: NodeNil)
>>            or: [thenExpr statements last isAssignmentNode
>>                   and: [elseExpr statements last isAssignmentNode]]]) not
>>
>>         "^(thenExpr isJust: NodeNil) not
>>            and: [(elseExpr isJust: NodeNil) not
>>            and: [thenExpr statements last isAssignmentNode not
>>                   or: [elseExpr statements last isAssignmentNode not]]]"! !
>>
>>> Also, I'm sure that multiple-jump-elimination proposed by Igor and
>>> other kind of optimization would be a perfect subject for proving
>>> concepts of NewCompiler IR infrastructure.
>>>
>>> MessageNode>>doesEffectRequiresAPop: encoder
>>>        special > 0
>>>                ifTrue:
>>>                        [^self perform: (MacroTesters at: special) with:
>>> encoder].
>>>        ^super doesEffectRequiresAPop: encoder
>>>
>>> MessageNode>>doesEffectForIfRequiresAPop: encoder
>>>        "If both branch require a pop instruction, then the pop is factored
>>> after the jump.
>>>        In this case, the translation of this node also require a final pop
>>> that can further be eliminated eventually."
>>>        | thenExpr elseExpr |
>>>        thenExpr := arguments at: 1.
>>>        elseExpr := arguments at: 2.
>>>        ^((thenExpr isJust: NodeNil) or: [elseExpr isJust: NodeNil]) not
>>>                and: [(thenExpr doesEvaluatingEffectRequiresAPop: encoder)
>>> and:
>>> [elseExpr doesEvaluatingEffectRequiresAPop: encoder]].
>>>
>>> BlockNode>>doesEvaluatingEffectRequiresAPop: anEncoder
>>>        "Test whether a pop instruction is required to skip the value on
>>> the
>>> stack when this block is inlined."
>>>        ^statements size > 0 and: [statements last doesEffectRequiresAPop:
>>> anEncoder]
>>>
>>> AssigmentNode>>doesEffectRequiresAPop: anEncoder
>>>        "Test whether a pop instruction is required to skip the value on
>>> the stack"
>>>        ^(variable canStorePopInASingleInstruction: anEncoder) not
>>>
>>> InstanceVariableNode>>canStorePopInASingleInstruction: anEncoder
>>>        ^true
>>>
>>> etc...
>>>
>>> Le 14 février 2012 01:27, Eliot Miranda <[hidden email]> a écrit
>>> :
>>> > OK, I fixed this (a pleasant Monday afternoon distraction) (at least I
>>> > *think* I've fixed it; I still have to check the decompiler).  But... in
>>> > doing so I realised I had to fix CompiledMethod>>#= since I needed to
>>> > see
>>> > exactly which methods the compiler change affected (just committed as
>>> > Kernel-eem.669).  In doing this I noticed that recent compiler changes
>>> > have
>>> > not been applied by recompiling affected methods in the system.  If you
>>> > look
>>> > at Behavior>>#sourceMatchesBytecodeAt: it uses CompiledMethod>>#= to
>>> > check
>>> > that the compiler's output remains unchanged.  In the 4.3 trunk image
>>> > with
>>> > CompiledMethod>>#= fixed, sourceMatchesBytecodeAt: reports that
>>> > some 19654
>>> > methods need recompiling:
>>> >
>>> > (SystemNavigation new allSelect: [:m| (m methodClass
>>> > sourceMatchesBytecodeAt: m selector) not]) size 19654
>>> >
>>> > Being selective in recompiling, via e.g.
>>> >
>>> > SystemNavigation new allSelect: [:m| (m methodClass
>>> > sourceMatchesBytecodeAt:
>>> > m selector) ifFalse: [m methodClass recompile: m selector]. false]
>>> >
>>> > one gets to the desired
>>> >
>>> > (SystemNavigation new allSelect: [:m| (m methodClass
>>> > sourceMatchesBytecodeAt: m selector) not]) size 0
>>> >
>>> > So the question is should we add an update that does the selective
>>> > recompile?  I think we should, e.g. by committing a version of Compiler
>>> > that
>>> > contains the selective recompile as a post-script.  Agreed?
>>> >
>>> > On Mon, Feb 13, 2012 at 11:58 AM, Eliot Miranda
>>> > <[hidden email]>
>>> > wrote:
>>> >>
>>> >> Hi All,
>>> >>
>>> >>     (whitewash alert)  I just had occasion to look at the bytecode
>>> >> generated by the standard compiler for HashedCollection
>>> >> class>>#goodPrimeAtLeast:.  Here's the source, with the issue in bold:
>>> >>
>>> >> goodPrimeAtLeast: lowerLimit
>>> >> "Answer the next good prime >= lowerlimit.
>>> >> If lowerLimit is larger than the largest known good prime,
>>> >> just make it odd."
>>> >> | primes low mid high prime |
>>> >> primes := self goodPrimes.
>>> >> low := 1.
>>> >> high := primes size.
>>> >> lowerLimit > (primes at: high) ifTrue: [
>>> >> ^lowerLimit bitOr: 1 ].
>>> >> [ high - low <= 1 ] whileFalse: [
>>> >> mid := high + low // 2.
>>> >> prime := primes at: mid.
>>> >> prime = lowerLimit ifTrue: [ ^prime ].
>>> >> prime < lowerLimit
>>> >> ifTrue: [ low := mid ]
>>> >> ifFalse: [ high := mid ] ].
>>> >> (primes at: low) >= lowerLimit ifTrue: [ ^primes at: low ].
>>> >> ^primes at: high
>>> >>
>>> >> The code for this sequence is
>>> >> 58 <15> pushTemp: 5
>>> >> 59 <10> pushTemp: 0
>>> >> 60 <B2> send: <
>>> >> 61 <9B> jumpFalse: 66
>>> >> 62 <13> pushTemp: 3
>>> >> 63 <81 42> storeIntoTemp: 2
>>> >> 65 <92> jumpTo: 69
>>> >> 66 <13> pushTemp: 3
>>> >> 67 <81 44> storeIntoTemp: 4
>>> >> 69 <87> pop
>>> >>
>>> >> where-as the following would be better:
>>> >>
>>> >> 58 <15> pushTemp: 5
>>> >> 59 <10> pushTemp: 0
>>> >> 60 <B2> send: <
>>> >> 61 <9B> jumpFalse: 66
>>> >> 62 <13> pushTemp: 3
>>> >> 63 <82 42> popIntoTemp: 2
>>> >> 65 <92> jumpTo: 69
>>> >> 66 <13> pushTemp: 3
>>> >> 67 <82 44> popIntoTemp: 4
>>> >>
>>> >> The reason is that the code generator favours using a single pop for
>>> >> both
>>> >> arms of the if:
>>> >>
>>> >> MessageNode>>sizeCodeForIf: encoder value: forValue
>>> >> | thenExpr elseExpr branchSize thenSize elseSize |
>>> >> thenExpr := arguments at: 1.
>>> >> elseExpr := arguments at: 2.
>>> >> (forValue
>>> >> or: [(thenExpr isJust: NodeNil)
>>> >> or: [elseExpr isJust: NodeNil]]) not
>>> >> "(...not ifTrue: avoids using ifFalse: alone during this compile)"
>>> >> ifTrue:  "Two-armed IFs forEffect share a single pop"
>>> >> [^super sizeCodeForEffect: encoder].
>>> >> ...
>>> >>
>>> >> MessageNode>>emitCodeForIf: stack encoder: encoder value: forValue
>>> >> | thenExpr thenSize elseExpr elseSize |
>>> >> thenSize := sizes at: 1.
>>> >> elseSize := sizes at: 2.
>>> >> (forValue not and: [elseSize * thenSize > 0]) ifTrue:
>>> >> "Two-armed IFs forEffect share a single pop"
>>> >> [^super emitCodeForEffect: stack encoder: encoder].
>>> >>
>>> >> It would be nice if this only happened if doing so actually reduced the
>>> >> size of the generated code.
>>> >> --
>>> >> best,
>>> >> Eliot
>>> >>
>>> >
>>> >
>>> >
>>> > --
>>> > best,
>>> > Eliot
>>> >
>>> >
>>> >
>>> >
>>>
>>
>>
>>
>> --
>> best,
>> Eliot
>>
>>
>>
>>
>

--
Best regards,
Igor Stasenko.