Back to index

cell-binutils  2.17cvs20070401
xtensa-relax.c
Go to the documentation of this file.
00001 /* Table of relaxations for Xtensa assembly.
00002    Copyright 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
00003 
00004    This file is part of GAS, the GNU Assembler.
00005 
00006    GAS is free software; you can redistribute it and/or modify
00007    it under the terms of the GNU General Public License as published by
00008    the Free Software Foundation; either version 2, or (at your option)
00009    any later version.
00010 
00011    GAS is distributed in the hope that it will be useful,
00012    but WITHOUT ANY WARRANTY; without even the implied warranty of
00013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014    GNU General Public License for more details.
00015 
00016    You should have received a copy of the GNU General Public License
00017    along with GAS; see the file COPYING.  If not, write to
00018    the Free Software Foundation, 51 Franklin Street - Fifth Floor, Boston,
00019    MA 02110-1301, USA.  */
00020 
00021 /* This file contains the code for generating runtime data structures
00022    for relaxation pattern matching from statically specified strings.
00023    Each action contains an instruction pattern to match and
00024    preconditions for the match as well as an expansion if the pattern
00025    matches.  The preconditions can specify that two operands are the
00026    same or an operand is a specific constant or register.  The expansion
00027    uses the bound variables from the pattern to specify that specific
00028    operands from the pattern should be used in the result.
00029 
00030    The code determines whether the condition applies to a constant or
00031    a register depending on the type of the operand.  You may get
00032    unexpected results if you don't match the rule against the operand
00033    type correctly.
00034 
00035    The patterns match a language like:
00036 
00037    INSN_PATTERN ::= INSN_TEMPL ( '|' PRECOND )* ( '?' OPTIONPRED )*
00038    INSN_TEMPL   ::= OPCODE ' ' [ OPERAND (',' OPERAND)* ]
00039    OPCODE       ::=  id
00040    OPERAND      ::= CONSTANT | VARIABLE | SPECIALFN '(' VARIABLE ')'
00041    SPECIALFN    ::= 'HI24S' | 'F32MINUS' | 'LOW8'
00042                     | 'HI16' | 'LOW16'
00043    VARIABLE     ::= '%' id
00044    PRECOND      ::= OPERAND CMPOP OPERAND
00045    CMPOP        ::= '==' | '!='
00046    OPTIONPRED   ::= OPTIONNAME ('+' OPTIONNAME)
00047    OPTIONNAME   ::= '"' id '"'
00048 
00049    The replacement language
00050    INSN_REPL      ::= INSN_LABEL_LIT ( ';' INSN_LABEL_LIT )*
00051    INSN_LABEL_LIT ::= INSN_TEMPL
00052                       | 'LABEL'
00053                       | 'LITERAL' VARIABLE
00054 
00055    The operands in a PRECOND must be constants or variables bound by
00056    the INSN_PATTERN.
00057 
00058    The configuration options define a predicate on the availability of
00059    options which must be TRUE for this rule to be valid.  Examples are
00060    requiring "density" for replacements with density instructions,
00061    requiring "const16" for replacements that require const16
00062    instructions, etc.  The names are interpreted by the assembler to a
00063    truth value for a particular frag.
00064 
00065    The operands in the INSN_REPL must be constants, variables bound in
00066    the associated INSN_PATTERN, special variables that are bound in
00067    the INSN_REPL by LABEL or LITERAL definitions, or special value
00068    manipulation functions.
00069 
00070    A simple example of a replacement pattern:
00071    {"movi.n %as,%imm", "movi %as,%imm"} would convert the narrow
00072    movi.n instruction to the wide movi instruction.
00073 
00074    A more complex example of a branch around:
00075    {"beqz %as,%label", "bnez %as,%LABEL;j %label;LABEL"}
00076    would convert a branch to a negated branch to the following instruction
00077    with a jump to the original label.
00078 
00079    An Xtensa-specific example that generates a literal:
00080    {"movi %at,%imm", "LITERAL %imm; l32r %at,%LITERAL"}
00081    will convert a movi instruction to an l32r of a literal
00082    literal defined in the literal pool.
00083 
00084    Even more complex is a conversion of a load with immediate offset
00085    to a load of a freshly generated literal, an explicit add and
00086    a load with 0 offset.  This transformation is only valid, though
00087    when the first and second operands are not the same as specified
00088    by the "| %at!=%as" precondition clause.
00089    {"l32i %at,%as,%imm | %at!=%as",
00090    "LITERAL %imm; l32r %at,%LITERAL; add %at,%at,%as; l32i %at,%at,0"}
00091 
00092    There is special case for loop instructions here, but because we do
00093    not currently have the ability to represent the difference of two
00094    symbols, the conversion requires special code in the assembler to
00095    write the operands of the addi/addmi pair representing the
00096    difference of the old and new loop end label.  */
00097 
00098 #include "as.h"
00099 #include "xtensa-isa.h"
00100 #include "xtensa-relax.h"
00101 #include <stddef.h>
00102 #include "xtensa-config.h"
00103 
00104 #ifndef XCHAL_HAVE_WIDE_BRANCHES
00105 #define XCHAL_HAVE_WIDE_BRANCHES 0
00106 #endif
00107 
00108 /* Imported from bfd.  */
00109 extern xtensa_isa xtensa_default_isa;
00110 
00111 /* The opname_list is a small list of names that we use for opcode and
00112    operand variable names to simplify ownership of these commonly used
00113    strings.  Strings entered in the table can be compared by pointer
00114    equality.  */
00115 
00116 typedef struct opname_list_struct opname_list;
00117 typedef opname_list opname_e;
00118 
00119 struct opname_list_struct
00120 {
00121   char *opname;
00122   opname_list *next;
00123 };
00124 
00125 static opname_list *local_opnames = NULL;
00126 
00127 
00128 /* The "opname_map" and its element structure "opname_map_e" are used
00129    for binding an operand number to a name or a constant.  */
00130 
00131 typedef struct opname_map_e_struct opname_map_e;
00132 typedef struct opname_map_struct opname_map;
00133 
00134 struct opname_map_e_struct
00135 {
00136   const char *operand_name; /* If null, then use constant_value.  */
00137   int operand_num;
00138   unsigned constant_value;
00139   opname_map_e *next;
00140 };
00141 
00142 struct opname_map_struct
00143 {
00144   opname_map_e *head;
00145   opname_map_e **tail;
00146 };
00147 
00148 /* The "precond_list" and its element structure "precond_e" represents
00149    explicit preconditions comparing operand variables and constants.
00150    In the "precond_e" structure, a variable is identified by the name
00151    in the "opname" field.   If that field is NULL, then the operand
00152    is the constant in field "opval".  */
00153 
00154 typedef struct precond_e_struct precond_e;
00155 typedef struct precond_list_struct precond_list;
00156 
00157 struct precond_e_struct
00158 {
00159   const char *opname1;
00160   unsigned opval1;
00161   CmpOp cmpop;
00162   const char *opname2;
00163   unsigned opval2;
00164   precond_e *next;
00165 };
00166 
00167 struct precond_list_struct
00168 {
00169   precond_e *head;
00170   precond_e **tail;
00171 };
00172 
00173 
00174 /* The insn_templ represents the INSN_TEMPL instruction template.  It
00175    is an opcode name with a list of operands.  These are used for
00176    instruction patterns and replacement patterns.  */
00177 
00178 typedef struct insn_templ_struct insn_templ;
00179 struct insn_templ_struct
00180 {
00181   const char *opcode_name;
00182   opname_map operand_map;
00183 };
00184 
00185 
00186 /* The insn_pattern represents an INSN_PATTERN instruction pattern.
00187    It is an instruction template with preconditions that specify when
00188    it actually matches a given instruction.  */
00189 
00190 typedef struct insn_pattern_struct insn_pattern;
00191 struct insn_pattern_struct
00192 {
00193   insn_templ t;
00194   precond_list preconds;
00195   ReqOptionList *options;
00196 };
00197 
00198 
00199 /* The "insn_repl" and associated element structure "insn_repl_e"
00200    instruction replacement list is a list of
00201    instructions/LITERALS/LABELS with constant operands or operands
00202    with names bound to the operand names in the associated pattern.  */
00203 
00204 typedef struct insn_repl_e_struct insn_repl_e;
00205 struct insn_repl_e_struct
00206 {
00207   insn_templ t;
00208   insn_repl_e *next;
00209 };
00210 
00211 typedef struct insn_repl_struct insn_repl;
00212 struct insn_repl_struct
00213 {
00214   insn_repl_e *head;
00215   insn_repl_e **tail;
00216 };
00217 
00218 
00219 /* The split_rec is a vector of allocated char * pointers.  */
00220 
00221 typedef struct split_rec_struct split_rec;
00222 struct split_rec_struct
00223 {
00224   char **vec;
00225   int count;
00226 };
00227 
00228 /* The "string_pattern_pair" is a set of pairs containing instruction
00229    patterns and replacement strings.  */
00230 
00231 typedef struct string_pattern_pair_struct string_pattern_pair;
00232 struct string_pattern_pair_struct
00233 {
00234   const char *pattern;
00235   const char *replacement;
00236 };
00237 
00238 
00239 /* The widen_spec_list is a list of valid substitutions that generate
00240    wider representations.  These are generally used to specify
00241    replacements for instructions whose immediates do not fit their
00242    encodings.  A valid transition may require multiple steps of
00243    one-to-one instruction replacements with a final multiple
00244    instruction replacement.  As an example, here are the transitions
00245    required to replace an 'addi.n' with an 'addi', 'addmi'.
00246 
00247      addi.n a4, 0x1010
00248      => addi a4, 0x1010
00249      => addmi a4, 0x1010
00250      => addmi a4, 0x1000, addi a4, 0x10.  */
00251 
00252 static string_pattern_pair widen_spec_list[] =
00253 {
00254   {"add.n %ar,%as,%at ? IsaUseDensityInstruction", "add %ar,%as,%at"},
00255   {"addi.n %ar,%as,%imm ? IsaUseDensityInstruction", "addi %ar,%as,%imm"},
00256   {"beqz.n %as,%label ? IsaUseDensityInstruction", "beqz %as,%label"},
00257   {"bnez.n %as,%label ? IsaUseDensityInstruction", "bnez %as,%label"},
00258   {"l32i.n %at,%as,%imm ? IsaUseDensityInstruction", "l32i %at,%as,%imm"},
00259   {"mov.n %at,%as ? IsaUseDensityInstruction", "or %at,%as,%as"},
00260   {"movi.n %as,%imm ? IsaUseDensityInstruction", "movi %as,%imm"},
00261   {"nop.n ? IsaUseDensityInstruction ? realnop", "nop"},
00262   {"nop.n ? IsaUseDensityInstruction ? no-realnop", "or 1,1,1"},
00263   {"ret.n %as ? IsaUseDensityInstruction", "ret %as"},
00264   {"retw.n %as ? IsaUseDensityInstruction", "retw %as"},
00265   {"s32i.n %at,%as,%imm ? IsaUseDensityInstruction", "s32i %at,%as,%imm"},
00266   {"srli %at,%as,%imm", "extui %at,%as,%imm,F32MINUS(%imm)"},
00267   {"slli %ar,%as,0", "or %ar,%as,%as"},
00268 
00269   /* Widening with literals or const16.  */
00270   {"movi %at,%imm ? IsaUseL32R ",
00271    "LITERAL %imm; l32r %at,%LITERAL"},
00272   {"movi %at,%imm ? IsaUseConst16",
00273    "const16 %at,HI16U(%imm); const16 %at,LOW16U(%imm)"},
00274 
00275   {"addi %ar,%as,%imm", "addmi %ar,%as,%imm"},
00276   /* LOW8 is the low 8 bits of the Immed
00277      MID8S is the middle 8 bits of the Immed */
00278   {"addmi %ar,%as,%imm", "addmi %ar,%as,HI24S(%imm); addi %ar,%ar,LOW8(%imm)"},
00279 
00280   /* In the end convert to either an l32r or const16.  */
00281   {"addmi %ar,%as,%imm | %ar!=%as ? IsaUseL32R",
00282    "LITERAL %imm; l32r %ar,%LITERAL; add %ar,%as,%ar"},
00283   {"addmi %ar,%as,%imm | %ar!=%as ? IsaUseConst16",
00284    "const16 %ar,HI16U(%imm); const16 %ar,LOW16U(%imm); add %ar,%as,%ar"},
00285 
00286   /* Widening the load instructions with too-large immediates */
00287   {"l8ui %at,%as,%imm | %at!=%as ? IsaUseL32R",
00288    "LITERAL %imm; l32r %at,%LITERAL; add %at,%at,%as; l8ui %at,%at,0"},
00289   {"l16si %at,%as,%imm | %at!=%as ? IsaUseL32R",
00290    "LITERAL %imm; l32r %at,%LITERAL; add %at,%at,%as; l16si %at,%at,0"},
00291   {"l16ui %at,%as,%imm | %at!=%as ? IsaUseL32R",
00292    "LITERAL %imm; l32r %at,%LITERAL; add %at,%at,%as; l16ui %at,%at,0"},
00293   {"l32i %at,%as,%imm | %at!=%as ? IsaUseL32R",
00294    "LITERAL %imm; l32r %at,%LITERAL; add %at,%at,%as; l32i %at,%at,0"},
00295 
00296   /* Widening load instructions with const16s.  */
00297   {"l8ui %at,%as,%imm | %at!=%as ? IsaUseConst16",
00298    "const16 %at,HI16U(%imm); const16 %at,LOW16U(%imm); add %at,%at,%as; l8ui %at,%at,0"},
00299   {"l16si %at,%as,%imm | %at!=%as ? IsaUseConst16",
00300    "const16 %at,HI16U(%imm); const16 %at,LOW16U(%imm); add %at,%at,%as; l16si %at,%at,0"},
00301   {"l16ui %at,%as,%imm | %at!=%as ? IsaUseConst16",
00302    "const16 %at,HI16U(%imm); const16 %at,LOW16U(%imm); add %at,%at,%as; l16ui %at,%at,0"},
00303   {"l32i %at,%as,%imm | %at!=%as ? IsaUseConst16",
00304    "const16 %at,HI16U(%imm); const16 %at,LOW16U(%imm); add %at,%at,%as; l32i %at,%at,0"},
00305 
00306   /* This is only PART of the loop instruction.  In addition,
00307      hardcoded into its use is a modification of the final operand in
00308      the instruction in bytes 9 and 12.  */
00309   {"loop %as,%label | %as!=1 ? IsaUseLoops",
00310    "loop %as,%LABEL;"
00311    "rsr.lend    %as;"              /* LEND */
00312    "wsr.lbeg    %as;"              /* LBEG */
00313    "addi    %as, %as, 0;"   /* lo8(%label-%LABEL1) */
00314    "addmi   %as, %as, 0;"   /* mid8(%label-%LABEL1) */
00315    "wsr.lend    %as;"
00316    "isync;"
00317    "rsr.lcount    %as;"            /* LCOUNT */
00318    "addi    %as, %as, 1;"   /* density -> addi.n %as, %as, 1 */
00319    "LABEL"},
00320   {"loopgtz %as,%label | %as!=1 ? IsaUseLoops",
00321    "beqz    %as,%label;"
00322    "bltz    %as,%label;"
00323    "loopgtz %as,%LABEL;"
00324    "rsr.lend    %as;"              /* LEND */
00325    "wsr.lbeg    %as;"              /* LBEG */
00326    "addi    %as, %as, 0;"   /* lo8(%label-%LABEL1) */
00327    "addmi   %as, %as, 0;"   /* mid8(%label-%LABEL1) */
00328    "wsr.lend    %as;"
00329    "isync;"
00330    "rsr.lcount    %as;"            /* LCOUNT */
00331    "addi    %as, %as, 1;"   /* density -> addi.n %as, %as, 1 */
00332    "LABEL"},
00333   {"loopnez %as,%label | %as!=1 ? IsaUseLoops",
00334    "beqz     %as,%label;"
00335    "loopnez %as,%LABEL;"
00336    "rsr.lend    %as;"              /* LEND */
00337    "wsr.lbeg    %as;"              /* LBEG */
00338    "addi    %as, %as, 0;"   /* lo8(%label-%LABEL1) */
00339    "addmi   %as, %as, 0;"   /* mid8(%label-%LABEL1) */
00340    "wsr.lend    %as;"
00341    "isync;"
00342    "rsr.lcount    %as;"            /* LCOUNT */
00343    "addi    %as, %as, 1;"   /* density -> addi.n %as, %as, 1 */
00344    "LABEL"},
00345 
00346   /* Relaxing to wide branches.  Order is important here.  With wide
00347      branches, there is more than one correct relaxation for an
00348      out-of-range branch.  Put the wide branch relaxations first in the
00349      table since they are more efficient than the branch-around
00350      relaxations.  */
00351   
00352   {"beqz %as,%label ? IsaUseWideBranches", "WIDE.beqz %as,%label"},
00353   {"bnez %as,%label ? IsaUseWideBranches", "WIDE.bnez %as,%label"},
00354   {"bgez %as,%label ? IsaUseWideBranches", "WIDE.bgez %as,%label"},
00355   {"bltz %as,%label ? IsaUseWideBranches", "WIDE.bltz %as,%label"},
00356   {"beqi %as,%imm,%label ? IsaUseWideBranches", "WIDE.beqi %as,%imm,%label"},
00357   {"bnei %as,%imm,%label ? IsaUseWideBranches", "WIDE.bnei %as,%imm,%label"},
00358   {"bgei %as,%imm,%label ? IsaUseWideBranches", "WIDE.bgei %as,%imm,%label"},
00359   {"blti %as,%imm,%label ? IsaUseWideBranches", "WIDE.blti %as,%imm,%label"},
00360   {"bgeui %as,%imm,%label ? IsaUseWideBranches", "WIDE.bgeui %as,%imm,%label"},
00361   {"bltui %as,%imm,%label ? IsaUseWideBranches", "WIDE.bltui %as,%imm,%label"},
00362   {"bbci %as,%imm,%label ? IsaUseWideBranches", "WIDE.bbci %as,%imm,%label"},
00363   {"bbsi %as,%imm,%label ? IsaUseWideBranches", "WIDE.bbsi %as,%imm,%label"},
00364   {"beq %as,%at,%label ? IsaUseWideBranches", "WIDE.beq %as,%at,%label"},
00365   {"bne %as,%at,%label ? IsaUseWideBranches", "WIDE.bne %as,%at,%label"},
00366   {"bge %as,%at,%label ? IsaUseWideBranches", "WIDE.bge %as,%at,%label"},
00367   {"blt %as,%at,%label ? IsaUseWideBranches", "WIDE.blt %as,%at,%label"},
00368   {"bgeu %as,%at,%label ? IsaUseWideBranches", "WIDE.bgeu %as,%at,%label"},
00369   {"bltu %as,%at,%label ? IsaUseWideBranches", "WIDE.bltu %as,%at,%label"},
00370   {"bany %as,%at,%label ? IsaUseWideBranches", "WIDE.bany %as,%at,%label"},
00371   {"bnone %as,%at,%label ? IsaUseWideBranches", "WIDE.bnone %as,%at,%label"},
00372   {"ball %as,%at,%label ? IsaUseWideBranches", "WIDE.ball %as,%at,%label"},
00373   {"bnall %as,%at,%label ? IsaUseWideBranches", "WIDE.bnall %as,%at,%label"},
00374   {"bbc %as,%at,%label ? IsaUseWideBranches", "WIDE.bbc %as,%at,%label"},
00375   {"bbs %as,%at,%label ? IsaUseWideBranches", "WIDE.bbs %as,%at,%label"},
00376   
00377   /* Widening branch comparisons eq/ne to zero.  Prefer relaxing to narrow
00378      branches if the density option is available.  */
00379   {"beqz %as,%label ? IsaUseDensityInstruction", "bnez.n %as,%LABEL;j %label;LABEL"},
00380   {"bnez %as,%label ? IsaUseDensityInstruction", "beqz.n %as,%LABEL;j %label;LABEL"},
00381   {"beqz %as,%label", "bnez %as,%LABEL;j %label;LABEL"},
00382   {"bnez %as,%label", "beqz %as,%LABEL;j %label;LABEL"},
00383 
00384   /* Widening expect-taken branches.  */
00385   {"beqzt %as,%label ? IsaUsePredictedBranches", "bnez %as,%LABEL;j %label;LABEL"},
00386   {"bnezt %as,%label ? IsaUsePredictedBranches", "beqz %as,%LABEL;j %label;LABEL"},
00387   {"beqt %as,%at,%label ? IsaUsePredictedBranches", "bne %as,%at,%LABEL;j %label;LABEL"},
00388   {"bnet %as,%at,%label ? IsaUsePredictedBranches", "beq %as,%at,%LABEL;j %label;LABEL"},
00389 
00390   /* Widening branches from the Xtensa boolean option.  */
00391   {"bt %bs,%label ? IsaUseBooleans", "bf %bs,%LABEL;j %label;LABEL"},
00392   {"bf %bs,%label ? IsaUseBooleans", "bt %bs,%LABEL;j %label;LABEL"},
00393 
00394   /* Other branch-around-jump widenings.  */
00395   {"bgez %as,%label", "bltz %as,%LABEL;j %label;LABEL"},
00396   {"bltz %as,%label", "bgez %as,%LABEL;j %label;LABEL"},
00397   {"beqi %as,%imm,%label", "bnei %as,%imm,%LABEL;j %label;LABEL"},
00398   {"bnei %as,%imm,%label", "beqi %as,%imm,%LABEL;j %label;LABEL"},
00399   {"bgei %as,%imm,%label", "blti %as,%imm,%LABEL;j %label;LABEL"},
00400   {"blti %as,%imm,%label", "bgei %as,%imm,%LABEL;j %label;LABEL"},
00401   {"bgeui %as,%imm,%label", "bltui %as,%imm,%LABEL;j %label;LABEL"},
00402   {"bltui %as,%imm,%label", "bgeui %as,%imm,%LABEL;j %label;LABEL"},
00403   {"bbci %as,%imm,%label", "bbsi %as,%imm,%LABEL;j %label;LABEL"},
00404   {"bbsi %as,%imm,%label", "bbci %as,%imm,%LABEL;j %label;LABEL"},
00405   {"beq %as,%at,%label", "bne %as,%at,%LABEL;j %label;LABEL"},
00406   {"bne %as,%at,%label", "beq %as,%at,%LABEL;j %label;LABEL"},
00407   {"bge %as,%at,%label", "blt %as,%at,%LABEL;j %label;LABEL"},
00408   {"blt %as,%at,%label", "bge %as,%at,%LABEL;j %label;LABEL"},
00409   {"bgeu %as,%at,%label", "bltu %as,%at,%LABEL;j %label;LABEL"},
00410   {"bltu %as,%at,%label", "bgeu %as,%at,%LABEL;j %label;LABEL"},
00411   {"bany %as,%at,%label", "bnone %as,%at,%LABEL;j %label;LABEL"},
00412   {"bnone %as,%at,%label", "bany %as,%at,%LABEL;j %label;LABEL"},
00413   {"ball %as,%at,%label", "bnall %as,%at,%LABEL;j %label;LABEL"},
00414   {"bnall %as,%at,%label", "ball %as,%at,%LABEL;j %label;LABEL"},
00415   {"bbc %as,%at,%label", "bbs %as,%at,%LABEL;j %label;LABEL"},
00416   {"bbs %as,%at,%label", "bbc %as,%at,%LABEL;j %label;LABEL"},
00417 
00418   /* Expanding calls with literals.  */
00419   {"call0 %label,%ar0 ? IsaUseL32R",
00420    "LITERAL %label; l32r a0,%LITERAL; callx0 a0,%ar0"},
00421   {"call4 %label,%ar4 ? IsaUseL32R",
00422    "LITERAL %label; l32r a4,%LITERAL; callx4 a4,%ar4"},
00423   {"call8 %label,%ar8 ? IsaUseL32R",
00424    "LITERAL %label; l32r a8,%LITERAL; callx8 a8,%ar8"},
00425   {"call12 %label,%ar12 ? IsaUseL32R",
00426    "LITERAL %label; l32r a12,%LITERAL; callx12 a12,%ar12"},
00427 
00428   /* Expanding calls with const16.  */
00429   {"call0 %label,%ar0 ? IsaUseConst16",
00430    "const16 a0,HI16U(%label); const16 a0,LOW16U(%label); callx0 a0,%ar0"},
00431   {"call4 %label,%ar4 ? IsaUseConst16",
00432    "const16 a4,HI16U(%label); const16 a4,LOW16U(%label); callx4 a4,%ar4"},
00433   {"call8 %label,%ar8 ? IsaUseConst16",
00434    "const16 a8,HI16U(%label); const16 a8,LOW16U(%label); callx8 a8,%ar8"},
00435   {"call12 %label,%ar12 ? IsaUseConst16",
00436    "const16 a12,HI16U(%label); const16 a12,LOW16U(%label); callx12 a12,%ar12"}
00437 };
00438 
00439 #define WIDEN_COUNT (sizeof (widen_spec_list) / sizeof (string_pattern_pair))
00440 
00441 
00442 /* The simplify_spec_list specifies simplifying transformations that
00443    will reduce the instruction width or otherwise simplify an
00444    instruction.  These are usually applied before relaxation in the
00445    assembler.  It is always legal to simplify.  Even for "addi as, 0",
00446    the "addi.n as, 0" will eventually be widened back to an "addi 0"
00447    after the widening table is applied.  Note: The usage of this table
00448    has changed somewhat so that it is entirely specific to "narrowing"
00449    instructions to use the density option.  This table is not used at
00450    all when the density option is not available.  */
00451 
00452 string_pattern_pair simplify_spec_list[] =
00453 {
00454   {"add %ar,%as,%at ? IsaUseDensityInstruction", "add.n %ar,%as,%at"},
00455   {"addi.n %ar,%as,0 ? IsaUseDensityInstruction", "mov.n %ar,%as"},
00456   {"addi %ar,%as,0 ? IsaUseDensityInstruction", "mov.n %ar,%as"},
00457   {"addi %ar,%as,%imm ? IsaUseDensityInstruction", "addi.n %ar,%as,%imm"},
00458   {"addmi %ar,%as,%imm ? IsaUseDensityInstruction", "addi.n %ar,%as,%imm"},
00459   {"beqz %as,%label ? IsaUseDensityInstruction", "beqz.n %as,%label"},
00460   {"bnez %as,%label ? IsaUseDensityInstruction", "bnez.n %as,%label"},
00461   {"l32i %at,%as,%imm ? IsaUseDensityInstruction", "l32i.n %at,%as,%imm"},
00462   {"movi %as,%imm ? IsaUseDensityInstruction", "movi.n %as,%imm"},
00463   {"nop ? realnop ? IsaUseDensityInstruction", "nop.n"},
00464   {"or %ar,%as,%at | %ar==%as | %as==%at ? IsaUseDensityInstruction", "nop.n"},
00465   {"or %ar,%as,%at | %ar!=%as | %as==%at ? IsaUseDensityInstruction", "mov.n %ar,%as"},
00466   {"ret %as ? IsaUseDensityInstruction", "ret.n %as"},
00467   {"retw %as ? IsaUseDensityInstruction", "retw.n %as"},
00468   {"s32i %at,%as,%imm ? IsaUseDensityInstruction", "s32i.n %at,%as,%imm"},
00469   {"slli %ar,%as,0 ? IsaUseDensityInstruction", "mov.n %ar,%as"}
00470 };
00471 
00472 #define SIMPLIFY_COUNT \
00473   (sizeof (simplify_spec_list) / sizeof (string_pattern_pair))
00474 
00475 
00476 /* Externally visible functions.  */
00477 
00478 extern bfd_boolean xg_has_userdef_op_fn (OpType);
00479 extern long xg_apply_userdef_op_fn (OpType, long);
00480 
00481 
00482 static void
00483 append_transition (TransitionTable *tt,
00484                  xtensa_opcode opcode,
00485                  TransitionRule *t,
00486                  transition_cmp_fn cmp)
00487 {
00488   TransitionList *tl = (TransitionList *) xmalloc (sizeof (TransitionList));
00489   TransitionList *prev;
00490   TransitionList **t_p;
00491   assert (tt != NULL);
00492   assert (opcode < tt->num_opcodes);
00493 
00494   prev = tt->table[opcode];
00495   tl->rule = t;
00496   tl->next = NULL;
00497   if (prev == NULL)
00498     {
00499       tt->table[opcode] = tl;
00500       return;
00501     }
00502 
00503   for (t_p = &tt->table[opcode]; (*t_p) != NULL; t_p = &(*t_p)->next)
00504     {
00505       if (cmp && cmp (t, (*t_p)->rule) < 0)
00506        {
00507          /* Insert it here.  */
00508          tl->next = *t_p;
00509          *t_p = tl;
00510          return;
00511        }
00512     }
00513   (*t_p) = tl;
00514 }
00515 
00516 
00517 static void
00518 append_condition (TransitionRule *tr, Precondition *cond)
00519 {
00520   PreconditionList *pl =
00521     (PreconditionList *) xmalloc (sizeof (PreconditionList));
00522   PreconditionList *prev = tr->conditions;
00523   PreconditionList *nxt;
00524 
00525   pl->precond = cond;
00526   pl->next = NULL;
00527   if (prev == NULL)
00528     {
00529       tr->conditions = pl;
00530       return;
00531     }
00532   nxt = prev->next;
00533   while (nxt != NULL)
00534     {
00535       prev = nxt;
00536       nxt = nxt->next;
00537     }
00538   prev->next = pl;
00539 }
00540 
00541 
00542 static void
00543 append_value_condition (TransitionRule *tr,
00544                      CmpOp cmp,
00545                      unsigned op1,
00546                      unsigned op2)
00547 {
00548   Precondition *cond = (Precondition *) xmalloc (sizeof (Precondition));
00549 
00550   cond->cmp = cmp;
00551   cond->op_num = op1;
00552   cond->typ = OP_OPERAND;
00553   cond->op_data = op2;
00554   append_condition (tr, cond);
00555 }
00556 
00557 
00558 static void
00559 append_constant_value_condition (TransitionRule *tr,
00560                              CmpOp cmp,
00561                              unsigned op1,
00562                              unsigned cnst)
00563 {
00564   Precondition *cond = (Precondition *) xmalloc (sizeof (Precondition));
00565 
00566   cond->cmp = cmp;
00567   cond->op_num = op1;
00568   cond->typ = OP_CONSTANT;
00569   cond->op_data = cnst;
00570   append_condition (tr, cond);
00571 }
00572 
00573 
00574 static void
00575 append_build_insn (TransitionRule *tr, BuildInstr *bi)
00576 {
00577   BuildInstr *prev = tr->to_instr;
00578   BuildInstr *nxt;
00579 
00580   bi->next = NULL;
00581   if (prev == NULL)
00582     {
00583       tr->to_instr = bi;
00584       return;
00585     }
00586   nxt = prev->next;
00587   while (nxt != 0)
00588     {
00589       prev = nxt;
00590       nxt = prev->next;
00591     }
00592   prev->next = bi;
00593 }
00594 
00595 
00596 static void
00597 append_op (BuildInstr *bi, BuildOp *b_op)
00598 {
00599   BuildOp *prev = bi->ops;
00600   BuildOp *nxt;
00601 
00602   if (prev == NULL)
00603     {
00604       bi->ops = b_op;
00605       return;
00606     }
00607   nxt = prev->next;
00608   while (nxt != NULL)
00609     {
00610       prev = nxt;
00611       nxt = nxt->next;
00612     }
00613   prev->next = b_op;
00614 }
00615 
00616 
00617 static void
00618 append_literal_op (BuildInstr *bi, unsigned op1)
00619 {
00620   BuildOp *b_op = (BuildOp *) xmalloc (sizeof (BuildOp));
00621 
00622   b_op->op_num = op1;
00623   b_op->typ = OP_LITERAL;
00624   b_op->op_data = 0;
00625   b_op->next = NULL;
00626   append_op (bi, b_op);
00627 }
00628 
00629 
00630 static void
00631 append_label_op (BuildInstr *bi, unsigned op1)
00632 {
00633   BuildOp *b_op = (BuildOp *) xmalloc (sizeof (BuildOp));
00634 
00635   b_op->op_num = op1;
00636   b_op->typ = OP_LABEL;
00637   b_op->op_data = 0;
00638   b_op->next = NULL;
00639   append_op (bi, b_op);
00640 }
00641 
00642 
00643 static void
00644 append_constant_op (BuildInstr *bi, unsigned op1, unsigned cnst)
00645 {
00646   BuildOp *b_op = (BuildOp *) xmalloc (sizeof (BuildOp));
00647 
00648   b_op->op_num = op1;
00649   b_op->typ = OP_CONSTANT;
00650   b_op->op_data = cnst;
00651   b_op->next = NULL;
00652   append_op (bi, b_op);
00653 }
00654 
00655 
00656 static void
00657 append_field_op (BuildInstr *bi, unsigned op1, unsigned src_op)
00658 {
00659   BuildOp *b_op = (BuildOp *) xmalloc (sizeof (BuildOp));
00660 
00661   b_op->op_num = op1;
00662   b_op->typ = OP_OPERAND;
00663   b_op->op_data = src_op;
00664   b_op->next = NULL;
00665   append_op (bi, b_op);
00666 }
00667 
00668 
00669 /* These could be generated but are not currently.  */
00670 
00671 static void
00672 append_user_fn_field_op (BuildInstr *bi,
00673                       unsigned op1,
00674                       OpType typ,
00675                       unsigned src_op)
00676 {
00677   BuildOp *b_op = (BuildOp *) xmalloc (sizeof (BuildOp));
00678 
00679   b_op->op_num = op1;
00680   b_op->typ = typ;
00681   b_op->op_data = src_op;
00682   b_op->next = NULL;
00683   append_op (bi, b_op);
00684 }
00685 
00686 
00687 /* These operand functions are the semantics of user-defined
00688    operand functions.  */
00689 
00690 static long
00691 operand_function_HI24S (long a)
00692 {
00693   if (a & 0x80)
00694     return (a & (~0xff)) + 0x100;
00695   else
00696     return (a & (~0xff));
00697 }
00698 
00699 
00700 static long
00701 operand_function_F32MINUS (long a)
00702 {
00703   return (32 - a);
00704 }
00705 
00706 
00707 static long
00708 operand_function_LOW8 (long a)
00709 {
00710   if (a & 0x80)
00711     return (a & 0xff) | ~0xff;
00712   else
00713     return (a & 0xff);
00714 }
00715 
00716 
00717 static long
00718 operand_function_LOW16U (long a)
00719 {
00720   return (a & 0xffff);
00721 }
00722 
00723 
00724 static long
00725 operand_function_HI16U (long a)
00726 {
00727   unsigned long b = a & 0xffff0000;
00728   return (long) (b >> 16);
00729 }
00730 
00731 
00732 bfd_boolean
00733 xg_has_userdef_op_fn (OpType op)
00734 {
00735   switch (op)
00736     {
00737     case OP_OPERAND_F32MINUS:
00738     case OP_OPERAND_LOW8:
00739     case OP_OPERAND_HI24S:
00740     case OP_OPERAND_LOW16U:
00741     case OP_OPERAND_HI16U:
00742       return TRUE;
00743     default:
00744       break;
00745     }
00746   return FALSE;
00747 }
00748 
00749 
00750 long
00751 xg_apply_userdef_op_fn (OpType op, long a)
00752 {
00753   switch (op)
00754     {
00755     case OP_OPERAND_F32MINUS:
00756       return operand_function_F32MINUS (a);
00757     case OP_OPERAND_LOW8:
00758       return operand_function_LOW8 (a);
00759     case OP_OPERAND_HI24S:
00760       return operand_function_HI24S (a);
00761     case OP_OPERAND_LOW16U:
00762       return operand_function_LOW16U (a);
00763     case OP_OPERAND_HI16U:
00764       return operand_function_HI16U (a);
00765     default:
00766       break;
00767     }
00768   return FALSE;
00769 }
00770 
00771 
00772 /* Generate a transition table.  */
00773 
00774 static const char *
00775 enter_opname_n (const char *name, int len)
00776 {
00777   opname_e *op;
00778 
00779   for (op = local_opnames; op != NULL; op = op->next)
00780     {
00781       if (strlen (op->opname) == (unsigned) len
00782          && strncmp (op->opname, name, len) == 0)
00783        return op->opname;
00784     }
00785   op = (opname_e *) xmalloc (sizeof (opname_e));
00786   op->opname = (char *) xmalloc (len + 1);
00787   strncpy (op->opname, name, len);
00788   op->opname[len] = '\0';
00789   return op->opname;
00790 }
00791 
00792 
00793 static const char *
00794 enter_opname (const char *name)
00795 {
00796   opname_e *op;
00797 
00798   for (op = local_opnames; op != NULL; op = op->next)
00799     {
00800       if (strcmp (op->opname, name) == 0)
00801        return op->opname;
00802     }
00803   op = (opname_e *) xmalloc (sizeof (opname_e));
00804   op->opname = xstrdup (name);
00805   return op->opname;
00806 }
00807 
00808 
00809 static void
00810 init_opname_map (opname_map *m)
00811 {
00812   m->head = NULL;
00813   m->tail = &m->head;
00814 }
00815 
00816 
00817 static void
00818 clear_opname_map (opname_map *m)
00819 {
00820   opname_map_e *e;
00821 
00822   while (m->head != NULL)
00823     {
00824       e = m->head;
00825       m->head = e->next;
00826       free (e);
00827     }
00828   m->tail = &m->head;
00829 }
00830 
00831 
00832 static bfd_boolean
00833 same_operand_name (const opname_map_e *m1, const opname_map_e *m2)
00834 {
00835   if (m1->operand_name == NULL || m1->operand_name == NULL)
00836     return FALSE;
00837   return (m1->operand_name == m2->operand_name);
00838 }
00839 
00840 
00841 static opname_map_e *
00842 get_opmatch (opname_map *map, const char *operand_name)
00843 {
00844   opname_map_e *m;
00845 
00846   for (m = map->head; m != NULL; m = m->next)
00847     {
00848       if (strcmp (m->operand_name, operand_name) == 0)
00849        return m;
00850     }
00851   return NULL;
00852 }
00853 
00854 
00855 static bfd_boolean
00856 op_is_constant (const opname_map_e *m1)
00857 {
00858   return (m1->operand_name == NULL);
00859 }
00860 
00861 
00862 static unsigned
00863 op_get_constant (const opname_map_e *m1)
00864 {
00865   assert (m1->operand_name == NULL);
00866   return m1->constant_value;
00867 }
00868 
00869 
00870 static void
00871 init_precond_list (precond_list *l)
00872 {
00873   l->head = NULL;
00874   l->tail = &l->head;
00875 }
00876 
00877 
00878 static void
00879 clear_precond_list (precond_list *l)
00880 {
00881   precond_e *e;
00882 
00883   while (l->head != NULL)
00884     {
00885       e = l->head;
00886       l->head = e->next;
00887       free (e);
00888     }
00889   l->tail = &l->head;
00890 }
00891 
00892 
00893 static void
00894 init_insn_templ (insn_templ *t)
00895 {
00896   t->opcode_name = NULL;
00897   init_opname_map (&t->operand_map);
00898 }
00899 
00900 
00901 static void
00902 clear_insn_templ (insn_templ *t)
00903 {
00904   clear_opname_map (&t->operand_map);
00905 }
00906 
00907 
00908 static void
00909 init_insn_pattern (insn_pattern *p)
00910 {
00911   init_insn_templ (&p->t);
00912   init_precond_list (&p->preconds);
00913   p->options = NULL;
00914 }
00915 
00916 
00917 static void
00918 clear_insn_pattern (insn_pattern *p)
00919 {
00920   clear_insn_templ (&p->t);
00921   clear_precond_list (&p->preconds);
00922 }
00923 
00924 
00925 static void
00926 init_insn_repl (insn_repl *r)
00927 {
00928   r->head = NULL;
00929   r->tail = &r->head;
00930 }
00931 
00932 
00933 static void
00934 clear_insn_repl (insn_repl *r)
00935 {
00936   insn_repl_e *e;
00937 
00938   while (r->head != NULL)
00939     {
00940       e = r->head;
00941       r->head = e->next;
00942       clear_insn_templ (&e->t);
00943     }
00944   r->tail = &r->head;
00945 }
00946 
00947 
00948 static int
00949 insn_templ_operand_count (const insn_templ *t)
00950 {
00951   int i = 0;
00952   const opname_map_e *op;
00953 
00954   for (op = t->operand_map.head; op != NULL; op = op->next, i++)
00955     ;
00956   return i;
00957 }
00958 
00959 
00960 /* Convert a string to a number.  E.G.: parse_constant("10", &num) */
00961 
00962 static bfd_boolean
00963 parse_constant (const char *in, unsigned *val_p)
00964 {
00965   unsigned val = 0;
00966   const char *p;
00967 
00968   if (in == NULL)
00969     return FALSE;
00970   p = in;
00971 
00972   while (*p != '\0')
00973     {
00974       if (*p >= '0' && *p <= '9')
00975        val = val * 10 + (*p - '0');
00976       else
00977        return FALSE;
00978       ++p;
00979     }
00980   *val_p = val;
00981   return TRUE;
00982 }
00983 
00984 
00985 static bfd_boolean
00986 parse_special_fn (const char *name,
00987                 const char **fn_name_p,
00988                 const char **arg_name_p)
00989 {
00990   char *p_start;
00991   const char *p_end;
00992 
00993   p_start = strchr (name, '(');
00994   if (p_start == NULL)
00995     return FALSE;
00996 
00997   p_end = strchr (p_start, ')');
00998 
00999   if (p_end == NULL)
01000     return FALSE;
01001 
01002   if (p_end[1] != '\0')
01003     return FALSE;
01004 
01005   *fn_name_p = enter_opname_n (name, p_start - name);
01006   *arg_name_p = enter_opname_n (p_start + 1, p_end - p_start - 1);
01007   return TRUE;
01008 }
01009 
01010 
01011 static const char *
01012 skip_white (const char *p)
01013 {
01014   if (p == NULL)
01015     return p;
01016   while (*p == ' ')
01017     ++p;
01018   return p;
01019 }
01020 
01021 
01022 static void
01023 trim_whitespace (char *in)
01024 {
01025   char *last_white = NULL;
01026   char *p = in;
01027 
01028   while (p && *p != '\0')
01029     {
01030       while (*p == ' ')
01031        {
01032          if (last_white == NULL)
01033            last_white = p;
01034          p++;
01035        }
01036       if (*p != '\0')
01037        {
01038          last_white = NULL;
01039          p++;
01040        }
01041     }
01042   if (last_white)
01043     *last_white = '\0';
01044 }
01045 
01046 
01047 /* Split a string into component strings where "c" is the
01048    delimiter.  Place the result in the split_rec.  */
01049 
01050 static void
01051 split_string (split_rec *rec,
01052              const char *in,
01053              char c,
01054              bfd_boolean elide_whitespace)
01055 {
01056   int cnt = 0;
01057   int i;
01058   const char *p = in;
01059 
01060   while (p != NULL && *p != '\0')
01061     {
01062       cnt++;
01063       p = strchr (p, c);
01064       if (p)
01065        p++;
01066     }
01067   rec->count = cnt;
01068   rec->vec = NULL;
01069 
01070   if (rec->count == 0)
01071     return;
01072 
01073   rec->vec = (char **) xmalloc (sizeof (char *) * cnt);
01074   for (i = 0; i < cnt; i++)
01075     rec->vec[i] = 0;
01076 
01077   p = in;
01078   for (i = 0; i < cnt; i++)
01079     {
01080       const char *q;
01081       int len;
01082 
01083       q = p;
01084       if (elide_whitespace)
01085        q = skip_white (q);
01086 
01087       p = strchr (q, c);
01088       if (p == NULL)
01089        rec->vec[i] = xstrdup (q);
01090       else
01091        {
01092          len = p - q;
01093          rec->vec[i] = (char *) xmalloc (sizeof (char) * (len + 1));
01094          strncpy (rec->vec[i], q, len);
01095          rec->vec[i][len] = '\0';
01096          p++;
01097        }
01098 
01099       if (elide_whitespace)
01100        trim_whitespace (rec->vec[i]);
01101     }
01102 }
01103 
01104 
01105 static void
01106 clear_split_rec (split_rec *rec)
01107 {
01108   int i;
01109 
01110   for (i = 0; i < rec->count; i++)
01111     free (rec->vec[i]);
01112 
01113   if (rec->count > 0)
01114     free (rec->vec);
01115 }
01116 
01117 
01118 /* Initialize a split record.  The split record must be initialized
01119    before split_string is called.  */
01120 
01121 static void
01122 init_split_rec (split_rec *rec)
01123 {
01124   rec->vec = NULL;
01125   rec->count = 0;
01126 }
01127 
01128 
01129 /* Parse an instruction template like "insn op1, op2, op3".  */
01130 
01131 static bfd_boolean
01132 parse_insn_templ (const char *s, insn_templ *t)
01133 {
01134   const char *p = s;
01135   int insn_name_len;
01136   split_rec oprec;
01137   int i;
01138 
01139   /* First find the first whitespace.  */
01140 
01141   init_split_rec (&oprec);
01142 
01143   p = skip_white (p);
01144   insn_name_len = strcspn (s, " ");
01145   if (insn_name_len == 0)
01146     return FALSE;
01147 
01148   init_insn_templ (t);
01149   t->opcode_name = enter_opname_n (p, insn_name_len);
01150 
01151   p = p + insn_name_len;
01152 
01153   /* Split by ',' and skip beginning and trailing whitespace.  */
01154   split_string (&oprec, p, ',', TRUE);
01155 
01156   for (i = 0; i < oprec.count; i++)
01157     {
01158       const char *opname = oprec.vec[i];
01159       opname_map_e *e = (opname_map_e *) xmalloc (sizeof (opname_map_e));
01160       e->next = NULL;
01161       e->operand_name = NULL;
01162       e->constant_value = 0;
01163       e->operand_num = i;
01164 
01165       /* If it begins with a number, assume that it is a number.  */
01166       if (opname && opname[0] >= '0' && opname[0] <= '9')
01167        {
01168          unsigned val;
01169 
01170          if (parse_constant (opname, &val))
01171            e->constant_value = val;
01172          else
01173            {
01174              free (e);
01175              clear_split_rec (&oprec);
01176              clear_insn_templ (t);
01177              return FALSE;
01178            }
01179        }
01180       else
01181        e->operand_name = enter_opname (oprec.vec[i]);
01182 
01183       *t->operand_map.tail = e;
01184       t->operand_map.tail = &e->next;
01185     }
01186   clear_split_rec (&oprec);
01187   return TRUE;
01188 }
01189 
01190 
01191 static bfd_boolean
01192 parse_precond (const char *s, precond_e *precond)
01193 {
01194   /* All preconditions are currently of the form:
01195      a == b or a != b or a == k (where k is a constant).
01196      Later we may use some special functions like DENSITY == 1
01197      to identify when density is available.  */
01198 
01199   const char *p = s;
01200   int len;
01201   precond->opname1 = NULL;
01202   precond->opval1 = 0;
01203   precond->cmpop = OP_EQUAL;
01204   precond->opname2 = NULL;
01205   precond->opval2 = 0;
01206   precond->next = NULL;
01207 
01208   p = skip_white (p);
01209 
01210   len = strcspn (p, " !=");
01211 
01212   if (len == 0)
01213     return FALSE;
01214 
01215   precond->opname1 = enter_opname_n (p, len);
01216   p = p + len;
01217   p = skip_white (p);
01218 
01219   /* Check for "==" and "!=".  */
01220   if (strncmp (p, "==", 2) == 0)
01221     precond->cmpop = OP_EQUAL;
01222   else if (strncmp (p, "!=", 2) == 0)
01223     precond->cmpop = OP_NOTEQUAL;
01224   else
01225     return FALSE;
01226 
01227   p = p + 2;
01228   p = skip_white (p);
01229 
01230   /* No trailing whitespace from earlier parsing.  */
01231   if (p[0] >= '0' && p[0] <= '9')
01232     {
01233       unsigned val;
01234       if (parse_constant (p, &val))
01235        precond->opval2 = val;
01236       else
01237        return FALSE;
01238     }
01239   else
01240     precond->opname2 = enter_opname (p);
01241   return TRUE;
01242 }
01243 
01244 
01245 static void
01246 clear_req_or_option_list (ReqOrOption **r_p)
01247 {
01248   if (*r_p == NULL)
01249     return;
01250 
01251   free ((*r_p)->option_name);
01252   clear_req_or_option_list (&(*r_p)->next);
01253   *r_p = NULL;
01254 }
01255 
01256 
01257 static void
01258 clear_req_option_list (ReqOption **r_p)
01259 {
01260   if (*r_p == NULL)
01261     return;
01262 
01263   clear_req_or_option_list (&(*r_p)->or_option_terms);
01264   clear_req_option_list (&(*r_p)->next);
01265   *r_p = NULL;
01266 }
01267 
01268 
01269 static ReqOrOption *
01270 clone_req_or_option_list (ReqOrOption *req_or_option)
01271 {
01272   ReqOrOption *new_req_or_option;
01273 
01274   if (req_or_option == NULL)
01275     return NULL;
01276 
01277   new_req_or_option = (ReqOrOption *) xmalloc (sizeof (ReqOrOption));
01278   new_req_or_option->option_name = xstrdup (req_or_option->option_name);
01279   new_req_or_option->is_true = req_or_option->is_true;
01280   new_req_or_option->next = NULL;
01281   new_req_or_option->next = clone_req_or_option_list (req_or_option->next);
01282   return new_req_or_option;
01283 }
01284 
01285 
01286 static ReqOption *
01287 clone_req_option_list (ReqOption *req_option)
01288 {
01289   ReqOption *new_req_option;
01290 
01291   if (req_option == NULL)
01292     return NULL;
01293 
01294   new_req_option = (ReqOption *) xmalloc (sizeof (ReqOption));
01295   new_req_option->or_option_terms = NULL;
01296   new_req_option->next = NULL;
01297   new_req_option->or_option_terms =
01298     clone_req_or_option_list (req_option->or_option_terms);
01299   new_req_option->next = clone_req_option_list (req_option->next);
01300   return new_req_option;
01301 }
01302 
01303 
01304 static bfd_boolean
01305 parse_option_cond (const char *s, ReqOption *option)
01306 {
01307   int i;
01308   split_rec option_term_rec;
01309 
01310   /* All option or conditions are of the form:
01311      optionA + no-optionB + ...
01312      "Ands" are divided by "?".  */
01313 
01314   init_split_rec (&option_term_rec);
01315   split_string (&option_term_rec, s, '+', TRUE);
01316 
01317   if (option_term_rec.count == 0)
01318     {
01319       clear_split_rec (&option_term_rec);
01320       return FALSE;
01321     }
01322 
01323   for (i = 0; i < option_term_rec.count; i++)
01324     {
01325       char *option_name = option_term_rec.vec[i];
01326       bfd_boolean is_true = TRUE;
01327       ReqOrOption *req;
01328       ReqOrOption **r_p;
01329 
01330       if (strncmp (option_name, "no-", 3) == 0)
01331        {
01332          option_name = xstrdup (&option_name[3]);
01333          is_true = FALSE;
01334        }
01335       else
01336        option_name = xstrdup (option_name);
01337 
01338       req = (ReqOrOption *) xmalloc (sizeof (ReqOrOption));
01339       req->option_name = option_name;
01340       req->is_true = is_true;
01341       req->next = NULL;
01342 
01343       /* Append to list.  */
01344       for (r_p = &option->or_option_terms; (*r_p) != NULL;
01345           r_p = &(*r_p)->next)
01346        ;
01347       (*r_p) = req;
01348     }
01349   return TRUE;
01350 }
01351 
01352 
01353 /* Parse a string like:
01354    "insn op1, op2, op3, op4 | op1 != op2 | op2 == op3 | op4 == 1".
01355    I.E., instruction "insn" with 4 operands where operand 1 and 2 are not
01356    the same and operand 2 and 3 are the same and operand 4 is 1.
01357 
01358    or:
01359 
01360    "insn op1 | op1 == 1 / density + boolean / no-useroption".
01361    i.e. instruction "insn" with 1 operands where operand 1 is 1
01362    when "density" or "boolean" options are available and
01363    "useroption" is not available.
01364 
01365    Because the current implementation of this parsing scheme uses
01366    split_string, it requires that '|' and '?' are only used as
01367    delimiters for predicates and required options.  */
01368 
01369 static bfd_boolean
01370 parse_insn_pattern (const char *in, insn_pattern *insn)
01371 {
01372   split_rec rec;
01373   split_rec optionrec;
01374   int i;
01375 
01376   init_insn_pattern (insn);
01377 
01378   init_split_rec (&optionrec);
01379   split_string (&optionrec, in, '?', TRUE);
01380   if (optionrec.count == 0)
01381     {
01382       clear_split_rec (&optionrec);
01383       return FALSE;
01384     }
01385 
01386   init_split_rec (&rec);
01387 
01388   split_string (&rec, optionrec.vec[0], '|', TRUE);
01389 
01390   if (rec.count == 0)
01391     {
01392       clear_split_rec (&rec);
01393       clear_split_rec (&optionrec);
01394       return FALSE;
01395     }
01396 
01397   if (!parse_insn_templ (rec.vec[0], &insn->t))
01398     {
01399       clear_split_rec (&rec);
01400       clear_split_rec (&optionrec);
01401       return FALSE;
01402     }
01403 
01404   for (i = 1; i < rec.count; i++)
01405     {
01406       precond_e *cond = (precond_e *) xmalloc (sizeof (precond_e));
01407 
01408       if (!parse_precond (rec.vec[i], cond))
01409        {
01410          clear_split_rec (&rec);
01411          clear_split_rec (&optionrec);
01412          clear_insn_pattern (insn);
01413          return FALSE;
01414        }
01415 
01416       /* Append the condition.  */
01417       *insn->preconds.tail = cond;
01418       insn->preconds.tail = &cond->next;
01419     }
01420 
01421   for (i = 1; i < optionrec.count; i++)
01422     {
01423       /* Handle the option conditions.  */
01424       ReqOption **r_p;
01425       ReqOption *req_option = (ReqOption *) xmalloc (sizeof (ReqOption));
01426       req_option->or_option_terms = NULL;
01427       req_option->next = NULL;
01428 
01429       if (!parse_option_cond (optionrec.vec[i], req_option))
01430        {
01431          clear_split_rec (&rec);
01432          clear_split_rec (&optionrec);
01433          clear_insn_pattern (insn);
01434          clear_req_option_list (&req_option);
01435          return FALSE;
01436        }
01437 
01438       /* Append the condition.  */
01439       for (r_p = &insn->options; (*r_p) != NULL; r_p = &(*r_p)->next)
01440        ;
01441 
01442       (*r_p) = req_option;
01443     }
01444 
01445   clear_split_rec (&rec);
01446   clear_split_rec (&optionrec);
01447   return TRUE;
01448 }
01449 
01450 
01451 static bfd_boolean
01452 parse_insn_repl (const char *in, insn_repl *r_p)
01453 {
01454   /* This is a list of instruction templates separated by ';'.  */
01455   split_rec rec;
01456   int i;
01457 
01458   split_string (&rec, in, ';', TRUE);
01459 
01460   for (i = 0; i < rec.count; i++)
01461     {
01462       insn_repl_e *e = (insn_repl_e *) xmalloc (sizeof (insn_repl_e));
01463 
01464       e->next = NULL;
01465 
01466       if (!parse_insn_templ (rec.vec[i], &e->t))
01467        {
01468          free (e);
01469          clear_insn_repl (r_p);
01470          return FALSE;
01471        }
01472       *r_p->tail = e;
01473       r_p->tail = &e->next;
01474     }
01475   return TRUE;
01476 }
01477 
01478 
01479 static bfd_boolean
01480 transition_applies (insn_pattern *initial_insn,
01481                   const char *from_string ATTRIBUTE_UNUSED,
01482                   const char *to_string ATTRIBUTE_UNUSED)
01483 {
01484   ReqOption *req_option;
01485 
01486   for (req_option = initial_insn->options;
01487        req_option != NULL;
01488        req_option = req_option->next)
01489     {
01490       ReqOrOption *req_or_option = req_option->or_option_terms;
01491 
01492       if (req_or_option == NULL
01493          || req_or_option->next != NULL)
01494        continue;
01495 
01496       if (strncmp (req_or_option->option_name, "IsaUse", 6) == 0)
01497        {
01498          bfd_boolean option_available = FALSE;
01499          char *option_name = req_or_option->option_name + 6;
01500          if (!strcmp (option_name, "DensityInstruction"))
01501            option_available = (XCHAL_HAVE_DENSITY == 1);
01502          else if (!strcmp (option_name, "L32R"))
01503            option_available = (XCHAL_HAVE_L32R == 1);
01504          else if (!strcmp (option_name, "Const16"))
01505            option_available = (XCHAL_HAVE_CONST16 == 1);
01506          else if (!strcmp (option_name, "Loops"))
01507            option_available = (XCHAL_HAVE_LOOPS == 1);
01508          else if (!strcmp (option_name, "WideBranches"))
01509            option_available = (XCHAL_HAVE_WIDE_BRANCHES == 1);
01510          else if (!strcmp (option_name, "PredictedBranches"))
01511            option_available = (XCHAL_HAVE_PREDICTED_BRANCHES == 1);
01512          else if (!strcmp (option_name, "Booleans"))
01513            option_available = (XCHAL_HAVE_BOOLEANS == 1);
01514          else
01515            as_warn (_("invalid configuration option '%s' in transition rule '%s'"),
01516                    req_or_option->option_name, from_string);
01517          if ((option_available ^ req_or_option->is_true) != 0)
01518            return FALSE;
01519        }
01520       else if (strcmp (req_or_option->option_name, "realnop") == 0)
01521        {
01522          bfd_boolean nop_available =
01523            (xtensa_opcode_lookup (xtensa_default_isa, "nop")
01524             != XTENSA_UNDEFINED);
01525          if ((nop_available ^ req_or_option->is_true) != 0)
01526            return FALSE;
01527        }
01528     }
01529   return TRUE;
01530 }
01531 
01532 
01533 static bfd_boolean
01534 wide_branch_opcode (const char *opcode_name,
01535                   char *suffix,
01536                   xtensa_opcode *popcode)
01537 {
01538   xtensa_isa isa = xtensa_default_isa;
01539   xtensa_opcode opcode;
01540   static char wbr_name_buf[20];
01541 
01542   if (strncmp (opcode_name, "WIDE.", 5) != 0)
01543     return FALSE;
01544 
01545   strcpy (wbr_name_buf, opcode_name + 5);
01546   strcat (wbr_name_buf, suffix);
01547   opcode = xtensa_opcode_lookup (isa, wbr_name_buf);
01548   if (opcode != XTENSA_UNDEFINED)
01549     {
01550       *popcode = opcode;
01551       return TRUE;
01552     }
01553 
01554   return FALSE;
01555 }
01556 
01557 
01558 static TransitionRule *
01559 build_transition (insn_pattern *initial_insn,
01560                 insn_repl *replace_insns,
01561                 const char *from_string,
01562                 const char *to_string)
01563 {
01564   TransitionRule *tr = NULL;
01565   xtensa_opcode opcode;
01566   xtensa_isa isa = xtensa_default_isa;
01567 
01568   opname_map_e *op1;
01569   opname_map_e *op2;
01570 
01571   precond_e *precond;
01572   insn_repl_e *r;
01573 
01574   opcode = xtensa_opcode_lookup (isa, initial_insn->t.opcode_name);
01575   if (opcode == XTENSA_UNDEFINED)
01576     {
01577       /* It is OK to not be able to translate some of these opcodes.  */
01578       return NULL;
01579     }
01580 
01581 
01582   if (xtensa_opcode_num_operands (isa, opcode)
01583       != insn_templ_operand_count (&initial_insn->t))
01584     {
01585       /* This is also OK because there are opcodes that
01586         have different numbers of operands on different
01587         architecture variations.  */
01588       return NULL;
01589     }
01590 
01591   tr = (TransitionRule *) xmalloc (sizeof (TransitionRule));
01592   tr->opcode = opcode;
01593   tr->conditions = NULL;
01594   tr->to_instr = NULL;
01595 
01596   /* Build the conditions. First, equivalent operand condition....  */
01597   for (op1 = initial_insn->t.operand_map.head; op1 != NULL; op1 = op1->next)
01598     {
01599       for (op2 = op1->next; op2 != NULL; op2 = op2->next)
01600        {
01601          if (same_operand_name (op1, op2))
01602            {
01603              append_value_condition (tr, OP_EQUAL,
01604                                   op1->operand_num, op2->operand_num);
01605            }
01606        }
01607     }
01608 
01609   /* Now the condition that an operand value must be a constant....  */
01610   for (op1 = initial_insn->t.operand_map.head; op1 != NULL; op1 = op1->next)
01611     {
01612       if (op_is_constant (op1))
01613        {
01614          append_constant_value_condition (tr,
01615                                       OP_EQUAL,
01616                                       op1->operand_num,
01617                                       op_get_constant (op1));
01618        }
01619     }
01620 
01621 
01622   /* Now add the explicit preconditions listed after the "|" in the spec.
01623      These are currently very limited, so we do a special case
01624      parse for them.  We expect spaces, opname != opname.  */
01625   for (precond = initial_insn->preconds.head;
01626        precond != NULL;
01627        precond = precond->next)
01628     {
01629       op1 = NULL;
01630       op2 = NULL;
01631 
01632       if (precond->opname1)
01633        {
01634          op1 = get_opmatch (&initial_insn->t.operand_map, precond->opname1);
01635          if (op1 == NULL)
01636            as_fatal (_("opcode '%s': no bound opname '%s' "
01637                      "for precondition in '%s'"),
01638                     xtensa_opcode_name (isa, opcode),
01639                     precond->opname1, from_string);
01640        }
01641 
01642       if (precond->opname2)
01643        {
01644          op2 = get_opmatch (&initial_insn->t.operand_map, precond->opname2);
01645          if (op2 == NULL)
01646            as_fatal (_("opcode '%s': no bound opname '%s' "
01647                      "for precondition in %s"),
01648                     xtensa_opcode_name (isa, opcode),
01649                     precond->opname2, from_string);
01650        }
01651 
01652       if (op1 == NULL && op2 == NULL)
01653        as_fatal (_("opcode '%s': precondition only contains "
01654                   "constants in '%s'"),
01655                 xtensa_opcode_name (isa, opcode), from_string);
01656       else if (op1 != NULL && op2 != NULL)
01657        append_value_condition (tr, precond->cmpop,
01658                             op1->operand_num, op2->operand_num);
01659       else if (op2 == NULL)
01660        append_constant_value_condition (tr, precond->cmpop,
01661                                     op1->operand_num, precond->opval2);
01662       else
01663        append_constant_value_condition (tr, precond->cmpop,
01664                                     op2->operand_num, precond->opval1);
01665     }
01666 
01667   tr->options = clone_req_option_list (initial_insn->options);
01668 
01669   /* Generate the replacement instructions.  Some of these
01670      "instructions" are actually labels and literals.  There can be at
01671      most one literal and at most one label.  A literal must be defined
01672      (e.g., "LITERAL %imm") before use (e.g., "%LITERAL").  The labels
01673      can be used before they are defined.  Also there are a number of
01674      special operands (e.g., HI24S).  */
01675 
01676   for (r = replace_insns->head; r != NULL; r = r->next)
01677     {
01678       BuildInstr *bi;
01679       const char *opcode_name;
01680       int operand_count;
01681       opname_map_e *op;
01682       const char *fn_name;
01683       const char *operand_arg_name;
01684 
01685       bi = (BuildInstr *) xmalloc (sizeof (BuildInstr));
01686       append_build_insn (tr, bi);
01687 
01688       bi->opcode = XTENSA_UNDEFINED;
01689       bi->ops = NULL;
01690       bi->next = NULL;
01691 
01692       opcode_name = r->t.opcode_name;
01693       operand_count = insn_templ_operand_count (&r->t);
01694 
01695       if (strcmp (opcode_name, "LITERAL") == 0)
01696        {
01697          bi->typ = INSTR_LITERAL_DEF;
01698          if (operand_count != 1)
01699            as_fatal (_("expected one operand for generated literal"));
01700        }
01701       else if (strcmp (opcode_name, "LABEL") == 0)
01702        {
01703          bi->typ = INSTR_LABEL_DEF;
01704          if (operand_count != 0)
01705            as_fatal (_("expected 0 operands for generated label"));
01706        }
01707       else
01708        {
01709          bi->typ = INSTR_INSTR;
01710          if (wide_branch_opcode (opcode_name, ".w18", &bi->opcode)
01711              || wide_branch_opcode (opcode_name, ".w15", &bi->opcode))
01712            opcode_name = xtensa_opcode_name (isa, bi->opcode);
01713          else
01714            bi->opcode = xtensa_opcode_lookup (isa, opcode_name);
01715 
01716          if (bi->opcode == XTENSA_UNDEFINED)
01717            {
01718              as_warn (_("invalid opcode '%s' in transition rule '%s'"),
01719                      opcode_name, to_string);
01720              return NULL;
01721            }
01722 
01723          /* Check for the right number of ops.  */
01724          if (xtensa_opcode_num_operands (isa, bi->opcode)
01725              != (int) operand_count)
01726            as_fatal (_("opcode '%s': replacement does not have %d ops"),
01727                     opcode_name,
01728                     xtensa_opcode_num_operands (isa, bi->opcode));
01729        }
01730 
01731       for (op = r->t.operand_map.head; op != NULL; op = op->next)
01732        {
01733          unsigned idnum;
01734 
01735          if (op_is_constant (op))
01736            append_constant_op (bi, op->operand_num, op_get_constant (op));
01737          else if (strcmp (op->operand_name, "%LITERAL") == 0)
01738            append_literal_op (bi, op->operand_num);
01739          else if (strcmp (op->operand_name, "%LABEL") == 0)
01740            append_label_op (bi, op->operand_num);
01741          else if (op->operand_name[0] == 'a'
01742                  && parse_constant (op->operand_name + 1, &idnum))
01743            append_constant_op (bi, op->operand_num, idnum);
01744          else if (op->operand_name[0] == '%')
01745            {
01746              opname_map_e *orig_op;
01747              orig_op = get_opmatch (&initial_insn->t.operand_map,
01748                                  op->operand_name);
01749              if (orig_op == NULL)
01750               as_fatal (_("opcode %s: unidentified operand '%s' in '%s'"),
01751                        opcode_name, op->operand_name, to_string);
01752              append_field_op (bi, op->operand_num, orig_op->operand_num);
01753            }
01754          else if (parse_special_fn (op->operand_name,
01755                                  &fn_name, &operand_arg_name))
01756            {
01757              opname_map_e *orig_op;
01758              OpType typ = OP_CONSTANT;
01759 
01760              if (strcmp (fn_name, "LOW8") == 0)
01761               typ = OP_OPERAND_LOW8;
01762              else if (strcmp (fn_name, "HI24S") == 0)
01763               typ = OP_OPERAND_HI24S;
01764              else if (strcmp (fn_name, "F32MINUS") == 0)
01765               typ = OP_OPERAND_F32MINUS;
01766              else if (strcmp (fn_name, "LOW16U") == 0)
01767               typ = OP_OPERAND_LOW16U;
01768              else if (strcmp (fn_name, "HI16U") == 0)
01769               typ = OP_OPERAND_HI16U;
01770              else
01771               as_fatal (_("unknown user-defined function %s"), fn_name);
01772 
01773              orig_op = get_opmatch (&initial_insn->t.operand_map,
01774                                  operand_arg_name);
01775              if (orig_op == NULL)
01776               as_fatal (_("opcode %s: unidentified operand '%s' in '%s'"),
01777                        opcode_name, op->operand_name, to_string);
01778              append_user_fn_field_op (bi, op->operand_num,
01779                                    typ, orig_op->operand_num);
01780            }
01781          else
01782            as_fatal (_("opcode %s: could not parse operand '%s' in '%s'"),
01783                     opcode_name, op->operand_name, to_string);
01784        }
01785     }
01786 
01787   return tr;
01788 }
01789 
01790 
01791 static TransitionTable *
01792 build_transition_table (const string_pattern_pair *transitions,
01793                      int transition_count,
01794                      transition_cmp_fn cmp)
01795 {
01796   TransitionTable *table = NULL;
01797   int num_opcodes = xtensa_isa_num_opcodes (xtensa_default_isa);
01798   int i, tnum;
01799 
01800   if (table != NULL)
01801     return table;
01802 
01803   /* Otherwise, build it now.  */
01804   table = (TransitionTable *) xmalloc (sizeof (TransitionTable));
01805   table->num_opcodes = num_opcodes;
01806   table->table =
01807     (TransitionList **) xmalloc (sizeof (TransitionTable *) * num_opcodes);
01808 
01809   for (i = 0; i < num_opcodes; i++)
01810     table->table[i] = NULL;
01811 
01812   for (tnum = 0; tnum < transition_count; tnum++)
01813     {
01814       const char *from_string = transitions[tnum].pattern;
01815       const char *to_string = transitions[tnum].replacement;
01816 
01817       insn_pattern initial_insn;
01818       insn_repl replace_insns;
01819       TransitionRule *tr;
01820 
01821       init_insn_pattern (&initial_insn);
01822       if (!parse_insn_pattern (from_string, &initial_insn))
01823        as_fatal (_("could not parse INSN_PATTERN '%s'"), from_string);
01824 
01825       init_insn_repl (&replace_insns);
01826       if (!parse_insn_repl (to_string, &replace_insns))
01827        as_fatal (_("could not parse INSN_REPL '%s'"), to_string);
01828 
01829       if (transition_applies (&initial_insn, from_string, to_string))
01830        {
01831          tr = build_transition (&initial_insn, &replace_insns,
01832                              from_string, to_string);
01833          if (tr)
01834            append_transition (table, tr->opcode, tr, cmp);
01835          else
01836            {
01837 #if TENSILICA_DEBUG
01838              as_warn (_("could not build transition for %s => %s"),
01839                      from_string, to_string);
01840 #endif
01841            }
01842        }
01843 
01844       clear_insn_repl (&replace_insns);
01845       clear_insn_pattern (&initial_insn);
01846     }
01847   return table;
01848 }
01849 
01850 
01851 extern TransitionTable *
01852 xg_build_widen_table (transition_cmp_fn cmp)
01853 {
01854   static TransitionTable *table = NULL;
01855   if (table == NULL)
01856     table = build_transition_table (widen_spec_list, WIDEN_COUNT, cmp);
01857   return table;
01858 }
01859 
01860 
01861 extern TransitionTable *
01862 xg_build_simplify_table (transition_cmp_fn cmp)
01863 {
01864   static TransitionTable *table = NULL;
01865   if (table == NULL)
01866     table = build_transition_table (simplify_spec_list, SIMPLIFY_COUNT, cmp);
01867   return table;
01868 }