[PATCH, generic] New RTL primitive: `define_subst'

[PATCH, generic] New RTL primitive: `define_subst'

[Kirill Yukhin]

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

Hi,
This patch introduces a new RTL expression called define_subst and
required by it define_subst_attr.

The new feature allows to make MD-files more compact - it defines a
rule by which a parser could generate modified versions of
RTL-templates. For example, i386.md contains RTL-templates for
ordinary arithmetic, as well as templates for arithmetic with
zero-extension. With define_subst one could specify one rule (write
one define_subst) and keep only RTL-templates for ordinary arithmetic
- the versions with zero-extensions will be generated automatically.
The rule in this case would describe how zero-extended pattern could
be generated with given pattern without zero-extension.

There are some more examples in existing RTL templates where
define_subst could be useful, and it would be extremely useful for
future x86 ISA extensions.

I'd be glad to have a feedback on this feature and ask any questions.

The patch contains implementation of the new feature and its
documentation. Bootstrap passes, and as currently this feature hasn't
been used by anybody no new failures are expected.

Changelog entry:
2012-10-30  Maxim Kuznetsov <maxim.kuznetsov@intel.com>
                    Kirill Yukhin <kirill.yukhin@intel.com>
                    Michael Zolotukhin  <michael.v.zolotukhin@intel.com>

        * doc/md.texi: Document define_subst.
        * gensupport.c (MAX_OPERANDS): New define.
        (operand_data): New.
        (match_operand_entries_in_pattern): New.
        (used_operands_numbers): New.
        (subst_true): New.
        (subst_false): New.
        (define_subst_queue): New.
        (define_subst_tail): New.
        (define_subst_attr_queue): New.
        (define_subst_attr_tail): New.
        (has_subst_attribute): New.
        (subst_pattern_match): New.
        (get_alternatives_number): New.
        (alter_output_for_subst_insn): New.
        (alter_attrs_for_subst_insn): New.
        (process_substs_on_one_elem): New.
        (subst_dup): New.
        (process_define_subst): New.
        (duplicate_alternatives): New.
        (duplicate_each_alternative): New.
        (constraints_handler_t): New typedef.
        (alter_constraints): New.
        (adjust_operands_numbers): New.
        (replace_duplicating_operands_in_pattern): New.
        (remove_from_queue): New.
        (process_rtx): Handle define_subst and define_subst_attr.
        (change_subst_attribute): New.
        (alter_predicate_for_insn): Fix formatting.
        (alter_attrs_for_insn): Likewise.
        (alter_output_for_insn): Likewise.
        (mark_operands_from_match_dup): New.
        (mark_operands_used_in_match_dup): New.
        (find_first_unused_number_of_operand): New.
        (renumerate_operands_in_pattern): New.
        (generate_match_dup): New.
        (check_define_attr_duplicates): New.
        (init_rtx_reader_args_cb): Add checking for duplicated attrs and
        processing of define_subst.
        (read_md_rtx): Handle define_subst.
        * read-rtl.c (struct subst_attr_to_iter_mapping): New.
        (substs): New global.
        (apply_subst_iterator): New.
        (bind_subst_iter_and_attr): New.
        (find_subst_iter_by_attr): New.
        (map_attr_string): Handle subst-iterators.
        (add_condition_to_rtx): Handle define_subst.
        (apply_iterators): Likewise.
        (initialize_iterators): Likewise.
        (add_define_attr_for_define_subst): New.
        (add_define_subst_attr): New.
        (read_subst_mapping): New.
        (read_rtx): Handle define_subst_attr.
        (read_rtx_code): Add subst-attributes recognition during reading of
        strings.
        * rtl.def (DEFINE_EXPAND): Add vector of attributes.
        (DEFINE_SUBST): New.
        (DEFINE_SUBST_ATTR): New.

Is it ok for trunk?

--
Thanks, K

[-- Attachment #2: define_subst-4.patch --]
[-- Type: application/octet-stream, Size: 61429 bytes --]

diff --git a/gcc/doc/md.texi b/gcc/doc/md.texi
index bcc9bb6..7c5361d 100644
--- a/gcc/doc/md.texi
+++ b/gcc/doc/md.texi
@@ -46,6 +46,8 @@ See the next chapter for information on the C header file.
 * Insn Attributes::     Specifying the value of attributes for generated insns.
 * Conditional Execution::Generating @code{define_insn} patterns for
                          predication.
+* Define Subst::	Generating @code{define_insn} and @code{define_expand}
+			patterns from other patterns.
 * Constant Definitions::Defining symbolic constants that can be used in the
                         md file.
 * Iterators::           Using iterators to generate patterns from a template.
@@ -8719,6 +8721,201 @@ generates a new pattern
 
 @end ifset
 @ifset INTERNALS
+@node Define Subst
+@section RTL Templates Transformations
+@cindex define_subst
+
+On some architectures RTL-templates for many instructions can be
+obtained with some specific rule from RTL-templates of other
+instructions.  For example, @file{i386.md} contains RTL-templates for
+usual arithmetics (like addition and substraction) as well as
+RTL-templates for arithmetics with subsequent zero-extension.  Each pair
+of such templates can be replaced by a single one with use of
+@code{define_subst}.
+
+@findex define_subst
+@smallexample
+(define_subst "@var{name}"
+  [@var{input-template}]
+  "@var{condition}"
+  [@var{output-template}])
+@end smallexample
+
+@var{input-template} is a pattern describing RTL-templates, that can
+be transformed by the given @code{define_subst}.  It plays a role of a
+filter, and also is used for referring to particular parts of the
+RTL-template from the output-template of the @code{define_subst}.
+
+@var{condition} is a C expression that is joined with condition from the
+input-template for generation of the output-template.
+
+@var{output-template} describes which template should be produced by the
+@code{define_subst}.
+
+@code{define_subst} can be used only in @code{define_insn} and
+@code{define_expand}, but can not be used other expressions (e.g. in
+@code{define_insn_and_split}).
+
+To apply @code{define_subst} to an RTL-template, it should be marked---
+that is done by using subst-attribute in any place of the template, e.g.
+in condition or constraints string, in the name or in the output
+template.  Expanding of a subst-attribute always results in duplicating
+the original pattern (correspondingly, subst-attributes always have only
+two values).  The first copy is left with unchanged pattern, while the
+second copy is later subjected to @code{define_subst} transformation.
+If @code{define_subst} could not be applied because the pattern does not
+match the @code{define_insn}/@code{define_expand} original template,
+then the second copy is deleted.
+
+@menu
+* Define Subst Pattern Matching:: Process of template comparison.
+* Define Subst Output Template::  Generation of output template.
+* Define Subst Example::	  Example of @code{define_subst} usage.
+@end menu
+
+@node Define Subst Pattern Matching
+@subsection Pattern Matching in @code{define_subst}
+@cindex define_subst
+
+Most of expressions, allowed in @code{define_insn} or @code{define_expand},
+are allowed in the input RTL-template of @code{define_subst}.  However,
+meaning of some of them were expanded:
+
+@code{match_operand} matches any expression (possibly, a subtree in
+RTL-template), if modes of the @code{match_operand} and this expression
+are the same, or mode of the @code{match_operand} is @code{VOIDmode}, or
+this expression is @code{match_dup}, @code{match_op_dup}.  If the
+expression is @code{match_operand} too, and predicate of
+@code{match_operand} from the input pattern is not empty, then the
+predicates are compared.  That can be used to more accurate filtering of
+accepted RTL-templates.
+
+@code{match_operator} matches common operators (like @code{plus},
+@code{minus}), @code{unspec}, @code{unspec_volatile} operators and
+@code{match_operator}s from the original pattern if the modes match and
+@code{match_operator} from the input pattern has the same number of
+operands as the operator from the original pattern.
+
+Behaviour of some expressions in @code{define_subst}
+@var{input-template} has not been defined for now, so their usage in
+@code{define_subst} is prohibited.  Such expressions are:
+@code{match_par_dup}, @code{match_scratch}, @code{match_parallel}.
+
+@node Define Subst Output Template
+@subsection Generation of output template in @code{define_subst}
+@cindex define_subst
+
+If all necessary checks for @code{define_subst} application pass, a new
+RTL-pattern, based on the output-template, is created.  Like in
+input-patterns, meaning of some RTL expressions are changed when they
+are used in output-patterns of a @code{define_subst}.  Thus,
+@code{match_dup} is used for copying the whole expression from the
+original pattern, which matched corresponding @code{match_operand} from
+the input pattern.
+
+For referring to expressions from the original pattern, @code{match_dup N}
+is used---wherever it is used, it is replaced with the expression from
+the original pattern, which matched @code{match_operand N} from the
+input pattern.  As a consequence, @code{match_dup} can not be used to
+point to @code{match_operand}s from the output pattern, it should always
+refer to a @code{match_operand} from the input pattern.
+
+Along with referring to existing in the original pattern ones,
+completely new expressions could be used in the output template.  For
+instance, some operands could be added with use of standard
+@code{match_operand}.
+
+After replacing @code{match_dup} with some RTL-subtree from the original
+pattern, it could happen that several @code{match_operand}s in the
+output pattern have the same indexes.  It is unknown, how many and what
+indexes would be used in the expression which would replace
+@code{match_dup}, so such conflicts in indexes are inevitable.  To
+overcome this issue, @code{match_operands} and @code{match_operators},
+which were introduced into the output pattern, are renumerated when all
+@code{match_dup}s are replaced.
+
+Number of alternatives in @code{match_operand}s introduced into the
+output template @code{M} could differ from the number of alternatives in
+the original pattern @code{N}, so in the resultant pattern there would
+be @code{NxM} alternatives.  Thus, constraints from the original pattern
+would be duplicated @code{N} times, constraints from the output pattern
+would be duplicated @code{M} times, producing all possible combinations
+of them.
+
+@node Define Subst Example
+@subsection Example of @code{define_subst}
+@cindex define_subst
+
+Here is an example of shift instruction and its analog with
+zero-extension from @file{i386.md}:
+
+@smallexample
+(define_insn "*<shift_insn><mode>3_1"
+  [(set (match_operand:SWI48 0 "nonimmediate_operand" "=rm,r")
+        (any_shiftrt:SWI48
+          (match_operand:SWI48 1 "nonimmediate_operand" "0,rm")
+          (match_operand:QI 2 "nonmemory_operand" "c<S>,r")))
+   (clobber (reg:CC FLAGS_REG))]
+  "ix86_binary_operator_ok (<CODE>, <MODE>mode, operands)"
+ @{
+    @dots{}
+    return "<shift>@{<imodesuffix>@}\t@{%2, %0|%0, %2@}";
+ @}
+ [@dots{}])
+
+(define_insn "*<shift_insn>si3_1_zext"
+  [(set (match_operand:DI 0 "register_operand" "=r,r")
+        (zero_extend:DI
+          (any_shiftrt:SI (match_operand:SI 1 "nonimmediate_operand" "0,rm")
+          (match_operand:QI 2 "nonmemory_operand" "cI,r"))))
+   (clobber (reg:CC FLAGS_REG))]
+   "TARGET_64BIT && ix86_binary_operator_ok (<CODE>, SImode, operands)"
+  @{
+     @dots{}
+     return "<shift>@{l@}\t@{%2, %k0|%k0, %2@}";
+  @}
+  [@dots{}])
+@end smallexample
+
+As the second pattern differs from the first only in @code{zero_extend}, they
+can be generated by one @code{define_insn} using @code{define_subst} and two
+@code{define_subst_attr}s for insn name and output.
+
+@smallexample
+(define_subst_attr "zext" "zext_subst" "" "_zext")
+(define_subst_attr "k" "zext_subst" "" "k")
+
+(define_subst "zext_subst"
+  [(set (match_operand:SI 0)
+        (match_operator 1 "=r" [(match_operand 2) (match_operand 3)]))
+  (clobber (reg:CC FLAGS_REG))]
+  "TARGET_64BIT"
+  [(set (match_operand:DI 0 "register_operand" "=r")
+       (zero_extend:DI (match_op_dup 1 [(match_dup 2) (match_dup 3)])))
+  (clobber (reg:CC FLAGS_REG))]
+)
+
+(define_insn "*<shift_insn><mode>3_1<zext>"
+  [(set (match_operand:SWI48 0 "nonimmediate_operand" "=rm,r")
+        (any_shiftrt:SWI48
+          (match_operand:SWI48 1 "nonimmediate_operand" "0,rm")
+          (match_operand:QI 2 "nonmemory_operand" "c<S>,r")))
+  (clobber (reg:CC FLAGS_REG))]
+  "ix86_binary_operator_ok (<CODE>, <MODE>mode, operands)"
+  @{
+     @dots{}
+     return "<shift>@{<imodesuffix>@}\t@{%2, %<k>0|%<k>0, %2@}";
+  @}
+  [@dots{}])
+@end smallexample
+
+When such @code{define_subst} is created, it could be used to collapse
+other pairs of ordinary/zero_extended instructions into a single entry
+in @file{.md}-file.
+
+@end ifset
+
+@ifset INTERNALS
 @node Constant Definitions
 @section Constant Definitions
 @cindex constant definitions
@@ -8902,6 +9099,7 @@ facilities to make this process easier.
 * Mode Iterators::         Generating variations of patterns for different modes.
 * Code Iterators::         Doing the same for codes.
 * Int Iterators::          Doing the same for integers.
+* Subst Iterators::	   Generating variations of patterns for define_subst.
 @end menu
 
 @node Mode Iterators
@@ -9250,4 +9448,54 @@ This is equivalent to:
 
 @end smallexample
 
+@node Subst Iterators
+@subsection Subst Iterators
+@cindex subst iterators in @file{.md} files
+@findex define_subst
+@findex define_subst_attr
+
+Subst iterators differ from other iterators in many ways: they could
+not be declared explicitly, and they always have only two values.
+Subst-iterators are triggered only when corresponding subst-attribute is
+used in RTL-pattern.  Unlike other ones, subst iterators can not be
+triggered by explicit mentioning them in the pattern, as they do not
+have an explicit dedicated name.
+
+Subst iterators transform templates they are applied to in the following
+way: the templates are duplicated, the subst-attributes in these
+templates are replaced with the corresponding values, and a new
+attribute is implicitly added to the given
+@code{define_insn}/@code{define_expand}.  The name of the added
+attribute matches the name of @code{define_subst} that should be applied
+to this template.  Such attributes are declared implicitly and it is not
+allowed to declare them manually - that means it is not allowed to have
+a @code{define_attr} named as a @code{define_subst}.
+
+Each subst iterator is linked to a @code{define_subst}.  It is declared
+implicitly by the first appearance of the corresponding
+@code{define_subst_attr}, and it is not allowed to define it explicitly.
+
+Declarations of subst-attributes have the following syntax:
+
+@findex define_subst_attr
+@smallexample
+(define_subst_attr "@var{name}"
+  "@var{subst-name}"
+  "@var{no-subst-value}"
+  "@var{subst-applied-value}")
+@end smallexample
+
+@var{name} is a string with which the given subst-attribute could be
+referred to.
+
+@var{subst-name} shows which @code{define_subst} should be applied an
+RTL-template if the given subst-attribute is present in this
+RTL-template.
+
+@var{no-subst-value} is a value with which subst-attribute would be
+replaced in the first copy of the original RTL-template.
+
+@var{subst-applied-value} is a value with which subst-attribute would be
+replaced in the second copy of the original RTL-template.
+
 @end ifset
diff --git a/gcc/gensupport.c b/gcc/gensupport.c
index 44443e2..05e84e0 100644
--- a/gcc/gensupport.c
+++ b/gcc/gensupport.c
@@ -29,6 +29,12 @@
 #include "read-md.h"
 #include "gensupport.h"
 
+#define MAX_OPERANDS 40
+
+static rtx operand_data[MAX_OPERANDS];
+static rtx match_operand_entries_in_pattern[MAX_OPERANDS];
+static char used_operands_numbers[MAX_OPERANDS];
+
 
 /* In case some macros used by files we include need it, define this here.  */
 int target_flags;
@@ -48,10 +54,14 @@ static int predicable_default;
 static const char *predicable_true;
 static const char *predicable_false;
 
+static const char *subst_true = "yes";
+static const char *subst_false = "no";
+
 static htab_t condition_table;
 
-/* We initially queue all patterns, process the define_insn and
-   define_cond_exec patterns, then return them one at a time.  */
+/* We initially queue all patterns, process the define_insn,
+   define_cond_exec and define_subst patterns, then return
+   them one at a time.  */
 
 struct queue_elem
 {
@@ -75,8 +85,12 @@ static struct queue_elem *define_insn_queue;
 static struct queue_elem **define_insn_tail = &define_insn_queue;
 static struct queue_elem *define_cond_exec_queue;
 static struct queue_elem **define_cond_exec_tail = &define_cond_exec_queue;
+static struct queue_elem *define_subst_queue;
+static struct queue_elem **define_subst_tail = &define_subst_queue;
 static struct queue_elem *other_queue;
 static struct queue_elem **other_tail = &other_queue;
+static struct queue_elem *define_subst_attr_queue;
+static struct queue_elem **define_subst_attr_tail = &define_subst_attr_queue;
 
 static struct queue_elem *queue_pattern (rtx, struct queue_elem ***,
 					 const char *, int);
@@ -99,6 +113,24 @@ static void process_one_cond_exec (struct queue_elem *);
 static void process_define_cond_exec (void);
 static void init_predicate_table (void);
 static void record_insn_name (int, const char *);
+
+static bool has_subst_attribute (struct queue_elem *, struct queue_elem *);
+static bool subst_pattern_match (rtx, rtx, int);
+static int get_alternatives_number (rtx, int *, int);
+static const char * alter_output_for_subst_insn (rtx, int);
+static void alter_attrs_for_subst_insn (struct queue_elem *, int);
+static void process_substs_on_one_elem (struct queue_elem *,
+					struct queue_elem *);
+static rtx subst_dup (rtx, int, int);
+static void process_define_subst (void);
+
+static const char * duplicate_alternatives (const char *, int);
+static const char * duplicate_each_alternative (const char * str, int n_dup);
+
+typedef const char * (*constraints_handler_t) (const char *, int);
+static rtx alter_constraints (rtx, int, constraints_handler_t);
+static rtx adjust_operands_numbers (rtx);
+static rtx replace_duplicating_operands_in_pattern (rtx);
 \f
 /* Make a version of gen_rtx_CONST_INT so that GEN_INT can be used in
    the gensupport programs.  */
@@ -372,6 +404,27 @@ queue_pattern (rtx pattern, struct queue_elem ***list_tail,
   return e;
 }
 
+/* Remove element ELEM from QUEUE.  */
+static void
+remove_from_queue (struct queue_elem *elem, struct queue_elem **queue)
+{
+  struct queue_elem *prev, *e;
+  prev = NULL;
+  for (e = *queue; e ; e = e->next)
+    {
+      if (e == elem)
+	break;
+      prev = e;
+    }
+  if (e == NULL)
+    return;
+
+  if (prev)
+    prev->next = elem->next;
+  else
+    *queue = elem->next;
+}
+
 /* Build a define_attr for an binary attribute with name NAME and
    possible values "yes" and "no", and queue it.  */
 static void
@@ -439,6 +492,14 @@ process_rtx (rtx desc, int lineno)
       queue_pattern (desc, &define_cond_exec_tail, read_md_filename, lineno);
       break;
 
+    case DEFINE_SUBST:
+      queue_pattern (desc, &define_subst_tail, read_md_filename, lineno);
+      break;
+
+    case DEFINE_SUBST_ATTR:
+      queue_pattern (desc, &define_subst_attr_tail, read_md_filename, lineno);
+      break;
+
     case DEFINE_ATTR:
     case DEFINE_ENUM_ATTR:
       queue_pattern (desc, &define_attr_tail, read_md_filename, lineno);
@@ -584,6 +645,267 @@ is_predicable (struct queue_elem *elem)
   return 0;
 }
 
+/* Find attribute SUBST in ELEM and assign NEW_VALUE to it.  */
+static void
+change_subst_attribute (struct queue_elem *elem,
+			struct queue_elem *subst_elem,
+			const char *new_value)
+{
+  rtvec attrs_vec = XVEC (elem->data, 4);
+  const char *subst_name = XSTR (subst_elem->data, 0);
+  int i;
+
+  if (! attrs_vec)
+    return;
+
+  for (i = GET_NUM_ELEM (attrs_vec) - 1; i >= 0; --i)
+    {
+      rtx cur_attr = RTVEC_ELT (attrs_vec, i);
+      if (GET_CODE (cur_attr) != SET_ATTR)
+	continue;
+      if (strcmp (XSTR (cur_attr, 0), subst_name) == 0)
+	{
+	  XSTR (cur_attr, 1) = new_value;
+	  return;
+	}
+    }
+}
+
+/* Return true if ELEM has the attribute with the name of DEFINE_SUBST
+   represented by SUBST_ELEM and this attribute has value SUBST_TRUE.
+   DEFINE_SUBST isn't applied to patterns without such attribute.  In other
+   words, we suppose the default value of the attribute to be 'no' since it is
+   always generated automaticaly in read-rtl.c.  */
+static bool
+has_subst_attribute (struct queue_elem *elem, struct queue_elem *subst_elem)
+{
+  rtvec attrs_vec = XVEC (elem->data, 4);
+  const char *value, *subst_name = XSTR (subst_elem->data, 0);
+  int i;
+
+  if (! attrs_vec)
+    return false;
+
+  for (i = GET_NUM_ELEM (attrs_vec) - 1; i >= 0; --i)
+    {
+      rtx cur_attr = RTVEC_ELT (attrs_vec, i);
+      switch (GET_CODE (cur_attr))
+	{
+	case SET_ATTR:
+	  if (strcmp (XSTR (cur_attr, 0), subst_name) == 0)
+	    {
+	      value = XSTR (cur_attr, 1);
+	      goto found;
+	    }
+	  break;
+
+	case SET:
+	  if (GET_CODE (SET_DEST (cur_attr)) != ATTR
+	      || strcmp (XSTR (SET_DEST (cur_attr), 0), subst_name) != 0)
+	    break;
+	  cur_attr = SET_SRC (cur_attr);
+	  if (GET_CODE (cur_attr) == CONST_STRING)
+	    {
+	      value = XSTR (cur_attr, 0);
+	      goto found;
+	    }
+
+	  /* Only (set_attr "subst" "yes/no") and
+		  (set (attr "subst" (const_string "yes/no")))
+	     are currently allowed.  */
+	  error_with_line (elem->lineno,
+			   "unsupported value for `%s'", subst_name);
+	  return false;
+
+	case SET_ATTR_ALTERNATIVE:
+	  error_with_line (elem->lineno,
+			   "%s: `set_attr_alternative' is unsupported by "
+			   "`define_subst'",
+			   XSTR (elem->data, 0));
+	  return false;
+
+
+	default:
+	  gcc_unreachable ();
+	}
+    }
+
+  return false;
+
+ found:
+  if (strcmp (value, subst_true) == 0)
+    return true;
+  if (strcmp (value, subst_false) == 0)
+    return false;
+
+  error_with_line (elem->lineno,
+		   "unknown value `%s' for `%s' attribute", value, subst_name);
+  return false;
+}
+
+/* Compare RTL-template of original define_insn X to input RTL-template of
+   define_subst PT.  Return 1 if the templates match, 0 otherwise.
+   During the comparison, the routine also fills global_array OPERAND_DATA.  */
+static bool
+subst_pattern_match (rtx x, rtx pt, int lineno)
+{
+  RTX_CODE code, code_pt;
+  int i, j, len;
+  const char *fmt, *pred_name;
+
+  code = GET_CODE (x);
+  code_pt = GET_CODE (pt);
+
+  if (code_pt == MATCH_OPERAND)
+    {
+      /* MATCH_DUP, and MATCH_OP_DUP don't have a specified mode, so we
+	 always accept them.  */
+      if (GET_MODE (pt) != VOIDmode && GET_MODE (x) != GET_MODE (pt)
+	  && (code != MATCH_DUP && code != MATCH_OP_DUP))
+	return false; /* Modes don't match.  */
+
+      if (code == MATCH_OPERAND)
+	{
+	  pred_name = XSTR (pt, 1);
+	  if (pred_name[0] != 0)
+	    {
+	      const struct pred_data *pred_pt = lookup_predicate (pred_name);
+	      if (!pred_pt || pred_pt != lookup_predicate (XSTR (x, 1)))
+		return false; /* Predicates don't match.  */
+	    }
+	}
+
+      gcc_assert (XINT (pt, 0) >= 0 && XINT (pt, 0) < MAX_OPERANDS);
+      operand_data[XINT (pt, 0)] = x;
+      return true;
+    }
+
+  if (code_pt == MATCH_OPERATOR)
+    {
+      int x_vecexp_pos = -1;
+
+      /* Compare modes.  */
+      if (GET_MODE (pt) != VOIDmode && GET_MODE (x) != GET_MODE (pt))
+	return false;
+
+      /* In case X is also match_operator, compare predicates.  */
+      if (code == MATCH_OPERATOR)
+	{
+	  pred_name = XSTR (pt, 1);
+	  if (pred_name[0] != 0)
+	    {
+	      const struct pred_data *pred_pt = lookup_predicate (pred_name);
+	      if (!pred_pt || pred_pt != lookup_predicate (XSTR (x, 1)))
+		return false;
+	    }
+	}
+
+      /* Compare operands.
+	 MATCH_OPERATOR in input template could match in original template
+	 either 1) MATCH_OPERAND, 2) UNSPEC, 3) ordinary operation (like PLUS).
+	 In the first case operands are at (XVECEXP (x, 2, j)), in the second
+	 - at (XVECEXP (x, 0, j)), in the last one - (XEXP (x, j)).
+	 X_VECEXP_POS variable shows, where to look for these operands.  */
+      if (code == UNSPEC
+	  || code == UNSPEC_VOLATILE)
+	x_vecexp_pos = 0;
+      else if (code == MATCH_OPERATOR)
+	x_vecexp_pos = 2;
+      else
+	x_vecexp_pos = -1;
+
+      /* MATCH_OPERATOR or UNSPEC case.  */
+      if (x_vecexp_pos >= 0)
+	{
+	  /* Compare operands number in X and PT.  */
+	  if (XVECLEN (x, x_vecexp_pos) != XVECLEN (pt, 2))
+	    return false;
+	  for (j = 0; j < XVECLEN (pt, 2); j++)
+	    if (!subst_pattern_match (XVECEXP (x, x_vecexp_pos, j),
+				      XVECEXP (pt, 2, j), lineno))
+	      return false;
+	}
+
+      /* Ordinary operator.  */
+      else
+	{
+	  /* Compare operands number in X and PT.
+	     We count operands differently for X and PT since we compare
+	     an operator (with operands directly in RTX) and MATCH_OPERATOR
+	     (that has a vector with operands).  */
+	  if (GET_RTX_LENGTH (code) != XVECLEN (pt, 2))
+	    return false;
+	  for (j = 0; j < XVECLEN (pt, 2); j++)
+	    if (!subst_pattern_match (XEXP (x, j), XVECEXP (pt, 2, j), lineno))
+	      return false;
+	}
+
+      /* Store the operand to OPERAND_DATA array.  */
+      gcc_assert (XINT (pt, 0) >= 0 && XINT (pt, 0) < MAX_OPERANDS);
+      operand_data[XINT (pt, 0)] = x;
+      return true;
+    }
+
+  if (code_pt == MATCH_PAR_DUP
+      || code_pt == MATCH_DUP
+      || code_pt == MATCH_OP_DUP
+      || code_pt == MATCH_SCRATCH
+      || code_pt == MATCH_PARALLEL)
+    {
+      /* Currently interface for these constructions isn't defined -
+	 probably they aren't needed in input template of define_subst at all.
+	 So, for now their usage in define_subst is forbidden.  */
+      error_with_line (lineno, "%s cannot be used in define_subst",
+		       GET_RTX_NAME (code_pt));
+    }
+
+  gcc_assert (code != MATCH_PAR_DUP
+      && code_pt != MATCH_DUP
+      && code_pt != MATCH_OP_DUP
+      && code_pt != MATCH_SCRATCH
+      && code_pt != MATCH_PARALLEL
+      && code_pt != MATCH_OPERAND
+      && code_pt != MATCH_OPERATOR);
+  /* If PT is none of the handled above, then we match only expressions with
+     the same code in X.  */
+  if (code != code_pt)
+    return false;
+
+  fmt = GET_RTX_FORMAT (code_pt);
+  len = GET_RTX_LENGTH (code_pt);
+
+  for (i = 0; i < len; i++)
+    {
+      if (fmt[i] == '0')
+	break;
+
+      switch (fmt[i])
+	{
+	case 'i': case 'w': case 's':
+	  continue;
+
+	case 'e': case 'u':
+	  if (!subst_pattern_match (XEXP (x, i), XEXP (pt, i), lineno))
+	    return false;
+	  break;
+	case 'E':
+	  {
+	    if (XVECLEN (x, i) != XVECLEN (pt, i))
+	      return false;
+	    for (j = 0; j < XVECLEN (pt, i); j++)
+	      if (!subst_pattern_match (XVECEXP (x, i, j), XVECEXP (pt, i, j),
+					lineno))
+		return false;
+	    break;
+	  }
+	default:
+	  gcc_unreachable ();
+	}
+    }
+
+  return true;
+}
+
 /* Examine the attribute "predicable"; discover its boolean values
    and its default.  */
 
@@ -662,6 +984,78 @@ n_alternatives (const char *s)
   return n;
 }
 
