/* Compute register class preferences for pseudo-registers.
Copyright (C) 1987, 1988 Free Software Foundation, Inc.
This file is part of GNU CC.
GNU CC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 1, or (at your option)
GNU CC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with GNU CC; see the file COPYING. If not, write to
the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
/* This file contains two passes of the compiler: reg_scan and reg_class.
It also defines some tables of information about the hardware registers
and a function init_reg_sets to initialize the tables. */
#include "hard-reg-set.h"
#define max(A,B) ((A) > (B) ? (A) : (B))
#define min(A,B) ((A) < (B) ? (A) : (B))
/* Register tables used by many passes. */
/* Indexed by hard register number, contains 1 for registers
that are fixed use (stack pointer, pc, frame pointer, etc.).
These are the registers that cannot be used to allocate
a pseudo reg whose life does not cross calls. */
char fixed_regs
[FIRST_PSEUDO_REGISTER
];
/* Same info as a HARD_REG_SET. */
HARD_REG_SET fixed_reg_set
;
/* Data for initializing the above. */
static char initial_fixed_regs
[] = FIXED_REGISTERS
;
/* Indexed by hard register number, contains 1 for registers
that are fixed use or are clobbered by function calls.
These are the registers that cannot be used to allocate
a pseudo reg whose life crosses calls. */
char call_used_regs
[FIRST_PSEUDO_REGISTER
];
/* Same info as a HARD_REG_SET. */
HARD_REG_SET call_used_reg_set
;
/* Data for initializing the above. */
static char initial_call_used_regs
[] = CALL_USED_REGISTERS
;
/* Indexed by hard register number, contains 1 for registers that are
fixed use -- i.e. in fixed_regs -- or a function value return register
or STRUCT_VALUE_REGNUM or STATIC_CHAIN_REGNUM. These are the
registers that cannot hold quantities across calls even if we are
willing to save and restore them. */
char call_fixed_regs
[FIRST_PSEUDO_REGISTER
];
/* The same info as a HARD_REG_SET. */
HARD_REG_SET call_fixed_reg_set
;
/* Indexed by hard register number, contains 1 for registers
that are being used for global register decls.
These must be exempt from ordinary flow analysis
and are also considered fixed. */
char global_regs
[FIRST_PSEUDO_REGISTER
];
/* Table of register numbers in the order in which to try to use them. */
int reg_alloc_order
[FIRST_PSEUDO_REGISTER
] = REG_ALLOC_ORDER
;
/* For each reg class, a HARD_REG_SET saying which registers are in it. */
HARD_REG_SET reg_class_contents
[] = REG_CLASS_CONTENTS
;
/* For each reg class, number of regs it contains. */
int reg_class_size
[N_REG_CLASSES
];
/* For each reg class, table listing all the containing classes. */
enum reg_class reg_class_superclasses
[N_REG_CLASSES
][N_REG_CLASSES
];
/* For each reg class, table listing all the classes contained in it. */
enum reg_class reg_class_subclasses
[N_REG_CLASSES
][N_REG_CLASSES
];
/* For each pair of reg classes,
a largest reg class contained in their union. */
enum reg_class reg_class_subunion
[N_REG_CLASSES
][N_REG_CLASSES
];
/* Array containing all of the register names */
char *reg_names
[] = REGISTER_NAMES
;
/* Function called only once to initialize the above data on reg usage.
Once this is done, various switches may override. */
bcopy (initial_fixed_regs
, fixed_regs
, sizeof fixed_regs
);
bcopy (initial_call_used_regs
, call_used_regs
, sizeof call_used_regs
);
bzero (global_regs
, sizeof global_regs
);
/* Compute number of hard regs in each class. */
bzero (reg_class_size
, sizeof reg_class_size
);
for (i
= 0; i
< N_REG_CLASSES
; i
++)
for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
if (TEST_HARD_REG_BIT (reg_class_contents
[i
], j
))
/* Initialize the table of subunions.
reg_class_subunion[I][J] gets the largest-numbered reg-class
that is contained in the union of classes I and J. */
for (i
= 0; i
< N_REG_CLASSES
; i
++)
for (j
= 0; j
< N_REG_CLASSES
; j
++)
register /* Declare it register if it's a scalar. */
COPY_HARD_REG_SET (c
, reg_class_contents
[i
]);
IOR_HARD_REG_SET (c
, reg_class_contents
[j
]);
for (k
= 0; k
< N_REG_CLASSES
; k
++)
GO_IF_HARD_REG_SUBSET (reg_class_contents
[k
], c
,
reg_class_subunion
[i
][j
] = (enum reg_class
) k
;
/* Initialize the tables of subclasses and superclasses of each reg class.
First clear the whole table, then add the elements as they are found. */
for (i
= 0; i
< N_REG_CLASSES
; i
++)
for (j
= 0; j
< N_REG_CLASSES
; j
++)
reg_class_superclasses
[i
][j
] = LIM_REG_CLASSES
;
reg_class_subclasses
[i
][j
] = LIM_REG_CLASSES
;
for (i
= 0; i
< N_REG_CLASSES
; i
++)
for (j
= i
+ 1; j
< N_REG_CLASSES
; j
++)
GO_IF_HARD_REG_SUBSET (reg_class_contents
[i
], reg_class_contents
[j
],
/* Reg class I is a subclass of J.
Add J to the table of superclasses of I. */
p
= ®_class_superclasses
[i
][0];
while (*p
!= LIM_REG_CLASSES
) p
++;
/* Add I to the table of superclasses of J. */
p
= ®_class_subclasses
[j
][0];
while (*p
!= LIM_REG_CLASSES
) p
++;
/* After switches have been processed, which perhaps alter
`fixed_regs' and `call_used_regs', convert them to HARD_REG_SETs. */
/* This macro allows the fixed or call-used registers
to depend on target flags. */
#ifdef CONDITIONAL_REGISTER_USAGE
CONDITIONAL_REGISTER_USAGE
;
for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
if (call_used_regs
[i
] && ! fixed_regs
[i
])
warning ("call-clobbered register used for global register variable");
/* Prevent saving/restoring of this reg. */
/* Initialize "constant" tables. */
CLEAR_HARD_REG_SET (fixed_reg_set
);
CLEAR_HARD_REG_SET (call_used_reg_set
);
CLEAR_HARD_REG_SET (call_fixed_reg_set
);
bcopy (fixed_regs
, call_fixed_regs
, sizeof call_fixed_regs
);
#ifdef STRUCT_VALUE_REGNUM
call_fixed_regs
[STRUCT_VALUE_REGNUM
] = 1;
#ifdef STATIC_CHAIN_REGNUM
call_fixed_regs
[STATIC_CHAIN_REGNUM
] = 1;
for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
if (FUNCTION_VALUE_REGNO_P (i
))
SET_HARD_REG_BIT (fixed_reg_set
, i
);
SET_HARD_REG_BIT (call_used_reg_set
, i
);
SET_HARD_REG_BIT (call_fixed_reg_set
, i
);
/* Specify the usage characteristics of the register named NAME.
It should be a fixed register if FIXED and a
call-used register if CALL_USED. */
fix_register (name
, fixed
, call_used
)
/* Decode the name and update the primary form of
for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
if (!strcmp (reg_names
[i
], name
))
call_used_regs
[i
] = call_used
;
if (i
== FIRST_PSEUDO_REGISTER
)
warning ("unknown register name: %s", name
);
/* Now the data and code for the `regclass' pass, which happens
just before local-alloc. */
/* savings[R].savings[CL] is twice the amount saved by putting register R
in class CL. This data is used within `regclass' and freed
short savings
[N_REG_CLASSES
];
static struct savings
*savings
;
/* (enum reg_class) prefclass[R] is the preferred class for pseudo number R.
This is available after `regclass' is run. */
/* preferred_or_nothing[R] is nonzero if we should put pseudo number R
in memory if we can't get its perferred class.
This is available after `regclass' is run. */
static char *preferred_or_nothing
;
void reg_class_record ();
void record_address_regs ();
/* Return the reg_class in which pseudo reg number REGNO is best allocated.
This function is sometimes called before the info has been computed.
When that happens, just return GENERAL_REGS, which is innocuous. */
reg_preferred_class (regno
)
return (enum reg_class
) prefclass
[regno
];
reg_preferred_or_nothing (regno
)
return preferred_or_nothing
[regno
];
/* This prevents dump_flow_info from losing if called
before regclass is run. */
/* This is a pass of the compiler that scans all instructions
and calculates the preferred class for each pseudo-register.
This information can be accessed later by calling `reg_preferred_class'.
This pass comes just before local register allocation. */
#ifdef REGISTER_CONSTRAINTS
/* Zero out our accumulation of the cost of each class for each reg. */
savings
= (struct savings
*) alloca (nregs
* sizeof (struct savings
));
bzero (savings
, nregs
* sizeof (struct savings
));
/* Scan the instructions and record each time it would
save code to put a certain register in a certain class. */
for (insn
= f
; insn
; insn
= NEXT_INSN (insn
))
if ((GET_CODE (insn
) == INSN
&& GET_CODE (PATTERN (insn
)) != USE
&& GET_CODE (PATTERN (insn
)) != CLOBBER
&& GET_CODE (PATTERN (insn
)) != ASM_INPUT
)
|| (GET_CODE (insn
) == JUMP_INSN
&& GET_CODE (PATTERN (insn
)) != ADDR_VEC
&& GET_CODE (PATTERN (insn
)) != ADDR_DIFF_VEC
)
|| GET_CODE (insn
) == CALL_INSN
)
if (GET_CODE (insn
) == INSN
&& asm_noperands (PATTERN (insn
)) >= 0)
int noperands
= asm_noperands (PATTERN (insn
));
/* We don't use alloca because alloca would not free
any of the space until this function returns. */
rtx
*operands
= (rtx
*) oballoc (noperands
* sizeof (rtx
));
= (char **) oballoc (noperands
* sizeof (char *));
decode_asm_operands (PATTERN (insn
), operands
, 0, constraints
, 0);
for (i
= noperands
- 1; i
>= 0; i
--)
reg_class_record (operands
[i
], i
, constraints
);
int insn_code_number
= recog_memoized (insn
);
for (i
= insn_n_operands
[insn_code_number
] - 1; i
>= 0; i
--)
reg_class_record (recog_operand
[i
], i
,
insn_operand_constraint
[insn_code_number
]);
/* Improve handling of two-address insns such as
(set X (ashift CONST Y)) where CONST must be made to match X.
Change it into two insns: (set X CONST) (set X (ashift X Y)).
If we left this for reloading, it would probably get three insns
because X and Y might go in the same place.
This prevents X and Y from receiving the same hard reg. */
&& insn_n_operands
[insn_code_number
] >= 3
&& insn_operand_constraint
[insn_code_number
][1][0] == '0'
&& insn_operand_constraint
[insn_code_number
][1][1] == 0
&& CONSTANT_P (recog_operand
[1])
&& ! rtx_equal_p (recog_operand
[0], recog_operand
[1])
&& ! rtx_equal_p (recog_operand
[0], recog_operand
[2])
&& GET_CODE (recog_operand
[0]) == REG
)
rtx previnsn
= prev_real_insn (insn
);
= emit_insn_before (gen_move_insn (recog_operand
[0],
/* If this insn was the start of a basic block,
include the new insn in that block. */
if (previnsn
== 0 || GET_CODE (previnsn
) == JUMP_INSN
)
for (b
= 0; b
< n_basic_blocks
; b
++)
if (insn
== basic_block_head
[b
])
basic_block_head
[b
] = newinsn
;
/* This makes one more setting of new insns's destination. */
reg_n_sets
[REGNO (recog_operand
[0])]++;
*recog_operand_loc
[1] = recog_operand
[0];
for (i
= insn_n_dups
[insn_code_number
] - 1; i
>= 0; i
--)
if (recog_dup_num
[i
] == 1)
*recog_dup_loc
[i
] = recog_operand
[0];
/* Now for each register look at how desirable each class is
and find which class is preferred. Store that in `prefclass[REGNO]'. */
prefclass
= (char *) oballoc (nregs
);
preferred_or_nothing
= (char *) oballoc (nregs
);
for (i
= FIRST_PSEUDO_REGISTER
; i
< nregs
; i
++)
register int best_savings
= 0;
enum reg_class best
= ALL_REGS
;
/* This is an enum reg_class, but we call it an int
to save lots of casts. */
register struct savings
*p
= &savings
[i
];
for (class = (int) ALL_REGS
- 1; class > 0; class--)
if (p
->savings
[class] > best_savings
)
best_savings
= p
->savings
[class];
best
= (enum reg_class
) class;
else if (p
->savings
[class] == best_savings
)
best
= reg_class_subunion
[(int)best
][class];
/* Note that best_savings is twice number of places something
if ((best_savings
- p
->savings
[(int) GENERAL_REGS
]) * 5 < reg_n_refs
[i
])
prefclass
[i
] = (int) GENERAL_REGS
;
prefclass
[i
] = (int) best
;
/* We cast to (int) because (char) hits bugs in some compilers. */
prefclass
[i
] = (int) best
;
/* reg_n_refs + p->memcost measures the cost of putting in memory.
If a GENERAL_REG is no better, don't even try for one.
Since savings and memcost are 2 * number of refs,
this effectively counts each memory operand not needing reloading
as costing 1/2 of a reload insn. */
= ((best_savings
- p
->savings
[(int) GENERAL_REGS
])
>= p
->nrefs
+ p
->memcost
);
#endif /* REGISTER_CONSTRAINTS */
#ifdef REGISTER_CONSTRAINTS
/* Scan an operand OP for register class preferences.
OPNO is the operand number, and CONSTRAINTS is the constraint
Record the preferred register classes from the constraint for OP
if OP is a register. If OP is a memory reference, record suitable
preferences for registers used in the address. */
reg_class_record (op
, opno
, constraints
)
char *constraint
= constraints
[opno
];
register enum reg_class
class = NO_REGS
;
if (GET_CODE (op
) == SUBREG
)
/* Memory reference: scan the address. */
if (GET_CODE (op
) == MEM
)
record_address_regs (XEXP (op
, 0), 2, 0);
if (GET_CODE (op
) != REG
)
/* If the constraint says the operand is supposed to BE an address,
if (constraint
!= 0 && constraint
[0] == 'p')
record_address_regs (op
, 2, 0);
/* Operand is a register: examine the constraint for specified classes. */
for (p
= constraint
; *p
|| next
; p
++)
/* An input-output operand is twice as costly if it loses. */
/* * means ignore following letter
when choosing register preferences. */
= reg_class_subunion
[(int) class][(int) GENERAL_REGS
];
/* If constraint says "match another operand",
use that operand's constraint to choose preferences. */
next
= constraints
[*p
- '0'];
= reg_class_subunion
[(int) class][(int) REG_CLASS_FROM_LETTER (*p
)];
register struct savings
*pp
;
register enum reg_class class1
;
int cost
= 2 * (1 + double_cost
);
pp
= &savings
[REGNO (op
)];
/* Increment the savings for this reg
for each class contained in the one the constraint asks for. */
if (class != NO_REGS
&& class != ALL_REGS
)
pp
->savings
[(int) class] += cost
;
class1
= reg_class_subclasses
[(int)class][i
];
if (class1
== LIM_REG_CLASSES
)
pp
->savings
[(int) class1
] += cost
;
pp
->memcost
+= 1 + 2 * double_cost
;
/* Record the pseudo registers we must reload into hard registers
in a subexpression of a memory address, X.
BCOST is the cost if X is a register and it fails to be in BASE_REG_CLASS.
ICOST is the cost if it fails to be in INDEX_REG_CLASS. */
record_address_regs (x
, bcost
, icost
)
register enum rtx_code code
= GET_CODE (x
);
/* When we have an address that is a sum,
we must determine whether registers are "base" or "index" regs.
If there is a sum of two registers, we must choose one to be
the "base". Luckily, we can use the REGNO_POINTER_FLAG
to make a good choice most of the time. */
register enum rtx_code code0
= GET_CODE (arg0
);
register enum rtx_code code1
= GET_CODE (arg1
);
/* Look inside subregs. */
arg0
= SUBREG_REG (arg0
), code0
= GET_CODE (arg0
);
arg1
= SUBREG_REG (arg1
), code1
= GET_CODE (arg1
);
if (code0
== MULT
|| code1
== MEM
)
else if (code1
== MULT
|| code0
== MEM
)
else if (code0
== CONST_INT
)
else if (code1
== CONST_INT
)
else if (code0
== REG
&& code1
== REG
)
if (REGNO_POINTER_FLAG (REGNO (arg0
)))
else if (REGNO_POINTER_FLAG (REGNO (arg1
)))
&& ! REGNO_POINTER_FLAG (REGNO (arg0
)))
REGNO_POINTER_FLAG (REGNO (arg0
)) = 1;
&& ! REGNO_POINTER_FLAG (REGNO (arg1
)))
REGNO_POINTER_FLAG (REGNO (arg1
)) = 1;
/* ICOST0 determines whether we are treating operand 0
as a base register or as an index register.
SUPPRESS0 nonzero means it isn't a register at all.
ICOST1 and SUPPRESS1 are likewise for operand 1. */
record_address_regs (arg0
, 2 - icost0
, icost0
);
record_address_regs (arg1
, 2 - icost1
, icost1
);
/* Double the importance of a pseudo register that is incremented
or decremented, since it would take two extra insns
if it ends up in the wrong place. */
record_address_regs (XEXP (x
, 0), 2 * bcost
, 2 * icost
);
register struct savings
*pp
;
register enum reg_class
class, class1
;
pp
= &savings
[REGNO (x
)];
/* We have an address (or part of one) that is just one register. */
/* Record BCOST worth of savings for classes contained
if (class != NO_REGS
&& class != ALL_REGS
)
pp
->savings
[(int) class] += bcost
;
class1
= reg_class_subclasses
[(int)class][i
];
if (class1
== LIM_REG_CLASSES
)
pp
->savings
[(int) class1
] += bcost
;
/* Record ICOST worth of savings for classes contained
if (icost
!= 0 && class != NO_REGS
&& class != ALL_REGS
)
pp
->savings
[(int) class] += icost
;
class1
= reg_class_subclasses
[(int)class][i
];
if (class1
== LIM_REG_CLASSES
)
pp
->savings
[(int) class1
] += icost
;
register char *fmt
= GET_RTX_FORMAT (code
);
for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
record_address_regs (XEXP (x
, i
), bcost
, icost
);
#endif /* REGISTER_CONSTRAINTS */
/* This is the `regscan' pass of the compiler, run just before cse
and again just before loop.
It finds the first and last use of each pseudo-register
and records them in the vectors regno_first_uid, regno_last_uid.
REPEAT is nonzero the second time this is called. */
/* Indexed by pseudo register number, gives uid of first insn using the reg
(as of the time reg_scan is called). */
/* Indexed by pseudo register number, gives uid of last insn using the reg
(as of the time reg_scan is called). */
/* Maximum number of parallel sets and clobbers in any insn in this fn.
Always at least 3, since the combiner could put that many togetherm
and we want this to remain correct for all the remaining passes. */
void reg_scan_mark_refs ();
reg_scan (f
, nregs
, repeat
)
regno_first_uid
= (short *) oballoc (nregs
* sizeof (short));
bzero (regno_first_uid
, nregs
* sizeof (short));
regno_last_uid
= (short *) oballoc (nregs
* sizeof (short));
bzero (regno_last_uid
, nregs
* sizeof (short));
for (insn
= f
; insn
; insn
= NEXT_INSN (insn
))
if (GET_CODE (insn
) == INSN
|| GET_CODE (insn
) == CALL_INSN
|| GET_CODE (insn
) == JUMP_INSN
)
if (GET_CODE (PATTERN (insn
)) == PARALLEL
&& XVECLEN (PATTERN (insn
), 0) > max_parallel
)
max_parallel
= XVECLEN (PATTERN (insn
), 0);
reg_scan_mark_refs (PATTERN (insn
), INSN_UID (insn
));
reg_scan_mark_refs (x
, uid
)
register enum rtx_code code
= GET_CODE (x
);
register int regno
= REGNO (x
);
regno_last_uid
[regno
] = uid
;
if (regno_first_uid
[regno
] == 0)
regno_first_uid
[regno
] = uid
;
register char *fmt
= GET_RTX_FORMAT (code
);
for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
reg_scan_mark_refs (XEXP (x
, i
), uid
);
else if (fmt
[i
] == 'E' && XVEC (x
, i
) != 0)
for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
reg_scan_mark_refs (XVECEXP (x
, i
, j
), uid
);