[Bug tree-optimization/48837] [4.4/4.5/4.6/4.6 Regression] Wrong optimization of recursive function calls
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48837 --- Comment #9 from Zdenek Dvorak rakdver at gcc dot gnu.org 2011-05-07 19:43:21 UTC --- Author: rakdver Date: Sat May 7 19:43:18 2011 New Revision: 173534 URL: http://gcc.gnu.org/viewcvs?root=gccview=revrev=173534 Log: PR tree-optimization/48837 * tree-tailcall.c (tree_optimize_tail_calls_1): Do not mark tailcalls when accumulator transformation is performed. * gcc.dg/pr48837.c: New testcase. Added: trunk/gcc/testsuite/gcc.dg/pr48837.c Modified: trunk/gcc/ChangeLog trunk/gcc/testsuite/ChangeLog trunk/gcc/tree-tailcall.c
[Bug tree-optimization/48837] [4.4/4.5/4.6/4.6 Regression] Wrong optimization of recursive function calls
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48837 --- Comment #8 from Zdenek Dvorak rakdver at gcc dot gnu.org 2011-05-04 08:33:51 UTC --- Created attachment 24177 -- http://gcc.gnu.org/bugzilla/attachment.cgi?id=24177 Fix for the issue Indeed, once the accumulator transformation is performed, the other tail calls in the function are moved to non-tail positions.
[Bug tree-optimization/48837] [4.4/4.5/4.6/4.6 Regression] Wrong optimization of recursive function calls
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48837 Steven Bosscher steven at gcc dot gnu.org changed: What|Removed |Added Target Milestone|--- |4.3.6
[Bug tree-optimization/48837] [4.4/4.5/4.6/4.6 Regression] Wrong optimization of recursive function calls
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48837 Steven Bosscher steven at gcc dot gnu.org changed: What|Removed |Added CC||steven at gcc dot gnu.org --- Comment #4 from Steven Bosscher steven at gcc dot gnu.org 2011-05-01 19:01:45 UTC --- Works with -fno-optimize-sibling-calls. Looks like this has something to do with the accumulators optimization in tree-tailcall.c
[Bug tree-optimization/48837] [4.4/4.5/4.6/4.6 Regression] Wrong optimization of recursive function calls
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48837
--- Comment #5 from Steven Bosscher steven at gcc dot gnu.org 2011-05-01
19:24:06 UTC ---
Function foo from .143.expand dump:
;; Function int foo(int, int) (_Z3fooii)
int foo(int, int) (int a, int b)
{
int acc_tmp.13;
int add_acc.12;
int D.2091;
int D.2085;
int D.2081;
# BLOCK 2 freq:6950
# PRED: ENTRY [100.0%] (fallthru,exec)
# a_1 = PHI a_2(D)(0)
# b_7 = PHI b_3(D)(0)
# add_acc.12_21 = PHI 0(0)
# SUCC: 3 [100.0%] (fallthru)
# BLOCK 3 freq:1
# PRED: 2 [100.0%] (fallthru) 5 [100.0%] (fallthru,dfs_back,exec)
# a_14 = PHI a_1(2), a_23(5)
# b_22 = PHI b_7(2), b_25(5)
# add_acc.12_19 = PHI add_acc.12_21(2), add_acc.12_12(5)
D.2085_4 = b_22 | a_14;
if (D.2085_4 != 0)
goto bb 4;
else
goto bb 5;
# SUCC: 4 [39.0%] (true,exec) 5 [61.0%] (false,exec)
# BLOCK 4 freq:3900
# PRED: 3 [39.0%] (true,exec)
D.2081_5 = baz (); [tail call]
acc_tmp.13_10 = D.2081_5 + add_acc.12_19;
return acc_tmp.13_10;
# SUCC: EXIT [100.0%]
# BLOCK 5 freq:3050
# PRED: 3 [61.0%] (false,exec)
Invalid sum of incoming frequencies 6100, should be 3050
D.2091_8 = foo (0, 1);
add_acc.12_12 = add_acc.12_19 + D.2091_8;
a_23 = 1;
b_25 = 0;
goto bb 3;
# SUCC: 3 [100.0%] (fallthru,dfs_back,exec)
}
Invalid sum of incoming frequencies 3900, should be 6950
(Note, someone is not updating the CFG properly, see incorrect profile info.
This is caused by VRP, the mismatch appears first in the .vrp1 dump.)
The PHI nodes in basic block 3 show that the + foo(1,0) part of foo() has
been transformed from a recursive call into a loop inside foo.
We enter the function with a==0 and b==0 so control flow is as follows:
BB2 - BB3 - BB5 (because (a | b) == 0) -
D.2091_8 = foo(0, 1)// D.2091_8 = 1
add_acc = 0 (from the PHI in BB2) + 1 = 1
- BB3 with a=1 and b=0 - BB4 -
D.2081_5 = baz () [tail call] // D.2081_5 = 1
acc_tmp.13_10 = 1 + add_acc.12_19 = 1 + 1 = 2
return acc_tmp.13_10// return 2
That looks correct to me, but foo(0,0) returns 1 instead of 2. Both foo(0,1)
and foo(1,0) both return 1 as expected.
I think the problem is in RTL expansion of the tail call in basic block 4,
which doesn't look like a tail call to me. The RTL generated for basic block 4
is this:
;; Generating RTL for gimple basic block 4
;; D.2081_5 = baz (); [tail call]
(call_insn/u/j 13 12 14 4 (set (reg:SI 0 ax)
(call (mem:QI (symbol_ref:DI (_Z3bazv) [flags 0x3] function_decl
0x7722c100 baz) [0 baz S1 A8])
(const_int 0 [0]))) t.cc:14 -1
(expr_list:REG_EH_REGION (const_int 0 [0])
(nil))
(nil))
(barrier 14 13 0)
The acc_tmp.13_10 = D.2081_5 + add_acc.12_19; part is lost.
[Bug tree-optimization/48837] [4.4/4.5/4.6/4.6 Regression] Wrong optimization of recursive function calls
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48837
--- Comment #6 from Steven Bosscher steven at gcc dot gnu.org 2011-05-01
19:56:37 UTC ---
In the tail recursion optimization:
Breakpoint 3, gimple_call_set_tail (s=0x77ed3680, tail_p=1 '\001') at
../../trunk/gcc/gimple.h:2241
2241 GIMPLE_CHECK (s, GIMPLE_CALL);
(gdb) bt 2
#0 gimple_call_set_tail (s=0x77ed3680, tail_p=1 '\001') at
../../trunk/gcc/gimple.h:2241
#1 0x00f6d5a3 in optimize_tail_call (t=0x1cd7820, opt_tailcalls=1
'\001') at ../../trunk/gcc/tree-tailcall.c:917
(More stack frames follow...)
(gdb) up
#1 0x00f6d5a3 in optimize_tail_call (t=0x1cd7820, opt_tailcalls=1
'\001') at ../../trunk/gcc/tree-tailcall.c:917
917 gimple_call_set_tail (stmt, true);
(gdb) l
912
913 if (opt_tailcalls)
914 {
915 gimple stmt = gsi_stmt (t-call_gsi);
916
917 gimple_call_set_tail (stmt, true);
918 if (dump_file (dump_flags TDF_DETAILS))
919 {
920 fprintf (dump_file, Found tail call );
921 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
(gdb) disp debug_bb_n(5)
3: debug_bb_n (5) = ;; basic block 5, loop depth 0, count 0
;; prev block 4, next block 1
;; pred: 3 [100.0%] (fallthru,exec)
;; succ: EXIT [100.0%]
bb 5:
Invalid sum of incoming frequencies 3900, should be 6950
# D.2081_1 = PHI D.2081_5(3)
return D.2081_1;
(struct basic_block_def *) 0x77227548
(gdb) p debug_bb_n(3)
;; basic block 3, loop depth 0, count 0
;; prev block 2, next block 4
;; pred: 2 [39.0%] (true,exec)
;; succ: 5 [100.0%] (fallthru,exec)
bb 3:
D.2081_5 = baz (); [tail call]
goto bb 5;
$9 = (struct basic_block_def *) 0x77227478
(gdb)
So far so good. But now compensation code must be inserted for the
recursive-call-turned-loop:
(gdb)
3: debug_bb_n (5) = ;; basic block 5, loop depth 0, count 0
;; prev block 4, next block 1
;; pred: 3 [100.0%] (fallthru,exec)
;; succ: EXIT [100.0%]
bb 5:
Invalid sum of incoming frequencies 3900, should be 6950
# D.2081_1 = PHI D.2081_5(3)
return D.2081_1;
(struct basic_block_def *) 0x77227548
(gdb)
1040adjust_return_value (e-src, m_acc, a_acc);
3: debug_bb_n (5) = ;; basic block 5, loop depth 0, count 0
;; prev block 4, next block 1
;; pred: 3 [100.0%] (fallthru,exec)
;; succ: EXIT [100.0%]
bb 5:
Invalid sum of incoming frequencies 3900, should be 6950
# D.2081_1 = PHI D.2081_5(3)
return D.2081_1;
(struct basic_block_def *) 0x77227548
(gdb)
1034 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR-preds)
3: debug_bb_n (5) = ;; basic block 5, loop depth 0, count 0
;; prev block 4, next block 1
;; pred: 3 [100.0%] (fallthru,exec)
;; succ: EXIT [100.0%]
bb 5:
Invalid sum of incoming frequencies 3900, should be 6950
# D.2081_1 = PHI D.2081_5(3)
acc_tmp.13_10 = add_acc.12_19 + D.2081_1;
return acc_tmp.13_10;
(struct basic_block_def *) 0x77227548
(gdb)
(I don't see now r127491 can be the cause of this, FWIW.)
[Bug tree-optimization/48837] [4.4/4.5/4.6/4.6 Regression] Wrong optimization of recursive function calls
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48837 Steven Bosscher steven at gcc dot gnu.org changed: What|Removed |Added CC||rakdver at kam dot ||mff.cuni.cz --- Comment #7 from Steven Bosscher steven at gcc dot gnu.org 2011-05-01 20:24:11 UTC --- Zdenek, this problem is caused by your work to handle addends/multiplicands in tree-tailcall.c. It looks like an interaction problem between tail-calls and tail-recursion, where elimination tail recursion turns a tail-call into a normal call.
