gas/config/xtensa-relax.c

   1 /* Table of relaxations for Xtensa assembly.
   2    Copyright (C) 2003-2022 Free Software Foundation, Inc.
   3
   4    This file is part of GAS, the GNU Assembler.
   5
   6    GAS is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 3, or (at your option)
   9    any later version.
  10
  11    GAS is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with GAS; see the file COPYING.  If not, write to
  18    the Free Software Foundation, 51 Franklin Street - Fifth Floor, Boston,
  19    MA 02110-1301, USA.  */
  20
  21 /* This file contains the code for generating runtime data structures
  22    for relaxation pattern matching from statically specified strings.
  23    Each action contains an instruction pattern to match and
  24    preconditions for the match as well as an expansion if the pattern
  25    matches.  The preconditions can specify that two operands are the
  26    same or an operand is a specific constant or register.  The expansion
  27    uses the bound variables from the pattern to specify that specific
  28    operands from the pattern should be used in the result.
  29
  30    The code determines whether the condition applies to a constant or
  31    a register depending on the type of the operand.  You may get
  32    unexpected results if you don't match the rule against the operand
  33    type correctly.
  34
  35    The patterns match a language like:
  36
  37    INSN_PATTERN ::= INSN_TEMPL ( '|' PRECOND )* ( '?' OPTIONPRED )*
  38    INSN_TEMPL   ::= OPCODE ' ' [ OPERAND (',' OPERAND)* ]
  39    OPCODE       ::=  id
  40    OPERAND      ::= CONSTANT | VARIABLE | SPECIALFN '(' VARIABLE ')'
  41    SPECIALFN    ::= 'HI24S' | 'F32MINUS' | 'LOW8'
  42                     | 'HI16' | 'LOW16'
  43    VARIABLE     ::= '%' id
  44    PRECOND      ::= OPERAND CMPOP OPERAND
  45    CMPOP        ::= '==' | '!='
  46    OPTIONPRED   ::= OPTIONNAME ('+' OPTIONNAME)
  47    OPTIONNAME   ::= '"' id '"'
  48
  49    The replacement language
  50    INSN_REPL      ::= INSN_LABEL_LIT ( ';' INSN_LABEL_LIT )*
  51    INSN_LABEL_LIT ::= INSN_TEMPL
  52                       | 'LABEL'
  53                       | 'LITERAL' VARIABLE
  54
  55    The operands in a PRECOND must be constants or variables bound by
  56    the INSN_PATTERN.
  57
  58    The configuration options define a predicate on the availability of
  59    options which must be TRUE for this rule to be valid.  Examples are
  60    requiring "density" for replacements with density instructions,
  61    requiring "const16" for replacements that require const16
  62    instructions, etc.  The names are interpreted by the assembler to a
  63    truth value for a particular frag.
  64
  65    The operands in the INSN_REPL must be constants, variables bound in
  66    the associated INSN_PATTERN, special variables that are bound in
  67    the INSN_REPL by LABEL or LITERAL definitions, or special value
  68    manipulation functions.
  69
  70    A simple example of a replacement pattern:
  71    {"movi.n %as,%imm", "movi %as,%imm"} would convert the narrow
  72    movi.n instruction to the wide movi instruction.
  73
  74    A more complex example of a branch around:
  75    {"beqz %as,%label", "bnez %as,%LABEL;j %label;LABEL"}
  76    would convert a branch to a negated branch to the following instruction
  77    with a jump to the original label.
  78
  79    An Xtensa-specific example that generates a literal:
  80    {"movi %at,%imm", "LITERAL %imm; l32r %at,%LITERAL"}
  81    will convert a movi instruction to an l32r of a literal
  82    literal defined in the literal pool.
  83
  84    Even more complex is a conversion of a load with immediate offset
  85    to a load of a freshly generated literal, an explicit add and
  86    a load with 0 offset.  This transformation is only valid, though
  87    when the first and second operands are not the same as specified
  88    by the "| %at!=%as" precondition clause.
  89    {"l32i %at,%as,%imm | %at!=%as",
  90    "LITERAL %imm; l32r %at,%LITERAL; add %at,%at,%as; l32i %at,%at,0"}  */
  91
  92 #include "as.h"
  93 #include "xtensa-isa.h"
  94 #include "xtensa-relax.h"
  95 #include <stddef.h>
  96 #include "xtensa-dynconfig.h"
  97
  98 /* Imported from bfd.  */
  99 extern xtensa_isa xtensa_default_isa;
 100
 101 /* The opname_list is a small list of names that we use for opcode and
 102    operand variable names to simplify ownership of these commonly used
 103    strings.  Strings entered in the table can be compared by pointer
 104    equality.  */
 105
 106 typedef struct opname_list_struct opname_list;
 107 typedef opname_list opname_e;
 108
 109 struct opname_list_struct
 110 {
 111   char *opname;
 112   opname_list *next;
 113 };
 114
 115 static opname_list *local_opnames = NULL;
 116
 117
 118 /* The "opname_map" and its element structure "opname_map_e" are used
 119    for binding an operand number to a name or a constant.  */
 120
 121 typedef struct opname_map_e_struct opname_map_e;
 122 typedef struct opname_map_struct opname_map;
 123
 124 struct opname_map_e_struct
 125 {
 126   const char *operand_name;     /* If null, then use constant_value.  */
 127   int operand_num;
 128   unsigned constant_value;
 129   opname_map_e *next;
 130 };
 131
 132 struct opname_map_struct
 133 {
 134   opname_map_e *head;
 135   opname_map_e **tail;
 136 };
 137
 138 /* The "precond_list" and its element structure "precond_e" represents
 139    explicit preconditions comparing operand variables and constants.
 140    In the "precond_e" structure, a variable is identified by the name
 141    in the "opname" field.   If that field is NULL, then the operand
 142    is the constant in field "opval".  */
 143
 144 typedef struct precond_e_struct precond_e;
 145 typedef struct precond_list_struct precond_list;
 146
 147 struct precond_e_struct
 148 {
 149   const char *opname1;
 150   unsigned opval1;
 151   CmpOp cmpop;
 152   const char *opname2;
 153   unsigned opval2;
 154   precond_e *next;
 155 };
 156
 157 struct precond_list_struct
 158 {
 159   precond_e *head;
 160   precond_e **tail;
 161 };
 162
 163
 164 /* The insn_templ represents the INSN_TEMPL instruction template.  It
 165    is an opcode name with a list of operands.  These are used for
 166    instruction patterns and replacement patterns.  */
 167
 168 typedef struct insn_templ_struct insn_templ;
 169 struct insn_templ_struct
 170 {
 171   const char *opcode_name;
 172   opname_map operand_map;
 173 };
 174
 175
 176 /* The insn_pattern represents an INSN_PATTERN instruction pattern.
 177    It is an instruction template with preconditions that specify when
 178    it actually matches a given instruction.  */
 179
 180 typedef struct insn_pattern_struct insn_pattern;
 181 struct insn_pattern_struct
 182 {
 183   insn_templ t;
 184   precond_list preconds;
 185   ReqOptionList *options;
 186 };
 187
 188
 189 /* The "insn_repl" and associated element structure "insn_repl_e"
 190    instruction replacement list is a list of
 191    instructions/LITERALS/LABELS with constant operands or operands
 192    with names bound to the operand names in the associated pattern.  */
 193
 194 typedef struct insn_repl_e_struct insn_repl_e;
 195 struct insn_repl_e_struct
 196 {
 197   insn_templ t;
 198   insn_repl_e *next;
 199 };
 200
 201 typedef struct insn_repl_struct insn_repl;
 202 struct insn_repl_struct
 203 {
 204   insn_repl_e *head;
 205   insn_repl_e **tail;
 206 };
 207
 208
 209 /* The split_rec is a vector of allocated char * pointers.  */
 210
 211 typedef struct split_rec_struct split_rec;
 212 struct split_rec_struct
 213 {
 214   char **vec;
 215   int count;
 216 };
 217
 218 /* The "string_pattern_pair" is a set of pairs containing instruction
 219    patterns and replacement strings.  */
 220
 221 typedef struct string_pattern_pair_struct string_pattern_pair;
 222 struct string_pattern_pair_struct
 223 {
 224   const char *pattern;
 225   const char *replacement;
 226 };
 227
 228 \f
 229 /* The widen_spec_list is a list of valid substitutions that generate
 230    wider representations.  These are generally used to specify
 231    replacements for instructions whose immediates do not fit their
 232    encodings.  A valid transition may require multiple steps of
 233    one-to-one instruction replacements with a final multiple
 234    instruction replacement.  As an example, here are the transitions
 235    required to replace an 'addi.n' with an 'addi', 'addmi'.
 236
 237      addi.n a4, 0x1010
 238      => addi a4, 0x1010
 239      => addmi a4, 0x1010
 240      => addmi a4, 0x1000, addi a4, 0x10.
 241
 242    See the comments in xg_assembly_relax for some important details
 243    regarding how these chains must be built.  */
 244
 245 static string_pattern_pair widen_spec_list[] =
 246 {
 247   {"add.n %ar,%as,%at ? IsaUseDensityInstruction", "add %ar,%as,%at"},
 248   {"addi.n %ar,%as,%imm ? IsaUseDensityInstruction", "addi %ar,%as,%imm"},
 249   {"beqz.n %as,%label ? IsaUseDensityInstruction", "beqz %as,%label"},
 250   {"bnez.n %as,%label ? IsaUseDensityInstruction", "bnez %as,%label"},
 251   {"l32i.n %at,%as,%imm ? IsaUseDensityInstruction", "l32i %at,%as,%imm"},
 252   {"mov.n %at,%as ? IsaUseDensityInstruction", "or %at,%as,%as"},
 253   {"movi.n %as,%imm ? IsaUseDensityInstruction", "movi %as,%imm"},
 254   {"nop.n ? IsaUseDensityInstruction ? realnop", "nop"},
 255   {"nop.n ? IsaUseDensityInstruction ? no-realnop", "or 1,1,1"},
 256   {"ret.n %as ? IsaUseDensityInstruction", "ret %as"},
 257   {"retw.n %as ? IsaUseDensityInstruction", "retw %as"},
 258   {"s32i.n %at,%as,%imm ? IsaUseDensityInstruction", "s32i %at,%as,%imm"},
 259   {"srli %at,%as,%imm", "extui %at,%as,%imm,F32MINUS(%imm)"},
 260   {"slli %ar,%as,0", "or %ar,%as,%as"},
 261
 262   /* Widening with literals or const16.  */
 263   {"movi %at,%imm ? IsaUseL32R ",
 264    "LITERAL %imm; l32r %at,%LITERAL"},
 265   {"movi %at,%imm ? IsaUseConst16",
 266    "const16 %at,HI16U(%imm); const16 %at,LOW16U(%imm)"},
 267
 268   {"addi %ar,%as,%imm", "addmi %ar,%as,%imm"},
 269   /* LOW8 is the low 8 bits of the Immed
 270      MID8S is the middle 8 bits of the Immed */
 271   {"addmi %ar,%as,%imm", "addmi %ar,%as,HI24S(%imm); addi %ar,%ar,LOW8(%imm)"},
 272
 273   /* In the end convert to either an l32r or const16.  */
 274   {"addmi %ar,%as,%imm | %ar!=%as ? IsaUseL32R",
 275    "LITERAL %imm; l32r %ar,%LITERAL; add %ar,%as,%ar"},
 276   {"addmi %ar,%as,%imm | %ar!=%as ? IsaUseConst16",
 277    "const16 %ar,HI16U(%imm); const16 %ar,LOW16U(%imm); add %ar,%as,%ar"},
 278
 279   /* Widening the load instructions with too-large immediates */
 280   {"l8ui %at,%as,%imm | %at!=%as ? IsaUseL32R",
 281    "LITERAL %imm; l32r %at,%LITERAL; add %at,%at,%as; l8ui %at,%at,0"},
 282   {"l16si %at,%as,%imm | %at!=%as ? IsaUseL32R",
 283    "LITERAL %imm; l32r %at,%LITERAL; add %at,%at,%as; l16si %at,%at,0"},
 284   {"l16ui %at,%as,%imm | %at!=%as ? IsaUseL32R",
 285    "LITERAL %imm; l32r %at,%LITERAL; add %at,%at,%as; l16ui %at,%at,0"},
 286   {"l32i %at,%as,%imm | %at!=%as ? IsaUseL32R",
 287    "LITERAL %imm; l32r %at,%LITERAL; add %at,%at,%as; l32i %at,%at,0"},
 288
 289   /* Widening load instructions with const16s.  */
 290   {"l8ui %at,%as,%imm | %at!=%as ? IsaUseConst16",
 291    "const16 %at,HI16U(%imm); const16 %at,LOW16U(%imm); add %at,%at,%as; l8ui %at,%at,0"},
 292   {"l16si %at,%as,%imm | %at!=%as ? IsaUseConst16",
 293    "const16 %at,HI16U(%imm); const16 %at,LOW16U(%imm); add %at,%at,%as; l16si %at,%at,0"},
 294   {"l16ui %at,%as,%imm | %at!=%as ? IsaUseConst16",
 295    "const16 %at,HI16U(%imm); const16 %at,LOW16U(%imm); add %at,%at,%as; l16ui %at,%at,0"},
 296   {"l32i %at,%as,%imm | %at!=%as ? IsaUseConst16",
 297    "const16 %at,HI16U(%imm); const16 %at,LOW16U(%imm); add %at,%at,%as; l32i %at,%at,0"},
 298
 299   /* Widening loops with literals.  */
 300   {"loop %as,%label | %as!=1 ? IsaUseLoops ? IsaUseL32R",
 301    "loop %as,%LABEL;"
 302    "rsr.lend    %as;"           /* LEND */
 303    "wsr.lbeg    %as;"           /* LBEG */
 304    "LITERAL     %label;"
 305    "l32r        %as, %LITERAL;"
 306    "nop;"
 307    "wsr.lend    %as;"
 308    "isync;"
 309    "rsr.lcount    %as;"         /* LCOUNT */
 310    "addi    %as, %as, 1;"
 311    "LABEL"},
 312   {"loopgtz %as,%label | %as!=1 ? IsaUseLoops ? IsaUseL32R",
 313    "beqz    %as,%label;"
 314    "bltz    %as,%label;"
 315    "loopgtz %as,%LABEL;"
 316    "rsr.lend    %as;"           /* LEND */
 317    "wsr.lbeg    %as;"           /* LBEG */
 318    "LITERAL     %label;"
 319    "l32r        %as, %LITERAL;"
 320    "nop;"
 321    "wsr.lend    %as;"
 322    "isync;"
 323    "rsr.lcount    %as;"         /* LCOUNT */
 324    "addi    %as, %as, 1;"
 325    "LABEL"},
 326   {"loopnez %as,%label | %as!=1 ? IsaUseLoops ? IsaUseL32R",
 327    "beqz     %as,%label;"
 328    "loopnez %as,%LABEL;"
 329    "rsr.lend    %as;"           /* LEND */
 330    "wsr.lbeg    %as;"           /* LBEG */
 331    "LITERAL     %label;"
 332    "l32r        %as, %LITERAL;"
 333    "nop;"
 334    "wsr.lend    %as;"
 335    "isync;"
 336    "rsr.lcount    %as;"         /* LCOUNT */
 337    "addi    %as, %as, 1;"
 338    "LABEL"},
 339
 340   /* Widening loops with const16.  */
 341   {"loop %as,%label | %as!=1 ? IsaUseLoops ? IsaUseConst16",
 342    "loop %as,%LABEL;"
 343    "rsr.lend    %as;"           /* LEND */
 344    "wsr.lbeg    %as;"           /* LBEG */
 345    "const16     %as,HI16U(%label);"
 346    "const16     %as,LOW16U(%label);"
 347    "wsr.lend    %as;"
 348    "isync;"
 349    "rsr.lcount    %as;"         /* LCOUNT */
 350    "addi    %as, %as, 1;"
 351    "LABEL"},
 352   {"loopgtz %as,%label | %as!=1 ? IsaUseLoops ? IsaUseConst16",
 353    "beqz    %as,%label;"
 354    "bltz    %as,%label;"
 355    "loopgtz %as,%LABEL;"
 356    "rsr.lend    %as;"           /* LEND */
 357    "wsr.lbeg    %as;"           /* LBEG */
 358    "const16     %as,HI16U(%label);"
 359    "const16     %as,LOW16U(%label);"
 360    "wsr.lend    %as;"
 361    "isync;"
 362    "rsr.lcount    %as;"         /* LCOUNT */
 363    "addi    %as, %as, 1;"
 364    "LABEL"},
 365   {"loopnez %as,%label | %as!=1 ? IsaUseLoops ? IsaUseConst16",
 366    "beqz     %as,%label;"
 367    "loopnez %as,%LABEL;"
 368    "rsr.lend    %as;"           /* LEND */
 369    "wsr.lbeg    %as;"           /* LBEG */
 370    "const16     %as,HI16U(%label);"
 371    "const16     %as,LOW16U(%label);"
 372    "wsr.lend    %as;"
 373    "isync;"
 374    "rsr.lcount    %as;"         /* LCOUNT */
 375    "addi    %as, %as, 1;"
 376    "LABEL"},
 377
 378   /* Relaxing to wide branches.  Order is important here.  With wide
 379      branches, there is more than one correct relaxation for an
 380      out-of-range branch.  Put the wide branch relaxations first in the
 381      table since they are more efficient than the branch-around
 382      relaxations.  */
 383
 384   {"beqz %as,%label ? IsaUseWideBranches", "WIDE.beqz %as,%label"},
 385   {"bnez %as,%label ? IsaUseWideBranches", "WIDE.bnez %as,%label"},
 386   {"bgez %as,%label ? IsaUseWideBranches", "WIDE.bgez %as,%label"},
 387   {"bltz %as,%label ? IsaUseWideBranches", "WIDE.bltz %as,%label"},
 388   {"beqi %as,%imm,%label ? IsaUseWideBranches", "WIDE.beqi %as,%imm,%label"},
 389   {"bnei %as,%imm,%label ? IsaUseWideBranches", "WIDE.bnei %as,%imm,%label"},
 390   {"bgei %as,%imm,%label ? IsaUseWideBranches", "WIDE.bgei %as,%imm,%label"},
 391   {"blti %as,%imm,%label ? IsaUseWideBranches", "WIDE.blti %as,%imm,%label"},
 392   {"bgeui %as,%imm,%label ? IsaUseWideBranches", "WIDE.bgeui %as,%imm,%label"},
 393   {"bltui %as,%imm,%label ? IsaUseWideBranches", "WIDE.bltui %as,%imm,%label"},
 394   {"bbci %as,%imm,%label ? IsaUseWideBranches", "WIDE.bbci %as,%imm,%label"},
 395   {"bbsi %as,%imm,%label ? IsaUseWideBranches", "WIDE.bbsi %as,%imm,%label"},
 396   {"beq %as,%at,%label ? IsaUseWideBranches", "WIDE.beq %as,%at,%label"},
 397   {"bne %as,%at,%label ? IsaUseWideBranches", "WIDE.bne %as,%at,%label"},
 398   {"bge %as,%at,%label ? IsaUseWideBranches", "WIDE.bge %as,%at,%label"},
 399   {"blt %as,%at,%label ? IsaUseWideBranches", "WIDE.blt %as,%at,%label"},
 400   {"bgeu %as,%at,%label ? IsaUseWideBranches", "WIDE.bgeu %as,%at,%label"},
 401   {"bltu %as,%at,%label ? IsaUseWideBranches", "WIDE.bltu %as,%at,%label"},
 402   {"bany %as,%at,%label ? IsaUseWideBranches", "WIDE.bany %as,%at,%label"},
 403   {"bnone %as,%at,%label ? IsaUseWideBranches", "WIDE.bnone %as,%at,%label"},
 404   {"ball %as,%at,%label ? IsaUseWideBranches", "WIDE.ball %as,%at,%label"},
 405   {"bnall %as,%at,%label ? IsaUseWideBranches", "WIDE.bnall %as,%at,%label"},
 406   {"bbc %as,%at,%label ? IsaUseWideBranches", "WIDE.bbc %as,%at,%label"},
 407   {"bbs %as,%at,%label ? IsaUseWideBranches", "WIDE.bbs %as,%at,%label"},
 408
 409   /* Widening branch comparisons eq/ne to zero.  Prefer relaxing to narrow
 410      branches if the density option is available.  */
 411   {"beqz %as,%label ? IsaUseDensityInstruction", "bnez.n %as,%LABEL;j %label;LABEL"},
 412   {"bnez %as,%label ? IsaUseDensityInstruction", "beqz.n %as,%LABEL;j %label;LABEL"},
 413   {"beqz %as,%label", "bnez %as,%LABEL;j %label;LABEL"},
 414   {"bnez %as,%label", "beqz %as,%LABEL;j %label;LABEL"},
 415   {"WIDE.beqz %as,%label ? IsaUseDensityInstruction", "bnez.n %as,%LABEL;j %label;LABEL"},
 416   {"WIDE.bnez %as,%label ? IsaUseDensityInstruction", "beqz.n %as,%LABEL;j %label;LABEL"},
 417   {"WIDE.beqz %as,%label", "bnez %as,%LABEL;j %label;LABEL"},
 418   {"WIDE.bnez %as,%label", "beqz %as,%LABEL;j %label;LABEL"},
 419
 420   /* Widening expect-taken branches.  */
 421   {"beqzt %as,%label ? IsaUsePredictedBranches", "bnez %as,%LABEL;j %label;LABEL"},
 422   {"bnezt %as,%label ? IsaUsePredictedBranches", "beqz %as,%LABEL;j %label;LABEL"},
 423   {"beqt %as,%at,%label ? IsaUsePredictedBranches", "bne %as,%at,%LABEL;j %label;LABEL"},
 424   {"bnet %as,%at,%label ? IsaUsePredictedBranches", "beq %as,%at,%LABEL;j %label;LABEL"},
 425
 426   /* Widening branches from the Xtensa boolean option.  */
 427   {"bt %bs,%label ? IsaUseBooleans", "bf %bs,%LABEL;j %label;LABEL"},
 428   {"bf %bs,%label ? IsaUseBooleans", "bt %bs,%LABEL;j %label;LABEL"},
 429
 430   /* Other branch-around-jump widenings.  */
 431   {"bgez %as,%label", "bltz %as,%LABEL;j %label;LABEL"},
 432   {"bltz %as,%label", "bgez %as,%LABEL;j %label;LABEL"},
 433   {"beqi %as,%imm,%label", "bnei %as,%imm,%LABEL;j %label;LABEL"},
 434   {"bnei %as,%imm,%label", "beqi %as,%imm,%LABEL;j %label;LABEL"},
 435   {"bgei %as,%imm,%label", "blti %as,%imm,%LABEL;j %label;LABEL"},
 436   {"blti %as,%imm,%label", "bgei %as,%imm,%LABEL;j %label;LABEL"},
 437   {"bgeui %as,%imm,%label", "bltui %as,%imm,%LABEL;j %label;LABEL"},
 438   {"bltui %as,%imm,%label", "bgeui %as,%imm,%LABEL;j %label;LABEL"},
 439   {"bbci %as,%imm,%label", "bbsi %as,%imm,%LABEL;j %label;LABEL"},
 440   {"bbsi %as,%imm,%label", "bbci %as,%imm,%LABEL;j %label;LABEL"},
 441   {"beq %as,%at,%label", "bne %as,%at,%LABEL;j %label;LABEL"},
 442   {"bne %as,%at,%label", "beq %as,%at,%LABEL;j %label;LABEL"},
 443   {"bge %as,%at,%label", "blt %as,%at,%LABEL;j %label;LABEL"},
 444   {"blt %as,%at,%label", "bge %as,%at,%LABEL;j %label;LABEL"},
 445   {"bgeu %as,%at,%label", "bltu %as,%at,%LABEL;j %label;LABEL"},
 446   {"bltu %as,%at,%label", "bgeu %as,%at,%LABEL;j %label;LABEL"},
 447   {"bany %as,%at,%label", "bnone %as,%at,%LABEL;j %label;LABEL"},
 448   {"bnone %as,%at,%label", "bany %as,%at,%LABEL;j %label;LABEL"},
 449   {"ball %as,%at,%label", "bnall %as,%at,%LABEL;j %label;LABEL"},
 450   {"bnall %as,%at,%label", "ball %as,%at,%LABEL;j %label;LABEL"},
 451   {"bbc %as,%at,%label", "bbs %as,%at,%LABEL;j %label;LABEL"},
 452   {"bbs %as,%at,%label", "bbc %as,%at,%LABEL;j %label;LABEL"},
 453
 454   {"WIDE.bgez %as,%label", "bltz %as,%LABEL;j %label;LABEL"},
 455   {"WIDE.bltz %as,%label", "bgez %as,%LABEL;j %label;LABEL"},
 456   {"WIDE.beqi %as,%imm,%label", "bnei %as,%imm,%LABEL;j %label;LABEL"},
 457   {"WIDE.bnei %as,%imm,%label", "beqi %as,%imm,%LABEL;j %label;LABEL"},
 458   {"WIDE.bgei %as,%imm,%label", "blti %as,%imm,%LABEL;j %label;LABEL"},
 459   {"WIDE.blti %as,%imm,%label", "bgei %as,%imm,%LABEL;j %label;LABEL"},
 460   {"WIDE.bgeui %as,%imm,%label", "bltui %as,%imm,%LABEL;j %label;LABEL"},
 461   {"WIDE.bltui %as,%imm,%label", "bgeui %as,%imm,%LABEL;j %label;LABEL"},
 462   {"WIDE.bbci %as,%imm,%label", "bbsi %as,%imm,%LABEL;j %label;LABEL"},
 463   {"WIDE.bbsi %as,%imm,%label", "bbci %as,%imm,%LABEL;j %label;LABEL"},
 464   {"WIDE.beq %as,%at,%label", "bne %as,%at,%LABEL;j %label;LABEL"},
 465   {"WIDE.bne %as,%at,%label", "beq %as,%at,%LABEL;j %label;LABEL"},
 466   {"WIDE.bge %as,%at,%label", "blt %as,%at,%LABEL;j %label;LABEL"},
 467   {"WIDE.blt %as,%at,%label", "bge %as,%at,%LABEL;j %label;LABEL"},
 468   {"WIDE.bgeu %as,%at,%label", "bltu %as,%at,%LABEL;j %label;LABEL"},
 469   {"WIDE.bltu %as,%at,%label", "bgeu %as,%at,%LABEL;j %label;LABEL"},
 470   {"WIDE.bany %as,%at,%label", "bnone %as,%at,%LABEL;j %label;LABEL"},
 471   {"WIDE.bnone %as,%at,%label", "bany %as,%at,%LABEL;j %label;LABEL"},
 472   {"WIDE.ball %as,%at,%label", "bnall %as,%at,%LABEL;j %label;LABEL"},
 473   {"WIDE.bnall %as,%at,%label", "ball %as,%at,%LABEL;j %label;LABEL"},
 474   {"WIDE.bbc %as,%at,%label", "bbs %as,%at,%LABEL;j %label;LABEL"},
 475   {"WIDE.bbs %as,%at,%label", "bbc %as,%at,%LABEL;j %label;LABEL"},
 476
 477   /* Expanding calls with literals.  */
 478   {"call0 %label,%ar0 ? IsaUseL32R",
 479    "LITERAL %label; l32r a0,%LITERAL; callx0 a0,%ar0"},
 480   {"call4 %label,%ar4 ? IsaUseL32R",
 481    "LITERAL %label; l32r a4,%LITERAL; callx4 a4,%ar4"},
 482   {"call8 %label,%ar8 ? IsaUseL32R",
 483    "LITERAL %label; l32r a8,%LITERAL; callx8 a8,%ar8"},
 484   {"call12 %label,%ar12 ? IsaUseL32R",
 485    "LITERAL %label; l32r a12,%LITERAL; callx12 a12,%ar12"},
 486
 487   /* Expanding calls with const16.  */
 488   {"call0 %label,%ar0 ? IsaUseConst16",
 489    "const16 a0,HI16U(%label); const16 a0,LOW16U(%label); callx0 a0,%ar0"},
 490   {"call4 %label,%ar4 ? IsaUseConst16",
 491    "const16 a4,HI16U(%label); const16 a4,LOW16U(%label); callx4 a4,%ar4"},
 492   {"call8 %label,%ar8 ? IsaUseConst16",
 493    "const16 a8,HI16U(%label); const16 a8,LOW16U(%label); callx8 a8,%ar8"},
 494   {"call12 %label,%ar12 ? IsaUseConst16",
 495    "const16 a12,HI16U(%label); const16 a12,LOW16U(%label); callx12 a12,%ar12"},
 496
 497   /* Expanding j.l with literals.  */
 498   {"j %label ? FREEREG ? IsaUseL32R",
 499    "LITERAL %label; l32r FREEREG,%LITERAL; jx FREEREG"},
 500   /* Expanding j.l with const16.  */
 501   {"j %label ? FREEREG ? IsaUseConst16",
 502    "const16 FREEREG,HI16U(%label); const16 FREEREG,LOW16U(%label); jx FREEREG"},
 503 };
 504
 505 #define WIDEN_COUNT (sizeof (widen_spec_list) / sizeof (string_pattern_pair))
 506
 507
 508 /* The simplify_spec_list specifies simplifying transformations that
 509    will reduce the instruction width or otherwise simplify an
 510    instruction.  These are usually applied before relaxation in the
 511    assembler.  It is always legal to simplify.  Even for "addi as, 0",
 512    the "addi.n as, 0" will eventually be widened back to an "addi 0"
 513    after the widening table is applied.  Note: The usage of this table
 514    has changed somewhat so that it is entirely specific to "narrowing"
 515    instructions to use the density option.  This table is not used at
 516    all when the density option is not available.  */
 517
 518 string_pattern_pair simplify_spec_list[] =
 519 {
 520   {"add %ar,%as,%at ? IsaUseDensityInstruction", "add.n %ar,%as,%at"},
 521   {"addi.n %ar,%as,0 ? IsaUseDensityInstruction", "mov.n %ar,%as"},
 522   {"addi %ar,%as,0 ? IsaUseDensityInstruction", "mov.n %ar,%as"},
 523   {"addi %ar,%as,%imm ? IsaUseDensityInstruction", "addi.n %ar,%as,%imm"},
 524   {"addmi %ar,%as,%imm ? IsaUseDensityInstruction", "addi.n %ar,%as,%imm"},
 525   {"beqz %as,%label ? IsaUseDensityInstruction", "beqz.n %as,%label"},
 526   {"bnez %as,%label ? IsaUseDensityInstruction", "bnez.n %as,%label"},
 527   {"l32i %at,%as,%imm ? IsaUseDensityInstruction", "l32i.n %at,%as,%imm"},
 528   {"movi %as,%imm ? IsaUseDensityInstruction", "movi.n %as,%imm"},
 529   {"nop ? realnop ? IsaUseDensityInstruction", "nop.n"},
 530   {"or %ar,%as,%at | %ar==%as | %as==%at ? IsaUseDensityInstruction", "nop.n"},
 531   {"or %ar,%as,%at | %ar!=%as | %as==%at ? IsaUseDensityInstruction", "mov.n %ar,%as"},
 532   {"ret %as ? IsaUseDensityInstruction", "ret.n %as"},
 533   {"retw %as ? IsaUseDensityInstruction", "retw.n %as"},
 534   {"s32i %at,%as,%imm ? IsaUseDensityInstruction", "s32i.n %at,%as,%imm"},
 535   {"slli %ar,%as,0 ? IsaUseDensityInstruction", "mov.n %ar,%as"}
 536 };
 537
 538 #define SIMPLIFY_COUNT \
 539   (sizeof (simplify_spec_list) / sizeof (string_pattern_pair))
 540
 541 \f
 542 /* Externally visible functions.  */
 543
 544 extern bool xg_has_userdef_op_fn (OpType);
 545 extern long xg_apply_userdef_op_fn (OpType, long);
 546
 547
 548 static void
 549 append_transition (TransitionTable *tt,
 550                    xtensa_opcode opcode,
 551                    TransitionRule *t,
 552                    transition_cmp_fn cmp)
 553 {
 554   TransitionList *tl = XNEW (TransitionList);
 555   TransitionList *prev;
 556   TransitionList **t_p;
 557   gas_assert (tt != NULL);
 558   gas_assert (opcode < tt->num_opcodes);
 559
 560   prev = tt->table[opcode];
 561   tl->rule = t;
 562   tl->next = NULL;
 563   if (prev == NULL)
 564     {
 565       tt->table[opcode] = tl;
 566       return;
 567     }
 568
 569   for (t_p = &tt->table[opcode]; (*t_p) != NULL; t_p = &(*t_p)->next)
 570     {
 571       if (cmp && cmp (t, (*t_p)->rule) < 0)
 572         {
 573           /* Insert it here.  */
 574           tl->next = *t_p;
 575           *t_p = tl;
 576           return;
 577         }
 578     }
 579   (*t_p) = tl;
 580 }
 581
 582
 583 static void
 584 append_condition (TransitionRule *tr, Precondition *cond)
 585 {
 586   PreconditionList *pl = XNEW (PreconditionList);
 587   PreconditionList *prev = tr->conditions;
 588   PreconditionList *nxt;
 589
 590   pl->precond = cond;
 591   pl->next = NULL;
 592   if (prev == NULL)
 593     {
 594       tr->conditions = pl;
 595       return;
 596     }
 597   nxt = prev->next;
 598   while (nxt != NULL)
 599     {
 600       prev = nxt;
 601       nxt = nxt->next;
 602     }
 603   prev->next = pl;
 604 }
 605
 606
 607 static void
 608 append_value_condition (TransitionRule *tr,
 609                         CmpOp cmp,
 610                         unsigned op1,
 611                         unsigned op2)
 612 {
 613   Precondition *cond = XNEW (Precondition);
 614
 615   cond->cmp = cmp;
 616   cond->op_num = op1;
 617   cond->typ = OP_OPERAND;
 618   cond->op_data = op2;
 619   append_condition (tr, cond);
 620 }
 621
 622
 623 static void
 624 append_constant_value_condition (TransitionRule *tr,
 625                                  CmpOp cmp,
 626                                  unsigned op1,
 627                                  unsigned cnst)
 628 {
 629   Precondition *cond = XNEW (Precondition);
 630
 631   cond->cmp = cmp;
 632   cond->op_num = op1;
 633   cond->typ = OP_CONSTANT;
 634   cond->op_data = cnst;
 635   append_condition (tr, cond);
 636 }
 637
 638
 639 static void
 640 append_build_insn (TransitionRule *tr, BuildInstr *bi)
 641 {
 642   BuildInstr *prev = tr->to_instr;
 643   BuildInstr *nxt;
 644
 645   bi->next = NULL;
 646   if (prev == NULL)
 647     {
 648       tr->to_instr = bi;
 649       return;
 650     }
 651   nxt = prev->next;
 652   while (nxt != 0)
 653     {
 654       prev = nxt;
 655       nxt = prev->next;
 656     }
 657   prev->next = bi;
 658 }
 659
 660
 661 static void
 662 append_op (BuildInstr *bi, BuildOp *b_op)
 663 {
 664   BuildOp *prev = bi->ops;
 665   BuildOp *nxt;
 666
 667   if (prev == NULL)
 668     {
 669       bi->ops = b_op;
 670       return;
 671     }
 672   nxt = prev->next;
 673   while (nxt != NULL)
 674     {
 675       prev = nxt;
 676       nxt = nxt->next;
 677     }
 678   prev->next = b_op;
 679 }
 680
 681
 682 static void
 683 append_literal_op (BuildInstr *bi, unsigned op1, unsigned src_op)
 684 {
 685   BuildOp *b_op = XNEW (BuildOp);
 686
 687   b_op->op_num = op1;
 688   b_op->typ = OP_LITERAL;
 689   b_op->op_data = src_op;
 690   b_op->next = NULL;
 691   append_op (bi, b_op);
 692 }
 693
 694
 695 static void
 696 append_label_op (BuildInstr *bi, unsigned op1)
 697 {
 698   BuildOp *b_op = XNEW (BuildOp);
 699
 700   b_op->op_num = op1;
 701   b_op->typ = OP_LABEL;
 702   b_op->op_data = 0;
 703   b_op->next = NULL;
 704   append_op (bi, b_op);
 705 }
 706
 707
 708 static void
 709 append_constant_op (BuildInstr *bi, unsigned op1, unsigned cnst)
 710 {
 711   BuildOp *b_op = XNEW (BuildOp);
 712
 713   b_op->op_num = op1;
 714   b_op->typ = OP_CONSTANT;
 715   b_op->op_data = cnst;
 716   b_op->next = NULL;
 717   append_op (bi, b_op);
 718 }
 719
 720
 721 static void
 722 append_field_op (BuildInstr *bi, unsigned op1, unsigned src_op)
 723 {
 724   BuildOp *b_op = XNEW (BuildOp);
 725
 726   b_op->op_num = op1;
 727   b_op->typ = OP_OPERAND;
 728   b_op->op_data = src_op;
 729   b_op->next = NULL;
 730   append_op (bi, b_op);
 731 }
 732
 733
 734 /* These could be generated but are not currently.  */
 735
 736 static void
 737 append_user_fn_field_op (BuildInstr *bi,
 738                          unsigned op1,
 739                          OpType typ,
 740                          unsigned src_op)
 741 {
 742   BuildOp *b_op = XNEW (BuildOp);
 743
 744   b_op->op_num = op1;
 745   b_op->typ = typ;
 746   b_op->op_data = src_op;
 747   b_op->next = NULL;
 748   append_op (bi, b_op);
 749 }
 750
 751
 752 /* These operand functions are the semantics of user-defined
 753    operand functions.  */
 754
 755 static long
 756 operand_function_HI24S (long a)
 757 {
 758   if (a & 0x80)
 759     return (a & (~0xff)) + 0x100;
 760   else
 761     return (a & (~0xff));
 762 }
 763
 764
 765 static long
 766 operand_function_F32MINUS (long a)
 767 {
 768   return (32 - a);
 769 }
 770
 771
 772 static long
 773 operand_function_LOW8 (long a)
 774 {
 775   if (a & 0x80)
 776     return (a & 0xff) | ~0xff;
 777   else
 778     return (a & 0xff);
 779 }
 780
 781
 782 static long
 783 operand_function_LOW16U (long a)
 784 {
 785   return (a & 0xffff);
 786 }
 787
 788
 789 static long
 790 operand_function_HI16U (long a)
 791 {
 792   unsigned long b = a & 0xffff0000;
 793   return (long) (b >> 16);
 794 }
 795
 796
 797 bool
 798 xg_has_userdef_op_fn (OpType op)
 799 {
 800   switch (op)
 801     {
 802     case OP_OPERAND_F32MINUS:
 803     case OP_OPERAND_LOW8:
 804     case OP_OPERAND_HI24S:
 805     case OP_OPERAND_LOW16U:
 806     case OP_OPERAND_HI16U:
 807       return true;
 808     default:
 809       break;
 810     }
 811   return false;
 812 }
 813
 814
 815 long
 816 xg_apply_userdef_op_fn (OpType op, long a)
 817 {
 818   switch (op)
 819     {
 820     case OP_OPERAND_F32MINUS:
 821       return operand_function_F32MINUS (a);
 822     case OP_OPERAND_LOW8:
 823       return operand_function_LOW8 (a);
 824     case OP_OPERAND_HI24S:
 825       return operand_function_HI24S (a);
 826     case OP_OPERAND_LOW16U:
 827       return operand_function_LOW16U (a);
 828     case OP_OPERAND_HI16U:
 829       return operand_function_HI16U (a);
 830     default:
 831       break;
 832     }
 833   return false;
 834 }
 835
 836
 837 /* Generate a transition table.  */
 838
 839 static const char *
 840 enter_opname_n (const char *name, int len)
 841 {
 842   opname_e *op;
 843
 844   for (op = local_opnames; op != NULL; op = op->next)
 845     {
 846       if (strlen (op->opname) == (unsigned) len
 847           && strncmp (op->opname, name, len) == 0)
 848         return op->opname;
 849     }
 850   op = XNEW (opname_e);
 851   op->opname = xmemdup0 (name, len);
 852   return op->opname;
 853 }
 854
 855
 856 static const char *
 857 enter_opname (const char *name)
 858 {
 859   opname_e *op;
 860
 861   for (op = local_opnames; op != NULL; op = op->next)
 862     {
 863       if (strcmp (op->opname, name) == 0)
 864         return op->opname;
 865     }
 866   op = XNEW (opname_e);
 867   op->opname = xstrdup (name);
 868   return op->opname;
 869 }
 870
 871
 872 static void
 873 init_opname_map (opname_map *m)
 874 {
 875   m->head = NULL;
 876   m->tail = &m->head;
 877 }
 878
 879
 880 static void
 881 clear_opname_map (opname_map *m)
 882 {
 883   opname_map_e *e;
 884
 885   while (m->head != NULL)
 886     {
 887       e = m->head;
 888       m->head = e->next;
 889       free (e);
 890     }
 891   m->tail = &m->head;
 892 }
 893
 894
 895 static bool
 896 same_operand_name (const opname_map_e *m1, const opname_map_e *m2)
 897 {
 898   if (m1->operand_name == NULL || m2->operand_name == NULL)
 899     return false;
 900   return (m1->operand_name == m2->operand_name);
 901 }
 902
 903
 904 static opname_map_e *
 905 get_opmatch (opname_map *map, const char *operand_name)
 906 {
 907   opname_map_e *m;
 908
 909   for (m = map->head; m != NULL; m = m->next)
 910     {
 911       if (strcmp (m->operand_name, operand_name) == 0)
 912         return m;
 913     }
 914   return NULL;
 915 }
 916
 917
 918 static bool
 919 op_is_constant (const opname_map_e *m1)
 920 {
 921   return (m1->operand_name == NULL);
 922 }
 923
 924
 925 static unsigned
 926 op_get_constant (const opname_map_e *m1)
 927 {
 928   gas_assert (m1->operand_name == NULL);
 929   return m1->constant_value;
 930 }
 931
 932
 933 static void
 934 init_precond_list (precond_list *l)
 935 {
 936   l->head = NULL;
 937   l->tail = &l->head;
 938 }
 939
 940
 941 static void
 942 clear_precond_list (precond_list *l)
 943 {
 944   precond_e *e;
 945
 946   while (l->head != NULL)
 947     {
 948       e = l->head;
 949       l->head = e->next;
 950       free (e);
 951     }
 952   l->tail = &l->head;
 953 }
 954
 955
 956 static void
 957 init_insn_templ (insn_templ *t)
 958 {
 959   t->opcode_name = NULL;
 960   init_opname_map (&t->operand_map);
 961 }
 962
 963
 964 static void
 965 clear_insn_templ (insn_templ *t)
 966 {
 967   clear_opname_map (&t->operand_map);
 968 }
 969
 970
 971 static void
 972 init_insn_pattern (insn_pattern *p)
 973 {
 974   init_insn_templ (&p->t);
 975   init_precond_list (&p->preconds);
 976   p->options = NULL;
 977 }
 978
 979
 980 static void
 981 clear_insn_pattern (insn_pattern *p)
 982 {
 983   clear_insn_templ (&p->t);
 984   clear_precond_list (&p->preconds);
 985 }
 986
 987
 988 static void
 989 init_insn_repl (insn_repl *r)
 990 {
 991   r->head = NULL;
 992   r->tail = &r->head;
 993 }
 994
 995
 996 static void
 997 clear_insn_repl (insn_repl *r)
 998 {
 999   insn_repl_e *e;
1000
1001   while (r->head != NULL)
1002     {
1003       e = r->head;
1004       r->head = e->next;
1005       clear_insn_templ (&e->t);
1006     }
1007   r->tail = &r->head;
1008 }
1009
1010
1011 static int
1012 insn_templ_operand_count (const insn_templ *t)
1013 {
1014   int i = 0;
1015   const opname_map_e *op;
1016
1017   for (op = t->operand_map.head; op != NULL; op = op->next, i++)
1018     ;
1019   return i;
1020 }
1021
1022
1023 /* Convert a string to a number.  E.G.: parse_constant("10", &num) */
1024
1025 static bool
1026 parse_constant (const char *in, unsigned *val_p)
1027 {
1028   unsigned val = 0;
1029   const char *p;
1030
1031   if (in == NULL)
1032     return false;
1033   p = in;
1034
1035   while (*p != '\0')
1036     {
1037       if (*p >= '0' && *p <= '9')
1038         val = val * 10 + (*p - '0');
1039       else
1040         return false;
1041       ++p;
1042     }
1043   *val_p = val;
1044   return true;
1045 }
1046
1047
1048 static bool
1049 parse_special_fn (const char *name,
1050                   const char **fn_name_p,
1051                   const char **arg_name_p)
1052 {
1053   const char *p_start;
1054   const char *p_end;
1055
1056   p_start = strchr (name, '(');
1057   if (p_start == NULL)
1058     return false;
1059
1060   p_end = strchr (p_start, ')');
1061
1062   if (p_end == NULL)
1063     return false;
1064
1065   if (p_end[1] != '\0')
1066     return false;
1067
1068   *fn_name_p = enter_opname_n (name, p_start - name);
1069   *arg_name_p = enter_opname_n (p_start + 1, p_end - p_start - 1);
1070   return true;
1071 }
1072
1073
1074 static const char *
1075 skip_white (const char *p)
1076 {
1077   if (p == NULL)
1078     return p;
1079   while (*p == ' ')
1080     ++p;
1081   return p;
1082 }
1083
1084
1085 static void
1086 trim_whitespace (char *in)
1087 {
1088   char *last_white = NULL;
1089   char *p = in;
1090
1091   while (p && *p != '\0')
1092     {
1093       while (*p == ' ')
1094         {
1095           if (last_white == NULL)
1096             last_white = p;
1097           p++;
1098         }
1099       if (*p != '\0')
1100         {
1101           last_white = NULL;
1102           p++;
1103         }
1104     }
1105   if (last_white)
1106     *last_white = '\0';
1107 }
1108
1109
1110 /* Split a string into component strings where "c" is the
1111    delimiter.  Place the result in the split_rec.  */
1112
1113 static void
1114 split_string (split_rec *rec,
1115               const char *in,
1116               char c,
1117               bool elide_whitespace)
1118 {
1119   int cnt = 0;
1120   int i;
1121   const char *p = in;
1122
1123   while (p != NULL && *p != '\0')
1124     {
1125       cnt++;
1126       p = strchr (p, c);
1127       if (p)
1128         p++;
1129     }
1130   rec->count = cnt;
1131   rec->vec = NULL;
1132
1133   if (rec->count == 0)
1134     return;
1135
1136   rec->vec = XNEWVEC (char *, cnt);
1137   for (i = 0; i < cnt; i++)
1138     rec->vec[i] = 0;
1139
1140   p = in;
1141   for (i = 0; i < cnt; i++)
1142     {
1143       const char *q;
1144       int len;
1145
1146       q = p;
1147       if (elide_whitespace)
1148         q = skip_white (q);
1149
1150       p = strchr (q, c);
1151       if (p == NULL)
1152         rec->vec[i] = xstrdup (q);
1153       else
1154         {
1155           len = p - q;
1156           rec->vec[i] = xmemdup0 (q, len);
1157           p++;
1158         }
1159
1160       if (elide_whitespace)
1161         trim_whitespace (rec->vec[i]);
1162     }
1163 }
1164
1165
1166 static void
1167 clear_split_rec (split_rec *rec)
1168 {
1169   int i;
1170
1171   for (i = 0; i < rec->count; i++)
1172     free (rec->vec[i]);
1173
1174   if (rec->count > 0)
1175     free (rec->vec);
1176 }
1177
1178
1179 /* Initialize a split record.  The split record must be initialized
1180    before split_string is called.  */
1181
1182 static void
1183 init_split_rec (split_rec *rec)
1184 {
1185   rec->vec = NULL;
1186   rec->count = 0;
1187 }
1188
1189
1190 /* Parse an instruction template like "insn op1, op2, op3".  */
1191
1192 static bool
1193 parse_insn_templ (const char *s, insn_templ *t)
1194 {
1195   const char *p = s;
1196   int insn_name_len;
1197   split_rec oprec;
1198   int i;
1199
1200   /* First find the first whitespace.  */
1201
1202   init_split_rec (&oprec);
1203
1204   p = skip_white (p);
1205   insn_name_len = strcspn (s, " ");
1206   if (insn_name_len == 0)
1207     return false;
1208
1209   init_insn_templ (t);
1210   t->opcode_name = enter_opname_n (p, insn_name_len);
1211
1212   p = p + insn_name_len;
1213
1214   /* Split by ',' and skip beginning and trailing whitespace.  */
1215   split_string (&oprec, p, ',', true);
1216
1217   for (i = 0; i < oprec.count; i++)
1218     {
1219       const char *opname = oprec.vec[i];
1220       opname_map_e *e = XNEW (opname_map_e);
1221       e->next = NULL;
1222       e->operand_name = NULL;
1223       e->constant_value = 0;
1224       e->operand_num = i;
1225
1226       /* If it begins with a number, assume that it is a number.  */
1227       if (opname && opname[0] >= '0' && opname[0] <= '9')
1228         {
1229           unsigned val;
1230
1231           if (parse_constant (opname, &val))
1232             e->constant_value = val;
1233           else
1234             {
1235               free (e);
1236               clear_split_rec (&oprec);
1237               clear_insn_templ (t);
1238               return false;
1239             }
1240         }
1241       else
1242         e->operand_name = enter_opname (oprec.vec[i]);
1243
1244       *t->operand_map.tail = e;
1245       t->operand_map.tail = &e->next;
1246     }
1247   clear_split_rec (&oprec);
1248   return true;
1249 }
1250
1251
1252 static bool
1253 parse_precond (const char *s, precond_e *precond)
1254 {
1255   /* All preconditions are currently of the form:
1256      a == b or a != b or a == k (where k is a constant).
1257      Later we may use some special functions like DENSITY == 1
1258      to identify when density is available.  */
1259
1260   const char *p = s;
1261   int len;
1262   precond->opname1 = NULL;
1263   precond->opval1 = 0;
1264   precond->cmpop = OP_EQUAL;
1265   precond->opname2 = NULL;
1266   precond->opval2 = 0;
1267   precond->next = NULL;
1268
1269   p = skip_white (p);
1270
1271   len = strcspn (p, " !=");
1272
1273   if (len == 0)
1274     return false;
1275
1276   precond->opname1 = enter_opname_n (p, len);
1277   p = p + len;
1278   p = skip_white (p);
1279
1280   /* Check for "==" and "!=".  */
1281   if (startswith (p, "=="))
1282     precond->cmpop = OP_EQUAL;
1283   else if (startswith (p, "!="))
1284     precond->cmpop = OP_NOTEQUAL;
1285   else
1286     return false;
1287
1288   p = p + 2;
1289   p = skip_white (p);
1290
1291   /* No trailing whitespace from earlier parsing.  */
1292   if (p[0] >= '0' && p[0] <= '9')
1293     {
1294       unsigned val;
1295       if (parse_constant (p, &val))
1296         precond->opval2 = val;
1297       else
1298         return false;
1299     }
1300   else
1301     precond->opname2 = enter_opname (p);
1302   return true;
1303 }
1304
1305
1306 static void
1307 clear_req_or_option_list (ReqOrOption **r_p)
1308 {
1309   if (*r_p == NULL)
1310     return;
1311
1312   free ((*r_p)->option_name);
1313   clear_req_or_option_list (&(*r_p)->next);
1314   *r_p = NULL;
1315 }
1316
1317
1318 static void
1319 clear_req_option_list (ReqOption **r_p)
1320 {
1321   if (*r_p == NULL)
1322     return;
1323
1324   clear_req_or_option_list (&(*r_p)->or_option_terms);
1325   clear_req_option_list (&(*r_p)->next);
1326   *r_p = NULL;
1327 }
1328
1329
1330 static ReqOrOption *
1331 clone_req_or_option_list (ReqOrOption *req_or_option)
1332 {
1333   ReqOrOption *new_req_or_option;
1334
1335   if (req_or_option == NULL)
1336     return NULL;
1337
1338   new_req_or_option = XNEW (ReqOrOption);
1339   new_req_or_option->option_name = xstrdup (req_or_option->option_name);
1340   new_req_or_option->is_true = req_or_option->is_true;
1341   new_req_or_option->next = NULL;
1342   new_req_or_option->next = clone_req_or_option_list (req_or_option->next);
1343   return new_req_or_option;
1344 }
1345
1346
1347 static ReqOption *
1348 clone_req_option_list (ReqOption *req_option)
1349 {
1350   ReqOption *new_req_option;
1351
1352   if (req_option == NULL)
1353     return NULL;
1354
1355   new_req_option = XNEW (ReqOption);
1356   new_req_option->or_option_terms = NULL;
1357   new_req_option->next = NULL;
1358   new_req_option->or_option_terms =
1359     clone_req_or_option_list (req_option->or_option_terms);
1360   new_req_option->next = clone_req_option_list (req_option->next);
1361   return new_req_option;
1362 }
1363
1364
1365 static bool
1366 parse_option_cond (const char *s, ReqOption *option)
1367 {
1368   int i;
1369   split_rec option_term_rec;
1370
1371   /* All option or conditions are of the form:
1372      optionA + no-optionB + ...
1373      "Ands" are divided by "?".  */
1374
1375   init_split_rec (&option_term_rec);
1376   split_string (&option_term_rec, s, '+', true);
1377
1378   if (option_term_rec.count == 0)
1379     {
1380       clear_split_rec (&option_term_rec);
1381       return false;
1382     }
1383
1384   for (i = 0; i < option_term_rec.count; i++)
1385     {
1386       char *option_name = option_term_rec.vec[i];
1387       bool is_true = true;
1388       ReqOrOption *req;
1389       ReqOrOption **r_p;
1390
1391       if (startswith (option_name, "no-"))
1392         {
1393           option_name = xstrdup (&option_name[3]);
1394           is_true = false;
1395         }
1396       else
1397         option_name = xstrdup (option_name);
1398
1399       req = XNEW (ReqOrOption);
1400       req->option_name = option_name;
1401       req->is_true = is_true;
1402       req->next = NULL;
1403
1404       /* Append to list.  */
1405       for (r_p = &option->or_option_terms; (*r_p) != NULL;
1406            r_p = &(*r_p)->next)
1407         ;
1408       (*r_p) = req;
1409     }
1410   return true;
1411 }
1412
1413
1414 /* Parse a string like:
1415    "insn op1, op2, op3, op4 | op1 != op2 | op2 == op3 | op4 == 1".
1416    I.E., instruction "insn" with 4 operands where operand 1 and 2 are not
1417    the same and operand 2 and 3 are the same and operand 4 is 1.
1418
1419    or:
1420
1421    "insn op1 | op1 == 1 / density + boolean / no-useroption".
1422    i.e. instruction "insn" with 1 operands where operand 1 is 1
1423    when "density" or "boolean" options are available and
1424    "useroption" is not available.
1425
1426    Because the current implementation of this parsing scheme uses
1427    split_string, it requires that '|' and '?' are only used as
1428    delimiters for predicates and required options.  */
1429
1430 static bool
1431 parse_insn_pattern (const char *in, insn_pattern *insn)
1432 {
1433   split_rec rec;
1434   split_rec optionrec;
1435   int i;
1436
1437   init_insn_pattern (insn);
1438
1439   init_split_rec (&optionrec);
1440   split_string (&optionrec, in, '?', true);
1441   if (optionrec.count == 0)
1442     {
1443       clear_split_rec (&optionrec);
1444       return false;
1445     }
1446
1447   init_split_rec (&rec);
1448
1449   split_string (&rec, optionrec.vec[0], '|', true);
1450
1451   if (rec.count == 0)
1452     {
1453       clear_split_rec (&rec);
1454       clear_split_rec (&optionrec);
1455       return false;
1456     }
1457
1458   if (!parse_insn_templ (rec.vec[0], &insn->t))
1459     {
1460       clear_split_rec (&rec);
1461       clear_split_rec (&optionrec);
1462       return false;
1463     }
1464
1465   for (i = 1; i < rec.count; i++)
1466     {
1467       precond_e *cond = XNEW (precond_e);
1468
1469       if (!parse_precond (rec.vec[i], cond))
1470         {
1471           clear_split_rec (&rec);
1472           clear_split_rec (&optionrec);
1473           clear_insn_pattern (insn);
1474           return false;
1475         }
1476
1477       /* Append the condition.  */
1478       *insn->preconds.tail = cond;
1479       insn->preconds.tail = &cond->next;
1480     }
1481
1482   for (i = 1; i < optionrec.count; i++)
1483     {
1484       /* Handle the option conditions.  */
1485       ReqOption **r_p;
1486       ReqOption *req_option = XNEW (ReqOption);
1487       req_option->or_option_terms = NULL;
1488       req_option->next = NULL;
1489
1490       if (!parse_option_cond (optionrec.vec[i], req_option))
1491         {
1492           clear_split_rec (&rec);
1493           clear_split_rec (&optionrec);
1494           clear_insn_pattern (insn);
1495           clear_req_option_list (&req_option);
1496           return false;
1497         }
1498
1499       /* Append the condition.  */
1500       for (r_p = &insn->options; (*r_p) != NULL; r_p = &(*r_p)->next)
1501         ;
1502
1503       (*r_p) = req_option;
1504     }
1505
1506   clear_split_rec (&rec);
1507   clear_split_rec (&optionrec);
1508   return true;
1509 }
1510
1511
1512 static bool
1513 parse_insn_repl (const char *in, insn_repl *r_p)
1514 {
1515   /* This is a list of instruction templates separated by ';'.  */
1516   split_rec rec;
1517   int i;
1518
1519   split_string (&rec, in, ';', true);
1520
1521   for (i = 0; i < rec.count; i++)
1522     {
1523       insn_repl_e *e = XNEW (insn_repl_e);
1524
1525       e->next = NULL;
1526
1527       if (!parse_insn_templ (rec.vec[i], &e->t))
1528         {
1529           free (e);
1530           clear_insn_repl (r_p);
1531           return false;
1532         }
1533       *r_p->tail = e;
1534       r_p->tail = &e->next;
1535     }
1536   return true;
1537 }
1538
1539
1540 static bool
1541 transition_applies (insn_pattern *initial_insn,
1542                     const char *from_string ATTRIBUTE_UNUSED,
1543                     const char *to_string ATTRIBUTE_UNUSED)
1544 {
1545   ReqOption *req_option;
1546
1547   for (req_option = initial_insn->options;
1548        req_option != NULL;
1549        req_option = req_option->next)
1550     {
1551       ReqOrOption *req_or_option = req_option->or_option_terms;
1552
1553       if (req_or_option == NULL
1554           || req_or_option->next != NULL)
1555         continue;
1556
1557       if (startswith (req_or_option->option_name, "IsaUse"))
1558         {
1559           bool option_available = false;
1560           char *option_name = req_or_option->option_name + 6;
1561           if (!strcmp (option_name, "DensityInstruction"))
1562             option_available = (XCHAL_HAVE_DENSITY == 1);
1563           else if (!strcmp (option_name, "L32R"))
1564             option_available = (XCHAL_HAVE_L32R == 1);
1565           else if (!strcmp (option_name, "Const16"))
1566             option_available = (XCHAL_HAVE_CONST16 == 1);
1567           else if (!strcmp (option_name, "Loops"))
1568             option_available = (XCHAL_HAVE_LOOPS == 1);
1569           else if (!strcmp (option_name, "WideBranches"))
1570             option_available
1571               = (XCHAL_HAVE_WIDE_BRANCHES == 1 && produce_flix == FLIX_ALL);
1572           else if (!strcmp (option_name, "PredictedBranches"))
1573             option_available
1574               = (XCHAL_HAVE_PREDICTED_BRANCHES == 1
1575                  && produce_flix == FLIX_ALL);
1576           else if (!strcmp (option_name, "Booleans"))
1577             option_available = (XCHAL_HAVE_BOOLEANS == 1);
1578           else
1579             as_warn (_("invalid configuration option '%s' in transition rule '%s'"),
1580                      req_or_option->option_name, from_string);
1581           if ((option_available ^ req_or_option->is_true) != 0)
1582             return false;
1583         }
1584       else if (strcmp (req_or_option->option_name, "realnop") == 0)
1585         {
1586           bool nop_available =
1587             (xtensa_opcode_lookup (xtensa_default_isa, "nop")
1588              != XTENSA_UNDEFINED);
1589           if ((nop_available ^ req_or_option->is_true) != 0)
1590             return false;
1591         }
1592     }
1593   return true;
1594 }
1595
1596
1597 static bool
1598 wide_branch_opcode (const char *opcode_name,
1599                     const char *suffix,
1600                     xtensa_opcode *popcode)
1601 {
1602   xtensa_isa isa = xtensa_default_isa;
1603   xtensa_opcode opcode;
1604   static char wbr_name_buf[20];
1605
1606   if (!startswith (opcode_name, "WIDE."))
1607     return false;
1608
1609   strcpy (wbr_name_buf, opcode_name + 5);
1610   strcat (wbr_name_buf, suffix);
1611   opcode = xtensa_opcode_lookup (isa, wbr_name_buf);
1612   if (opcode != XTENSA_UNDEFINED)
1613     {
1614       *popcode = opcode;
1615       return true;
1616     }
1617
1618   return false;
1619 }
1620
1621
1622 static TransitionRule *
1623 build_transition (insn_pattern *initial_insn,
1624                   insn_repl *replace_insns,
1625                   const char *from_string,
1626                   const char *to_string)
1627 {
1628   TransitionRule *tr = NULL;
1629   xtensa_opcode opcode;
1630   xtensa_isa isa = xtensa_default_isa;
1631   BuildInstr *literal_bi;
1632
1633   opname_map_e *op1;
1634   opname_map_e *op2;
1635
1636   precond_e *precond;
1637   insn_repl_e *r;
1638
1639   if (!wide_branch_opcode (initial_insn->t.opcode_name, ".w18", &opcode)
1640       && !wide_branch_opcode (initial_insn->t.opcode_name, ".w15", &opcode))
1641     opcode = xtensa_opcode_lookup (isa, initial_insn->t.opcode_name);
1642
1643   if (opcode == XTENSA_UNDEFINED)
1644     {
1645       /* It is OK to not be able to translate some of these opcodes.  */
1646       return NULL;
1647     }
1648
1649
1650   if (xtensa_opcode_num_operands (isa, opcode)
1651       != insn_templ_operand_count (&initial_insn->t))
1652     {
1653       /* This is also OK because there are opcodes that
1654          have different numbers of operands on different
1655          architecture variations.  */
1656       return NULL;
1657     }
1658
1659   tr = XNEW (TransitionRule);
1660   tr->opcode = opcode;
1661   tr->conditions = NULL;
1662   tr->to_instr = NULL;
1663
1664   /* Build the conditions. First, equivalent operand condition....  */
1665   for (op1 = initial_insn->t.operand_map.head; op1 != NULL; op1 = op1->next)
1666     {
1667       for (op2 = op1->next; op2 != NULL; op2 = op2->next)
1668         {
1669           if (same_operand_name (op1, op2))
1670             {
1671               append_value_condition (tr, OP_EQUAL,
1672                                       op1->operand_num, op2->operand_num);
1673             }
1674         }
1675     }
1676
1677   /* Now the condition that an operand value must be a constant....  */
1678   for (op1 = initial_insn->t.operand_map.head; op1 != NULL; op1 = op1->next)
1679     {
1680       if (op_is_constant (op1))
1681         {
1682           append_constant_value_condition (tr,
1683                                            OP_EQUAL,
1684                                            op1->operand_num,
1685                                            op_get_constant (op1));
1686         }
1687     }
1688
1689
1690   /* Now add the explicit preconditions listed after the "|" in the spec.
1691      These are currently very limited, so we do a special case
1692      parse for them.  We expect spaces, opname != opname.  */
1693   for (precond = initial_insn->preconds.head;
1694        precond != NULL;
1695        precond = precond->next)
1696     {
1697       op1 = NULL;
1698       op2 = NULL;
1699
1700       if (precond->opname1)
1701         {
1702           op1 = get_opmatch (&initial_insn->t.operand_map, precond->opname1);
1703           if (op1 == NULL)
1704             as_fatal (_("opcode '%s': no bound opname '%s' "
1705                         "for precondition in '%s'"),
1706                       xtensa_opcode_name (isa, opcode),
1707                       precond->opname1, from_string);
1708         }
1709
1710       if (precond->opname2)
1711         {
1712           op2 = get_opmatch (&initial_insn->t.operand_map, precond->opname2);
1713           if (op2 == NULL)
1714             as_fatal (_("opcode '%s': no bound opname '%s' "
1715                         "for precondition in '%s'"),
1716                       xtensa_opcode_name (isa, opcode),
1717                       precond->opname2, from_string);
1718         }
1719
1720       if (op1 == NULL && op2 == NULL)
1721         as_fatal (_("opcode '%s': precondition only contains "
1722                     "constants in '%s'"),
1723                   xtensa_opcode_name (isa, opcode), from_string);
1724       else if (op1 != NULL && op2 != NULL)
1725         append_value_condition (tr, precond->cmpop,
1726                                 op1->operand_num, op2->operand_num);
1727       else if (op2 == NULL)
1728         append_constant_value_condition (tr, precond->cmpop,
1729                                          op1->operand_num, precond->opval2);
1730       else
1731         append_constant_value_condition (tr, precond->cmpop,
1732                                          op2->operand_num, precond->opval1);
1733     }
1734
1735   tr->options = clone_req_option_list (initial_insn->options);
1736
1737   /* Generate the replacement instructions.  Some of these
1738      "instructions" are actually labels and literals.  There can be at
1739      most one literal and at most one label.  A literal must be defined
1740      (e.g., "LITERAL %imm") before use (e.g., "%LITERAL").  The labels
1741      can be used before they are defined.  Also there are a number of
1742      special operands (e.g., HI24S).  */
1743
1744   literal_bi = NULL;
1745   for (r = replace_insns->head; r != NULL; r = r->next)
1746     {
1747       BuildInstr *bi;
1748       const char *opcode_name;
1749       int operand_count;
1750       opname_map_e *op;
1751       const char *fn_name;
1752       const char *operand_arg_name;
1753
1754       bi = XNEW (BuildInstr);
1755       append_build_insn (tr, bi);
1756
1757       bi->opcode = XTENSA_UNDEFINED;
1758       bi->ops = NULL;
1759       bi->next = NULL;
1760
1761       opcode_name = r->t.opcode_name;
1762       operand_count = insn_templ_operand_count (&r->t);
1763
1764       if (strcmp (opcode_name, "LITERAL") == 0)
1765         {
1766           bi->typ = INSTR_LITERAL_DEF;
1767           if (operand_count != 1)
1768             as_fatal (_("expected one operand for generated literal"));
1769           literal_bi = bi;
1770         }
1771       else if (strcmp (opcode_name, "LABEL") == 0)
1772         {
1773           bi->typ = INSTR_LABEL_DEF;
1774           if (operand_count != 0)
1775             as_fatal (_("expected 0 operands for generated label"));
1776         }
1777       else
1778         {
1779           bi->typ = INSTR_INSTR;
1780           if (wide_branch_opcode (opcode_name, ".w18", &bi->opcode)
1781               || wide_branch_opcode (opcode_name, ".w15", &bi->opcode))
1782             opcode_name = xtensa_opcode_name (isa, bi->opcode);
1783           else
1784             bi->opcode = xtensa_opcode_lookup (isa, opcode_name);
1785
1786           if (bi->opcode == XTENSA_UNDEFINED)
1787             {
1788               as_warn (_("invalid opcode '%s' in transition rule '%s'"),
1789                        opcode_name, to_string);
1790               return NULL;
1791             }
1792
1793           /* Check for the right number of ops.  */
1794           if (xtensa_opcode_num_operands (isa, bi->opcode)
1795               != (int) operand_count)
1796             as_fatal (ngettext ("opcode '%s': replacement does not have %d op",
1797                                 "opcode '%s': replacement does not have %d ops",
1798                                 xtensa_opcode_num_operands (isa, bi->opcode)),
1799                       opcode_name,
1800                       xtensa_opcode_num_operands (isa, bi->opcode));
1801         }
1802
1803       for (op = r->t.operand_map.head; op != NULL; op = op->next)
1804         {
1805           unsigned idnum;
1806
1807           if (op_is_constant (op))
1808             append_constant_op (bi, op->operand_num, op_get_constant (op));
1809           else if (strcmp (op->operand_name, "%LITERAL") == 0)
1810             {
1811               if (! literal_bi || ! literal_bi->ops || literal_bi->ops->next)
1812                 as_fatal (_("opcode '%s': cannot find literal definition"),
1813                           opcode_name);
1814               append_literal_op (bi, op->operand_num,
1815                                  literal_bi->ops->op_data);
1816             }
1817           else if (strcmp (op->operand_name, "%LABEL") == 0)
1818             append_label_op (bi, op->operand_num);
1819           else if (op->operand_name[0] == 'a'
1820                    && parse_constant (op->operand_name + 1, &idnum))
1821             append_constant_op (bi, op->operand_num, idnum);
1822           else if (op->operand_name[0] == '%')
1823             {
1824               opname_map_e *orig_op;
1825               orig_op = get_opmatch (&initial_insn->t.operand_map,
1826                                      op->operand_name);
1827               if (orig_op == NULL)
1828                 as_fatal (_("opcode '%s': unidentified operand '%s' in '%s'"),
1829                           opcode_name, op->operand_name, to_string);
1830               append_field_op (bi, op->operand_num, orig_op->operand_num);
1831             }
1832           else if (strcmp (op->operand_name, "FREEREG") == 0)
1833             {
1834               append_user_fn_field_op (bi, op->operand_num, OP_FREEREG, 0);
1835             }
1836           else if (parse_special_fn (op->operand_name,
1837                                      &fn_name, &operand_arg_name))
1838             {
1839               opname_map_e *orig_op;
1840               OpType typ = OP_CONSTANT;
1841
1842               if (strcmp (fn_name, "LOW8") == 0)
1843                 typ = OP_OPERAND_LOW8;
1844               else if (strcmp (fn_name, "HI24S") == 0)
1845                 typ = OP_OPERAND_HI24S;
1846               else if (strcmp (fn_name, "F32MINUS") == 0)
1847                 typ = OP_OPERAND_F32MINUS;
1848               else if (strcmp (fn_name, "LOW16U") == 0)
1849                 typ = OP_OPERAND_LOW16U;
1850               else if (strcmp (fn_name, "HI16U") == 0)
1851                 typ = OP_OPERAND_HI16U;
1852               else
1853                 as_fatal (_("unknown user-defined function %s"), fn_name);
1854
1855               orig_op = get_opmatch (&initial_insn->t.operand_map,
1856                                      operand_arg_name);
1857               if (orig_op == NULL)
1858                 as_fatal (_("opcode '%s': unidentified operand '%s' in '%s'"),
1859                           opcode_name, op->operand_name, to_string);
1860               append_user_fn_field_op (bi, op->operand_num,
1861                                        typ, orig_op->operand_num);
1862             }
1863           else
1864             as_fatal (_("opcode '%s': could not parse operand '%s' in '%s'"),
1865                       opcode_name, op->operand_name, to_string);
1866         }
1867     }
1868
1869   return tr;
1870 }
1871
1872
1873 static TransitionTable *
1874 build_transition_table (const string_pattern_pair *transitions,
1875                         int transition_count,
1876                         transition_cmp_fn cmp)
1877 {
1878   TransitionTable *table = NULL;
1879   int num_opcodes = xtensa_isa_num_opcodes (xtensa_default_isa);
1880   int i, tnum;
1881
1882   if (table != NULL)
1883     return table;
1884
1885   /* Otherwise, build it now.  */
1886   table = XNEW (TransitionTable);
1887   table->num_opcodes = num_opcodes;
1888   table->table = XNEWVEC (TransitionList *, num_opcodes);
1889
1890   for (i = 0; i < num_opcodes; i++)
1891     table->table[i] = NULL;
1892
1893   for (tnum = 0; tnum < transition_count; tnum++)
1894     {
1895       const char *from_string = transitions[tnum].pattern;
1896       const char *to_string = transitions[tnum].replacement;
1897
1898       insn_pattern initial_insn;
1899       insn_repl replace_insns;
1900       TransitionRule *tr;
1901
1902       init_insn_pattern (&initial_insn);
1903       if (!parse_insn_pattern (from_string, &initial_insn))
1904         as_fatal (_("could not parse INSN_PATTERN '%s'"), from_string);
1905
1906       init_insn_repl (&replace_insns);
1907       if (!parse_insn_repl (to_string, &replace_insns))
1908         as_fatal (_("could not parse INSN_REPL '%s'"), to_string);
1909
1910       if (transition_applies (&initial_insn, from_string, to_string))
1911         {
1912           tr = build_transition (&initial_insn, &replace_insns,
1913                                  from_string, to_string);
1914           if (tr)
1915             append_transition (table, tr->opcode, tr, cmp);
1916           else
1917             {
1918 #if TENSILICA_DEBUG
1919               as_warn (_("could not build transition for %s => %s"),
1920                        from_string, to_string);
1921 #endif
1922             }
1923         }
1924
1925       clear_insn_repl (&replace_insns);
1926       clear_insn_pattern (&initial_insn);
1927     }
1928   return table;
1929 }
1930
1931 \f
1932 extern TransitionTable *
1933 xg_build_widen_table (transition_cmp_fn cmp)
1934 {
1935   static TransitionTable *table = NULL;
1936   if (table == NULL)
1937     table = build_transition_table (widen_spec_list, WIDEN_COUNT, cmp);
1938   return table;
1939 }
1940
1941
1942 extern TransitionTable *
1943 xg_build_simplify_table (transition_cmp_fn cmp)
1944 {
1945   static TransitionTable *table = NULL;
1946   if (table == NULL)
1947     table = build_transition_table (simplify_spec_list, SIMPLIFY_COUNT, cmp);
1948   return table;
1949 }