[PATCH] Fix PR33642, unrecognizable insn for -frtl-abstract-sequences

[PATCH] Fix PR33642, unrecognizable insn for -frtl-abstract-sequences

[Gábor Lóki]

[-- Attachment #1: Type: text/plain, Size: 1443 bytes --]

Hi,

This patch fixes the PR33642 for rtl-factoring.c.

It contains the following modifications:

- Redesign the cost computation (based on 'get_attr_length'),
because the previous one fails on many targets.

- The generation of indirect jump sequence has been also modified.
An intermediate register move have been inserted before indirect jump
if the target requires it.

- Use constant pool if the target doesn't allow to store a symbol
reference directly to a register.

- Detect the need of intermediate register and constant pool during
initialization.


Bootstrapped on i686-linux, x86_64-linux.
Regtested on i686-linux, x86_64-linux, arm-eabi, mips-elf, powerpc-elf, sh-elf.


It has a known deficiency: fails into an 'unrecognizable insn' error on arm-eabi
with '-O0 -fPIC -frtl-abstract-sequences' flags.

Currently I don't know why, but I will look into it.

Ok for trunk?

--Gabor



2008-03-13  Gabor Loki  <loki@gcc.gnu.org>

	PR gcc/33642
	* rtl-factoring.c (get_default_length, compute_rtx_length): New.
	Computes the length of INSNs.
	(compute_rtx_cost): Use COMPUTE_RTX_LENGTH instead of GET_ATTR_LENGTH.
	(match_seqs): Initialize IJMP_REG field.
	(recompute_gain_for_pattern_seq): Find a register for IJMP_REG.
	(gen_symbol_ref_rtx_for_label): Force constant to memory if necessary.
	(split_pattern_seq): Use IJMP_REG for indirect jump.
	(compute_init_costs): Detect the need of intermediate register and
	constant pool.




[-- Attachment #2: PR33642_0313.patch --]
[-- Type: text/x-patch, Size: 9354 bytes --]

Index: gcc/rtl-factoring.c
===================================================================
--- gcc/rtl-factoring.c	(revision 133102)
+++ gcc/rtl-factoring.c	(working copy)
@@ -37,6 +37,8 @@
 #include "output.h"
 #include "df.h"
 #include "addresses.h"
+#include "insn-attr.h"
+#include "recog.h"
 
 /* Sequence abstraction:
 
@@ -202,6 +204,9 @@
 
   /* The register used to hold the return address during the pseudo-call.  */
   rtx link_reg;
+  
+  /* The register for indirect jump.  */
+  rtx ijmp_reg;
 
   /* The sequences matching this pattern.  */
   matching_seq matching_seqs;
@@ -271,6 +276,12 @@
 /* Cost of returning.  */
 static int seq_return_cost;
 
+/* Register class for indirect jump.  */
+static enum reg_class ijmp_class;
+
+/* Use constant pool to store generated symbol references.  */
+static int use_const_pool = 0;
+
 /* Returns the first insn preceding INSN for which INSN_P is true and belongs to
    the same basic block. Returns NULL_RTX if no such insn can be found.  */
 
@@ -308,9 +319,59 @@
   return hash;
 }
 
-/* Compute the cost of INSN rtx for abstraction.  */
+/* Returns default length of INSN or its PATTERN if INSN isn't recognized.  */
 
+static inline int
+get_default_length (rtx insn)
+{
+  rtx body = PATTERN (insn);
+  if (recog_memoized (insn) >= 0)
+    return insn_default_length (insn);
+  else if (recog_memoized (body) >= 0)
+    return insn_default_length (body);
+  else
+    return 0;
+}
+
+/* Compute the length of INSN.  */
+
 static int
+compute_rtx_length (rtx insn)
+{
+  rtx body;
+  int i;
+  int length = 0;
+
+  switch (GET_CODE (insn))
+    {
+    case CALL_INSN:
+      length = get_default_length (insn);
+      break;
+
+    case JUMP_INSN:
+      length = get_default_length (insn);
+      break;
+
+    case INSN:
+      body = PATTERN (insn);
+      if (GET_CODE (body) == USE || GET_CODE (body) == CLOBBER)
+        return 0;
+      else if (GET_CODE (body) == SEQUENCE)
+        for (i = 0; i < XVECLEN (body, 0); i++)
+          length += compute_rtx_length (XVECEXP (body, 0, i));
+      else
+        length = get_default_length (insn);
+      break;
+
+    default:
+      break;
+    }
+  return length;
+}
+
+/* Compute and cache the cost of INSN rtx.  */
+
+static int
 compute_rtx_cost (rtx insn)
 {
   struct hash_bucket_def tmp_bucket;
@@ -340,7 +401,7 @@
   /* If we can't parse the INSN cost will be the instruction length.  */
   if (cost == -1)
   {
-    cost = get_attr_length (insn);
+    cost = compute_rtx_length (insn);
 
     /* Cache the length.  */
     if (elem)
@@ -349,7 +410,7 @@
 
   /* If we can't get an accurate estimate for a complex instruction,
      assume that it has the same cost as a single fast instruction.  */
-  return cost != 0 ? cost : COSTS_N_INSNS (1);
+  return cost > 0 ? cost : COSTS_N_INSNS (1);
 }
 
 /* Determines the number of common insns in the sequences ending in INSN1 and
@@ -405,6 +466,7 @@
       pseq->abstracted_length = 0;
       pseq->cost = 0;
       pseq->link_reg = NULL_RTX;
+      pseq->ijmp_reg = NULL_RTX;
       pseq->matching_seqs = NULL;
       pseq->next_pattern_seq = pattern_seqs;
       pattern_seqs = pseq;
@@ -594,6 +656,7 @@
   /* Initialize data.  */
   SET_HARD_REG_SET (linkregs);
   pseq->link_reg = NULL_RTX;
+  pseq->ijmp_reg = NULL_RTX;
   pseq->abstracted_length = 0;
 
   pseq->gain = -(seq_call_cost - seq_jump_cost + seq_return_cost);
@@ -697,7 +760,7 @@
 #else
         || (!ok_for_base_p_1 (i, Pmode, MEM, SCRATCH))
         || (!reg_class_subset_p (REGNO_REG_CLASS (i),
-				 base_reg_class (VOIDmode, MEM, SCRATCH)))
+                                 base_reg_class (VOIDmode, MEM, SCRATCH)))
 #endif
         || (hascall && call_used_regs[i])
         || (!call_used_regs[i] && !df_regs_ever_live_p (i)))
