harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "xiaoming gu" <xiaoming...@gmail.com>
Subject Re: [jira] Updated: (HARMONY-5965) [drlvm][jit]generate Mnemonic_LEA LIR for Op_Shladd HIR in IA32
Date Fri, 19 Sep 2008 15:05:49 GMT
On Fri, Sep 19, 2008 at 8:24 PM, Ian Rogers <rogers.email@gmail.com> wrote:

> xiaoming gu wrote:
>
>> Hi, all. I did something more for shladd=>LEA today. With the available
>> MUL
>> strength reduction,
>> X*10 is reduced to (X<<2+X) <<1+0 and 0 is generated by a self XOR
>> instruction (CASE 3).
>> Actually this XOR is not necessay and could be eliminated in HIR2LIR pass.
>> Following is the
>> better instructions generated with the improve patch. Comparing with
>> previous CASE 3, you may
>> find XOR gone.
>>
>>
>> CASE 4: MUL strength reduction - using LEA and taking care of 0
>>
>> I22: LEA t48(EDI):I_32,t47[v434(EBP)+v434(EBP)*t46(4)]:I_32 bcOff: 42 \l\
>> I23: LEA t52(EDI):I_32,t51[t48(EDI)*t50(2)+t49(0)]:I_32 bcOff: 42 \l\
>> I861: MOV v533[v521(ESP)+t532(-24)]:I_32,t52(EDI):I_32 bcOff: 43 \l\
>> I860: MOV v535[v521(ESP)+t534(-28)]:I_32,t53(1):I_32 bcOff: 45 \l\
>> I26: EmptyPseudoInst bcOff: 48 \l\
>>
>>                    CASE1      CASE2     CASE3      CASE4
>> Time (msec)   6234         7688          5734          5704
>> Normalized     1              1.233         0.920         0.915
>>
>>
>> I'm going to submit the patch though it only brings small performance
>> improvement (0.5%). Any
>> comment is welcome. Thanks.
>>
>> Xiaoming
>>
>>
> Hi Xiaoming,
>
> inspired by all this discussion I rehashed some of this code in Jikes RVM,
> the results are here [1]. We have a BURS instruction selector so we don't
> generate ShiftAdd operations instead the tree pattern matcher will combine a
> shift and add into an address [2] that we then turn into an LEA [3]. Anyway
> for a multiply by 10 we now produce:
>
> 3           int_move                t3si(I) = 0
> 3           int_shl                 t4si(I) = l0si(I,d), 1
> 3           int_add                 t5si(I) = t3si(I), t4si(I)
> 3           int_shl                 t6si(I) = l0si(I,d), 3
> 3           int_add                 t7si(I) = t5si(I), t6si(I)
> 3           int_move                t2si(I) = t7si(I)
>
> that becomes:
>
> 3           ia32_lea                t6si(I) = <0+[l0si(I,d)*8]>DW
> 3           ia32_lea                t7si(I) = <[t6si(I)]+[l0si(I,d)*2]>DW
>
> Rather than (x<<2+x)<<1 we produce (x<<3)+(x<<1) as I believe
this approach
> gives better opportunity for ILP. A better example is 100 for which we
> generate:
>
> 3           ia32_lea                EDX(I) = <0+[EAX(I,d)*4]>DW
> 3           ia32_lea                EDX(I) = <[EDX(I)]+[EDX(I)*8]>DW
> 3           ia32_shl                EAX(I) AF CF OF PF SF ZF <-- 6
> 3           ia32_add                EAX(I) AF CF OF PF SF ZF <-- EDX(I)
>
> that is ((x*4)*(1+8))+x*64. If we generated the shift and adds for the *64
> from the preceding shift then we end up losing the add in the 2nd LEA and
> having to generate an extra add to compensate, ie:
>
> 3           ia32_lea               t1 = l0*4
> 3           ia32_lea               t2 = t1*8
> 3           ia32_lea               t3 = t2*2 + t2
> 3           ia32_add              t1 = t3 + t1
>
> I believe we might as well do the shift by 6 and add as at least that can
> be done in parallel to the LEAs. I mention this as I think this may be what
> your multiply by 100 should look like. It'd be nice if Jikes RVM were doing
> simplification of constant division and of course for multiplication we're
> not considering subtractions to create the desired result (help welcome :-)
> ).
>
> Regards,
> Ian
>
> [1]
> http://jikesrvm.svn.sourceforge.net/viewvc/jikesrvm/rvmroot/trunk/rvm/src/org/jikesrvm/compilers/opt/Simplifier.java?revision=15001&view=markup#l_1379
> [2]
> http://jikesrvm.svn.sourceforge.net/viewvc/jikesrvm/rvmroot/trunk/rvm/src-generated/opt-burs/ia32/IA32.rules?view=markup#l_229
> [3]
> http://jikesrvm.svn.sourceforge.net/viewvc/jikesrvm/rvmroot/trunk/rvm/src-generated/opt-burs/ia32/IA32.rules?view=markup#l_297


Hi, Ian. Thanks for your helpful information.

X*100 is reduced to ((X<<2+X)<<2+0)<<2+((X<<2+X)<<2+0) and ((X<<2+X)<<2+0)
is reused. I get to know what your better ILP means and do some testing with
X*10. The timing result is 5750ms and no improvement on my desktop which is
with an Intel 4-core Q9550. I think the reason might be the advanced
micro-architecture of modern processors. The strategy of MUL strength
reduction in Harmony is not with the ILP concern and it always consumes the
produced operands in a stack as soon as possible.

There are SUB and NEG operations in the reduction and I'm going to study the
details next week. You may refer to multiplybyconstant.cpp for MUL reduction
and DIV reduction is in simplifyTauDiv() and simplifyTauRem() in
simplifier.cpp. Hope they are helpful. Thanks.

Xiaoming

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message