gas/config/xtensa-relax.c

   1 /* Table of relaxations for Xtensa assembly.
   2    Copyright 2003, 2004, 2005, 2007, 2008 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
 469 #define WIDEN_COUNT (sizeof (widen_spec_list) / sizeof (string_pattern_pair))
 470
 471
 472 /* The simplify_spec_list specifies simplifying transformations that
 473    will reduce the instruction width or otherwise simplify an
 474    instruction.  These are usually applied before relaxation in the
 475    assembler.  It is always legal to simplify.  Even for "addi as, 0",
 476    the "addi.n as, 0" will eventually be widened back to an "addi 0"
 477    after the widening table is applied.  Note: The usage of this table
 478    has changed somewhat so that it is entirely specific to "narrowing"
 479    instructions to use the density option.  This table is not used at
 480    all when the density option is not available.  */
 481
 482 string_pattern_pair simplify_spec_list[] =
 483 {
 484   {"add %ar,%as,%at ? IsaUseDensityInstruction", "add.n %ar,%as,%at"},
 485   {"addi.n %ar,%as,0 ? IsaUseDensityInstruction", "mov.n %ar,%as"},
 486   {"addi %ar,%as,0 ? IsaUseDensityInstruction", "mov.n %ar,%as"},
 487   {"addi %ar,%as,%imm ? IsaUseDensityInstruction", "addi.n %ar,%as,%imm"},
 488   {"addmi %ar,%as,%imm ? IsaUseDensityInstruction", "addi.n %ar,%as,%imm"},
 489   {"beqz %as,%label ? IsaUseDensityInstruction", "beqz.n %as,%label"},
 490   {"bnez %as,%label ? IsaUseDensityInstruction", "bnez.n %as,%label"},
 491   {"l32i %at,%as,%imm ? IsaUseDensityInstruction", "l32i.n %at,%as,%imm"},
 492   {"movi %as,%imm ? IsaUseDensityInstruction", "movi.n %as,%imm"},
 493   {"nop ? realnop ? IsaUseDensityInstruction", "nop.n"},
 494   {"or %ar,%as,%at | %ar==%as | %as==%at ? IsaUseDensityInstruction", "nop.n"},
 495   {"or %ar,%as,%at | %ar!=%as | %as==%at ? IsaUseDensityInstruction", "mov.n %ar,%as"},
 496   {"ret %as ? IsaUseDensityInstruction", "ret.n %as"},
 497   {"retw %as ? IsaUseDensityInstruction", "retw.n %as"},
 498   {"s32i %at,%as,%imm ? IsaUseDensityInstruction", "s32i.n %at,%as,%imm"},
 499   {"slli %ar,%as,0 ? IsaUseDensityInstruction", "mov.n %ar,%as"}
 500 };
 501
 502 #define SIMPLIFY_COUNT \
 503   (sizeof (simplify_spec_list) / sizeof (string_pattern_pair))
 504
 505 \f
 506 /* Externally visible functions.  */
 507
 508 extern bfd_boolean xg_has_userdef_op_fn (OpType);
 509 extern long xg_apply_userdef_op_fn (OpType, long);
 510
 511
 512 static void
 513 append_transition (TransitionTable *tt,
 514                    xtensa_opcode opcode,
 515                    TransitionRule *t,
 516                    transition_cmp_fn cmp)
 517 {
 518   TransitionList *tl = (TransitionList *) xmalloc (sizeof (TransitionList));
 519   TransitionList *prev;
 520   TransitionList **t_p;
 521   assert (tt != NULL);
 522   assert (opcode < tt->num_opcodes);
 523
 524   prev = tt->table[opcode];
 525   tl->rule = t;
 526   tl->next = NULL;
 527   if (prev == NULL)
 528     {
 529       tt->table[opcode] = tl;
 530       return;
 531     }
 532
 533   for (t_p = &tt->table[opcode]; (*t_p) != NULL; t_p = &(*t_p)->next)
 534     {
 535       if (cmp && cmp (t, (*t_p)->rule) < 0)
 536         {
 537           /* Insert it here.  */
 538           tl->next = *t_p;
 539           *t_p = tl;
 540           return;
 541         }
 542     }
 543   (*t_p) = tl;
 544 }
 545
 546
 547 static void
 548 append_condition (TransitionRule *tr, Precondition *cond)
 549 {
 550   PreconditionList *pl =
 551     (PreconditionList *) xmalloc (sizeof (PreconditionList));
 552   PreconditionList *prev = tr->conditions;
 553   PreconditionList *nxt;
 554
 555   pl->precond = cond;
 556   pl->next = NULL;
 557   if (prev == NULL)
 558     {
 559       tr->conditions = pl;
 560       return;
 561     }
 562   nxt = prev->next;
 563   while (nxt != NULL)
 564     {
 565       prev = nxt;
 566       nxt = nxt->next;
 567     }
 568   prev->next = pl;
 569 }
 570
 571
 572 static void
 573 append_value_condition (TransitionRule *tr,
 574                         CmpOp cmp,
 575                         unsigned op1,
 576                         unsigned op2)
 577 {
 578   Precondition *cond = (Precondition *) xmalloc (sizeof (Precondition));
 579
 580   cond->cmp = cmp;
 581   cond->op_num = op1;
 582   cond->typ = OP_OPERAND;
 583   cond->op_data = op2;
 584   append_condition (tr, cond);
 585 }
 586
 587
 588 static void
 589 append_constant_value_condition (TransitionRule *tr,
 590                                  CmpOp cmp,
 591                                  unsigned op1,
 592                                  unsigned cnst)
 593 {
 594   Precondition *cond = (Precondition *) xmalloc (sizeof (Precondition));
 595
 596   cond->cmp = cmp;
 597   cond->op_num = op1;
 598   cond->typ = OP_CONSTANT;
 599   cond->op_data = cnst;
 600   append_condition (tr, cond);
 601 }
 602
 603
 604 static void
 605 append_build_insn (TransitionRule *tr, BuildInstr *bi)
 606 {
 607   BuildInstr *prev = tr->to_instr;
 608   BuildInstr *nxt;
 609
 610   bi->next = NULL;
 611   if (prev == NULL)
 612     {
 613       tr->to_instr = bi;
 614       return;
 615     }
 616   nxt = prev->next;
 617   while (nxt != 0)
 618     {
 619       prev = nxt;
 620       nxt = prev->next;
 621     }
 622   prev->next = bi;
 623 }
 624
 625
 626 static void
 627 append_op (BuildInstr *bi, BuildOp *b_op)
 628 {
 629   BuildOp *prev = bi->ops;
 630   BuildOp *nxt;
 631
 632   if (prev == NULL)
 633     {
 634       bi->ops = b_op;
 635       return;
 636     }
 637   nxt = prev->next;
 638   while (nxt != NULL)
 639     {
 640       prev = nxt;
 641       nxt = nxt->next;
 642     }
 643   prev->next = b_op;
 644 }
 645
 646
 647 static void
 648 append_literal_op (BuildInstr *bi, unsigned op1, unsigned src_op)
 649 {
 650   BuildOp *b_op = (BuildOp *) xmalloc (sizeof (BuildOp));
 651
 652   b_op->op_num = op1;
 653   b_op->typ = OP_LITERAL;
 654   b_op->op_data = src_op;
 655   b_op->next = NULL;
 656   append_op (bi, b_op);
 657 }
 658
 659
 660 static void
 661 append_label_op (BuildInstr *bi, unsigned op1)
 662 {
 663   BuildOp *b_op = (BuildOp *) xmalloc (sizeof (BuildOp));
 664
 665   b_op->op_num = op1;
 666   b_op->typ = OP_LABEL;
 667   b_op->op_data = 0;
 668   b_op->next = NULL;
 669   append_op (bi, b_op);
 670 }
 671
 672
 673 static void
 674 append_constant_op (BuildInstr *bi, unsigned op1, unsigned cnst)
 675 {
 676   BuildOp *b_op = (BuildOp *) xmalloc (sizeof (BuildOp));
 677
 678   b_op->op_num = op1;
 679   b_op->typ = OP_CONSTANT;
 680   b_op->op_data = cnst;
 681   b_op->next = NULL;
 682   append_op (bi, b_op);
 683 }
 684
 685
 686 static void
 687 append_field_op (BuildInstr *bi, unsigned op1, unsigned src_op)
 688 {
 689   BuildOp *b_op = (BuildOp *) xmalloc (sizeof (BuildOp));
 690
 691   b_op->op_num = op1;
 692   b_op->typ = OP_OPERAND;
 693   b_op->op_data = src_op;
 694   b_op->next = NULL;
 695   append_op (bi, b_op);
 696 }
 697
 698
 699 /* These could be generated but are not currently.  */
 700
 701 static void
 702 append_user_fn_field_op (BuildInstr *bi,
 703                          unsigned op1,
 704                          OpType typ,
 705                          unsigned src_op)
 706 {
 707   BuildOp *b_op = (BuildOp *) xmalloc (sizeof (BuildOp));
 708
 709   b_op->op_num = op1;
 710   b_op->typ = typ;
 711   b_op->op_data = src_op;
 712   b_op->next = NULL;
 713   append_op (bi, b_op);
 714 }
 715
 716
 717 /* These operand functions are the semantics of user-defined
 718    operand functions.  */
 719
 720 static long
 721 operand_function_HI24S (long a)
 722 {
 723   if (a & 0x80)
 724     return (a & (~0xff)) + 0x100;
 725   else
 726     return (a & (~0xff));
 727 }
 728
 729
 730 static long
 731 operand_function_F32MINUS (long a)
 732 {
 733   return (32 - a);
 734 }
 735
 736
 737 static long
 738 operand_function_LOW8 (long a)
 739 {
 740   if (a & 0x80)
 741     return (a & 0xff) | ~0xff;
 742   else
 743     return (a & 0xff);
 744 }
 745
 746
 747 static long
 748 operand_function_LOW16U (long a)
 749 {
 750   return (a & 0xffff);
 751 }
 752
 753
 754 static long
 755 operand_function_HI16U (long a)
 756 {
 757   unsigned long b = a & 0xffff0000;
 758   return (long) (b >> 16);
 759 }
 760
 761
 762 bfd_boolean
 763 xg_has_userdef_op_fn (OpType op)
 764 {
 765   switch (op)
 766     {
 767     case OP_OPERAND_F32MINUS:
 768     case OP_OPERAND_LOW8:
 769     case OP_OPERAND_HI24S:
 770     case OP_OPERAND_LOW16U:
 771     case OP_OPERAND_HI16U:
 772       return TRUE;
 773     default:
 774       break;
 775     }
 776   return FALSE;
 777 }
 778
 779
 780 long
 781 xg_apply_userdef_op_fn (OpType op, long a)
 782 {
 783   switch (op)
 784     {
 785     case OP_OPERAND_F32MINUS:
 786       return operand_function_F32MINUS (a);
 787     case OP_OPERAND_LOW8:
 788       return operand_function_LOW8 (a);
 789     case OP_OPERAND_HI24S:
 790       return operand_function_HI24S (a);
 791     case OP_OPERAND_LOW16U:
 792       return operand_function_LOW16U (a);
 793     case OP_OPERAND_HI16U:
 794       return operand_function_HI16U (a);
 795     default:
 796       break;
 797     }
 798   return FALSE;
 799 }
 800
 801
 802 /* Generate a transition table.  */
 803
 804 static const char *
 805 enter_opname_n (const char *name, int len)
 806 {
 807   opname_e *op;
 808
 809   for (op = local_opnames; op != NULL; op = op->next)
 810     {
 811       if (strlen (op->opname) == (unsigned) len
 812           && strncmp (op->opname, name, len) == 0)
 813         return op->opname;
 814     }
 815   op = (opname_e *) xmalloc (sizeof (opname_e));
 816   op->opname = (char *) xmalloc (len + 1);
 817   strncpy (op->opname, name, len);
 818   op->opname[len] = '\0';
 819   return op->opname;
 820 }
 821
 822
 823 static const char *
 824 enter_opname (const char *name)
 825 {
 826   opname_e *op;
 827
 828   for (op = local_opnames; op != NULL; op = op->next)
 829     {
 830       if (strcmp (op->opname, name) == 0)
 831         return op->opname;
 832     }
 833   op = (opname_e *) xmalloc (sizeof (opname_e));
 834   op->opname = xstrdup (name);
 835   return op->opname;
 836 }
 837
 838
 839 static void
 840 init_opname_map (opname_map *m)
 841 {
 842   m->head = NULL;
 843   m->tail = &m->head;
 844 }
 845
 846
 847 static void
 848 clear_opname_map (opname_map *m)
 849 {
 850   opname_map_e *e;
 851
 852   while (m->head != NULL)
 853     {
 854       e = m->head;
 855       m->head = e->next;
 856       free (e);
 857     }
 858   m->tail = &m->head;
 859 }
 860
 861
 862 static bfd_boolean
 863 same_operand_name (const opname_map_e *m1, const opname_map_e *m2)
 864 {
 865   if (m1->operand_name == NULL || m1->operand_name == NULL)
 866     return FALSE;
 867   return (m1->operand_name == m2->operand_name);
 868 }
 869
 870
 871 static opname_map_e *
 872 get_opmatch (opname_map *map, const char *operand_name)
 873 {
 874   opname_map_e *m;
 875
 876   for (m = map->head; m != NULL; m = m->next)
 877     {
 878       if (strcmp (m->operand_name, operand_name) == 0)
 879         return m;
 880     }
 881   return NULL;
 882 }
 883
 884
 885 static bfd_boolean
 886 op_is_constant (const opname_map_e *m1)
 887 {
 888   return (m1->operand_name == NULL);
 889 }
 890
 891
 892 static unsigned
 893 op_get_constant (const opname_map_e *m1)
 894 {
 895   assert (m1->operand_name == NULL);
 896   return m1->constant_value;
 897 }
 898
 899
 900 static void
 901 init_precond_list (precond_list *l)
 902 {
 903   l->head = NULL;
 904   l->tail = &l->head;
 905 }
 906
 907
 908 static void
 909 clear_precond_list (precond_list *l)
 910 {
 911   precond_e *e;
 912
 913   while (l->head != NULL)
 914     {
 915       e = l->head;
 916       l->head = e->next;
 917       free (e);
 918     }
 919   l->tail = &l->head;
 920 }
 921
 922
 923 static void
 924 init_insn_templ (insn_templ *t)
 925 {
 926   t->opcode_name = NULL;
 927   init_opname_map (&t->operand_map);
 928 }
 929
 930
 931 static void
 932 clear_insn_templ (insn_templ *t)
 933 {
 934   clear_opname_map (&t->operand_map);
 935 }
 936
 937
 938 static void
 939 init_insn_pattern (insn_pattern *p)
 940 {
 941   init_insn_templ (&p->t);
 942   init_precond_list (&p->preconds);
 943   p->options = NULL;
 944 }
 945
 946
 947 static void
 948 clear_insn_pattern (insn_pattern *p)
 949 {
 950   clear_insn_templ (&p->t);
 951   clear_precond_list (&p->preconds);
 952 }
 953
 954
 955 static void
 956 init_insn_repl (insn_repl *r)
 957 {
 958   r->head = NULL;
 959   r->tail = &r->head;
 960 }
 961
 962
 963 static void
 964 clear_insn_repl (insn_repl *r)
 965 {
 966   insn_repl_e *e;
 967
 968   while (r->head != NULL)
 969     {
 970       e = r->head;
 971       r->head = e->next;
 972       clear_insn_templ (&e->t);
 973     }
 974   r->tail = &r->head;
 975 }
 976
 977
 978 static int
 979 insn_templ_operand_count (const insn_templ *t)
 980 {
 981   int i = 0;
 982   const opname_map_e *op;
 983
 984   for (op = t->operand_map.head; op != NULL; op = op->next, i++)
 985     ;
 986   return i;
 987 }
 988
 989
 990 /* Convert a string to a number.  E.G.: parse_constant("10", &num) */
 991
 992 static bfd_boolean
 993 parse_constant (const char *in, unsigned *val_p)
 994 {
 995   unsigned val = 0;
 996   const char *p;
 997
 998   if (in == NULL)
 999     return FALSE;
1000   p = in;
1001
1002   while (*p != '\0')
1003     {
1004       if (*p >= '0' && *p <= '9')
1005         val = val * 10 + (*p - '0');
1006       else
1007         return FALSE;
1008       ++p;
1009     }
1010   *val_p = val;
1011   return TRUE;
1012 }
1013
1014
1015 static bfd_boolean
1016 parse_special_fn (const char *name,
1017                   const char **fn_name_p,
1018                   const char **arg_name_p)
1019 {
1020   char *p_start;
1021   const char *p_end;
1022
1023   p_start = strchr (name, '(');
1024   if (p_start == NULL)
1025     return FALSE;
1026
1027   p_end = strchr (p_start, ')');
1028
1029   if (p_end == NULL)
1030     return FALSE;
1031
1032   if (p_end[1] != '\0')
1033     return FALSE;
1034
1035   *fn_name_p = enter_opname_n (name, p_start - name);
1036   *arg_name_p = enter_opname_n (p_start + 1, p_end - p_start - 1);
1037   return TRUE;
1038 }
1039
1040
1041 static const char *
1042 skip_white (const char *p)
1043 {
1044   if (p == NULL)
1045     return p;
1046   while (*p == ' ')
1047     ++p;
1048   return p;
1049 }
1050
1051
1052 static void
1053 trim_whitespace (char *in)
1054 {
1055   char *last_white = NULL;
1056   char *p = in;
1057
1058   while (p && *p != '\0')
1059     {
1060       while (*p == ' ')
1061         {
1062           if (last_white == NULL)
1063             last_white = p;
1064           p++;
1065         }
1066       if (*p != '\0')
1067         {
1068           last_white = NULL;
1069           p++;
1070         }
1071     }
1072   if (last_white)
1073     *last_white = '\0';
1074 }
1075
1076
1077 /* Split a string into component strings where "c" is the
1078    delimiter.  Place the result in the split_rec.  */
1079
1080 static void
1081 split_string (split_rec *rec,
1082               const char *in,
1083               char c,
1084               bfd_boolean elide_whitespace)
1085 {
1086   int cnt = 0;
1087   int i;
1088   const char *p = in;
1089
1090   while (p != NULL && *p != '\0')
1091     {
1092       cnt++;
1093       p = strchr (p, c);
1094       if (p)
1095         p++;
1096     }
1097   rec->count = cnt;
1098   rec->vec = NULL;
1099
1100   if (rec->count == 0)
1101     return;
1102
1103   rec->vec = (char **) xmalloc (sizeof (char *) * cnt);
1104   for (i = 0; i < cnt; i++)
1105     rec->vec[i] = 0;
1106
1107   p = in;
1108   for (i = 0; i < cnt; i++)
1109     {
1110       const char *q;
1111       int len;
1112
1113       q = p;
1114       if (elide_whitespace)
1115         q = skip_white (q);
1116
1117       p = strchr (q, c);
1118       if (p == NULL)
1119         rec->vec[i] = xstrdup (q);
1120       else
1121         {
1122           len = p - q;
1123           rec->vec[i] = (char *) xmalloc (sizeof (char) * (len + 1));
1124           strncpy (rec->vec[i], q, len);
1125           rec->vec[i][len] = '\0';
1126           p++;
1127         }
1128
1129       if (elide_whitespace)
1130         trim_whitespace (rec->vec[i]);
1131     }
1132 }
1133
1134
1135 static void
1136 clear_split_rec (split_rec *rec)
1137 {
1138   int i;
1139
1140   for (i = 0; i < rec->count; i++)
1141     free (rec->vec[i]);
1142
1143   if (rec->count > 0)
1144     free (rec->vec);
1145 }
1146
1147
1148 /* Initialize a split record.  The split record must be initialized
1149    before split_string is called.  */
1150
1151 static void
1152 init_split_rec (split_rec *rec)
1153 {
1154   rec->vec = NULL;
1155   rec->count = 0;
1156 }
1157
1158
1159 /* Parse an instruction template like "insn op1, op2, op3".  */
1160
1161 static bfd_boolean
1162 parse_insn_templ (const char *s, insn_templ *t)
1163 {
1164   const char *p = s;
1165   int insn_name_len;
1166   split_rec oprec;
1167   int i;
1168
1169   /* First find the first whitespace.  */
1170
1171   init_split_rec (&oprec);
1172
1173   p = skip_white (p);
1174   insn_name_len = strcspn (s, " ");
1175   if (insn_name_len == 0)
1176     return FALSE;
1177
1178   init_insn_templ (t);
1179   t->opcode_name = enter_opname_n (p, insn_name_len);
1180
1181   p = p + insn_name_len;
1182
1183   /* Split by ',' and skip beginning and trailing whitespace.  */
1184   split_string (&oprec, p, ',', TRUE);
1185
1186   for (i = 0; i < oprec.count; i++)
1187     {
1188       const char *opname = oprec.vec[i];
1189       opname_map_e *e = (opname_map_e *) xmalloc (sizeof (opname_map_e));
1190       e->next = NULL;
1191       e->operand_name = NULL;
1192       e->constant_value = 0;
1193       e->operand_num = i;
1194
1195       /* If it begins with a number, assume that it is a number.  */
1196       if (opname && opname[0] >= '0' && opname[0] <= '9')
1197         {
1198           unsigned val;
1199
1200           if (parse_constant (opname, &val))
1201             e->constant_value = val;
1202           else
1203             {
1204               free (e);
1205               clear_split_rec (&oprec);
1206               clear_insn_templ (t);
1207               return FALSE;
1208             }
1209         }
1210       else
1211         e->operand_name = enter_opname (oprec.vec[i]);
1212
1213       *t->operand_map.tail = e;
1214       t->operand_map.tail = &e->next;
1215     }
1216   clear_split_rec (&oprec);
1217   return TRUE;
1218 }
1219
1220
1221 static bfd_boolean
1222 parse_precond (const char *s, precond_e *precond)
1223 {
1224   /* All preconditions are currently of the form:
1225      a == b or a != b or a == k (where k is a constant).
1226      Later we may use some special functions like DENSITY == 1
1227      to identify when density is available.  */
1228
1229   const char *p = s;
1230   int len;
1231   precond->opname1 = NULL;
1232   precond->opval1 = 0;
1233   precond->cmpop = OP_EQUAL;
1234   precond->opname2 = NULL;
1235   precond->opval2 = 0;
1236   precond->next = NULL;
1237
1238   p = skip_white (p);
1239
1240   len = strcspn (p, " !=");
1241
1242   if (len == 0)
1243     return FALSE;
1244
1245   precond->opname1 = enter_opname_n (p, len);
1246   p = p + len;
1247   p = skip_white (p);
1248
1249   /* Check for "==" and "!=".  */
1250   if (strncmp (p, "==", 2) == 0)
1251     precond->cmpop = OP_EQUAL;
1252   else if (strncmp (p, "!=", 2) == 0)
1253     precond->cmpop = OP_NOTEQUAL;
1254   else
1255     return FALSE;
1256
1257   p = p + 2;
1258   p = skip_white (p);
1259
1260   /* No trailing whitespace from earlier parsing.  */
1261   if (p[0] >= '0' && p[0] <= '9')
1262     {
1263       unsigned val;
1264       if (parse_constant (p, &val))
1265         precond->opval2 = val;
1266       else
1267         return FALSE;
1268     }
1269   else
1270     precond->opname2 = enter_opname (p);
1271   return TRUE;
1272 }
1273
1274
1275 static void
1276 clear_req_or_option_list (ReqOrOption **r_p)
1277 {
1278   if (*r_p == NULL)
1279     return;
1280
1281   free ((*r_p)->option_name);
1282   clear_req_or_option_list (&(*r_p)->next);
1283   *r_p = NULL;
1284 }
1285
1286
1287 static void
1288 clear_req_option_list (ReqOption **r_p)
1289 {
1290   if (*r_p == NULL)
1291     return;
1292
1293   clear_req_or_option_list (&(*r_p)->or_option_terms);
1294   clear_req_option_list (&(*r_p)->next);
1295   *r_p = NULL;
1296 }
1297
1298
1299 static ReqOrOption *
1300 clone_req_or_option_list (ReqOrOption *req_or_option)
1301 {
1302   ReqOrOption *new_req_or_option;
1303
1304   if (req_or_option == NULL)
1305     return NULL;
1306
1307   new_req_or_option = (ReqOrOption *) xmalloc (sizeof (ReqOrOption));
1308   new_req_or_option->option_name = xstrdup (req_or_option->option_name);
1309   new_req_or_option->is_true = req_or_option->is_true;
1310   new_req_or_option->next = NULL;
1311   new_req_or_option->next = clone_req_or_option_list (req_or_option->next);
1312   return new_req_or_option;
1313 }
1314
1315
1316 static ReqOption *
1317 clone_req_option_list (ReqOption *req_option)
1318 {
1319   ReqOption *new_req_option;
1320
1321   if (req_option == NULL)
1322     return NULL;
1323
1324   new_req_option = (ReqOption *) xmalloc (sizeof (ReqOption));
1325   new_req_option->or_option_terms = NULL;
1326   new_req_option->next = NULL;
1327   new_req_option->or_option_terms =
1328     clone_req_or_option_list (req_option->or_option_terms);
1329   new_req_option->next = clone_req_option_list (req_option->next);
1330   return new_req_option;
1331 }
1332
1333
1334 static bfd_boolean
1335 parse_option_cond (const char *s, ReqOption *option)
1336 {
1337   int i;
1338   split_rec option_term_rec;
1339
1340   /* All option or conditions are of the form:
1341      optionA + no-optionB + ...
1342      "Ands" are divided by "?".  */
1343
1344   init_split_rec (&option_term_rec);
1345   split_string (&option_term_rec, s, '+', TRUE);
1346
1347   if (option_term_rec.count == 0)
1348     {
1349       clear_split_rec (&option_term_rec);
1350       return FALSE;
1351     }
1352
1353   for (i = 0; i < option_term_rec.count; i++)
1354     {
1355       char *option_name = option_term_rec.vec[i];
1356       bfd_boolean is_true = TRUE;
1357       ReqOrOption *req;
1358       ReqOrOption **r_p;
1359
1360       if (strncmp (option_name, "no-", 3) == 0)
1361         {
1362           option_name = xstrdup (&option_name[3]);
1363           is_true = FALSE;
1364         }
1365       else
1366         option_name = xstrdup (option_name);
1367
1368       req = (ReqOrOption *) xmalloc (sizeof (ReqOrOption));
1369       req->option_name = option_name;
1370       req->is_true = is_true;
1371       req->next = NULL;
1372
1373       /* Append to list.  */
1374       for (r_p = &option->or_option_terms; (*r_p) != NULL;
1375            r_p = &(*r_p)->next)
1376         ;
1377       (*r_p) = req;
1378     }
1379   return TRUE;
1380 }
1381
1382
1383 /* Parse a string like:
1384    "insn op1, op2, op3, op4 | op1 != op2 | op2 == op3 | op4 == 1".
1385    I.E., instruction "insn" with 4 operands where operand 1 and 2 are not
1386    the same and operand 2 and 3 are the same and operand 4 is 1.
1387
1388    or:
1389
1390    "insn op1 | op1 == 1 / density + boolean / no-useroption".
1391    i.e. instruction "insn" with 1 operands where operand 1 is 1
1392    when "density" or "boolean" options are available and
1393    "useroption" is not available.
1394
1395    Because the current implementation of this parsing scheme uses
1396    split_string, it requires that '|' and '?' are only used as
1397    delimiters for predicates and required options.  */
1398
1399 static bfd_boolean
1400 parse_insn_pattern (const char *in, insn_pattern *insn)
1401 {
1402   split_rec rec;
1403   split_rec optionrec;
1404   int i;
1405
1406   init_insn_pattern (insn);
1407
1408   init_split_rec (&optionrec);
1409   split_string (&optionrec, in, '?', TRUE);
1410   if (optionrec.count == 0)
1411     {
1412       clear_split_rec (&optionrec);
1413       return FALSE;
1414     }
1415
1416   init_split_rec (&rec);
1417
1418   split_string (&rec, optionrec.vec[0], '|', TRUE);
1419
1420   if (rec.count == 0)
1421     {
1422       clear_split_rec (&rec);
1423       clear_split_rec (&optionrec);
1424       return FALSE;
1425     }
1426
1427   if (!parse_insn_templ (rec.vec[0], &insn->t))
1428     {
1429       clear_split_rec (&rec);
1430       clear_split_rec (&optionrec);
1431       return FALSE;
1432     }
1433
1434   for (i = 1; i < rec.count; i++)
1435     {
1436       precond_e *cond = (precond_e *) xmalloc (sizeof (precond_e));
1437
1438       if (!parse_precond (rec.vec[i], cond))
1439         {
1440           clear_split_rec (&rec);
1441           clear_split_rec (&optionrec);
1442           clear_insn_pattern (insn);
1443           return FALSE;
1444         }
1445
1446       /* Append the condition.  */
1447       *insn->preconds.tail = cond;
1448       insn->preconds.tail = &cond->next;
1449     }
1450
1451   for (i = 1; i < optionrec.count; i++)
1452     {
1453       /* Handle the option conditions.  */
1454       ReqOption **r_p;
1455       ReqOption *req_option = (ReqOption *) xmalloc (sizeof (ReqOption));
1456       req_option->or_option_terms = NULL;
1457       req_option->next = NULL;
1458
1459       if (!parse_option_cond (optionrec.vec[i], req_option))
1460         {
1461           clear_split_rec (&rec);
1462           clear_split_rec (&optionrec);
1463           clear_insn_pattern (insn);
1464           clear_req_option_list (&req_option);
1465           return FALSE;
1466         }
1467
1468       /* Append the condition.  */
1469       for (r_p = &insn->options; (*r_p) != NULL; r_p = &(*r_p)->next)
1470         ;
1471
1472       (*r_p) = req_option;
1473     }
1474
1475   clear_split_rec (&rec);
1476   clear_split_rec (&optionrec);
1477   return TRUE;
1478 }
1479
1480
1481 static bfd_boolean
1482 parse_insn_repl (const char *in, insn_repl *r_p)
1483 {
1484   /* This is a list of instruction templates separated by ';'.  */
1485   split_rec rec;
1486   int i;
1487
1488   split_string (&rec, in, ';', TRUE);
1489
1490   for (i = 0; i < rec.count; i++)
1491     {
1492       insn_repl_e *e = (insn_repl_e *) xmalloc (sizeof (insn_repl_e));
1493
1494       e->next = NULL;
1495
1496       if (!parse_insn_templ (rec.vec[i], &e->t))
1497         {
1498           free (e);
1499           clear_insn_repl (r_p);
1500           return FALSE;
1501         }
1502       *r_p->tail = e;
1503       r_p->tail = &e->next;
1504     }
1505   return TRUE;
1506 }
1507
1508
1509 static bfd_boolean
1510 transition_applies (insn_pattern *initial_insn,
1511                     const char *from_string ATTRIBUTE_UNUSED,
1512                     const char *to_string ATTRIBUTE_UNUSED)
1513 {
1514   ReqOption *req_option;
1515
1516   for (req_option = initial_insn->options;
1517        req_option != NULL;
1518        req_option = req_option->next)
1519     {
1520       ReqOrOption *req_or_option = req_option->or_option_terms;
1521
1522       if (req_or_option == NULL
1523           || req_or_option->next != NULL)
1524         continue;
1525
1526       if (strncmp (req_or_option->option_name, "IsaUse", 6) == 0)
1527         {
1528           bfd_boolean option_available = FALSE;
1529           char *option_name = req_or_option->option_name + 6;
1530           if (!strcmp (option_name, "DensityInstruction"))
1531             option_available = (XCHAL_HAVE_DENSITY == 1);
1532           else if (!strcmp (option_name, "L32R"))
1533             option_available = (XCHAL_HAVE_L32R == 1);
1534           else if (!strcmp (option_name, "Const16"))
1535             option_available = (XCHAL_HAVE_CONST16 == 1);
1536           else if (!strcmp (option_name, "Loops"))
1537             option_available = (XCHAL_HAVE_LOOPS == 1);
1538           else if (!strcmp (option_name, "WideBranches"))
1539             option_available = (XCHAL_HAVE_WIDE_BRANCHES == 1);
1540           else if (!strcmp (option_name, "PredictedBranches"))
1541             option_available = (XCHAL_HAVE_PREDICTED_BRANCHES == 1);
1542           else if (!strcmp (option_name, "Booleans"))
1543             option_available = (XCHAL_HAVE_BOOLEANS == 1);
1544           else
1545             as_warn (_("invalid configuration option '%s' in transition rule '%s'"),
1546                      req_or_option->option_name, from_string);
1547           if ((option_available ^ req_or_option->is_true) != 0)
1548             return FALSE;
1549         }
1550       else if (strcmp (req_or_option->option_name, "realnop") == 0)
1551         {
1552           bfd_boolean nop_available =
1553             (xtensa_opcode_lookup (xtensa_default_isa, "nop")
1554              != XTENSA_UNDEFINED);
1555           if ((nop_available ^ req_or_option->is_true) != 0)
1556             return FALSE;
1557         }
1558     }
1559   return TRUE;
1560 }
1561
1562
1563 static bfd_boolean
1564 wide_branch_opcode (const char *opcode_name,
1565                     char *suffix,
1566                     xtensa_opcode *popcode)
1567 {
1568   xtensa_isa isa = xtensa_default_isa;
1569   xtensa_opcode opcode;
1570   static char wbr_name_buf[20];
1571
1572   if (strncmp (opcode_name, "WIDE.", 5) != 0)
1573     return FALSE;
1574
1575   strcpy (wbr_name_buf, opcode_name + 5);
1576   strcat (wbr_name_buf, suffix);
1577   opcode = xtensa_opcode_lookup (isa, wbr_name_buf);
1578   if (opcode != XTENSA_UNDEFINED)
1579     {
1580       *popcode = opcode;
1581       return TRUE;
1582     }
1583
1584   return FALSE;
1585 }
1586
1587
1588 static TransitionRule *
1589 build_transition (insn_pattern *initial_insn,
1590                   insn_repl *replace_insns,
1591                   const char *from_string,
1592                   const char *to_string)
1593 {
1594   TransitionRule *tr = NULL;
1595   xtensa_opcode opcode;
1596   xtensa_isa isa = xtensa_default_isa;
1597   BuildInstr *literal_bi;
1598
1599   opname_map_e *op1;
1600   opname_map_e *op2;
1601
1602   precond_e *precond;
1603   insn_repl_e *r;
1604
1605   if (!wide_branch_opcode (initial_insn->t.opcode_name, ".w18", &opcode)
1606       && !wide_branch_opcode (initial_insn->t.opcode_name, ".w15", &opcode))
1607     opcode = xtensa_opcode_lookup (isa, initial_insn->t.opcode_name);
1608
1609   if (opcode == XTENSA_UNDEFINED)
1610     {
1611       /* It is OK to not be able to translate some of these opcodes.  */
1612       return NULL;
1613     }
1614
1615
1616   if (xtensa_opcode_num_operands (isa, opcode)
1617       != insn_templ_operand_count (&initial_insn->t))
1618     {
1619       /* This is also OK because there are opcodes that
1620          have different numbers of operands on different
1621          architecture variations.  */
1622       return NULL;
1623     }
1624
1625   tr = (TransitionRule *) xmalloc (sizeof (TransitionRule));
1626   tr->opcode = opcode;
1627   tr->conditions = NULL;
1628   tr->to_instr = NULL;
1629
1630   /* Build the conditions. First, equivalent operand condition....  */
1631   for (op1 = initial_insn->t.operand_map.head; op1 != NULL; op1 = op1->next)
1632     {
1633       for (op2 = op1->next; op2 != NULL; op2 = op2->next)
1634         {
1635           if (same_operand_name (op1, op2))
1636             {
1637               append_value_condition (tr, OP_EQUAL,
1638                                       op1->operand_num, op2->operand_num);
1639             }
1640         }
1641     }
1642
1643   /* Now the condition that an operand value must be a constant....  */
1644   for (op1 = initial_insn->t.operand_map.head; op1 != NULL; op1 = op1->next)
1645     {
1646       if (op_is_constant (op1))
1647         {
1648           append_constant_value_condition (tr,
1649                                            OP_EQUAL,
1650                                            op1->operand_num,
1651                                            op_get_constant (op1));
1652         }
1653     }
1654
1655
1656   /* Now add the explicit preconditions listed after the "|" in the spec.
1657      These are currently very limited, so we do a special case
1658      parse for them.  We expect spaces, opname != opname.  */
1659   for (precond = initial_insn->preconds.head;
1660        precond != NULL;
1661        precond = precond->next)
1662     {
1663       op1 = NULL;
1664       op2 = NULL;
1665
1666       if (precond->opname1)
1667         {
1668           op1 = get_opmatch (&initial_insn->t.operand_map, precond->opname1);
1669           if (op1 == NULL)
1670             as_fatal (_("opcode '%s': no bound opname '%s' "
1671                         "for precondition in '%s'"),
1672                       xtensa_opcode_name (isa, opcode),
1673                       precond->opname1, from_string);
1674         }
1675
1676       if (precond->opname2)
1677         {
1678           op2 = get_opmatch (&initial_insn->t.operand_map, precond->opname2);
1679           if (op2 == NULL)
1680             as_fatal (_("opcode '%s': no bound opname '%s' "
1681                         "for precondition in %s"),
1682                       xtensa_opcode_name (isa, opcode),
1683                       precond->opname2, from_string);
1684         }
1685
1686       if (op1 == NULL && op2 == NULL)
1687         as_fatal (_("opcode '%s': precondition only contains "
1688                     "constants in '%s'"),
1689                   xtensa_opcode_name (isa, opcode), from_string);
1690       else if (op1 != NULL && op2 != NULL)
1691         append_value_condition (tr, precond->cmpop,
1692                                 op1->operand_num, op2->operand_num);
1693       else if (op2 == NULL)
1694         append_constant_value_condition (tr, precond->cmpop,
1695                                          op1->operand_num, precond->opval2);
1696       else
1697         append_constant_value_condition (tr, precond->cmpop,
1698                                          op2->operand_num, precond->opval1);
1699     }
1700
1701   tr->options = clone_req_option_list (initial_insn->options);
1702
1703   /* Generate the replacement instructions.  Some of these
1704      "instructions" are actually labels and literals.  There can be at
1705      most one literal and at most one label.  A literal must be defined
1706      (e.g., "LITERAL %imm") before use (e.g., "%LITERAL").  The labels
1707      can be used before they are defined.  Also there are a number of
1708      special operands (e.g., HI24S).  */
1709
1710   literal_bi = NULL;
1711   for (r = replace_insns->head; r != NULL; r = r->next)
1712     {
1713       BuildInstr *bi;
1714       const char *opcode_name;
1715       int operand_count;
1716       opname_map_e *op;
1717       const char *fn_name;
1718       const char *operand_arg_name;
1719
1720       bi = (BuildInstr *) xmalloc (sizeof (BuildInstr));
1721       append_build_insn (tr, bi);
1722
1723       bi->opcode = XTENSA_UNDEFINED;
1724       bi->ops = NULL;
1725       bi->next = NULL;
1726
1727       opcode_name = r->t.opcode_name;
1728       operand_count = insn_templ_operand_count (&r->t);
1729
1730       if (strcmp (opcode_name, "LITERAL") == 0)
1731         {
1732           bi->typ = INSTR_LITERAL_DEF;
1733           if (operand_count != 1)
1734             as_fatal (_("expected one operand for generated literal"));
1735           literal_bi = bi;
1736         }
1737       else if (strcmp (opcode_name, "LABEL") == 0)
1738         {
1739           bi->typ = INSTR_LABEL_DEF;
1740           if (operand_count != 0)
1741             as_fatal (_("expected 0 operands for generated label"));
1742         }
1743       else
1744         {
1745           bi->typ = INSTR_INSTR;
1746           if (wide_branch_opcode (opcode_name, ".w18", &bi->opcode)
1747               || wide_branch_opcode (opcode_name, ".w15", &bi->opcode))
1748             opcode_name = xtensa_opcode_name (isa, bi->opcode);
1749           else
1750             bi->opcode = xtensa_opcode_lookup (isa, opcode_name);
1751
1752           if (bi->opcode == XTENSA_UNDEFINED)
1753             {
1754               as_warn (_("invalid opcode '%s' in transition rule '%s'"),
1755                        opcode_name, to_string);
1756               return NULL;
1757             }
1758
1759           /* Check for the right number of ops.  */
1760           if (xtensa_opcode_num_operands (isa, bi->opcode)
1761               != (int) operand_count)
1762             as_fatal (_("opcode '%s': replacement does not have %d ops"),
1763                       opcode_name,
1764                       xtensa_opcode_num_operands (isa, bi->opcode));
1765         }
1766
1767       for (op = r->t.operand_map.head; op != NULL; op = op->next)
1768         {
1769           unsigned idnum;
1770
1771           if (op_is_constant (op))
1772             append_constant_op (bi, op->operand_num, op_get_constant (op));
1773           else if (strcmp (op->operand_name, "%LITERAL") == 0)
1774             {
1775               if (! literal_bi || ! literal_bi->ops || literal_bi->ops->next)
1776                 as_fatal (_("opcode '%s': cannot find literal definition"),
1777                           opcode_name);
1778               append_literal_op (bi, op->operand_num,
1779                                  literal_bi->ops->op_data);
1780             }
1781           else if (strcmp (op->operand_name, "%LABEL") == 0)
1782             append_label_op (bi, op->operand_num);
1783           else if (op->operand_name[0] == 'a'
1784                    && parse_constant (op->operand_name + 1, &idnum))
1785             append_constant_op (bi, op->operand_num, idnum);
1786           else if (op->operand_name[0] == '%')
1787             {
1788               opname_map_e *orig_op;
1789               orig_op = get_opmatch (&initial_insn->t.operand_map,
1790                                      op->operand_name);
1791               if (orig_op == NULL)
1792                 as_fatal (_("opcode %s: unidentified operand '%s' in '%s'"),
1793                           opcode_name, op->operand_name, to_string);
1794               append_field_op (bi, op->operand_num, orig_op->operand_num);
1795             }
1796           else if (parse_special_fn (op->operand_name,
1797                                      &fn_name, &operand_arg_name))
1798             {
1799               opname_map_e *orig_op;
1800               OpType typ = OP_CONSTANT;
1801
1802               if (strcmp (fn_name, "LOW8") == 0)
1803                 typ = OP_OPERAND_LOW8;
1804               else if (strcmp (fn_name, "HI24S") == 0)
1805                 typ = OP_OPERAND_HI24S;
1806               else if (strcmp (fn_name, "F32MINUS") == 0)
1807                 typ = OP_OPERAND_F32MINUS;
1808               else if (strcmp (fn_name, "LOW16U") == 0)
1809                 typ = OP_OPERAND_LOW16U;
1810               else if (strcmp (fn_name, "HI16U") == 0)
1811                 typ = OP_OPERAND_HI16U;
1812               else
1813                 as_fatal (_("unknown user-defined function %s"), fn_name);
1814
1815               orig_op = get_opmatch (&initial_insn->t.operand_map,
1816                                      operand_arg_name);
1817               if (orig_op == NULL)
1818                 as_fatal (_("opcode %s: unidentified operand '%s' in '%s'"),
1819                           opcode_name, op->operand_name, to_string);
1820               append_user_fn_field_op (bi, op->operand_num,
1821                                        typ, orig_op->operand_num);
1822             }
1823           else
1824             as_fatal (_("opcode %s: could not parse operand '%s' in '%s'"),
1825                       opcode_name, op->operand_name, to_string);
1826         }
1827     }
1828
1829   return tr;
1830 }
1831
1832
1833 static TransitionTable *
1834 build_transition_table (const string_pattern_pair *transitions,
1835                         int transition_count,
1836                         transition_cmp_fn cmp)
1837 {
1838   TransitionTable *table = NULL;
1839   int num_opcodes = xtensa_isa_num_opcodes (xtensa_default_isa);
1840   int i, tnum;
1841
1842   if (table != NULL)
1843     return table;
1844
1845   /* Otherwise, build it now.  */
1846   table = (TransitionTable *) xmalloc (sizeof (TransitionTable));
1847   table->num_opcodes = num_opcodes;
1848   table->table =
1849     (TransitionList **) xmalloc (sizeof (TransitionTable *) * num_opcodes);
1850
1851   for (i = 0; i < num_opcodes; i++)
1852     table->table[i] = NULL;
1853
1854   for (tnum = 0; tnum < transition_count; tnum++)
1855     {
1856       const char *from_string = transitions[tnum].pattern;
1857       const char *to_string = transitions[tnum].replacement;
1858
1859       insn_pattern initial_insn;
1860       insn_repl replace_insns;
1861       TransitionRule *tr;
1862
1863       init_insn_pattern (&initial_insn);
1864       if (!parse_insn_pattern (from_string, &initial_insn))
1865         as_fatal (_("could not parse INSN_PATTERN '%s'"), from_string);
1866
1867       init_insn_repl (&replace_insns);
1868       if (!parse_insn_repl (to_string, &replace_insns))
1869         as_fatal (_("could not parse INSN_REPL '%s'"), to_string);
1870
1871       if (transition_applies (&initial_insn, from_string, to_string))
1872         {
1873           tr = build_transition (&initial_insn, &replace_insns,
1874                                  from_string, to_string);
1875           if (tr)
1876             append_transition (table, tr->opcode, tr, cmp);
1877           else
1878             {
1879 #if TENSILICA_DEBUG
1880               as_warn (_("could not build transition for %s => %s"),
1881                        from_string, to_string);
1882 #endif
1883             }
1884         }
1885
1886       clear_insn_repl (&replace_insns);
1887       clear_insn_pattern (&initial_insn);
1888     }
1889   return table;
1890 }
1891
1892 \f
1893 extern TransitionTable *
1894 xg_build_widen_table (transition_cmp_fn cmp)
1895 {
1896   static TransitionTable *table = NULL;
1897   if (table == NULL)
1898     table = build_transition_table (widen_spec_list, WIDEN_COUNT, cmp);
1899   return table;
1900 }
1901
1902
1903 extern TransitionTable *
1904 xg_build_simplify_table (transition_cmp_fn cmp)
1905 {
1906   static TransitionTable *table = NULL;
1907   if (table == NULL)
1908     table = build_transition_table (simplify_spec_list, SIMPLIFY_COUNT, cmp);
1909   return table;
1910 }