public inbox for gcc@gcc.gnu.org
 help / color / mirror / Atom feed
* missing conditional propagation in cprop.c pass
@ 2011-09-27 14:56 Amker.Cheng
  2011-09-29 14:25 ` Amker.Cheng
  2011-09-29 15:26 ` Paulo J. Matos
  0 siblings, 2 replies; 17+ messages in thread
From: Amker.Cheng @ 2011-09-27 14:56 UTC (permalink / raw)
  To: gcc

Hi,
I ran into a case and found conditional (const) propagation is
mishandled in cprop pass.
With following insn sequence after cprop1 pass:
----------------------------------------------------
(note 878 877 880 96 [bb 96] NOTE_INSN_BASIC_BLOCK)

(insn 882 881 883 96 (set (reg:CC 24 cc)
        (compare:CC (reg:SI 684 [ default_num_contexts ])
            (const_int 0 [0]))) core_main.c:265 211 {*arm_cmpsi_insn}
     (nil))

(jump_insn 883 882 886 96 (set (pc)
        (if_then_else (ne (reg:CC 24 cc)
                (const_int 0 [0]))
            (label_ref:SI 905)
            (pc))) core_main.c:265 223 {*arm_cond_branch}
     (expr_list:REG_DEAD (reg:CC 24 cc)
        (expr_list:REG_BR_PROB (const_int 9100 [0x238c])
            (nil)))
 -> 905)

(note 886 883 49 97 [bb 97] NOTE_INSN_BASIC_BLOCK)

(insn 49 886 0 97 (set (reg/v:SI 291 [ total_errors ])
        (reg:SI 684 [ default_num_contexts ])) core_main.c:265 709
{*thumb2_movsi_insn}
     (expr_list:REG_DEAD (reg:SI 684 [ default_num_contexts ])
        (expr_list:REG_EQUAL (const_int 0 [0])
            (nil))))
......

(code_label 905 54 904 47 54 "" [1 uses])

(note 904 905 46 47 [bb 47] NOTE_INSN_BASIC_BLOCK)

(insn 46 904 47 47 (set (reg/v:SI 291 [ total_errors ])
        (const_int 0 [0])) core_main.c:265 709 {*thumb2_movsi_insn}
     (nil))
----------------------------------------------------

The insn49 should be propagated with conditional const from insn882
and jump_insn883, optimized into "r291<-0" as following code, then let
pre do redundancy elimination work.
----------------------------------------------------
(note 878 877 880 96 [bb 96] NOTE_INSN_BASIC_BLOCK)

(insn 882 881 883 96 (set (reg:CC 24 cc)
        (compare:CC (reg:SI 684 [ default_num_contexts ])
            (const_int 0 [0]))) core_main.c:265 211 {*arm_cmpsi_insn}
     (nil))

(jump_insn 883 882 886 96 (set (pc)
        (if_then_else (ne (reg:CC 24 cc)
                (const_int 0 [0]))
            (label_ref:SI 905)
            (pc))) core_main.c:265 223 {*arm_cond_branch}
     (expr_list:REG_DEAD (reg:CC 24 cc)
        (expr_list:REG_BR_PROB (const_int 9100 [0x238c])
            (nil)))
 -> 905)

(note 886 883 49 97 [bb 97] NOTE_INSN_BASIC_BLOCK)

(insn 49 886 0 97 (set (reg/v:SI 291 [ total_errors ])
        (const_int 0 [0])) core_main.c:265 709 {*thumb2_movsi_insn}
     (expr_list:REG_DEAD (reg:SI 684 [ default_num_contexts ])
        (expr_list:REG_EQUAL (const_int 0 [0])
            (nil))))
......

(code_label 905 54 904 47 54 "" [1 uses])

(note 904 905 46 47 [bb 47] NOTE_INSN_BASIC_BLOCK)

(insn 46 904 47 47 (set (reg/v:SI 291 [ total_errors ])
        (const_int 0 [0])) core_main.c:265 709 {*thumb2_movsi_insn}
     (nil))
----------------------------------------------------

The problem is function one_cprop_pass does local const/copy
propagation pass first, then the global pass, which only handles
global opportunities.
Though conditional const information "r684 <- 0" is collected by
find_implicit_sets, the conditional information is recorded as local
information of bb 97, and it is not recorded in avout of bb 96, so not
in avin of bb 97 either.

