This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] Fix cfg around tablejumps after tree_expand_cfg (PR rtl-optimization/18861)


Hi!

The testcase below has proper number of succs for switch bb's at the tree

level:
  # BLOCK 1
  # PRED: 0 [50.0%]  (true,exec)
<L0>:;
  switch (codeD.1118)
    {
      case 3: goto <L1>;
      case 4: goto <L2>;
      case 5: goto <L3>;
      case 6: goto <L4>;
      case 7: goto <L5>;
      case 8: goto <L23>;
      default : goto <L7>;
    }
  # SUCC: 2 [14.3%]  (exec) 3 [14.3%]  (exec) 4 [14.3%]  (exec) 5 [14.3%]  (exec) 6 [14.3%]  (exec) 20 [14.3%]  (exec) 7 [14.3%]  (exec)
...
  # BLOCK 7
  # PRED: 1 [14.3%]  (exec)
<L7>:;
  #   VUSE <.GLOBAL_VARD.1158_16>;
  abort ();
  # SUCC:

but when it is expanded into RTL, the basic block with the tablejump
instruction that can't reach the default label has that default:
basic block still listed as successor:

Basic block 1 prev 0, next 2, loop_depth 0, count 0, freq 5000, maybe hot.
Predecessors:  0 [50.0%]  (fallthru)
Successors:  3 [50.0%]  2 [50.0%]  (fallthru)

Basic block 2 prev 1, next 3, loop_depth 0, count 0, freq 2500, maybe hot.
Predecessors:  1 [50.0%]  (fallthru)
Successors:  7 [14.3%]  8 [14.3%]  9 [14.3%]  10 [14.3%]  11 [14.3%]  12 [14.3%]  3 [14.3%]

;; Start of basic block 1, registers live: (nil)
...
(jump_insn 19 18 94 1 (set (pc)
        (if_then_else (gtu (reg:CC 17 flags)
                (const_int 0 [0x0]))
            (label_ref 27)
            (pc))) 337 {*jcc_1} (nil)
    (expr_list:REG_BR_PROB (const_int 5000 [0x1388])
        (nil)))
;; End of basic block 1, registers live:
 (nil)

;; Start of basic block 2, registers live: (nil)
(note 94 19 21 2 [bb 2] NOTE_INSN_BASIC_BLOCK)

(insn 21 94 22 2 (set (reg:SI 63)
        (mem/u/c:SI (plus:SI (mult:SI (reg:SI 61)
                    (const_int 4 [0x4]))
                (label_ref:SI 24)) [0 S4 A8])) 35 {*movsi_1} (nil)
    (insn_list:REG_LABEL 24 (nil)))

(jump_insn 22 21 23 2 (parallel [
            (set (pc)
                (reg:SI 63))
            (use (label_ref 24))
        ]) 353 {*tablejump_1} (nil)
    (nil))
;; End of basic block 2, registers live:
 (nil)

(barrier 23 22 24)

;; Insn is not within a basic block
(code_label 24 23 25 11 "" [2 uses])

;; Insn is not within a basic block
(jump_insn 25 24 26 (addr_vec:SI [
            (label_ref:SI 50)
            (label_ref:SI 55)
            (label_ref:SI 60)
            (label_ref:SI 65)
            (label_ref:SI 70)
            (label_ref:SI 75)
        ]) -1 (nil)
    (nil))

(barrier 26 25 27)

;; Start of basic block 3, registers live: (nil)
(code_label 27 26 28 3 4 "" [1 uses])

(note 28 27 30 3 [bb 3] NOTE_INSN_BASIC_BLOCK)

(call_insn 30 28 31 3 (call (mem:QI (symbol_ref:SI ("abort") [flags 0x41] <function_decl 0xf7d1fca8 abort>) [0 S1 A8])
        (const_int 0 [0x0])) -1 (nil)
    (expr_list:REG_NORETURN (const_int 0 [0x0])
        (expr_list:REG_EH_REGION (const_int 0 [0x0])
            (nil)))
    (nil))

Note the addr_vec has just 6 labels while bb2 has still 7 successors, bb3
shouldn't be among them.
This later on confuses the cfg code and causes ICE.

When find_many_sub_basic_blocks/find_bb_boundaries/split_block splits
the basic block after the jcc_1 insn, the second basic block inheris all
the successors.  find_bb_boundaries calls purge_dead_edges, but that
one doesn't handle tablejumps.

The attached patch adds a separate routine that purges dead edges for
the tablejump.