+/* The routine scans rtl PATTERN, find match_operand in it and counts
+   number of alternatives.  If PATTERN contains several match_operands
+   with different number of alternatives, error is emitted, and the
+   routine returns 0.  If all match_operands in PATTERN have the same
+   number of alternatives, it's stored in N_ALT, and the routine returns 1.
+   Argument LINENO is used in when the error is emitted.  */
+static int
+get_alternatives_number (rtx pattern, int *n_alt, int lineno)
+{
+  const char *fmt;
+  enum rtx_code code;
+  int i, j, len;
+
+  if (!n_alt)
+    return 0;
+
+  code = GET_CODE (pattern);
+  switch (code)
+    {
+    case MATCH_OPERAND:
+      i = n_alternatives (XSTR (pattern, 2));
+      /* n_alternatives returns 1 if constraint string is empty -
+	 here we fix it up.  */
+      if (!*(XSTR (pattern, 2)))
+	i = 0;
+      if (*n_alt <= 0)
+	*n_alt = i;
+
+      else if (i && i != *n_alt)
+	{
+	  error_with_line (lineno,
+			   "wrong number of alternatives in operand %d",
+			   XINT (pattern, 0));
+	  return 0;
+	}
+
+    default:
+      break;
+    }
+
+  fmt = GET_RTX_FORMAT (code);
+  len = GET_RTX_LENGTH (code);
+  for (i = 0; i < len; i++)
+    {
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  if (!get_alternatives_number (XEXP (pattern, i), n_alt, lineno))
+		return 0;
+	  break;
+
+	case 'V':
+	  if (XVEC (pattern, i) == NULL)
+	    break;
+
+	case 'E':
+	  for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
+	    if (!get_alternatives_number (XVECEXP (pattern, i, j),
+					  n_alt, lineno))
+		return 0;
+	  break;
+
+	case 'i': case 'w': case '0': case 's': case 'S': case 'T':
+	  break;
+
+	default:
+	  gcc_unreachable ();
+	}
+    }
+    return 1;
+}
+
 /* Determine how many alternatives there are in INSN, and how many
    operands.  */
 
@@ -746,7 +1140,7 @@ alter_predicate_for_insn (rtx pattern, int alt, int max_op, int lineno)
 	  {
 	    size_t c_len = strlen (c);
 	    size_t len = alt * (c_len + 1);
-	    char *new_c = XNEWVEC(char, len);
+	    char *new_c = XNEWVEC (char, len);
 
 	    memcpy (new_c, c, c_len);
 	    for (i = 1; i < alt; ++i)
@@ -806,6 +1200,64 @@ alter_predicate_for_insn (rtx pattern, int alt, int max_op, int lineno)
   return pattern;
 }
 
+/* Duplicate constraints in PATTERN.  If pattern is from original
+   rtl-template, we need to duplicate each alternative - for that we
+   need to use duplicate_each_alternative () as a functor ALTER.
+   If pattern is from output-pattern of define_subst, we need to
+   duplicate constraints in another way - with duplicate_alternatives ().
+   N_DUP is multiplication factor.  */
+static rtx
+alter_constraints (rtx pattern, int n_dup, constraints_handler_t alter)
+{
+  const char *fmt;
+  enum rtx_code code;
+  int i, j, len;
+
+  code = GET_CODE (pattern);
+  switch (code)
+    {
+    case MATCH_OPERAND:
+      XSTR (pattern, 2) = alter (XSTR (pattern, 2), n_dup);
+      break;
+
+    default:
+      break;
+    }
+
+  fmt = GET_RTX_FORMAT (code);
+  len = GET_RTX_LENGTH (code);
+  for (i = 0; i < len; i++)
+    {
+      rtx r;
+
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  r = alter_constraints (XEXP (pattern, i), n_dup, alter);
+	  if (r == NULL)
+	    return r;
+	  break;
+
+	case 'E':
+	  for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
+	    {
+	      r = alter_constraints (XVECEXP (pattern, i, j), n_dup, alter);
+	      if (r == NULL)
+		return r;
+	    }
+	  break;
+
+	case 'i': case 'w': case '0': case 's':
+	  break;
+
+	default:
+	  break;
+	}
+    }
+
+  return pattern;
+}
+
 static const char *
 alter_test_for_insn (struct queue_elem *ce_elem,
 		     struct queue_elem *insn_elem)
@@ -920,7 +1372,7 @@ alter_attrs_for_insn (rtx insn)
   if (!global_changes_made)
     {
       struct queue_elem *elem;
-      
+
       global_changes_made = true;
       add_define_attr ("ce_enabled");
       add_define_attr ("nonce_enabled");
@@ -954,23 +1406,63 @@ alter_attrs_for_insn (rtx insn)
   XVEC (insn, 4) = new_vec;
 }
 
-/* Adjust all of the operand numbers in SRC to match the shift they'll
-   get from an operand displacement of DISP.  Return a pointer after the
-   adjusted string.  */
-
-static char *
-shift_output_template (char *dest, const char *src, int disp)
+/* As number of constraints is changed after define_subst, we need to
+   process attributes as well - we need to duplicate them the same way
+   that we duplicated constraints in original pattern
+   ELEM is a queue element, containing our rtl-template,
+   N_DUP - multiplication factor.  */
+static void
+alter_attrs_for_subst_insn (struct queue_elem * elem, int n_dup)
 {
-  while (*src)
+  rtvec vec = XVEC (elem->data, 4);
+  int num_elem;
+  int i;
+
+  if (n_dup < 2 || ! vec)
+    return;
+
+  num_elem = GET_NUM_ELEM (vec);
+  for (i = num_elem - 1; i >= 0; --i)
     {
-      char c = *src++;
-      *dest++ = c;
-      if (c == '%')
+      rtx sub = RTVEC_ELT (vec, i);
+      switch (GET_CODE (sub))
 	{
-	  c = *src++;
-	  if (ISDIGIT ((unsigned char) c))
-	    c += disp;
-	  else if (ISALPHA (c))
+	case SET_ATTR:
+	  if (strchr (XSTR (sub, 1), ',') != NULL)
+	    XSTR (sub, 1) = duplicate_alternatives (XSTR (sub, 1), n_dup);
+	    break;
+
+	case SET_ATTR_ALTERNATIVE:
+	case SET:
+	  error_with_line (elem->lineno,
+			   "%s: `define_subst' does not support attributes "
+			   "assigned by `set' and `set_attr_alternative'",
+			   XSTR (elem->data, 0));
+	  return;
+
+	default:
+	  gcc_unreachable ();
+	}
+    }
+}
+
+/* Adjust all of the operand numbers in SRC to match the shift they'll
+   get from an operand displacement of DISP.  Return a pointer after the
+   adjusted string.  */
+
+static char *
+shift_output_template (char *dest, const char *src, int disp)
+{
+  while (*src)
+    {
+      char c = *src++;
+      *dest++ = c;
+      if (c == '%')
+	{
+	  c = *src++;
+	  if (ISDIGIT ((unsigned char) c))
+	    c += disp;
+	  else if (ISALPHA (c))
 	    {
 	      *dest++ = c;
 	      c = *src++ + disp;
@@ -1008,7 +1500,7 @@ alter_output_for_insn (struct queue_elem *ce_elem,
   if (*insn_out == '@')
     {
       len = (ce_len + 1) * alt + insn_len + 1;
-      p = result = XNEWVEC(char, len);
+      p = result = XNEWVEC (char, len);
 
       do
 	{
@@ -1042,6 +1534,136 @@ alter_output_for_insn (struct queue_elem *ce_elem,
   return result;
 }
 
+/* From string STR "a,b,c" produce "a,b,c,a,b,c,a,b,c", i.e. original
+   string, duplicated N_DUP times.  */
+
+static const char *
+duplicate_alternatives (const char * str, int n_dup)
+{
+  int i, len, new_len;
+  char *result, *sp;
+  const char *cp;
+
+  if (n_dup < 2)
+    return str;
+
+  while (ISSPACE (*str))
+    str++;
+
+  if (*str == '\0')
+    return str;
+
+  cp = str;
+  len = strlen (str);
+  new_len = (len + 1) * n_dup;
+
+  sp = result = XNEWVEC (char, new_len);
+
+  /* Global modifier characters mustn't be duplicated: skip if found.  */
+  if (*cp == '=' || *cp == '+' || *cp == '%')
+    {
+      *sp++ = *cp++;
+      len--;
+    }
+
+  /* Copy original constraints N_DUP times.  */
+  for (i = 0; i < n_dup; i++, sp += len+1)
+    {
+      memcpy (sp, cp, len);
+      *(sp+len) = (i == n_dup - 1) ? '\0' : ',';
+    }
+
+  return result;
+}
+
+/* From string STR "a,b,c" produce "a,a,a,b,b,b,c,c,c", i.e. string where
+   each alternative from the original string is duplicated N_DUP times.  */
+static const char *
+duplicate_each_alternative (const char * str, int n_dup)
+{
+  int i, len, new_len;
+  char *result, *sp, *ep, *cp;
+
+  if (n_dup < 2)
+    return str;
+
+  while (ISSPACE (*str))
+    str++;
+
+  if (*str == '\0')
+    return str;
+
+  cp = xstrdup (str);
+
+  new_len = (strlen (cp) + 1) * n_dup;
+
+  sp = result = XNEWVEC (char, new_len);
+
+  /* Global modifier characters mustn't be duplicated: skip if found.  */
+  if (*cp == '=' || *cp == '+' || *cp == '%')
+      *sp++ = *cp++;
+
+  do
+    {
+      if ((ep = strchr (cp, ',')) != NULL)
+	*ep++ = '\0';
+      len = strlen (cp);
+
+      /* Copy a constraint N_DUP times.  */
+      for (i = 0; i < n_dup; i++, sp += len + 1)
+	{
+	  memcpy (sp, cp, len);
+	  *(sp+len) = (ep == NULL && i == n_dup - 1) ? '\0' : ',';
+	}
+
+      cp = ep;
+    }
+  while (cp != NULL);
+
+  return result;
+}
+
+/* Alter the output of INSN whose pattern was modified by
+   DEFINE_SUBST.  We must replicate output strings according
+   to the new number of alternatives ALT in substituted pattern.
+   If ALT equals 1, output has one alternative or defined by C
+   code, then output is returned without any changes.  */
+
+static const char *
+alter_output_for_subst_insn (rtx insn, int alt)
+{
+  const char *insn_out, *sp ;
+  char *old_out, *new_out, *cp;
+  int i, j, new_len;
+
+  insn_out = XTMPL (insn, 3);
+
+  if (alt < 2 || *insn_out == '*' || *insn_out != '@')
+    return insn_out;
+
+  old_out = XNEWVEC (char, strlen (insn_out)),
+  sp = insn_out;
+
+  while (ISSPACE (*sp) || *sp == '@')
+    sp++;
+
+  for (i = 0; *sp;)
+    old_out[i++] = *sp++;
+
+  new_len = alt * (i + 1) + 1;
+
+  new_out = XNEWVEC (char, new_len);
+  new_out[0] = '@';
+
+  for (j = 0, cp = new_out + 1; j < alt; j++, cp += i + 1)
+    {
+      memcpy (cp, old_out, i);
+      *(cp+i) = (j == alt - 1) ? '\0' : '\n';
+    }
+
+  return new_out;
+}
+
 /* Replicate insns as appropriate for the given DEFINE_COND_EXEC.  */
 
 static void
@@ -1151,6 +1773,411 @@ process_one_cond_exec (struct queue_elem *ce_elem)
     }
 }
 
+/* Try to apply define_substs to the given ELEM.
+   Only define_substs, specified via attributes would be applied.
+   If attribute, requiring define_subst, is set, but no define_subst
+   was applied, ELEM would be deleted.  */
+
+static void
+process_substs_on_one_elem (struct queue_elem *elem,
+			    struct queue_elem *queue)
+{
+  struct queue_elem *subst_elem;
+  int i, j, patterns_match;
+
+  for (subst_elem = define_subst_queue;
+       subst_elem; subst_elem = subst_elem->next)
+    {
+      int alternatives, alternatives_subst;
+      rtx subst_pattern;
+      rtvec subst_pattern_vec;
+
+      if (!has_subst_attribute (elem, subst_elem))
+	continue;
+
+      /* Compare original rtl-pattern from define_insn with input
+	 pattern from define_subst.
+	 Also, check if numbers of alternatives are the same in all
+	 match_operands.  */
+      if (XVECLEN (elem->data, 1) != XVECLEN (subst_elem->data, 1))
+	continue;
+      patterns_match = 1;
+      alternatives = -1;
+      alternatives_subst = -1;
+      for (j = 0; j < XVECLEN (elem->data, 1); j++)
+	{
+	  if (!subst_pattern_match (XVECEXP (elem->data, 1, j),
+				    XVECEXP (subst_elem->data, 1, j),
+				    subst_elem->lineno))
+	    {
+	      patterns_match = 0;
+	      break;
+	    }
+
+	  if (!get_alternatives_number (XVECEXP (elem->data, 1, j),
+					&alternatives, subst_elem->lineno))
+	    {
+	      patterns_match = 0;
+	      break;
+	    }
+	}
+
+      /* Check if numbers of alternatives are the same in all
+	 match_operands in output template of define_subst.  */
+      for (j = 0; j < XVECLEN (subst_elem->data, 3); j++)
+	{
+	  if (!get_alternatives_number (XVECEXP (subst_elem->data, 3, j),
+					&alternatives_subst,
+					subst_elem->lineno))
+	    {
+	      patterns_match = 0;
+	      break;
+	    }
+	}
+
+      if (!patterns_match)
+	continue;
+
+      /* Clear array in which we save occupied indexes of operands.  */
+      memset (used_operands_numbers, 0, sizeof (used_operands_numbers));
+
+      /* Create a pattern, based on the output one from define_subst.  */
+      subst_pattern_vec = rtvec_alloc (XVECLEN (subst_elem->data, 3));
+      for (j = 0; j < XVECLEN (subst_elem->data, 3); j++)
+	{
+	  subst_pattern = copy_rtx (XVECEXP (subst_elem->data, 3, j));
+
+	  /* Duplicate constraints in substitute-pattern.  */
+	  subst_pattern = alter_constraints (subst_pattern, alternatives,
+					     duplicate_each_alternative);
+
+	  subst_pattern = adjust_operands_numbers (subst_pattern);
+
+	  /* Substitute match_dup and match_op_dup in the new pattern and
+	     duplicate constraints.  */
+	  subst_pattern = subst_dup (subst_pattern, alternatives,
+				     alternatives_subst);
+
+	  replace_duplicating_operands_in_pattern (subst_pattern);
+
+	  /* We don't need any constraints in DEFINE_EXPAND.  */
+	  if (GET_CODE (elem->data) == DEFINE_EXPAND)
+	    remove_constraints (subst_pattern);
+
+	  RTVEC_ELT (subst_pattern_vec, j) = subst_pattern;
+	}
+      XVEC (elem->data, 1) = subst_pattern_vec;
+
+      for (i = 0; i < MAX_OPERANDS; i++)
+	  match_operand_entries_in_pattern[i] = NULL;
+
+      if (GET_CODE (elem->data) == DEFINE_INSN)
+	{
+	  XTMPL (elem->data, 3) =
+	    alter_output_for_subst_insn (elem->data, alternatives_subst);
+	  alter_attrs_for_subst_insn (elem, alternatives_subst);
+	}
+
+      /* Recalculate condition, joining conditions from original and
+	 DEFINE_SUBST input patterns.  */
+      XSTR (elem->data, 2) = join_c_conditions (XSTR (subst_elem->data, 2),
+						XSTR (elem->data, 2));
+      /* Mark that subst was applied by changing attribute from "yes"
+	 to "no".  */
+      change_subst_attribute (elem, subst_elem, subst_false);
+    }
+
+  /* If ELEM contains a subst attribute with value "yes", then we
+     expected that a subst would be applied, but it wasn't - so,
+     we need to remove that elementto avoid duplicating.  */
+  for (subst_elem = define_subst_queue;
+       subst_elem; subst_elem = subst_elem->next)
+    {
+      if (has_subst_attribute (elem, subst_elem))
+	{
+	  remove_from_queue (elem, &queue);
+	  return;
+	}
+    }
+}
+
+/* This is a subroutine of mark_operands_used_in_match_dup.
+   This routine is marks all MATCH_OPERANDs inside PATTERN as occupied.  */
+static void
+mark_operands_from_match_dup (rtx pattern)
+{
+  const char *fmt;
+  int i, j, len, opno;
+
+  if (GET_CODE (pattern) == MATCH_OPERAND)
+    {
+      opno = XINT (pattern, 0);
+      gcc_assert (opno >= 0 && opno < MAX_OPERANDS);
+      used_operands_numbers [opno] = 1;
+    }
+  fmt = GET_RTX_FORMAT (GET_CODE (pattern));
+  len = GET_RTX_LENGTH (GET_CODE (pattern));
+  for (i = 0; i < len; i++)
+    {
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  mark_operands_from_match_dup (XEXP (pattern, i));
+	  break;
+	case 'E':
+	  for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
+	    mark_operands_from_match_dup (XVECEXP (pattern, i, j));
+	  break;
+	}
+    }
+}
+
+/* This is a subroutine of adjust_operands_numbers.
+   It goes through all expressions in PATTERN and when MATCH_DUP is
+   met, all MATCH_OPERANDs inside it is marked as occupied.  The
+   process of marking is done by routin mark_operands_from_match_dup.  */
+static void
+mark_operands_used_in_match_dup (rtx pattern)
+{
+  const char *fmt;
+  int i, j, len, opno;
+
+  if (GET_CODE (pattern) == MATCH_DUP)
+    {
+      opno = XINT (pattern, 0);
+      gcc_assert (opno >= 0 && opno < MAX_OPERANDS);
+      mark_operands_from_match_dup (operand_data[opno]);
+      return;
+    }
+  fmt = GET_RTX_FORMAT (GET_CODE (pattern));
+  len = GET_RTX_LENGTH (GET_CODE (pattern));
+  for (i = 0; i < len; i++)
+    {
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  mark_operands_used_in_match_dup (XEXP (pattern, i));
+	  break;
+	case 'E':
+	  for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
+	    mark_operands_used_in_match_dup (XVECEXP (pattern, i, j));
+	  break;
+	}
+    }
+}
+
+/* This is subroutine of renumerate_operands_in_pattern.
+   It finds first not-occupied operand-index.  */
+static int
+find_first_unused_number_of_operand ()
+{
+  int i;
+  for (i = 0; i < MAX_OPERANDS; i++)
+    if (!used_operands_numbers[i])
+      return i;
+  return MAX_OPERANDS;
+}
+
+/* This is subroutine of adjust_operands_numbers.
+   It visits all expressions in PATTERN and assigns not-occupied
+   operand indexes to MATCH_OPERANDs and MATCH_OPERATORs of this
+   PATTERN.  */
+static void
+renumerate_operands_in_pattern (rtx pattern)
+{
+  const char *fmt;
+  enum rtx_code code;
+  int i, j, len, new_opno;
+  code = GET_CODE (pattern);
+
+  if (code == MATCH_OPERAND
+      || code == MATCH_OPERATOR)
+    {
+      new_opno = find_first_unused_number_of_operand ();
+      gcc_assert (new_opno >= 0 && new_opno < MAX_OPERANDS);
+      XINT (pattern, 0) = new_opno;
+      used_operands_numbers [new_opno] = 1;
+    }
+
+  fmt = GET_RTX_FORMAT (GET_CODE (pattern));
+  len = GET_RTX_LENGTH (GET_CODE (pattern));
+  for (i = 0; i < len; i++)
+    {
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  renumerate_operands_in_pattern (XEXP (pattern, i));
+	  break;
+	case 'E':
+	  for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
+	    renumerate_operands_in_pattern (XVECEXP (pattern, i, j));
+	  break;
+	}
+    }
+}
+
+/* If output pattern of define_subst contains MATCH_DUP, then this
+   expression would be replaced with the pattern, matched with
+   MATCH_OPERAND from input pattern.  This pattern could contain any
+   number of MATCH_OPERANDs, MATCH_OPERATORs etc., so it's possible
+   that a MATCH_OPERAND from output_pattern (if any) would have the
+   same number, as MATCH_OPERAND from copied pattern.  To avoid such
+   indexes overlapping, we assign new indexes to MATCH_OPERANDs,
+   laying in the output pattern outside of MATCH_DUPs.  */
+static rtx
+adjust_operands_numbers (rtx pattern)
+{
+  mark_operands_used_in_match_dup (pattern);
+
+  renumerate_operands_in_pattern (pattern);
+
+  return pattern;
+}
+
+/* Generate RTL expression
+   (match_dup OPNO)
+   */
+static rtx
+generate_match_dup (int opno)
+{
+  rtx return_rtx = rtx_alloc (MATCH_DUP);
+  PUT_CODE (return_rtx, MATCH_DUP);
+  XINT (return_rtx, 0) = opno;
+  return return_rtx;
+}
+
+/* This routine checks all match_operands in PATTERN and if some of
+   have the same index, it replaces all of them except the first one  to
+   match_dup.
+   Usually, match_operands with the same indexes are forbidden, but
+   after define_subst copy an RTL-expression from original template,
+   indexes of existed and just-copied match_operands could coincide.
+   To fix it, we replace one of them with match_dup.  */
+static rtx
+replace_duplicating_operands_in_pattern (rtx pattern)
+{
+  const char *fmt;
+  int i, j, len, opno;
+  rtx mdup;
+
+  if (GET_CODE (pattern) == MATCH_OPERAND)
+    {
+      opno = XINT (pattern, 0);
+      gcc_assert (opno >= 0 && opno < MAX_OPERANDS);
+      if (match_operand_entries_in_pattern[opno] == NULL)
+	{
+	  match_operand_entries_in_pattern[opno] = pattern;
+	  return NULL;
+	}
+      else
+	{
+	  /* Compare predicates before replacing with match_dup.  */
+	  if (strcmp (XSTR (pattern, 1),
+		      XSTR (match_operand_entries_in_pattern[opno], 1)))
+	    {
+	      error ("duplicated match_operands with different predicates were"
+		     " found.");
+	      return NULL;
+	    }
+	  return generate_match_dup (opno);
+	}
+    }
+  fmt = GET_RTX_FORMAT (GET_CODE (pattern));
+  len = GET_RTX_LENGTH (GET_CODE (pattern));
+  for (i = 0; i < len; i++)
+    {
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  mdup = replace_duplicating_operands_in_pattern (XEXP (pattern, i));
+	  if (mdup)
+	    XEXP (pattern, i) = mdup;
+	  break;
+	case 'E':
+	  for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
+	    {
+	      mdup =
+		replace_duplicating_operands_in_pattern (XVECEXP
+							 (pattern, i, j));
+	      if (mdup)
+		XVECEXP (pattern, i, j) = mdup;
+	    }
+	  break;
+	}
+    }
+  return NULL;
+}
+
+/* The routine modifies given input PATTERN of define_subst, replacing
+   MATCH_DUP and MATCH_OP_DUP with operands from define_insn original
+   pattern, whose operands are stored in OPERAND_DATA array.
+   It also duplicates constraints in operands - constraints from
+   define_insn operands are duplicated N_SUBST_ALT times, constraints
+   from define_subst operands are duplicated N_ALT times.
+   After the duplication, returned output rtl-pattern contains every
+   combination of input constraints Vs constraints from define_subst
+   output.  */
+static rtx
+subst_dup (rtx pattern, int n_alt, int n_subst_alt)
+{
+  const char *fmt;
+  enum rtx_code code;
+  int i, j, len, opno;
+
+  code = GET_CODE (pattern);
+  switch (code)
+    {
+    case MATCH_DUP:
+    case MATCH_OP_DUP:
+      opno = XINT (pattern, 0);
+
+      gcc_assert (opno >= 0 && opno < MAX_OPERANDS);
+
+      if (operand_data[opno])
+	{
+	  pattern = copy_rtx (operand_data[opno]);
+
+	  /* Duplicate constraints.  */
+	  pattern = alter_constraints (pattern, n_subst_alt,
+				       duplicate_alternatives);
+	}
+      break;
+
+    default:
+      break;
+    }
+
+  fmt = GET_RTX_FORMAT (GET_CODE (pattern));
+  len = GET_RTX_LENGTH (GET_CODE (pattern));
+  for (i = 0; i < len; i++)
+    {
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  if (code != MATCH_DUP && code != MATCH_OP_DUP)
+	    XEXP (pattern, i) = subst_dup (XEXP (pattern, i),
+					   n_alt, n_subst_alt);
+	  break;
+	case 'V':
+	  if (XVEC (pattern, i) == NULL)
+	    break;
+	case 'E':
+	  for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
+	    if (code != MATCH_DUP && code != MATCH_OP_DUP)
+	      XVECEXP (pattern, i, j) = subst_dup (XVECEXP (pattern, i, j),
+						   n_alt, n_subst_alt);
+	  break;
+
+	case 'i': case 'w': case '0': case 's': case 'S': case 'T':
+	  break;
+
+	default:
+	  gcc_unreachable ();
+	}
+    }
+  return pattern;
+}
+
 /* If we have any DEFINE_COND_EXEC patterns, expand the DEFINE_INSN
    patterns appropriately.  */
 
@@ -1166,6 +2193,42 @@ process_define_cond_exec (void)
   for (elem = define_cond_exec_queue; elem ; elem = elem->next)
     process_one_cond_exec (elem);
 }
+
+/* If we have any DEFINE_SUBST patterns, expand DEFINE_INSN and
+   DEFINE_EXPAND patterns appropriately.  */
+
+static void
+process_define_subst (void)
+{
+  struct queue_elem *elem, *elem_attr;
+
+  /* Check if each define_subst has corresponding define_subst_attr.  */
+  for (elem = define_subst_queue; elem ; elem = elem->next)
+    {
+      for (elem_attr = define_subst_attr_queue;
+	   elem_attr;
+	   elem_attr = elem_attr->next)
+	if (strcmp (XSTR (elem->data, 0), XSTR (elem_attr->data, 1)) == 0)
+	    goto found;
+
+	error_with_line (elem->lineno,
+			 "%s: `define_subst' must have at least one "
+			 "corresponding `define_subst_attr'",
+			 XSTR (elem->data, 0));
+	return;
+      found:
+	continue;
+    }
+
+  for (elem = define_insn_queue; elem ; elem = elem->next)
+    process_substs_on_one_elem (elem, define_insn_queue);
+  for (elem = other_queue; elem ; elem = elem->next)
+  {
+    if (GET_CODE (elem->data) != DEFINE_EXPAND)
+      continue;
+    process_substs_on_one_elem (elem, other_queue);
+  }
+}
 \f
 /* A read_md_files callback for reading an rtx.  */
 
@@ -1391,6 +2454,38 @@ gen_mnemonic_attr (void)
   XSTR (mnemonic_attr, 1) = XOBFINISH (&string_obstack, char *);
 }
 
+/* Check if there are DEFINE_ATTRs with the same name.  */
+static void
+check_define_attr_duplicates ()
+{
+  struct queue_elem *elem;
+  htab_t attr_htab;
+  char * attr_name;
+  void **slot;
+
+  attr_htab = htab_create (500, htab_hash_string, htab_eq_string, NULL);
+
+  for (elem = define_attr_queue; elem; elem = elem->next)
+    {
+      attr_name = xstrdup (XSTR (elem->data, 0));
+
+      slot = htab_find_slot (attr_htab, attr_name, INSERT);
+
+      /* Duplicate.  */
+      if (*slot)
+	{
+	  error_with_line (elem->lineno, "redefinition of attribute '%s'",
+			   attr_name);
+	  htab_delete (attr_htab);
+	  return;
+	}
+
+      *slot = attr_name;
+    }
+
+  htab_delete (attr_htab);
+}
+
 /* The entry point for initializing the reader.  */
 
 bool
