gas/config/xtensa-relax.c

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