Alternatively this could be perhaps done in purge_dead_edges (but at that
point it probably can't abuse bb->aux and would need to use say a sbitmap),
or perhaps even by removing all successors of tablejumps in
find_bb_boundaries if their basic block has been split - make_edges is
called later on and that one should handle adding the edges back. Not sure
whether that's desirable though, as we'd loose any probabilities etc. counted
earlier.

2005-01-05  Jakub Jelinek  <jakub@redhat.com>

	PR rtl-optimization/18861
	* cfgbuild.c (BLOCK_USED_BY_TABLEJUMP): Define.
	(FULL_STATE): Define.
	(mark_tablejump_edge): New function.
	(purge_dead_tablejump_edges): New function.
	(find_bb_boundaries): Use it.

	* gcc.dg/20050105-1.c: New test.

--- gcc/cfgbuild.c.jj	2004-12-07 09:41:35.000000000 +0100
+++ gcc/cfgbuild.c	2005-01-05 17:14:31.189905955 +0100
@@ -559,14 +559,73 @@ enum state {BLOCK_NEW = 0, BLOCK_ORIGINA
 #define STATE(BB) (enum state) ((size_t) (BB)->aux)
 #define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE))
 
+/* Used internally by purge_dead_tablejump_edges, ORed into state.  */
+#define BLOCK_USED_BY_TABLEJUMP		32
+#define FULL_STATE(BB) ((size_t) (BB)->aux)
+
+static void
+mark_tablejump_edge (rtx label)
+{
+  basic_block bb;
+
+  gcc_assert (LABEL_P (label));
+  /* See comment in make_label_edge.  */
+  if (INSN_UID (label) == 0)
+    return;
+  bb = BLOCK_FOR_INSN (label);
+  SET_STATE (bb, FULL_STATE (bb) | BLOCK_USED_BY_TABLEJUMP);
+}
+
+static void
+purge_dead_tablejump_edges (basic_block bb, rtx table)
+{
+  rtx insn = BB_END (bb), tmp;
+  rtvec vec;
+  int j;
+  edge_iterator ei;
+  edge e;
+
+  if (GET_CODE (PATTERN (table)) == ADDR_VEC)
+    vec = XVEC (PATTERN (table), 0);
+  else
+    vec = XVEC (PATTERN (table), 1);
+
+  for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
+    mark_tablejump_edge (XEXP (RTVEC_ELT (vec, j), 0));
+
+  /* Some targets (eg, ARM) emit a conditional jump that also
+     contains the out-of-range target.  Scan for these and
+     add an edge if necessary.  */
+  if ((tmp = single_set (insn)) != NULL
+       && SET_DEST (tmp) == pc_rtx
+       && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
+       && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
+    mark_tablejump_edge (XEXP (XEXP (SET_SRC (tmp), 2), 0));
+
+  for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
+    {
+      if (FULL_STATE (e->dest) & BLOCK_USED_BY_TABLEJUMP)
+        SET_STATE (e->dest, FULL_STATE (e->dest)
+                            & ~(size_t) BLOCK_USED_BY_TABLEJUMP);
+      else if (!(e->flags & (EDGE_ABNORMAL | EDGE_EH)))
+        {
+          remove_edge (e);
+          continue;
+        }
+      ei_next (&ei);
+    }
+}
+
 /* Scan basic block BB for possible BB boundaries inside the block
    and create new basic blocks in the progress.  */
 
 static void
 find_bb_boundaries (basic_block bb)
 {
+  basic_block orig_bb = bb;
   rtx insn = BB_HEAD (bb);
   rtx end = BB_END (bb);
+  rtx table;
   rtx flow_transfer_insn = NULL_RTX;
   edge fallthru = NULL;
 
@@ -623,6 +682,11 @@ find_bb_boundaries (basic_block bb)
      followed by cleanup at fallthru edge, so the outgoing edges may
      be dead.  */
   purge_dead_edges (bb);
+
+  /* purge_dead_edges doesn't handle tablejump's, but if we have split the
+     basic block, we might need to kill some edges.  */
+  if (bb != orig_bb && tablejump_p (BB_END (bb), NULL, &table))
+    purge_dead_tablejump_edges (bb, table);
 }
 
 /*  Assume that frequency of basic block B is known.  Compute frequencies
--- gcc/testsuite/gcc.dg/20050105-1.c.jj	2005-01-05 17:27:13.145456585 +0100
+++ gcc/testsuite/gcc.dg/20050105-1.c	2005-01-05 17:26:50.000000000 +0100
@@ -0,0 +1,31 @@
+/* PR rtl-optimization/18861 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -floop-optimize2" } */
+
+extern void abort (void);
+
+int
+foo (int code)
+{
+  if (code >= 3)
+    switch (code)
+      {
+      case 3: return 4;
+      case 4: return 3;
+      case 5: return 6;
+      case 6: return 7;
+      case 7: return 8;
+      case 8: return 5;
+      default: abort ();
+      }
+  switch (code)
+    {
+    case 3: return 4;
+    case 4: return 3;
+    case 5: return 6;
+    case 6: return 7;
+    case 7: return 8;
+    case 8: return 5;
+    default: abort ();
+    }
+}

	Jakub


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]