gas/config/xtensa-relax.c

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