@@ -714,7 +777,28 @@
   /* Abstraction is not possible if no link register is available, so set
      gain to 0.  */
   if (!pseq->link_reg)
-    pseq->gain = 0;
+    {
+      pseq->gain = 0;
+      return;
+    }
+
+  if (reg_class_subset_p (REGNO_REG_CLASS (i), ijmp_class))
+    return;
+
+  /* Find a register for indirect jump.  */
+  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+    if (reg_class_subset_p (REGNO_REG_CLASS (i), ijmp_class) 
+        && (!hascall || !call_used_regs[i])
+        && (call_used_regs[i] || df_regs_ever_live_p (i)))
+      {
+        pseq->ijmp_reg = gen_rtx_REG (Pmode, i);
+        break;
+      }
+  if (!pseq->ijmp_reg)
+    {
+      pseq->gain = 0;
+      return;
+    }
 }
 
 /* Deallocates memory occupied by PSEQ and its matching seqs.  */
@@ -938,7 +1022,7 @@
 /* Builds a symbol_ref for LABEL.  */
 
 static rtx
-gen_symbol_ref_rtx_for_label (const_rtx label)
+gen_symbol_ref_rtx_for_label (rtx label)
 {
   char name[20];
   rtx sym;
@@ -946,6 +1030,10 @@
   ASM_GENERATE_INTERNAL_LABEL (name, "L", CODE_LABEL_NUMBER (label));
   sym = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (name));
   SYMBOL_REF_FLAGS (sym) = SYMBOL_FLAG_LOCAL;
+  if (use_const_pool) {
+    LABEL_PRESERVE_P (label) = 1;
+    return force_const_mem (Pmode, sym);
+  }
   return sym;
 }
 
