This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [tree-ssa] More jump threading improvements
On Sat, Jan 24, 2004 at 09:57:26PM -0700, law@redhat.com wrote:
> >
> >The analyzer was expected to answer the following:
> >a -> {{22, +, 7}_1, +, 1}_2
> >
> >but after the merge, the analyzer answers:
> >a -> {{22, +, 8}_1, +, 1}_2
> >
> >that means that the variable A has a step 8 in the loop 1 instead of a
> >step 7. After having investigated a little, on another example that
> >showed the same bogus behaviour,
> Well, I can't really help with this part since I'm not familiar with the
> analysis code.
>
Well, that part was just for the "short story" about how I get into
all this.
> >
> >int main(void)
> >{
> > int a = 0;
> > int b;
> > while (a < 50)
> > {
> > for (b = 0; b < 10; b++)
> > {
> > a++;
> > }
> > a++;
> > }
> >}
> >
> >I discovered that the dom-pass transforms the statement of the outer loop
> >
> > a_6 = a_1 + 1;
> >into
> > a_15 = a_1 + 2;
> Err, no, you need to look at it more closely.
>
I did before posting this first mail, and rechecked after several
times. Let me explain in more details why I think this is an unsafe
transformation...
>
> >see the representation before and after the dom pass below. An
> >interesting thing is that when the inner loop contains a statement
> >with a different step: say "a += 3", the result after the dom pass is
> >"a_15 = a_1 + 4".
> >
> Of course. Again, it's following the use-def chains and transformaing
>
> a_X = a_Y + 1;
>
> [ ... ]
>
> a_Z = a_X + 1;
>
> into
>
> a_X = a_Y + 1;
>
> [ ... ]
>
> a_Z = a_Y + 2;
>
... the important thing is that "a_X = a_Y + 1;" is in a loop
structure and it is executed several times...
>
> >I don't know enough about the dom pass in order to completely diagnose
> >this case, but it seems related to the recent changes to this pass.
> >If you want I can track this behavior down to the patch that introduced it.
> >
> >Sebastian
> >
> >
> >The representation before the "dom" pass:
> >
> >main ()
> >{
> > int b;
> > int a;
> >
> > # BLOCK 0
> > # PRED: ENTRY (fallthru)
> > a_4 = 0;
> > goto <bb 5> (<L4>);
> > # SUCC: 5 (fallthru)
> >
> > # BLOCK 1
> > # PRED: 5 (true)
> ><L0>:;
> > b_5 = 0;
> > goto <bb 3> (<L2>);
> > # SUCC: 3 (fallthru)
> >
> > # BLOCK 2
> > # PRED: 3 (true)
> ><L1>:;
> > a_7 = a_1 + 1;
> > b_8 = b_3 + 1;
> > # SUCC: 3 (fallthru)
> >
> > # BLOCK 3
> > # PRED: 2 (fallthru) 1 (fallthru)
> > # b_3 = PHI <b_5(1), b_8(2)>;
> > # a_1 = PHI <a_2(1), a_7(2)>;
> ><L2>:;
> > if (b_3 <= 9) goto <L1>; else goto <L3>;
> > # SUCC: 4 (false) 2 (true)
> >
> > # BLOCK 4
> > # PRED: 3 (false)
> ><L3>:;
> > a_6 = a_1 + 1;
> > # SUCC: 5 (fallthru)
> >
> > # BLOCK 5
> > # PRED: 4 (fallthru) 0 (fallthru)
> > # a_2 = PHI <a_4(0), a_6(4)>;
> ><L4>:;
> > if (a_2 <= 49) goto <L0>; else goto <L5>;
> > # SUCC: 6 (false) 1 (true)
> >
> > # BLOCK 6
> > # PRED: 5 (false)
> ><L5>:;
> > return;
> > # SUCC: EXIT
> >
> >}
> >
> >and the representation after the "dom" pass:
> >
> >main ()
> >{
> > int b;
> > int a;
> >
> > # BLOCK 0
> > # PRED: ENTRY (fallthru)
> > a_9 = 0;
> > a_10 = 0;
> > # SUCC: 1 (fallthru)
> >
> > # BLOCK 1
> > # PRED: 0 (fallthru) 3 (true)
> > # a_2 = PHI <0(0), a_15(3)>;
> ><L0>:;
> > b_11 = 0;
> > b_12 = 0;
> > # SUCC: 2 (fallthru)
> >
> > # BLOCK 2
> > # PRED: 1 (fallthru) 2 (true)
> > # b_3 = PHI <0(1), b_14(2)>;
> > # a_1 = PHI <a_2(1), a_13(2)>;
> ><L1>:;
> > a_13 = a_1 + 1;
> > b_14 = b_3 + 1;
> > if (b_14 <= 9) goto <L1>; else goto <L3>;
> > # SUCC: 3 (false) 2 (true)
> >
> > # BLOCK 3
> > # PRED: 2 (false)
> ><L3>:;
> > a_15 = a_1 + 2;
> > if (a_15 <= 49) goto <L0>; else goto <L5>;
> > # SUCC: 4 (false) 1 (true)
> >
> > # BLOCK 4
> > # PRED: 3 (false)
> ><L5>:;
> > return;
> > # SUCC: EXIT
>
> I'm not sure what about this you think is wrong. It looks like a
> perfectly legitimate translation of your source code.
>
> Note carefully the statement you pointed out
>
> a_15 = a_1 + 2
>
> Uses "a_1", not "a_13".
>
>
> Basically we had
>
> a_15 = a_13 + 1;
>
>
> We followed the use-def chain for a_13 to the statement a_13 = a_1 + 1 and
> substituted a_1 + 1 for a_13. This resulted in
>
> a_15 = (a_1 + 1) + 1;
>
... and this should have been:
a_15 = (a_1 + 1 * number_of_iterations_in_loop (loop_2)) + 1;
a_15 = (a_1 + 10) + 1;
> Which we then folded into
>
> a_15 = a_1 + 2
>
... and after folding, we _have to_ end on:
a_15 = a_1 + 11
that is, the initial condition before the loop_2: "a_1", plus the
overall effect of the loop_2 on the evolution of the variable A after
crossing the loop_2, plus the increment of the loop_1.
Sebastian