@@ -1407,10 +2502,17 @@ init_rtx_reader_args_cb (int argc, char **argv,
 
   read_md_files (argc, argv, parse_opt, rtx_handle_directive);
 
+  if (define_attr_queue != NULL)
+    check_define_attr_duplicates ();
+
   /* Process define_cond_exec patterns.  */
   if (define_cond_exec_queue != NULL)
     process_define_cond_exec ();
 
+  /* Process define_subst patterns.  */
+  if (define_subst_queue != NULL)
+    process_define_subst ();
+
   if (define_attr_queue != NULL)
     gen_mnemonic_attr ();
 
@@ -1470,6 +2572,7 @@ read_md_rtx (int *lineno, int *seqnr)
     {
     case DEFINE_INSN:
     case DEFINE_EXPAND:
+    case DEFINE_SUBST:
       if (maybe_eval_c_test (XSTR (desc, 2)) != 0)
 	sequence_num++;
       else if (insn_elision)
diff --git a/gcc/read-rtl.c b/gcc/read-rtl.c
index 71ecf53..ef8ef4f 100644
--- a/gcc/read-rtl.c
+++ b/gcc/read-rtl.c
@@ -108,13 +108,28 @@ typedef struct attribute_use attribute_use;
 DEF_VEC_O (attribute_use);
 DEF_VEC_ALLOC_O (attribute_use, heap);
 
+/* This struct is used to link subst_attr named ATTR_NAME with
+   corresponding define_subst named ITER_NAME.  */
+struct subst_attr_to_iter_mapping
+{
+    char *attr_name;
+    char *iter_name;
+};
+
+/* Hash-table to store links between subst-attributes and
+   define_substs.  */
+htab_t subst_attr_to_iter_map = NULL;
+/* This global stores name of subst-iterator which is currently being
+   processed.  */
+const char *current_iterator_name;
+
 static void validate_const_int (const char *);
 static rtx read_rtx_code (const char *);
 static rtx read_nested_rtx (void);
 static rtx read_rtx_variadic (rtx);
 
 /* The mode and code iterator structures.  */
-static struct iterator_group modes, codes, ints;
+static struct iterator_group modes, codes, ints, substs;
 
 /* All iterators used in the current rtx.  */
 static VEC (mapping_ptr, heap) *current_iterators;
@@ -184,6 +199,91 @@ apply_int_iterator (void *loc, int value)
   *(int *)loc = value;
 }
 
+/* This routine adds attribute or does nothing depending on VALUE.  When
+   VALUE is 1, it does nothing - the first duplicate of original
+   template is kept untouched when it's subjected to a define_subst.
+   When VALUE isn't 1, the routine modifies RTL-template LOC, adding
+   attribute, named exactly as define_subst, which later will be
+   applied.  If such attribute has already been added, then no the
+   routine has no effect.  */
+static void
+apply_subst_iterator (void *loc, int value)
+{
+  rtx rt = (rtx)loc;
+  rtx new_attr;
+  rtvec attrs_vec, new_attrs_vec;
+  int i;
+  if (value == 1)
+    return;
+  gcc_assert (GET_CODE (rt) == DEFINE_INSN
+	      || GET_CODE (rt) == DEFINE_EXPAND);
+
+  attrs_vec = XVEC (rt, 4);
+
+  /* If we've already added attribute 'current_iterator_name', then we
+     have nothing to do now.  */
+  if (attrs_vec)
+    {
+      for (i = 0; i < GET_NUM_ELEM (attrs_vec); i++)
+	{
+	  if (strcmp (XSTR (attrs_vec->elem[i], 0), current_iterator_name) == 0)
+	    return;
+	}
+    }
+
+  /* Add attribute with subst name - it serves as a mark for
+     define_subst which later would be applied to this pattern.  */
+  new_attr = rtx_alloc (SET_ATTR);
+  PUT_CODE (new_attr, SET_ATTR);
+  XSTR (new_attr, 0) = xstrdup (current_iterator_name);
+  XSTR (new_attr, 1) = xstrdup ("yes");
+
+  if (!attrs_vec)
+    {
+      new_attrs_vec = rtvec_alloc (1);
+      new_attrs_vec->elem[0] = new_attr;
+    }
+  else
+    {
+      new_attrs_vec = rtvec_alloc (GET_NUM_ELEM (attrs_vec) + 1);
+      memcpy (&new_attrs_vec->elem[0], &attrs_vec->elem[0],
+	      GET_NUM_ELEM (attrs_vec) * sizeof (rtx));
+      new_attrs_vec->elem[GET_NUM_ELEM (attrs_vec)] = new_attr;
+    }
+  XVEC (rt, 4) = new_attrs_vec;
+}
+
+/* Map subst-attribute ATTR to subst iterator ITER.  */
+
+static void
+bind_subst_iter_and_attr (const char *iter, const char *attr)
+{
+  struct subst_attr_to_iter_mapping *value;
+  void **slot;
+  if (!subst_attr_to_iter_map)
+    subst_attr_to_iter_map =
+      htab_create (1, leading_string_hash, leading_string_eq_p, 0);
+  value = XNEW (struct subst_attr_to_iter_mapping);
+  value->attr_name = xstrdup (attr);
+  value->iter_name = xstrdup (iter);
+  slot = htab_find_slot (subst_attr_to_iter_map, value, INSERT);
+  *slot = value;
+}
+
+/* Return name of a subst-iterator, corresponding to subst-attribute ATTR.  */
+
+static char*
+find_subst_iter_by_attr (const char *attr)
+{
+  char *iter_name = NULL;
+  struct subst_attr_to_iter_mapping *value;
+  value = (struct subst_attr_to_iter_mapping*)
+    htab_find (subst_attr_to_iter_map, &attr);
+  if (value)
+    iter_name = value->iter_name;
+  return iter_name;
+}
+
 /* Map attribute string P to its current value.  Return null if the attribute
    isn't known.  */
 
@@ -222,11 +322,23 @@ map_attr_string (const char *p)
       /* Find the attribute specification.  */
       m = (struct mapping *) htab_find (iterator->group->attrs, &attr);
       if (m)
-	/* Find the attribute value associated with the current
-	   iterator value.  */
-	for (v = m->values; v; v = v->next)
-	  if (v->number == iterator->current_value->number)
-	    return v;
+	{
+	  /* In contrast to code/mode/int iterators, attributes of subst
+	     iterators are linked to one specific subst-iterator.  So, if
+	     we are dealing with subst-iterator, we should check if it's
+	     the one which linked with the given attribute.  */
+	  if (iterator->group == &substs)
+	    {
+	      char *iter_name = find_subst_iter_by_attr (attr);
+	      if (strcmp (iter_name, iterator->name) != 0)
+		continue;
+	    }
+	  /* Find the attribute value associated with the current
+	     iterator value.  */
+	  for (v = m->values; v; v = v->next)
+	    if (v->number == iterator->current_value->number)
+	      return v;
+	}
     }
   return NULL;
 }
@@ -343,6 +455,7 @@ add_condition_to_rtx (rtx x, const char *extra)
     {
     case DEFINE_INSN:
     case DEFINE_EXPAND:
+    case DEFINE_SUBST:
       XSTR (x, 2) = add_condition_to_string (XSTR (x, 2), extra);
       break;
 
@@ -432,6 +545,7 @@ apply_iterators (rtx original, rtx *queue)
   htab_traverse (modes.iterators, add_current_iterators, NULL);
   htab_traverse (codes.iterators, add_current_iterators, NULL);
   htab_traverse (ints.iterators, add_current_iterators, NULL);
+  htab_traverse (substs.iterators, add_current_iterators, NULL);
   gcc_assert (!VEC_empty (mapping_ptr, current_iterators));
 
   for (;;)
@@ -441,6 +555,8 @@ apply_iterators (rtx original, rtx *queue)
       condition = NULL;
       FOR_EACH_VEC_ELT (iterator_use, iterator_uses, i, iuse)
 	{
+	  if (iuse->iterator->group == &substs)
+	    continue;
 	  v = iuse->iterator->current_value;
 	  iuse->iterator->group->apply_iterator (iuse->ptr, v->number);
 	  condition = join_c_conditions (condition, v->string);
@@ -449,6 +565,19 @@ apply_iterators (rtx original, rtx *queue)
       x = copy_rtx_for_iterators (original);
       add_condition_to_rtx (x, condition);
 
+      /* We apply subst iterator after RTL-template is copied, as during
+	 subst-iterator processing, we could add an attribute to the
+	 RTL-template, and we don't want to do it in the original one.  */
+      FOR_EACH_VEC_ELT (iterator_use, iterator_uses, i, iuse)
+	{
+	  v = iuse->iterator->current_value;
+	  if (iuse->iterator->group == &substs)
+	    {
+	      iuse->ptr = x;
+	      current_iterator_name = iuse->iterator->name;
+	      iuse->iterator->group->apply_iterator (iuse->ptr, v->number);
+	    }
+	}
       /* Add the new rtx to the end of the queue.  */
       XEXP (*queue, 0) = x;
       XEXP (*queue, 1) = NULL_RTX;
@@ -544,6 +673,12 @@ initialize_iterators (void)
   ints.find_builtin = find_int;
   ints.apply_iterator = apply_int_iterator;
 
+  substs.attrs = htab_create (13, leading_string_hash, leading_string_eq_p, 0);
+  substs.iterators = htab_create (13, leading_string_hash,
+				 leading_string_eq_p, 0);
+  substs.find_builtin = find_int; /* We don't use it, anyway.  */
+  substs.apply_iterator = apply_subst_iterator;
+
   lower = add_mapping (&modes, modes.attrs, "mode");
   upper = add_mapping (&modes, modes.attrs, "MODE");
   lower_ptr = &lower->values;
@@ -793,6 +928,94 @@ read_mapping (struct iterator_group *group, htab_t table)
   return m;
 }
 
+/* For iterator with name ATTR_NAME generate define_attr with values
+   'yes' and 'no'.  This attribute is used to mark templates to which
+   define_subst ATTR_NAME should be applied.  This attribute is set and
+   defined implicitly and automatically.  */
+static void
+add_define_attr_for_define_subst (const char *attr_name, rtx *queue)
+{
+  rtx const_str, return_rtx;
+
+  return_rtx = rtx_alloc (DEFINE_ATTR);
+  PUT_CODE (return_rtx, DEFINE_ATTR);
+
+  const_str = rtx_alloc (CONST_STRING);
+  PUT_CODE (const_str, CONST_STRING);
+  XSTR (const_str, 0) = xstrdup ("no");
+
+  XSTR (return_rtx, 0) = xstrdup (attr_name);
+  XSTR (return_rtx, 1) = xstrdup ("no,yes");
+  XEXP (return_rtx, 2) = const_str;
+
+  XEXP (*queue, 0) = return_rtx;
+  XEXP (*queue, 1) = NULL_RTX;
+}
+
+/* This routine generates DEFINE_SUBST_ATTR expression with operands
+   ATTR_OPERANDS and places it to QUEUE.  */
+static void
+add_define_subst_attr (const char **attr_operands, rtx *queue)
+{
+  rtx return_rtx;
+  int i;
+
+  return_rtx = rtx_alloc (DEFINE_SUBST_ATTR);
+  PUT_CODE (return_rtx, DEFINE_SUBST_ATTR);
+
+  for (i = 0; i < 4; i++)
+    XSTR (return_rtx, i) = xstrdup (attr_operands[i]);
+
+  XEXP (*queue, 0) = return_rtx;
+  XEXP (*queue, 1) = NULL_RTX;
+}
+
+/* Read define_subst_attribute construction.  It has next form:
+	(define_subst_attribute <attribute_name> <iterator_name> <value1> <value2>)
+   Attribute is substituted with value1 when no subst is applied and with
+   value2 in the opposite case.
+   Attributes are added to SUBST_ATTRS_TABLE.
+   In case the iterator is encountered for the first time, it's added to
+   SUBST_ITERS_TABLE.  Also, implicit define_attr is generated.  */
+
+static void
+read_subst_mapping (htab_t subst_iters_table, htab_t subst_attrs_table,
+		    rtx *queue)
+{
+  struct mapping *m;
+  struct map_value **end_ptr;
+  const char *attr_operands[4];
+  rtx * queue_elem = queue;
+  int i;
+
+  for (i = 0; i < 4; i++)
+    attr_operands[i] = read_string (false);
+
+  add_define_subst_attr (attr_operands, queue_elem);
+
+  bind_subst_iter_and_attr (attr_operands[1], attr_operands[0]);
+
+  m = (struct mapping *) htab_find (substs.iterators, &attr_operands[1]);
+  if (!m)
+    {
+      m = add_mapping (&substs, subst_iters_table, attr_operands[1]);
+      end_ptr = &m->values;
+      end_ptr = add_map_value (end_ptr, 1, "");
+      end_ptr = add_map_value (end_ptr, 2, "");
+
+      /* Add element to the queue.  */
+      XEXP (*queue, 1) = rtx_alloc (EXPR_LIST);
+      queue_elem = &XEXP (*queue, 1);
+
+      add_define_attr_for_define_subst (attr_operands[1], queue_elem);
+    }
+
+  m = add_mapping (&substs, subst_attrs_table, attr_operands[0]);
+  end_ptr = &m->values;
+  end_ptr = add_map_value (end_ptr, 1, attr_operands[2]);
+  end_ptr = add_map_value (end_ptr, 2, attr_operands[3]);
+}
+
 /* Check newly-created code iterator ITERATOR to see whether every code has the
    same format.  */
 
@@ -863,6 +1086,19 @@ read_rtx (const char *rtx_name, rtx *x)
       read_mapping (&ints, ints.iterators);
       return false;
     }
+  if (strcmp (rtx_name, "define_subst_attr") == 0)
+    {
+      /* We are parsing DEFINE_SUBST_ATTR, which could cause generation
+	 of DEFINE_ATTR for introduced DEFINE_SUBST.  It doesn't happen
+	 if such DEFINE_ATTR has already been introduced.
+	 If this did happen, we need to return TRUE to process newly
+	 introduced DEFINE_ATTR.  */
+
+      read_subst_mapping (substs.iterators, substs.attrs, &queue_head);
+
+      *x = queue_head;
+      return true;
+    }
 
   apply_iterators (read_rtx_code (rtx_name), &queue_head);
   VEC_truncate (iterator_use, iterator_uses, 0);
@@ -881,12 +1117,15 @@ read_rtx_code (const char *code_name)
 {
   int i;
   RTX_CODE code;
-  struct mapping *iterator;
+  struct mapping *iterator, *m;
   const char *format_ptr;
   struct md_name name;
   rtx return_rtx;
   int c;
   HOST_WIDE_INT tmp_wide;
+  char *str;
+  char *start, *end, *ptr;
+  char tmpstr[256];
 
   /* Linked list structure for making RTXs: */
   struct rtx_list
@@ -1031,6 +1270,35 @@ read_rtx_code (const char *code_name)
 	      stringbuf = XOBFINISH (&string_obstack, char *);
 	    }
 
+	  /* Find attr-names in the string.  */
+	  ptr = &tmpstr[0];
+	  end = stringbuf;
+	  while ((start = strchr (end, '<')) && (end  = strchr (end, '>')))
+	    {
+	      if (start && end
+		  && (end - start - 1 > 0)
+		  && (end - start - 1 < (int)sizeof (tmpstr)))
+		{
+		  strncpy (tmpstr, start+1, end-start-1);
+		  tmpstr[end-start-1] = 0;
+		  end++;
+		}
+	      else
+		break;
+	      m = (struct mapping *) htab_find (substs.attrs, &ptr);
+	      if (m != 0)
+		{
+		  /* Here we should find linked subst-iter.  */
+		  str = find_subst_iter_by_attr (ptr);
+		  if (str)
+		    m = (struct mapping *) htab_find (substs.iterators, &str);
+		  else
+		    m = 0;
+		}
+	      if (m != 0)
+		record_iterator_use (m, return_rtx);
+	    }
+
 	  if (star_if_braced)
 	    XTMPL (return_rtx, i) = stringbuf;
 	  else
