gcc/lra-int.h

   1 /* Local Register Allocator (LRA) intercommunication header file.
   2    Copyright (C) 2010-2015 Free Software Foundation, Inc.
   3    Contributed by Vladimir Makarov <vmakarov@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #ifndef GCC_LRA_INT_H
  22 #define GCC_LRA_INT_H
  23
  24 #include "lra.h"
  25 #include "bitmap.h"
  26 #include "recog.h"
  27 #include "insn-attr.h"
  28 #include "insn-codes.h"
  29 #include "insn-config.h"
  30 #include "regs.h"
  31
  32 #define lra_assert(c) gcc_checking_assert (c)
  33
  34 /* The parameter used to prevent infinite reloading for an insn.  Each
  35    insn operands might require a reload and, if it is a memory, its
  36    base and index registers might require a reload too.  */
  37 #define LRA_MAX_INSN_RELOADS (MAX_RECOG_OPERANDS * 3)
  38
  39 typedef struct lra_live_range *lra_live_range_t;
  40
  41 /* The structure describes program points where a given pseudo lives.
  42    The live ranges can be used to find conflicts with other pseudos.
  43    If the live ranges of two pseudos are intersected, the pseudos are
  44    in conflict.  */
  45 struct lra_live_range
  46 {
  47   /* Pseudo regno whose live range is described by given
  48      structure.  */
  49   int regno;
  50   /* Program point range.  */
  51   int start, finish;
  52   /* Next structure describing program points where the pseudo
  53      lives.  */
  54   lra_live_range_t next;
  55   /* Pointer to structures with the same start.  */
  56   lra_live_range_t start_next;
  57
  58   /* Pool allocation new operator.  */
  59   inline void *operator new (size_t)
  60   {
  61     return pool.allocate ();
  62   }
  63
  64   /* Delete operator utilizing pool allocation.  */
  65   inline void operator delete (void *ptr)
  66   {
  67     pool.remove ((lra_live_range *) ptr);
  68   }
  69
  70   /* Memory allocation pool.  */
  71   static pool_allocator<lra_live_range> pool;
  72 };
  73
  74 typedef struct lra_copy *lra_copy_t;
  75
  76 /* Copy between pseudos which affects assigning hard registers.  */
  77 struct lra_copy
  78 {
  79   /* True if regno1 is the destination of the copy.  */
  80   bool regno1_dest_p;
  81   /* Execution frequency of the copy.  */
  82   int freq;
  83   /* Pseudos connected by the copy.  REGNO1 < REGNO2.  */
  84   int regno1, regno2;
  85   /* Next copy with correspondingly REGNO1 and REGNO2.  */
  86   lra_copy_t regno1_next, regno2_next;
  87 };
  88
  89 /* Common info about a register (pseudo or hard register).  */
  90 struct lra_reg
  91 {
  92   /* Bitmap of UIDs of insns (including debug insns) referring the
  93      reg.  */
  94   bitmap_head insn_bitmap;
  95   /* The following fields are defined only for pseudos.  */
  96   /* Hard registers with which the pseudo conflicts.  */
  97   HARD_REG_SET conflict_hard_regs;
  98   /* Call used registers with which the pseudo conflicts, taking into account
  99      the registers used by functions called from calls which cross the
 100      pseudo.  */
 101   HARD_REG_SET actual_call_used_reg_set;
 102   /* We assign hard registers to reload pseudos which can occur in few
 103      places.  So two hard register preferences are enough for them.
 104      The following fields define the preferred hard registers.  If
 105      there are no such hard registers the first field value is
 106      negative.  If there is only one preferred hard register, the 2nd
 107      field is negative.  */
 108   int preferred_hard_regno1, preferred_hard_regno2;
 109   /* Profits to use the corresponding preferred hard registers.  If
 110      the both hard registers defined, the first hard register has not
 111      less profit than the second one.  */
 112   int preferred_hard_regno_profit1, preferred_hard_regno_profit2;
 113 #ifdef STACK_REGS
 114   /* True if the pseudo should not be assigned to a stack register.  */
 115   bool no_stack_p;
 116 #endif
 117 #ifdef ENABLE_CHECKING
 118   /* True if the pseudo crosses a call.  It is setup in lra-lives.c
 119      and used to check that the pseudo crossing a call did not get a
 120      call used hard register.  */
 121   bool call_p;
 122 #endif
 123   /* Number of references and execution frequencies of the register in
 124      *non-debug* insns.  */
 125   int nrefs, freq;
 126   int last_reload;
 127   /* Regno used to undo the inheritance.  It can be non-zero only
 128      between couple of inheritance and undo inheritance passes.  */
 129   int restore_regno;
 130   /* Value holding by register.  If the pseudos have the same value
 131      they do not conflict.  */
 132   int val;
 133   /* Offset from relative eliminate register to pesudo reg.  */
 134   int offset;
 135   /* These members are set up in lra-lives.c and updated in
 136      lra-coalesce.c.  */
 137   /* The biggest size mode in which each pseudo reg is referred in
 138      whole function (possibly via subreg).  */
 139   machine_mode biggest_mode;
 140   /* Live ranges of the pseudo.  */
 141   lra_live_range_t live_ranges;
 142   /* This member is set up in lra-lives.c for subsequent
 143      assignments.  */
 144   lra_copy_t copies;
 145 };
 146
 147 /* References to the common info about each register.  */
 148 extern struct lra_reg *lra_reg_info;
 149
 150 /* Static info about each insn operand (common for all insns with the
 151    same ICODE).  Warning: if the structure definition is changed, the
 152    initializer for debug_operand_data in lra.c should be changed
 153    too.  */
 154 struct lra_operand_data
 155 {
 156   /* The machine description constraint string of the operand.  */
 157   const char *constraint;
 158   /* It is taken only from machine description (which is different
 159      from recog_data.operand_mode) and can be of VOIDmode.  */
 160   ENUM_BITFIELD(machine_mode) mode : 16;
 161   /* The type of the operand (in/out/inout).  */
 162   ENUM_BITFIELD (op_type) type : 8;
 163   /* Through if accessed through STRICT_LOW.  */
 164   unsigned int strict_low : 1;
 165   /* True if the operand is an operator.  */
 166   unsigned int is_operator : 1;
 167   /* True if there is an early clobber alternative for this operand.
 168      This field is set up every time when corresponding
 169      operand_alternative in lra_static_insn_data is set up.  */
 170   unsigned int early_clobber : 1;
 171   /* True if the operand is an address.  */
 172   unsigned int is_address : 1;
 173 };
 174
 175 /* Info about register occurrence in an insn.  */
 176 struct lra_insn_reg
 177 {
 178   /* The biggest mode through which the insn refers to the register
 179      occurrence (remember the register can be accessed through a
 180      subreg in the insn).  */
 181   ENUM_BITFIELD(machine_mode) biggest_mode : 16;
 182   /* The type of the corresponding operand which is the register.  */
 183   ENUM_BITFIELD (op_type) type : 8;
 184   /* True if the reg is accessed through a subreg and the subreg is
 185      just a part of the register.  */
 186   unsigned int subreg_p : 1;
 187   /* True if there is an early clobber alternative for this
 188      operand.  */
 189   unsigned int early_clobber : 1;
 190   /* The corresponding regno of the register.  */
 191   int regno;
 192   /* Next reg info of the same insn.  */
 193   struct lra_insn_reg *next;
 194 };
 195
 196 /* Static part (common info for insns with the same ICODE) of LRA
 197    internal insn info. It exists in at most one exemplar for each
 198    non-negative ICODE. There is only one exception. Each asm insn has
 199    own structure.  Warning: if the structure definition is changed,
 200    the initializer for debug_insn_static_data in lra.c should be
 201    changed too.  */
 202 struct lra_static_insn_data
 203 {
 204   /* Static info about each insn operand.  */
 205   struct lra_operand_data *operand;
 206   /* Each duplication refers to the number of the corresponding
 207      operand which is duplicated.  */
 208   int *dup_num;
 209   /* The number of an operand marked as commutative, -1 otherwise.  */
 210   int commutative;
 211   /* Number of operands, duplications, and alternatives of the
 212      insn.  */
 213   char n_operands;
 214   char n_dups;
 215   char n_alternatives;
 216   /* Insns in machine description (or clobbers in asm) may contain
 217      explicit hard regs which are not operands.  The following list
 218      describes such hard registers.  */
 219   struct lra_insn_reg *hard_regs;
 220   /* Array [n_alternatives][n_operand] of static constraint info for
 221      given operand in given alternative.  This info can be changed if
 222      the target reg info is changed.  */
 223   const struct operand_alternative *operand_alternative;
 224 };
 225
 226 /* LRA internal info about an insn (LRA internal insn
 227    representation).  */
 228 struct lra_insn_recog_data
 229 {
 230   /* The insn code.  */
 231   int icode;
 232   /* The alternative should be used for the insn, -1 if invalid, or we
 233      should try to use any alternative, or the insn is a debug
 234      insn.  */
 235   int used_insn_alternative;
 236   /* SP offset before the insn relative to one at the func start.  */
 237   HOST_WIDE_INT sp_offset;
 238   /* The insn itself.  */
 239   rtx_insn *insn;
 240   /* Common data for insns with the same ICODE.  Asm insns (their
 241      ICODE is negative) do not share such structures.  */
 242   struct lra_static_insn_data *insn_static_data;
 243   /* Two arrays of size correspondingly equal to the operand and the
 244      duplication numbers: */
 245   rtx **operand_loc; /* The operand locations, NULL if no operands.  */
 246   rtx **dup_loc; /* The dup locations, NULL if no dups.  */
 247   /* Number of hard registers implicitly used in given call insn.  The
 248      value can be NULL or points to array of the hard register numbers
 249      ending with a negative value.  */
 250   int *arg_hard_regs;
 251   /* Cached value of get_preferred_alternatives.  */
 252   alternative_mask preferred_alternatives;
 253   /* The following member value is always NULL for a debug insn.  */
 254   struct lra_insn_reg *regs;
 255 };
 256
 257 typedef struct lra_insn_recog_data *lra_insn_recog_data_t;
 258
 259 /* Whether the clobber is used temporary in LRA.  */
 260 #define LRA_TEMP_CLOBBER_P(x) \
 261   (RTL_FLAG_CHECK1 ("TEMP_CLOBBER_P", (x), CLOBBER)->unchanging)
 262
 263 /* Cost factor for each additional reload and maximal cost reject for
 264    insn reloads.  One might ask about such strange numbers.  Their
 265    values occurred historically from former reload pass.  */
 266 #define LRA_LOSER_COST_FACTOR 6
 267 #define LRA_MAX_REJECT 600
 268
 269 /* Maximum allowed number of assignment pass iterations after the
 270    latest spill pass when any former reload pseudo was spilled.  It is
 271    for preventing LRA cycling in a bug case.  */
 272 #define LRA_MAX_ASSIGNMENT_ITERATION_NUMBER 30
 273
 274 /* The maximal number of inheritance/split passes in LRA.  It should
 275    be more 1 in order to perform caller saves transformations and much
 276    less MAX_CONSTRAINT_ITERATION_NUMBER to prevent LRA to do as many
 277    as permitted constraint passes in some complicated cases.  The
 278    first inheritance/split pass has a biggest impact on generated code
 279    quality.  Each subsequent affects generated code in less degree.
 280    For example, the 3rd pass does not change generated SPEC2000 code
 281    at all on x86-64.  */
 282 #define LRA_MAX_INHERITANCE_PASSES 2
 283
 284 #if LRA_MAX_INHERITANCE_PASSES <= 0 \
 285     || LRA_MAX_INHERITANCE_PASSES >= LRA_MAX_ASSIGNMENT_ITERATION_NUMBER - 8
 286 #error wrong LRA_MAX_INHERITANCE_PASSES value
 287 #endif
 288
 289 /* Analogous macro to the above one but for rematerialization.  */
 290 #define LRA_MAX_REMATERIALIZATION_PASSES 2
 291
 292 #if LRA_MAX_REMATERIALIZATION_PASSES <= 0 \
 293     || LRA_MAX_REMATERIALIZATION_PASSES >= LRA_MAX_ASSIGNMENT_ITERATION_NUMBER - 8
 294 #error wrong LRA_MAX_REMATERIALIZATION_PASSES value
 295 #endif
 296
 297 /* lra.c: */
 298
 299 extern FILE *lra_dump_file;
 300
 301 extern bool lra_reg_spill_p;
 302
 303 extern HARD_REG_SET lra_no_alloc_regs;
 304
 305 extern int lra_insn_recog_data_len;
 306 extern lra_insn_recog_data_t *lra_insn_recog_data;
 307
 308 extern int lra_curr_reload_num;
 309
 310 extern void lra_dump_bitmap_with_title (const char *, bitmap, int);
 311 extern void lra_push_insn (rtx_insn *);
 312 extern void lra_push_insn_by_uid (unsigned int);
 313 extern void lra_push_insn_and_update_insn_regno_info (rtx_insn *);
 314 extern rtx_insn *lra_pop_insn (void);
 315 extern unsigned int lra_insn_stack_length (void);
 316
 317 extern rtx lra_create_new_reg_with_unique_value (machine_mode, rtx,
 318                                                  enum reg_class, const char *);
 319 extern void lra_set_regno_unique_value (int);
 320 extern void lra_invalidate_insn_data (rtx_insn *);
 321 extern void lra_set_insn_deleted (rtx_insn *);
 322 extern void lra_delete_dead_insn (rtx_insn *);
 323 extern void lra_emit_add (rtx, rtx, rtx);
 324 extern void lra_emit_move (rtx, rtx);
 325 extern void lra_update_dups (lra_insn_recog_data_t, signed char *);
 326
 327 extern void lra_process_new_insns (rtx_insn *, rtx_insn *, rtx_insn *,
 328                                    const char *);
 329
 330 extern bool lra_substitute_pseudo (rtx *, int, rtx);
 331 extern bool lra_substitute_pseudo_within_insn (rtx_insn *, int, rtx);
 332
 333 extern lra_insn_recog_data_t lra_set_insn_recog_data (rtx_insn *);
 334 extern lra_insn_recog_data_t lra_update_insn_recog_data (rtx_insn *);
 335 extern void lra_set_used_insn_alternative (rtx_insn *, int);
 336 extern void lra_set_used_insn_alternative_by_uid (int, int);
 337
 338 extern void lra_invalidate_insn_regno_info (rtx_insn *);
 339 extern void lra_update_insn_regno_info (rtx_insn *);
 340 extern struct lra_insn_reg *lra_get_insn_regs (int);
 341
 342 extern void lra_free_copies (void);
 343 extern void lra_create_copy (int, int, int);
 344 extern lra_copy_t lra_get_copy (int);
 345 extern bool lra_former_scratch_p (int);
 346 extern bool lra_former_scratch_operand_p (rtx_insn *, int);
 347 extern void lra_register_new_scratch_op (rtx_insn *, int);
 348
 349 extern int lra_new_regno_start;
 350 extern int lra_constraint_new_regno_start;
 351 extern int lra_bad_spill_regno_start;
 352 extern bitmap_head lra_inheritance_pseudos;
 353 extern bitmap_head lra_split_regs;
 354 extern bitmap_head lra_subreg_reload_pseudos;
 355 extern bitmap_head lra_optional_reload_pseudos;
 356
 357 /* lra-constraints.c: */
 358
 359 extern void lra_init_equiv (void);
 360 extern int lra_constraint_offset (int, machine_mode);
 361
 362 extern int lra_constraint_iter;
 363 extern bool lra_risky_transformations_p;
 364 extern int lra_inheritance_iter;
 365 extern int lra_undo_inheritance_iter;
 366 extern bool lra_constrain_insn (rtx_insn *);
 367 extern bool lra_constraints (bool);
 368 extern void lra_constraints_init (void);
 369 extern void lra_constraints_finish (void);
 370 extern void lra_inheritance (void);
 371 extern bool lra_undo_inheritance (void);
 372
 373 /* lra-lives.c: */
 374
 375 extern int lra_live_max_point;
 376 extern int *lra_point_freq;
 377
 378 extern int lra_hard_reg_usage[FIRST_PSEUDO_REGISTER];
 379
 380 extern int lra_live_range_iter;
 381 extern void lra_create_live_ranges (bool, bool);
 382 extern lra_live_range_t lra_copy_live_range_list (lra_live_range_t);
 383 extern lra_live_range_t lra_merge_live_ranges (lra_live_range_t,
 384                                                lra_live_range_t);
 385 extern bool lra_intersected_live_ranges_p (lra_live_range_t,
 386                                            lra_live_range_t);
 387 extern void lra_print_live_range_list (FILE *, lra_live_range_t);
 388 extern void debug (lra_live_range &ref);
 389 extern void debug (lra_live_range *ptr);
 390 extern void lra_debug_live_range_list (lra_live_range_t);
 391 extern void lra_debug_pseudo_live_ranges (int);
 392 extern void lra_debug_live_ranges (void);
 393 extern void lra_clear_live_ranges (void);
 394 extern void lra_live_ranges_init (void);
 395 extern void lra_live_ranges_finish (void);
 396 extern void lra_setup_reload_pseudo_preferenced_hard_reg (int, int, int);
 397
 398 /* lra-assigns.c: */
 399
 400 extern int lra_assignment_iter;
 401 extern int lra_assignment_iter_after_spill;
 402 extern void lra_setup_reg_renumber (int, int, bool);
 403 extern bool lra_assign (void);
 404
 405
 406 /* lra-coalesce.c: */
 407
 408 extern int lra_coalesce_iter;
 409 extern bool lra_coalesce (void);
 410
 411 /* lra-spills.c:  */
 412
 413 extern bool lra_need_for_spills_p (void);
 414 extern void lra_spill (void);
 415 extern void lra_final_code_change (void);
 416
 417 /* lra-remat.c:  */
 418
 419 extern int lra_rematerialization_iter;
 420 extern bool lra_remat (void);
 421
 422 /* lra-elimination.c: */
 423
 424 extern void lra_debug_elim_table (void);
 425 extern int lra_get_elimination_hard_regno (int);
 426 extern rtx lra_eliminate_regs_1 (rtx_insn *, rtx, machine_mode,
 427                                  bool, bool, HOST_WIDE_INT, bool);
 428 extern void eliminate_regs_in_insn (rtx_insn *insn, bool, bool, HOST_WIDE_INT);
 429 extern void lra_eliminate (bool, bool);
 430
 431 extern void lra_eliminate_reg_if_possible (rtx *);
 432
 433 \f
 434
 435 /* Return the hard register which given pseudo REGNO assigned to.
 436    Negative value means that the register got memory or we don't know
 437    allocation yet.  */
 438 static inline int
 439 lra_get_regno_hard_regno (int regno)
 440 {
 441   resize_reg_info ();
 442   return reg_renumber[regno];
 443 }
 444
 445 /* Change class of pseudo REGNO to NEW_CLASS.  Print info about it
 446    using TITLE.  Output a new line if NL_P.  */
 447 static void inline
 448 lra_change_class (int regno, enum reg_class new_class,
 449                   const char *title, bool nl_p)
 450 {
 451   lra_assert (regno >= FIRST_PSEUDO_REGISTER);
 452   if (lra_dump_file != NULL)
 453     fprintf (lra_dump_file, "%s class %s for r%d",
 454              title, reg_class_names[new_class], regno);
 455   setup_reg_classes (regno, new_class, NO_REGS, new_class);
 456   if (lra_dump_file != NULL && nl_p)
 457     fprintf (lra_dump_file, "\n");
 458 }
 459
 460 /* Update insn operands which are duplication of NOP operand.  The
 461    insn is represented by its LRA internal representation ID.  */
 462 static inline void
 463 lra_update_dup (lra_insn_recog_data_t id, int nop)
 464 {
 465   int i;
 466   struct lra_static_insn_data *static_id = id->insn_static_data;
 467
 468   for (i = 0; i < static_id->n_dups; i++)
 469     if (static_id->dup_num[i] == nop)
 470       *id->dup_loc[i] = *id->operand_loc[nop];
 471 }
 472
 473 /* Process operator duplications in insn with ID.  We do it after the
 474    operands processing.  Generally speaking, we could do this probably
 475    simultaneously with operands processing because a common practice
 476    is to enumerate the operators after their operands.  */
 477 static inline void
 478 lra_update_operator_dups (lra_insn_recog_data_t id)
 479 {
 480   int i;
 481   struct lra_static_insn_data *static_id = id->insn_static_data;
 482
 483   for (i = 0; i < static_id->n_dups; i++)
 484     {
 485       int ndup = static_id->dup_num[i];
 486
 487       if (static_id->operand[ndup].is_operator)
 488         *id->dup_loc[i] = *id->operand_loc[ndup];
 489     }
 490 }
 491
 492 /* Return info about INSN.  Set up the info if it is not done yet.  */
 493 static inline lra_insn_recog_data_t
 494 lra_get_insn_recog_data (rtx_insn *insn)
 495 {
 496   lra_insn_recog_data_t data;
 497   unsigned int uid = INSN_UID (insn);
 498
 499   if (lra_insn_recog_data_len > (int) uid
 500       && (data = lra_insn_recog_data[uid]) != NULL)
 501     {
 502       /* Check that we did not change insn without updating the insn
 503          info.  */
 504       lra_assert (data->insn == insn
 505                   && (INSN_CODE (insn) < 0
 506                       || data->icode == INSN_CODE (insn)));
 507       return data;
 508     }
 509   return lra_set_insn_recog_data (insn);
 510 }
 511
 512 /* Update offset from pseudos with VAL by INCR.  */
 513 static inline void
 514 lra_update_reg_val_offset (int val, int incr)
 515 {
 516   int i;
 517
 518   for (i = FIRST_PSEUDO_REGISTER; i < max_reg_num (); i++)
 519     {
 520       if (lra_reg_info[i].val == val)
 521         lra_reg_info[i].offset += incr;
 522     }
 523 }
 524
 525 /* Return true if register content is equal to VAL with OFFSET.  */
 526 static inline bool
 527 lra_reg_val_equal_p (int regno, int val, int offset)
 528 {
 529   if (lra_reg_info[regno].val == val
 530       && lra_reg_info[regno].offset == offset)
 531     return true;
 532
 533   return false;
 534 }
 535
 536 /* Assign value of register FROM to TO.  */
 537 static inline void
 538 lra_assign_reg_val (int from, int to)
 539 {
 540   lra_reg_info[to].val = lra_reg_info[from].val;
 541   lra_reg_info[to].offset = lra_reg_info[from].offset;
 542 }
 543
 544 #endif /* GCC_LRA_INT_H */