Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.

open64-devel

 [Open64-devel] one more question about strength reduction and SSA PRE From: Yiran Wang - 2013-06-27 00:08:02 Attachments: Message as HTML ```Hi All, This one looks somewhat similar to the last example, but is different. int foo(int N, int j, int *x, int *z) { int y = N; N += 7; N >>= 3; int i; for(i = 0; i< j; i++) { x += N*N << 3; z = x + N; y = y + *x + *z; } return y; } Assembly of the loop at -O3. .p2align 4,,15 .Lt_0_3586: # Loop body line 7, nesting depth: 1, estimated iterations: 1000 .loc 1 9 0 # 8 { # 9 x += N*N << 3; movl %eax,%ebx # [0] .loc 1 11 0 # 10 z = x + N; # 11 y = y + *x + *z; addl \$1,%ebp # [0] .loc 1 9 0 imull %eax,%ebx # [1] shll \$3,%ebx # [4] shll \$2,%ebx # [5] addl %ebx,%edi # [6] addl %ebx,%esi # [6] .loc 1 11 0 movl 0(%edi),%ecx # [7] id:23 addl 0(%esi),%ecx # [10] addl %ecx,%edx # [13] cmpl 36(%esp),%ebp # [13] j jl .Lt_0_3586 # [16] As we see, the imul instruction remains in the loop. (and two consequent shll instructions, my guess is that CG is thinking there should not be such input from WOPT, so it is not optimized in CG, though it is simple. ) It looks like SSA PRE omitted the rhs of Iv_update statement x+= N*N<<3, and VNFRE is only doing one level of CSE, say, promoting the ASHR + LDC 3 out of the loop. I am curious why SSA PRE is omitting the expression here. By disabling this in opt_etable.cxx, the result looks good for this test case. I wonder if there is any correctness issue for some other test case, or performance issue? It should be noted one strength reduction transformation is done for z for this case. Also replacing "N>>=3;" with "N*=5;" results in similar sub-optimal code. Best Regards, Yiran Wang ```
 Re: [Open64-devel] one more question about strength reduction and SSA PRE From: Jian-Xin Lai - 2013-06-27 07:26:10 Attachments: Message as HTML ```>From your description, if the code is change a little: for(i = 0; i< j; i++) { int t = N*N; x += t << 3; z = x + N; y = y + *x + *z; } Will the N*N be hoisted? 2013/6/27 Yiran Wang > Hi All, > > This one looks somewhat similar to the last example, but is different. > > int foo(int N, int j, int *x, int *z) > { > int y = N; > N += 7; > N >>= 3; > int i; > for(i = 0; i< j; i++) > { > x += N*N << 3; > z = x + N; > y = y + *x + *z; > } > return y; > } > > Assembly of the loop at -O3. > .p2align 4,,15 > .Lt_0_3586: > # Loop body line 7, nesting depth: 1, estimated iterations: 1000 > .loc 1 9 0 > # 8 { > # 9 x += N*N << 3; > movl %eax,%ebx # [0] > .loc 1 11 0 > # 10 z = x + N; > # 11 y = y + *x + *z; > addl \$1,%ebp # [0] > .loc 1 9 0 > imull %eax,%ebx # [1] > shll \$3,%ebx # [4] > shll \$2,%ebx # [5] > addl %ebx,%edi # [6] > addl %ebx,%esi # [6] > .loc 1 11 0 > movl 0(%edi),%ecx # [7] id:23 > addl 0(%esi),%ecx # [10] > addl %ecx,%edx # [13] > cmpl 36(%esp),%ebp # [13] j > jl .Lt_0_3586 # [16] > > As we see, the imul instruction remains in the loop. > (and two consequent shll instructions, my guess is that CG is thinking > there should not be such input from WOPT, so it is not optimized in CG, > though it is simple. ) > > It looks like SSA PRE omitted the rhs of Iv_update statement x+= N*N<<3, > and VNFRE is only doing one level of CSE, say, promoting the ASHR + LDC 3 > out of the loop. > > I am curious why SSA PRE is omitting the expression here. By disabling > this in opt_etable.cxx, the result looks good for this test case. I wonder > if there is any correctness issue for some other test case, or performance > issue? > > It should be noted one strength reduction transformation is done for z for > this case. Also replacing "N>>=3;" with "N*=5;" results in similar > sub-optimal code. > > Best Regards, > Yiran Wang > > > > > ------------------------------------------------------------------------------ > This SF.net email is sponsored by Windows: > > Build for Windows Store. > > http://p.sf.net/sfu/windows-dev2dev > _______________________________________________ > Open64-devel mailing list > Open64-devel@... > https://lists.sourceforge.net/lists/listinfo/open64-devel > > -- Regards, Lai Jian-Xin ```
 Re: [Open64-devel] one more question about strength reduction and SSA PRE From: Yiran Wang - 2013-06-27 17:14:26 Attachments: Message as HTML ```Thanks for your comments. No, the assembly looks the same. Good or bad, the compiler is able to clean up the temporary completely, say, copy propagation and DSE. Regards, Yiran On Thu, Jun 27, 2013 at 12:26 AM, Jian-Xin Lai wrote: > From your description, if the code is change a little: > > for(i = 0; i< j; i++) > { > int t = N*N; > x += t << 3; > z = x + N; > y = y + *x + *z; > } > > Will the N*N be hoisted? > > > 2013/6/27 Yiran Wang > >> Hi All, >> >> This one looks somewhat similar to the last example, but is different. >> >> int foo(int N, int j, int *x, int *z) >> { >> int y = N; >> N += 7; >> N >>= 3; >> int i; >> for(i = 0; i< j; i++) >> { >> x += N*N << 3; >> z = x + N; >> y = y + *x + *z; >> } >> return y; >> } >> >> Assembly of the loop at -O3. >> .p2align 4,,15 >> .Lt_0_3586: >> # Loop body line 7, nesting depth: 1, estimated iterations: 1000 >> .loc 1 9 0 >> # 8 { >> # 9 x += N*N << 3; >> movl %eax,%ebx # [0] >> .loc 1 11 0 >> # 10 z = x + N; >> # 11 y = y + *x + *z; >> addl \$1,%ebp # [0] >> .loc 1 9 0 >> imull %eax,%ebx # [1] >> shll \$3,%ebx # [4] >> shll \$2,%ebx # [5] >> addl %ebx,%edi # [6] >> addl %ebx,%esi # [6] >> .loc 1 11 0 >> movl 0(%edi),%ecx # [7] id:23 >> addl 0(%esi),%ecx # [10] >> addl %ecx,%edx # [13] >> cmpl 36(%esp),%ebp # [13] j >> jl .Lt_0_3586 # [16] >> >> As we see, the imul instruction remains in the loop. >> (and two consequent shll instructions, my guess is that CG is thinking >> there should not be such input from WOPT, so it is not optimized in CG, >> though it is simple. ) >> >> It looks like SSA PRE omitted the rhs of Iv_update statement x+= N*N<<3, >> and VNFRE is only doing one level of CSE, say, promoting the ASHR + LDC 3 >> out of the loop. >> >> I am curious why SSA PRE is omitting the expression here. By disabling >> this in opt_etable.cxx, the result looks good for this test case. I wonder >> if there is any correctness issue for some other test case, or performance >> issue? >> >> It should be noted one strength reduction transformation is done for z >> for this case. Also replacing "N>>=3;" with "N*=5;" results in similar >> sub-optimal code. >> >> Best Regards, >> Yiran Wang >> >> >> >> >> ------------------------------------------------------------------------------ >> This SF.net email is sponsored by Windows: >> >> Build for Windows Store. >> >> http://p.sf.net/sfu/windows-dev2dev >> _______________________________________________ >> Open64-devel mailing list >> Open64-devel@... >> https://lists.sourceforge.net/lists/listinfo/open64-devel >> >> > > > -- > Regards, > Lai Jian-Xin > ```
 Re: [Open64-devel] one more question about strength reduction and SSA PRE From: Jian-Xin Lai - 2013-07-01 08:44:11 Attachments: Message as HTML ```Using option "-WOPT:icopy=off:copy=off" to disable all copy-propagation? 2013/6/28 Yiran Wang > Thanks for your comments. > > No, the assembly looks the same. > > Good or bad, the compiler is able to clean up the temporary completely, > say, copy propagation and DSE. > > Regards, > Yiran > > > > On Thu, Jun 27, 2013 at 12:26 AM, Jian-Xin Lai wrote: > >> From your description, if the code is change a little: >> >> for(i = 0; i< j; i++) >> { >> int t = N*N; >> x += t << 3; >> z = x + N; >> y = y + *x + *z; >> } >> >> Will the N*N be hoisted? >> >> >> 2013/6/27 Yiran Wang >> >>> Hi All, >>> >>> This one looks somewhat similar to the last example, but is different. >>> >>> int foo(int N, int j, int *x, int *z) >>> { >>> int y = N; >>> N += 7; >>> N >>= 3; >>> int i; >>> for(i = 0; i< j; i++) >>> { >>> x += N*N << 3; >>> z = x + N; >>> y = y + *x + *z; >>> } >>> return y; >>> } >>> >>> Assembly of the loop at -O3. >>> .p2align 4,,15 >>> .Lt_0_3586: >>> # Loop body line 7, nesting depth: 1, estimated iterations: 1000 >>> .loc 1 9 0 >>> # 8 { >>> # 9 x += N*N << 3; >>> movl %eax,%ebx # [0] >>> .loc 1 11 0 >>> # 10 z = x + N; >>> # 11 y = y + *x + *z; >>> addl \$1,%ebp # [0] >>> .loc 1 9 0 >>> imull %eax,%ebx # [1] >>> shll \$3,%ebx # [4] >>> shll \$2,%ebx # [5] >>> addl %ebx,%edi # [6] >>> addl %ebx,%esi # [6] >>> .loc 1 11 0 >>> movl 0(%edi),%ecx # [7] id:23 >>> addl 0(%esi),%ecx # [10] >>> addl %ecx,%edx # [13] >>> cmpl 36(%esp),%ebp # [13] j >>> jl .Lt_0_3586 # [16] >>> >>> As we see, the imul instruction remains in the loop. >>> (and two consequent shll instructions, my guess is that CG is thinking >>> there should not be such input from WOPT, so it is not optimized in CG, >>> though it is simple. ) >>> >>> It looks like SSA PRE omitted the rhs of Iv_update statement x+= N*N<<3, >>> and VNFRE is only doing one level of CSE, say, promoting the ASHR + LDC 3 >>> out of the loop. >>> >>> I am curious why SSA PRE is omitting the expression here. By disabling >>> this in opt_etable.cxx, the result looks good for this test case. I wonder >>> if there is any correctness issue for some other test case, or performance >>> issue? >>> >>> It should be noted one strength reduction transformation is done for z >>> for this case. Also replacing "N>>=3;" with "N*=5;" results in similar >>> sub-optimal code. >>> >>> Best Regards, >>> Yiran Wang >>> >>> >>> >>> >>> ------------------------------------------------------------------------------ >>> This SF.net email is sponsored by Windows: >>> >>> Build for Windows Store. >>> >>> http://p.sf.net/sfu/windows-dev2dev >>> _______________________________________________ >>> Open64-devel mailing list >>> Open64-devel@... >>> https://lists.sourceforge.net/lists/listinfo/open64-devel >>> >>> >> >> >> -- >> Regards, >> Lai Jian-Xin >> > > -- Regards, Lai Jian-Xin ```
 Re: [Open64-devel] one more question about strength reduction and SSA PRE From: Sun Chan - 2013-06-27 18:32:52 Attachments: Message as HTML ```is N global? On Fri, Jun 28, 2013 at 1:14 AM, Yiran Wang wrote: > Thanks for your comments. > > No, the assembly looks the same. > > Good or bad, the compiler is able to clean up the temporary completely, > say, copy propagation and DSE. > > Regards, > Yiran > > > > On Thu, Jun 27, 2013 at 12:26 AM, Jian-Xin Lai wrote: > >> From your description, if the code is change a little: >> >> for(i = 0; i< j; i++) >> { >> int t = N*N; >> x += t << 3; >> z = x + N; >> y = y + *x + *z; >> } >> >> Will the N*N be hoisted? >> >> >> 2013/6/27 Yiran Wang >> >>> Hi All, >>> >>> This one looks somewhat similar to the last example, but is different. >>> >>> int foo(int N, int j, int *x, int *z) >>> { >>> int y = N; >>> N += 7; >>> N >>= 3; >>> int i; >>> for(i = 0; i< j; i++) >>> { >>> x += N*N << 3; >>> z = x + N; >>> y = y + *x + *z; >>> } >>> return y; >>> } >>> >>> Assembly of the loop at -O3. >>> .p2align 4,,15 >>> .Lt_0_3586: >>> # Loop body line 7, nesting depth: 1, estimated iterations: 1000 >>> .loc 1 9 0 >>> # 8 { >>> # 9 x += N*N << 3; >>> movl %eax,%ebx # [0] >>> .loc 1 11 0 >>> # 10 z = x + N; >>> # 11 y = y + *x + *z; >>> addl \$1,%ebp # [0] >>> .loc 1 9 0 >>> imull %eax,%ebx # [1] >>> shll \$3,%ebx # [4] >>> shll \$2,%ebx # [5] >>> addl %ebx,%edi # [6] >>> addl %ebx,%esi # [6] >>> .loc 1 11 0 >>> movl 0(%edi),%ecx # [7] id:23 >>> addl 0(%esi),%ecx # [10] >>> addl %ecx,%edx # [13] >>> cmpl 36(%esp),%ebp # [13] j >>> jl .Lt_0_3586 # [16] >>> >>> As we see, the imul instruction remains in the loop. >>> (and two consequent shll instructions, my guess is that CG is thinking >>> there should not be such input from WOPT, so it is not optimized in CG, >>> though it is simple. ) >>> >>> It looks like SSA PRE omitted the rhs of Iv_update statement x+= N*N<<3, >>> and VNFRE is only doing one level of CSE, say, promoting the ASHR + LDC 3 >>> out of the loop. >>> >>> I am curious why SSA PRE is omitting the expression here. By disabling >>> this in opt_etable.cxx, the result looks good for this test case. I wonder >>> if there is any correctness issue for some other test case, or performance >>> issue? >>> >>> It should be noted one strength reduction transformation is done for z >>> for this case. Also replacing "N>>=3;" with "N*=5;" results in similar >>> sub-optimal code. >>> >>> Best Regards, >>> Yiran Wang >>> >>> >>> >>> >>> ------------------------------------------------------------------------------ >>> This SF.net email is sponsored by Windows: >>> >>> Build for Windows Store. >>> >>> http://p.sf.net/sfu/windows-dev2dev >>> _______________________________________________ >>> Open64-devel mailing list >>> Open64-devel@... >>> https://lists.sourceforge.net/lists/listinfo/open64-devel >>> >>> >> >> >> -- >> Regards, >> Lai Jian-Xin >> > > > > ------------------------------------------------------------------------------ > This SF.net email is sponsored by Windows: > > Build for Windows Store. > > http://p.sf.net/sfu/windows-dev2dev > _______________________________________________ > Open64-devel mailing list > Open64-devel@... > https://lists.sourceforge.net/lists/listinfo/open64-devel > > ```
 Re: [Open64-devel] one more question about strength reduction and SSA PRE From: Sun Chan - 2013-06-27 18:33:40 Attachments: Message as HTML ```forget the stupid question. Something else is wrong Sun On Fri, Jun 28, 2013 at 2:32 AM, Sun Chan wrote: > is N global? > > > On Fri, Jun 28, 2013 at 1:14 AM, Yiran Wang wrote: > >> Thanks for your comments. >> >> No, the assembly looks the same. >> >> Good or bad, the compiler is able to clean up the temporary completely, >> say, copy propagation and DSE. >> >> Regards, >> Yiran >> >> >> >> On Thu, Jun 27, 2013 at 12:26 AM, Jian-Xin Lai wrote: >> >>> From your description, if the code is change a little: >>> >>> for(i = 0; i< j; i++) >>> { >>> int t = N*N; >>> x += t << 3; >>> z = x + N; >>> y = y + *x + *z; >>> } >>> >>> Will the N*N be hoisted? >>> >>> >>> 2013/6/27 Yiran Wang >>> >>>> Hi All, >>>> >>>> This one looks somewhat similar to the last example, but is different. >>>> >>>> int foo(int N, int j, int *x, int *z) >>>> { >>>> int y = N; >>>> N += 7; >>>> N >>= 3; >>>> int i; >>>> for(i = 0; i< j; i++) >>>> { >>>> x += N*N << 3; >>>> z = x + N; >>>> y = y + *x + *z; >>>> } >>>> return y; >>>> } >>>> >>>> Assembly of the loop at -O3. >>>> .p2align 4,,15 >>>> .Lt_0_3586: >>>> # Loop body line 7, nesting depth: 1, estimated iterations: 1000 >>>> .loc 1 9 0 >>>> # 8 { >>>> # 9 x += N*N << 3; >>>> movl %eax,%ebx # [0] >>>> .loc 1 11 0 >>>> # 10 z = x + N; >>>> # 11 y = y + *x + *z; >>>> addl \$1,%ebp # [0] >>>> .loc 1 9 0 >>>> imull %eax,%ebx # [1] >>>> shll \$3,%ebx # [4] >>>> shll \$2,%ebx # [5] >>>> addl %ebx,%edi # [6] >>>> addl %ebx,%esi # [6] >>>> .loc 1 11 0 >>>> movl 0(%edi),%ecx # [7] id:23 >>>> addl 0(%esi),%ecx # [10] >>>> addl %ecx,%edx # [13] >>>> cmpl 36(%esp),%ebp # [13] j >>>> jl .Lt_0_3586 # [16] >>>> >>>> As we see, the imul instruction remains in the loop. >>>> (and two consequent shll instructions, my guess is that CG is thinking >>>> there should not be such input from WOPT, so it is not optimized in CG, >>>> though it is simple. ) >>>> >>>> It looks like SSA PRE omitted the rhs of Iv_update statement x+= >>>> N*N<<3, and VNFRE is only doing one level of CSE, say, promoting the ASHR + >>>> LDC 3 out of the loop. >>>> >>>> I am curious why SSA PRE is omitting the expression here. By disabling >>>> this in opt_etable.cxx, the result looks good for this test case. I wonder >>>> if there is any correctness issue for some other test case, or performance >>>> issue? >>>> >>>> It should be noted one strength reduction transformation is done for z >>>> for this case. Also replacing "N>>=3;" with "N*=5;" results in similar >>>> sub-optimal code. >>>> >>>> Best Regards, >>>> Yiran Wang >>>> >>>> >>>> >>>> >>>> ------------------------------------------------------------------------------ >>>> This SF.net email is sponsored by Windows: >>>> >>>> Build for Windows Store. >>>> >>>> http://p.sf.net/sfu/windows-dev2dev >>>> _______________________________________________ >>>> Open64-devel mailing list >>>> Open64-devel@... >>>> https://lists.sourceforge.net/lists/listinfo/open64-devel >>>> >>>> >>> >>> >>> -- >>> Regards, >>> Lai Jian-Xin >>> >> >> >> >> ------------------------------------------------------------------------------ >> This SF.net email is sponsored by Windows: >> >> Build for Windows Store. >> >> http://p.sf.net/sfu/windows-dev2dev >> _______________________________________________ >> Open64-devel mailing list >> Open64-devel@... >> https://lists.sourceforge.net/lists/listinfo/open64-devel >> >> > ```
 Re: [Open64-devel] one more question about strength reduction and SSA PRE From: Fred Chow - 2013-07-02 12:29:54 Attachments: Message as HTML ```Hi Yiran, The reason is because PRE is not applied to the increment amount of an IV update statement. In your example, x += N*N << 3; is an IV update statement. If PRE is applied, the rhs of the IV update statement may be transformed so that the statement is no longer an IV update statement, which may in turn disable other IV-related optimizations. If you change the above statement to, say: x = z + (N*N << 3); (N*N << 3) will then be hoisted out of the loop because it is no longer an IV update statement. You can grep for "Set_omitted()" in opt_etable.cxx and see that "occur->Stmt()->Iv_update()" is one reason an expression is set omitted. Fred On 06/26/2013 05:07 PM, Yiran Wang wrote: > Hi All, > > This one looks somewhat similar to the last example, but is different. > > int foo(int N, int j, int *x, int *z) > { > int y = N; > N += 7; > N >>= 3; > int i; > for(i = 0; i< j; i++) > { > x += N*N << 3; > z = x + N; > y = y + *x + *z; > } > return y; > } > > Assembly of the loop at -O3. > .p2align 4,,15 > .Lt_0_3586: > # Loop body line 7, nesting depth: 1, estimated iterations: 1000 > .loc190 > # 8 { > # 9 x += N*N << 3; > movl %eax,%ebx # [0] > .loc1110 > # 10 z = x + N; > # 11 y = y + *x + *z; > addl \$1,%ebp # [0] > .loc190 > imull %eax,%ebx # [1] > shll \$3,%ebx # [4] > shll \$2,%ebx # [5] > addl %ebx,%edi # [6] > addl %ebx,%esi # [6] > .loc1110 > movl 0(%edi),%ecx # [7] id:23 > addl 0(%esi),%ecx # [10] > addl %ecx,%edx # [13] > cmpl 36(%esp),%ebp # [13] j > jl .Lt_0_3586 # [16] > > As we see, the imul instruction remains in the loop. > (and two consequent shll instructions, my guess is that CG is thinking > there should not be such input from WOPT, so it is not optimized in > CG, though it is simple. ) > > It looks like SSA PRE omitted the rhs of Iv_update statement x+= > N*N<<3, and VNFRE is only doing one level of CSE, say, promoting the > ASHR + LDC 3 out of the loop. > > I am curious why SSA PRE is omitting the expression here. By > disabling this in opt_etable.cxx, the result looks good for this test > case. I wonder if there is any correctness issue for some other test > case, or performance issue? > > It should be noted one strength reduction transformation is done for z > for this case. Also replacing "N>>=3;" with "N*=5;" results in similar > sub-optimal code. > > Best Regards, > Yiran Wang > > > > > ------------------------------------------------------------------------------ > This SF.net email is sponsored by Windows: > > Build for Windows Store. > > http://p.sf.net/sfu/windows-dev2dev > > > _______________________________________________ > Open64-devel mailing list > Open64-devel@... > https://lists.sourceforge.net/lists/listinfo/open64-devel ```
 Re: [Open64-devel] one more question about strength reduction and SSA PRE From: Yiran Wang - 2013-07-02 20:20:25 Attachments: Message as HTML ```Hi Fred, Thanks for your reply, and one more question. What kind of IV related optimizations are we talking about here? Actually I have tried to disable that condition in opt_etable.cxx before, and for this specific case, the output looks good. The update code of IV "x" and "z" looks efficient. .Lt_0_2050: # Loop body line 3, nesting depth: 1, estimated iterations: 100 .loc 1 9 0 # 5 N *= 5; # 6 int i; # 7 for(i = 0; i< j; i++) # 8 { # 9 x += N * N << 3; addl %eax,%edi # [0] addl %eax,%ebp # [0] .loc 1 7 0 addl \$1,%esi # [0] .loc 1 11 0 # 10 z = x + N; # 11 y = y + *x + *z; addl 0(%edi),%edx # [1] addl 140(%ebp),%edx # [4] .loc 1 7 0 movl 36(%esp),%ebx # [4] j cmpl %esi,%ebx # [7] jg .Lt_0_2050 # [8] As we can see, the gain is noticeable. It looks like IVR created the new IV, and not modified "x" or "z", and strength reduction works fine. Best Regards, Yiran On Tue, Jul 2, 2013 at 5:29 AM, Fred Chow wrote: > Hi Yiran, > > The reason is because PRE is not applied to the increment amount of an IV > update statement. In your example, > > x += N*N << 3; > > is an IV update statement. If PRE is applied, the rhs of the IV update > statement may be transformed so that the statement is no longer an IV > update statement, which may in turn disable other IV-related optimizations. > > If you change the above statement to, say: > > x = z + (N*N << 3); > > (N*N << 3) will then be hoisted out of the loop because it is no longer an > IV update statement. > > You can grep for "Set_omitted()" in opt_etable.cxx and see that > "occur->Stmt()->Iv_update()" is one reason an expression is set omitted. > > Fred > > > On 06/26/2013 05:07 PM, Yiran Wang wrote: > > Hi All, > > This one looks somewhat similar to the last example, but is different. > > int foo(int N, int j, int *x, int *z) > { > int y = N; > N += 7; > N >>= 3; > int i; > for(i = 0; i< j; i++) > { > x += N*N << 3; > z = x + N; > y = y + *x + *z; > } > return y; > } > > Assembly of the loop at -O3. > .p2align 4,,15 > .Lt_0_3586: > # Loop body line 7, nesting depth: 1, estimated iterations: 1000 > .loc 1 9 0 > # 8 { > # 9 x += N*N << 3; > movl %eax,%ebx # [0] > .loc 1 11 0 > # 10 z = x + N; > # 11 y = y + *x + *z; > addl \$1,%ebp # [0] > .loc 1 9 0 > imull %eax,%ebx # [1] > shll \$3,%ebx # [4] > shll \$2,%ebx # [5] > addl %ebx,%edi # [6] > addl %ebx,%esi # [6] > .loc 1 11 0 > movl 0(%edi),%ecx # [7] id:23 > addl 0(%esi),%ecx # [10] > addl %ecx,%edx # [13] > cmpl 36(%esp),%ebp # [13] j > jl .Lt_0_3586 # [16] > > As we see, the imul instruction remains in the loop. > (and two consequent shll instructions, my guess is that CG is thinking > there should not be such input from WOPT, so it is not optimized in CG, > though it is simple. ) > > It looks like SSA PRE omitted the rhs of Iv_update statement x+= N*N<<3, > and VNFRE is only doing one level of CSE, say, promoting the ASHR + LDC 3 > out of the loop. > > I am curious why SSA PRE is omitting the expression here. By disabling > this in opt_etable.cxx, the result looks good for this test case. I wonder > if there is any correctness issue for some other test case, or performance > issue? > > It should be noted one strength reduction transformation is done for z > for this case. Also replacing "N>>=3;" with "N*=5;" results in similar > sub-optimal code. > > Best Regards, > Yiran Wang > > > > > ------------------------------------------------------------------------------ > This SF.net email is sponsored by Windows: > > Build for Windows Store. > http://p.sf.net/sfu/windows-dev2dev > > > > _______________________________________________ > Open64-devel mailing listOpen64-devel@...nethttps://lists.sourceforge.net/lists/listinfo/open64-devel > > > ```
 Re: [Open64-devel] one more question about strength reduction and SSA PRE From: Fred Chow - 2013-07-03 11:25:55 Attachments: Message as HTML ```IV-related optimizations are strength reduction and linear function test replacement. For example, in the loop body: . . i + 1 . . i = i + 1; If we do PRE on the IV update statement, it will change i = i + 1 to i = t, and strength reduction will not work. Fred On 07/02/2013 01:20 PM, Yiran Wang wrote: > Hi Fred, > > Thanks for your reply, and one more question. > What kind of IV related optimizations are we talking about here? > > Actually I have tried to disable that condition in opt_etable.cxx > before, and for this specific case, the output looks good. The update > code of IV "x" and "z" looks efficient. > > .Lt_0_2050: > # Loop body line 3, nesting depth: 1, estimated iterations: 100 > .loc190 > # 5 N *= 5; > # 6 int i; > # 7 for(i = 0; i< j; i++) > # 8 { > # 9 x += N * N << 3; > addl %eax,%edi # [0] > addl %eax,%ebp # [0] > .loc170 > addl \$1,%esi # [0] > .loc1110 > # 10 z = x + N; > # 11 y = y + *x + *z; > addl 0(%edi),%edx # [1] > addl 140(%ebp),%edx # [4] > .loc170 > movl 36(%esp),%ebx # [4] j > cmpl %esi,%ebx # [7] > jg .Lt_0_2050 # [8] > > As we can see, the gain is noticeable. > > It looks like IVR created the new IV, and not modified "x" or "z", and > strength reduction works fine. > > Best Regards, > Yiran > > > On Tue, Jul 2, 2013 at 5:29 AM, Fred Chow > wrote: > > Hi Yiran, > > The reason is because PRE is not applied to the increment amount > of an IV update statement. In your example, > > x += N*N << 3; > > is an IV update statement. If PRE is applied, the rhs of the IV > update statement may be transformed so that the statement is no > longer an IV update statement, which may in turn disable other > IV-related optimizations. > > If you change the above statement to, say: > > x = z + (N*N << 3); > > (N*N << 3) will then be hoisted out of the loop because it is no > longer an IV update statement. > > You can grep for "Set_omitted()" in opt_etable.cxx and see that > "occur->Stmt()->Iv_update()" is one reason an expression is set > omitted. > > Fred > > > On 06/26/2013 05:07 PM, Yiran Wang wrote: >> Hi All, >> >> This one looks somewhat similar to the last example, but is >> different. >> >> int foo(int N, int j, int *x, int *z) >> { >> int y = N; >> N += 7; >> N >>= 3; >> int i; >> for(i = 0; i< j; i++) >> { >> x += N*N << 3; >> z = x + N; >> y = y + *x + *z; >> } >> return y; >> } >> >> Assembly of the loop at -O3. >> .p2align 4,,15 >> .Lt_0_3586: >> # Loop body line 7, nesting depth: 1, estimated >> iterations: 1000 >> .loc190 >> # 8 { >> # 9 x += N*N << 3; >> movl %eax,%ebx # [0] >> .loc1110 >> # 10 z = x + N; >> # 11 y = y + *x + *z; >> addl \$1,%ebp # [0] >> .loc190 >> imull %eax,%ebx # [1] >> shll \$3,%ebx # [4] >> shll \$2,%ebx # [5] >> addl %ebx,%edi # [6] >> addl %ebx,%esi # [6] >> .loc1110 >> movl 0(%edi),%ecx # [7] id:23 >> addl 0(%esi),%ecx # [10] >> addl %ecx,%edx # [13] >> cmpl 36(%esp),%ebp # [13] j >> jl .Lt_0_3586 # [16] >> >> As we see, the imul instruction remains in the loop. >> (and two consequent shll instructions, my guess is that CG is >> thinking there should not be such input from WOPT, so it is not >> optimized in CG, though it is simple. ) >> >> It looks like SSA PRE omitted the rhs of Iv_update statement x+= >> N*N<<3, and VNFRE is only doing one level of CSE, say, promoting >> the ASHR + LDC 3 out of the loop. >> >> I am curious why SSA PRE is omitting the expression here. By >> disabling this in opt_etable.cxx, the result looks good for this >> test case. I wonder if there is any correctness issue for some >> other test case, or performance issue? >> >> It should be noted one strength reduction transformation is done >> for z for this case. Also replacing "N>>=3;" with "N*=5;" results >> in similar sub-optimal code. >> >> Best Regards, >> Yiran Wang >> >> >> >> >> ------------------------------------------------------------------------------ >> This SF.net email is sponsored by Windows: >> >> Build for Windows Store. >> >> http://p.sf.net/sfu/windows-dev2dev >> >> >> _______________________________________________ >> Open64-devel mailing list >> Open64-devel@... >> https://lists.sourceforge.net/lists/listinfo/open64-devel > > ```