diff --git a/gcc/rtl.def b/gcc/rtl.def
index e8a6adf..06931d7 100644
--- a/gcc/rtl.def
+++ b/gcc/rtl.def
@@ -906,8 +906,9 @@ DEF_RTL_EXPR(DEFINE_PEEPHOLE2, "define_peephole2", "EsES", RTX_EXTRA)
 	This might, for example, create some RTX's and store them in
 	elements of `recog_data.operand' for use by the vector of
 	insn-patterns.
-	(`operands' is an alias here for `recog_data.operand').  */
-DEF_RTL_EXPR(DEFINE_EXPAND, "define_expand", "sEss", RTX_EXTRA)
+	(`operands' is an alias here for `recog_data.operand').
+   5th: optionally, a vector of attributes for this expand.  */
+DEF_RTL_EXPR(DEFINE_EXPAND, "define_expand", "sEssV", RTX_EXTRA)
 
 /* Define a requirement for delay slots.
    1st operand: Condition involving insn attributes that, if true,
@@ -1280,6 +1281,8 @@ DEF_RTL_EXPR (ATTR_FLAG, "attr_flag", "s", RTX_EXTRA)
    true, the second operand will be used as the value of the conditional.  */
 DEF_RTL_EXPR(COND, "cond", "Ee", RTX_EXTRA)
 
+DEF_RTL_EXPR(DEFINE_SUBST, "define_subst", "sEsE", RTX_EXTRA)
+DEF_RTL_EXPR(DEFINE_SUBST_ATTR, "define_subst_attr", "ssss", RTX_EXTRA)
 #endif /* GENERATOR_FILE */
 
 /*

Re: [PATCH, generic] New RTL primitive: `define_subst'

[Kirill Yukhin]

> Sounds great, (I think) this is something I've longed to see
> ever since I saw the iterator machinery (thanks, Richard S!) and
> wanted to do structural replacements just as easily.
Thanks!

> But... I don't really understand it, so here's some feedback on
> the documentation: Regarding the language, a definite article is
...
You're right, documentation must be improved and it will today/tomorrow
after English native-speakers review it.

We are looking for more feedbak on what can be understanded :)

Thanks, K

Re: [PATCH, generic] New RTL primitive: `define_subst'

[Kirill Yukhin]

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

Hi,

>> But... I don't really understand it, so here's some feedback on
>> the documentation: Regarding the language, a definite article is

Patch with fixed doc is attached. Changelog is the same

Is it OK?

Thanks, K

[-- Attachment #2: define_subst-5.patch --]
[-- Type: application/octet-stream, Size: 61915 bytes --]

diff --git a/gcc/doc/md.texi b/gcc/doc/md.texi
index bca0d8f..23d46cb 100644
--- a/gcc/doc/md.texi
+++ b/gcc/doc/md.texi
@@ -46,6 +46,8 @@ See the next chapter for information on the C header file.
 * Insn Attributes::     Specifying the value of attributes for generated insns.
 * Conditional Execution::Generating @code{define_insn} patterns for
                          predication.
+* Define Subst::	Generating @code{define_insn} and @code{define_expand}
+			patterns from other patterns.
 * Constant Definitions::Defining symbolic constants that can be used in the
                         md file.
 * Iterators::           Using iterators to generate patterns from a template.
@@ -6685,6 +6687,10 @@ Usually these statements prepare temporary registers for use as
 internal operands in the RTL template, but they can also generate RTL
 insns directly by calling routines such as @code{emit_insn}, etc.
 Any such insns precede the ones that come from the RTL template.
+
+@item
+Optionally, a vector containing the values of attributes. @xref{Insn
+Attributes}.
 @end itemize
 
 Every RTL insn emitted by a @code{define_expand} must match some
@@ -8819,6 +8825,213 @@ generates a new pattern
 
 @end ifset
 @ifset INTERNALS
+@node Define Subst
+@section RTL Templates Transformations
+@cindex define_subst
+
+For some hardware architectures there are common cases when the RTL
+templates for the instructions can be derived from the other RTL
+templates using simple transformations.  E.g., @file{i386.md} contains
+an RTL template for the ordinary @code{sub} instruction---
+@code{*subsi_1}, and for the @code{sub} instruction with subsequent
+zero-extension---@code{*subsi_1_zext}.  Such cases can be easily
+implemented by a single meta-template capable of generating a modified
+case based on the initial one:
+
+@findex define_subst
+@smallexample
+(define_subst "@var{name}"
+  [@var{input-template}]
+  "@var{condition}"
+  [@var{output-template}])
+@end smallexample
+@var{input-template} is a pattern describing the source RTL template,
+which will be transformed.
+
+@var{condition} is a C expression that is conjunct with the condition
+from the input-template to generate a condition to be used in the
+output-template.
+
+@var{output-template} is a pattern that will be used in the resulting
+template.
+
+@code{define_subst} mechanism is tightly coupled with the notion of the
+subst attribute (@xref{Subst Iterators}).  The use of
+@code{define_subst} is triggered by a reference to a subst attribute in
+the transforming RTL template.  This reference initiates duplication of
+the source RTL template and substitution of the attributes with their
+values.  The source RTL template is left unchanged, while the copy is
+transformed by @code{define_subst}.  This transformation can fail in the
+case when the source RTL template is not matched against the
+input-template of the @code{define_subst}.  In such case the copy is
+deleted.
+
+@code{define_subst} can be used only in @code{define_insn} and
+@code{define_expand}, it cannot be used in other expressions (e.g. in
+@code{define_insn_and_split}).
+
+@menu
+* Define Subst Example::	    Example of @code{define_subst} work.
+* Define Subst Pattern Matching::   Process of template comparison.
+* Define Subst Output Template::    Generation of output template.
+@end menu
+
+@node Define Subst Example
+@subsection @code{define_subst} Example
+@cindex define_subst
+
+To illustrate how @code{define_subst} works, let us examine a simple
+template transformation.
+
+Suppose there are two kinds of instructions: one that touches flags and
+the other that does not.  The instructions of the second type could be
+generated with the following @code{define_subst}:
+
+@smallexample
+(define_subst "add_clobber_subst"
+  [(set (match_operand:SI 0 "" "")
+        (match_operand:SI 1 "" ""))]
+  ""
+  [(set (match_dup 0)
+        (match_dup 1))
+   (clobber (reg:CC FLAGS_REG))]
+@end smallexample
+
+This @code{define_subst} can be applied to any RTL pattern containing
+@code{set} of mode SI and generates a copy with clobber when it is
+applied.
+
+Assume there is an RTL template for a @code{max} instruction to be used
+in @code{define_subst} mentioned above:
+
+@smallexample
+(define_insn "maxsi"
+  [(set (match_operand:SI 0 "register_operand" "=r")
+        (max:SI
+          (match_operand:SI 1 "register_operand" "r")
+          (match_operand:SI 2 "register_operand" "r")))]
+  ""
+  "max\t@{%2, %1, %0|%0, %1, %2@}"
+ [@dots{}])
+@end smallexample
+
+To mark the RTL template for @code{define_subst} application,
+subst-attributes are used.  They should be declared in advance:
+
+@smallexample
+(define_subst_attr "add_clobber_name" "add_clobber_subst" "_noclobber" "_clobber")
+@end smallexample
+
+Here @samp{add_clobber_name} is the attribute name,
+@samp{add_clobber_subst} is the name of the corresponding
+@code{define_subst}, the third argument (@samp{_noclobber}) is the
+attribute value that would be substituted into the unchanged version of
+the source RTL template, and the last argument (@samp{_clobber}) is the
+value that would be substituted into the second, transformed,
+version of the RTL template.
+
+Once the subst-attribute has been defined, it should be used in RTL
+templates which need to be processed by the @code{define_subst}.  So,
+the original RTL template should be changed:
+
+@smallexample
+(define_insn "maxsi<add_clobber_name>"
+  [(set (match_operand:SI 0 "register_operand" "=r")
+        (max:SI
+          (match_operand:SI 1 "register_operand" "r")
+          (match_operand:SI 2 "register_operand" "r")))]
+  ""
+  "max\t@{%2, %1, %0|%0, %1, %2@}"
+ [@dots{}])
+@end smallexample
+
+The result of the @code{define_subst} usage would look like the following:
+
+@smallexample
+(define_insn "maxsi_noclobber"
+  [(set (match_operand:SI 0 "register_operand" "=r")
+        (max:SI
+          (match_operand:SI 1 "register_operand" "r")
+          (match_operand:SI 2 "register_operand" "r")))]
+  ""
+  "max\t@{%2, %1, %0|%0, %1, %2@}"
+ [@dots{}])
+(define_insn "maxsi_clobber"
+  [(set (match_operand:SI 0 "register_operand" "=r")
+        (max:SI
+          (match_operand:SI 1 "register_operand" "r")
+          (match_operand:SI 2 "register_operand" "r")))
+   (clobber (reg:CC FLAGS_REG))]
+  ""
+  "max\t@{%2, %1, %0|%0, %1, %2@}"
+ [@dots{}])
+@end smallexample
+
+@node Define Subst Pattern Matching
+@subsection Pattern Matching in @code{define_subst}
+@cindex define_subst
+
+All expressions, allowed in @code{define_insn} or @code{define_expand},
+are allowed in the input-template of @code{define_subst}, except
+@code{match_par_dup}, @code{match_scratch}, @code{match_parallel}. The
+meanings of expressions in the input-template were changed:
+
+@code{match_operand} matches any expression (possibly, a subtree in
+RTL-template), if modes of the @code{match_operand} and this expression
+are the same, or mode of the @code{match_operand} is @code{VOIDmode}, or
+this expression is @code{match_dup}, @code{match_op_dup}.  If the
+expression is @code{match_operand} too, and predicate of
+@code{match_operand} from the input pattern is not empty, then the
+predicates are compared.  That can be used for more accurate filtering
+of accepted RTL-templates.
+
+@code{match_operator} matches common operators (like @code{plus},
+@code{minus}), @code{unspec}, @code{unspec_volatile} operators and
+@code{match_operator}s from the original pattern if the modes match and
+@code{match_operator} from the input pattern has the same number of
+operands as the operator from the original pattern.
+
+@node Define Subst Output Template
+@subsection Generation of output template in @code{define_subst}
+@cindex define_subst
+
+If all necessary checks for @code{define_subst} application pass, a new
+RTL-pattern, based on the output-template, is created to replace the old
+template.  Like in input-patterns, meanings of some RTL expressions are
+changed when they are used in output-patterns of a @code{define_subst}.
+Thus, @code{match_dup} is used for copying the whole expression from the
+original pattern, which matched corresponding @code{match_operand} from
+the input pattern.
+
+@code{match_dup N} is used in the output template to be replaced with
+the expression from the original pattern, which matched
+@code{match_operand N} from the input pattern.  As a consequence,
+@code{match_dup} cannot be used to point to @code{match_operand}s from
+the output pattern, it should always refer to a @code{match_operand}
+from the input pattern.
+
+In the output template one can refer to the expressions from the
+original pattern and create new ones.  For instance, some operands could
+be added by means of standard @code{match_operand}.
+
+After replacing @code{match_dup} with some RTL-subtree from the original
+pattern, it could happen that several @code{match_operand}s in the
+output pattern have the same indexes.  It is unknown, how many and what
+indexes would be used in the expression which would replace
+@code{match_dup}, so such conflicts in indexes are inevitable.  To
+overcome this issue, @code{match_operands} and @code{match_operators},
+which were introduced into the output pattern, are renumerated when all
+@code{match_dup}s are replaced.
+
+Number of alternatives in @code{match_operand}s introduced into the
+output template @code{M} could differ from the number of alternatives in
+the original pattern @code{N}, so in the resultant pattern there would
+be @code{N*M} alternatives.  Thus, constraints from the original pattern
+would be duplicated @code{N} times, constraints from the output pattern
+would be duplicated @code{M} times, producing all possible combinations.
+@end ifset
+
+@ifset INTERNALS
 @node Constant Definitions
 @section Constant Definitions
 @cindex constant definitions
@@ -9002,6 +9215,7 @@ facilities to make this process easier.
 * Mode Iterators::         Generating variations of patterns for different modes.
 * Code Iterators::         Doing the same for codes.
 * Int Iterators::          Doing the same for integers.
+* Subst Iterators::	   Generating variations of patterns for define_subst.
 @end menu
 
 @node Mode Iterators
@@ -9350,4 +9564,51 @@ This is equivalent to:
 
 @end smallexample
 
+@node Subst Iterators
+@subsection Subst Iterators
+@cindex subst iterators in @file{.md} files
+@findex define_subst
+@findex define_subst_attr
+
+Subst iterators are special type of iterators with the following
+restrictions: they could not be declared explicitly, they always have
+only two values, and they do not have explicit dedicated name.
+Subst-iterators are triggered only when corresponding subst-attribute is
+used in RTL-pattern.
+
+Subst iterators transform templates in the following way: the templates
+are duplicated, the subst-attributes in these templates are replaced
+with the corresponding values, and a new attribute is implicitly added
+to the given @code{define_insn}/@code{define_expand}.  The name of the
+added attribute matches the name of @code{define_subst}.  Such
+attributes are declared implicitly, and it is not allowed to have a
+@code{define_attr} named as a @code{define_subst}.
+
+Each subst iterator is linked to a @code{define_subst}.  It is declared
+implicitly by the first appearance of the corresponding
+@code{define_subst_attr}, and it is not allowed to define it explicitly.
+
+Declarations of subst-attributes have the following syntax:
+
+@findex define_subst_attr
+@smallexample
+(define_subst_attr "@var{name}"
+  "@var{subst-name}"
+  "@var{no-subst-value}"
+  "@var{subst-applied-value}")
+@end smallexample
+
+@var{name} is a string with which the given subst-attribute could be
+referred to.
+
+@var{subst-name} shows which @code{define_subst} should be applied to an
+RTL-template if the given subst-attribute is present in the
+RTL-template.
+
+@var{no-subst-value} is a value with which subst-attribute would be
+replaced in the first copy of the original RTL-template.
+
+@var{subst-applied-value} is a value with which subst-attribute would be
+replaced in the second copy of the original RTL-template.
+
 @end ifset
diff --git a/gcc/gensupport.c b/gcc/gensupport.c
index 44443e2..05e84e0 100644
--- a/gcc/gensupport.c
+++ b/gcc/gensupport.c
@@ -29,6 +29,12 @@
 #include "read-md.h"
 #include "gensupport.h"
 
+#define MAX_OPERANDS 40
+
+static rtx operand_data[MAX_OPERANDS];
+static rtx match_operand_entries_in_pattern[MAX_OPERANDS];
+static char used_operands_numbers[MAX_OPERANDS];
+
 
 /* In case some macros used by files we include need it, define this here.  */
 int target_flags;
@@ -48,10 +54,14 @@ static int predicable_default;
 static const char *predicable_true;
 static const char *predicable_false;
 
+static const char *subst_true = "yes";
+static const char *subst_false = "no";
+
 static htab_t condition_table;
 
-/* We initially queue all patterns, process the define_insn and
-   define_cond_exec patterns, then return them one at a time.  */
+/* We initially queue all patterns, process the define_insn,
+   define_cond_exec and define_subst patterns, then return
+   them one at a time.  */
 
 struct queue_elem
 {
@@ -75,8 +85,12 @@ static struct queue_elem *define_insn_queue;
 static struct queue_elem **define_insn_tail = &define_insn_queue;
 static struct queue_elem *define_cond_exec_queue;
 static struct queue_elem **define_cond_exec_tail = &define_cond_exec_queue;
+static struct queue_elem *define_subst_queue;
+static struct queue_elem **define_subst_tail = &define_subst_queue;
 static struct queue_elem *other_queue;
 static struct queue_elem **other_tail = &other_queue;
+static struct queue_elem *define_subst_attr_queue;
+static struct queue_elem **define_subst_attr_tail = &define_subst_attr_queue;
 
 static struct queue_elem *queue_pattern (rtx, struct queue_elem ***,
 					 const char *, int);
@@ -99,6 +113,24 @@ static void process_one_cond_exec (struct queue_elem *);
 static void process_define_cond_exec (void);
 static void init_predicate_table (void);
 static void record_insn_name (int, const char *);
+
+static bool has_subst_attribute (struct queue_elem *, struct queue_elem *);
+static bool subst_pattern_match (rtx, rtx, int);
+static int get_alternatives_number (rtx, int *, int);
+static const char * alter_output_for_subst_insn (rtx, int);
+static void alter_attrs_for_subst_insn (struct queue_elem *, int);
+static void process_substs_on_one_elem (struct queue_elem *,
+					struct queue_elem *);
+static rtx subst_dup (rtx, int, int);
+static void process_define_subst (void);
+
+static const char * duplicate_alternatives (const char *, int);
+static const char * duplicate_each_alternative (const char * str, int n_dup);
+
+typedef const char * (*constraints_handler_t) (const char *, int);
+static rtx alter_constraints (rtx, int, constraints_handler_t);
+static rtx adjust_operands_numbers (rtx);
+static rtx replace_duplicating_operands_in_pattern (rtx);
 \f
 /* Make a version of gen_rtx_CONST_INT so that GEN_INT can be used in
    the gensupport programs.  */
@@ -372,6 +404,27 @@ queue_pattern (rtx pattern, struct queue_elem ***list_tail,
   return e;
 }
 
+/* Remove element ELEM from QUEUE.  */
+static void
+remove_from_queue (struct queue_elem *elem, struct queue_elem **queue)
+{
+  struct queue_elem *prev, *e;
+  prev = NULL;
+  for (e = *queue; e ; e = e->next)
+    {
+      if (e == elem)
+	break;
+      prev = e;
+    }
+  if (e == NULL)
+    return;
+
+  if (prev)
+    prev->next = elem->next;
+  else
+    *queue = elem->next;
+}
+
 /* Build a define_attr for an binary attribute with name NAME and
    possible values "yes" and "no", and queue it.  */
 static void
@@ -439,6 +492,14 @@ process_rtx (rtx desc, int lineno)
       queue_pattern (desc, &define_cond_exec_tail, read_md_filename, lineno);
       break;
 
+    case DEFINE_SUBST:
+      queue_pattern (desc, &define_subst_tail, read_md_filename, lineno);
+      break;
+
+    case DEFINE_SUBST_ATTR:
+      queue_pattern (desc, &define_subst_attr_tail, read_md_filename, lineno);
+      break;
+
     case DEFINE_ATTR:
     case DEFINE_ENUM_ATTR:
       queue_pattern (desc, &define_attr_tail, read_md_filename, lineno);
@@ -584,6 +645,267 @@ is_predicable (struct queue_elem *elem)
   return 0;
 }
 
+/* Find attribute SUBST in ELEM and assign NEW_VALUE to it.  */
+static void
+change_subst_attribute (struct queue_elem *elem,
+			struct queue_elem *subst_elem,
+			const char *new_value)
+{
+  rtvec attrs_vec = XVEC (elem->data, 4);
+  const char *subst_name = XSTR (subst_elem->data, 0);
+  int i;
+
+  if (! attrs_vec)
+    return;
+
+  for (i = GET_NUM_ELEM (attrs_vec) - 1; i >= 0; --i)
+    {
+      rtx cur_attr = RTVEC_ELT (attrs_vec, i);
+      if (GET_CODE (cur_attr) != SET_ATTR)
+	continue;
+      if (strcmp (XSTR (cur_attr, 0), subst_name) == 0)
+	{
+	  XSTR (cur_attr, 1) = new_value;
+	  return;
+	}
+    }
+}
+
+/* Return true if ELEM has the attribute with the name of DEFINE_SUBST
+   represented by SUBST_ELEM and this attribute has value SUBST_TRUE.
+   DEFINE_SUBST isn't applied to patterns without such attribute.  In other
+   words, we suppose the default value of the attribute to be 'no' since it is
+   always generated automaticaly in read-rtl.c.  */
+static bool
+has_subst_attribute (struct queue_elem *elem, struct queue_elem *subst_elem)
+{
+  rtvec attrs_vec = XVEC (elem->data, 4);
+  const char *value, *subst_name = XSTR (subst_elem->data, 0);
+  int i;
+
+  if (! attrs_vec)
+    return false;
+
+  for (i = GET_NUM_ELEM (attrs_vec) - 1; i >= 0; --i)
+    {
+      rtx cur_attr = RTVEC_ELT (attrs_vec, i);
+      switch (GET_CODE (cur_attr))
+	{
+	case SET_ATTR:
+	  if (strcmp (XSTR (cur_attr, 0), subst_name) == 0)
+	    {
+	      value = XSTR (cur_attr, 1);
+	      goto found;
+	    }
+	  break;
+
+	case SET:
+	  if (GET_CODE (SET_DEST (cur_attr)) != ATTR
+	      || strcmp (XSTR (SET_DEST (cur_attr), 0), subst_name) != 0)
+	    break;
+	  cur_attr = SET_SRC (cur_attr);
+	  if (GET_CODE (cur_attr) == CONST_STRING)
+	    {
+	      value = XSTR (cur_attr, 0);
+	      goto found;
+	    }
+
+	  /* Only (set_attr "subst" "yes/no") and
+		  (set (attr "subst" (const_string "yes/no")))
+	     are currently allowed.  */
+	  error_with_line (elem->lineno,
+			   "unsupported value for `%s'", subst_name);
+	  return false;
+
+	case SET_ATTR_ALTERNATIVE:
+	  error_with_line (elem->lineno,
+			   "%s: `set_attr_alternative' is unsupported by "
+			   "`define_subst'",
+			   XSTR (elem->data, 0));
+	  return false;
+
+
+	default:
+	  gcc_unreachable ();
+	}
+    }
+
+  return false;
+
+ found:
+  if (strcmp (value, subst_true) == 0)
+    return true;
+  if (strcmp (value, subst_false) == 0)
+    return false;
+
+  error_with_line (elem->lineno,
+		   "unknown value `%s' for `%s' attribute", value, subst_name);
+  return false;
+}
+
+/* Compare RTL-template of original define_insn X to input RTL-template of
+   define_subst PT.  Return 1 if the templates match, 0 otherwise.
+   During the comparison, the routine also fills global_array OPERAND_DATA.  */
+static bool
+subst_pattern_match (rtx x, rtx pt, int lineno)
+{
+  RTX_CODE code, code_pt;
+  int i, j, len;
+  const char *fmt, *pred_name;
+
+  code = GET_CODE (x);
+  code_pt = GET_CODE (pt);
+
+  if (code_pt == MATCH_OPERAND)
+    {
+      /* MATCH_DUP, and MATCH_OP_DUP don't have a specified mode, so we
+	 always accept them.  */
+      if (GET_MODE (pt) != VOIDmode && GET_MODE (x) != GET_MODE (pt)
+	  && (code != MATCH_DUP && code != MATCH_OP_DUP))
+	return false; /* Modes don't match.  */
+
+      if (code == MATCH_OPERAND)
+	{
+	  pred_name = XSTR (pt, 1);
+	  if (pred_name[0] != 0)
+	    {
+	      const struct pred_data *pred_pt = lookup_predicate (pred_name);
+	      if (!pred_pt || pred_pt != lookup_predicate (XSTR (x, 1)))
+		return false; /* Predicates don't match.  */
+	    }
+	}
+
+      gcc_assert (XINT (pt, 0) >= 0 && XINT (pt, 0) < MAX_OPERANDS);
+      operand_data[XINT (pt, 0)] = x;
+      return true;
+    }
+
+  if (code_pt == MATCH_OPERATOR)
+    {
+      int x_vecexp_pos = -1;
+
+      /* Compare modes.  */
+      if (GET_MODE (pt) != VOIDmode && GET_MODE (x) != GET_MODE (pt))
+	return false;
+
+      /* In case X is also match_operator, compare predicates.  */
+      if (code == MATCH_OPERATOR)
+	{
+	  pred_name = XSTR (pt, 1);
+	  if (pred_name[0] != 0)
+	    {
+	      const struct pred_data *pred_pt = lookup_predicate (pred_name);
+	      if (!pred_pt || pred_pt != lookup_predicate (XSTR (x, 1)))
+		return false;
+	    }
+	}
+
+      /* Compare operands.
+	 MATCH_OPERATOR in input template could match in original template
+	 either 1) MATCH_OPERAND, 2) UNSPEC, 3) ordinary operation (like PLUS).
+	 In the first case operands are at (XVECEXP (x, 2, j)), in the second
+	 - at (XVECEXP (x, 0, j)), in the last one - (XEXP (x, j)).
+	 X_VECEXP_POS variable shows, where to look for these operands.  */
+      if (code == UNSPEC
+	  || code == UNSPEC_VOLATILE)
+	x_vecexp_pos = 0;
+      else if (code == MATCH_OPERATOR)
+	x_vecexp_pos = 2;
+      else
+	x_vecexp_pos = -1;
+
+      /* MATCH_OPERATOR or UNSPEC case.  */
+      if (x_vecexp_pos >= 0)
+	{
+	  /* Compare operands number in X and PT.  */
+	  if (XVECLEN (x, x_vecexp_pos) != XVECLEN (pt, 2))
+	    return false;
+	  for (j = 0; j < XVECLEN (pt, 2); j++)
+	    if (!subst_pattern_match (XVECEXP (x, x_vecexp_pos, j),
+				      XVECEXP (pt, 2, j), lineno))
+	      return false;
+	}
+
+      /* Ordinary operator.  */
+      else
+	{
+	  /* Compare operands number in X and PT.
+	     We count operands differently for X and PT since we compare
+	     an operator (with operands directly in RTX) and MATCH_OPERATOR
+	     (that has a vector with operands).  */
+	  if (GET_RTX_LENGTH (code) != XVECLEN (pt, 2))
+	    return false;
+	  for (j = 0; j < XVECLEN (pt, 2); j++)
+	    if (!subst_pattern_match (XEXP (x, j), XVECEXP (pt, 2, j), lineno))
+	      return false;
+	}
+
+      /* Store the operand to OPERAND_DATA array.  */
+      gcc_assert (XINT (pt, 0) >= 0 && XINT (pt, 0) < MAX_OPERANDS);
+      operand_data[XINT (pt, 0)] = x;
+      return true;
+    }
+
+  if (code_pt == MATCH_PAR_DUP
+      || code_pt == MATCH_DUP
+      || code_pt == MATCH_OP_DUP
+      || code_pt == MATCH_SCRATCH
+      || code_pt == MATCH_PARALLEL)
+    {
+      /* Currently interface for these constructions isn't defined -
+	 probably they aren't needed in input template of define_subst at all.
+	 So, for now their usage in define_subst is forbidden.  */
+      error_with_line (lineno, "%s cannot be used in define_subst",
+		       GET_RTX_NAME (code_pt));
+    }
+
+  gcc_assert (code != MATCH_PAR_DUP
+      && code_pt != MATCH_DUP
+      && code_pt != MATCH_OP_DUP
+      && code_pt != MATCH_SCRATCH
+      && code_pt != MATCH_PARALLEL
+      && code_pt != MATCH_OPERAND
+      && code_pt != MATCH_OPERATOR);
+  /* If PT is none of the handled above, then we match only expressions with
+     the same code in X.  */
+  if (code != code_pt)
+    return false;
+
+  fmt = GET_RTX_FORMAT (code_pt);
+  len = GET_RTX_LENGTH (code_pt);
+
+  for (i = 0; i < len; i++)
+    {
+      if (fmt[i] == '0')
+	break;
+
+      switch (fmt[i])
+	{
+	case 'i': case 'w': case 's':
+	  continue;
+
+	case 'e': case 'u':
+	  if (!subst_pattern_match (XEXP (x, i), XEXP (pt, i), lineno))
+	    return false;
+	  break;
+	case 'E':
+	  {
+	    if (XVECLEN (x, i) != XVECLEN (pt, i))
+	      return false;
+	    for (j = 0; j < XVECLEN (pt, i); j++)
+	      if (!subst_pattern_match (XVECEXP (x, i, j), XVECEXP (pt, i, j),
+					lineno))
+		return false;
+	    break;
+	  }
+	default:
+	  gcc_unreachable ();
+	}
+    }
+
+  return true;
+}
+
 /* Examine the attribute "predicable"; discover its boolean values
    and its default.  */
 
@@ -662,6 +984,78 @@ n_alternatives (const char *s)
   return n;
 }
 
+/* The routine scans rtl PATTERN, find match_operand in it and counts
+   number of alternatives.  If PATTERN contains several match_operands
+   with different number of alternatives, error is emitted, and the
+   routine returns 0.  If all match_operands in PATTERN have the same
+   number of alternatives, it's stored in N_ALT, and the routine returns 1.
+   Argument LINENO is used in when the error is emitted.  */
+static int
+get_alternatives_number (rtx pattern, int *n_alt, int lineno)
+{
+  const char *fmt;
+  enum rtx_code code;
+  int i, j, len;
+
+  if (!n_alt)
+    return 0;
+
+  code = GET_CODE (pattern);
+  switch (code)
+    {
+    case MATCH_OPERAND:
+      i = n_alternatives (XSTR (pattern, 2));
+      /* n_alternatives returns 1 if constraint string is empty -
+	 here we fix it up.  */
+      if (!*(XSTR (pattern, 2)))
+	i = 0;
+      if (*n_alt <= 0)
+	*n_alt = i;
+
+      else if (i && i != *n_alt)
+	{
+	  error_with_line (lineno,
+			   "wrong number of alternatives in operand %d",
+			   XINT (pattern, 0));
+	  return 0;
+	}
+
+    default:
+      break;
+    }
+
+  fmt = GET_RTX_FORMAT (code);
+  len = GET_RTX_LENGTH (code);
+  for (i = 0; i < len; i++)
+    {
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  if (!get_alternatives_number (XEXP (pattern, i), n_alt, lineno))
+		return 0;
+	  break;
+
+	case 'V':
+	  if (XVEC (pattern, i) == NULL)
+	    break;
+
+	case 'E':
+	  for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
+	    if (!get_alternatives_number (XVECEXP (pattern, i, j),
+					  n_alt, lineno))
+		return 0;
+	  break;
+
+	case 'i': case 'w': case '0': case 's': case 'S': case 'T':
+	  break;
+
+	default:
+	  gcc_unreachable ();
+	}
+    }
+    return 1;
+}
+
 /* Determine how many alternatives there are in INSN, and how many
    operands.  */
 
@@ -746,7 +1140,7 @@ alter_predicate_for_insn (rtx pattern, int alt, int max_op, int lineno)
 	  {
 	    size_t c_len = strlen (c);
 	    size_t len = alt * (c_len + 1);
-	    char *new_c = XNEWVEC(char, len);
+	    char *new_c = XNEWVEC (char, len);
 
 	    memcpy (new_c, c, c_len);
 	    for (i = 1; i < alt; ++i)
@@ -806,6 +1200,64 @@ alter_predicate_for_insn (rtx pattern, int alt, int max_op, int lineno)
   return pattern;
 }
 
+/* Duplicate constraints in PATTERN.  If pattern is from original
+   rtl-template, we need to duplicate each alternative - for that we
+   need to use duplicate_each_alternative () as a functor ALTER.
+   If pattern is from output-pattern of define_subst, we need to
+   duplicate constraints in another way - with duplicate_alternatives ().
+   N_DUP is multiplication factor.  */
+static rtx
+alter_constraints (rtx pattern, int n_dup, constraints_handler_t alter)
+{
+  const char *fmt;
+  enum rtx_code code;
+  int i, j, len;
+
+  code = GET_CODE (pattern);
+  switch (code)
+    {
+    case MATCH_OPERAND:
+      XSTR (pattern, 2) = alter (XSTR (pattern, 2), n_dup);
+      break;
+
+    default:
+      break;
+    }
+
+  fmt = GET_RTX_FORMAT (code);
+  len = GET_RTX_LENGTH (code);
+  for (i = 0; i < len; i++)
+    {
+      rtx r;
+
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  r = alter_constraints (XEXP (pattern, i), n_dup, alter);
+	  if (r == NULL)
+	    return r;
+	  break;
+
+	case 'E':
+	  for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
+	    {
+	      r = alter_constraints (XVECEXP (pattern, i, j), n_dup, alter);
+	      if (r == NULL)
+		return r;
+	    }
+	  break;
+
+	case 'i': case 'w': case '0': case 's':
+	  break;
+
+	default:
+	  break;
+	}
+    }
+
+  return pattern;
+}
+
 static const char *
 alter_test_for_insn (struct queue_elem *ce_elem,
 		     struct queue_elem *insn_elem)
@@ -920,7 +1372,7 @@ alter_attrs_for_insn (rtx insn)
   if (!global_changes_made)
     {
       struct queue_elem *elem;
-      
+
       global_changes_made = true;
       add_define_attr ("ce_enabled");
       add_define_attr ("nonce_enabled");
@@ -954,23 +1406,63 @@ alter_attrs_for_insn (rtx insn)
   XVEC (insn, 4) = new_vec;
 }
 
