Take the following code: int a, b; int f(int bool1) { int c; int c1 = a/b; if(bool1) c = 0; else c = a/b; return c; } On the mainline, we produce (at -O2 -fomit-frame-pointer): f: subl $8, %esp xorl %ecx, %ecx movl 12(%esp), %eax movl %ebx, (%esp) movl b, %edx movl %esi, 4(%esp) movl a, %ebx testl %eax, %eax jne .L4 movl %ebx, %eax movl %edx, %esi cltd idivl %esi movl %eax, %ecx .L4: movl (%esp), %ebx movl %ecx, %eax movl 4(%esp), %esi addl $8, %esp ret Which is just a mess. in 4.0.0, we produced: f: movl 4(%esp), %edx xorl %eax, %eax testl %edx, %edx jne .L4 movl a, %eax cltd idivl b .L4: ret There are two ways of fixing this, one way is to sink loads; the other simple way (most likely for 4.1) is to call dce before fre. I think the reason why the testcase which Steven committed did not catch this is because sink will sink the divide which is what is only in Steven's testcase.
I will need someone to test DCE before FRE for me.
Could you show what the code looks like before and after FRE? I imagine FRE eliminates one a/b, which isn't really making a mess of loads.
(In reply to comment #2) > I imagine FRE eliminates one a/b, which isn't really making a mess of loads. It is eliminating the loads of a and b too but nothing (maybe it is the job of the ra), moves the loads back into the conditional branch.
FRE can't really do anything about this. DOM would do the same thing if it was run before DCE. I'll make the sinker sink loads.
(In reply to comment #4) > I'll make the sinker sink loads. Since that will not happen until 4.2 at the earliest because it needs some cleanup as mentioned on http://gcc.gnu.org/wiki/Improved%20Aliasing%20Todo%20List Is adding an extra DCE before FRE and such, a possibility?
Re. comment #5 -- it's always a possibility ;-) Just show that it's worth it. I doubt it is, really.
Why have we regressed relative to 4.0?
Subject: Re: [4.1 Regression] FRE before DCE makes a mess of loads or need to sink loads > > > > ------- Comment #7 from mmitchel at gcc dot gnu dot org 2005-10-31 04:58 ------- > Why have we regressed relative to 4.0? Because passes were reordered in 4.1. -- Pinski
This issue will not be resolved in GCC 4.1.0; retargeted at GCC 4.1.1.
Now, we have /* Initial scalar cleanups. */ NEXT_PASS (pass_ccp); NEXT_PASS (pass_fre); NEXT_PASS (pass_dce); NEXT_PASS (pass_forwprop); NEXT_PASS (pass_copy_prop); NEXT_PASS (pass_merge_phi); NEXT_PASS (pass_vrp); NEXT_PASS (pass_dce); NEXT_PASS (pass_dominator); where I would suggest changing that to NEXT_PASS (pass_ccp); NEXT_PASS (pass_forwprop); NEXT_PASS (pass_copy_prop); (maybe even doing store copyprop here, instead of copyprop, trying to get rid of the first dom pass) NEXT_PASS (pass_dce); NEXT_PASS (pass_fre); NEXT_PASS (pass_merge_phi); NEXT_PASS (pass_vrp); NEXT_PASS (pass_dce); NEXT_PASS (pass_dominator); Now, there's definitely too little comments in the pass ordering to decide what the particular reason is for the current state. Another question is what would be sufficient testing for a pass-reordering patch? I suppose we have testcases for optimizations that rely on a particular pass ordering, so running say SPEC in addition to the testsuite should suffice?
Exchanging FRE with DCE produces on x86_64 (-O2 vs. -O2 with patch): Estimated Estimated Base Base Base Peak Peak Peak Benchmarks Ref Time Run Time Ratio Ref Time Run Time Ratio ------------ -------- -------- -------- -------- -------- -------- 164.gzip 1400 165 851 1400 164 851 * 164.gzip 1400 164 851 * 1400 164 856 164.gzip 1400 164 856 1400 164 851 175.vpr 1400 157 892 * 1400 160 877 * 175.vpr 1400 156 898 1400 159 882 175.vpr 1400 158 888 1400 161 872 176.gcc 1100 -- X 1100 -- X 181.mcf 1800 319 564 1800 320 562 * 181.mcf 1800 320 562 * 1800 320 562 181.mcf 1800 321 562 1800 320 563 186.crafty 1000 65.8 1520 1000 65.3 1532 186.crafty 1000 66.0 1515 * 1000 65.2 1534 186.crafty 1000 66.6 1500 1000 65.2 1533 * 197.parser 1800 267 675 1800 268 671 197.parser 1800 268 671 * 1800 269 670 197.parser 1800 268 671 1800 268 671 * 252.eon 1300 89.4 1454 1300 89.1 1459 * 252.eon 1300 90.0 1444 1300 90.1 1443 252.eon 1300 89.5 1452 * 1300 89.0 1461 253.perlbmk 1800 160 1126 * 1800 160 1126 * 253.perlbmk 1800 159 1131 1800 159 1130 253.perlbmk 1800 160 1123 1800 160 1124 254.gap 1100 114 963 * 1100 117 941 * 254.gap 1100 114 963 1100 117 942 254.gap 1100 115 956 1100 118 934 255.vortex 1900 143 X 1900 143 X 255.vortex 1900 144 X 1900 144 X 255.vortex 1900 143 X 1900 143 X 256.bzip2 1500 164 913 * 1500 165 912 * 256.bzip2 1500 164 917 1500 164 917 256.bzip2 1500 164 912 1500 165 911 300.twolf 3000 292 1028 3000 296 1014 300.twolf 3000 293 1023 3000 292 1028 300.twolf 3000 293 1024 * 3000 295 1016 * ======================================================================== 164.gzip 1400 164 851 * 1400 164 851 * 175.vpr 1400 157 892 * 1400 160 877 * 176.gcc X X 181.mcf 1800 320 562 * 1800 320 562 * 186.crafty 1000 66.0 1515 * 1000 65.2 1533 * 197.parser 1800 268 671 * 1800 268 671 * 252.eon 1300 89.5 1452 * 1300 89.1 1459 * 253.perlbmk 1800 160 1126 * 1800 160 1126 * 254.gap 1100 114 963 * 1100 117 941 * 255.vortex X X 256.bzip2 1500 164 913 * 1500 165 912 * 300.twolf 3000 293 1024 * 3000 295 1016 * Est. SPECint_base2000 -- Est. SPECint2000 -- Estimated Estimated Base Base Base Peak Peak Peak Benchmarks Ref Time Run Time Ratio Ref Time Run Time Ratio ------------ -------- -------- -------- -------- -------- -------- 168.wupwise 1600 148 1084 1600 147 1086 168.wupwise 1600 149 1075 1600 148 1079 168.wupwise 1600 148 1082* 1600 147 1086* 171.swim 3100 381 814 3100 381 814 171.swim 3100 380 816 3100 380 815 171.swim 3100 380 816* 3100 380 815* 172.mgrid 1800 244 737 1800 243 740 172.mgrid 1800 244 737 1800 243 741 172.mgrid 1800 244 737* 1800 243 741* 173.applu 2100 262 801 2100 263 797 173.applu 2100 263 799* 2100 264 796* 173.applu 2100 263 798 2100 264 795 177.mesa 1400 120 1170 1400 120 1168 177.mesa 1400 119 1176* 1400 119 1177 177.mesa 1400 119 1176 1400 119 1176* 178.galgel 2900 195 1486 2900 193 1503* 178.galgel 2900 194 1495* 2900 197 1472 178.galgel 2900 193 1501 2900 192 1510 179.art 2600 249 1042* 2600 247 1053 179.art 2600 249 1044 2600 241 1080 179.art 2600 251 1035 2600 246 1058* 183.equake 1300 121 1073 1300 121 1072* 183.equake 1300 122 1066 1300 122 1067 183.equake 1300 121 1072* 1300 121 1073 187.facerec 1900 226 842* 1900 225 846* 187.facerec 1900 226 839 1900 225 843 187.facerec 1900 225 844 1900 224 847 188.ammp 2200 227 971 2200 227 968 188.ammp 2200 227 971* 2200 227 971* 188.ammp 2200 227 968 2200 227 971 189.lucas 2000 181 1105 2000 182 1097* 189.lucas 2000 182 1100 2000 183 1094 189.lucas 2000 181 1104* 2000 182 1101 191.fma3d 2100 257 818* 2100 256 819* 191.fma3d 2100 257 818 2100 257 819 191.fma3d 2100 257 818 2100 256 819 200.sixtrack 1100 257 428 1100 259 425 200.sixtrack 1100 257 428 1100 259 425 200.sixtrack 1100 257 428* 1100 259 425* 301.apsi 2600 277 937* 2600 281 926* 301.apsi 2600 277 939 2600 280 928 301.apsi 2600 278 936 2600 281 925 ======================================================================== 168.wupwise 1600 148 1082* 1600 147 1086* 171.swim 3100 380 816* 3100 380 815* 172.mgrid 1800 244 737* 1800 243 741* 173.applu 2100 263 799* 2100 264 796* 177.mesa 1400 119 1176* 1400 119 1176* 178.galgel 2900 194 1495* 2900 193 1503* 179.art 2600 249 1042* 2600 246 1058* 183.equake 1300 121 1072* 1300 121 1072* 187.facerec 1900 226 842* 1900 225 846* 188.ammp 2200 227 971* 2200 227 971* 189.lucas 2000 181 1104* 2000 182 1097* 191.fma3d 2100 257 818* 2100 256 819* 200.sixtrack 1100 257 428* 1100 259 425* 301.apsi 2600 277 937* 2600 281 926* Est. SPECfp_base2000 918 Est. SPECfp2000 918
Will not be fixed in 4.1.1; adjust target milestone to 4.1.2.
On mainline we now have f: xorl %eax, %eax movl a, %edx cmpl $0, 4(%esp) movl b, %ecx jne .L4 movl %edx, %eax sarl $31, %edx idivl %ecx .L4: rep ; ret which still loads a and b unconditionally, but it looks less "messy". 4.1.1 is the mess as in comment #1. We end up with f (bool1) { int c1; int c; int b.1; int a.0; <bb 2>: # VUSE <a_2>; a.0_3 = a; # VUSE <b_4>; b.1_5 = b; if (bool1_7 != 0) goto <L2>; else goto <L1>; <L1>:; c1_6 = a.0_3 / b.1_5; # c_1 = PHI <0(2), c1_6(3)>; <L2>:; return c_1; } where the best thing would be to sink the loads to the single-use a.0_3 and b.1_5 into the conditional BB. It looks like TER has code to deal with this case and could replace a.0_3 and b.1_5 with a and b, but this doesn't happen.
TER acts only within a basic block, and that will probably not change. Its primary function is simply to mash trees back together so the expander gets a better look. This is more likely to handled by the RABLET work eventually... Either by the register pressure reduction code, or the merge with expand.
Even though we now do a DCE before FRE, we still don't get this correct as we don't have we don't have aliasing (during the first DCE) so we assume all loads as violatile.
The new SCCVN fixes this testcase. So this is fixed for 4.3.0.
Closing 4.1 branch.
Closing 4.2 branch, fixed in 4.3.