gas/config/xtensa-relax.c

   1 /* Table of relaxations for Xtensa assembly.
   2    Copyright 2003, 2004, 2005, 2007 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'
  53                       | 'LITERAL' VARIABLE
  54
  55    The operands in a PRECOND must be constants or variables bound by
  56    the INSN_PATTERN.
  57
  58    The configuration options define a predicate on the availability of
  59    options which must be TRUE for this rule to be valid.  Examples are
  60    requiring "density" for replacements with density instructions,
  61    requiring "const16" for replacements that require const16
  62    instructions, etc.  The names are interpreted by the assembler to a
  63    truth value for a particular frag.
  64
  65    The operands in the INSN_REPL must be constants, variables bound in
  66    the associated INSN_PATTERN, special variables that are bound in
  67    the INSN_REPL by LABEL or LITERAL definitions, or special value
  68    manipulation functions.
  69
  70    A simple example of a replacement pattern:
  71    {"movi.n %as,%imm", "movi %as,%imm"} would convert the narrow
  72    movi.n instruction to the wide movi instruction.
  73
  74    A more complex example of a branch around:
  75    {"beqz %as,%label", "bnez %as,%LABEL;j %label;LABEL"}
  76    would convert a branch to a negated branch to the following instruction
  77    with a jump to the original label.
  78
  79    An Xtensa-specific example that generates a literal:
  80    {"movi %at,%imm", "LITERAL %imm; l32r %at,%LITERAL"}
  81    will convert a movi instruction to an l32r of a literal
  82    literal defined in the literal pool.
  83
  84    Even more complex is a conversion of a load with immediate offset
  85    to a load of a freshly generated literal, an explicit add and
  86    a load with 0 offset.  This transformation is only valid, though
  87    when the first and second operands are not the same as specified
  88    by the "| %at!=%as" precondition clause.
  89    {"l32i %at,%as,%imm | %at!=%as",
  90    "LITERAL %imm; l32r %at,%LITERAL; add %at,%at,%as; l32i %at,%at,0"}
  91
  92    There is special case for loop instructions here, but because we do
  93    not currently have the ability to represent the difference of two
  94    symbols, the conversion requires special code in the assembler to
  95    write the operands of the addi/addmi pair representing the
  96    difference of the old and new loop end label.  */
  97
  98 #include "as.h"
  99 #include "xtensa-isa.h"
 100 #include "xtensa-relax.h"
 101 #include <stddef.h>
 102 #include "xtensa-config.h"
 103
 104 #ifndef XCHAL_HAVE_WIDE_BRANCHES
 105 #define XCHAL_HAVE_WIDE_BRANCHES 0
 106 #endif
 107
 108 /* Imported from bfd.  */
 109 extern xtensa_isa xtensa_default_isa;
 110
 111 /* The opname_list is a small list of names that we use for opcode and
 112    operand variable names to simplify ownership of these commonly used
 113    strings.  Strings entered in the table can be compared by pointer
 114    equality.  */
 115
 116 typedef struct opname_list_struct opname_list;
 117 typedef opname_list opname_e;
 118
 119 struct opname_list_struct
 120 {
 121   char *opname;
 122   opname_list *next;
 123 };
 124
 125 static opname_list *local_opnames = NULL;
 126
 127
 128 /* The "opname_map" and its element structure "opname_map_e" are used
 129    for binding an operand number to a name or a constant.  */
 130
 131 typedef struct opname_map_e_struct opname_map_e;
 132 typedef struct opname_map_struct opname_map;
 133
 134 struct opname_map_e_struct
 135 {
 136   const char *operand_name;     /* If null, then use constant_value.  */
 137   int operand_num;
 138   unsigned constant_value;
 139   opname_map_e *next;
 140 };
 141
 142 struct opname_map_struct
 143 {
 144   opname_map_e *head;
 145   opname_map_e **tail;
 146 };
 147
 148 /* The "precond_list" and its element structure "precond_e" represents
 149    explicit preconditions comparing operand variables and constants.
 150    In the "precond_e" structure, a variable is identified by the name
 151    in the "opname" field.   If that field is NULL, then the operand
 152    is the constant in field "opval".  */
 153
 154 typedef struct precond_e_struct precond_e;
 155 typedef struct precond_list_struct precond_list;
 156
 157 struct precond_e_struct
 158 {
 159   const char *opname1;
 160   unsigned opval1;
 161   CmpOp cmpop;
 162   const char *opname2;
 163   unsigned opval2;
 164   precond_e *next;
 165 };
 166
 167 struct precond_list_struct
 168 {
 169   precond_e *head;
 170   precond_e **tail;
 171 };
 172
 173
 174 /* The insn_templ represents the INSN_TEMPL instruction template.  It
 175    is an opcode name with a list of operands.  These are used for
 176    instruction patterns and replacement patterns.  */
 177
 178 typedef struct insn_templ_struct insn_templ;
 179 struct insn_templ_struct
 180 {
 181   const char *opcode_name;
 182   opname_map operand_map;
 183 };
 184
 185
 186 /* The insn_pattern represents an INSN_PATTERN instruction pattern.
 187    It is an instruction template with preconditions that specify when
 188    it actually matches a given instruction.  */
 189
 190 typedef struct insn_pattern_struct insn_pattern;
 191 struct insn_pattern_struct
 192 {
 193   insn_templ t;
 194   precond_list preconds;
 195   ReqOptionList *options;
 196 };
 197
 198
 199 /* The "insn_repl" and associated element structure "insn_repl_e"
 200    instruction replacement list is a list of
 201    instructions/LITERALS/LABELS with constant operands or operands
 202    with names bound to the operand names in the associated pattern.  */
 203
 204 typedef struct insn_repl_e_struct insn_repl_e;
 205 struct insn_repl_e_struct
 206 {
 207   insn_templ t;
 208   insn_repl_e *next;
 209 };
 210
 211 typedef struct insn_repl_struct insn_repl;
 212 struct insn_repl_struct
 213 {
 214   insn_repl_e *head;
 215   insn_repl_e **tail;
 216 };
 217
 218
 219 /* The split_rec is a vector of allocated char * pointers.  */
 220
 221 typedef struct split_rec_struct split_rec;
 222 struct split_rec_struct
 223 {
 224   char **vec;
 225   int count;
 226 };
 227
 228 /* The "string_pattern_pair" is a set of pairs containing instruction
 229    patterns and replacement strings.  */
 230
 231 typedef struct string_pattern_pair_struct string_pattern_pair;
 232 struct string_pattern_pair_struct
 233 {
 234   const char *pattern;
 235   const char *replacement;
 236 };
 237
 238 \f
 239 /* The widen_spec_list is a list of valid substitutions that generate
 240    wider representations.  These are generally used to specify
 241    replacements for instructions whose immediates do not fit their
 242    encodings.  A valid transition may require multiple steps of
 243    one-to-one instruction replacements with a final multiple
 244    instruction replacement.  As an example, here are the transitions
 245    required to replace an 'addi.n' with an 'addi', 'addmi'.
 246
 247      addi.n a4, 0x1010
 248      => addi a4, 0x1010
 249      => addmi a4, 0x1010
 250      => addmi a4, 0x1000, addi a4, 0x10.  */
 251
 252 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    "LITERAL %imm; l32r %at,%LITERAL"},
 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    "LITERAL %imm; l32r %ar,%LITERAL; 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    "LITERAL %imm; l32r %at,%LITERAL; add %at,%at,%as; l8ui %at,%at,0"},
 289   {"l16si %at,%as,%imm | %at!=%as ? IsaUseL32R",
 290    "LITERAL %imm; l32r %at,%LITERAL; add %at,%at,%as; l16si %at,%at,0"},
 291   {"l16ui %at,%as,%imm | %at!=%as ? IsaUseL32R",
 292    "LITERAL %imm; l32r %at,%LITERAL; add %at,%at,%as; l16ui %at,%at,0"},
 293   {"l32i %at,%as,%imm | %at!=%as ? IsaUseL32R",
 294    "LITERAL %imm; l32r %at,%LITERAL; 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,%LABEL;"
 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    "LABEL"},
 320   {"loopgtz %as,%label | %as!=1 ? IsaUseLoops",
 321    "beqz    %as,%label;"
 322    "bltz    %as,%label;"
 323    "loopgtz %as,%LABEL;"
 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    "LABEL"},
 333   {"loopnez %as,%label | %as!=1 ? IsaUseLoops",
 334    "beqz     %as,%label;"
 335    "loopnez %as,%LABEL;"
 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    "LABEL"},
 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", "WIDE.beqz %as,%label"},
 353   {"bnez %as,%label ? IsaUseWideBranches", "WIDE.bnez %as,%label"},
 354   {"bgez %as,%label ? IsaUseWideBranches", "WIDE.bgez %as,%label"},
 355   {"bltz %as,%label ? IsaUseWideBranches", "WIDE.bltz %as,%label"},
 356   {"beqi %as,%imm,%label ? IsaUseWideBranches", "WIDE.beqi %as,%imm,%label"},
 357   {"bnei %as,%imm,%label ? IsaUseWideBranches", "WIDE.bnei %as,%imm,%label"},
 358   {"bgei %as,%imm,%label ? IsaUseWideBranches", "WIDE.bgei %as,%imm,%label"},
 359   {"blti %as,%imm,%label ? IsaUseWideBranches", "WIDE.blti %as,%imm,%label"},
 360   {"bgeui %as,%imm,%label ? IsaUseWideBranches", "WIDE.bgeui %as,%imm,%label"},
 361   {"bltui %as,%imm,%label ? IsaUseWideBranches", "WIDE.bltui %as,%imm,%label"},
 362   {"bbci %as,%imm,%label ? IsaUseWideBranches", "WIDE.bbci %as,%imm,%label"},
 363   {"bbsi %as,%imm,%label ? IsaUseWideBranches", "WIDE.bbsi %as,%imm,%label"},
 364   {"beq %as,%at,%label ? IsaUseWideBranches", "WIDE.beq %as,%at,%label"},
 365   {"bne %as,%at,%label ? IsaUseWideBranches", "WIDE.bne %as,%at,%label"},
 366   {"bge %as,%at,%label ? IsaUseWideBranches", "WIDE.bge %as,%at,%label"},
 367   {"blt %as,%at,%label ? IsaUseWideBranches", "WIDE.blt %as,%at,%label"},
 368   {"bgeu %as,%at,%label ? IsaUseWideBranches", "WIDE.bgeu %as,%at,%label"},
 369   {"bltu %as,%at,%label ? IsaUseWideBranches", "WIDE.bltu %as,%at,%label"},
 370   {"bany %as,%at,%label ? IsaUseWideBranches", "WIDE.bany %as,%at,%label"},
 371   {"bnone %as,%at,%label ? IsaUseWideBranches", "WIDE.bnone %as,%at,%label"},
 372   {"ball %as,%at,%label ? IsaUseWideBranches", "WIDE.ball %as,%at,%label"},
 373   {"bnall %as,%at,%label ? IsaUseWideBranches", "WIDE.bnall %as,%at,%label"},
 374   {"bbc %as,%at,%label ? IsaUseWideBranches", "WIDE.bbc %as,%at,%label"},
 375   {"bbs %as,%at,%label ? IsaUseWideBranches", "WIDE.bbs %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,%LABEL;j %label;LABEL"},
 380   {"bnez %as,%label ? IsaUseDensityInstruction", "beqz.n %as,%LABEL;j %label;LABEL"},
 381   {"beqz %as,%label", "bnez %as,%LABEL;j %label;LABEL"},
 382   {"bnez %as,%label", "beqz %as,%LABEL;j %label;LABEL"},
 383
 384   /* Widening expect-taken branches.  */
 385   {"beqzt %as,%label ? IsaUsePredictedBranches", "bnez %as,%LABEL;j %label;LABEL"},
 386   {"bnezt %as,%label ? IsaUsePredictedBranches", "beqz %as,%LABEL;j %label;LABEL"},
 387   {"beqt %as,%at,%label ? IsaUsePredictedBranches", "bne %as,%at,%LABEL;j %label;LABEL"},
 388   {"bnet %as,%at,%label ? IsaUsePredictedBranches", "beq %as,%at,%LABEL;j %label;LABEL"},
 389
 390   /* Widening branches from the Xtensa boolean option.  */
 391   {"bt %bs,%label ? IsaUseBooleans", "bf %bs,%LABEL;j %label;LABEL"},
 392   {"bf %bs,%label ? IsaUseBooleans", "bt %bs,%LABEL;j %label;LABEL"},
 393
 394   /* Other branch-around-jump widenings.  */
 395   {"bgez %as,%label", "bltz %as,%LABEL;j %label;LABEL"},
 396   {"bltz %as,%label", "bgez %as,%LABEL;j %label;LABEL"},
 397   {"beqi %as,%imm,%label", "bnei %as,%imm,%LABEL;j %label;LABEL"},
 398   {"bnei %as,%imm,%label", "beqi %as,%imm,%LABEL;j %label;LABEL"},
 399   {"bgei %as,%imm,%label", "blti %as,%imm,%LABEL;j %label;LABEL"},
 400   {"blti %as,%imm,%label", "bgei %as,%imm,%LABEL;j %label;LABEL"},
 401   {"bgeui %as,%imm,%label", "bltui %as,%imm,%LABEL;j %label;LABEL"},
 402   {"bltui %as,%imm,%label", "bgeui %as,%imm,%LABEL;j %label;LABEL"},
 403   {"bbci %as,%imm,%label", "bbsi %as,%imm,%LABEL;j %label;LABEL"},
 404   {"bbsi %as,%imm,%label", "bbci %as,%imm,%LABEL;j %label;LABEL"},
 405   {"beq %as,%at,%label", "bne %as,%at,%LABEL;j %label;LABEL"},
 406   {"bne %as,%at,%label", "beq %as,%at,%LABEL;j %label;LABEL"},
 407   {"bge %as,%at,%label", "blt %as,%at,%LABEL;j %label;LABEL"},
 408   {"blt %as,%at,%label", "bge %as,%at,%LABEL;j %label;LABEL"},
 409   {"bgeu %as,%at,%label", "bltu %as,%at,%LABEL;j %label;LABEL"},
 410   {"bltu %as,%at,%label", "bgeu %as,%at,%LABEL;j %label;LABEL"},
 411   {"bany %as,%at,%label", "bnone %as,%at,%LABEL;j %label;LABEL"},
 412   {"bnone %as,%at,%label", "bany %as,%at,%LABEL;j %label;LABEL"},
 413   {"ball %as,%at,%label", "bnall %as,%at,%LABEL;j %label;LABEL"},
 414   {"bnall %as,%at,%label", "ball %as,%at,%LABEL;j %label;LABEL"},
 415   {"bbc %as,%at,%label", "bbs %as,%at,%LABEL;j %label;LABEL"},
 416   {"bbs %as,%at,%label", "bbc %as,%at,%LABEL;j %label;LABEL"},
 417
 418   /* Expanding calls with literals.  */
 419   {"call0 %label,%ar0 ? IsaUseL32R",
 420    "LITERAL %label; l32r a0,%LITERAL; callx0 a0,%ar0"},
 421   {"call4 %label,%ar4 ? IsaUseL32R",
 422    "LITERAL %label; l32r a4,%LITERAL; callx4 a4,%ar4"},
 423   {"call8 %label,%ar8 ? IsaUseL32R",
 424    "LITERAL %label; l32r a8,%LITERAL; callx8 a8,%ar8"},
 425   {"call12 %label,%ar12 ? IsaUseL32R",
 426    "LITERAL %label; l32r a12,%LITERAL; 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)
 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 = 0;
 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)
 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 = 0;
 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 static bfd_boolean
 986 parse_special_fn (const char *name,
 987                   const char **fn_name_p,
 988                   const char **arg_name_p)
 989 {
 990   char *p_start;
 991   const char *p_end;
 992
 993   p_start = strchr (name, '(');
 994   if (p_start == NULL)
 995     return FALSE;
 996
 997   p_end = strchr (p_start, ')');
 998
 999   if (p_end == NULL)
1000     return FALSE;
1001
1002   if (p_end[1] != '\0')
1003     return FALSE;
1004
1005   *fn_name_p = enter_opname_n (name, p_start - name);
1006   *arg_name_p = enter_opname_n (p_start + 1, p_end - p_start - 1);
1007   return TRUE;
1008 }
1009
1010
1011 static const char *
1012 skip_white (const char *p)
1013 {
1014   if (p == NULL)
1015     return p;
1016   while (*p == ' ')
1017     ++p;
1018   return p;
1019 }
1020
1021
1022 static void
1023 trim_whitespace (char *in)
1024 {
1025   char *last_white = NULL;
1026   char *p = in;
1027
1028   while (p && *p != '\0')
1029     {
1030       while (*p == ' ')
1031         {
1032           if (last_white == NULL)
1033             last_white = p;
1034           p++;
1035         }
1036       if (*p != '\0')
1037         {
1038           last_white = NULL;
1039           p++;
1040         }
1041     }
1042   if (last_white)
1043     *last_white = '\0';
1044 }
1045
1046
1047 /* Split a string into component strings where "c" is the
1048    delimiter.  Place the result in the split_rec.  */
1049
1050 static void
1051 split_string (split_rec *rec,
1052               const char *in,
1053               char c,
1054               bfd_boolean elide_whitespace)
1055 {
1056   int cnt = 0;
1057   int i;
1058   const char *p = in;
1059
1060   while (p != NULL && *p != '\0')
1061     {
1062       cnt++;
1063       p = strchr (p, c);
1064       if (p)
1065         p++;
1066     }
1067   rec->count = cnt;
1068   rec->vec = NULL;
1069
1070   if (rec->count == 0)
1071     return;
1072
1073   rec->vec = (char **) xmalloc (sizeof (char *) * cnt);
1074   for (i = 0; i < cnt; i++)
1075     rec->vec[i] = 0;
1076
1077   p = in;
1078   for (i = 0; i < cnt; i++)
1079     {
1080       const char *q;
1081       int len;
1082
1083       q = p;
1084       if (elide_whitespace)
1085         q = skip_white (q);
1086
1087       p = strchr (q, c);
1088       if (p == NULL)
1089         rec->vec[i] = xstrdup (q);
1090       else
1091         {
1092           len = p - q;
1093           rec->vec[i] = (char *) xmalloc (sizeof (char) * (len + 1));
1094           strncpy (rec->vec[i], q, len);
1095           rec->vec[i][len] = '\0';
1096           p++;
1097         }
1098
1099       if (elide_whitespace)
1100         trim_whitespace (rec->vec[i]);
1101     }
1102 }
1103
1104
1105 static void
1106 clear_split_rec (split_rec *rec)
1107 {
1108   int i;
1109
1110   for (i = 0; i < rec->count; i++)
1111     free (rec->vec[i]);
1112
1113   if (rec->count > 0)
1114     free (rec->vec);
1115 }
1116
1117
1118 /* Initialize a split record.  The split record must be initialized
1119    before split_string is called.  */
1120
1121 static void
1122 init_split_rec (split_rec *rec)
1123 {
1124   rec->vec = NULL;
1125   rec->count = 0;
1126 }
1127
1128
1129 /* Parse an instruction template like "insn op1, op2, op3".  */
1130
1131 static bfd_boolean
1132 parse_insn_templ (const char *s, insn_templ *t)
1133 {
1134   const char *p = s;
1135   int insn_name_len;
1136   split_rec oprec;
1137   int i;
1138
1139   /* First find the first whitespace.  */
1140
1141   init_split_rec (&oprec);
1142
1143   p = skip_white (p);
1144   insn_name_len = strcspn (s, " ");
1145   if (insn_name_len == 0)
1146     return FALSE;
1147
1148   init_insn_templ (t);
1149   t->opcode_name = enter_opname_n (p, insn_name_len);
1150
1151   p = p + insn_name_len;
1152
1153   /* Split by ',' and skip beginning and trailing whitespace.  */
1154   split_string (&oprec, p, ',', TRUE);
1155
1156   for (i = 0; i < oprec.count; i++)
1157     {
1158       const char *opname = oprec.vec[i];
1159       opname_map_e *e = (opname_map_e *) xmalloc (sizeof (opname_map_e));
1160       e->next = NULL;
1161       e->operand_name = NULL;
1162       e->constant_value = 0;
1163       e->operand_num = i;
1164
1165       /* If it begins with a number, assume that it is a number.  */
1166       if (opname && opname[0] >= '0' && opname[0] <= '9')
1167         {
1168           unsigned val;
1169
1170           if (parse_constant (opname, &val))
1171             e->constant_value = val;
1172           else
1173             {
1174               free (e);
1175               clear_split_rec (&oprec);
1176               clear_insn_templ (t);
1177               return FALSE;
1178             }
1179         }
1180       else
1181         e->operand_name = enter_opname (oprec.vec[i]);
1182
1183       *t->operand_map.tail = e;
1184       t->operand_map.tail = &e->next;
1185     }
1186   clear_split_rec (&oprec);
1187   return TRUE;
1188 }
1189
1190
1191 static bfd_boolean
1192 parse_precond (const char *s, precond_e *precond)
1193 {
1194   /* All preconditions are currently of the form:
1195      a == b or a != b or a == k (where k is a constant).
1196      Later we may use some special functions like DENSITY == 1
1197      to identify when density is available.  */
1198
1199   const char *p = s;
1200   int len;
1201   precond->opname1 = NULL;
1202   precond->opval1 = 0;
1203   precond->cmpop = OP_EQUAL;
1204   precond->opname2 = NULL;
1205   precond->opval2 = 0;
1206   precond->next = NULL;
1207
1208   p = skip_white (p);
1209
1210   len = strcspn (p, " !=");
1211
1212   if (len == 0)
1213     return FALSE;
1214
1215   precond->opname1 = enter_opname_n (p, len);
1216   p = p + len;
1217   p = skip_white (p);
1218
1219   /* Check for "==" and "!=".  */
1220   if (strncmp (p, "==", 2) == 0)
1221     precond->cmpop = OP_EQUAL;
1222   else if (strncmp (p, "!=", 2) == 0)
1223     precond->cmpop = OP_NOTEQUAL;
1224   else
1225     return FALSE;
1226
1227   p = p + 2;
1228   p = skip_white (p);
1229
1230   /* No trailing whitespace from earlier parsing.  */
1231   if (p[0] >= '0' && p[0] <= '9')
1232     {
1233       unsigned val;
1234       if (parse_constant (p, &val))
1235         precond->opval2 = val;
1236       else
1237         return FALSE;
1238     }
1239   else
1240     precond->opname2 = enter_opname (p);
1241   return TRUE;
1242 }
1243
1244
1245 static void
1246 clear_req_or_option_list (ReqOrOption **r_p)
1247 {
1248   if (*r_p == NULL)
1249     return;
1250
1251   free ((*r_p)->option_name);
1252   clear_req_or_option_list (&(*r_p)->next);
1253   *r_p = NULL;
1254 }
1255
1256
1257 static void
1258 clear_req_option_list (ReqOption **r_p)
1259 {
1260   if (*r_p == NULL)
1261     return;
1262
1263   clear_req_or_option_list (&(*r_p)->or_option_terms);
1264   clear_req_option_list (&(*r_p)->next);
1265   *r_p = NULL;
1266 }
1267
1268
1269 static ReqOrOption *
1270 clone_req_or_option_list (ReqOrOption *req_or_option)
1271 {
1272   ReqOrOption *new_req_or_option;
1273
1274   if (req_or_option == NULL)
1275     return NULL;
1276
1277   new_req_or_option = (ReqOrOption *) xmalloc (sizeof (ReqOrOption));
1278   new_req_or_option->option_name = xstrdup (req_or_option->option_name);
1279   new_req_or_option->is_true = req_or_option->is_true;
1280   new_req_or_option->next = NULL;
1281   new_req_or_option->next = clone_req_or_option_list (req_or_option->next);
1282   return new_req_or_option;
1283 }
1284
1285
1286 static ReqOption *
1287 clone_req_option_list (ReqOption *req_option)
1288 {
1289   ReqOption *new_req_option;
1290
1291   if (req_option == NULL)
1292     return NULL;
1293
1294   new_req_option = (ReqOption *) xmalloc (sizeof (ReqOption));
1295   new_req_option->or_option_terms = NULL;
1296   new_req_option->next = NULL;
1297   new_req_option->or_option_terms =
1298     clone_req_or_option_list (req_option->or_option_terms);
1299   new_req_option->next = clone_req_option_list (req_option->next);
1300   return new_req_option;
1301 }
1302
1303
1304 static bfd_boolean
1305 parse_option_cond (const char *s, ReqOption *option)
1306 {
1307   int i;
1308   split_rec option_term_rec;
1309
1310   /* All option or conditions are of the form:
1311      optionA + no-optionB + ...
1312      "Ands" are divided by "?".  */
1313
1314   init_split_rec (&option_term_rec);
1315   split_string (&option_term_rec, s, '+', TRUE);
1316
1317   if (option_term_rec.count == 0)
1318     {
1319       clear_split_rec (&option_term_rec);
1320       return FALSE;
1321     }
1322
1323   for (i = 0; i < option_term_rec.count; i++)
1324     {
1325       char *option_name = option_term_rec.vec[i];
1326       bfd_boolean is_true = TRUE;
1327       ReqOrOption *req;
1328       ReqOrOption **r_p;
1329
1330       if (strncmp (option_name, "no-", 3) == 0)
1331         {
1332           option_name = xstrdup (&option_name[3]);
1333           is_true = FALSE;
1334         }
1335       else
1336         option_name = xstrdup (option_name);
1337
1338       req = (ReqOrOption *) xmalloc (sizeof (ReqOrOption));
1339       req->option_name = option_name;
1340       req->is_true = is_true;
1341       req->next = NULL;
1342
1343       /* Append to list.  */
1344       for (r_p = &option->or_option_terms; (*r_p) != NULL;
1345            r_p = &(*r_p)->next)
1346         ;
1347       (*r_p) = req;
1348     }
1349   return TRUE;
1350 }
1351
1352
1353 /* Parse a string like:
1354    "insn op1, op2, op3, op4 | op1 != op2 | op2 == op3 | op4 == 1".
1355    I.E., instruction "insn" with 4 operands where operand 1 and 2 are not
1356    the same and operand 2 and 3 are the same and operand 4 is 1.
1357
1358    or:
1359
1360    "insn op1 | op1 == 1 / density + boolean / no-useroption".
1361    i.e. instruction "insn" with 1 operands where operand 1 is 1
1362    when "density" or "boolean" options are available and
1363    "useroption" is not available.
1364
1365    Because the current implementation of this parsing scheme uses
1366    split_string, it requires that '|' and '?' are only used as
1367    delimiters for predicates and required options.  */
1368
1369 static bfd_boolean
1370 parse_insn_pattern (const char *in, insn_pattern *insn)
1371 {
1372   split_rec rec;
1373   split_rec optionrec;
1374   int i;
1375
1376   init_insn_pattern (insn);
1377
1378   init_split_rec (&optionrec);
1379   split_string (&optionrec, in, '?', TRUE);
1380   if (optionrec.count == 0)
1381     {
1382       clear_split_rec (&optionrec);
1383       return FALSE;
1384     }
1385
1386   init_split_rec (&rec);
1387
1388   split_string (&rec, optionrec.vec[0], '|', TRUE);
1389
1390   if (rec.count == 0)
1391     {
1392       clear_split_rec (&rec);
1393       clear_split_rec (&optionrec);
1394       return FALSE;
1395     }
1396
1397   if (!parse_insn_templ (rec.vec[0], &insn->t))
1398     {
1399       clear_split_rec (&rec);
1400       clear_split_rec (&optionrec);
1401       return FALSE;
1402     }
1403
1404   for (i = 1; i < rec.count; i++)
1405     {
1406       precond_e *cond = (precond_e *) xmalloc (sizeof (precond_e));
1407
1408       if (!parse_precond (rec.vec[i], cond))
1409         {
1410           clear_split_rec (&rec);
1411           clear_split_rec (&optionrec);
1412           clear_insn_pattern (insn);
1413           return FALSE;
1414         }
1415
1416       /* Append the condition.  */
1417       *insn->preconds.tail = cond;
1418       insn->preconds.tail = &cond->next;
1419     }
1420
1421   for (i = 1; i < optionrec.count; i++)
1422     {
1423       /* Handle the option conditions.  */
1424       ReqOption **r_p;
1425       ReqOption *req_option = (ReqOption *) xmalloc (sizeof (ReqOption));
1426       req_option->or_option_terms = NULL;
1427       req_option->next = NULL;
1428
1429       if (!parse_option_cond (optionrec.vec[i], req_option))
1430         {
1431           clear_split_rec (&rec);
1432           clear_split_rec (&optionrec);
1433           clear_insn_pattern (insn);
1434           clear_req_option_list (&req_option);
1435           return FALSE;
1436         }
1437
1438       /* Append the condition.  */
1439       for (r_p = &insn->options; (*r_p) != NULL; r_p = &(*r_p)->next)
1440         ;
1441
1442       (*r_p) = req_option;
1443     }
1444
1445   clear_split_rec (&rec);
1446   clear_split_rec (&optionrec);
1447   return TRUE;
1448 }
1449
1450
1451 static bfd_boolean
1452 parse_insn_repl (const char *in, insn_repl *r_p)
1453 {
1454   /* This is a list of instruction templates separated by ';'.  */
1455   split_rec rec;
1456   int i;
1457
1458   split_string (&rec, in, ';', TRUE);
1459
1460   for (i = 0; i < rec.count; i++)
1461     {
1462       insn_repl_e *e = (insn_repl_e *) xmalloc (sizeof (insn_repl_e));
1463
1464       e->next = NULL;
1465
1466       if (!parse_insn_templ (rec.vec[i], &e->t))
1467         {
1468           free (e);
1469           clear_insn_repl (r_p);
1470           return FALSE;
1471         }
1472       *r_p->tail = e;
1473       r_p->tail = &e->next;
1474     }
1475   return TRUE;
1476 }
1477
1478
1479 static bfd_boolean
1480 transition_applies (insn_pattern *initial_insn,
1481                     const char *from_string ATTRIBUTE_UNUSED,
1482                     const char *to_string ATTRIBUTE_UNUSED)
1483 {
1484   ReqOption *req_option;
1485
1486   for (req_option = initial_insn->options;
1487        req_option != NULL;
1488        req_option = req_option->next)
1489     {
1490       ReqOrOption *req_or_option = req_option->or_option_terms;
1491
1492       if (req_or_option == NULL
1493           || req_or_option->next != NULL)
1494         continue;
1495
1496       if (strncmp (req_or_option->option_name, "IsaUse", 6) == 0)
1497         {
1498           bfd_boolean option_available = FALSE;
1499           char *option_name = req_or_option->option_name + 6;
1500           if (!strcmp (option_name, "DensityInstruction"))
1501             option_available = (XCHAL_HAVE_DENSITY == 1);
1502           else if (!strcmp (option_name, "L32R"))
1503             option_available = (XCHAL_HAVE_L32R == 1);
1504           else if (!strcmp (option_name, "Const16"))
1505             option_available = (XCHAL_HAVE_CONST16 == 1);
1506           else if (!strcmp (option_name, "Loops"))
1507             option_available = (XCHAL_HAVE_LOOPS == 1);
1508           else if (!strcmp (option_name, "WideBranches"))
1509             option_available = (XCHAL_HAVE_WIDE_BRANCHES == 1);
1510           else if (!strcmp (option_name, "PredictedBranches"))
1511             option_available = (XCHAL_HAVE_PREDICTED_BRANCHES == 1);
1512           else if (!strcmp (option_name, "Booleans"))
1513             option_available = (XCHAL_HAVE_BOOLEANS == 1);
1514           else
1515             as_warn (_("invalid configuration option '%s' in transition rule '%s'"),
1516                      req_or_option->option_name, from_string);
1517           if ((option_available ^ req_or_option->is_true) != 0)
1518             return FALSE;
1519         }
1520       else if (strcmp (req_or_option->option_name, "realnop") == 0)
1521         {
1522           bfd_boolean nop_available =
1523             (xtensa_opcode_lookup (xtensa_default_isa, "nop")
1524              != XTENSA_UNDEFINED);
1525           if ((nop_available ^ req_or_option->is_true) != 0)
1526             return FALSE;
1527         }
1528     }
1529   return TRUE;
1530 }
1531
1532
1533 static bfd_boolean
1534 wide_branch_opcode (const char *opcode_name,
1535                     char *suffix,
1536                     xtensa_opcode *popcode)
1537 {
1538   xtensa_isa isa = xtensa_default_isa;
1539   xtensa_opcode opcode;
1540   static char wbr_name_buf[20];
1541
1542   if (strncmp (opcode_name, "WIDE.", 5) != 0)
1543     return FALSE;
1544
1545   strcpy (wbr_name_buf, opcode_name + 5);
1546   strcat (wbr_name_buf, suffix);
1547   opcode = xtensa_opcode_lookup (isa, wbr_name_buf);
1548   if (opcode != XTENSA_UNDEFINED)
1549     {
1550       *popcode = opcode;
1551       return TRUE;
1552     }
1553
1554   return FALSE;
1555 }
1556
1557
1558 static TransitionRule *
1559 build_transition (insn_pattern *initial_insn,
1560                   insn_repl *replace_insns,
1561                   const char *from_string,
1562                   const char *to_string)
1563 {
1564   TransitionRule *tr = NULL;
1565   xtensa_opcode opcode;
1566   xtensa_isa isa = xtensa_default_isa;
1567
1568   opname_map_e *op1;
1569   opname_map_e *op2;
1570
1571   precond_e *precond;
1572   insn_repl_e *r;
1573
1574   opcode = xtensa_opcode_lookup (isa, initial_insn->t.opcode_name);
1575   if (opcode == XTENSA_UNDEFINED)
1576     {
1577       /* It is OK to not be able to translate some of these opcodes.  */
1578       return NULL;
1579     }
1580
1581
1582   if (xtensa_opcode_num_operands (isa, opcode)
1583       != insn_templ_operand_count (&initial_insn->t))
1584     {
1585       /* This is also OK because there are opcodes that
1586          have different numbers of operands on different
1587          architecture variations.  */
1588       return NULL;
1589     }
1590
1591   tr = (TransitionRule *) xmalloc (sizeof (TransitionRule));
1592   tr->opcode = opcode;
1593   tr->conditions = NULL;
1594   tr->to_instr = NULL;
1595
1596   /* Build the conditions. First, equivalent operand condition....  */
1597   for (op1 = initial_insn->t.operand_map.head; op1 != NULL; op1 = op1->next)
1598     {
1599       for (op2 = op1->next; op2 != NULL; op2 = op2->next)
1600         {
1601           if (same_operand_name (op1, op2))
1602             {
1603               append_value_condition (tr, OP_EQUAL,
1604                                       op1->operand_num, op2->operand_num);
1605             }
1606         }
1607     }
1608
1609   /* Now the condition that an operand value must be a constant....  */
1610   for (op1 = initial_insn->t.operand_map.head; op1 != NULL; op1 = op1->next)
1611     {
1612       if (op_is_constant (op1))
1613         {
1614           append_constant_value_condition (tr,
1615                                            OP_EQUAL,
1616                                            op1->operand_num,
1617                                            op_get_constant (op1));
1618         }
1619     }
1620
1621
1622   /* Now add the explicit preconditions listed after the "|" in the spec.
1623      These are currently very limited, so we do a special case
1624      parse for them.  We expect spaces, opname != opname.  */
1625   for (precond = initial_insn->preconds.head;
1626        precond != NULL;
1627        precond = precond->next)
1628     {
1629       op1 = NULL;
1630       op2 = NULL;
1631
1632       if (precond->opname1)
1633         {
1634           op1 = get_opmatch (&initial_insn->t.operand_map, precond->opname1);
1635           if (op1 == NULL)
1636             as_fatal (_("opcode '%s': no bound opname '%s' "
1637                         "for precondition in '%s'"),
1638                       xtensa_opcode_name (isa, opcode),
1639                       precond->opname1, from_string);
1640         }
1641
1642       if (precond->opname2)
1643         {
1644           op2 = get_opmatch (&initial_insn->t.operand_map, precond->opname2);
1645           if (op2 == NULL)
1646             as_fatal (_("opcode '%s': no bound opname '%s' "
1647                         "for precondition in %s"),
1648                       xtensa_opcode_name (isa, opcode),
1649                       precond->opname2, from_string);
1650         }
1651
1652       if (op1 == NULL && op2 == NULL)
1653         as_fatal (_("opcode '%s': precondition only contains "
1654                     "constants in '%s'"),
1655                   xtensa_opcode_name (isa, opcode), from_string);
1656       else if (op1 != NULL && op2 != NULL)
1657         append_value_condition (tr, precond->cmpop,
1658                                 op1->operand_num, op2->operand_num);
1659       else if (op2 == NULL)
1660         append_constant_value_condition (tr, precond->cmpop,
1661                                          op1->operand_num, precond->opval2);
1662       else
1663         append_constant_value_condition (tr, precond->cmpop,
1664                                          op2->operand_num, precond->opval1);
1665     }
1666
1667   tr->options = clone_req_option_list (initial_insn->options);
1668
1669   /* Generate the replacement instructions.  Some of these
1670      "instructions" are actually labels and literals.  There can be at
1671      most one literal and at most one label.  A literal must be defined
1672      (e.g., "LITERAL %imm") before use (e.g., "%LITERAL").  The labels
1673      can be used before they are defined.  Also there are a number of
1674      special operands (e.g., HI24S).  */
1675
1676   for (r = replace_insns->head; r != NULL; r = r->next)
1677     {
1678       BuildInstr *bi;
1679       const char *opcode_name;
1680       int operand_count;
1681       opname_map_e *op;
1682       const char *fn_name;
1683       const char *operand_arg_name;
1684
1685       bi = (BuildInstr *) xmalloc (sizeof (BuildInstr));
1686       append_build_insn (tr, bi);
1687
1688       bi->opcode = XTENSA_UNDEFINED;
1689       bi->ops = NULL;
1690       bi->next = NULL;
1691
1692       opcode_name = r->t.opcode_name;
1693       operand_count = insn_templ_operand_count (&r->t);
1694
1695       if (strcmp (opcode_name, "LITERAL") == 0)
1696         {
1697           bi->typ = INSTR_LITERAL_DEF;
1698           if (operand_count != 1)
1699             as_fatal (_("expected one operand for generated literal"));
1700         }
1701       else if (strcmp (opcode_name, "LABEL") == 0)
1702         {
1703           bi->typ = INSTR_LABEL_DEF;
1704           if (operand_count != 0)
1705             as_fatal (_("expected 0 operands for generated label"));
1706         }
1707       else
1708         {
1709           bi->typ = INSTR_INSTR;
1710           if (wide_branch_opcode (opcode_name, ".w18", &bi->opcode)
1711               || wide_branch_opcode (opcode_name, ".w15", &bi->opcode))
1712             opcode_name = xtensa_opcode_name (isa, bi->opcode);
1713           else
1714             bi->opcode = xtensa_opcode_lookup (isa, opcode_name);
1715
1716           if (bi->opcode == XTENSA_UNDEFINED)
1717             {
1718               as_warn (_("invalid opcode '%s' in transition rule '%s'"),
1719                        opcode_name, to_string);
1720               return NULL;
1721             }
1722
1723           /* Check for the right number of ops.  */
1724           if (xtensa_opcode_num_operands (isa, bi->opcode)
1725               != (int) operand_count)
1726             as_fatal (_("opcode '%s': replacement does not have %d ops"),
1727                       opcode_name,
1728                       xtensa_opcode_num_operands (isa, bi->opcode));
1729         }
1730
1731       for (op = r->t.operand_map.head; op != NULL; op = op->next)
1732         {
1733           unsigned idnum;
1734
1735           if (op_is_constant (op))
1736             append_constant_op (bi, op->operand_num, op_get_constant (op));
1737           else if (strcmp (op->operand_name, "%LITERAL") == 0)
1738             append_literal_op (bi, op->operand_num);
1739           else if (strcmp (op->operand_name, "%LABEL") == 0)
1740             append_label_op (bi, op->operand_num);
1741           else if (op->operand_name[0] == 'a'
1742                    && parse_constant (op->operand_name + 1, &idnum))
1743             append_constant_op (bi, op->operand_num, idnum);
1744           else if (op->operand_name[0] == '%')
1745             {
1746               opname_map_e *orig_op;
1747               orig_op = get_opmatch (&initial_insn->t.operand_map,
1748                                      op->operand_name);
1749               if (orig_op == NULL)
1750                 as_fatal (_("opcode %s: unidentified operand '%s' in '%s'"),
1751                           opcode_name, op->operand_name, to_string);
1752               append_field_op (bi, op->operand_num, orig_op->operand_num);
1753             }
1754           else if (parse_special_fn (op->operand_name,
1755                                      &fn_name, &operand_arg_name))
1756             {
1757               opname_map_e *orig_op;
1758               OpType typ = OP_CONSTANT;
1759
1760               if (strcmp (fn_name, "LOW8") == 0)
1761                 typ = OP_OPERAND_LOW8;
1762               else if (strcmp (fn_name, "HI24S") == 0)
1763                 typ = OP_OPERAND_HI24S;
1764               else if (strcmp (fn_name, "F32MINUS") == 0)
1765                 typ = OP_OPERAND_F32MINUS;
1766               else if (strcmp (fn_name, "LOW16U") == 0)
1767                 typ = OP_OPERAND_LOW16U;
1768               else if (strcmp (fn_name, "HI16U") == 0)
1769                 typ = OP_OPERAND_HI16U;
1770               else
1771                 as_fatal (_("unknown user-defined function %s"), fn_name);
1772
1773               orig_op = get_opmatch (&initial_insn->t.operand_map,
1774                                      operand_arg_name);
1775               if (orig_op == NULL)
1776                 as_fatal (_("opcode %s: unidentified operand '%s' in '%s'"),
1777                           opcode_name, op->operand_name, to_string);
1778               append_user_fn_field_op (bi, op->operand_num,
1779                                        typ, orig_op->operand_num);
1780             }
1781           else
1782             as_fatal (_("opcode %s: could not parse operand '%s' in '%s'"),
1783                       opcode_name, op->operand_name, to_string);
1784         }
1785     }
1786
1787   return tr;
1788 }
1789
1790
1791 static TransitionTable *
1792 build_transition_table (const string_pattern_pair *transitions,
1793                         int transition_count,
1794                         transition_cmp_fn cmp)
1795 {
1796   TransitionTable *table = NULL;
1797   int num_opcodes = xtensa_isa_num_opcodes (xtensa_default_isa);
1798   int i, tnum;
1799
1800   if (table != NULL)
1801     return table;
1802
1803   /* Otherwise, build it now.  */
1804   table = (TransitionTable *) xmalloc (sizeof (TransitionTable));
1805   table->num_opcodes = num_opcodes;
1806   table->table =
1807     (TransitionList **) xmalloc (sizeof (TransitionTable *) * num_opcodes);
1808
1809   for (i = 0; i < num_opcodes; i++)
1810     table->table[i] = NULL;
1811
1812   for (tnum = 0; tnum < transition_count; tnum++)
1813     {
1814       const char *from_string = transitions[tnum].pattern;
1815       const char *to_string = transitions[tnum].replacement;
1816
1817       insn_pattern initial_insn;
1818       insn_repl replace_insns;
1819       TransitionRule *tr;
1820
1821       init_insn_pattern (&initial_insn);
1822       if (!parse_insn_pattern (from_string, &initial_insn))
1823         as_fatal (_("could not parse INSN_PATTERN '%s'"), from_string);
1824
1825       init_insn_repl (&replace_insns);
1826       if (!parse_insn_repl (to_string, &replace_insns))
1827         as_fatal (_("could not parse INSN_REPL '%s'"), to_string);
1828
1829       if (transition_applies (&initial_insn, from_string, to_string))
1830         {
1831           tr = build_transition (&initial_insn, &replace_insns,
1832                                  from_string, to_string);
1833           if (tr)
1834             append_transition (table, tr->opcode, tr, cmp);
1835           else
1836             {
1837 #if TENSILICA_DEBUG
1838               as_warn (_("could not build transition for %s => %s"),
1839                        from_string, to_string);
1840 #endif
1841             }
1842         }
1843
1844       clear_insn_repl (&replace_insns);
1845       clear_insn_pattern (&initial_insn);
1846     }
1847   return table;
1848 }
1849
1850 \f
1851 extern TransitionTable *
1852 xg_build_widen_table (transition_cmp_fn cmp)
1853 {
1854   static TransitionTable *table = NULL;
1855   if (table == NULL)
1856     table = build_transition_table (widen_spec_list, WIDEN_COUNT, cmp);
1857   return table;
1858 }
1859
1860
1861 extern TransitionTable *
1862 xg_build_simplify_table (transition_cmp_fn cmp)
1863 {
1864   static TransitionTable *table = NULL;
1865   if (table == NULL)
1866     table = build_transition_table (simplify_spec_list, SIMPLIFY_COUNT, cmp);
1867   return table;
1868 }