-/* Adjust all of the operand numbers in SRC to match the shift they'll
-   get from an operand displacement of DISP.  Return a pointer after the
-   adjusted string.  */
-
-static char *
-shift_output_template (char *dest, const char *src, int disp)
+/* As number of constraints is changed after define_subst, we need to
+   process attributes as well - we need to duplicate them the same way
+   that we duplicated constraints in original pattern
+   ELEM is a queue element, containing our rtl-template,
+   N_DUP - multiplication factor.  */
+static void
+alter_attrs_for_subst_insn (struct queue_elem * elem, int n_dup)
 {
-  while (*src)
+  rtvec vec = XVEC (elem->data, 4);
+  int num_elem;
+  int i;
+
+  if (n_dup < 2 || ! vec)
+    return;
+
+  num_elem = GET_NUM_ELEM (vec);
+  for (i = num_elem - 1; i >= 0; --i)
     {
-      char c = *src++;
-      *dest++ = c;
-      if (c == '%')
+      rtx sub = RTVEC_ELT (vec, i);
+      switch (GET_CODE (sub))
 	{
-	  c = *src++;
-	  if (ISDIGIT ((unsigned char) c))
-	    c += disp;
-	  else if (ISALPHA (c))
+	case SET_ATTR:
+	  if (strchr (XSTR (sub, 1), ',') != NULL)
+	    XSTR (sub, 1) = duplicate_alternatives (XSTR (sub, 1), n_dup);
+	    break;
+
+	case SET_ATTR_ALTERNATIVE:
+	case SET:
+	  error_with_line (elem->lineno,
+			   "%s: `define_subst' does not support attributes "
+			   "assigned by `set' and `set_attr_alternative'",
+			   XSTR (elem->data, 0));
+	  return;
+
+	default:
+	  gcc_unreachable ();
+	}
+    }
+}
+
+/* Adjust all of the operand numbers in SRC to match the shift they'll
+   get from an operand displacement of DISP.  Return a pointer after the
+   adjusted string.  */
+
+static char *
+shift_output_template (char *dest, const char *src, int disp)
+{
+  while (*src)
+    {
+      char c = *src++;
+      *dest++ = c;
+      if (c == '%')
+	{
+	  c = *src++;
+	  if (ISDIGIT ((unsigned char) c))
+	    c += disp;
+	  else if (ISALPHA (c))
 	    {
 	      *dest++ = c;
 	      c = *src++ + disp;
@@ -1008,7 +1500,7 @@ alter_output_for_insn (struct queue_elem *ce_elem,
   if (*insn_out == '@')
     {
       len = (ce_len + 1) * alt + insn_len + 1;
-      p = result = XNEWVEC(char, len);
+      p = result = XNEWVEC (char, len);
 
       do
 	{
@@ -1042,6 +1534,136 @@ alter_output_for_insn (struct queue_elem *ce_elem,
   return result;
 }
 
+/* From string STR "a,b,c" produce "a,b,c,a,b,c,a,b,c", i.e. original
+   string, duplicated N_DUP times.  */
+
+static const char *
+duplicate_alternatives (const char * str, int n_dup)
+{
+  int i, len, new_len;
+  char *result, *sp;
+  const char *cp;
+
+  if (n_dup < 2)
+    return str;
+
+  while (ISSPACE (*str))
+    str++;
+
+  if (*str == '\0')
+    return str;
+
+  cp = str;
+  len = strlen (str);
+  new_len = (len + 1) * n_dup;
+
+  sp = result = XNEWVEC (char, new_len);
+
+  /* Global modifier characters mustn't be duplicated: skip if found.  */
+  if (*cp == '=' || *cp == '+' || *cp == '%')
+    {
+      *sp++ = *cp++;
+      len--;
+    }
+
+  /* Copy original constraints N_DUP times.  */
+  for (i = 0; i < n_dup; i++, sp += len+1)
+    {
+      memcpy (sp, cp, len);
+      *(sp+len) = (i == n_dup - 1) ? '\0' : ',';
+    }
+
+  return result;
+}
+
+/* From string STR "a,b,c" produce "a,a,a,b,b,b,c,c,c", i.e. string where
+   each alternative from the original string is duplicated N_DUP times.  */
+static const char *
+duplicate_each_alternative (const char * str, int n_dup)
+{
+  int i, len, new_len;
+  char *result, *sp, *ep, *cp;
+
+  if (n_dup < 2)
+    return str;
+
+  while (ISSPACE (*str))
+    str++;
+
+  if (*str == '\0')
+    return str;
+
+  cp = xstrdup (str);
+
+  new_len = (strlen (cp) + 1) * n_dup;
+
+  sp = result = XNEWVEC (char, new_len);
+
+  /* Global modifier characters mustn't be duplicated: skip if found.  */
+  if (*cp == '=' || *cp == '+' || *cp == '%')
+      *sp++ = *cp++;
+
+  do
+    {
+      if ((ep = strchr (cp, ',')) != NULL)
+	*ep++ = '\0';
+      len = strlen (cp);
+
+      /* Copy a constraint N_DUP times.  */
+      for (i = 0; i < n_dup; i++, sp += len + 1)
+	{
+	  memcpy (sp, cp, len);
+	  *(sp+len) = (ep == NULL && i == n_dup - 1) ? '\0' : ',';
+	}
+
+      cp = ep;
+    }
+  while (cp != NULL);
+
+  return result;
+}
+
+/* Alter the output of INSN whose pattern was modified by
+   DEFINE_SUBST.  We must replicate output strings according
+   to the new number of alternatives ALT in substituted pattern.
+   If ALT equals 1, output has one alternative or defined by C
+   code, then output is returned without any changes.  */
+
+static const char *
+alter_output_for_subst_insn (rtx insn, int alt)
+{
+  const char *insn_out, *sp ;
+  char *old_out, *new_out, *cp;
+  int i, j, new_len;
+
+  insn_out = XTMPL (insn, 3);
+
+  if (alt < 2 || *insn_out == '*' || *insn_out != '@')
+    return insn_out;
+
+  old_out = XNEWVEC (char, strlen (insn_out)),
+  sp = insn_out;
+
+  while (ISSPACE (*sp) || *sp == '@')
+    sp++;
+
+  for (i = 0; *sp;)
+    old_out[i++] = *sp++;
+
+  new_len = alt * (i + 1) + 1;
+
+  new_out = XNEWVEC (char, new_len);
+  new_out[0] = '@';
+
+  for (j = 0, cp = new_out + 1; j < alt; j++, cp += i + 1)
+    {
+      memcpy (cp, old_out, i);
+      *(cp+i) = (j == alt - 1) ? '\0' : '\n';
+    }
+
+  return new_out;
+}
+
 /* Replicate insns as appropriate for the given DEFINE_COND_EXEC.  */
 
 static void
@@ -1151,6 +1773,411 @@ process_one_cond_exec (struct queue_elem *ce_elem)
     }
 }
 
+/* Try to apply define_substs to the given ELEM.
+   Only define_substs, specified via attributes would be applied.
+   If attribute, requiring define_subst, is set, but no define_subst
+   was applied, ELEM would be deleted.  */
+
+static void
+process_substs_on_one_elem (struct queue_elem *elem,
+			    struct queue_elem *queue)
+{
+  struct queue_elem *subst_elem;
+  int i, j, patterns_match;
+
+  for (subst_elem = define_subst_queue;
+       subst_elem; subst_elem = subst_elem->next)
+    {
+      int alternatives, alternatives_subst;
+      rtx subst_pattern;
+      rtvec subst_pattern_vec;
+
+      if (!has_subst_attribute (elem, subst_elem))
+	continue;
+
+      /* Compare original rtl-pattern from define_insn with input
+	 pattern from define_subst.
+	 Also, check if numbers of alternatives are the same in all
+	 match_operands.  */
+      if (XVECLEN (elem->data, 1) != XVECLEN (subst_elem->data, 1))
+	continue;
+      patterns_match = 1;
+      alternatives = -1;
+      alternatives_subst = -1;
+      for (j = 0; j < XVECLEN (elem->data, 1); j++)
+	{
+	  if (!subst_pattern_match (XVECEXP (elem->data, 1, j),
+				    XVECEXP (subst_elem->data, 1, j),
+				    subst_elem->lineno))
+	    {
+	      patterns_match = 0;
+	      break;
+	    }
+
+	  if (!get_alternatives_number (XVECEXP (elem->data, 1, j),
+					&alternatives, subst_elem->lineno))
+	    {
+	      patterns_match = 0;
+	      break;
+	    }
+	}
+
+      /* Check if numbers of alternatives are the same in all
+	 match_operands in output template of define_subst.  */
+      for (j = 0; j < XVECLEN (subst_elem->data, 3); j++)
+	{
+	  if (!get_alternatives_number (XVECEXP (subst_elem->data, 3, j),
+					&alternatives_subst,
+					subst_elem->lineno))
+	    {
+	      patterns_match = 0;
+	      break;
+	    }
+	}
+
+      if (!patterns_match)
+	continue;
+
+      /* Clear array in which we save occupied indexes of operands.  */
+      memset (used_operands_numbers, 0, sizeof (used_operands_numbers));
+
+      /* Create a pattern, based on the output one from define_subst.  */
+      subst_pattern_vec = rtvec_alloc (XVECLEN (subst_elem->data, 3));
+      for (j = 0; j < XVECLEN (subst_elem->data, 3); j++)
+	{
+	  subst_pattern = copy_rtx (XVECEXP (subst_elem->data, 3, j));
+
+	  /* Duplicate constraints in substitute-pattern.  */
+	  subst_pattern = alter_constraints (subst_pattern, alternatives,
+					     duplicate_each_alternative);
+
+	  subst_pattern = adjust_operands_numbers (subst_pattern);
+
+	  /* Substitute match_dup and match_op_dup in the new pattern and
+	     duplicate constraints.  */
+	  subst_pattern = subst_dup (subst_pattern, alternatives,
+				     alternatives_subst);
+
+	  replace_duplicating_operands_in_pattern (subst_pattern);
+
+	  /* We don't need any constraints in DEFINE_EXPAND.  */
+	  if (GET_CODE (elem->data) == DEFINE_EXPAND)
+	    remove_constraints (subst_pattern);
+
+	  RTVEC_ELT (subst_pattern_vec, j) = subst_pattern;
+	}
+      XVEC (elem->data, 1) = subst_pattern_vec;
+
+      for (i = 0; i < MAX_OPERANDS; i++)
+	  match_operand_entries_in_pattern[i] = NULL;
+
+      if (GET_CODE (elem->data) == DEFINE_INSN)
+	{
+	  XTMPL (elem->data, 3) =
+	    alter_output_for_subst_insn (elem->data, alternatives_subst);
+	  alter_attrs_for_subst_insn (elem, alternatives_subst);
+	}
+
+      /* Recalculate condition, joining conditions from original and
+	 DEFINE_SUBST input patterns.  */
+      XSTR (elem->data, 2) = join_c_conditions (XSTR (subst_elem->data, 2),
+						XSTR (elem->data, 2));
+      /* Mark that subst was applied by changing attribute from "yes"
+	 to "no".  */
+      change_subst_attribute (elem, subst_elem, subst_false);
+    }
+
+  /* If ELEM contains a subst attribute with value "yes", then we
+     expected that a subst would be applied, but it wasn't - so,
+     we need to remove that elementto avoid duplicating.  */
+  for (subst_elem = define_subst_queue;
+       subst_elem; subst_elem = subst_elem->next)
+    {
+      if (has_subst_attribute (elem, subst_elem))
+	{
+	  remove_from_queue (elem, &queue);
+	  return;
+	}
+    }
+}
+
+/* This is a subroutine of mark_operands_used_in_match_dup.
+   This routine is marks all MATCH_OPERANDs inside PATTERN as occupied.  */
+static void
+mark_operands_from_match_dup (rtx pattern)
+{
+  const char *fmt;
+  int i, j, len, opno;
+
+  if (GET_CODE (pattern) == MATCH_OPERAND)
+    {
+      opno = XINT (pattern, 0);
+      gcc_assert (opno >= 0 && opno < MAX_OPERANDS);
+      used_operands_numbers [opno] = 1;
+    }
+  fmt = GET_RTX_FORMAT (GET_CODE (pattern));
+  len = GET_RTX_LENGTH (GET_CODE (pattern));
+  for (i = 0; i < len; i++)
+    {
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  mark_operands_from_match_dup (XEXP (pattern, i));
+	  break;
+	case 'E':
+	  for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
+	    mark_operands_from_match_dup (XVECEXP (pattern, i, j));
+	  break;
+	}
+    }
+}
+
+/* This is a subroutine of adjust_operands_numbers.
+   It goes through all expressions in PATTERN and when MATCH_DUP is
+   met, all MATCH_OPERANDs inside it is marked as occupied.  The
+   process of marking is done by routin mark_operands_from_match_dup.  */
+static void
+mark_operands_used_in_match_dup (rtx pattern)
+{
+  const char *fmt;
+  int i, j, len, opno;
+
+  if (GET_CODE (pattern) == MATCH_DUP)
+    {
+      opno = XINT (pattern, 0);
+      gcc_assert (opno >= 0 && opno < MAX_OPERANDS);
+      mark_operands_from_match_dup (operand_data[opno]);
+      return;
+    }
+  fmt = GET_RTX_FORMAT (GET_CODE (pattern));
+  len = GET_RTX_LENGTH (GET_CODE (pattern));
+  for (i = 0; i < len; i++)
+    {
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  mark_operands_used_in_match_dup (XEXP (pattern, i));
+	  break;
+	case 'E':
+	  for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
+	    mark_operands_used_in_match_dup (XVECEXP (pattern, i, j));
+	  break;
+	}
+    }
+}
+
+/* This is subroutine of renumerate_operands_in_pattern.
+   It finds first not-occupied operand-index.  */
+static int
+find_first_unused_number_of_operand ()
+{
+  int i;
+  for (i = 0; i < MAX_OPERANDS; i++)
+    if (!used_operands_numbers[i])
+      return i;
+  return MAX_OPERANDS;
+}
+
+/* This is subroutine of adjust_operands_numbers.
+   It visits all expressions in PATTERN and assigns not-occupied
+   operand indexes to MATCH_OPERANDs and MATCH_OPERATORs of this
+   PATTERN.  */
+static void
+renumerate_operands_in_pattern (rtx pattern)
+{
+  const char *fmt;
+  enum rtx_code code;
+  int i, j, len, new_opno;
+  code = GET_CODE (pattern);
+
+  if (code == MATCH_OPERAND
+      || code == MATCH_OPERATOR)
+    {
+      new_opno = find_first_unused_number_of_operand ();
+      gcc_assert (new_opno >= 0 && new_opno < MAX_OPERANDS);
+      XINT (pattern, 0) = new_opno;
+      used_operands_numbers [new_opno] = 1;
+    }
+
+  fmt = GET_RTX_FORMAT (GET_CODE (pattern));
+  len = GET_RTX_LENGTH (GET_CODE (pattern));
+  for (i = 0; i < len; i++)
+    {
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  renumerate_operands_in_pattern (XEXP (pattern, i));
+	  break;
+	case 'E':
+	  for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
+	    renumerate_operands_in_pattern (XVECEXP (pattern, i, j));
+	  break;
+	}
+    }
+}
+
+/* If output pattern of define_subst contains MATCH_DUP, then this
+   expression would be replaced with the pattern, matched with
+   MATCH_OPERAND from input pattern.  This pattern could contain any
+   number of MATCH_OPERANDs, MATCH_OPERATORs etc., so it's possible
+   that a MATCH_OPERAND from output_pattern (if any) would have the
+   same number, as MATCH_OPERAND from copied pattern.  To avoid such
+   indexes overlapping, we assign new indexes to MATCH_OPERANDs,
+   laying in the output pattern outside of MATCH_DUPs.  */
+static rtx
+adjust_operands_numbers (rtx pattern)
+{
+  mark_operands_used_in_match_dup (pattern);
+
+  renumerate_operands_in_pattern (pattern);
+
+  return pattern;
+}
+
+/* Generate RTL expression
+   (match_dup OPNO)
+   */
+static rtx
+generate_match_dup (int opno)
+{
+  rtx return_rtx = rtx_alloc (MATCH_DUP);
+  PUT_CODE (return_rtx, MATCH_DUP);
+  XINT (return_rtx, 0) = opno;
+  return return_rtx;
+}
+
+/* This routine checks all match_operands in PATTERN and if some of
+   have the same index, it replaces all of them except the first one  to
+   match_dup.
+   Usually, match_operands with the same indexes are forbidden, but
+   after define_subst copy an RTL-expression from original template,
+   indexes of existed and just-copied match_operands could coincide.
+   To fix it, we replace one of them with match_dup.  */
+static rtx
+replace_duplicating_operands_in_pattern (rtx pattern)
+{
+  const char *fmt;
+  int i, j, len, opno;
+  rtx mdup;
+
+  if (GET_CODE (pattern) == MATCH_OPERAND)
+    {
+      opno = XINT (pattern, 0);
+      gcc_assert (opno >= 0 && opno < MAX_OPERANDS);
+      if (match_operand_entries_in_pattern[opno] == NULL)
+	{
+	  match_operand_entries_in_pattern[opno] = pattern;
+	  return NULL;
+	}
+      else
+	{
+	  /* Compare predicates before replacing with match_dup.  */
+	  if (strcmp (XSTR (pattern, 1),
+		      XSTR (match_operand_entries_in_pattern[opno], 1)))
+	    {
+	      error ("duplicated match_operands with different predicates were"
+		     " found.");
+	      return NULL;
+	    }
+	  return generate_match_dup (opno);
+	}
+    }
+  fmt = GET_RTX_FORMAT (GET_CODE (pattern));
+  len = GET_RTX_LENGTH (GET_CODE (pattern));
+  for (i = 0; i < len; i++)
+    {
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  mdup = replace_duplicating_operands_in_pattern (XEXP (pattern, i));
+	  if (mdup)
+	    XEXP (pattern, i) = mdup;
+	  break;
+	case 'E':
+	  for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
+	    {
+	      mdup =
+		replace_duplicating_operands_in_pattern (XVECEXP
+							 (pattern, i, j));
+	      if (mdup)
+		XVECEXP (pattern, i, j) = mdup;
+	    }
+	  break;
+	}
+    }
+  return NULL;
+}
+
+/* The routine modifies given input PATTERN of define_subst, replacing
+   MATCH_DUP and MATCH_OP_DUP with operands from define_insn original
+   pattern, whose operands are stored in OPERAND_DATA array.
+   It also duplicates constraints in operands - constraints from
+   define_insn operands are duplicated N_SUBST_ALT times, constraints
+   from define_subst operands are duplicated N_ALT times.
+   After the duplication, returned output rtl-pattern contains every
+   combination of input constraints Vs constraints from define_subst
+   output.  */
+static rtx
+subst_dup (rtx pattern, int n_alt, int n_subst_alt)
+{
+  const char *fmt;
+  enum rtx_code code;
+  int i, j, len, opno;
+
+  code = GET_CODE (pattern);
+  switch (code)
+    {
+    case MATCH_DUP:
+    case MATCH_OP_DUP:
+      opno = XINT (pattern, 0);
+
+      gcc_assert (opno >= 0 && opno < MAX_OPERANDS);
+
+      if (operand_data[opno])
+	{
+	  pattern = copy_rtx (operand_data[opno]);
+
+	  /* Duplicate constraints.  */
+	  pattern = alter_constraints (pattern, n_subst_alt,
+				       duplicate_alternatives);
+	}
+      break;
+
+    default:
+      break;
+    }
+
+  fmt = GET_RTX_FORMAT (GET_CODE (pattern));
+  len = GET_RTX_LENGTH (GET_CODE (pattern));
+  for (i = 0; i < len; i++)
+    {
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  if (code != MATCH_DUP && code != MATCH_OP_DUP)
+	    XEXP (pattern, i) = subst_dup (XEXP (pattern, i),
+					   n_alt, n_subst_alt);
+	  break;
+	case 'V':
+	  if (XVEC (pattern, i) == NULL)
+	    break;
+	case 'E':
+	  for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
+	    if (code != MATCH_DUP && code != MATCH_OP_DUP)
+	      XVECEXP (pattern, i, j) = subst_dup (XVECEXP (pattern, i, j),
+						   n_alt, n_subst_alt);
+	  break;
+
+	case 'i': case 'w': case '0': case 's': case 'S': case 'T':
+	  break;
+
+	default:
+	  gcc_unreachable ();
+	}
+    }
+  return pattern;
+}
+
 /* If we have any DEFINE_COND_EXEC patterns, expand the DEFINE_INSN
    patterns appropriately.  */
 
@@ -1166,6 +2193,42 @@ process_define_cond_exec (void)
   for (elem = define_cond_exec_queue; elem ; elem = elem->next)
     process_one_cond_exec (elem);
 }
+
+/* If we have any DEFINE_SUBST patterns, expand DEFINE_INSN and
+   DEFINE_EXPAND patterns appropriately.  */
+
+static void
+process_define_subst (void)
+{
+  struct queue_elem *elem, *elem_attr;
+
+  /* Check if each define_subst has corresponding define_subst_attr.  */
+  for (elem = define_subst_queue; elem ; elem = elem->next)
+    {
+      for (elem_attr = define_subst_attr_queue;
+	   elem_attr;
+	   elem_attr = elem_attr->next)
+	if (strcmp (XSTR (elem->data, 0), XSTR (elem_attr->data, 1)) == 0)
+	    goto found;
+
+	error_with_line (elem->lineno,
+			 "%s: `define_subst' must have at least one "
+			 "corresponding `define_subst_attr'",
+			 XSTR (elem->data, 0));
+	return;
+      found:
+	continue;
+    }
+
+  for (elem = define_insn_queue; elem ; elem = elem->next)
+    process_substs_on_one_elem (elem, define_insn_queue);
+  for (elem = other_queue; elem ; elem = elem->next)
+  {
+    if (GET_CODE (elem->data) != DEFINE_EXPAND)
+      continue;
+    process_substs_on_one_elem (elem, other_queue);
+  }
+}
 \f
 /* A read_md_files callback for reading an rtx.  */
 
@@ -1391,6 +2454,38 @@ gen_mnemonic_attr (void)
   XSTR (mnemonic_attr, 1) = XOBFINISH (&string_obstack, char *);
 }
 
+/* Check if there are DEFINE_ATTRs with the same name.  */
+static void
+check_define_attr_duplicates ()
+{
+  struct queue_elem *elem;
+  htab_t attr_htab;
+  char * attr_name;
+  void **slot;
+
+  attr_htab = htab_create (500, htab_hash_string, htab_eq_string, NULL);
+
+  for (elem = define_attr_queue; elem; elem = elem->next)
+    {
+      attr_name = xstrdup (XSTR (elem->data, 0));
+
+      slot = htab_find_slot (attr_htab, attr_name, INSERT);
+
+      /* Duplicate.  */
+      if (*slot)
+	{
+	  error_with_line (elem->lineno, "redefinition of attribute '%s'",
+			   attr_name);
+	  htab_delete (attr_htab);
+	  return;
+	}
+
+      *slot = attr_name;
+    }
+
+  htab_delete (attr_htab);
+}
+
 /* The entry point for initializing the reader.  */
 
 bool
@@ -1407,10 +2502,17 @@ init_rtx_reader_args_cb (int argc, char **argv,
 
   read_md_files (argc, argv, parse_opt, rtx_handle_directive);
 
+  if (define_attr_queue != NULL)
+    check_define_attr_duplicates ();
+
   /* Process define_cond_exec patterns.  */
   if (define_cond_exec_queue != NULL)
     process_define_cond_exec ();
 
+  /* Process define_subst patterns.  */
+  if (define_subst_queue != NULL)
+    process_define_subst ();
+
   if (define_attr_queue != NULL)
     gen_mnemonic_attr ();
 
@@ -1470,6 +2572,7 @@ read_md_rtx (int *lineno, int *seqnr)
     {
     case DEFINE_INSN:
     case DEFINE_EXPAND:
+    case DEFINE_SUBST:
       if (maybe_eval_c_test (XSTR (desc, 2)) != 0)
 	sequence_num++;
       else if (insn_elision)
diff --git a/gcc/read-rtl.c b/gcc/read-rtl.c
index 30c2fb6..219d718 100644
--- a/gcc/read-rtl.c
+++ b/gcc/read-rtl.c
@@ -108,13 +108,28 @@ typedef struct attribute_use attribute_use;
 DEF_VEC_O (attribute_use);
 DEF_VEC_ALLOC_O (attribute_use, heap);
 
+/* This struct is used to link subst_attr named ATTR_NAME with
+   corresponding define_subst named ITER_NAME.  */
+struct subst_attr_to_iter_mapping
+{
+    char *attr_name;
+    char *iter_name;
+};
+
+/* Hash-table to store links between subst-attributes and
+   define_substs.  */
+htab_t subst_attr_to_iter_map = NULL;
+/* This global stores name of subst-iterator which is currently being
+   processed.  */
+const char *current_iterator_name;
+
 static void validate_const_int (const char *);
 static rtx read_rtx_code (const char *);
 static rtx read_nested_rtx (void);
 static rtx read_rtx_variadic (rtx);
 
 /* The mode and code iterator structures.  */
-static struct iterator_group modes, codes, ints;
+static struct iterator_group modes, codes, ints, substs;
 
 /* All iterators used in the current rtx.  */
 static VEC (mapping_ptr, heap) *current_iterators;
@@ -184,6 +199,91 @@ apply_int_iterator (void *loc, int value)
   *(int *)loc = value;
 }
 
+/* This routine adds attribute or does nothing depending on VALUE.  When
+   VALUE is 1, it does nothing - the first duplicate of original
+   template is kept untouched when it's subjected to a define_subst.
+   When VALUE isn't 1, the routine modifies RTL-template LOC, adding
+   attribute, named exactly as define_subst, which later will be
+   applied.  If such attribute has already been added, then no the
+   routine has no effect.  */
+static void
+apply_subst_iterator (void *loc, int value)
+{
+  rtx rt = (rtx)loc;
+  rtx new_attr;
+  rtvec attrs_vec, new_attrs_vec;
+  int i;
+  if (value == 1)
+    return;
+  gcc_assert (GET_CODE (rt) == DEFINE_INSN
+	      || GET_CODE (rt) == DEFINE_EXPAND);
+
+  attrs_vec = XVEC (rt, 4);
+
+  /* If we've already added attribute 'current_iterator_name', then we
+     have nothing to do now.  */
+  if (attrs_vec)
+    {
+      for (i = 0; i < GET_NUM_ELEM (attrs_vec); i++)
+	{
+	  if (strcmp (XSTR (attrs_vec->elem[i], 0), current_iterator_name) == 0)
+	    return;
+	}
+    }
+
+  /* Add attribute with subst name - it serves as a mark for
+     define_subst which later would be applied to this pattern.  */
+  new_attr = rtx_alloc (SET_ATTR);
+  PUT_CODE (new_attr, SET_ATTR);
+  XSTR (new_attr, 0) = xstrdup (current_iterator_name);
+  XSTR (new_attr, 1) = xstrdup ("yes");
+
+  if (!attrs_vec)
+    {
+      new_attrs_vec = rtvec_alloc (1);
+      new_attrs_vec->elem[0] = new_attr;
+    }
+  else
+    {
+      new_attrs_vec = rtvec_alloc (GET_NUM_ELEM (attrs_vec) + 1);
+      memcpy (&new_attrs_vec->elem[0], &attrs_vec->elem[0],
+	      GET_NUM_ELEM (attrs_vec) * sizeof (rtx));
+      new_attrs_vec->elem[GET_NUM_ELEM (attrs_vec)] = new_attr;
+    }
+  XVEC (rt, 4) = new_attrs_vec;
+}
+
+/* Map subst-attribute ATTR to subst iterator ITER.  */
+
+static void
+bind_subst_iter_and_attr (const char *iter, const char *attr)
+{
+  struct subst_attr_to_iter_mapping *value;
+  void **slot;
+  if (!subst_attr_to_iter_map)
+    subst_attr_to_iter_map =
+      htab_create (1, leading_string_hash, leading_string_eq_p, 0);
+  value = XNEW (struct subst_attr_to_iter_mapping);
+  value->attr_name = xstrdup (attr);
+  value->iter_name = xstrdup (iter);
+  slot = htab_find_slot (subst_attr_to_iter_map, value, INSERT);
+  *slot = value;
+}
+
+/* Return name of a subst-iterator, corresponding to subst-attribute ATTR.  */
+
+static char*
+find_subst_iter_by_attr (const char *attr)
+{
+  char *iter_name = NULL;
+  struct subst_attr_to_iter_mapping *value;
+  value = (struct subst_attr_to_iter_mapping*)
+    htab_find (subst_attr_to_iter_map, &attr);
+  if (value)
+    iter_name = value->iter_name;
+  return iter_name;
+}
+
 /* Map attribute string P to its current value.  Return null if the attribute
    isn't known.  */
 
@@ -222,11 +322,23 @@ map_attr_string (const char *p)
       /* Find the attribute specification.  */
       m = (struct mapping *) htab_find (iterator->group->attrs, &attr);
       if (m)
-	/* Find the attribute value associated with the current
-	   iterator value.  */
-	for (v = m->values; v; v = v->next)
-	  if (v->number == iterator->current_value->number)
-	    return v;
+	{
+	  /* In contrast to code/mode/int iterators, attributes of subst
+	     iterators are linked to one specific subst-iterator.  So, if
+	     we are dealing with subst-iterator, we should check if it's
+	     the one which linked with the given attribute.  */
+	  if (iterator->group == &substs)
+	    {
+	      char *iter_name = find_subst_iter_by_attr (attr);
+	      if (strcmp (iter_name, iterator->name) != 0)
+		continue;
+	    }
+	  /* Find the attribute value associated with the current
+	     iterator value.  */
+	  for (v = m->values; v; v = v->next)
+	    if (v->number == iterator->current_value->number)
+	      return v;
+	}
     }
   return NULL;
 }
@@ -343,6 +455,7 @@ add_condition_to_rtx (rtx x, const char *extra)
     {
     case DEFINE_INSN:
     case DEFINE_EXPAND:
+    case DEFINE_SUBST:
       XSTR (x, 2) = add_condition_to_string (XSTR (x, 2), extra);
       break;
 
@@ -432,6 +545,7 @@ apply_iterators (rtx original, rtx *queue)
   htab_traverse (modes.iterators, add_current_iterators, NULL);
   htab_traverse (codes.iterators, add_current_iterators, NULL);
   htab_traverse (ints.iterators, add_current_iterators, NULL);
+  htab_traverse (substs.iterators, add_current_iterators, NULL);
   gcc_assert (!VEC_empty (mapping_ptr, current_iterators));
 
   for (;;)
@@ -441,6 +555,8 @@ apply_iterators (rtx original, rtx *queue)
       condition = NULL;
       FOR_EACH_VEC_ELT (iterator_use, iterator_uses, i, iuse)
 	{
+	  if (iuse->iterator->group == &substs)
+	    continue;
 	  v = iuse->iterator->current_value;
 	  iuse->iterator->group->apply_iterator (iuse->ptr, v->number);
 	  condition = join_c_conditions (condition, v->string);
@@ -449,6 +565,19 @@ apply_iterators (rtx original, rtx *queue)
       x = copy_rtx_for_iterators (original);
       add_condition_to_rtx (x, condition);
 
+      /* We apply subst iterator after RTL-template is copied, as during
+	 subst-iterator processing, we could add an attribute to the
+	 RTL-template, and we don't want to do it in the original one.  */
+      FOR_EACH_VEC_ELT (iterator_use, iterator_uses, i, iuse)
+	{
+	  v = iuse->iterator->current_value;
+	  if (iuse->iterator->group == &substs)
+	    {
+	      iuse->ptr = x;
+	      current_iterator_name = iuse->iterator->name;
+	      iuse->iterator->group->apply_iterator (iuse->ptr, v->number);
+	    }
+	}
       /* Add the new rtx to the end of the queue.  */
       XEXP (*queue, 0) = x;
       XEXP (*queue, 1) = NULL_RTX;
@@ -544,6 +673,12 @@ initialize_iterators (void)
   ints.find_builtin = find_int;
   ints.apply_iterator = apply_int_iterator;
 
+  substs.attrs = htab_create (13, leading_string_hash, leading_string_eq_p, 0);
+  substs.iterators = htab_create (13, leading_string_hash,
+				 leading_string_eq_p, 0);
+  substs.find_builtin = find_int; /* We don't use it, anyway.  */
+  substs.apply_iterator = apply_subst_iterator;
+
   lower = add_mapping (&modes, modes.attrs, "mode");
   upper = add_mapping (&modes, modes.attrs, "MODE");
   lower_ptr = &lower->values;
@@ -786,6 +921,94 @@ read_mapping (struct iterator_group *group, htab_t table)
   return m;
 }
 
+/* For iterator with name ATTR_NAME generate define_attr with values
+   'yes' and 'no'.  This attribute is used to mark templates to which
+   define_subst ATTR_NAME should be applied.  This attribute is set and
+   defined implicitly and automatically.  */
+static void
+add_define_attr_for_define_subst (const char *attr_name, rtx *queue)
+{
+  rtx const_str, return_rtx;
+
+  return_rtx = rtx_alloc (DEFINE_ATTR);
+  PUT_CODE (return_rtx, DEFINE_ATTR);
+
+  const_str = rtx_alloc (CONST_STRING);
+  PUT_CODE (const_str, CONST_STRING);
+  XSTR (const_str, 0) = xstrdup ("no");
+
+  XSTR (return_rtx, 0) = xstrdup (attr_name);
+  XSTR (return_rtx, 1) = xstrdup ("no,yes");
+  XEXP (return_rtx, 2) = const_str;
+
+  XEXP (*queue, 0) = return_rtx;
+  XEXP (*queue, 1) = NULL_RTX;
+}
+
+/* This routine generates DEFINE_SUBST_ATTR expression with operands
+   ATTR_OPERANDS and places it to QUEUE.  */
+static void
+add_define_subst_attr (const char **attr_operands, rtx *queue)
+{
+  rtx return_rtx;
+  int i;
+
+  return_rtx = rtx_alloc (DEFINE_SUBST_ATTR);
+  PUT_CODE (return_rtx, DEFINE_SUBST_ATTR);
+
+  for (i = 0; i < 4; i++)
+    XSTR (return_rtx, i) = xstrdup (attr_operands[i]);
+
+  XEXP (*queue, 0) = return_rtx;
+  XEXP (*queue, 1) = NULL_RTX;
+}
+
+/* Read define_subst_attribute construction.  It has next form:
+	(define_subst_attribute <attribute_name> <iterator_name> <value1> <value2>)
+   Attribute is substituted with value1 when no subst is applied and with
+   value2 in the opposite case.
+   Attributes are added to SUBST_ATTRS_TABLE.
+   In case the iterator is encountered for the first time, it's added to
+   SUBST_ITERS_TABLE.  Also, implicit define_attr is generated.  */
+
+static void
+read_subst_mapping (htab_t subst_iters_table, htab_t subst_attrs_table,
+		    rtx *queue)
+{
+  struct mapping *m;
+  struct map_value **end_ptr;
+  const char *attr_operands[4];
+  rtx * queue_elem = queue;
+  int i;
+
+  for (i = 0; i < 4; i++)
+    attr_operands[i] = read_string (false);
+
+  add_define_subst_attr (attr_operands, queue_elem);
+
+  bind_subst_iter_and_attr (attr_operands[1], attr_operands[0]);
+
+  m = (struct mapping *) htab_find (substs.iterators, &attr_operands[1]);
+  if (!m)
+    {
+      m = add_mapping (&substs, subst_iters_table, attr_operands[1]);
+      end_ptr = &m->values;
+      end_ptr = add_map_value (end_ptr, 1, "");
+      end_ptr = add_map_value (end_ptr, 2, "");
+
+      /* Add element to the queue.  */
+      XEXP (*queue, 1) = rtx_alloc (EXPR_LIST);
+      queue_elem = &XEXP (*queue, 1);
+
+      add_define_attr_for_define_subst (attr_operands[1], queue_elem);
+    }
+
+  m = add_mapping (&substs, subst_attrs_table, attr_operands[0]);
+  end_ptr = &m->values;
+  end_ptr = add_map_value (end_ptr, 1, attr_operands[2]);
+  end_ptr = add_map_value (end_ptr, 2, attr_operands[3]);
+}
+
 /* Check newly-created code iterator ITERATOR to see whether every code has the
    same format.  */
 
@@ -856,6 +1079,19 @@ read_rtx (const char *rtx_name, rtx *x)
       read_mapping (&ints, ints.iterators);
       return false;
     }
+  if (strcmp (rtx_name, "define_subst_attr") == 0)
+    {
+      /* We are parsing DEFINE_SUBST_ATTR, which could cause generation
+	 of DEFINE_ATTR for introduced DEFINE_SUBST.  It doesn't happen
+	 if such DEFINE_ATTR has already been introduced.
+	 If this did happen, we need to return TRUE to process newly
+	 introduced DEFINE_ATTR.  */
+
+      read_subst_mapping (substs.iterators, substs.attrs, &queue_head);
+
+      *x = queue_head;
+      return true;
+    }
 
   apply_iterators (read_rtx_code (rtx_name), &queue_head);
   VEC_truncate (iterator_use, iterator_uses, 0);
