[squeak-dev] Re: here's a curio for compiler mavens...
Igor Stasenko
siguctua at gmail.com
Tue Feb 14 22:55:18 UTC 2012
On 15 February 2012 00:50, Nicolas Cellier
<nicolas.cellier.aka.nice at gmail.com> wrote:
> Le 14 février 2012 23:10, Eliot Miranda <eliot.miranda at gmail.com> a écrit :
>> On Tue, Feb 14, 2012 at 5:30 AM, Nicolas Cellier
>> <nicolas.cellier.aka.nice at gmail.com> 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 <eliot.miranda at gmail.com> 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
>>> > <eliot.miranda at gmail.com>
>>> > 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.
More information about the Squeak-dev
mailing list
|