Unfortunately, the global pass only considers potential opportunities
from avin of each basic block in function cprop_insn and
find_avail_set.

That's why the conditional propagation opportunity in bb 97 is missed.

I worked a patch to fix this, and wanna hear more suggestions on this topic.
Is it a bug or I missed something important?

Thanks

BTW, I'm using gcc mainline which configured for arm-none-eabi target.

^ permalink raw reply	[flat|nested] 17+ messages in thread
* Re: missing conditional propagation in cprop.c pass
@ 2011-10-03 22:30 Steven Bosscher
  2011-10-10 10:29 ` Amker.Cheng
  0 siblings, 1 reply; 17+ messages in thread
From: Steven Bosscher @ 2011-10-03 22:30 UTC (permalink / raw)
  To: Jeff Law, Amker.Cheng; +Cc: Rahul Kharche, Paulo J. Matos, GCC Mailing List

Hi,

> Though conditional const information "r684 <- 0" is collected by
> find_implicit_sets, the conditional information is recorded as local
> information of bb 97, and it is not recorded in avout of bb 96, so not
> in avin of bb 97 either.

To have the set in avout of bb 96 would be wrong because the set is
only available on the edge from bb 96 to bb 97, but not on the edge
from bb 96 to bb 47.

What should be done about this, is to add the implicit sets to AVIN of
the block that the implicit set is recorded for. You have to do this
after calling lcm.c's compute_available() because the normal
"available expressions" problem in its basic block based form cannot
handle implicit sets. I think something like the patch below
(completely untested, of course ;-) will be necessary to fix this
problem.

If you file a PR with a test case, and assign it to me, I'll have a
closer look and I'll see if I can come up with a proper patch.

Ciao!
Steven



Index: cprop.c
===================================================================
--- cprop.c     (revision 179480)
+++ cprop.c     (working copy)
@@ -641,9 +641,33 @@
 static void
 compute_cprop_data (void)
 {
+  basic_block bb;
+
   compute_local_properties (cprop_absaltered, cprop_pavloc, &set_hash_table);
   compute_available (cprop_pavloc, cprop_absaltered,
                     cprop_avout, cprop_avin);
+
+  /* Merge implicit sets into CPROP_AVIN.  Implicit sets are always
+     available at the head of the basic block they are recorded for.  */
+  FOR_EACH_BB (bb)
+    {
+      if (implicit_sets[bb->index] != NULL_RTX)
+       {
+         rtx implicit_set = implicit_sets[bb->index];
+         int regno = REGNO (SET_DEST (implicit_set));
+         struct expr *set = lookup_set (regno, &set_hash_table);
+
+         /* Find the set that is computed in BB.  */
+         while (set)
+           {
+             if (TEST_BIT (cprop_pavloc[bb->index], set->bitmap_index))
+               break;
+             set = next_set (regno, set);
+           }
+         gcc_assert (set);
+         SET_BIT (cprop_avin[bb->index], set->bitmap_index);
+       }
+    }
 }
 ♀
 /* Copy/constant propagation.  */

^ permalink raw reply	[flat|nested] 17+ messages in thread
end of thread, other threads:[~2011-10-10  7:06 UTC | newest]

Thread overview: 17+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-09-27 14:56 missing conditional propagation in cprop.c pass Amker.Cheng
2011-09-29 14:25 ` Amker.Cheng
2011-09-29 15:26 ` Paulo J. Matos
2011-09-29 15:37   ` Amker.Cheng
2011-09-29 15:38     ` Rahul Kharche
2011-09-29 15:39       ` Bernd Schmidt
2011-09-29 16:06         ` Jeff Law
2011-09-29 18:38           ` Bernd Schmidt
2011-09-29 22:46             ` Rahul Kharche
2011-09-30  1:51               ` Jeff Law
2011-09-29 17:20       ` Jeff Law
2011-09-30 13:01         ` Amker.Cheng
2011-10-03 18:02           ` Jeff Law
2011-09-30  2:51     ` Paulo J. Matos
2011-09-30  9:00       ` Amker.Cheng
2011-10-03 22:30 Steven Bosscher
2011-10-10 10:29 ` Amker.Cheng

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).