gas/config/xtensa-relax.c

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