home *** CD-ROM | disk | FTP | other *** search
/ Education Sampler 1992 [NeXTSTEP] / Education_1992_Sampler.iso / NeXT / GnuSource / cc-61.0.1 / cc / regclass.c < prev    next >
C/C++ Source or Header  |  1991-08-01  |  30KB  |  1,127 lines
  1. /* Compute register class preferences for pseudo-registers.
  2.    Copyright (C) 1987-1991 Free Software Foundation, Inc.
  3.  
  4. This file is part of GNU CC.
  5.  
  6. GNU CC 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. GNU CC 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 GNU CC; see the file COPYING.  If not, write to
  18. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19.  
  20.  
  21. /* This file contains two passes of the compiler: reg_scan and reg_class.
  22.    It also defines some tables of information about the hardware registers
  23.    and a function init_reg_sets to initialize the tables.  */
  24.  
  25. #include "config.h"
  26. #include "rtl.h"
  27. #include "hard-reg-set.h"
  28. #include "flags.h"
  29. #include "basic-block.h"
  30. #include "regs.h"
  31. #include "insn-config.h"
  32. #include "recog.h"
  33.  
  34. #define max(A,B) ((A) > (B) ? (A) : (B))
  35. #define min(A,B) ((A) < (B) ? (A) : (B))
  36.  
  37. #ifndef REGISTER_MOVE_COST
  38. #define REGISTER_MOVE_COST(x, y) 2
  39. #endif
  40.  
  41. /* Register tables used by many passes.  */
  42.  
  43. /* Indexed by hard register number, contains 1 for registers
  44.    that are fixed use (stack pointer, pc, frame pointer, etc.).
  45.    These are the registers that cannot be used to allocate
  46.    a pseudo reg whose life does not cross calls.  */
  47.  
  48. char fixed_regs[FIRST_PSEUDO_REGISTER];
  49.  
  50. /* Same info as a HARD_REG_SET.  */
  51.  
  52. HARD_REG_SET fixed_reg_set;
  53.  
  54. /* Data for initializing the above.  */
  55.  
  56. static char initial_fixed_regs[] = FIXED_REGISTERS;
  57.  
  58. /* Indexed by hard register number, contains 1 for registers
  59.    that are fixed use or are clobbered by function calls.
  60.    These are the registers that cannot be used to allocate
  61.    a pseudo reg whose life crosses calls.  */
  62.  
  63. char call_used_regs[FIRST_PSEUDO_REGISTER];
  64.  
  65. /* Same info as a HARD_REG_SET.  */
  66.  
  67. HARD_REG_SET call_used_reg_set;
  68.  
  69. /* Data for initializing the above.  */
  70.  
  71. static char initial_call_used_regs[] = CALL_USED_REGISTERS;
  72.   
  73. /* Indexed by hard register number, contains 1 for registers that are
  74.    fixed use -- i.e. in fixed_regs -- or a function value return register
  75.    or STRUCT_VALUE_REGNUM or STATIC_CHAIN_REGNUM.  These are the
  76.    registers that cannot hold quantities across calls even if we are
  77.    willing to save and restore them.  */
  78.  
  79. char call_fixed_regs[FIRST_PSEUDO_REGISTER];
  80.  
  81. /* The same info as a HARD_REG_SET.  */
  82.  
  83. HARD_REG_SET call_fixed_reg_set;
  84.  
  85. /* Number of non-fixed registers.  */
  86.  
  87. int n_non_fixed_regs;
  88.  
  89. /* Indexed by hard register number, contains 1 for registers
  90.    that are being used for global register decls.
  91.    These must be exempt from ordinary flow analysis
  92.    and are also considered fixed.  */
  93.  
  94. char global_regs[FIRST_PSEUDO_REGISTER];
  95.   
  96. /* Table of register numbers in the order in which to try to use them.  */
  97. #ifdef REG_ALLOC_ORDER
  98. int reg_alloc_order[FIRST_PSEUDO_REGISTER] = REG_ALLOC_ORDER;
  99. #endif
  100.  
  101. /* For each reg class, a HARD_REG_SET saying which registers are in it.  */
  102.  
  103. HARD_REG_SET reg_class_contents[] = REG_CLASS_CONTENTS;
  104.  
  105. /* For each reg class, number of regs it contains.  */
  106.  
  107. int reg_class_size[N_REG_CLASSES];
  108.  
  109. /* For each reg class, table listing all the containing classes.  */
  110.  
  111. enum reg_class reg_class_superclasses[N_REG_CLASSES][N_REG_CLASSES];
  112.  
  113. /* For each reg class, table listing all the classes contained in it.  */
  114.  
  115. enum reg_class reg_class_subclasses[N_REG_CLASSES][N_REG_CLASSES];
  116.  
  117. /* For each pair of reg classes,
  118.    a largest reg class contained in their union.  */
  119.  
  120. enum reg_class reg_class_subunion[N_REG_CLASSES][N_REG_CLASSES];
  121.  
  122. /* For each pair of reg classes,
  123.    the smallest reg class containing their union.  */
  124.  
  125. enum reg_class reg_class_superunion[N_REG_CLASSES][N_REG_CLASSES];
  126.  
  127. /* Array containing all of the register names */
  128.  
  129. char *reg_names[] = REGISTER_NAMES;
  130.  
  131.  
  132. /* Indexed by n, gives number of times (REG n) is set or clobbered.
  133.    This information remains valid for the rest of the compilation
  134.    of the current function; it is used to control register allocation.
  135.  
  136.    This information applies to both hard registers and pseudo registers,
  137.    unlike much of the information above.  */
  138.  
  139. short *reg_n_sets;
  140.  
  141. /* Function called only once to initialize the above data on reg usage.
  142.    Once this is done, various switches may override.  */
  143.  
  144. void
  145. init_reg_sets ()
  146. {
  147.   register int i, j;
  148.  
  149.   bcopy (initial_fixed_regs, fixed_regs, sizeof fixed_regs);
  150.   bcopy (initial_call_used_regs, call_used_regs, sizeof call_used_regs);
  151.   bzero (global_regs, sizeof global_regs);
  152.  
  153.   /* Compute number of hard regs in each class.  */
  154.  
  155.   bzero (reg_class_size, sizeof reg_class_size);
  156.   for (i = 0; i < N_REG_CLASSES; i++)
  157.     for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
  158.       if (TEST_HARD_REG_BIT (reg_class_contents[i], j))
  159.     reg_class_size[i]++;
  160.  
  161.   /* Initialize the table of subunions.
  162.      reg_class_subunion[I][J] gets the largest-numbered reg-class
  163.      that is contained in the union of classes I and J.  */
  164.  
  165.   for (i = 0; i < N_REG_CLASSES; i++)
  166.     {
  167.       for (j = 0; j < N_REG_CLASSES; j++)
  168.     {
  169. #ifdef HARD_REG_SET
  170.       register        /* Declare it register if it's a scalar.  */
  171. #endif
  172.         HARD_REG_SET c;
  173.       register int k;
  174.  
  175.       COPY_HARD_REG_SET (c, reg_class_contents[i]);
  176.       IOR_HARD_REG_SET (c, reg_class_contents[j]);
  177.       for (k = 0; k < N_REG_CLASSES; k++)
  178.         {
  179.           GO_IF_HARD_REG_SUBSET (reg_class_contents[k], c,
  180.                      subclass1);
  181.           continue;
  182.  
  183.         subclass1:
  184.           /* keep the largest subclass */        /* SPEE 900308 */
  185.           GO_IF_HARD_REG_SUBSET (reg_class_contents[k],
  186.                      reg_class_contents[(int) reg_class_subunion[i][j]],
  187.                      subclass2);
  188.           reg_class_subunion[i][j] = (enum reg_class) k;
  189.         subclass2:
  190.           ;
  191.         }
  192.     }
  193.     }
  194.  
  195.   /* Initialize the table of superunions.
  196.      reg_class_superunion[I][J] gets the smallest-numbered reg-class
  197.      containing the union of classes I and J.  */
  198.  
  199.   for (i = 0; i < N_REG_CLASSES; i++)
  200.     {
  201.       for (j = 0; j < N_REG_CLASSES; j++)
  202.     {
  203. #ifdef HARD_REG_SET
  204.       register        /* Declare it register if it's a scalar.  */
  205. #endif
  206.         HARD_REG_SET c;
  207.       register int k;
  208.  
  209.       COPY_HARD_REG_SET (c, reg_class_contents[i]);
  210.       IOR_HARD_REG_SET (c, reg_class_contents[j]);
  211.       for (k = 0; k < N_REG_CLASSES; k++)
  212.         GO_IF_HARD_REG_SUBSET (c, reg_class_contents[k], superclass);
  213.  
  214.     superclass:
  215.       reg_class_superunion[i][j] = (enum reg_class) k;
  216.     }
  217.     }
  218.  
  219.   /* Initialize the tables of subclasses and superclasses of each reg class.
  220.      First clear the whole table, then add the elements as they are found.  */
  221.  
  222.   for (i = 0; i < N_REG_CLASSES; i++)
  223.     {
  224.       for (j = 0; j < N_REG_CLASSES; j++)
  225.     {
  226.       reg_class_superclasses[i][j] = LIM_REG_CLASSES;
  227.       reg_class_subclasses[i][j] = LIM_REG_CLASSES;
  228.     }
  229.     }
  230.  
  231.   for (i = 0; i < N_REG_CLASSES; i++)
  232.     {
  233.       if (i == (int) NO_REGS)
  234.     continue;
  235.  
  236.       for (j = i + 1; j < N_REG_CLASSES; j++)
  237.     {
  238.       enum reg_class *p;
  239.  
  240.       GO_IF_HARD_REG_SUBSET (reg_class_contents[i], reg_class_contents[j],
  241.                  subclass);
  242.       continue;
  243.     subclass:
  244.       /* Reg class I is a subclass of J.
  245.          Add J to the table of superclasses of I.  */
  246.       p = ®_class_superclasses[i][0];
  247.       while (*p != LIM_REG_CLASSES) p++;
  248.       *p = (enum reg_class) j;
  249.       /* Add I to the table of superclasses of J.  */
  250.       p = ®_class_subclasses[j][0];
  251.       while (*p != LIM_REG_CLASSES) p++;
  252.       *p = (enum reg_class) i;
  253.     }
  254.     }
  255. }
  256.  
  257. /* After switches have been processed, which perhaps alter
  258.    `fixed_regs' and `call_used_regs', convert them to HARD_REG_SETs.  */
  259.  
  260. void
  261. init_reg_sets_1 ()
  262. {
  263.   register int i;
  264.  
  265.   /* This macro allows the fixed or call-used registers
  266.      to depend on target flags.  */
  267.  
  268. #ifdef CONDITIONAL_REGISTER_USAGE
  269.   CONDITIONAL_REGISTER_USAGE;
  270. #endif
  271.  
  272.   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
  273.     if (global_regs[i])
  274.       {
  275.     if (call_used_regs[i] && ! fixed_regs[i])
  276.       warning ("call-clobbered register used for global register variable");
  277.     fixed_regs[i] = 1;
  278.     /* Prevent saving/restoring of this reg.  */
  279.     call_used_regs[i] = 1;
  280.       }
  281.  
  282.   /* Initialize "constant" tables.  */
  283.  
  284.   CLEAR_HARD_REG_SET (fixed_reg_set);
  285.   CLEAR_HARD_REG_SET (call_used_reg_set);
  286.   CLEAR_HARD_REG_SET (call_fixed_reg_set);
  287.  
  288.   bcopy (fixed_regs, call_fixed_regs, sizeof call_fixed_regs);
  289. #ifdef STRUCT_VALUE_REGNUM
  290.   call_fixed_regs[STRUCT_VALUE_REGNUM] = 1;
  291. #endif
  292. #ifdef STATIC_CHAIN_REGNUM
  293.   call_fixed_regs[STATIC_CHAIN_REGNUM] = 1;
  294. #endif
  295.  
  296.   n_non_fixed_regs = 0;
  297.  
  298.   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
  299.     {
  300.       if (FUNCTION_VALUE_REGNO_P (i))
  301.     call_fixed_regs[i] = 1;
  302.       if (fixed_regs[i])
  303.     SET_HARD_REG_BIT (fixed_reg_set, i);
  304.       else
  305.     n_non_fixed_regs++;
  306.  
  307.       if (call_used_regs[i])
  308.     SET_HARD_REG_BIT (call_used_reg_set, i);
  309.       if (call_fixed_regs[i])
  310.     SET_HARD_REG_BIT (call_fixed_reg_set, i);
  311.     }
  312. }
  313.  
  314. /* Specify the usage characteristics of the register named NAME.
  315.    It should be a fixed register if FIXED and a
  316.    call-used register if CALL_USED.  */
  317.  
  318. void
  319. fix_register (name, fixed, call_used)
  320.      char *name;
  321.      int fixed, call_used;
  322. {
  323.   int i;
  324.  
  325.   /* Decode the name and update the primary form of
  326.      the register info.  */
  327.  
  328.   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
  329.     if (!strcmp (reg_names[i], name))
  330.       {
  331.     fixed_regs[i] = fixed;
  332.     call_used_regs[i] = call_used;
  333.     break;
  334.       }
  335.  
  336.   if (i == FIRST_PSEUDO_REGISTER)
  337.     {
  338.       warning ("unknown register name: %s", name);
  339.       return;
  340.     }
  341. }
  342.  
  343. /* Now the data and code for the `regclass' pass, which happens
  344.    just before local-alloc.  */
  345.  
  346. /* savings[R].savings[CL] is twice the amount saved by putting register R
  347.    in class CL.  This data is used within `regclass' and freed
  348.    when it is finished.  */
  349.  
  350. struct savings
  351. {
  352.   short savings[N_REG_CLASSES];
  353.   short memcost;
  354.   short nrefs;
  355. };
  356.  
  357. static struct savings *savings;
  358.  
  359. /* (enum reg_class) prefclass[R] is the preferred class for pseudo number R.
  360.    This is available after `regclass' is run.  */
  361.  
  362. static char *prefclass;
  363.  
  364. /* preferred_or_nothing[R] is nonzero if we should put pseudo number R
  365.    in memory if we can't get its perferred class.
  366.    This is available after `regclass' is run.  */
  367.  
  368. static char *preferred_or_nothing;
  369.  
  370. /* Record the depth of loops that we are in, 1 for no loops.  */
  371.  
  372. static int loop_depth;
  373.  
  374. void reg_class_record ();
  375. void record_address_regs ();
  376.  
  377.  
  378. /* Return the reg_class in which pseudo reg number REGNO is best allocated.
  379.    This function is sometimes called before the info has been computed.
  380.    When that happens, just return GENERAL_REGS, which is innocuous.  */
  381.  
  382. enum reg_class
  383. reg_preferred_class (regno)
  384.      int regno;
  385. {
  386.   if (prefclass == 0)
  387.     return GENERAL_REGS;
  388.   return (enum reg_class) prefclass[regno];
  389. }
  390.  
  391. int
  392. reg_preferred_or_nothing (regno)
  393. {
  394.   if (prefclass == 0)
  395.     return 0;
  396.   return preferred_or_nothing[regno];
  397. }
  398.  
  399. /* This prevents dump_flow_info from losing if called
  400.    before regclass is run.  */
  401.  
  402. void
  403. regclass_init ()
  404. {
  405.   prefclass = 0;
  406. }
  407.  
  408. /* This is a pass of the compiler that scans all instructions
  409.    and calculates the preferred class for each pseudo-register.
  410.    This information can be accessed later by calling `reg_preferred_class'.
  411.    This pass comes just before local register allocation.  */
  412.  
  413. void
  414. regclass (f, nregs)
  415.      rtx f;
  416.      int nregs;
  417. {
  418. #ifdef REGISTER_CONSTRAINTS
  419.   register rtx insn;
  420.   register int i;
  421.  
  422.   init_recog ();
  423.  
  424.   /* Zero out our accumulation of the cost of each class for each reg.  */
  425.  
  426.   savings = (struct savings *) alloca (nregs * sizeof (struct savings));
  427.   bzero (savings, nregs * sizeof (struct savings));
  428.  
  429.   loop_depth = 1;
  430.  
  431.   /* Scan the instructions and record each time it would
  432.      save code to put a certain register in a certain class.  */
  433.  
  434.   for (insn = f; insn; insn = NEXT_INSN (insn))
  435.     {
  436.       if (GET_CODE (insn) == NOTE
  437.       && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
  438.     loop_depth++;
  439.       else if (GET_CODE (insn) == NOTE
  440.            && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
  441.     loop_depth--;
  442.       else if ((GET_CODE (insn) == INSN
  443.         && GET_CODE (PATTERN (insn)) != USE
  444.         && GET_CODE (PATTERN (insn)) != CLOBBER
  445.         && GET_CODE (PATTERN (insn)) != ASM_INPUT)
  446.            || (GET_CODE (insn) == JUMP_INSN
  447.            && GET_CODE (PATTERN (insn)) != ADDR_VEC
  448.            && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC)
  449.            || GET_CODE (insn) == CALL_INSN)
  450.     {
  451.       if (GET_CODE (insn) == INSN && asm_noperands (PATTERN (insn)) >= 0)
  452.         {
  453.           int noperands = asm_noperands (PATTERN (insn));
  454.           /* We don't use alloca because alloca would not free
  455.          any of the space until this function returns.  */
  456.           rtx *operands = (rtx *) oballoc (noperands * sizeof (rtx));
  457.           char **constraints
  458.         = (char **) oballoc (noperands * sizeof (char *));
  459.  
  460.           decode_asm_operands (PATTERN (insn), operands, 0, constraints, 0);
  461.  
  462.           for (i = noperands - 1; i >= 0; i--)
  463.         reg_class_record (operands[i], i, constraints);
  464.  
  465.           obfree (operands);
  466.         }
  467.       else
  468.         {
  469.           int insn_code_number = recog_memoized (insn);
  470.  
  471.           insn_extract (insn);
  472.  
  473.           for (i = insn_n_operands[insn_code_number] - 1; i >= 0; i--)
  474.         reg_class_record (recog_operand[i], i,
  475.                   insn_operand_constraint[insn_code_number]);
  476.  
  477.           /* If this insn loads a parameter from its stack slot,
  478.          then it represents a savings, rather than a cost,
  479.          if the parameter is stored in memory.  Record this fact.  */
  480.           if (GET_CODE (PATTERN (insn)) == SET
  481.           && GET_CODE (SET_DEST (PATTERN (insn))) == REG
  482.           && GET_CODE (SET_SRC (PATTERN (insn))) == MEM)
  483.         {
  484.           rtx note = find_reg_note (insn, REG_EQUIV, 0);
  485.           if (note != 0 && GET_CODE (XEXP (note, 0)) == MEM)
  486.             savings[REGNO (SET_DEST (PATTERN (insn)))].memcost
  487.               -= 2 * loop_depth;
  488.         }
  489.           
  490.           /* Improve handling of two-address insns such as
  491.          (set X (ashift CONST Y)) where CONST must be made to match X.
  492.          Change it into two insns: (set X CONST)  (set X (ashift X Y)).
  493.          If we left this for reloading, it would probably get three
  494.          insns because X and Y might go in the same place.
  495.          This prevents X and Y from receiving the same hard reg.
  496.  
  497.          We can only do this if the modes of operands 0 and 1 (which
  498.          might not be the same) are tieable.  */
  499.  
  500.           if (optimize
  501.           && insn_n_operands[insn_code_number] >= 3
  502.           && insn_operand_constraint[insn_code_number][1][0] == '0'
  503.           && insn_operand_constraint[insn_code_number][1][1] == 0
  504.           && CONSTANT_P (recog_operand[1])
  505.           && ! rtx_equal_p (recog_operand[0], recog_operand[1])
  506.           && ! rtx_equal_p (recog_operand[0], recog_operand[2])
  507.           && GET_CODE (recog_operand[0]) == REG
  508.           && MODES_TIEABLE_P (GET_MODE (recog_operand[0]),
  509.                       insn_operand_mode[insn_code_number][1]))
  510.         {
  511.           rtx previnsn = prev_real_insn (insn);
  512.           rtx dest
  513.             = gen_lowpart (insn_operand_mode[insn_code_number][1],
  514.                    recog_operand[0]);
  515.           rtx newinsn
  516.             = emit_insn_before (gen_move_insn (dest, recog_operand[1]),
  517.                     insn);
  518.  
  519.           /* If this insn was the start of a basic block,
  520.              include the new insn in that block.  */
  521.           if (previnsn == 0 || GET_CODE (previnsn) == JUMP_INSN)
  522.             {
  523.               int b;
  524.               for (b = 0; b < n_basic_blocks; b++)
  525.             if (insn == basic_block_head[b])
  526.               basic_block_head[b] = newinsn;
  527.             }
  528.  
  529.           /* This makes one more setting of new insns's destination. */
  530.           reg_n_sets[REGNO (recog_operand[0])]++;
  531.  
  532.           *recog_operand_loc[1] = recog_operand[0];
  533.           for (i = insn_n_dups[insn_code_number] - 1; i >= 0; i--)
  534.             if (recog_dup_num[i] == 1)
  535.               *recog_dup_loc[i] = recog_operand[0];
  536.         }
  537.         }
  538.     }
  539.     }
  540.  
  541.   /* Now for each register look at how desirable each class is
  542.      and find which class is preferred.  Store that in `prefclass[REGNO]'.  */
  543.     
  544.   prefclass = (char *) oballoc (nregs);
  545.     
  546.   preferred_or_nothing = (char *) oballoc (nregs);
  547.  
  548.   for (i = FIRST_PSEUDO_REGISTER; i < nregs; i++)
  549.     {
  550.       register int best_savings = 0;
  551.       enum reg_class best = ALL_REGS;
  552.  
  553.       /* This is an enum reg_class, but we call it an int
  554.      to save lots of casts.  */
  555.       register int class;
  556.       register struct savings *p = &savings[i];
  557.  
  558.       for (class = (int) ALL_REGS - 1; class > 0; class--)
  559.     {
  560.       if (p->savings[class] > best_savings)
  561.         {
  562.           best_savings = p->savings[class];
  563.           best = (enum reg_class) class;
  564.         }
  565.       else if (p->savings[class] == best_savings)
  566.         {
  567.           best = reg_class_subunion[(int)best][class];
  568.         }
  569.     }
  570.  
  571. #if 0
  572.       /* Note that best_savings is twice number of places something
  573.      is saved.  */
  574.       if ((best_savings - p->savings[(int) GENERAL_REGS]) * 5 < reg_n_refs[i])
  575.     prefclass[i] = (int) GENERAL_REGS;
  576.       else
  577.     prefclass[i] = (int) best;
  578. #else
  579.       /* We cast to (int) because (char) hits bugs in some compilers.  */
  580.       prefclass[i] = (int) best;
  581. #endif
  582.  
  583.       /* reg_n_refs + p->memcost measures the cost of putting in memory.
  584.      If a GENERAL_REG is no better, don't even try for one.
  585.      Since savings and memcost are 2 * number of refs,
  586.      this effectively counts each memory operand not needing reloading
  587.      as costing 1/2 of a reload insn.  */
  588.       if (reg_n_refs != 0)
  589.     preferred_or_nothing[i]
  590.       = ((best_savings - p->savings[(int) GENERAL_REGS])
  591.          >= p->nrefs + p->memcost);
  592.     }
  593. #endif /* REGISTER_CONSTRAINTS */
  594. }
  595.  
  596. #ifdef REGISTER_CONSTRAINTS
  597.  
  598. /* Scan an operand OP for register class preferences.
  599.    OPNO is the operand number, and CONSTRAINTS is the constraint
  600.    vector for the insn.
  601.  
  602.    Record the preferred register classes from the constraint for OP
  603.    if OP is a register.  If OP is a memory reference, record suitable
  604.    preferences for registers used in the address.  */
  605.  
  606. void
  607. reg_class_record (op, opno, constraints)
  608.      rtx op;
  609.      int opno;
  610.      char **constraints;
  611. {
  612.   char *constraint = constraints[opno];
  613.   register char *p;
  614.   register enum reg_class class = NO_REGS;
  615.   char *next = 0;
  616.   int memok = 0;
  617.   int double_cost = 0;
  618.  
  619.   if (op == 0)
  620.     return;
  621.  
  622.   while (1)
  623.     {
  624.       if (GET_CODE (op) == SUBREG)
  625.     op = SUBREG_REG (op);
  626.       else break;
  627.     }
  628.  
  629.   /* Memory reference: scan the address.  */
  630.  
  631.   if (GET_CODE (op) == MEM)
  632.     record_address_regs (XEXP (op, 0), 2, 0);
  633.  
  634.   if (GET_CODE (op) != REG)
  635.     {
  636.       /* If the constraint says the operand is supposed to BE an address,
  637.      scan it as one.  */
  638.  
  639.       if (constraint != 0 && constraint[0] == 'p')
  640.     record_address_regs (op, 2, 0);
  641.       return;
  642.     }
  643.  
  644.   /* Operand is a register: examine the constraint for specified classes.  */
  645.  
  646.   for (p = constraint; *p || next; p++)
  647.     {
  648.       enum reg_class new_class = NO_REGS;
  649.  
  650.       if (*p == 0)
  651.     {
  652.       p = next;
  653.       next = 0;
  654.     }
  655.       switch (*p)
  656.     {
  657.     case '=':
  658.     case '?':
  659.     case '#':
  660.     case '&':
  661.     case '!':
  662.     case '%':
  663.     case 'E':
  664.     case 'F':
  665.     case 'G':
  666.     case 'H':
  667.     case 'i':
  668.     case 'n':
  669.     case 's':
  670.     case 'p':
  671.     case ',':
  672.     case 'I':
  673.     case 'J':
  674.     case 'K':
  675.     case 'L':
  676.     case 'M':
  677.     case 'N':
  678.     case 'O':
  679.     case 'P':
  680.     case 'Q':
  681.     case 'R':
  682.     case 'S':
  683.     case 'T':
  684.     case 'U':
  685.     case 'X':
  686.       break;
  687.  
  688.     case '+':
  689.       /* An input-output operand is twice as costly if it loses.  */
  690.       double_cost = 1;
  691.       break;
  692.  
  693.     case 'm':
  694.     case 'o':
  695.       memok = 1;
  696.       break;
  697.  
  698.       /* * means ignore following letter
  699.          when choosing register preferences.  */
  700.     case '*':
  701.       p++;
  702.       break;
  703.  
  704.     case 'g':
  705.     case 'r':
  706.       new_class = GENERAL_REGS;
  707.       break;
  708.  
  709.     case '0':
  710.     case '1':
  711.     case '2':
  712.     case '3':
  713.     case '4':
  714.       /* If constraint says "match another operand",
  715.          use that operand's constraint to choose preferences.  */
  716.       next = constraints[*p - '0'];
  717.       break;
  718.  
  719.     default:
  720.       new_class = REG_CLASS_FROM_LETTER (*p);
  721.       break;
  722.     }
  723.  
  724.       /* If this object can fit into the class requested, compute the subunion
  725.      of the requested class and classes found so far.  */
  726.       if (CLASS_MAX_NREGS (new_class, GET_MODE (op))
  727.       <= reg_class_size[(int) new_class])
  728.     class = reg_class_subunion[(int) class][(int) new_class];
  729.     }
  730.  
  731.   {
  732.     register int i;
  733.     register struct savings *pp;
  734.     register enum reg_class class1;
  735.     int cost = 2 * (1 + double_cost) * loop_depth;
  736.     pp = &savings[REGNO (op)];
  737.  
  738.     /* Increment the savings for this reg
  739.        for each class contained in the one the constraint asks for.  */
  740.  
  741.     if (class != NO_REGS && class != ALL_REGS)
  742.       {
  743.     int extracost;
  744.  
  745.     pp->savings[(int) class] += cost;
  746.     for (i = 0; ; i++)
  747.       {
  748.         class1 = reg_class_subclasses[(int)class][i];
  749.         if (class1 == LIM_REG_CLASSES)
  750.           break;
  751.         pp->savings[(int) class1] += cost;
  752.       }
  753.     /* If it's slow to move data between this class and GENERAL_REGS,
  754.        record that fact.  */
  755.     extracost = (REGISTER_MOVE_COST (class, GENERAL_REGS) - 2) * loop_depth;
  756.     if (extracost > 0)
  757.       {
  758.         /* Check that this class and GENERAL_REGS don't overlap.
  759.            REGISTER_MOVE_COST is meaningless if there is overlap.  */
  760.         HARD_REG_SET temp;
  761.         COMPL_HARD_REG_SET (temp, reg_class_contents[(int) class]);
  762.         GO_IF_HARD_REG_SUBSET (reg_class_contents[(int) GENERAL_REGS],
  763.                    temp, label1);
  764.         /* Overlap.  */
  765.         goto label2;
  766.  
  767.       label1: /* No overlap.  */
  768.         /* Charge this extra cost to GENERAL_REGS
  769.            and all its subclasses (none of which overlap this class).  */
  770.         extracost = extracost * cost / (2 * loop_depth);
  771.         pp->savings[(int) GENERAL_REGS] -= extracost;
  772.         for (i = 0; ; i++)
  773.           {
  774.         class1 = reg_class_subclasses[(int)GENERAL_REGS][i];
  775.         if (class1 == LIM_REG_CLASSES)
  776.           break;
  777.         pp->savings[(int) class1] -= extracost;
  778.           }
  779.  
  780.       label2: ;
  781.       }
  782.       }
  783.  
  784.     if (! memok)
  785.       pp->memcost += (1 + 2 * double_cost) * loop_depth;
  786.     pp->nrefs += loop_depth;
  787.   }
  788. }
  789.  
  790. /* Record the pseudo registers we must reload into hard registers
  791.    in a subexpression of a memory address, X.
  792.    BCOST is the cost if X is a register and it fails to be in BASE_REG_CLASS.
  793.    ICOST is the cost if it fails to be in INDEX_REG_CLASS. */
  794.  
  795. void
  796. record_address_regs (x, bcost, icost)
  797.      rtx x;
  798.      int bcost, icost;
  799. {
  800.   register enum rtx_code code = GET_CODE (x);
  801.  
  802.   switch (code)
  803.     {
  804.     case CONST_INT:
  805.     case CONST:
  806.     case CC0:
  807.     case PC:
  808.     case SYMBOL_REF:
  809.     case LABEL_REF:
  810.       return;
  811.  
  812.     case PLUS:
  813.       /* When we have an address that is a sum,
  814.      we must determine whether registers are "base" or "index" regs.
  815.      If there is a sum of two registers, we must choose one to be
  816.      the "base".  Luckily, we can use the REGNO_POINTER_FLAG
  817.      to make a good choice most of the time.  */
  818.       {
  819.     rtx arg0 = XEXP (x, 0);
  820.     rtx arg1 = XEXP (x, 1);
  821.     register enum rtx_code code0 = GET_CODE (arg0);
  822.     register enum rtx_code code1 = GET_CODE (arg1);
  823.     int icost0 = 0;
  824.     int icost1 = 0;
  825.     int suppress1 = 0;
  826.     int suppress0 = 0;
  827.  
  828.     /* Look inside subregs.  */
  829.     while (code0 == SUBREG)
  830.       arg0 = SUBREG_REG (arg0), code0 = GET_CODE (arg0);
  831.     while (code1 == SUBREG)
  832.       arg1 = SUBREG_REG (arg1), code1 = GET_CODE (arg1);
  833.  
  834.     if (code0 == MULT || code1 == MEM)
  835.       icost0 = 2;
  836.     else if (code1 == MULT || code0 == MEM)
  837.       icost1 = 2;
  838.     else if (code0 == CONST_INT)
  839.       suppress0 = 1;
  840.     else if (code1 == CONST_INT)
  841.       suppress1 = 1;
  842.     else if (code0 == REG && code1 == REG)
  843.       {
  844.         if (REGNO_POINTER_FLAG (REGNO (arg0)))
  845.           icost1 = 2;
  846.         else if (REGNO_POINTER_FLAG (REGNO (arg1)))
  847.           icost0 = 2;
  848.         else
  849.           icost0 = icost1 = 1;
  850.       }
  851.     else if (code0 == REG)
  852.       {
  853.         if (code1 == PLUS
  854.         && ! REGNO_POINTER_FLAG (REGNO (arg0)))
  855.           icost0 = 2;
  856.         else
  857.           REGNO_POINTER_FLAG (REGNO (arg0)) = 1;
  858.       }
  859.     else if (code1 == REG)
  860.       {
  861.         if (code0 == PLUS
  862.         && ! REGNO_POINTER_FLAG (REGNO (arg1)))
  863.           icost1 = 2;
  864.         else
  865.           REGNO_POINTER_FLAG (REGNO (arg1)) = 1;
  866.       }
  867.  
  868.     /* ICOST0 determines whether we are treating operand 0
  869.        as a base register or as an index register.
  870.        SUPPRESS0 nonzero means it isn't a register at all.
  871.        ICOST1 and SUPPRESS1 are likewise for operand 1.  */
  872.  
  873.     if (! suppress0)
  874.       record_address_regs (arg0, 2 - icost0, icost0);
  875.     if (! suppress1)
  876.       record_address_regs (arg1, 2 - icost1, icost1);
  877.       }
  878.       break;
  879.  
  880.     case POST_INC:
  881.     case PRE_INC:
  882.     case POST_DEC:
  883.     case PRE_DEC:
  884.       /* Double the importance of a pseudo register that is incremented
  885.      or decremented, since it would take two extra insns
  886.      if it ends up in the wrong place.  */
  887.       record_address_regs (XEXP (x, 0), 2 * bcost, 2 * icost);
  888.       break;
  889.  
  890.     case REG:
  891.       {
  892.     register struct savings *pp;
  893.     register enum reg_class class, class1;
  894.     pp = &savings[REGNO (x)];
  895.     pp->nrefs += loop_depth;
  896.  
  897.     /* We have an address (or part of one) that is just one register.  */
  898.  
  899.     /* Record BCOST worth of savings for classes contained
  900.        in BASE_REG_CLASS.  */
  901.  
  902.     class = BASE_REG_CLASS;
  903.     if (class != NO_REGS && class != ALL_REGS)
  904.       {
  905.         register int i;
  906.         pp->savings[(int) class] += bcost * loop_depth;
  907.         for (i = 0; ; i++)
  908.           {
  909.         class1 = reg_class_subclasses[(int)class][i];
  910.         if (class1 == LIM_REG_CLASSES)
  911.           break;
  912.         pp->savings[(int) class1] += bcost * loop_depth;
  913.           }
  914.       }
  915.  
  916.     /* Record ICOST worth of savings for classes contained
  917.        in INDEX_REG_CLASS.  */
  918.  
  919.     class = INDEX_REG_CLASS;
  920.     if (icost != 0 && class != NO_REGS && class != ALL_REGS)
  921.       {
  922.         register int i;
  923.         pp->savings[(int) class] += icost * loop_depth;
  924.         for (i = 0; ; i++)
  925.           {
  926.         class1 = reg_class_subclasses[(int)class][i];
  927.         if (class1 == LIM_REG_CLASSES)
  928.           break;
  929.         pp->savings[(int) class1] += icost * loop_depth;
  930.           }
  931.       }
  932.       }
  933.       break;
  934.  
  935.     default:
  936.       {
  937.     register char *fmt = GET_RTX_FORMAT (code);
  938.     register int i;
  939.     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  940.       if (fmt[i] == 'e')
  941.         record_address_regs (XEXP (x, i), bcost, icost);
  942.       }
  943.     }
  944. }
  945. #endif /* REGISTER_CONSTRAINTS */
  946.  
  947. /* This is the `regscan' pass of the compiler, run just before cse
  948.    and again just before loop.
  949.  
  950.    It finds the first and last use of each pseudo-register
  951.    and records them in the vectors regno_first_uid, regno_last_uid
  952.    and counts the number of sets in the vector reg_n_sets.
  953.  
  954.    REPEAT is nonzero the second time this is called.  */
  955.  
  956. /* Indexed by pseudo register number, gives uid of first insn using the reg
  957.    (as of the time reg_scan is called).  */
  958.  
  959. short *regno_first_uid;
  960.  
  961. /* Indexed by pseudo register number, gives uid of last insn using the reg
  962.    (as of the time reg_scan is called).  */
  963.  
  964. short *regno_last_uid;
  965.  
  966. /* Record the number of registers we used when we allocated the above two
  967.    tables.  If we are called again with more than this, we must re-allocate
  968.    the tables.  */
  969.  
  970. static int highest_regno_in_uid_map;
  971.  
  972. /* Maximum number of parallel sets and clobbers in any insn in this fn.
  973.    Always at least 3, since the combiner could put that many togetherm
  974.    and we want this to remain correct for all the remaining passes.  */
  975.  
  976. int max_parallel;
  977.  
  978. void reg_scan_mark_refs ();
  979.  
  980. void
  981. reg_scan (f, nregs, repeat)
  982.      rtx f;
  983.      int nregs;
  984.      int repeat;
  985. {
  986.   register rtx insn;
  987.  
  988.   if (!repeat || nregs > highest_regno_in_uid_map)
  989.     {
  990.       /* Leave some spare space in case more regs are allocated.  */
  991.       highest_regno_in_uid_map = nregs + nregs / 20;
  992.       regno_first_uid
  993.     = (short *) oballoc (highest_regno_in_uid_map * sizeof (short));
  994.       regno_last_uid
  995.     = (short *) oballoc (highest_regno_in_uid_map * sizeof (short));
  996.       reg_n_sets
  997.     = (short *) oballoc (highest_regno_in_uid_map * sizeof (short));
  998.     }
  999.  
  1000.   bzero (regno_first_uid, highest_regno_in_uid_map * sizeof (short));
  1001.   bzero (regno_last_uid, highest_regno_in_uid_map * sizeof (short));
  1002.   bzero (reg_n_sets, highest_regno_in_uid_map * sizeof (short));
  1003.  
  1004.   max_parallel = 3;
  1005.  
  1006.   for (insn = f; insn; insn = NEXT_INSN (insn))
  1007.     if (GET_CODE (insn) == INSN
  1008.     || GET_CODE (insn) == CALL_INSN
  1009.     || GET_CODE (insn) == JUMP_INSN)
  1010.       {
  1011.     if (GET_CODE (PATTERN (insn)) == PARALLEL
  1012.         && XVECLEN (PATTERN (insn), 0) > max_parallel)
  1013.       max_parallel = XVECLEN (PATTERN (insn), 0);
  1014.     reg_scan_mark_refs (PATTERN (insn), INSN_UID (insn));
  1015.       }
  1016. }
  1017.  
  1018. void
  1019. reg_scan_mark_refs (x, uid)
  1020.      rtx x;
  1021.      int uid;
  1022. {
  1023.   register enum rtx_code code = GET_CODE (x);
  1024.   register rtx dest;
  1025.  
  1026.   switch (code)
  1027.     {
  1028.     case CONST_INT:
  1029.     case CONST:
  1030.     case CONST_DOUBLE:
  1031.     case CC0:
  1032.     case PC:
  1033.     case SYMBOL_REF:
  1034.     case LABEL_REF:
  1035.     case ADDR_VEC:
  1036.     case ADDR_DIFF_VEC:
  1037.       return;
  1038.  
  1039.     case REG:
  1040.       {
  1041.     register int regno = REGNO (x);
  1042.  
  1043.     regno_last_uid[regno] = uid;
  1044.     if (regno_first_uid[regno] == 0)
  1045.       regno_first_uid[regno] = uid;
  1046.       }
  1047.       break;
  1048.  
  1049.     case SET:
  1050.       /* Count a set of the destination if it is a register.  */
  1051.       for (dest = SET_DEST (x);
  1052.        GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART
  1053.        || GET_CODE (dest) == ZERO_EXTEND;
  1054.        dest = XEXP (dest, 0))
  1055.     ;
  1056.  
  1057.       if (GET_CODE (dest) == REG)
  1058.     reg_n_sets[REGNO (dest)]++;
  1059.  
  1060.       /* ... fall through ... */
  1061.  
  1062.     default:
  1063.       {
  1064.     register char *fmt = GET_RTX_FORMAT (code);
  1065.     register int i;
  1066.     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  1067.       {
  1068.         if (fmt[i] == 'e')
  1069.           reg_scan_mark_refs (XEXP (x, i), uid);
  1070.         else if (fmt[i] == 'E' && XVEC (x, i) != 0)
  1071.           {
  1072.         register int j;
  1073.         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
  1074.           reg_scan_mark_refs (XVECEXP (x, i, j), uid);          
  1075.           }
  1076.       }
  1077.       }
  1078.     }
  1079. }
  1080.  
  1081. /* Return nonzero if C1 is a subset of C2, i.e., if every register in C1
  1082.    is also in C2.  */
  1083.  
  1084. int
  1085. reg_class_subset_p (c1, c2)
  1086.      register enum reg_class c1;
  1087.      register enum reg_class c2;
  1088. {
  1089.   if (c1 == c2) return 1;
  1090.  
  1091.   if (c2 == ALL_REGS)
  1092.   win:
  1093.     return 1;
  1094.   GO_IF_HARD_REG_SUBSET (reg_class_contents[(int)c1],
  1095.              reg_class_contents[(int)c2],
  1096.              win);
  1097.   return 0;
  1098. }
  1099.  
  1100. /* Return nonzero if there is a register that is in both C1 and C2.  */
  1101.  
  1102. int
  1103. reg_classes_intersect_p (c1, c2)
  1104.      register enum reg_class c1;
  1105.      register enum reg_class c2;
  1106. {
  1107. #ifdef HARD_REG_SET
  1108.   register
  1109. #endif
  1110.     HARD_REG_SET c;
  1111.  
  1112.   if (c1 == c2) return 1;
  1113.  
  1114.   if (c1 == ALL_REGS || c2 == ALL_REGS)
  1115.     return 1;
  1116.  
  1117.   COPY_HARD_REG_SET (c, reg_class_contents[(int) c1]);
  1118.   AND_HARD_REG_SET (c, reg_class_contents[(int) c2]);
  1119.  
  1120.   GO_IF_HARD_REG_SUBSET (c, reg_class_contents[(int) NO_REGS], lose);
  1121.   return 1;
  1122.  
  1123.  lose:
  1124.   return 0;
  1125. }
  1126.  
  1127.