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