@@ -1004,7 +1092,7 @@
 {
   rtx insn;
   basic_block bb;
-  rtx retlabel, retjmp, saveinsn;
+  rtx retlabel, saveinsn;
   int i;
   seq_block sb;
 
@@ -1020,8 +1108,19 @@
   /* Emit an indirect jump via the link register after the sequence acting
      as the return insn.  Also emit a barrier and update the basic block.  */
   if (!find_reg_note (BB_END (bb), REG_NORETURN, NULL))
-    retjmp = emit_jump_insn_after (gen_indirect_jump (pattern_seqs->link_reg),
-                                   BB_END (bb));
+    {
+      if (!reg_class_subset_p (REGNO_REG_CLASS (REGNO (pattern_seqs->link_reg)),
+                               ijmp_class))
+        {
+          emit_insn_after (gen_move_insn (pattern_seqs->ijmp_reg,
+                                          pattern_seqs->link_reg), BB_END (bb));
+          emit_jump_insn_after (gen_indirect_jump (pattern_seqs->ijmp_reg),
+                                BB_END (bb));
+        }
+      else
+        emit_jump_insn_after (gen_indirect_jump (pattern_seqs->link_reg),
+                              BB_END (bb));
+    }
   emit_barrier_after (BB_END (bb));
 
   /* Replace all outgoing edges with a new one to the block of RETLABEL.  */
@@ -1335,32 +1434,91 @@
 static void
 compute_init_costs (void)
 {
-  rtx rtx_jump, rtx_store, rtx_return, reg, label;
+  rtx rtx_jump, rtx_store, rtx_return, reg, jmp_reg, label, tmp;
   basic_block bb;
+  int i, regno, jmpno;
 
   FOR_EACH_BB (bb)
     if (BB_HEAD (bb))
       break;
 
   label = block_label (bb);
-  reg = gen_rtx_REG (Pmode, 0);
 
+  regno = 0;
+  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+    if (regno_ok_for_base_p (i, Pmode, MEM, SCRATCH))
+      {
+        regno = i;
+        break;
+      }
+  reg = gen_rtx_REG (Pmode, regno);
+
   /* Pattern for indirect jump.  */
   rtx_jump = gen_indirect_jump (reg);
 
-  /* Pattern for storing address.  */
-  rtx_store = gen_rtx_SET (VOIDmode, reg, gen_symbol_ref_rtx_for_label (label));
+  /* The cost of jump.  */
+  if  (GET_CODE (rtx_jump) == JUMP_INSN)
+    tmp = rtx_jump;
+  else
+    tmp = make_jump_insn_raw (rtx_jump);
+  seq_jump_cost = compute_rtx_cost (tmp);
 
-  /* Pattern for return insn.  */
-  rtx_return = gen_jump (label);
+  /* Determine the register class for indirect jump.  */
+  extract_insn (tmp);
+  preprocess_constraints ();
+  ijmp_class = NO_REGS;
+  if (recog_data.n_operands == 1)
+    {
+      char c;
+      const char *p = recog_data.constraints[0];
+      for (;(c = *p) != '\0';)
+        {
+          if (c == 'r' || c == 'g')
+            ijmp_class = GENERAL_REGS;
+          else
+            ijmp_class = REG_CLASS_FROM_CONSTRAINT (c, p);
+          
+          if (ijmp_class != NO_REGS)
+            break;
+          p += CONSTRAINT_LEN (c, p);
+        }
+    }
 
-  /* The cost of jump.  */
-  seq_jump_cost = compute_rtx_cost (make_jump_insn_raw (rtx_jump));
+  jmpno = 0;
+  jmp_reg = NULL_RTX;
+  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+    if (reg_class_subset_p (REGNO_REG_CLASS (i), ijmp_class))
+      {
+        jmp_reg = gen_rtx_REG (Pmode, i);
+        jmpno = i;
+        break;
+      }
 
+  if (REGNO_REG_CLASS (regno) != REGNO_REG_CLASS (jmpno))
+    seq_jump_cost += compute_rtx_cost (gen_move_insn (jmp_reg, reg));
+
+  /* Pattern for storing address.  */
+  rtx_store = gen_move_insn (reg, gen_symbol_ref_rtx_for_label (label));
+  for (tmp = rtx_store; tmp; tmp = NEXT_INSN(tmp))
+    if (recog_memoized(tmp) < 0 && GET_CODE (PATTERN (tmp)) != USE)
+      {
+        use_const_pool = 1;
+        break;
+      }
+  /* Try to use constant pool for symbol reference.  */
+  if (use_const_pool)
+    {
+      rtx_store = gen_move_insn (reg, gen_symbol_ref_rtx_for_label (label));
+      for (tmp = rtx_store; tmp; tmp = NEXT_INSN(tmp))
+        gcc_assert (recog_memoized(tmp) >= 0);
+    }
+
   /* The cost of calling sequence.  */
-  seq_call_cost = seq_jump_cost + compute_rtx_cost (make_insn_raw (rtx_store));
+  seq_call_cost = seq_jump_cost + compute_rtx_cost (rtx_store) +
+                  COSTS_N_INSNS (use_const_pool);
 
   /* The cost of return.  */
+  rtx_return = gen_jump (label);
   seq_return_cost = compute_rtx_cost (make_jump_insn_raw (rtx_return));
 
   /* Simple heuristic for minimal sequence cost.  */

Re: [PATCH] Fix PR33642, unrecognizable insn for -frtl-abstract-sequences

[Jim Wilson]

Gábor Lóki wrote:
> Bootstrapped on i686-linux, x86_64-linux.
> Regtested on i686-linux, x86_64-linux, arm-eabi, mips-elf, powerpc-elf, 
> sh-elf.

rtl-factoring aka seqabstr isn't enabled by default, and there are only 
2 testcases in the testsuite, so this isn't a very good test in general. 
  It would be a better test if you bootstrapped with seqabstr defaulted 
to on; or tried running the entire testsuite with seqabstr defaulted to on.

This mostly looks like an improvement.  It attacks the same problem I 
tried to fix for PR 35785 in a more general way.

One thing I notice is that you still have code checking 
REGNO_OK_FOR_INDIRECT_JUMP_P which should not be necessary now that you 
have the code to set ijmp_class and ijmp_reg.  And since this is an 
unused and undocumented macro we really either need to get rid of it or 
fix it (i.e. document it).

I tried building this for an ia64-linux cross compiler and noticed that 
I get a error linking cc1.
> libbackend.a(rtl-factoring.o): In function `get_default_length':
> /home/wilson/GCC/X-ia64-linux/gcc/../../gcc/gcc/rtl-factoring.c:329: undefined reference to `insn_default_length'

insn_default_length is only defined for targets that define a length 
attribute.  The IA-64 port does not.  Since this breaks building of all 
ia64 targets, I can't approve it as is.

I hacked in an insn_default_length function that returns 1 always and 
tried again.  It seems to work in this case, "work" meaning that it 
didn't ICE.  I didn't check whether correct code was emitted.  A proper 
fix here probably involves checking whether HAVE_ATTR_length is defined.

I noticed comments from Janis in PR 33642 pointing out that the patch 
makes this worse for rs6000 since we now get silent miscompilation 
instead of an ICE.  However, this isn't really a problem with this 
patch.  This is a problem with the optimization pass in general.  This 
patch is just exposing underlying existing problems with this 
optimization pass.  This needs a lot more work before it will usable for 
all targets.  So we can either accept that this optimization pass is 
currently unsafe, and that some patches may temporarily make things 
worse, or we can remove it until it is fixed and readd it later.  The 
second choice doesn't seem quite fair to you.  The first choice isn't 
fair to others.

As a temporary fix, one thing we could perhaps do is add warning 
messages for anyone using the option, for instance in process_options() 
in toplev.c.  That way people won't be expecting it to work if they try it.

Another thing we could do is modify the docs for the 
-frtl-abstract-sequences option to document that this option is known to 
be unsafe.  By the way, the docs for this option is in the middle of a 
table for options that control FP semantics.  This is definitely 
misplaced, and another thing that needs to be fixed.

I know that we have done things like this before for other options, but 
I don't recall the details.

Finally, one last comment, I don't like the fact that this optimization 
pass has 3 different names.  The file is rtl-factoring.c, the option 
name is -frtl-abstract-sequences, and in the dump files it is seqabstr. 
    I find this confusing.  I'm not asking you to fix this though, I'm 
just being grumpy.

Jim

Re: [PATCH] Fix PR33642, unrecognizable insn for -frtl-abstract-sequences

[Gabor Loki]

Jim Wilson wrote:
> Gábor Lóki wrote:
>> Bootstrapped on i686-linux, x86_64-linux.
>> Regtested on i686-linux, x86_64-linux, arm-eabi, mips-elf, 
>> powerpc-elf, sh-elf.
> 
> rtl-factoring aka seqabstr isn't enabled by default, and there are only 
> 2 testcases in the testsuite, so this isn't a very good test in general. 
>  It would be a better test if you bootstrapped with seqabstr defaulted 
> to on; or tried running the entire testsuite with seqabstr defaulted to on.

Ok, next time I will enable -frtl-abstract-sequences during regtest.

> This mostly looks like an improvement.  It attacks the same problem I 
> tried to fix for PR 35785 in a more general way.
> 
> One thing I notice is that you still have code checking 
> REGNO_OK_FOR_INDIRECT_JUMP_P which should not be necessary now that you 
> have the code to set ijmp_class and ijmp_reg.  And since this is an 
> unused and undocumented macro we really either need to get rid of it or 
> fix it (i.e. document it).

Ok, I will check and remove this code if it is not necessary.

> I tried building this for an ia64-linux cross compiler and noticed that 
> I get a error linking cc1.
>> libbackend.a(rtl-factoring.o): In function `get_default_length':
>> /home/wilson/GCC/X-ia64-linux/gcc/../../gcc/gcc/rtl-factoring.c:329: 
>> undefined reference to `insn_default_length'
> 
> insn_default_length is only defined for targets that define a length 
> attribute.  The IA-64 port does not.  Since this breaks building of all 
> ia64 targets, I can't approve it as is.
> 
> I hacked in an insn_default_length function that returns 1 always and 
> tried again.  It seems to work in this case, "work" meaning that it 
> didn't ICE.  I didn't check whether correct code was emitted.  A proper 
> fix here probably involves checking whether HAVE_ATTR_length is defined.

Well, you are probably right. The sequence abstraction algorithm
cannot live without insn_*_length functions. I will add HAVE_ATTR_length
check.

BTW, why don't IA-64 have insn_default_length or something similar?
I am not familiar with IA64 port, but I guessed insn_*_length functions
are not negligible for code size optimization passes.

Some years ago I used rtx_cost instead of insn_default_length.
Unfortunately many ports do not involve optimize_size check to
produce size related numbers in their PORT_rtx_cost* functions.
And the result wasn't optimal to decrease code size.

I would be very happy if there was a common way to have the length of
an rtx insn. If we have an opportunity to determine the length of an
arbitrary rtx insn (or sequence) we will also have the opportunity to
move sequence abstraction before register allocation passes.
This will surely dismiss all 'unrecognizable insn' related problems.

> I noticed comments from Janis in PR 33642 pointing out that the patch 
> makes this worse for rs6000 since we now get silent miscompilation 
> instead of an ICE.  However, this isn't really a problem with this 
> patch.  This is a problem with the optimization pass in general.  This 
> patch is just exposing underlying existing problems with this 
> optimization pass.  This needs a lot more work before it will usable for 
> all targets.  So we can either accept that this optimization pass is 
> currently unsafe, and that some patches may temporarily make things 
> worse, or we can remove it until it is fixed and readd it later.  The 
> second choice doesn't seem quite fair to you.  The first choice isn't 
> fair to others.

One reason for merging this patch into mainline was that the code
size optimizations could get more attention. Until someone help me
out with common length computing method, I am going to add those
checks which were suggested by you and others, and send a new patch.

Is it ok? Or you have an other suggestion?

--Gabor

Re: [PATCH] Fix PR33642, unrecognizable insn for -frtl-abstract-sequences

[Andrew Pinski]

On Tue, Apr 8, 2008 at 3:00 AM, Gabor Loki <loki@gcc.gnu.org> wrote:
>  Well, you are probably right. The sequence abstraction algorithm
>  cannot live without insn_*_length functions. I will add HAVE_ATTR_length
>  check.
>
>  BTW, why don't IA-64 have insn_default_length or something similar?
>  I am not familiar with IA64 port, but I guessed insn_*_length functions
>  are not negligible for code size optimization passes.

Well ia64 is not usually a target which you care much about code size.
 Also insn_*_length was only used for branch relaxation so it was not
needed for ia64 or some other targets.  And in some cases it can be
wrong for some targets.

>  Some years ago I used rtx_cost instead of insn_default_length.
>  Unfortunately many ports do not involve optimize_size check to
>  produce size related numbers in their PORT_rtx_cost* functions.
>  And the result wasn't optimal to decrease code size.

I think those targets should be considered broken and fix the issue
there instead of changing to use insn_default_length.

Thanks,
Andrew Pinski

Re: [PATCH] Fix PR33642, unrecognizable insn for -frtl-abstract-sequences

[Jim Wilson]

On Tue, 2008-04-08 at 12:00 +0200, Gabor Loki wrote:
> BTW, why don't IA-64 have insn_default_length or something similar?
> I am not familiar with IA64 port, but I guessed insn_*_length functions
> are not negligible for code size optimization passes.

IA-64 has 40-bit instructions that are packed into 128-bit bundles with
8 control bits along with 3 instructions.  It isn't obvious how to
handle this with the simple semantics implemented by the length
attribute.  I figured one day I would have to look at this, but as yet
no one has reported any out-of-range branch bug for the IA-64 port, so
it still remains unsolved.  I suppose I could give a length of one byte
to the bundle selector unspecs, and 5 bytes to each insn.  That might
work.

Another problem is that any fixes that the shorten_branches optimization
pass might make would break the VLIW instruction bundles, which means we
may never be able to use it for IA-64.  We probably have to do this
ourselves in the md_reorg pass.  Since defining an instruction length
attribute automatically enables shorten_branches, this means we probably
can't define the length attribute.  Unless we maybe define yet another
macro or variable to disable this pass.  Maybe we could have a
flag_shorten_branches variable that is always true, which IA-64 can then
turn off.  We could then maybe manually call shorten_branches inside
md_reorg.

Meanwhile, until someone really cares, I don't plan to do anything here.

> Some years ago I used rtx_cost instead of insn_default_length.
> Unfortunately many ports do not involve optimize_size check to
> produce size related numbers in their PORT_rtx_cost* functions.
> And the result wasn't optimal to decrease code size.

They should be fixed, as Andrew Pinksi said.

> I would be very happy if there was a common way to have the length of
> an rtx insn.

Unfortunately, there is no standard way to do this.  insn_default_length
comes close, but there is no requirement that it be defined.  Just
grepping config/*/*.md for length, I see that there are 5 ports that
don't define the length attribute.  You could maybe fall back on
rtx_cost if there is no length attribute.

You can use HAVE_ATTR_length to choose between the code that uses
insn_default_length and the code that uses rtx_cost.

> One reason for merging this patch into mainline was that the code
> size optimizations could get more attention. Until someone help me
> out with common length computing method, I am going to add those
> checks which were suggested by you and others, and send a new patch.
> 
> Is it ok? Or you have an other suggestion?

I don't have any problem with the code remaining in mainline for now.
I'm not going to approve any patch that doesn't have a fix for the
attribute length problem though, as that would break the ia64 port.

Jim

Re: [PATCH] Fix PR33642, unrecognizable insn for -frtl-abstract-sequences

[Maxim Kuvyrkov]

GĂĄbor LĂłki wrote:
> Hi,
> 
> This patch fixes the PR33642 for rtl-factoring.c.
> 
> It contains the following modifications:
> 
> - Redesign the cost computation (based on 'get_attr_length'),
> because the previous one fails on many targets.

And this one fails on targets that don't define length attribute.  You 
should condition use of get_attr_length with 'ifdef HAVE_attr_length'.

--
Maxim