PRE in GCC-4.4 and mainline appears to backfire.
Consider:
void
foo (unsigned int n, unsigned int *p)
{
*p = 0;
if (0x01 & n) *p |= 0x0101;
if (0x02 & n) *p |= 0x0202;
if (0x04 & n) *p |= 0x0404;
if (0x08 & n) *p |= 0x0808;
if (0x10 & n) *p |= 0x1010;
if (0x20 & n) *p |= 0x2020;
if (0x40 & n) *p |= 0x4040;
if (0x80 & n) *p |= 0x8080;
}
"arm-none-eabi-gcc-4.3.3 -mcpu=cortex-a8 -O3 -S test.c" generates:
foo:
@ args = 0, pretend = 0, frame = 0
@ frame_needed = 0, uses_anonymous_args = 0
@ link register save eliminated.
and ip, r0, #1
movw r3, #771
cmp ip, #0
movw r2, #257
str r4, [sp, #-4]!
mov r4, r0
movw r0, #514
moveq r2, ip
moveq r3, r0
tst r4, #2
str r2, [r1, #0]
moveq r3, r2
strne r3, [r1, #0]
tst r4, #4
orrne r3, r3, #1024
orrne r3, r3, #4
strne r3, [r1, #0]
tst r4, #8
orrne r3, r3, #2048
orrne r3, r3, #8
strne r3, [r1, #0]
tst r4, #16
orrne r3, r3, #4096
orrne r3, r3, #16
strne r3, [r1, #0]
tst r4, #32
orrne r3, r3, #8192
orrne r3, r3, #32
strne r3, [r1, #0]
tst r4, #64
orrne r3, r3, #16384
orrne r3, r3, #64
strne r3, [r1, #0]
tst r4, #128
orrne r3, r3, #32768
orrne r3, r3, #128
strne r3, [r1, #0]
ldmfd sp!, {r4}
bx lr
In English, GCC-4.3 generates straight-line code with the contents of
the "if" statements taking advantage of conditional execution.
"arm-none-eabi-gcc-4.4.1 -mcpu=cortex-a8 -O3 -S test.c" generates
about 700 lines of assembly code. Since it's hard to decipher, here
is a tree-level dump.
<bb 2>:
if ((int) n & 1 != 0)
goto <bb 4>;
else
goto <bb 3>;
<bb 3>:
prephitmp.152 = 32896;
prephitmp.151 = 49344;
prephitmp.150 = 16448;
prephitmp.149 = 41120;
prephitmp.148 = 57568;
prephitmp.147 = 24672;
prephitmp.146 = 8224;
prephitmp.145 = 37008;
prephitmp.144 = 53456;
prephitmp.143 = 20560;
prephitmp.142 = 45232;
prephitmp.141 = 61680;
prephitmp.140 = 28784;
prephitmp.139 = 12336;
prephitmp.138 = 4112;
prephitmp.137 = 34952;
prephitmp.136 = 51400;
prephitmp.135 = 18504;
prephitmp.134 = 43176;
prephitmp.133 = 59624;
prephitmp.132 = 26728;
prephitmp.131 = 10280;
prephitmp.130 = 39064;
prephitmp.129 = 55512;
prephitmp.128 = 22616;
prephitmp.127 = 47288;
prephitmp.126 = 63736;
prephitmp.125 = 30840;
prephitmp.124 = 14392;
prephitmp.123 = 6168;
prephitmp.122 = 2056;
prephitmp.121 = 33924;
prephitmp.120 = 50372;
prephitmp.119 = 17476;
prephitmp.118 = 42148;
prephitmp.117 = 58596;
prephitmp.116 = 25700;
prephitmp.115 = 9252;
prephitmp.114 = 38036;
prephitmp.113 = 54484;
prephitmp.112 = 21588;
prephitmp.111 = 46260;
prephitmp.110 = 62708;
prephitmp.109 = 29812;
prephitmp.108 = 13364;
prephitmp.107 = 5140;
prephitmp.106 = 35980;
prephitmp.105 = 52428;
prephitmp.104 = 19532;
prephitmp.103 = 44204;
prephitmp.102 = 60652;
prephitmp.101 = 27756;
prephitmp.100 = 11308;
prephitmp.99 = 40092;
prephitmp.98 = 56540;
prephitmp.97 = 23644;
prephitmp.96 = 48316;
prephitmp.95 = 64764;
prephitmp.94 = 31868;
prephitmp.93 = 15420;
prephitmp.92 = 7196;
prephitmp.91 = 3084;
prephitmp.90 = 1028;
prephitmp.89 = 33410;
prephitmp.88 = 49858;
prephitmp.87 = 16962;
prephitmp.86 = 41634;
prephitmp.85 = 58082;
prephitmp.84 = 25186;
prephitmp.83 = 8738;
prephitmp.82 = 37522;
prephitmp.81 = 53970;
prephitmp.80 = 21074;
prephitmp.79 = 45746;
prephitmp.78 = 62194;
prephitmp.77 = 29298;
prephitmp.76 = 12850;
prephitmp.75 = 4626;
prephitmp.74 = 35466;
prephitmp.73 = 51914;
prephitmp.72 = 19018;
prephitmp.71 = 43690;
prephitmp.70 = 60138;
prephitmp.69 = 27242;
prephitmp.68 = 10794;
prephitmp.67 = 39578;
prephitmp.66 = 56026;
prephitmp.65 = 23130;
prephitmp.64 = 47802;
prephitmp.63 = 64250;
prephitmp.62 = 31354;
prephitmp.61 = 14906;
prephitmp.60 = 6682;
prephitmp.59 = 2570;
prephitmp.58 = 34438;
prephitmp.57 = 50886;
prephitmp.56 = 17990;
prephitmp.55 = 42662;
prephitmp.54 = 59110;
prephitmp.53 = 26214;
prephitmp.52 = 9766;
prephitmp.51 = 38550;
prephitmp.50 = 54998;
prephitmp.49 = 22102;
prephitmp.48 = 46774;
prephitmp.47 = 63222;
prephitmp.46 = 30326;
prephitmp.45 = 13878;
prephitmp.44 = 5654;
prephitmp.43 = 36494;
prephitmp.42 = 52942;
prephitmp.41 = 20046;
prephitmp.40 = 44718;
prephitmp.39 = 61166;
prephitmp.38 = 28270;
prephitmp.37 = 11822;
prephitmp.36 = 40606;
prephitmp.35 = 57054;
prephitmp.34 = 24158;
prephitmp.33 = 48830;
prephitmp.32 = 65278;
prephitmp.31 = 32382;
prephitmp.30 = 15934;
prephitmp.29 = 7710;
prephitmp.28 = 3598;
prephitmp.27 = 1542;
prephitmp.16 = 514;
cstore.13 = 0;
goto <bb 5>;
<bb 4>:
prephitmp.152 = 33153;
prephitmp.151 = 49601;
prephitmp.150 = 16705;
prephitmp.149 = 41377;
prephitmp.148 = 57825;
prephitmp.147 = 24929;
prephitmp.146 = 8481;
prephitmp.145 = 37265;
prephitmp.144 = 53713;
prephitmp.143 = 20817;
prephitmp.142 = 45489;
prephitmp.141 = 61937;
prephitmp.140 = 29041;
prephitmp.139 = 12593;
prephitmp.138 = 4369;
prephitmp.137 = 35209;
prephitmp.136 = 51657;
prephitmp.135 = 18761;
prephitmp.134 = 43433;
prephitmp.133 = 59881;
prephitmp.132 = 26985;
prephitmp.131 = 10537;
prephitmp.130 = 39321;
prephitmp.129 = 55769;
prephitmp.128 = 22873;
prephitmp.127 = 47545;
prephitmp.126 = 63993;
prephitmp.125 = 31097;
prephitmp.124 = 14649;
prephitmp.123 = 6425;
prephitmp.122 = 2313;
prephitmp.121 = 34181;
prephitmp.120 = 50629;
prephitmp.119 = 17733;
prephitmp.118 = 42405;
prephitmp.117 = 58853;
prephitmp.116 = 25957;
prephitmp.115 = 9509;
prephitmp.114 = 38293;
prephitmp.113 = 54741;
prephitmp.112 = 21845;
prephitmp.111 = 46517;
prephitmp.110 = 62965;
prephitmp.109 = 30069;
prephitmp.108 = 13621;
prephitmp.107 = 5397;
prephitmp.106 = 36237;
prephitmp.105 = 52685;
prephitmp.104 = 19789;
prephitmp.103 = 44461;
prephitmp.102 = 60909;
prephitmp.101 = 28013;
prephitmp.100 = 11565;
prephitmp.99 = 40349;
prephitmp.98 = 56797;
prephitmp.97 = 23901;
prephitmp.96 = 48573;
prephitmp.95 = 65021;
prephitmp.94 = 32125;
prephitmp.93 = 15677;
prephitmp.92 = 7453;
prephitmp.91 = 3341;
prephitmp.90 = 1285;
prephitmp.89 = 33667;
prephitmp.88 = 50115;
prephitmp.87 = 17219;
prephitmp.86 = 41891;
prephitmp.85 = 58339;
prephitmp.84 = 25443;
prephitmp.83 = 8995;
prephitmp.82 = 37779;
prephitmp.81 = 54227;
prephitmp.80 = 21331;
prephitmp.79 = 46003;
prephitmp.78 = 62451;
prephitmp.77 = 29555;
prephitmp.76 = 13107;
prephitmp.75 = 4883;
prephitmp.74 = 35723;
prephitmp.73 = 52171;
prephitmp.72 = 19275;
prephitmp.71 = 43947;
prephitmp.70 = 60395;
prephitmp.69 = 27499;
prephitmp.68 = 11051;
prephitmp.67 = 39835;
prephitmp.66 = 56283;
prephitmp.65 = 23387;
prephitmp.64 = 48059;
prephitmp.63 = 64507;
prephitmp.62 = 31611;
prephitmp.61 = 15163;
prephitmp.60 = 6939;
prephitmp.59 = 2827;
prephitmp.58 = 34695;
prephitmp.57 = 51143;
prephitmp.56 = 18247;
prephitmp.55 = 42919;
prephitmp.54 = 59367;
prephitmp.53 = 26471;
prephitmp.52 = 10023;
prephitmp.51 = 38807;
prephitmp.50 = 55255;
prephitmp.49 = 22359;
prephitmp.48 = 47031;
prephitmp.47 = 63479;
prephitmp.46 = 30583;
prephitmp.45 = 14135;
prephitmp.44 = 5911;
prephitmp.43 = 36751;
prephitmp.42 = 53199;
prephitmp.41 = 20303;
prephitmp.40 = 44975;
prephitmp.39 = 61423;
prephitmp.38 = 28527;
prephitmp.37 = 12079;
prephitmp.36 = 40863;
prephitmp.35 = 57311;
prephitmp.34 = 24415;
prephitmp.33 = 49087;
prephitmp.32 = 65535;
prephitmp.31 = 32639;
prephitmp.30 = 16191;
prephitmp.29 = 7967;
prephitmp.28 = 3855;
prephitmp.27 = 1799;
prephitmp.16 = 771;
cstore.13 = 257;
<bb 5>:
*p = cstore.13;
if (n & 2 != 0)
goto <bb 7>;
else
goto <bb 6>;
<bb 6>:
prephitmp.89 = prephitmp.152;
prephitmp.88 = prephitmp.151;
prephitmp.87 = prephitmp.150;
prephitmp.86 = prephitmp.149;
prephitmp.85 = prephitmp.148;
prephitmp.84 = prephitmp.147;
prephitmp.83 = prephitmp.146;
prephitmp.82 = prephitmp.145;
prephitmp.81 = prephitmp.144;
prephitmp.80 = prephitmp.143;
prephitmp.79 = prephitmp.142;
prephitmp.78 = prephitmp.141;
prephitmp.77 = prephitmp.140;
prephitmp.76 = prephitmp.139;
prephitmp.75 = prephitmp.138;
prephitmp.74 = prephitmp.137;
prephitmp.73 = prephitmp.136;
prephitmp.72 = prephitmp.135;
prephitmp.71 = prephitmp.134;
prephitmp.70 = prephitmp.133;
prephitmp.69 = prephitmp.132;
prephitmp.68 = prephitmp.131;
prephitmp.67 = prephitmp.130;
prephitmp.66 = prephitmp.129;
prephitmp.65 = prephitmp.128;
prephitmp.64 = prephitmp.127;
prephitmp.63 = prephitmp.126;
prephitmp.62 = prephitmp.125;
prephitmp.61 = prephitmp.124;
prephitmp.60 = prephitmp.123;
prephitmp.59 = prephitmp.122;
prephitmp.58 = prephitmp.121;
prephitmp.57 = prephitmp.120;
prephitmp.56 = prephitmp.119;
prephitmp.55 = prephitmp.118;
prephitmp.54 = prephitmp.117;
prephitmp.53 = prephitmp.116;
prephitmp.52 = prephitmp.115;
prephitmp.51 = prephitmp.114;
prephitmp.50 = prephitmp.113;
prephitmp.49 = prephitmp.112;
prephitmp.48 = prephitmp.111;
prephitmp.47 = prephitmp.110;
prephitmp.46 = prephitmp.109;
prephitmp.45 = prephitmp.108;
prephitmp.44 = prephitmp.107;
prephitmp.43 = prephitmp.106;
prephitmp.42 = prephitmp.105;
prephitmp.41 = prephitmp.104;
prephitmp.40 = prephitmp.103;
prephitmp.39 = prephitmp.102;
prephitmp.38 = prephitmp.101;
prephitmp.37 = prephitmp.100;
prephitmp.36 = prephitmp.99;
prephitmp.35 = prephitmp.98;
prephitmp.34 = prephitmp.97;
prephitmp.33 = prephitmp.96;
prephitmp.32 = prephitmp.95;
prephitmp.31 = prephitmp.94;
prephitmp.30 = prephitmp.93;
prephitmp.29 = prephitmp.92;
prephitmp.28 = prephitmp.91;
prephitmp.27 = prephitmp.90;
goto <bb 8>;
<bb 7>:
*p = prephitmp.16;
In assembly code, virtually all these "prephitmp" assignments are
spilled to the stack. Since these spills outweigh the benefit of
eliminating redundant loads just before the OR operations, the
resulting code runs slower.
This code explosion comes from PRE.
<bb 2>:
n.0_3 = (int) n_2(D);
D.1263_4 = n.0_3 & 1;
if (D.1263_4 != 0)
goto <bb 19>;
else
goto <bb 3>;
<bb 19>:
goto <bb 4>;
<bb 3>:
<bb 4>:
# cstore.13_46 = PHI <0(3), 257(19)>
# prephitmp.16_157 = PHI <514(3), 771(19)>
# prephitmp.16_158 = PHI <1542(3), 1799(19)>
# prephitmp.16_159 = PHI <3598(3), 3855(19)>
# prephitmp.16_160 = PHI <7710(3), 7967(19)>
# prephitmp.16_161 = PHI <15934(3), 16191(19)>
# prephitmp.16_162 = PHI <32382(3), 32639(19)>
# prephitmp.16_163 = PHI <65278(3), 65535(19)>
# prephitmp.16_164 = PHI <48830(3), 49087(19)>
# prephitmp.16_165 = PHI <24158(3), 24415(19)>
# prephitmp.16_166 = PHI <57054(3), 57311(19)>
# prephitmp.16_167 = PHI <40606(3), 40863(19)>
# prephitmp.16_168 = PHI <11822(3), 12079(19)>
# prephitmp.16_169 = PHI <28270(3), 28527(19)>
# prephitmp.16_170 = PHI <61166(3), 61423(19)>
# prephitmp.16_171 = PHI <44718(3), 44975(19)>
# prephitmp.16_172 = PHI <20046(3), 20303(19)>
# prephitmp.16_173 = PHI <52942(3), 53199(19)>
# prephitmp.16_174 = PHI <36494(3), 36751(19)>
# prephitmp.16_175 = PHI <5654(3), 5911(19)>
# prephitmp.16_176 = PHI <13878(3), 14135(19)>
# prephitmp.16_177 = PHI <30326(3), 30583(19)>
# prephitmp.16_178 = PHI <63222(3), 63479(19)>
# prephitmp.16_179 = PHI <46774(3), 47031(19)>
# prephitmp.16_180 = PHI <22102(3), 22359(19)>
# prephitmp.16_181 = PHI <54998(3), 55255(19)>
# prephitmp.16_182 = PHI <38550(3), 38807(19)>
# prephitmp.16_183 = PHI <9766(3), 10023(19)>
# prephitmp.16_184 = PHI <26214(3), 26471(19)>
# prephitmp.16_185 = PHI <59110(3), 59367(19)>
# prephitmp.16_186 = PHI <42662(3), 42919(19)>
# prephitmp.16_187 = PHI <17990(3), 18247(19)>
# prephitmp.16_188 = PHI <50886(3), 51143(19)>
# prephitmp.16_189 = PHI <34438(3), 34695(19)>
# prephitmp.16_190 = PHI <2570(3), 2827(19)>
# prephitmp.16_191 = PHI <6682(3), 6939(19)>
# prephitmp.16_192 = PHI <14906(3), 15163(19)>
# prephitmp.16_193 = PHI <31354(3), 31611(19)>
# prephitmp.16_194 = PHI <64250(3), 64507(19)>
# prephitmp.16_195 = PHI <47802(3), 48059(19)>
# prephitmp.16_196 = PHI <23130(3), 23387(19)>
# prephitmp.16_197 = PHI <56026(3), 56283(19)>
# prephitmp.16_198 = PHI <39578(3), 39835(19)>
# prephitmp.16_199 = PHI <10794(3), 11051(19)>
# prephitmp.16_200 = PHI <27242(3), 27499(19)>
# prephitmp.16_201 = PHI <60138(3), 60395(19)>
# prephitmp.16_202 = PHI <43690(3), 43947(19)>
# prephitmp.16_203 = PHI <19018(3), 19275(19)>
# prephitmp.16_204 = PHI <51914(3), 52171(19)>
# prephitmp.16_205 = PHI <35466(3), 35723(19)>
# prephitmp.16_206 = PHI <4626(3), 4883(19)>
# prephitmp.16_207 = PHI <12850(3), 13107(19)>
# prephitmp.16_208 = PHI <29298(3), 29555(19)>
# prephitmp.16_209 = PHI <62194(3), 62451(19)>
# prephitmp.16_210 = PHI <45746(3), 46003(19)>
# prephitmp.16_211 = PHI <21074(3), 21331(19)>
# prephitmp.16_212 = PHI <53970(3), 54227(19)>
# prephitmp.16_213 = PHI <37522(3), 37779(19)>
# prephitmp.16_214 = PHI <8738(3), 8995(19)>
# prephitmp.16_215 = PHI <25186(3), 25443(19)>
# prephitmp.16_216 = PHI <58082(3), 58339(19)>
# prephitmp.16_217 = PHI <41634(3), 41891(19)>
# prephitmp.16_218 = PHI <16962(3), 17219(19)>
# prephitmp.16_219 = PHI <49858(3), 50115(19)>
# prephitmp.16_220 = PHI <33410(3), 33667(19)>
# prephitmp.16_221 = PHI <1028(3), 1285(19)>
# prephitmp.16_222 = PHI <3084(3), 3341(19)>
# prephitmp.16_223 = PHI <7196(3), 7453(19)>
# prephitmp.16_224 = PHI <15420(3), 15677(19)>
# prephitmp.16_225 = PHI <31868(3), 32125(19)>
# prephitmp.16_226 = PHI <64764(3), 65021(19)>
# prephitmp.16_227 = PHI <48316(3), 48573(19)>
# prephitmp.16_228 = PHI <23644(3), 23901(19)>
# prephitmp.16_229 = PHI <56540(3), 56797(19)>
# prephitmp.16_230 = PHI <40092(3), 40349(19)>
# prephitmp.16_231 = PHI <11308(3), 11565(19)>
# prephitmp.16_232 = PHI <27756(3), 28013(19)>
# prephitmp.16_233 = PHI <60652(3), 60909(19)>
# prephitmp.16_234 = PHI <44204(3), 44461(19)>
# prephitmp.16_235 = PHI <19532(3), 19789(19)>
# prephitmp.16_236 = PHI <52428(3), 52685(19)>
# prephitmp.16_237 = PHI <35980(3), 36237(19)>
# prephitmp.16_238 = PHI <5140(3), 5397(19)>
# prephitmp.16_239 = PHI <13364(3), 13621(19)>
# prephitmp.16_240 = PHI <29812(3), 30069(19)>
# prephitmp.16_241 = PHI <62708(3), 62965(19)>
# prephitmp.16_242 = PHI <46260(3), 46517(19)>
# prephitmp.16_243 = PHI <21588(3), 21845(19)>
# prephitmp.16_244 = PHI <54484(3), 54741(19)>
# prephitmp.16_245 = PHI <38036(3), 38293(19)>
# prephitmp.16_246 = PHI <9252(3), 9509(19)>
# prephitmp.16_247 = PHI <25700(3), 25957(19)>
# prephitmp.16_248 = PHI <58596(3), 58853(19)>
# prephitmp.16_249 = PHI <42148(3), 42405(19)>
# prephitmp.16_250 = PHI <17476(3), 17733(19)>
# prephitmp.16_251 = PHI <50372(3), 50629(19)>
# prephitmp.16_252 = PHI <33924(3), 34181(19)>
# prephitmp.16_253 = PHI <2056(3), 2313(19)>
# prephitmp.16_254 = PHI <6168(3), 6425(19)>
# prephitmp.16_255 = PHI <14392(3), 14649(19)>
# prephitmp.16_256 = PHI <30840(3), 31097(19)>
# prephitmp.16_257 = PHI <63736(3), 63993(19)>
# prephitmp.16_258 = PHI <47288(3), 47545(19)>
# prephitmp.16_259 = PHI <22616(3), 22873(19)>
# prephitmp.16_260 = PHI <55512(3), 55769(19)>
# prephitmp.16_261 = PHI <39064(3), 39321(19)>
# prephitmp.16_262 = PHI <10280(3), 10537(19)>
# prephitmp.16_263 = PHI <26728(3), 26985(19)>
# prephitmp.16_264 = PHI <59624(3), 59881(19)>
# prephitmp.16_265 = PHI <43176(3), 43433(19)>
# prephitmp.16_266 = PHI <18504(3), 18761(19)>
# prephitmp.16_267 = PHI <51400(3), 51657(19)>
# prephitmp.16_268 = PHI <34952(3), 35209(19)>
# prephitmp.16_269 = PHI <4112(3), 4369(19)>
# prephitmp.16_270 = PHI <12336(3), 12593(19)>
# prephitmp.16_271 = PHI <28784(3), 29041(19)>
# prephitmp.16_272 = PHI <61680(3), 61937(19)>
# prephitmp.16_273 = PHI <45232(3), 45489(19)>
# prephitmp.16_274 = PHI <20560(3), 20817(19)>
# prephitmp.16_275 = PHI <53456(3), 53713(19)>
# prephitmp.16_276 = PHI <37008(3), 37265(19)>
# prephitmp.16_277 = PHI <8224(3), 8481(19)>
# prephitmp.16_278 = PHI <24672(3), 24929(19)>
# prephitmp.16_279 = PHI <57568(3), 57825(19)>
# prephitmp.16_280 = PHI <41120(3), 41377(19)>
# prephitmp.16_281 = PHI <16448(3), 16705(19)>
# prephitmp.16_282 = PHI <49344(3), 49601(19)>
# prephitmp.16_283 = PHI <32896(3), 33153(19)>
*p_1(D) = cstore.13_46;
D.1269_8 = n_2(D) & 2;
if (D.1269_8 != 0)
goto <bb 5>;
else
goto <bb 20>;
<bb 20>:
goto <bb 6>;
<bb 5>:
D.1272_10 = prephitmp.16_157;
*p_1(D) = D.1272_10;
<bb 6>:
# prephitmp.16_284 = PHI <cstore.13_46(20), D.1272_10(5)>
# prephitmp.16_290 = PHI <prephitmp.16_221(20), prephitmp.16_158(5)>
# prephitmp.16_291 = PHI <prephitmp.16_222(20), prephitmp.16_159(5)>
# prephitmp.16_292 = PHI <prephitmp.16_223(20), prephitmp.16_160(5)>
# prephitmp.16_293 = PHI <prephitmp.16_224(20), prephitmp.16_161(5)>
# prephitmp.16_294 = PHI <prephitmp.16_225(20), prephitmp.16_162(5)>
# prephitmp.16_295 = PHI <prephitmp.16_226(20), prephitmp.16_163(5)>
# prephitmp.16_296 = PHI <prephitmp.16_227(20), prephitmp.16_164(5)>
# prephitmp.16_297 = PHI <prephitmp.16_228(20), prephitmp.16_165(5)>
# prephitmp.16_298 = PHI <prephitmp.16_229(20), prephitmp.16_166(5)>
# prephitmp.16_299 = PHI <prephitmp.16_230(20), prephitmp.16_167(5)>
# prephitmp.16_300 = PHI <prephitmp.16_231(20), prephitmp.16_168(5)>
# prephitmp.16_301 = PHI <prephitmp.16_232(20), prephitmp.16_169(5)>
# prephitmp.16_302 = PHI <prephitmp.16_233(20), prephitmp.16_170(5)>
# prephitmp.16_303 = PHI <prephitmp.16_234(20), prephitmp.16_171(5)>
# prephitmp.16_304 = PHI <prephitmp.16_235(20), prephitmp.16_172(5)>
# prephitmp.16_305 = PHI <prephitmp.16_236(20), prephitmp.16_173(5)>
# prephitmp.16_306 = PHI <prephitmp.16_237(20), prephitmp.16_174(5)>
# prephitmp.16_307 = PHI <prephitmp.16_238(20), prephitmp.16_175(5)>
# prephitmp.16_308 = PHI <prephitmp.16_239(20), prephitmp.16_176(5)>
# prephitmp.16_309 = PHI <prephitmp.16_240(20), prephitmp.16_177(5)>
# prephitmp.16_310 = PHI <prephitmp.16_241(20), prephitmp.16_178(5)>
# prephitmp.16_311 = PHI <prephitmp.16_242(20), prephitmp.16_179(5)>
# prephitmp.16_312 = PHI <prephitmp.16_243(20), prephitmp.16_180(5)>
# prephitmp.16_313 = PHI <prephitmp.16_244(20), prephitmp.16_181(5)>
# prephitmp.16_314 = PHI <prephitmp.16_245(20), prephitmp.16_182(5)>
# prephitmp.16_315 = PHI <prephitmp.16_246(20), prephitmp.16_183(5)>
# prephitmp.16_316 = PHI <prephitmp.16_247(20), prephitmp.16_184(5)>
# prephitmp.16_317 = PHI <prephitmp.16_248(20), prephitmp.16_185(5)>
# prephitmp.16_318 = PHI <prephitmp.16_249(20), prephitmp.16_186(5)>
# prephitmp.16_319 = PHI <prephitmp.16_250(20), prephitmp.16_187(5)>
# prephitmp.16_320 = PHI <prephitmp.16_251(20), prephitmp.16_188(5)>
# prephitmp.16_321 = PHI <prephitmp.16_252(20), prephitmp.16_189(5)>
# prephitmp.16_322 = PHI <prephitmp.16_253(20), prephitmp.16_190(5)>
# prephitmp.16_323 = PHI <prephitmp.16_254(20), prephitmp.16_191(5)>
# prephitmp.16_324 = PHI <prephitmp.16_255(20), prephitmp.16_192(5)>
# prephitmp.16_325 = PHI <prephitmp.16_256(20), prephitmp.16_193(5)>
# prephitmp.16_326 = PHI <prephitmp.16_257(20), prephitmp.16_194(5)>
# prephitmp.16_327 = PHI <prephitmp.16_258(20), prephitmp.16_195(5)>
# prephitmp.16_328 = PHI <prephitmp.16_259(20), prephitmp.16_196(5)>
# prephitmp.16_329 = PHI <prephitmp.16_260(20), prephitmp.16_197(5)>
# prephitmp.16_330 = PHI <prephitmp.16_261(20), prephitmp.16_198(5)>
# prephitmp.16_331 = PHI <prephitmp.16_262(20), prephitmp.16_199(5)>
# prephitmp.16_332 = PHI <prephitmp.16_263(20), prephitmp.16_200(5)>
# prephitmp.16_333 = PHI <prephitmp.16_264(20), prephitmp.16_201(5)>
# prephitmp.16_334 = PHI <prephitmp.16_265(20), prephitmp.16_202(5)>
# prephitmp.16_335 = PHI <prephitmp.16_266(20), prephitmp.16_203(5)>
# prephitmp.16_336 = PHI <prephitmp.16_267(20), prephitmp.16_204(5)>
# prephitmp.16_337 = PHI <prephitmp.16_268(20), prephitmp.16_205(5)>
# prephitmp.16_338 = PHI <prephitmp.16_269(20), prephitmp.16_206(5)>
# prephitmp.16_339 = PHI <prephitmp.16_270(20), prephitmp.16_207(5)>
# prephitmp.16_340 = PHI <prephitmp.16_271(20), prephitmp.16_208(5)>
# prephitmp.16_341 = PHI <prephitmp.16_272(20), prephitmp.16_209(5)>
# prephitmp.16_342 = PHI <prephitmp.16_273(20), prephitmp.16_210(5)>
# prephitmp.16_343 = PHI <prephitmp.16_274(20), prephitmp.16_211(5)>
# prephitmp.16_344 = PHI <prephitmp.16_275(20), prephitmp.16_212(5)>
# prephitmp.16_345 = PHI <prephitmp.16_276(20), prephitmp.16_213(5)>
# prephitmp.16_346 = PHI <prephitmp.16_277(20), prephitmp.16_214(5)>
# prephitmp.16_347 = PHI <prephitmp.16_278(20), prephitmp.16_215(5)>
# prephitmp.16_348 = PHI <prephitmp.16_279(20), prephitmp.16_216(5)>
# prephitmp.16_349 = PHI <prephitmp.16_280(20), prephitmp.16_217(5)>
# prephitmp.16_350 = PHI <prephitmp.16_281(20), prephitmp.16_218(5)>
# prephitmp.16_351 = PHI <prephitmp.16_282(20), prephitmp.16_219(5)>
# prephitmp.16_352 = PHI <prephitmp.16_283(20), prephitmp.16_220(5)>
D.1273_11 = n_2(D) & 4;
if (D.1273_11 != 0)
goto <bb 7>;
else
goto <bb 21>;
<bb 21>:
goto <bb 8>;
<bb 7>:
D.1267_12 = prephitmp.16_284;
D.1276_13 = prephitmp.16_290;
*p_1(D) = D.1276_13;
<bb 8>:
# prephitmp.16_285 = PHI <prephitmp.16_284(21), D.1276_13(7)>
# prephitmp.16_353 = PHI <prephitmp.16_322(21), prephitmp.16_291(7)>
# prephitmp.16_354 = PHI <prephitmp.16_323(21), prephitmp.16_292(7)>
# prephitmp.16_355 = PHI <prephitmp.16_324(21), prephitmp.16_293(7)>
# prephitmp.16_356 = PHI <prephitmp.16_325(21), prephitmp.16_294(7)>
# prephitmp.16_357 = PHI <prephitmp.16_326(21), prephitmp.16_295(7)>
# prephitmp.16_358 = PHI <prephitmp.16_327(21), prephitmp.16_296(7)>
# prephitmp.16_359 = PHI <prephitmp.16_328(21), prephitmp.16_297(7)>
# prephitmp.16_360 = PHI <prephitmp.16_329(21), prephitmp.16_298(7)>
# prephitmp.16_361 = PHI <prephitmp.16_330(21), prephitmp.16_299(7)>
# prephitmp.16_362 = PHI <prephitmp.16_331(21), prephitmp.16_300(7)>
# prephitmp.16_363 = PHI <prephitmp.16_332(21), prephitmp.16_301(7)>
# prephitmp.16_364 = PHI <prephitmp.16_333(21), prephitmp.16_302(7)>
# prephitmp.16_365 = PHI <prephitmp.16_334(21), prephitmp.16_303(7)>
# prephitmp.16_366 = PHI <prephitmp.16_335(21), prephitmp.16_304(7)>
# prephitmp.16_367 = PHI <prephitmp.16_336(21), prephitmp.16_305(7)>
# prephitmp.16_368 = PHI <prephitmp.16_337(21), prephitmp.16_306(7)>
# prephitmp.16_369 = PHI <prephitmp.16_338(21), prephitmp.16_307(7)>
# prephitmp.16_370 = PHI <prephitmp.16_339(21), prephitmp.16_308(7)>
# prephitmp.16_371 = PHI <prephitmp.16_340(21), prephitmp.16_309(7)>
# prephitmp.16_372 = PHI <prephitmp.16_341(21), prephitmp.16_310(7)>
# prephitmp.16_373 = PHI <prephitmp.16_342(21), prephitmp.16_311(7)>
# prephitmp.16_374 = PHI <prephitmp.16_343(21), prephitmp.16_312(7)>
# prephitmp.16_375 = PHI <prephitmp.16_344(21), prephitmp.16_313(7)>
# prephitmp.16_376 = PHI <prephitmp.16_345(21), prephitmp.16_314(7)>
# prephitmp.16_377 = PHI <prephitmp.16_346(21), prephitmp.16_315(7)>
# prephitmp.16_378 = PHI <prephitmp.16_347(21), prephitmp.16_316(7)>
# prephitmp.16_379 = PHI <prephitmp.16_348(21), prephitmp.16_317(7)>
# prephitmp.16_380 = PHI <prephitmp.16_349(21), prephitmp.16_318(7)>
# prephitmp.16_381 = PHI <prephitmp.16_350(21), prephitmp.16_319(7)>
# prephitmp.16_382 = PHI <prephitmp.16_351(21), prephitmp.16_320(7)>
# prephitmp.16_383 = PHI <prephitmp.16_352(21), prephitmp.16_321(7)>
D.1277_14 = n_2(D) & 8;
if (D.1277_14 != 0)
goto <bb 9>;
else
goto <bb 22>;
<bb 22>:
goto <bb 10>;
<bb 9>:
D.1267_15 = prephitmp.16_285;
D.1280_16 = prephitmp.16_353;
*p_1(D) = D.1280_16;
Essentially, the first set of PHI nodes, those at <bb 4>, pre-computes
all possible eventual values of "*p". The subsequent PHI nodes
"prune" those possibilities.
While compiler optimizations are not always profitable, we should
probably prevent exponential code size growth at least. Note that the
total number of PHI nodes (and code size) is roughly O(2^n), where n
is the number of "if" statements likes ones in the testcase above.
--
Summary: PRE backfires when given a sequence of "if" statements
Product: gcc
Version: 4.5.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: tree-optimization
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: kazu at gcc dot gnu dot org
GCC build triplet: i686-pc-linux-gnu
GCC host triplet: i686-pc-linux-gnu
GCC target triplet: arm-none-eabi
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40768
