gas/config/xtensa-relax.c

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