@@ -874,12 +1110,15 @@ read_rtx_code (const char *code_name)
 {
   int i;
   RTX_CODE code;
-  struct mapping *iterator;
+  struct mapping *iterator, *m;
   const char *format_ptr;
   struct md_name name;
   rtx return_rtx;
   int c;
   HOST_WIDE_INT tmp_wide;
+  char *str;
+  char *start, *end, *ptr;
+  char tmpstr[256];
 
   /* Linked list structure for making RTXs: */
   struct rtx_list
@@ -1024,6 +1263,35 @@ read_rtx_code (const char *code_name)
 	      stringbuf = XOBFINISH (&string_obstack, char *);
 	    }
 
+	  /* Find attr-names in the string.  */
+	  ptr = &tmpstr[0];
+	  end = stringbuf;
+	  while ((start = strchr (end, '<')) && (end  = strchr (end, '>')))
+	    {
+	      if (start && end
+		  && (end - start - 1 > 0)
+		  && (end - start - 1 < (int)sizeof (tmpstr)))
+		{
+		  strncpy (tmpstr, start+1, end-start-1);
+		  tmpstr[end-start-1] = 0;
+		  end++;
+		}
+	      else
+		break;
+	      m = (struct mapping *) htab_find (substs.attrs, &ptr);
+	      if (m != 0)
+		{
+		  /* Here we should find linked subst-iter.  */
+		  str = find_subst_iter_by_attr (ptr);
+		  if (str)
+		    m = (struct mapping *) htab_find (substs.iterators, &str);
+		  else
+		    m = 0;
+		}
+	      if (m != 0)
+		record_iterator_use (m, return_rtx);
+	    }
+
 	  if (star_if_braced)
 	    XTMPL (return_rtx, i) = stringbuf;
 	  else
diff --git a/gcc/rtl.def b/gcc/rtl.def
index 32098af..6948bfe 100644
--- a/gcc/rtl.def
+++ b/gcc/rtl.def
@@ -906,8 +906,9 @@ DEF_RTL_EXPR(DEFINE_PEEPHOLE2, "define_peephole2", "EsES", RTX_EXTRA)
 	This might, for example, create some RTX's and store them in
 	elements of `recog_data.operand' for use by the vector of
 	insn-patterns.
-	(`operands' is an alias here for `recog_data.operand').  */
-DEF_RTL_EXPR(DEFINE_EXPAND, "define_expand", "sEss", RTX_EXTRA)
+	(`operands' is an alias here for `recog_data.operand').
+   5th: optionally, a vector of attributes for this expand.  */
+DEF_RTL_EXPR(DEFINE_EXPAND, "define_expand", "sEssV", RTX_EXTRA)
 
 /* Define a requirement for delay slots.
    1st operand: Condition involving insn attributes that, if true,
@@ -1280,6 +1281,8 @@ DEF_RTL_EXPR (ATTR_FLAG, "attr_flag", "s", RTX_EXTRA)
    true, the second operand will be used as the value of the conditional.  */
 DEF_RTL_EXPR(COND, "cond", "Ee", RTX_EXTRA)
 
+DEF_RTL_EXPR(DEFINE_SUBST, "define_subst", "sEsE", RTX_EXTRA)
+DEF_RTL_EXPR(DEFINE_SUBST_ATTR, "define_subst_attr", "ssss", RTX_EXTRA)
 #endif /* GENERATOR_FILE */
 
 /*

Re: [PATCH, generic] New RTL primitive: `define_subst'

[Hans-Peter Nilsson]

On Sun, 4 Nov 2012, Kirill Yukhin wrote:
> Hi,
>
> >> But... I don't really understand it, so here's some feedback on
> >> the documentation: Regarding the language, a definite article is
>
> Patch with fixed doc is attached. Changelog is the same
>
> Is it OK?

The structure is much improved and quite satisfactory, thank
you!  I can actually understand it, even through a mild fever. :)

This feature looks quite nice: the example covers exactly where
I hope to use it: explicit condition-code settings i.e. to move
a target from the deprecated cc0 machinery without source
pattern explosion.  (Patterns generally need to be expressed in
three forms: clobbering cc0, setting cc0, and special cases for
insns with variants that don't touch cc0, so two "subst"s.)

Come to think of it, maybe "subst iterator" is somewhat a
misnomer; perhaps better use just "subst" in place of "subst
iterator" in the documentation.  Language issues with definite
article remain, but I'll leave further nitpicking until
maintainers with actual approval powers have reviewed the
feature and its implementation, from a higher level.

brgds, H-P

Re: [PATCH, generic] New RTL primitive: `define_subst'

[Kirill Yukhin]

Hello guys!
This is a PING. Could you pls have a look?

Thanks, K

>
> Is it OK?
>
> Thanks, K

Re: [PATCH, generic] New RTL primitive: `define_subst'

[Richard Henderson]

> +  for (elem = other_queue; elem ; elem = elem->next)
> +  {

Note that your indentation is off in places.

> +      /* We are parsing DEFINE_SUBST_ATTR, which could cause generation
> +	 of DEFINE_ATTR for introduced DEFINE_SUBST.  It doesn't happen
> +	 if such DEFINE_ATTR has already been introduced.
> +	 If this did happen, we need to return TRUE to process newly
> +	 introduced DEFINE_ATTR.  */

This comment is less than clear.  Unclear enough that I don't even
know how to suggest re-wording it.  We're returning true so that the
new define_subst_attr is processed, or that some define_subst is processed?

> +	  while ((start = strchr (end, '<')) && (end  = strchr (end, '>')))
> +	    {
> +	      if (start && end
> +		  && (end - start - 1 > 0)
> +		  && (end - start - 1 < (int)sizeof (tmpstr)))

That doesn't look right.
(1) end search should be from start, not from the previous end.
(2) you know start and end are non-null inside the loop; why are
    you checking for it again.

The bulk of the patch is looking pretty decent now.  We may find problems
with it when we start to use it, but at the moment it's fairly hard to
evaluate completely.

---

Looking at all this, I'm wondering if we shouldn't split out all of this
macro/include processing to a separate pass.  Perform the preprocessing
once, early, leaving the processed result in the build directory.  Then
run the original/traditional rtl reader on that when running the other
rtl manipulation passes.

The reason being that it's going to become increasingly hard to figure
out if the reason for an error is in the macro processing or in the source
md file.  Being able to see the macro expansion is going to be important.

Of course, another way to get this macro expansion is to leave the macro
processing where it is and have another gen program that merely dumps the
processed rtl.  It wouldn't be run normally, but a makefile target used
for debugging would be sufficient.

---

Which brings us to the question of what to do with the patch for 4.8.
It's true that you made the deadline for stage1 closure.  But there will
be no users of this feature, so it begs the question of why we should
apply it now.  Have you a convincing reason?

RM's do you have an opinion here?


r~

Re: [PATCH, generic] New RTL primitive: `define_subst'

[Mike Stump]

On Nov 13, 2012, at 1:03 PM, Richard Henderson <rth@redhat.com> wrote:
> Looking at all this, I'm wondering if we shouldn't split out all of this
> macro/include processing to a separate pass.  Perform the preprocessing
> once, early, leaving the processed result in the build directory.  Then
> run the original/traditional rtl reader on that when running the other
> rtl manipulation passes.

Kenny and I have a built-in generator that works by generating .md files in the build tree and using those as source.  My experience is that occasionally it handy to have those .md files, and it offers a way to better understand what is going on.  That said, I have only a slight preference for this.  I don't think it is the end of the world if this isn't done.  Occasionally, I want the existing iterator stuff to have an preprocess output mode…  though, only very occasionally.  So, I think that puts me in the nice to have but I don't think I would mandate it camp.

I do have some fear of customized macro languages that are really poor because they aren't generic enough and can never be, by design.  I can't help but wonder if there is a nice design that can be easily extended, if something is needed, yet, isn't as gross as all the generic solutions I've seen.  Sigh.

Re: [PATCH, generic] New RTL primitive: `define_subst'

[Jakub Jelinek]

On Tue, Nov 13, 2012 at 01:03:14PM -0800, Richard Henderson wrote:
> Note that your indentation is off in places.
> 
> > +	  while ((start = strchr (end, '<')) && (end  = strchr (end, '>')))

Above too when you mention it.

> Looking at all this, I'm wondering if we shouldn't split out all of this
> macro/include processing to a separate pass.  Perform the preprocessing
> once, early, leaving the processed result in the build directory.  Then
> run the original/traditional rtl reader on that when running the other
> rtl manipulation passes.
> 
> The reason being that it's going to become increasingly hard to figure
> out if the reason for an error is in the macro processing or in the source
> md file.  Being able to see the macro expansion is going to be important.
> 
> Of course, another way to get this macro expansion is to leave the macro
> processing where it is and have another gen program that merely dumps the
> processed rtl.  It wouldn't be run normally, but a makefile target used
> for debugging would be sufficient.

Yeah, one or other way to being able to debug what exactly has been
performed during the iterator expansion is certainly desirable for the
future.

> Which brings us to the question of what to do with the patch for 4.8.
> It's true that you made the deadline for stage1 closure.  But there will
> be no users of this feature, so it begs the question of why we should
> apply it now.  Have you a convincing reason?
> 
> RM's do you have an opinion here?

I'm not against it going in now, it shouldn't be too risky and will
allow people to start experimenting with it sooner.

It is not the end of the world if it doesn't get applied now on the other
side, the gen*.c changes aren't that big and invasive and what would be much
harder to maintain longer term are the actual *.md file changes, which
aren't being submitted for 4.8.

	Jakub

Re: [PATCH, generic] New RTL primitive: `define_subst'

[Kirill Yukhin]

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

Hi guys,
thanks for review. Comments along with updated patch are below.

>> > +     while ((start = strchr (end, '<')) && (end  = strchr (end, '>')))
> Above too when you mention it.
Fixed.

>> Looking at all this, I'm wondering if we shouldn't split out all of this
>> macro/include processing to a separate pass.  Perform the preprocessing
>> once, early, leaving the processed result in the build directory.  Then
>> run the original/traditional rtl reader on that when running the other
>> rtl manipulation passes.
>>
>> The reason being that it's going to become increasingly hard to figure
>> out if the reason for an error is in the macro processing or in the source
>> md file.  Being able to see the macro expansion is going to be important.
>>
>> Of course, another way to get this macro expansion is to leave the macro
>> processing where it is and have another gen program that merely dumps the
>> processed rtl.  It wouldn't be run normally, but a makefile target used
>> for debugging would be sufficient.
>
> Yeah, one or other way to being able to debug what exactly has been
> performed during the iterator expansion is certainly desirable for the
> future.
We actually have internal machinery for dumping MDs with expanded
iterators and substs, but this looks really kinda hack now.
We're going to submit it as subsequent patch after that one
is checked in (there'll be no change in `define_subst' interface) and some
discussion about necessary infrastructure changes is performed.

>> RM's do you have an opinion here?
>
> I'm not against it going in now, it shouldn't be too risky and will
> allow people to start experimenting with it sooner.
>
> It is not the end of the world if it doesn't get applied now on the other
> side, the gen*.c changes aren't that big and invasive and what would be much
> harder to maintain longer term are the actual *.md file changes, which
> aren't being submitted for 4.8.
The main reason we want it as early as possible is to prepare a solid
and validated by community ground for the further possible extensions
which can be added to the i386.md fairly easy by using this machinery.
Though you are right that it can be introduced at the usage point, we
think that define_subst itself is adding functionality that can be
used by other interested developers (e.g., it is possible to squash
i386.md by few hundred lines using `define_subst'). So early adoption
will be beneficial: the more people will look into it, use it, the
more robust and clean it will become.

Other questions/comments?

Thanks, K

[-- Attachment #2: define_subst-6.patch --]
[-- Type: application/octet-stream, Size: 61709 bytes --]

diff --git a/gcc/doc/md.texi b/gcc/doc/md.texi
index eb6ba91..8ee9d16 100644
--- a/gcc/doc/md.texi
+++ b/gcc/doc/md.texi
@@ -46,6 +46,8 @@ See the next chapter for information on the C header file.
 * Insn Attributes::     Specifying the value of attributes for generated insns.
 * Conditional Execution::Generating @code{define_insn} patterns for
                          predication.
+* Define Subst::	Generating @code{define_insn} and @code{define_expand}
+			patterns from other patterns.
 * Constant Definitions::Defining symbolic constants that can be used in the
                         md file.
 * Iterators::           Using iterators to generate patterns from a template.
@@ -6688,6 +6690,10 @@ Usually these statements prepare temporary registers for use as
 internal operands in the RTL template, but they can also generate RTL
 insns directly by calling routines such as @code{emit_insn}, etc.
 Any such insns precede the ones that come from the RTL template.
+
+@item
+Optionally, a vector containing the values of attributes. @xref{Insn
+Attributes}.
 @end itemize
 
 Every RTL insn emitted by a @code{define_expand} must match some
@@ -8826,6 +8832,213 @@ generates a new pattern
 
 @end ifset
 @ifset INTERNALS
+@node Define Subst
+@section RTL Templates Transformations
+@cindex define_subst
+
+For some hardware architectures there are common cases when the RTL
+templates for the instructions can be derived from the other RTL
+templates using simple transformations.  E.g., @file{i386.md} contains
+an RTL template for the ordinary @code{sub} instruction---
+@code{*subsi_1}, and for the @code{sub} instruction with subsequent
+zero-extension---@code{*subsi_1_zext}.  Such cases can be easily
+implemented by a single meta-template capable of generating a modified
+case based on the initial one:
+
+@findex define_subst
+@smallexample
+(define_subst "@var{name}"
+  [@var{input-template}]
+  "@var{condition}"
+  [@var{output-template}])
+@end smallexample
+@var{input-template} is a pattern describing the source RTL template,
+which will be transformed.
+
+@var{condition} is a C expression that is conjunct with the condition
+from the input-template to generate a condition to be used in the
+output-template.
+
+@var{output-template} is a pattern that will be used in the resulting
+template.
+
+@code{define_subst} mechanism is tightly coupled with the notion of the
+subst attribute (@xref{Subst Iterators}).  The use of
+@code{define_subst} is triggered by a reference to a subst attribute in
+the transforming RTL template.  This reference initiates duplication of
+the source RTL template and substitution of the attributes with their
+values.  The source RTL template is left unchanged, while the copy is
+transformed by @code{define_subst}.  This transformation can fail in the
+case when the source RTL template is not matched against the
+input-template of the @code{define_subst}.  In such case the copy is
+deleted.
+
+@code{define_subst} can be used only in @code{define_insn} and
+@code{define_expand}, it cannot be used in other expressions (e.g. in
+@code{define_insn_and_split}).
+
+@menu
+* Define Subst Example::	    Example of @code{define_subst} work.
+* Define Subst Pattern Matching::   Process of template comparison.
+* Define Subst Output Template::    Generation of output template.
+@end menu
+
+@node Define Subst Example
+@subsection @code{define_subst} Example
+@cindex define_subst
+
+To illustrate how @code{define_subst} works, let us examine a simple
+template transformation.
+
+Suppose there are two kinds of instructions: one that touches flags and
+the other that does not.  The instructions of the second type could be
+generated with the following @code{define_subst}:
+
+@smallexample
+(define_subst "add_clobber_subst"
+  [(set (match_operand:SI 0 "" "")
+        (match_operand:SI 1 "" ""))]
+  ""
+  [(set (match_dup 0)
+        (match_dup 1))
+   (clobber (reg:CC FLAGS_REG))]
+@end smallexample
+
+This @code{define_subst} can be applied to any RTL pattern containing
+@code{set} of mode SI and generates a copy with clobber when it is
+applied.
+
+Assume there is an RTL template for a @code{max} instruction to be used
+in @code{define_subst} mentioned above:
+
+@smallexample
+(define_insn "maxsi"
+  [(set (match_operand:SI 0 "register_operand" "=r")
+        (max:SI
+          (match_operand:SI 1 "register_operand" "r")
+          (match_operand:SI 2 "register_operand" "r")))]
+  ""
+  "max\t@{%2, %1, %0|%0, %1, %2@}"
+ [@dots{}])
+@end smallexample
+
+To mark the RTL template for @code{define_subst} application,
+subst-attributes are used.  They should be declared in advance:
+
+@smallexample
+(define_subst_attr "add_clobber_name" "add_clobber_subst" "_noclobber" "_clobber")
+@end smallexample
+
+Here @samp{add_clobber_name} is the attribute name,
+@samp{add_clobber_subst} is the name of the corresponding
+@code{define_subst}, the third argument (@samp{_noclobber}) is the
+attribute value that would be substituted into the unchanged version of
+the source RTL template, and the last argument (@samp{_clobber}) is the
+value that would be substituted into the second, transformed,
+version of the RTL template.
+
+Once the subst-attribute has been defined, it should be used in RTL
+templates which need to be processed by the @code{define_subst}.  So,
+the original RTL template should be changed:
+
+@smallexample
+(define_insn "maxsi<add_clobber_name>"
+  [(set (match_operand:SI 0 "register_operand" "=r")
+        (max:SI
+          (match_operand:SI 1 "register_operand" "r")
+          (match_operand:SI 2 "register_operand" "r")))]
+  ""
+  "max\t@{%2, %1, %0|%0, %1, %2@}"
+ [@dots{}])
+@end smallexample
+
+The result of the @code{define_subst} usage would look like the following:
+
+@smallexample
+(define_insn "maxsi_noclobber"
+  [(set (match_operand:SI 0 "register_operand" "=r")
+        (max:SI
+          (match_operand:SI 1 "register_operand" "r")
+          (match_operand:SI 2 "register_operand" "r")))]
+  ""
+  "max\t@{%2, %1, %0|%0, %1, %2@}"
+ [@dots{}])
+(define_insn "maxsi_clobber"
+  [(set (match_operand:SI 0 "register_operand" "=r")
+        (max:SI
+          (match_operand:SI 1 "register_operand" "r")
+          (match_operand:SI 2 "register_operand" "r")))
+   (clobber (reg:CC FLAGS_REG))]
+  ""
+  "max\t@{%2, %1, %0|%0, %1, %2@}"
+ [@dots{}])
+@end smallexample
+
+@node Define Subst Pattern Matching
+@subsection Pattern Matching in @code{define_subst}
+@cindex define_subst
+
+All expressions, allowed in @code{define_insn} or @code{define_expand},
+are allowed in the input-template of @code{define_subst}, except
+@code{match_par_dup}, @code{match_scratch}, @code{match_parallel}. The
+meanings of expressions in the input-template were changed:
+
+@code{match_operand} matches any expression (possibly, a subtree in
+RTL-template), if modes of the @code{match_operand} and this expression
+are the same, or mode of the @code{match_operand} is @code{VOIDmode}, or
+this expression is @code{match_dup}, @code{match_op_dup}.  If the
+expression is @code{match_operand} too, and predicate of
+@code{match_operand} from the input pattern is not empty, then the
+predicates are compared.  That can be used for more accurate filtering
+of accepted RTL-templates.
+
+@code{match_operator} matches common operators (like @code{plus},
+@code{minus}), @code{unspec}, @code{unspec_volatile} operators and
+@code{match_operator}s from the original pattern if the modes match and
+@code{match_operator} from the input pattern has the same number of
+operands as the operator from the original pattern.
+
+@node Define Subst Output Template
+@subsection Generation of output template in @code{define_subst}
+@cindex define_subst
+
+If all necessary checks for @code{define_subst} application pass, a new
+RTL-pattern, based on the output-template, is created to replace the old
+template.  Like in input-patterns, meanings of some RTL expressions are
+changed when they are used in output-patterns of a @code{define_subst}.
+Thus, @code{match_dup} is used for copying the whole expression from the
+original pattern, which matched corresponding @code{match_operand} from
+the input pattern.
+
+@code{match_dup N} is used in the output template to be replaced with
+the expression from the original pattern, which matched
+@code{match_operand N} from the input pattern.  As a consequence,
+@code{match_dup} cannot be used to point to @code{match_operand}s from
+the output pattern, it should always refer to a @code{match_operand}
+from the input pattern.
+
+In the output template one can refer to the expressions from the
+original pattern and create new ones.  For instance, some operands could
+be added by means of standard @code{match_operand}.
+
+After replacing @code{match_dup} with some RTL-subtree from the original
+pattern, it could happen that several @code{match_operand}s in the
+output pattern have the same indexes.  It is unknown, how many and what
+indexes would be used in the expression which would replace
+@code{match_dup}, so such conflicts in indexes are inevitable.  To
+overcome this issue, @code{match_operands} and @code{match_operators},
+which were introduced into the output pattern, are renumerated when all
+@code{match_dup}s are replaced.
+
+Number of alternatives in @code{match_operand}s introduced into the
+output template @code{M} could differ from the number of alternatives in
+the original pattern @code{N}, so in the resultant pattern there would
+be @code{N*M} alternatives.  Thus, constraints from the original pattern
+would be duplicated @code{N} times, constraints from the output pattern
+would be duplicated @code{M} times, producing all possible combinations.
+@end ifset
+
+@ifset INTERNALS
 @node Constant Definitions
 @section Constant Definitions
 @cindex constant definitions
@@ -9009,6 +9222,7 @@ facilities to make this process easier.
 * Mode Iterators::         Generating variations of patterns for different modes.
 * Code Iterators::         Doing the same for codes.
 * Int Iterators::          Doing the same for integers.
+* Subst Iterators::	   Generating variations of patterns for define_subst.
 @end menu
 
 @node Mode Iterators
@@ -9357,4 +9571,51 @@ This is equivalent to:
 
 @end smallexample
 
+@node Subst Iterators
+@subsection Subst Iterators
+@cindex subst iterators in @file{.md} files
+@findex define_subst
+@findex define_subst_attr
+
+Subst iterators are special type of iterators with the following
+restrictions: they could not be declared explicitly, they always have
+only two values, and they do not have explicit dedicated name.
+Subst-iterators are triggered only when corresponding subst-attribute is
+used in RTL-pattern.
+
+Subst iterators transform templates in the following way: the templates
+are duplicated, the subst-attributes in these templates are replaced
+with the corresponding values, and a new attribute is implicitly added
+to the given @code{define_insn}/@code{define_expand}.  The name of the
+added attribute matches the name of @code{define_subst}.  Such
+attributes are declared implicitly, and it is not allowed to have a
+@code{define_attr} named as a @code{define_subst}.
+
+Each subst iterator is linked to a @code{define_subst}.  It is declared
+implicitly by the first appearance of the corresponding
+@code{define_subst_attr}, and it is not allowed to define it explicitly.
+
+Declarations of subst-attributes have the following syntax:
+
+@findex define_subst_attr
+@smallexample
+(define_subst_attr "@var{name}"
+  "@var{subst-name}"
+  "@var{no-subst-value}"
+  "@var{subst-applied-value}")
+@end smallexample
+
+@var{name} is a string with which the given subst-attribute could be
+referred to.
+
+@var{subst-name} shows which @code{define_subst} should be applied to an
+RTL-template if the given subst-attribute is present in the
+RTL-template.
+
+@var{no-subst-value} is a value with which subst-attribute would be
+replaced in the first copy of the original RTL-template.
+
+@var{subst-applied-value} is a value with which subst-attribute would be
+replaced in the second copy of the original RTL-template.
+
 @end ifset
diff --git a/gcc/gensupport.c b/gcc/gensupport.c
index 44443e2..8d29c7e 100644
--- a/gcc/gensupport.c
+++ b/gcc/gensupport.c
@@ -29,6 +29,12 @@
 #include "read-md.h"
 #include "gensupport.h"
 
+#define MAX_OPERANDS 40
+
+static rtx operand_data[MAX_OPERANDS];
+static rtx match_operand_entries_in_pattern[MAX_OPERANDS];
+static char used_operands_numbers[MAX_OPERANDS];
+
 
 /* In case some macros used by files we include need it, define this here.  */
 int target_flags;
@@ -48,10 +54,14 @@ static int predicable_default;
 static const char *predicable_true;
 static const char *predicable_false;
 
+static const char *subst_true = "yes";
+static const char *subst_false = "no";
+
 static htab_t condition_table;
 
-/* We initially queue all patterns, process the define_insn and
-   define_cond_exec patterns, then return them one at a time.  */
+/* We initially queue all patterns, process the define_insn,
+   define_cond_exec and define_subst patterns, then return
+   them one at a time.  */
 
 struct queue_elem
 {
@@ -75,8 +85,12 @@ static struct queue_elem *define_insn_queue;
 static struct queue_elem **define_insn_tail = &define_insn_queue;
 static struct queue_elem *define_cond_exec_queue;
 static struct queue_elem **define_cond_exec_tail = &define_cond_exec_queue;
+static struct queue_elem *define_subst_queue;
+static struct queue_elem **define_subst_tail = &define_subst_queue;
 static struct queue_elem *other_queue;
 static struct queue_elem **other_tail = &other_queue;
+static struct queue_elem *define_subst_attr_queue;
+static struct queue_elem **define_subst_attr_tail = &define_subst_attr_queue;
 
 static struct queue_elem *queue_pattern (rtx, struct queue_elem ***,
 					 const char *, int);
@@ -99,6 +113,24 @@ static void process_one_cond_exec (struct queue_elem *);
 static void process_define_cond_exec (void);
 static void init_predicate_table (void);
 static void record_insn_name (int, const char *);
+
+static bool has_subst_attribute (struct queue_elem *, struct queue_elem *);
+static bool subst_pattern_match (rtx, rtx, int);
+static int get_alternatives_number (rtx, int *, int);
+static const char * alter_output_for_subst_insn (rtx, int);
+static void alter_attrs_for_subst_insn (struct queue_elem *, int);
+static void process_substs_on_one_elem (struct queue_elem *,
+					struct queue_elem *);
+static rtx subst_dup (rtx, int, int);
+static void process_define_subst (void);
+
+static const char * duplicate_alternatives (const char *, int);
+static const char * duplicate_each_alternative (const char * str, int n_dup);
+
+typedef const char * (*constraints_handler_t) (const char *, int);
+static rtx alter_constraints (rtx, int, constraints_handler_t);
+static rtx adjust_operands_numbers (rtx);
+static rtx replace_duplicating_operands_in_pattern (rtx);
 \f
 /* Make a version of gen_rtx_CONST_INT so that GEN_INT can be used in
    the gensupport programs.  */
@@ -372,6 +404,27 @@ queue_pattern (rtx pattern, struct queue_elem ***list_tail,
   return e;
 }
 
+/* Remove element ELEM from QUEUE.  */
+static void
+remove_from_queue (struct queue_elem *elem, struct queue_elem **queue)
+{
+  struct queue_elem *prev, *e;
+  prev = NULL;
+  for (e = *queue; e ; e = e->next)
+    {
+      if (e == elem)
+	break;
+      prev = e;
+    }
+  if (e == NULL)
+    return;
+
+  if (prev)
+    prev->next = elem->next;
+  else
+    *queue = elem->next;
+}
+
 /* Build a define_attr for an binary attribute with name NAME and
    possible values "yes" and "no", and queue it.  */
 static void
@@ -439,6 +492,14 @@ process_rtx (rtx desc, int lineno)
       queue_pattern (desc, &define_cond_exec_tail, read_md_filename, lineno);
       break;
 
+    case DEFINE_SUBST:
+      queue_pattern (desc, &define_subst_tail, read_md_filename, lineno);
+      break;
+
+    case DEFINE_SUBST_ATTR:
+      queue_pattern (desc, &define_subst_attr_tail, read_md_filename, lineno);
+      break;
+
     case DEFINE_ATTR:
     case DEFINE_ENUM_ATTR:
       queue_pattern (desc, &define_attr_tail, read_md_filename, lineno);
@@ -584,6 +645,267 @@ is_predicable (struct queue_elem *elem)
   return 0;
 }
 
+/* Find attribute SUBST in ELEM and assign NEW_VALUE to it.  */
+static void
+change_subst_attribute (struct queue_elem *elem,
+			struct queue_elem *subst_elem,
+			const char *new_value)
+{
+  rtvec attrs_vec = XVEC (elem->data, 4);
+  const char *subst_name = XSTR (subst_elem->data, 0);
+  int i;
+
+  if (! attrs_vec)
+    return;
+
+  for (i = GET_NUM_ELEM (attrs_vec) - 1; i >= 0; --i)
+    {
+      rtx cur_attr = RTVEC_ELT (attrs_vec, i);
+      if (GET_CODE (cur_attr) != SET_ATTR)
+	continue;
+      if (strcmp (XSTR (cur_attr, 0), subst_name) == 0)
+	{
+	  XSTR (cur_attr, 1) = new_value;
+	  return;
+	}
+    }
+}
+
+/* Return true if ELEM has the attribute with the name of DEFINE_SUBST
+   represented by SUBST_ELEM and this attribute has value SUBST_TRUE.
+   DEFINE_SUBST isn't applied to patterns without such attribute.  In other
+   words, we suppose the default value of the attribute to be 'no' since it is
+   always generated automaticaly in read-rtl.c.  */
+static bool
+has_subst_attribute (struct queue_elem *elem, struct queue_elem *subst_elem)
+{
+  rtvec attrs_vec = XVEC (elem->data, 4);
+  const char *value, *subst_name = XSTR (subst_elem->data, 0);
+  int i;
+
+  if (! attrs_vec)
+    return false;
+
+  for (i = GET_NUM_ELEM (attrs_vec) - 1; i >= 0; --i)
+    {
+      rtx cur_attr = RTVEC_ELT (attrs_vec, i);
+      switch (GET_CODE (cur_attr))
+	{
+	case SET_ATTR:
+	  if (strcmp (XSTR (cur_attr, 0), subst_name) == 0)
+	    {
+	      value = XSTR (cur_attr, 1);
+	      goto found;
+	    }
+	  break;
+
+	case SET:
+	  if (GET_CODE (SET_DEST (cur_attr)) != ATTR
+	      || strcmp (XSTR (SET_DEST (cur_attr), 0), subst_name) != 0)
+	    break;
+	  cur_attr = SET_SRC (cur_attr);
+	  if (GET_CODE (cur_attr) == CONST_STRING)
+	    {
+	      value = XSTR (cur_attr, 0);
+	      goto found;
+	    }
+
+	  /* Only (set_attr "subst" "yes/no") and
+		  (set (attr "subst" (const_string "yes/no")))
+	     are currently allowed.  */
+	  error_with_line (elem->lineno,
+			   "unsupported value for `%s'", subst_name);
+	  return false;
+
+	case SET_ATTR_ALTERNATIVE:
+	  error_with_line (elem->lineno,
+			   "%s: `set_attr_alternative' is unsupported by "
+			   "`define_subst'",
+			   XSTR (elem->data, 0));
+	  return false;
+
+
+	default:
+	  gcc_unreachable ();
+	}
+    }
+
+  return false;
+
+ found:
+  if (strcmp (value, subst_true) == 0)
+    return true;
+  if (strcmp (value, subst_false) == 0)
+    return false;
+
+  error_with_line (elem->lineno,
+		   "unknown value `%s' for `%s' attribute", value, subst_name);
+  return false;
+}
+
+/* Compare RTL-template of original define_insn X to input RTL-template of
+   define_subst PT.  Return 1 if the templates match, 0 otherwise.
+   During the comparison, the routine also fills global_array OPERAND_DATA.  */
+static bool
+subst_pattern_match (rtx x, rtx pt, int lineno)
+{
+  RTX_CODE code, code_pt;
+  int i, j, len;
+  const char *fmt, *pred_name;
+
+  code = GET_CODE (x);
+  code_pt = GET_CODE (pt);
+
+  if (code_pt == MATCH_OPERAND)
+    {
+      /* MATCH_DUP, and MATCH_OP_DUP don't have a specified mode, so we
+	 always accept them.  */
+      if (GET_MODE (pt) != VOIDmode && GET_MODE (x) != GET_MODE (pt)
+	  && (code != MATCH_DUP && code != MATCH_OP_DUP))
+	return false; /* Modes don't match.  */
+
+      if (code == MATCH_OPERAND)
+	{
+	  pred_name = XSTR (pt, 1);
+	  if (pred_name[0] != 0)
+	    {
+	      const struct pred_data *pred_pt = lookup_predicate (pred_name);
+	      if (!pred_pt || pred_pt != lookup_predicate (XSTR (x, 1)))
+		return false; /* Predicates don't match.  */
+	    }
+	}
+
+      gcc_assert (XINT (pt, 0) >= 0 && XINT (pt, 0) < MAX_OPERANDS);
+      operand_data[XINT (pt, 0)] = x;
+      return true;
+    }
+
+  if (code_pt == MATCH_OPERATOR)
+    {
+      int x_vecexp_pos = -1;
+
+      /* Compare modes.  */
+      if (GET_MODE (pt) != VOIDmode && GET_MODE (x) != GET_MODE (pt))
+	return false;
+
+      /* In case X is also match_operator, compare predicates.  */
+      if (code == MATCH_OPERATOR)
+	{
+	  pred_name = XSTR (pt, 1);
+	  if (pred_name[0] != 0)
+	    {
+	      const struct pred_data *pred_pt = lookup_predicate (pred_name);
+	      if (!pred_pt || pred_pt != lookup_predicate (XSTR (x, 1)))
+		return false;
+	    }
+	}
+
+      /* Compare operands.
+	 MATCH_OPERATOR in input template could match in original template
+	 either 1) MATCH_OPERAND, 2) UNSPEC, 3) ordinary operation (like PLUS).
+	 In the first case operands are at (XVECEXP (x, 2, j)), in the second
+	 - at (XVECEXP (x, 0, j)), in the last one - (XEXP (x, j)).
+	 X_VECEXP_POS variable shows, where to look for these operands.  */
+      if (code == UNSPEC
+	  || code == UNSPEC_VOLATILE)
+	x_vecexp_pos = 0;
+      else if (code == MATCH_OPERATOR)
+	x_vecexp_pos = 2;
+      else
+	x_vecexp_pos = -1;
+
+      /* MATCH_OPERATOR or UNSPEC case.  */
+      if (x_vecexp_pos >= 0)
+	{
+	  /* Compare operands number in X and PT.  */
+	  if (XVECLEN (x, x_vecexp_pos) != XVECLEN (pt, 2))
+	    return false;
+	  for (j = 0; j < XVECLEN (pt, 2); j++)
+	    if (!subst_pattern_match (XVECEXP (x, x_vecexp_pos, j),
+				      XVECEXP (pt, 2, j), lineno))
+	      return false;
+	}
+
+      /* Ordinary operator.  */
+      else
+	{
+	  /* Compare operands number in X and PT.
+	     We count operands differently for X and PT since we compare
+	     an operator (with operands directly in RTX) and MATCH_OPERATOR
+	     (that has a vector with operands).  */
+	  if (GET_RTX_LENGTH (code) != XVECLEN (pt, 2))
+	    return false;
+	  for (j = 0; j < XVECLEN (pt, 2); j++)
+	    if (!subst_pattern_match (XEXP (x, j), XVECEXP (pt, 2, j), lineno))
+	      return false;
+	}
+
+      /* Store the operand to OPERAND_DATA array.  */
+      gcc_assert (XINT (pt, 0) >= 0 && XINT (pt, 0) < MAX_OPERANDS);
+      operand_data[XINT (pt, 0)] = x;
+      return true;
+    }
+
+  if (code_pt == MATCH_PAR_DUP
+      || code_pt == MATCH_DUP
+      || code_pt == MATCH_OP_DUP
+      || code_pt == MATCH_SCRATCH
+      || code_pt == MATCH_PARALLEL)
+    {
+      /* Currently interface for these constructions isn't defined -
+	 probably they aren't needed in input template of define_subst at all.
+	 So, for now their usage in define_subst is forbidden.  */
+      error_with_line (lineno, "%s cannot be used in define_subst",
+		       GET_RTX_NAME (code_pt));
+    }
+
+  gcc_assert (code != MATCH_PAR_DUP
+      && code_pt != MATCH_DUP
+      && code_pt != MATCH_OP_DUP
+      && code_pt != MATCH_SCRATCH
+      && code_pt != MATCH_PARALLEL
+      && code_pt != MATCH_OPERAND
+      && code_pt != MATCH_OPERATOR);
+  /* If PT is none of the handled above, then we match only expressions with
+     the same code in X.  */
+  if (code != code_pt)
+    return false;
+
+  fmt = GET_RTX_FORMAT (code_pt);
+  len = GET_RTX_LENGTH (code_pt);
+
+  for (i = 0; i < len; i++)
+    {
+      if (fmt[i] == '0')
+	break;
+
+      switch (fmt[i])
+	{
+	case 'i': case 'w': case 's':
+	  continue;
+
+	case 'e': case 'u':
+	  if (!subst_pattern_match (XEXP (x, i), XEXP (pt, i), lineno))
+	    return false;
+	  break;
+	case 'E':
+	  {
+	    if (XVECLEN (x, i) != XVECLEN (pt, i))
+	      return false;
+	    for (j = 0; j < XVECLEN (pt, i); j++)
+	      if (!subst_pattern_match (XVECEXP (x, i, j), XVECEXP (pt, i, j),
+					lineno))
+		return false;
+	    break;
+	  }
+	default:
+	  gcc_unreachable ();
+	}
+    }
+
+  return true;
+}
+
 /* Examine the attribute "predicable"; discover its boolean values
    and its default.  */
 
