<br><br><div class="gmail_quote">On Tue, Feb 14, 2012 at 2:55 PM, Igor Stasenko <span dir="ltr"><<a href="mailto:siguctua@gmail.com">siguctua@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
On 15 February 2012 00:50, Nicolas Cellier<br>
<div class="im"><<a href="mailto:nicolas.cellier.aka.nice@gmail.com">nicolas.cellier.aka.nice@gmail.com</a>> wrote:<br>
> Le 14 février 2012 23:10, Eliot Miranda <<a href="mailto:eliot.miranda@gmail.com">eliot.miranda@gmail.com</a>> a écrit :<br>
>> On Tue, Feb 14, 2012 at 5:30 AM, Nicolas Cellier<br>
>> <<a href="mailto:nicolas.cellier.aka.nice@gmail.com">nicolas.cellier.aka.nice@gmail.com</a>> wrote:<br>
>>><br>
>>> Ah, I came up with a relatively explicit solution, but also quite<br>
>>> heavy in term of number of messages required to implement the<br>
>>> optimisation.<br>
>>> I'm curious to see your implementation :)<br>
>><br>
>><br>
>> similar, but should I commit it? I think mine is fine since it is only<br>
>> assignments that have storepop forms, so your generality doesn't win<br>
>> anything. but i could be wrong.<br>
>><br>
><br>
> I was thinking of<br>
><br>
> 1) nested ifTrue: ifFalse:<br>
> cond1 ifTrue: [x1 := y] ifFalse: [cond2 ifTrue: [x2 := y] ifFalse: [x3 := y]]<br>
><br>
> elseExpr statements last is a message, not an assignment, though we<br>
> can factor the pop out...<br>
><br>
> 2) inlined loop messages don't require a final pop...<br>
><br>
> x <= y ifTrue: [x to: y do: [:i | (self at: i) doSome]] ifFalse: [y<br>
> to: x do: [:i | (self at: i) doSome]].<br>
><br>
> An encoder pushing a value in both branches just to pop it after<br>
> wouldn't be that well behaved...<br>
><br>
> I won't give any version publicly because I crashed several images in<br>
> the bootstrap process, and don't know if the bug is in the bootstrap<br>
> or in the code.<br>
><br>
</div>IMO, too much effort for such diminishing returns. :)<br></blockquote><div><br></div><div>That was my thought too. It would be interesting to quantify the benefits. I noticed some 451 methods that were improved by my simple assignment-only mod. How many additional methods get caught by yours Nicolas?</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div><div></div><div class="h5"><br>
> Nicolas<br>
><br>
>> !MessageNode methodsFor: 'code generation' stamp: 'eem 2/13/2012 15:25'!<br>
>> ifThenElseForEffectShouldSharePop<br>
>> | thenExpr elseExpr |<br>
>> thenExpr := arguments at: 1.<br>
>> elseExpr := arguments at: 2.<br>
>> ^((thenExpr isJust: NodeNil)<br>
>> or: [(elseExpr isJust: NodeNil)<br>
>> or: [thenExpr statements last isAssignmentNode<br>
>> and: [elseExpr statements last isAssignmentNode]]]) not<br>
>><br>
>> "^(thenExpr isJust: NodeNil) not<br>
>> and: [(elseExpr isJust: NodeNil) not<br>
>> and: [thenExpr statements last isAssignmentNode not<br>
>> or: [elseExpr statements last isAssignmentNode not]]]"! !<br>
>><br>
>>> Also, I'm sure that multiple-jump-elimination proposed by Igor and<br>
>>> other kind of optimization would be a perfect subject for proving<br>
>>> concepts of NewCompiler IR infrastructure.<br>
>>><br>
>>> MessageNode>>doesEffectRequiresAPop: encoder<br>
>>> special > 0<br>
>>> ifTrue:<br>
>>> [^self perform: (MacroTesters at: special) with:<br>
>>> encoder].<br>
>>> ^super doesEffectRequiresAPop: encoder<br>
>>><br>
>>> MessageNode>>doesEffectForIfRequiresAPop: encoder<br>
>>> "If both branch require a pop instruction, then the pop is factored<br>
>>> after the jump.<br>
>>> In this case, the translation of this node also require a final pop<br>
>>> that can further be eliminated eventually."<br>
>>> | thenExpr elseExpr |<br>
>>> thenExpr := arguments at: 1.<br>
>>> elseExpr := arguments at: 2.<br>
>>> ^((thenExpr isJust: NodeNil) or: [elseExpr isJust: NodeNil]) not<br>
>>> and: [(thenExpr doesEvaluatingEffectRequiresAPop: encoder)<br>
>>> and:<br>
>>> [elseExpr doesEvaluatingEffectRequiresAPop: encoder]].<br>
>>><br>
>>> BlockNode>>doesEvaluatingEffectRequiresAPop: anEncoder<br>
>>> "Test whether a pop instruction is required to skip the value on<br>
>>> the<br>
>>> stack when this block is inlined."<br>
>>> ^statements size > 0 and: [statements last doesEffectRequiresAPop:<br>
>>> anEncoder]<br>
>>><br>
>>> AssigmentNode>>doesEffectRequiresAPop: anEncoder<br>
>>> "Test whether a pop instruction is required to skip the value on<br>
>>> the stack"<br>
>>> ^(variable canStorePopInASingleInstruction: anEncoder) not<br>
>>><br>
>>> InstanceVariableNode>>canStorePopInASingleInstruction: anEncoder<br>
>>> ^true<br>
>>><br>
>>> etc...<br>
>>><br>
>>> Le 14 février 2012 01:27, Eliot Miranda <<a href="mailto:eliot.miranda@gmail.com">eliot.miranda@gmail.com</a>> a écrit<br>
>>> :<br>
>>> > OK, I fixed this (a pleasant Monday afternoon distraction) (at least I<br>
>>> > *think* I've fixed it; I still have to check the decompiler). But... in<br>
>>> > doing so I realised I had to fix CompiledMethod>>#= since I needed to<br>
>>> > see<br>
>>> > exactly which methods the compiler change affected (just committed as<br>
>>> > Kernel-eem.669). In doing this I noticed that recent compiler changes<br>
>>> > have<br>
>>> > not been applied by recompiling affected methods in the system. If you<br>
>>> > look<br>
>>> > at Behavior>>#sourceMatchesBytecodeAt: it uses CompiledMethod>>#= to<br>
>>> > check<br>
>>> > that the compiler's output remains unchanged. In the 4.3 trunk image<br>
>>> > with<br>
>>> > CompiledMethod>>#= fixed, sourceMatchesBytecodeAt: reports that<br>
>>> > some 19654<br>
>>> > methods need recompiling:<br>
>>> ><br>
>>> > (SystemNavigation new allSelect: [:m| (m methodClass<br>
>>> > sourceMatchesBytecodeAt: m selector) not]) size 19654<br>
>>> ><br>
>>> > Being selective in recompiling, via e.g.<br>
>>> ><br>
>>> > SystemNavigation new allSelect: [:m| (m methodClass<br>
>>> > sourceMatchesBytecodeAt:<br>
>>> > m selector) ifFalse: [m methodClass recompile: m selector]. false]<br>
>>> ><br>
>>> > one gets to the desired<br>
>>> ><br>
>>> > (SystemNavigation new allSelect: [:m| (m methodClass<br>
>>> > sourceMatchesBytecodeAt: m selector) not]) size 0<br>
>>> ><br>
>>> > So the question is should we add an update that does the selective<br>
>>> > recompile? I think we should, e.g. by committing a version of Compiler<br>
>>> > that<br>
>>> > contains the selective recompile as a post-script. Agreed?<br>
>>> ><br>
>>> > On Mon, Feb 13, 2012 at 11:58 AM, Eliot Miranda<br>
>>> > <<a href="mailto:eliot.miranda@gmail.com">eliot.miranda@gmail.com</a>><br>
>>> > wrote:<br>
>>> >><br>
>>> >> Hi All,<br>
>>> >><br>
>>> >> (whitewash alert) I just had occasion to look at the bytecode<br>
>>> >> generated by the standard compiler for HashedCollection<br>
>>> >> class>>#goodPrimeAtLeast:. Here's the source, with the issue in bold:<br>
>>> >><br>
>>> >> goodPrimeAtLeast: lowerLimit<br>
>>> >> "Answer the next good prime >= lowerlimit.<br>
>>> >> If lowerLimit is larger than the largest known good prime,<br>
>>> >> just make it odd."<br>
>>> >> | primes low mid high prime |<br>
>>> >> primes := self goodPrimes.<br>
>>> >> low := 1.<br>
>>> >> high := primes size.<br>
>>> >> lowerLimit > (primes at: high) ifTrue: [<br>
>>> >> ^lowerLimit bitOr: 1 ].<br>
>>> >> [ high - low <= 1 ] whileFalse: [<br>
>>> >> mid := high + low // 2.<br>
>>> >> prime := primes at: mid.<br>
>>> >> prime = lowerLimit ifTrue: [ ^prime ].<br>
>>> >> prime < lowerLimit<br>
>>> >> ifTrue: [ low := mid ]<br>
>>> >> ifFalse: [ high := mid ] ].<br>
>>> >> (primes at: low) >= lowerLimit ifTrue: [ ^primes at: low ].<br>
>>> >> ^primes at: high<br>
>>> >><br>
>>> >> The code for this sequence is<br>
>>> >> 58 <15> pushTemp: 5<br>
>>> >> 59 <10> pushTemp: 0<br>
>>> >> 60 <B2> send: <<br>
>>> >> 61 <9B> jumpFalse: 66<br>
>>> >> 62 <13> pushTemp: 3<br>
>>> >> 63 <81 42> storeIntoTemp: 2<br>
>>> >> 65 <92> jumpTo: 69<br>
>>> >> 66 <13> pushTemp: 3<br>
>>> >> 67 <81 44> storeIntoTemp: 4<br>
>>> >> 69 <87> pop<br>
>>> >><br>
>>> >> where-as the following would be better:<br>
>>> >><br>
>>> >> 58 <15> pushTemp: 5<br>
>>> >> 59 <10> pushTemp: 0<br>
>>> >> 60 <B2> send: <<br>
>>> >> 61 <9B> jumpFalse: 66<br>
>>> >> 62 <13> pushTemp: 3<br>
>>> >> 63 <82 42> popIntoTemp: 2<br>
>>> >> 65 <92> jumpTo: 69<br>
>>> >> 66 <13> pushTemp: 3<br>
>>> >> 67 <82 44> popIntoTemp: 4<br>
>>> >><br>
>>> >> The reason is that the code generator favours using a single pop for<br>
>>> >> both<br>
>>> >> arms of the if:<br>
>>> >><br>
>>> >> MessageNode>>sizeCodeForIf: encoder value: forValue<br>
>>> >> | thenExpr elseExpr branchSize thenSize elseSize |<br>
>>> >> thenExpr := arguments at: 1.<br>
>>> >> elseExpr := arguments at: 2.<br>
>>> >> (forValue<br>
>>> >> or: [(thenExpr isJust: NodeNil)<br>
>>> >> or: [elseExpr isJust: NodeNil]]) not<br>
>>> >> "(...not ifTrue: avoids using ifFalse: alone during this compile)"<br>
>>> >> ifTrue: "Two-armed IFs forEffect share a single pop"<br>
>>> >> [^super sizeCodeForEffect: encoder].<br>
>>> >> ...<br>
>>> >><br>
>>> >> MessageNode>>emitCodeForIf: stack encoder: encoder value: forValue<br>
>>> >> | thenExpr thenSize elseExpr elseSize |<br>
>>> >> thenSize := sizes at: 1.<br>
>>> >> elseSize := sizes at: 2.<br>
>>> >> (forValue not and: [elseSize * thenSize > 0]) ifTrue:<br>
>>> >> "Two-armed IFs forEffect share a single pop"<br>
>>> >> [^super emitCodeForEffect: stack encoder: encoder].<br>
>>> >><br>
>>> >> It would be nice if this only happened if doing so actually reduced the<br>
>>> >> size of the generated code.<br>
>>> >> --<br>
>>> >> best,<br>
>>> >> Eliot<br>
>>> >><br>
>>> ><br>
>>> ><br>
>>> ><br>
>>> > --<br>
>>> > best,<br>
>>> > Eliot<br>
>>> ><br>
>>> ><br>
>>> ><br>
>>> ><br>
>>><br>
>><br>
>><br>
>><br>
>> --<br>
>> best,<br>
>> Eliot<br>
>><br>
>><br>
>><br>
>><br>
><br>
<br>
<br>
<br>
</div></div><div><div></div><div class="h5">--<br>
Best regards,<br>
Igor Stasenko.<br>
<br>
</div></div></blockquote></div><br><br clear="all"><div><br></div>-- <br>best,<div>Eliot</div><br>