@@ -662,6 +984,78 @@ n_alternatives (const char *s)
   return n;
 }
 
+/* The routine scans rtl PATTERN, find match_operand in it and counts
+   number of alternatives.  If PATTERN contains several match_operands
+   with different number of alternatives, error is emitted, and the
+   routine returns 0.  If all match_operands in PATTERN have the same
+   number of alternatives, it's stored in N_ALT, and the routine returns 1.
+   Argument LINENO is used in when the error is emitted.  */
+static int
+get_alternatives_number (rtx pattern, int *n_alt, int lineno)
+{
+  const char *fmt;
+  enum rtx_code code;
+  int i, j, len;
+
+  if (!n_alt)
+    return 0;
+
+  code = GET_CODE (pattern);
+  switch (code)
+    {
+    case MATCH_OPERAND:
+      i = n_alternatives (XSTR (pattern, 2));
+      /* n_alternatives returns 1 if constraint string is empty -
+	 here we fix it up.  */
+      if (!*(XSTR (pattern, 2)))
+	i = 0;
+      if (*n_alt <= 0)
+	*n_alt = i;
+
+      else if (i && i != *n_alt)
+	{
+	  error_with_line (lineno,
+			   "wrong number of alternatives in operand %d",
+			   XINT (pattern, 0));
+	  return 0;
+	}
+
+    default:
+      break;
+    }
+
+  fmt = GET_RTX_FORMAT (code);
+  len = GET_RTX_LENGTH (code);
+  for (i = 0; i < len; i++)
+    {
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  if (!get_alternatives_number (XEXP (pattern, i), n_alt, lineno))
+		return 0;
+	  break;
+
+	case 'V':
+	  if (XVEC (pattern, i) == NULL)
+	    break;
+
+	case 'E':
+	  for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
+	    if (!get_alternatives_number (XVECEXP (pattern, i, j),
+					  n_alt, lineno))
+		return 0;
+	  break;
+
+	case 'i': case 'w': case '0': case 's': case 'S': case 'T':
+	  break;
+
+	default:
+	  gcc_unreachable ();
+	}
+    }
+    return 1;
+}
+
 /* Determine how many alternatives there are in INSN, and how many
    operands.  */
 
@@ -746,7 +1140,7 @@ alter_predicate_for_insn (rtx pattern, int alt, int max_op, int lineno)
 	  {
 	    size_t c_len = strlen (c);
 	    size_t len = alt * (c_len + 1);
-	    char *new_c = XNEWVEC(char, len);
+	    char *new_c = XNEWVEC (char, len);
 
 	    memcpy (new_c, c, c_len);
 	    for (i = 1; i < alt; ++i)
@@ -806,6 +1200,64 @@ alter_predicate_for_insn (rtx pattern, int alt, int max_op, int lineno)
   return pattern;
 }
 
+/* Duplicate constraints in PATTERN.  If pattern is from original
+   rtl-template, we need to duplicate each alternative - for that we
+   need to use duplicate_each_alternative () as a functor ALTER.
+   If pattern is from output-pattern of define_subst, we need to
+   duplicate constraints in another way - with duplicate_alternatives ().
+   N_DUP is multiplication factor.  */
+static rtx
+alter_constraints (rtx pattern, int n_dup, constraints_handler_t alter)
+{
+  const char *fmt;
+  enum rtx_code code;
+  int i, j, len;
+
+  code = GET_CODE (pattern);
+  switch (code)
+    {
+    case MATCH_OPERAND:
+      XSTR (pattern, 2) = alter (XSTR (pattern, 2), n_dup);
+      break;
+
+    default:
+      break;
+    }
+
+  fmt = GET_RTX_FORMAT (code);
+  len = GET_RTX_LENGTH (code);
+  for (i = 0; i < len; i++)
+    {
+      rtx r;
+
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  r = alter_constraints (XEXP (pattern, i), n_dup, alter);
+	  if (r == NULL)
+	    return r;
+	  break;
+
+	case 'E':
+	  for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
+	    {
+	      r = alter_constraints (XVECEXP (pattern, i, j), n_dup, alter);
+	      if (r == NULL)
+		return r;
+	    }
+	  break;
+
+	case 'i': case 'w': case '0': case 's':
+	  break;
+
+	default:
+	  break;
+	}
+    }
+
+  return pattern;
+}
+
 static const char *
 alter_test_for_insn (struct queue_elem *ce_elem,
 		     struct queue_elem *insn_elem)
@@ -920,7 +1372,7 @@ alter_attrs_for_insn (rtx insn)
   if (!global_changes_made)
     {
       struct queue_elem *elem;
-      
+
       global_changes_made = true;
       add_define_attr ("ce_enabled");
       add_define_attr ("nonce_enabled");
@@ -954,23 +1406,63 @@ alter_attrs_for_insn (rtx insn)
   XVEC (insn, 4) = new_vec;
 }
 
-/* Adjust all of the operand numbers in SRC to match the shift they'll
-   get from an operand displacement of DISP.  Return a pointer after the
-   adjusted string.  */
-
-static char *
-shift_output_template (char *dest, const char *src, int disp)
+/* As number of constraints is changed after define_subst, we need to
+   process attributes as well - we need to duplicate them the same way
+   that we duplicated constraints in original pattern
+   ELEM is a queue element, containing our rtl-template,
+   N_DUP - multiplication factor.  */
+static void
+alter_attrs_for_subst_insn (struct queue_elem * elem, int n_dup)
 {
-  while (*src)
+  rtvec vec = XVEC (elem->data, 4);
+  int num_elem;
+  int i;
+
+  if (n_dup < 2 || ! vec)
+    return;
+
+  num_elem = GET_NUM_ELEM (vec);
+  for (i = num_elem - 1; i >= 0; --i)
     {
-      char c = *src++;
-      *dest++ = c;
-      if (c == '%')
+      rtx sub = RTVEC_ELT (vec, i);
+      switch (GET_CODE (sub))
 	{
-	  c = *src++;
-	  if (ISDIGIT ((unsigned char) c))
-	    c += disp;
-	  else if (ISALPHA (c))
+	case SET_ATTR:
+	  if (strchr (XSTR (sub, 1), ',') != NULL)
+	    XSTR (sub, 1) = duplicate_alternatives (XSTR (sub, 1), n_dup);
+	    break;
+
+	case SET_ATTR_ALTERNATIVE:
+	case SET:
+	  error_with_line (elem->lineno,
+			   "%s: `define_subst' does not support attributes "
+			   "assigned by `set' and `set_attr_alternative'",
+			   XSTR (elem->data, 0));
+	  return;
+
+	default:
+	  gcc_unreachable ();
+	}
+    }
+}
+
+/* Adjust all of the operand numbers in SRC to match the shift they'll
+   get from an operand displacement of DISP.  Return a pointer after the
+   adjusted string.  */
+
+static char *
+shift_output_template (char *dest, const char *src, int disp)
+{
+  while (*src)
+    {
+      char c = *src++;
+      *dest++ = c;
+      if (c == '%')
+	{
+	  c = *src++;
+	  if (ISDIGIT ((unsigned char) c))
+	    c += disp;
+	  else if (ISALPHA (c))
 	    {
 	      *dest++ = c;
 	      c = *src++ + disp;
@@ -1008,7 +1500,7 @@ alter_output_for_insn (struct queue_elem *ce_elem,
   if (*insn_out == '@')
     {
       len = (ce_len + 1) * alt + insn_len + 1;
-      p = result = XNEWVEC(char, len);
+      p = result = XNEWVEC (char, len);
 
       do
 	{
@@ -1042,6 +1534,136 @@ alter_output_for_insn (struct queue_elem *ce_elem,
   return result;
 }
 
+/* From string STR "a,b,c" produce "a,b,c,a,b,c,a,b,c", i.e. original
+   string, duplicated N_DUP times.  */
+
+static const char *
+duplicate_alternatives (const char * str, int n_dup)
+{
+  int i, len, new_len;
+  char *result, *sp;
+  const char *cp;
+
+  if (n_dup < 2)
+    return str;
+
+  while (ISSPACE (*str))
+    str++;
+
+  if (*str == '\0')
+    return str;
+
+  cp = str;
+  len = strlen (str);
+  new_len = (len + 1) * n_dup;
+
+  sp = result = XNEWVEC (char, new_len);
+
+  /* Global modifier characters mustn't be duplicated: skip if found.  */
+  if (*cp == '=' || *cp == '+' || *cp == '%')
+    {
+      *sp++ = *cp++;
+      len--;
+    }
+
+  /* Copy original constraints N_DUP times.  */
+  for (i = 0; i < n_dup; i++, sp += len+1)
+    {
+      memcpy (sp, cp, len);
+      *(sp+len) = (i == n_dup - 1) ? '\0' : ',';
+    }
+
+  return result;
+}
+
+/* From string STR "a,b,c" produce "a,a,a,b,b,b,c,c,c", i.e. string where
+   each alternative from the original string is duplicated N_DUP times.  */
+static const char *
+duplicate_each_alternative (const char * str, int n_dup)
+{
+  int i, len, new_len;
+  char *result, *sp, *ep, *cp;
+
+  if (n_dup < 2)
+    return str;
+
+  while (ISSPACE (*str))
+    str++;
+
+  if (*str == '\0')
+    return str;
+
+  cp = xstrdup (str);
+
+  new_len = (strlen (cp) + 1) * n_dup;
+
+  sp = result = XNEWVEC (char, new_len);
+
+  /* Global modifier characters mustn't be duplicated: skip if found.  */
+  if (*cp == '=' || *cp == '+' || *cp == '%')
+      *sp++ = *cp++;
+
+  do
+    {
+      if ((ep = strchr (cp, ',')) != NULL)
+	*ep++ = '\0';
+      len = strlen (cp);
+
+      /* Copy a constraint N_DUP times.  */
+      for (i = 0; i < n_dup; i++, sp += len + 1)
+	{
+	  memcpy (sp, cp, len);
+	  *(sp+len) = (ep == NULL && i == n_dup - 1) ? '\0' : ',';
+	}
+
+      cp = ep;
+    }
+  while (cp != NULL);
+
+  return result;
+}
+
+/* Alter the output of INSN whose pattern was modified by
+   DEFINE_SUBST.  We must replicate output strings according
+   to the new number of alternatives ALT in substituted pattern.
+   If ALT equals 1, output has one alternative or defined by C
+   code, then output is returned without any changes.  */
+
+static const char *
+alter_output_for_subst_insn (rtx insn, int alt)
+{
+  const char *insn_out, *sp ;
+  char *old_out, *new_out, *cp;
+  int i, j, new_len;
+
+  insn_out = XTMPL (insn, 3);
+
+  if (alt < 2 || *insn_out == '*' || *insn_out != '@')
+    return insn_out;
+
+  old_out = XNEWVEC (char, strlen (insn_out)),
+  sp = insn_out;
+
+  while (ISSPACE (*sp) || *sp == '@')
+    sp++;
+
+  for (i = 0; *sp;)
+    old_out[i++] = *sp++;
+
+  new_len = alt * (i + 1) + 1;
+
+  new_out = XNEWVEC (char, new_len);
+  new_out[0] = '@';
+
+  for (j = 0, cp = new_out + 1; j < alt; j++, cp += i + 1)
+    {
+      memcpy (cp, old_out, i);
+      *(cp+i) = (j == alt - 1) ? '\0' : '\n';
+    }
+
+  return new_out;
+}
+
 /* Replicate insns as appropriate for the given DEFINE_COND_EXEC.  */
 
 static void
@@ -1151,6 +1773,411 @@ process_one_cond_exec (struct queue_elem *ce_elem)
     }
 }
 
+/* Try to apply define_substs to the given ELEM.
+   Only define_substs, specified via attributes would be applied.
+   If attribute, requiring define_subst, is set, but no define_subst
+   was applied, ELEM would be deleted.  */
+
+static void
+process_substs_on_one_elem (struct queue_elem *elem,
+			    struct queue_elem *queue)
+{
+  struct queue_elem *subst_elem;
+  int i, j, patterns_match;
+
+  for (subst_elem = define_subst_queue;
+       subst_elem; subst_elem = subst_elem->next)
+    {
+      int alternatives, alternatives_subst;
+      rtx subst_pattern;
+      rtvec subst_pattern_vec;
+
+      if (!has_subst_attribute (elem, subst_elem))
+	continue;
+
+      /* Compare original rtl-pattern from define_insn with input
+	 pattern from define_subst.
+	 Also, check if numbers of alternatives are the same in all
+	 match_operands.  */
+      if (XVECLEN (elem->data, 1) != XVECLEN (subst_elem->data, 1))
+	continue;
+      patterns_match = 1;
+      alternatives = -1;
+      alternatives_subst = -1;
+      for (j = 0; j < XVECLEN (elem->data, 1); j++)
+	{
+	  if (!subst_pattern_match (XVECEXP (elem->data, 1, j),
+				    XVECEXP (subst_elem->data, 1, j),
+				    subst_elem->lineno))
+	    {
+	      patterns_match = 0;
+	      break;
+	    }
+
+	  if (!get_alternatives_number (XVECEXP (elem->data, 1, j),
+					&alternatives, subst_elem->lineno))
+	    {
+	      patterns_match = 0;
+	      break;
+	    }
+	}
+
+      /* Check if numbers of alternatives are the same in all
+	 match_operands in output template of define_subst.  */
+      for (j = 0; j < XVECLEN (subst_elem->data, 3); j++)
+	{
+	  if (!get_alternatives_number (XVECEXP (subst_elem->data, 3, j),
+					&alternatives_subst,
+					subst_elem->lineno))
+	    {
+	      patterns_match = 0;
+	      break;
+	    }
+	}
+
+      if (!patterns_match)
+	continue;
+
+      /* Clear array in which we save occupied indexes of operands.  */
+      memset (used_operands_numbers, 0, sizeof (used_operands_numbers));
+
+      /* Create a pattern, based on the output one from define_subst.  */
+      subst_pattern_vec = rtvec_alloc (XVECLEN (subst_elem->data, 3));
+      for (j = 0; j < XVECLEN (subst_elem->data, 3); j++)
+	{
+	  subst_pattern = copy_rtx (XVECEXP (subst_elem->data, 3, j));
+
+	  /* Duplicate constraints in substitute-pattern.  */
+	  subst_pattern = alter_constraints (subst_pattern, alternatives,
+					     duplicate_each_alternative);
+
+	  subst_pattern = adjust_operands_numbers (subst_pattern);
+
+	  /* Substitute match_dup and match_op_dup in the new pattern and
+	     duplicate constraints.  */
+	  subst_pattern = subst_dup (subst_pattern, alternatives,
+				     alternatives_subst);
+
+	  replace_duplicating_operands_in_pattern (subst_pattern);
+
+	  /* We don't need any constraints in DEFINE_EXPAND.  */
+	  if (GET_CODE (elem->data) == DEFINE_EXPAND)
+	    remove_constraints (subst_pattern);
+
+	  RTVEC_ELT (subst_pattern_vec, j) = subst_pattern;
+	}
+      XVEC (elem->data, 1) = subst_pattern_vec;
+
+      for (i = 0; i < MAX_OPERANDS; i++)
+	  match_operand_entries_in_pattern[i] = NULL;
+
+      if (GET_CODE (elem->data) == DEFINE_INSN)
+	{
+	  XTMPL (elem->data, 3) =
+	    alter_output_for_subst_insn (elem->data, alternatives_subst);
+	  alter_attrs_for_subst_insn (elem, alternatives_subst);
+	}
+
+      /* Recalculate condition, joining conditions from original and
+	 DEFINE_SUBST input patterns.  */
+      XSTR (elem->data, 2) = join_c_conditions (XSTR (subst_elem->data, 2),
+						XSTR (elem->data, 2));
+      /* Mark that subst was applied by changing attribute from "yes"
+	 to "no".  */
+      change_subst_attribute (elem, subst_elem, subst_false);
+    }
+
+  /* If ELEM contains a subst attribute with value "yes", then we
+     expected that a subst would be applied, but it wasn't - so,
+     we need to remove that elementto avoid duplicating.  */
+  for (subst_elem = define_subst_queue;
+       subst_elem; subst_elem = subst_elem->next)
+    {
+      if (has_subst_attribute (elem, subst_elem))
+	{
+	  remove_from_queue (elem, &queue);
+	  return;
+	}
+    }
+}
+
+/* This is a subroutine of mark_operands_used_in_match_dup.
+   This routine is marks all MATCH_OPERANDs inside PATTERN as occupied.  */
+static void
+mark_operands_from_match_dup (rtx pattern)
+{
+  const char *fmt;
+  int i, j, len, opno;
+
+  if (GET_CODE (pattern) == MATCH_OPERAND)
+    {
+      opno = XINT (pattern, 0);
+      gcc_assert (opno >= 0 && opno < MAX_OPERANDS);
+      used_operands_numbers [opno] = 1;
+    }
+  fmt = GET_RTX_FORMAT (GET_CODE (pattern));
+  len = GET_RTX_LENGTH (GET_CODE (pattern));
+  for (i = 0; i < len; i++)
+    {
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  mark_operands_from_match_dup (XEXP (pattern, i));
+	  break;
+	case 'E':
+	  for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
+	    mark_operands_from_match_dup (XVECEXP (pattern, i, j));
+	  break;
+	}
+    }
+}
+
+/* This is a subroutine of adjust_operands_numbers.
+   It goes through all expressions in PATTERN and when MATCH_DUP is
+   met, all MATCH_OPERANDs inside it is marked as occupied.  The
+   process of marking is done by routin mark_operands_from_match_dup.  */
+static void
+mark_operands_used_in_match_dup (rtx pattern)
+{
+  const char *fmt;
+  int i, j, len, opno;
+
+  if (GET_CODE (pattern) == MATCH_DUP)
+    {
+      opno = XINT (pattern, 0);
+      gcc_assert (opno >= 0 && opno < MAX_OPERANDS);
+      mark_operands_from_match_dup (operand_data[opno]);
+      return;
+    }
+  fmt = GET_RTX_FORMAT (GET_CODE (pattern));
+  len = GET_RTX_LENGTH (GET_CODE (pattern));
+  for (i = 0; i < len; i++)
+    {
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  mark_operands_used_in_match_dup (XEXP (pattern, i));
+	  break;
+	case 'E':
+	  for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
+	    mark_operands_used_in_match_dup (XVECEXP (pattern, i, j));
+	  break;
+	}
+    }
+}
+
+/* This is subroutine of renumerate_operands_in_pattern.
+   It finds first not-occupied operand-index.  */
+static int
+find_first_unused_number_of_operand ()
+{
+  int i;
+  for (i = 0; i < MAX_OPERANDS; i++)
+    if (!used_operands_numbers[i])
+      return i;
+  return MAX_OPERANDS;
+}
+
+/* This is subroutine of adjust_operands_numbers.
+   It visits all expressions in PATTERN and assigns not-occupied
+   operand indexes to MATCH_OPERANDs and MATCH_OPERATORs of this
+   PATTERN.  */
+static void
+renumerate_operands_in_pattern (rtx pattern)
+{
+  const char *fmt;
+  enum rtx_code code;
+  int i, j, len, new_opno;
+  code = GET_CODE (pattern);
+
+  if (code == MATCH_OPERAND
+      || code == MATCH_OPERATOR)
+    {
+      new_opno = find_first_unused_number_of_operand ();
+      gcc_assert (new_opno >= 0 && new_opno < MAX_OPERANDS);
+      XINT (pattern, 0) = new_opno;
+      used_operands_numbers [new_opno] = 1;
+    }
+
+  fmt = GET_RTX_FORMAT (GET_CODE (pattern));
+  len = GET_RTX_LENGTH (GET_CODE (pattern));
+  for (i = 0; i < len; i++)
+    {
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  renumerate_operands_in_pattern (XEXP (pattern, i));
+	  break;
+	case 'E':
+	  for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
+	    renumerate_operands_in_pattern (XVECEXP (pattern, i, j));
+	  break;
+	}
+    }
+}
+
+/* If output pattern of define_subst contains MATCH_DUP, then this
+   expression would be replaced with the pattern, matched with
+   MATCH_OPERAND from input pattern.  This pattern could contain any
+   number of MATCH_OPERANDs, MATCH_OPERATORs etc., so it's possible
+   that a MATCH_OPERAND from output_pattern (if any) would have the
+   same number, as MATCH_OPERAND from copied pattern.  To avoid such
+   indexes overlapping, we assign new indexes to MATCH_OPERANDs,
+   laying in the output pattern outside of MATCH_DUPs.  */
+static rtx
+adjust_operands_numbers (rtx pattern)
+{
+  mark_operands_used_in_match_dup (pattern);
+
+  renumerate_operands_in_pattern (pattern);
+
+  return pattern;
+}
+
+/* Generate RTL expression
+   (match_dup OPNO)
+   */
+static rtx
+generate_match_dup (int opno)
+{
+  rtx return_rtx = rtx_alloc (MATCH_DUP);
+  PUT_CODE (return_rtx, MATCH_DUP);
+  XINT (return_rtx, 0) = opno;
+  return return_rtx;
+}
+
+/* This routine checks all match_operands in PATTERN and if some of
+   have the same index, it replaces all of them except the first one  to
+   match_dup.
+   Usually, match_operands with the same indexes are forbidden, but
+   after define_subst copy an RTL-expression from original template,
+   indexes of existed and just-copied match_operands could coincide.
+   To fix it, we replace one of them with match_dup.  */
+static rtx
+replace_duplicating_operands_in_pattern (rtx pattern)
+{
+  const char *fmt;
+  int i, j, len, opno;
+  rtx mdup;
+
+  if (GET_CODE (pattern) == MATCH_OPERAND)
+    {
+      opno = XINT (pattern, 0);
+      gcc_assert (opno >= 0 && opno < MAX_OPERANDS);
+      if (match_operand_entries_in_pattern[opno] == NULL)
+	{
+	  match_operand_entries_in_pattern[opno] = pattern;
+	  return NULL;
+	}
+      else
+	{
+	  /* Compare predicates before replacing with match_dup.  */
+	  if (strcmp (XSTR (pattern, 1),
+		      XSTR (match_operand_entries_in_pattern[opno], 1)))
+	    {
+	      error ("duplicated match_operands with different predicates were"
+		     " found.");
+	      return NULL;
+	    }
+	  return generate_match_dup (opno);
+	}
+    }
+  fmt = GET_RTX_FORMAT (GET_CODE (pattern));
+  len = GET_RTX_LENGTH (GET_CODE (pattern));
+  for (i = 0; i < len; i++)
+    {
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  mdup = replace_duplicating_operands_in_pattern (XEXP (pattern, i));
+	  if (mdup)
+	    XEXP (pattern, i) = mdup;
+	  break;
+	case 'E':
+	  for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
+	    {
+	      mdup =
+		replace_duplicating_operands_in_pattern (XVECEXP
+							 (pattern, i, j));
+	      if (mdup)
+		XVECEXP (pattern, i, j) = mdup;
+	    }
+	  break;
+	}
+    }
+  return NULL;
+}
+
+/* The routine modifies given input PATTERN of define_subst, replacing
+   MATCH_DUP and MATCH_OP_DUP with operands from define_insn original
+   pattern, whose operands are stored in OPERAND_DATA array.
+   It also duplicates constraints in operands - constraints from
+   define_insn operands are duplicated N_SUBST_ALT times, constraints
+   from define_subst operands are duplicated N_ALT times.
+   After the duplication, returned output rtl-pattern contains every
+   combination of input constraints Vs constraints from define_subst
+   output.  */
+static rtx
+subst_dup (rtx pattern, int n_alt, int n_subst_alt)
+{
+  const char *fmt;
+  enum rtx_code code;
+  int i, j, len, opno;
+
+  code = GET_CODE (pattern);
+  switch (code)
+    {
+    case MATCH_DUP:
+    case MATCH_OP_DUP:
+      opno = XINT (pattern, 0);
+
+      gcc_assert (opno >= 0 && opno < MAX_OPERANDS);
+
+      if (operand_data[opno])
+	{
+	  pattern = copy_rtx (operand_data[opno]);
+
+	  /* Duplicate constraints.  */
+	  pattern = alter_constraints (pattern, n_subst_alt,
+				       duplicate_alternatives);
+	}
+      break;
+
+    default:
+      break;
+    }
+
+  fmt = GET_RTX_FORMAT (GET_CODE (pattern));
+  len = GET_RTX_LENGTH (GET_CODE (pattern));
+  for (i = 0; i < len; i++)
+    {
+      switch (fmt[i])
+	{
+	case 'e': case 'u':
+	  if (code != MATCH_DUP && code != MATCH_OP_DUP)
+	    XEXP (pattern, i) = subst_dup (XEXP (pattern, i),
+					   n_alt, n_subst_alt);
+	  break;
+	case 'V':
+	  if (XVEC (pattern, i) == NULL)
+	    break;
+	case 'E':
+	  for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
+	    if (code != MATCH_DUP && code != MATCH_OP_DUP)
+	      XVECEXP (pattern, i, j) = subst_dup (XVECEXP (pattern, i, j),
+						   n_alt, n_subst_alt);
+	  break;
+
+	case 'i': case 'w': case '0': case 's': case 'S': case 'T':
+	  break;
+
+	default:
+	  gcc_unreachable ();
+	}
+    }
+  return pattern;
+}
+
 /* If we have any DEFINE_COND_EXEC patterns, expand the DEFINE_INSN
    patterns appropriately.  */
 
@@ -1166,6 +2193,42 @@ process_define_cond_exec (void)
   for (elem = define_cond_exec_queue; elem ; elem = elem->next)
     process_one_cond_exec (elem);
 }
+
+/* If we have any DEFINE_SUBST patterns, expand DEFINE_INSN and
+   DEFINE_EXPAND patterns appropriately.  */
+
+static void
+process_define_subst (void)
+{
+  struct queue_elem *elem, *elem_attr;
+
+  /* Check if each define_subst has corresponding define_subst_attr.  */
+  for (elem = define_subst_queue; elem ; elem = elem->next)
+    {
+      for (elem_attr = define_subst_attr_queue;
+	   elem_attr;
+	   elem_attr = elem_attr->next)
+	if (strcmp (XSTR (elem->data, 0), XSTR (elem_attr->data, 1)) == 0)
+	    goto found;
+
+	error_with_line (elem->lineno,
+			 "%s: `define_subst' must have at least one "
+			 "corresponding `define_subst_attr'",
+			 XSTR (elem->data, 0));
+	return;
+      found:
+	continue;
+    }
+
+  for (elem = define_insn_queue; elem ; elem = elem->next)
+    process_substs_on_one_elem (elem, define_insn_queue);
+  for (elem = other_queue; elem ; elem = elem->next)
+    {
+      if (GET_CODE (elem->data) != DEFINE_EXPAND)
+	continue;
+      process_substs_on_one_elem (elem, other_queue);
+    }
+}
 \f
 /* A read_md_files callback for reading an rtx.  */
 
@@ -1391,6 +2454,38 @@ gen_mnemonic_attr (void)
   XSTR (mnemonic_attr, 1) = XOBFINISH (&string_obstack, char *);
 }
 
+/* Check if there are DEFINE_ATTRs with the same name.  */
+static void
+check_define_attr_duplicates ()
+{
+  struct queue_elem *elem;
+  htab_t attr_htab;
+  char * attr_name;
+  void **slot;
+
+  attr_htab = htab_create (500, htab_hash_string, htab_eq_string, NULL);
+
+  for (elem = define_attr_queue; elem; elem = elem->next)
+    {
+      attr_name = xstrdup (XSTR (elem->data, 0));
+
+      slot = htab_find_slot (attr_htab, attr_name, INSERT);
+
+      /* Duplicate.  */
+      if (*slot)
+	{
+	  error_with_line (elem->lineno, "redefinition of attribute '%s'",
+			   attr_name);
+	  htab_delete (attr_htab);
+	  return;
+	}
+
+      *slot = attr_name;
+    }
+
+  htab_delete (attr_htab);
+}
+
 /* The entry point for initializing the reader.  */
 
 bool
@@ -1407,10 +2502,17 @@ init_rtx_reader_args_cb (int argc, char **argv,
 
   read_md_files (argc, argv, parse_opt, rtx_handle_directive);
 
+  if (define_attr_queue != NULL)
+    check_define_attr_duplicates ();
+
   /* Process define_cond_exec patterns.  */
   if (define_cond_exec_queue != NULL)
     process_define_cond_exec ();
 
+  /* Process define_subst patterns.  */
+  if (define_subst_queue != NULL)
+    process_define_subst ();
+
   if (define_attr_queue != NULL)
     gen_mnemonic_attr ();
 
@@ -1470,6 +2572,7 @@ read_md_rtx (int *lineno, int *seqnr)
     {
     case DEFINE_INSN:
     case DEFINE_EXPAND:
+    case DEFINE_SUBST:
       if (maybe_eval_c_test (XSTR (desc, 2)) != 0)
 	sequence_num++;
       else if (insn_elision)
diff --git a/gcc/read-rtl.c b/gcc/read-rtl.c
index 30c2fb6..f442b9a 100644
--- a/gcc/read-rtl.c
+++ b/gcc/read-rtl.c
@@ -108,13 +108,28 @@ typedef struct attribute_use attribute_use;
 DEF_VEC_O (attribute_use);
 DEF_VEC_ALLOC_O (attribute_use, heap);
 
+/* This struct is used to link subst_attr named ATTR_NAME with
+   corresponding define_subst named ITER_NAME.  */
+struct subst_attr_to_iter_mapping
+{
+    char *attr_name;
+    char *iter_name;
+};
+
+/* Hash-table to store links between subst-attributes and
+   define_substs.  */
+htab_t subst_attr_to_iter_map = NULL;
+/* This global stores name of subst-iterator which is currently being
+   processed.  */
+const char *current_iterator_name;
+
 static void validate_const_int (const char *);
 static rtx read_rtx_code (const char *);
 static rtx read_nested_rtx (void);
 static rtx read_rtx_variadic (rtx);
 
 /* The mode and code iterator structures.  */
-static struct iterator_group modes, codes, ints;
+static struct iterator_group modes, codes, ints, substs;
 
 /* All iterators used in the current rtx.  */
 static VEC (mapping_ptr, heap) *current_iterators;
@@ -184,6 +199,91 @@ apply_int_iterator (void *loc, int value)
   *(int *)loc = value;
 }
 
+/* This routine adds attribute or does nothing depending on VALUE.  When
+   VALUE is 1, it does nothing - the first duplicate of original
+   template is kept untouched when it's subjected to a define_subst.
+   When VALUE isn't 1, the routine modifies RTL-template LOC, adding
+   attribute, named exactly as define_subst, which later will be
+   applied.  If such attribute has already been added, then no the
+   routine has no effect.  */
+static void
+apply_subst_iterator (void *loc, int value)
+{
+  rtx rt = (rtx)loc;
+  rtx new_attr;
+  rtvec attrs_vec, new_attrs_vec;
+  int i;
+  if (value == 1)
+    return;
+  gcc_assert (GET_CODE (rt) == DEFINE_INSN
+	      || GET_CODE (rt) == DEFINE_EXPAND);
+
+  attrs_vec = XVEC (rt, 4);
+
+  /* If we've already added attribute 'current_iterator_name', then we
+     have nothing to do now.  */
+  if (attrs_vec)
+    {
+      for (i = 0; i < GET_NUM_ELEM (attrs_vec); i++)
+	{
+	  if (strcmp (XSTR (attrs_vec->elem[i], 0), current_iterator_name) == 0)
+	    return;
+	}
+    }
+
+  /* Add attribute with subst name - it serves as a mark for
+     define_subst which later would be applied to this pattern.  */
+  new_attr = rtx_alloc (SET_ATTR);
+  PUT_CODE (new_attr, SET_ATTR);
+  XSTR (new_attr, 0) = xstrdup (current_iterator_name);
+  XSTR (new_attr, 1) = xstrdup ("yes");
+
+  if (!attrs_vec)
+    {
+      new_attrs_vec = rtvec_alloc (1);
+      new_attrs_vec->elem[0] = new_attr;
+    }
+  else
+    {
+      new_attrs_vec = rtvec_alloc (GET_NUM_ELEM (attrs_vec) + 1);
+      memcpy (&new_attrs_vec->elem[0], &attrs_vec->elem[0],
+	      GET_NUM_ELEM (attrs_vec) * sizeof (rtx));
+      new_attrs_vec->elem[GET_NUM_ELEM (attrs_vec)] = new_attr;
+    }
+  XVEC (rt, 4) = new_attrs_vec;
+}
+
+/* Map subst-attribute ATTR to subst iterator ITER.  */
+
+static void
+bind_subst_iter_and_attr (const char *iter, const char *attr)
+{
+  struct subst_attr_to_iter_mapping *value;
+  void **slot;
+  if (!subst_attr_to_iter_map)
+    subst_attr_to_iter_map =
+      htab_create (1, leading_string_hash, leading_string_eq_p, 0);
+  value = XNEW (struct subst_attr_to_iter_mapping);
+  value->attr_name = xstrdup (attr);
+  value->iter_name = xstrdup (iter);
+  slot = htab_find_slot (subst_attr_to_iter_map, value, INSERT);
+  *slot = value;
+}
+
+/* Return name of a subst-iterator, corresponding to subst-attribute ATTR.  */
+
+static char*
+find_subst_iter_by_attr (const char *attr)
+{
+  char *iter_name = NULL;
+  struct subst_attr_to_iter_mapping *value;
+  value = (struct subst_attr_to_iter_mapping*)
+    htab_find (subst_attr_to_iter_map, &attr);
+  if (value)
+    iter_name = value->iter_name;
+  return iter_name;
+}
+
 /* Map attribute string P to its current value.  Return null if the attribute
    isn't known.  */
 
@@ -222,11 +322,23 @@ map_attr_string (const char *p)
       /* Find the attribute specification.  */
       m = (struct mapping *) htab_find (iterator->group->attrs, &attr);
       if (m)
-	/* Find the attribute value associated with the current
-	   iterator value.  */
-	for (v = m->values; v; v = v->next)
-	  if (v->number == iterator->current_value->number)
-	    return v;
+	{
+	  /* In contrast to code/mode/int iterators, attributes of subst
+	     iterators are linked to one specific subst-iterator.  So, if
+	     we are dealing with subst-iterator, we should check if it's
+	     the one which linked with the given attribute.  */
+	  if (iterator->group == &substs)
+	    {
+	      char *iter_name = find_subst_iter_by_attr (attr);
+	      if (strcmp (iter_name, iterator->name) != 0)
+		continue;
+	    }
+	  /* Find the attribute value associated with the current
+	     iterator value.  */
+	  for (v = m->values; v; v = v->next)
+	    if (v->number == iterator->current_value->number)
+	      return v;
+	}
     }
   return NULL;
 }
@@ -343,6 +455,7 @@ add_condition_to_rtx (rtx x, const char *extra)
     {
     case DEFINE_INSN:
     case DEFINE_EXPAND:
+    case DEFINE_SUBST:
       XSTR (x, 2) = add_condition_to_string (XSTR (x, 2), extra);
       break;
 
@@ -432,6 +545,7 @@ apply_iterators (rtx original, rtx *queue)
   htab_traverse (modes.iterators, add_current_iterators, NULL);
   htab_traverse (codes.iterators, add_current_iterators, NULL);
   htab_traverse (ints.iterators, add_current_iterators, NULL);
+  htab_traverse (substs.iterators, add_current_iterators, NULL);
   gcc_assert (!VEC_empty (mapping_ptr, current_iterators));
 
   for (;;)
@@ -441,6 +555,8 @@ apply_iterators (rtx original, rtx *queue)
       condition = NULL;
       FOR_EACH_VEC_ELT (iterator_use, iterator_uses, i, iuse)
 	{
+	  if (iuse->iterator->group == &substs)
+	    continue;
 	  v = iuse->iterator->current_value;
 	  iuse->iterator->group->apply_iterator (iuse->ptr, v->number);
 	  condition = join_c_conditions (condition, v->string);
@@ -449,6 +565,19 @@ apply_iterators (rtx original, rtx *queue)
       x = copy_rtx_for_iterators (original);
       add_condition_to_rtx (x, condition);
 
+      /* We apply subst iterator after RTL-template is copied, as during
+	 subst-iterator processing, we could add an attribute to the
+	 RTL-template, and we don't want to do it in the original one.  */
+      FOR_EACH_VEC_ELT (iterator_use, iterator_uses, i, iuse)
+	{
+	  v = iuse->iterator->current_value;
+	  if (iuse->iterator->group == &substs)
+	    {
+	      iuse->ptr = x;
+	      current_iterator_name = iuse->iterator->name;
+	      iuse->iterator->group->apply_iterator (iuse->ptr, v->number);
+	    }
+	}
       /* Add the new rtx to the end of the queue.  */
       XEXP (*queue, 0) = x;
       XEXP (*queue, 1) = NULL_RTX;
@@ -544,6 +673,12 @@ initialize_iterators (void)
   ints.find_builtin = find_int;
   ints.apply_iterator = apply_int_iterator;
 
+  substs.attrs = htab_create (13, leading_string_hash, leading_string_eq_p, 0);
+  substs.iterators = htab_create (13, leading_string_hash,
+				 leading_string_eq_p, 0);
+  substs.find_builtin = find_int; /* We don't use it, anyway.  */
+  substs.apply_iterator = apply_subst_iterator;
+
   lower = add_mapping (&modes, modes.attrs, "mode");
   upper = add_mapping (&modes, modes.attrs, "MODE");
   lower_ptr = &lower->values;
@@ -786,6 +921,94 @@ read_mapping (struct iterator_group *group, htab_t table)
   return m;
 }
 
+/* For iterator with name ATTR_NAME generate define_attr with values
+   'yes' and 'no'.  This attribute is used to mark templates to which
+   define_subst ATTR_NAME should be applied.  This attribute is set and
+   defined implicitly and automatically.  */
+static void
+add_define_attr_for_define_subst (const char *attr_name, rtx *queue)
+{
+  rtx const_str, return_rtx;
+
+  return_rtx = rtx_alloc (DEFINE_ATTR);
+  PUT_CODE (return_rtx, DEFINE_ATTR);
+
+  const_str = rtx_alloc (CONST_STRING);
+  PUT_CODE (const_str, CONST_STRING);
+  XSTR (const_str, 0) = xstrdup ("no");
+
+  XSTR (return_rtx, 0) = xstrdup (attr_name);
+  XSTR (return_rtx, 1) = xstrdup ("no,yes");
+  XEXP (return_rtx, 2) = const_str;
+
+  XEXP (*queue, 0) = return_rtx;
+  XEXP (*queue, 1) = NULL_RTX;
+}
+
+/* This routine generates DEFINE_SUBST_ATTR expression with operands
+   ATTR_OPERANDS and places it to QUEUE.  */
+static void
+add_define_subst_attr (const char **attr_operands, rtx *queue)
+{
+  rtx return_rtx;
+  int i;
+
+  return_rtx = rtx_alloc (DEFINE_SUBST_ATTR);
+  PUT_CODE (return_rtx, DEFINE_SUBST_ATTR);
+
+  for (i = 0; i < 4; i++)
+    XSTR (return_rtx, i) = xstrdup (attr_operands[i]);
+
+  XEXP (*queue, 0) = return_rtx;
+  XEXP (*queue, 1) = NULL_RTX;
+}
+
+/* Read define_subst_attribute construction.  It has next form:
+	(define_subst_attribute <attribute_name> <iterator_name> <value1> <value2>)
+   Attribute is substituted with value1 when no subst is applied and with
+   value2 in the opposite case.
+   Attributes are added to SUBST_ATTRS_TABLE.
+   In case the iterator is encountered for the first time, it's added to
+   SUBST_ITERS_TABLE.  Also, implicit define_attr is generated.  */
+
+static void
+read_subst_mapping (htab_t subst_iters_table, htab_t subst_attrs_table,
+		    rtx *queue)
+{
+  struct mapping *m;
+  struct map_value **end_ptr;
+  const char *attr_operands[4];
+  rtx * queue_elem = queue;
+  int i;
+
+  for (i = 0; i < 4; i++)
+    attr_operands[i] = read_string (false);
+
+  add_define_subst_attr (attr_operands, queue_elem);
+
+  bind_subst_iter_and_attr (attr_operands[1], attr_operands[0]);
+
+  m = (struct mapping *) htab_find (substs.iterators, &attr_operands[1]);
+  if (!m)
+    {
+      m = add_mapping (&substs, subst_iters_table, attr_operands[1]);
+      end_ptr = &m->values;
+      end_ptr = add_map_value (end_ptr, 1, "");
+      end_ptr = add_map_value (end_ptr, 2, "");
+
+      /* Add element to the queue.  */
+      XEXP (*queue, 1) = rtx_alloc (EXPR_LIST);
+      queue_elem = &XEXP (*queue, 1);
+
+      add_define_attr_for_define_subst (attr_operands[1], queue_elem);
+    }
+
+  m = add_mapping (&substs, subst_attrs_table, attr_operands[0]);
+  end_ptr = &m->values;
+  end_ptr = add_map_value (end_ptr, 1, attr_operands[2]);
+  end_ptr = add_map_value (end_ptr, 2, attr_operands[3]);
+}
+
 /* Check newly-created code iterator ITERATOR to see whether every code has the
    same format.  */
 
@@ -856,6 +1079,15 @@ read_rtx (const char *rtx_name, rtx *x)
       read_mapping (&ints, ints.iterators);
       return false;
     }
+  if (strcmp (rtx_name, "define_subst_attr") == 0)
+    {
+      read_subst_mapping (substs.iterators, substs.attrs, &queue_head);
+      *x = queue_head;
+
+      /* READ_SUBST_MAPPING could generate a new DEFINE_ATTR.  Return
+	 TRUE to process it.  */
+      return true;
+    }
 
   apply_iterators (read_rtx_code (rtx_name), &queue_head);
   VEC_truncate (iterator_use, iterator_uses, 0);
@@ -874,12 +1106,15 @@ read_rtx_code (const char *code_name)
 {
   int i;
   RTX_CODE code;
-  struct mapping *iterator;
+  struct mapping *iterator, *m;
   const char *format_ptr;
   struct md_name name;
   rtx return_rtx;
   int c;
   HOST_WIDE_INT tmp_wide;
+  char *str;
+  char *start, *end, *ptr;
+  char tmpstr[256];
 
   /* Linked list structure for making RTXs: */
   struct rtx_list
@@ -1024,6 +1259,34 @@ read_rtx_code (const char *code_name)
 	      stringbuf = XOBFINISH (&string_obstack, char *);
 	    }
 
+	  /* Find attr-names in the string.  */
+	  ptr = &tmpstr[0];
+	  end = stringbuf;
+	  while ((start = strchr (end, '<')) && (end = strchr (start, '>')))
+	    {
+	      if ((end - start - 1 > 0)
+		  && (end - start - 1 < (int)sizeof (tmpstr)))
+		{
+		  strncpy (tmpstr, start+1, end-start-1);
+		  tmpstr[end-start-1] = 0;
+		  end++;
+		}
+	      else
+		break;
+	      m = (struct mapping *) htab_find (substs.attrs, &ptr);
+	      if (m != 0)
+		{
+		  /* Here we should find linked subst-iter.  */
+		  str = find_subst_iter_by_attr (ptr);
+		  if (str)
+		    m = (struct mapping *) htab_find (substs.iterators, &str);
+		  else
+		    m = 0;
+		}
+	      if (m != 0)
+		record_iterator_use (m, return_rtx);
+	    }
+
 	  if (star_if_braced)
 	    XTMPL (return_rtx, i) = stringbuf;
 	  else
diff --git a/gcc/rtl.def b/gcc/rtl.def
index 32098af..6948bfe 100644
--- a/gcc/rtl.def
+++ b/gcc/rtl.def
@@ -906,8 +906,9 @@ DEF_RTL_EXPR(DEFINE_PEEPHOLE2, "define_peephole2", "EsES", RTX_EXTRA)
 	This might, for example, create some RTX's and store them in
 	elements of `recog_data.operand' for use by the vector of
 	insn-patterns.
-	(`operands' is an alias here for `recog_data.operand').  */
-DEF_RTL_EXPR(DEFINE_EXPAND, "define_expand", "sEss", RTX_EXTRA)
+	(`operands' is an alias here for `recog_data.operand').
+   5th: optionally, a vector of attributes for this expand.  */
+DEF_RTL_EXPR(DEFINE_EXPAND, "define_expand", "sEssV", RTX_EXTRA)
 
 /* Define a requirement for delay slots.
    1st operand: Condition involving insn attributes that, if true,
@@ -1280,6 +1281,8 @@ DEF_RTL_EXPR (ATTR_FLAG, "attr_flag", "s", RTX_EXTRA)
    true, the second operand will be used as the value of the conditional.  */
 DEF_RTL_EXPR(COND, "cond", "Ee", RTX_EXTRA)
 
+DEF_RTL_EXPR(DEFINE_SUBST, "define_subst", "sEsE", RTX_EXTRA)
+DEF_RTL_EXPR(DEFINE_SUBST_ATTR, "define_subst_attr", "ssss", RTX_EXTRA)
 #endif /* GENERATOR_FILE */
 
 /*

Re: [PATCH, generic] New RTL primitive: `define_subst'

[Michael Zolotukhin]

>> Yeah, one or other way to being able to debug what exactly has been
>> performed during the iterator expansion is certainly desirable for the
>> future.
> We actually have internal machinery for dumping MDs with expanded
> iterators and substs, but this looks really kinda hack now.
> We're going to submit it as subsequent patch after that one
> is checked in (there'll be no change in `define_subst' interface) and some
> discussion about necessary infrastructure changes is performed.

It's fairly easy to dump MD-file with expanded iterators and subst -
we could do it in any gen*-utility with a small piece of code. Like
this:

+void
+print_rtl_list (struct queue_elem **q)
+{
+  struct queue_elem *elem;
+  for (elem = *q; elem ; elem = elem->next)
+    debug_rtx (elem->data);
+}
...
+      print_rtl_list (&define_attr_queue);
+      print_rtl_list (&define_pred_queue);
+      print_rtl_list (&define_insn_queue);
+      print_rtl_list (&define_cond_exec_queue);
+      print_rtl_list (&define_subst_queue);
+      print_rtl_list (&other_queue);

Currently I just  don't know what way should be used to invoke it - in
our development we use an environment variable as a trigger for this,
but this is a real hack:
+  if (getenv ("__DUMP_RTL_LIST"))
+    {
+      print_rtl_list (&define_attr_queue);
...
+    }

I don't believe this way is appropriate to be in the trunk - so, could
you please advise how it should be done? Maybe we should introduce a
new gen-utility which should be used only for dumping md-files and add
a new target into makefile to invoke it, or should we add a command
line option to existing utilities?

--
Thanks, Michael




-- 
---
Best regards,
Michael V. Zolotukhin,
Software Engineer
Intel Corporation.

Re: [PATCH, generic] New RTL primitive: `define_subst'

[Richard Henderson]

On 11/16/2012 03:21 AM, Michael Zolotukhin wrote:
> Maybe we should introduce a
> new gen-utility which should be used only for dumping md-files and add
> a new target into makefile to invoke it,

This is exactly what I suggested somewhere up-thread.


r~

Re: [PATCH, generic] New RTL primitive: `define_subst'

[Hans-Peter Nilsson]

On Wed, 14 Nov 2012, Jakub Jelinek wrote:
> > Which brings us to the question of what to do with the patch for 4.8.
> > It's true that you made the deadline for stage1 closure.  But there will
> > be no users of this feature, so it begs the question of why we should
> > apply it now.  Have you a convincing reason?
> >
> > RM's do you have an opinion here?
>
> I'm not against it going in now, it shouldn't be too risky and will
> allow people to start experimenting with it sooner.

Another point in favor of applying it within 4.8 is that it
makes for easier backport of those bug fixes that are simplified
by use of define_subst.

brgds, H-P

Re: [PATCH, generic] New RTL primitive: `define_subst'

[Richard Henderson]

On 11/15/2012 05:50 AM, Kirill Yukhin wrote:
> Hi guys,
> thanks for review. Comments along with updated patch are below.

Version 6 is now ok.  Please apply.


r~

Re: [PATCH, generic] New RTL primitive: `define_subst'

[Kirill Yukhin]

Hello guys,
I've checked that in:
http://gcc.gnu.org/ml/gcc-cvs/2012-11/msg00565.html with tiny obvious
fix
Thanks a lot for your inputs and comments!

Thanks, K

On Sat, Nov 17, 2012 at 10:50 PM, Richard Henderson <rth@redhat.com> wrote:
> On 11/15/2012 05:50 AM, Kirill Yukhin wrote:
>> Hi guys,
>> thanks for review. Comments along with updated patch are below.
>
> Version 6 is now ok.  Please apply.
>
>
> r~