LCOV - code coverage report
Current view: top level - gcc - sel-sched-ir.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 217 226 96.0 %
Date: 2020-03-28 11:57:23 Functions: 10 10 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Instruction scheduling pass.  This file contains definitions used
       2                 :            :    internally in the scheduler.
       3                 :            :    Copyright (C) 2006-2020 Free Software Foundation, Inc.
       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_SEL_SCHED_IR_H
      22                 :            : #define GCC_SEL_SCHED_IR_H
      23                 :            : 
      24                 :            : /* For state_t.  */
      25                 :            : /* For reg_note.  */
      26                 :            : 
      27                 :            : /* tc_t is a short for target context.  This is a state of the target
      28                 :            :    backend.  */
      29                 :            : typedef void *tc_t;
      30                 :            : 
      31                 :            : /* List data types used for av sets, fences, paths, and boundaries.  */
      32                 :            : 
      33                 :            : /* Forward declarations for types that are part of some list nodes.  */
      34                 :            : struct _list_node;
      35                 :            : 
      36                 :            : /* List backend.  */
      37                 :            : typedef struct _list_node *_list_t;
      38                 :            : #define _LIST_NEXT(L) ((L)->next)
      39                 :            : 
      40                 :            : /* Instruction data that is part of vinsn type.  */
      41                 :            : struct idata_def;
      42                 :            : typedef struct idata_def *idata_t;
      43                 :            : 
      44                 :            : /* A virtual instruction, i.e. an instruction as seen by the scheduler.  */
      45                 :            : struct vinsn_def;
      46                 :            : typedef struct vinsn_def *vinsn_t;
      47                 :            : 
      48                 :            : /* RTX list.
      49                 :            :    This type is the backend for ilist.  */
      50                 :            : typedef _list_t _xlist_t;
      51                 :            : #define _XLIST_X(L) ((L)->u.x)
      52                 :            : #define _XLIST_NEXT(L) (_LIST_NEXT (L))
      53                 :            : 
      54                 :            : /* Instruction.  */
      55                 :            : typedef rtx_insn *insn_t;
      56                 :            : 
      57                 :            : /* List of insns.  */
      58                 :            : typedef _list_t ilist_t;
      59                 :            : #define ILIST_INSN(L) ((L)->u.insn)
      60                 :            : #define ILIST_NEXT(L) (_LIST_NEXT (L))
      61                 :            : 
      62                 :            : /* This lists possible transformations that done locally, i.e. in
      63                 :            :    moveup_expr.  */
      64                 :            : enum local_trans_type
      65                 :            :   {
      66                 :            :     TRANS_SUBSTITUTION,
      67                 :            :     TRANS_SPECULATION
      68                 :            :   };
      69                 :            : 
      70                 :            : /* This struct is used to record the history of expression's
      71                 :            :    transformations.  */
      72                 :            : struct expr_history_def_1
      73                 :            : {
      74                 :            :   /* UID of the insn.  */
      75                 :            :   unsigned uid;
      76                 :            : 
      77                 :            :   /* How the expression looked like.  */
      78                 :            :   vinsn_t old_expr_vinsn;
      79                 :            : 
      80                 :            :   /* How the expression looks after the transformation.  */
      81                 :            :   vinsn_t new_expr_vinsn;
      82                 :            : 
      83                 :            :   /* And its speculative status.  */
      84                 :            :   ds_t spec_ds;
      85                 :            : 
      86                 :            :   /* Type of the transformation.  */
      87                 :            :   enum local_trans_type type;
      88                 :            : };
      89                 :            : 
      90                 :            : typedef struct expr_history_def_1 expr_history_def;
      91                 :            : 
      92                 :            : 
      93                 :            : /* Expression information.  */
      94                 :            : struct _expr
      95                 :            : {
      96                 :            :   /* Insn description.  */
      97                 :            :   vinsn_t vinsn;
      98                 :            : 
      99                 :            :   /* SPEC is the degree of speculativeness.
     100                 :            :      FIXME: now spec is increased when an rhs is moved through a
     101                 :            :      conditional, thus showing only control speculativeness.  In the
     102                 :            :      future we'd like to count data spec separately to allow a better
     103                 :            :      control on scheduling.  */
     104                 :            :   int spec;
     105                 :            : 
     106                 :            :   /* Degree of speculativeness measured as probability of executing
     107                 :            :      instruction's original basic block given relative to
     108                 :            :      the current scheduling point.  */
     109                 :            :   int usefulness;
     110                 :            : 
     111                 :            :   /* A priority of this expression.  */
     112                 :            :   int priority;
     113                 :            : 
     114                 :            :   /* A priority adjustment of this expression.  */
     115                 :            :   int priority_adj;
     116                 :            : 
     117                 :            :   /* Number of times the insn was scheduled.  */
     118                 :            :   int sched_times;
     119                 :            : 
     120                 :            :   /* A basic block index this was originated from.  Zero when there is
     121                 :            :      more than one originator.  */
     122                 :            :   int orig_bb_index;
     123                 :            : 
     124                 :            :   /* Instruction should be of SPEC_DONE_DS type in order to be moved to this
     125                 :            :      point.  */
     126                 :            :   ds_t spec_done_ds;
     127                 :            : 
     128                 :            :   /* SPEC_TO_CHECK_DS hold speculation types that should be checked
     129                 :            :      (used only during move_op ()).  */
     130                 :            :   ds_t spec_to_check_ds;
     131                 :            : 
     132                 :            :   /* Cycle on which original insn was scheduled.  Zero when it has not yet
     133                 :            :      been scheduled or more than one originator.  */
     134                 :            :   int orig_sched_cycle;
     135                 :            : 
     136                 :            :   /* This vector contains the history of insn's transformations.  */
     137                 :            :   vec<expr_history_def> history_of_changes;
     138                 :            : 
     139                 :            :   /* True (1) when original target (register or memory) of this instruction
     140                 :            :      is available for scheduling, false otherwise.  -1 means we're not sure;
     141                 :            :      please run find_used_regs to clarify.  */
     142                 :            :   signed char target_available;
     143                 :            : 
     144                 :            :   /* True when this expression needs a speculation check to be scheduled.
     145                 :            :      This is used during find_used_regs.  */
     146                 :            :   BOOL_BITFIELD needs_spec_check_p : 1;
     147                 :            : 
     148                 :            :   /* True when the expression was substituted.  Used for statistical
     149                 :            :      purposes.  */
     150                 :            :   BOOL_BITFIELD was_substituted : 1;
     151                 :            : 
     152                 :            :   /* True when the expression was renamed.  */
     153                 :            :   BOOL_BITFIELD was_renamed : 1;
     154                 :            : 
     155                 :            :   /* True when expression can't be moved.  */
     156                 :            :   BOOL_BITFIELD cant_move : 1;
     157                 :            : };
     158                 :            : 
     159                 :            : typedef struct _expr expr_def;
     160                 :            : typedef expr_def *expr_t;
     161                 :            : 
     162                 :            : #define EXPR_VINSN(EXPR) ((EXPR)->vinsn)
     163                 :            : #define EXPR_INSN_RTX(EXPR) (VINSN_INSN_RTX (EXPR_VINSN (EXPR)))
     164                 :            : #define EXPR_PATTERN(EXPR) (VINSN_PATTERN (EXPR_VINSN (EXPR)))
     165                 :            : #define EXPR_LHS(EXPR) (VINSN_LHS (EXPR_VINSN (EXPR)))
     166                 :            : #define EXPR_RHS(EXPR) (VINSN_RHS (EXPR_VINSN (EXPR)))
     167                 :            : #define EXPR_TYPE(EXPR) (VINSN_TYPE (EXPR_VINSN (EXPR)))
     168                 :            : #define EXPR_SEPARABLE_P(EXPR) (VINSN_SEPARABLE_P (EXPR_VINSN (EXPR)))
     169                 :            : 
     170                 :            : #define EXPR_SPEC(EXPR) ((EXPR)->spec)
     171                 :            : #define EXPR_USEFULNESS(EXPR) ((EXPR)->usefulness)
     172                 :            : #define EXPR_PRIORITY(EXPR) ((EXPR)->priority)
     173                 :            : #define EXPR_PRIORITY_ADJ(EXPR) ((EXPR)->priority_adj)
     174                 :            : #define EXPR_SCHED_TIMES(EXPR) ((EXPR)->sched_times)
     175                 :            : #define EXPR_ORIG_BB_INDEX(EXPR) ((EXPR)->orig_bb_index)
     176                 :            : #define EXPR_ORIG_SCHED_CYCLE(EXPR) ((EXPR)->orig_sched_cycle)
     177                 :            : #define EXPR_SPEC_DONE_DS(EXPR) ((EXPR)->spec_done_ds)
     178                 :            : #define EXPR_SPEC_TO_CHECK_DS(EXPR) ((EXPR)->spec_to_check_ds)
     179                 :            : #define EXPR_HISTORY_OF_CHANGES(EXPR) ((EXPR)->history_of_changes)
     180                 :            : #define EXPR_TARGET_AVAILABLE(EXPR) ((EXPR)->target_available)
     181                 :            : #define EXPR_NEEDS_SPEC_CHECK_P(EXPR) ((EXPR)->needs_spec_check_p)
     182                 :            : #define EXPR_WAS_SUBSTITUTED(EXPR) ((EXPR)->was_substituted)
     183                 :            : #define EXPR_WAS_RENAMED(EXPR) ((EXPR)->was_renamed)
     184                 :            : #define EXPR_CANT_MOVE(EXPR) ((EXPR)->cant_move)
     185                 :            : 
     186                 :            : /* Insn definition for list of original insns in find_used_regs.  */
     187                 :            : struct _def
     188                 :            : {
     189                 :            :   insn_t orig_insn;
     190                 :            : 
     191                 :            :   /* FIXME: Get rid of CROSSED_CALL_ABIS in each def, since if we're moving up
     192                 :            :      rhs from two different places, but only one of the code motion paths
     193                 :            :      crosses a call, we can't use any of the call_used_regs, no matter which
     194                 :            :      path or whether all paths crosses a call.  Thus we should move
     195                 :            :      CROSSED_CALL_ABIS to static params.  */
     196                 :            :   unsigned int crossed_call_abis;
     197                 :            : };
     198                 :            : typedef struct _def *def_t;
     199                 :            : 
     200                 :            : 
     201                 :            : /* Availability sets are sets of expressions we're scheduling.  */
     202                 :            : typedef _list_t av_set_t;
     203                 :            : #define _AV_SET_EXPR(L) (&(L)->u.expr)
     204                 :            : #define _AV_SET_NEXT(L) (_LIST_NEXT (L))
     205                 :            : 
     206                 :            : 
     207                 :            : /* Boundary of the current fence group.  */
     208                 :            : struct _bnd
     209                 :            : {
     210                 :            :   /* The actual boundary instruction.  */
     211                 :            :   insn_t to;
     212                 :            : 
     213                 :            :   /* Its path to the fence.  */
     214                 :            :   ilist_t ptr;
     215                 :            : 
     216                 :            :   /* Availability set at the boundary.  */
     217                 :            :   av_set_t av;
     218                 :            : 
     219                 :            :   /* This set moved to the fence.  */
     220                 :            :   av_set_t av1;
     221                 :            : 
     222                 :            :   /* Deps context at this boundary.  As long as we have one boundary per fence,
     223                 :            :      this is just a pointer to the same deps context as in the corresponding
     224                 :            :      fence.  */
     225                 :            :   deps_t dc;
     226                 :            : };
     227                 :            : typedef struct _bnd *bnd_t;
     228                 :            : #define BND_TO(B) ((B)->to)
     229                 :            : 
     230                 :            : /* PTR stands not for pointer as you might think, but as a Path To Root of the
     231                 :            :    current instruction group from boundary B.  */
     232                 :            : #define BND_PTR(B) ((B)->ptr)
     233                 :            : #define BND_AV(B) ((B)->av)
     234                 :            : #define BND_AV1(B) ((B)->av1)
     235                 :            : #define BND_DC(B) ((B)->dc)
     236                 :            : 
     237                 :            : /* List of boundaries.  */
     238                 :            : typedef _list_t blist_t;
     239                 :            : #define BLIST_BND(L) (&(L)->u.bnd)
     240                 :            : #define BLIST_NEXT(L) (_LIST_NEXT (L))
     241                 :            : 
     242                 :            : 
     243                 :            : /* Fence information.  A fence represents current scheduling point and also
     244                 :            :    blocks code motion through it when pipelining.  */
     245                 :            : struct _fence
     246                 :            : {
     247                 :            :   /* Insn before which we gather an instruction group.*/
     248                 :            :   insn_t insn;
     249                 :            : 
     250                 :            :   /* Modeled state of the processor pipeline.  */
     251                 :            :   state_t state;
     252                 :            : 
     253                 :            :   /* Current cycle that is being scheduled on this fence.  */
     254                 :            :   int cycle;
     255                 :            : 
     256                 :            :   /* Number of insns that were scheduled on the current cycle.
     257                 :            :      This information has to be local to a fence.  */
     258                 :            :   int cycle_issued_insns;
     259                 :            : 
     260                 :            :   /* At the end of fill_insns () this field holds the list of the instructions
     261                 :            :      that are inner boundaries of the scheduled parallel group.  */
     262                 :            :   ilist_t bnds;
     263                 :            : 
     264                 :            :   /* Deps context at this fence.  It is used to model dependencies at the
     265                 :            :      fence so that insn ticks can be properly evaluated.  */
     266                 :            :   deps_t dc;
     267                 :            : 
     268                 :            :   /* Target context at this fence.  Used to save and load any local target
     269                 :            :      scheduling information when changing fences.  */
     270                 :            :   tc_t tc;
     271                 :            : 
     272                 :            :   /* A vector of insns that are scheduled but not yet completed.  */
     273                 :            :   vec<rtx_insn *, va_gc> *executing_insns;
     274                 :            : 
     275                 :            :   /* A vector indexed by UIDs that caches the earliest cycle on which
     276                 :            :      an insn can be scheduled on this fence.  */
     277                 :            :   int *ready_ticks;
     278                 :            : 
     279                 :            :   /* Its size.  */
     280                 :            :   int ready_ticks_size;
     281                 :            : 
     282                 :            :   /* Insn, which has been scheduled last on this fence.  */
     283                 :            :   rtx_insn *last_scheduled_insn;
     284                 :            : 
     285                 :            :   /* The last value of can_issue_more variable on this fence.  */
     286                 :            :   int issue_more;
     287                 :            : 
     288                 :            :   /* If non-NULL force the next scheduled insn to be SCHED_NEXT.  */
     289                 :            :   rtx_insn *sched_next;
     290                 :            : 
     291                 :            :   /* True if fill_insns processed this fence.  */
     292                 :            :   BOOL_BITFIELD processed_p : 1;
     293                 :            : 
     294                 :            :   /* True if fill_insns actually scheduled something on this fence.  */
     295                 :            :   BOOL_BITFIELD scheduled_p : 1;
     296                 :            : 
     297                 :            :   /* True when the next insn scheduled here would start a cycle.  */
     298                 :            :   BOOL_BITFIELD starts_cycle_p : 1;
     299                 :            : 
     300                 :            :   /* True when the next insn scheduled here would be scheduled after a stall.  */
     301                 :            :   BOOL_BITFIELD after_stall_p : 1;
     302                 :            : };
     303                 :            : typedef struct _fence *fence_t;
     304                 :            : 
     305                 :            : #define FENCE_INSN(F) ((F)->insn)
     306                 :            : #define FENCE_STATE(F) ((F)->state)
     307                 :            : #define FENCE_BNDS(F) ((F)->bnds)
     308                 :            : #define FENCE_PROCESSED_P(F) ((F)->processed_p)
     309                 :            : #define FENCE_SCHEDULED_P(F) ((F)->scheduled_p)
     310                 :            : #define FENCE_ISSUED_INSNS(F) ((F)->cycle_issued_insns)
     311                 :            : #define FENCE_CYCLE(F) ((F)->cycle)
     312                 :            : #define FENCE_STARTS_CYCLE_P(F) ((F)->starts_cycle_p)
     313                 :            : #define FENCE_AFTER_STALL_P(F) ((F)->after_stall_p)
     314                 :            : #define FENCE_DC(F) ((F)->dc)
     315                 :            : #define FENCE_TC(F) ((F)->tc)
     316                 :            : #define FENCE_LAST_SCHEDULED_INSN(F) ((F)->last_scheduled_insn)
     317                 :            : #define FENCE_ISSUE_MORE(F) ((F)->issue_more)
     318                 :            : #define FENCE_EXECUTING_INSNS(F) ((F)->executing_insns)
     319                 :            : #define FENCE_READY_TICKS(F) ((F)->ready_ticks)
     320                 :            : #define FENCE_READY_TICKS_SIZE(F) ((F)->ready_ticks_size)
     321                 :            : #define FENCE_SCHED_NEXT(F) ((F)->sched_next)
     322                 :            : 
     323                 :            : /* List of fences.  */
     324                 :            : typedef _list_t flist_t;
     325                 :            : #define FLIST_FENCE(L) (&(L)->u.fence)
     326                 :            : #define FLIST_NEXT(L) (_LIST_NEXT (L))
     327                 :            : 
     328                 :            : /* List of fences with pointer to the tail node.  */
     329                 :            : struct flist_tail_def
     330                 :            : {
     331                 :            :   flist_t head;
     332                 :            :   flist_t *tailp;
     333                 :            : };
     334                 :            : 
     335                 :            : typedef struct flist_tail_def *flist_tail_t;
     336                 :            : #define FLIST_TAIL_HEAD(L) ((L)->head)
     337                 :            : #define FLIST_TAIL_TAILP(L) ((L)->tailp)
     338                 :            : 
     339                 :            : /* List node information.  A list node can be any of the types above.  */
     340                 :            : struct _list_node
     341                 :            : {
     342                 :            :   _list_t next;
     343                 :            : 
     344                 :            :   union
     345                 :            :   {
     346                 :            :     rtx x;
     347                 :            :     insn_t insn;
     348                 :            :     struct _bnd bnd;
     349                 :            :     expr_def expr;
     350                 :            :     struct _fence fence;
     351                 :            :     struct _def def;
     352                 :            :     void *data;
     353                 :            :   } u;
     354                 :            : };
     355                 :            : 
     356                 :            : 
     357                 :            : /* _list_t functions.
     358                 :            :    All of _*list_* functions are used through accessor macros, thus
     359                 :            :    we can't move them in sel-sched-ir.c.  */
     360                 :            : extern object_allocator<_list_node> sched_lists_pool;
     361                 :            : 
     362                 :            : static inline _list_t
     363                 :     236208 : _list_alloc (void)
     364                 :            : {
     365                 :     472416 :   return sched_lists_pool.allocate ();
     366                 :            : }
     367                 :            : 
     368                 :            : static inline void
     369                 :     236208 : _list_add (_list_t *lp)
     370                 :            : {
     371                 :     277705 :   _list_t l = _list_alloc ();
     372                 :            : 
     373                 :     236208 :   _LIST_NEXT (l) = *lp;
     374                 :     210268 :   *lp = l;
     375                 :            : }
     376                 :            : 
     377                 :            : static inline void
     378                 :       2692 : _list_remove_nofree (_list_t *lp)
     379                 :            : {
     380                 :       2692 :   _list_t n = *lp;
     381                 :            : 
     382                 :       2692 :   *lp = _LIST_NEXT (n);
     383                 :            : }
     384                 :            : 
     385                 :            : static inline void
     386                 :     232884 : _list_remove (_list_t *lp)
     387                 :            : {
     388                 :     232884 :   _list_t n = *lp;
     389                 :            : 
     390                 :     232884 :   *lp = _LIST_NEXT (n);
     391                 :      51846 :   sched_lists_pool.remove (n);
     392                 :      33738 : }
     393                 :            : 
     394                 :            : static inline void
     395                 :       9875 : _list_clear (_list_t *l)
     396                 :            : {
     397                 :      38067 :   while (*l)
     398                 :      38067 :     _list_remove (l);
     399                 :            : }
     400                 :            : 
     401                 :            : 
     402                 :            : /* List iterator backend.  */
     403                 :            : struct _list_iterator
     404                 :            : {
     405                 :            :   /* The list we're iterating.  */
     406                 :            :   _list_t *lp;
     407                 :            : 
     408                 :            :   /* True when this iterator supprts removing.  */
     409                 :            :   bool can_remove_p;
     410                 :            : 
     411                 :            :   /* True when we've actually removed something.  */
     412                 :            :   bool removed_p;
     413                 :            : };
     414                 :            : 
     415                 :            : static inline void
     416                 :     729119 : _list_iter_start (_list_iterator *ip, _list_t *lp, bool can_remove_p)
     417                 :            : {
     418                 :     780185 :   ip->lp = lp;
     419                 :     467477 :   ip->can_remove_p = can_remove_p;
     420                 :     467926 :   ip->removed_p = false;
     421                 :     729119 : }
     422                 :            : 
     423                 :            : static inline void
     424                 :    1039623 : _list_iter_next (_list_iterator *ip)
     425                 :            : {
     426                 :     572264 :   if (!ip->removed_p)
     427                 :     417934 :     ip->lp = &_LIST_NEXT (*ip->lp);
     428                 :            :   else
     429                 :     102829 :     ip->removed_p = false;
     430                 :     332229 : }
     431                 :            : 
     432                 :            : static inline void
     433                 :     154397 : _list_iter_remove (_list_iterator *ip)
     434                 :            : {
     435                 :     154397 :   gcc_assert (!ip->removed_p && ip->can_remove_p);
     436                 :     154397 :   _list_remove (ip->lp);
     437                 :     154397 :   ip->removed_p = true;
     438                 :     154397 : }
     439                 :            : 
     440                 :            : static inline void
     441                 :       2692 : _list_iter_remove_nofree (_list_iterator *ip)
     442                 :            : {
     443                 :       2692 :   gcc_assert (!ip->removed_p && ip->can_remove_p);
     444                 :       2692 :   _list_remove_nofree (ip->lp);
     445                 :       2692 :   ip->removed_p = true;
     446                 :       2692 : }
     447                 :            : 
     448                 :            : /* General macros to traverse a list.  FOR_EACH_* interfaces are
     449                 :            :    implemented using these.  */
     450                 :            : #define _FOR_EACH(TYPE, ELEM, I, L)                             \
     451                 :            :   for (_list_iter_start (&(I), &(L), false);                    \
     452                 :            :        _list_iter_cond_##TYPE (*(I).lp, &(ELEM));           \
     453                 :            :        _list_iter_next (&(I)))
     454                 :            : 
     455                 :            : #define _FOR_EACH_1(TYPE, ELEM, I, LP)                              \
     456                 :            :   for (_list_iter_start (&(I), (LP), true);                         \
     457                 :            :        _list_iter_cond_##TYPE (*(I).lp, &(ELEM));                   \
     458                 :            :        _list_iter_next (&(I)))
     459                 :            : 
     460                 :            : 
     461                 :            : /* _xlist_t functions.  */
     462                 :            : 
     463                 :            : static inline void
     464                 :            : _xlist_add (_xlist_t *lp, rtx x)
     465                 :            : {
     466                 :            :   _list_add (lp);
     467                 :            :   _XLIST_X (*lp) = x;
     468                 :            : }
     469                 :            : 
     470                 :            : #define _xlist_remove(LP) (_list_remove (LP))
     471                 :            : #define _xlist_clear(LP) (_list_clear (LP))
     472                 :            : 
     473                 :            : static inline bool
     474                 :            : _xlist_is_in_p (_xlist_t l, rtx x)
     475                 :            : {
     476                 :            :   while (l)
     477                 :            :     {
     478                 :            :       if (_XLIST_X (l) == x)
     479                 :            :         return true;
     480                 :            :       l = _XLIST_NEXT (l);
     481                 :            :     }
     482                 :            : 
     483                 :            :   return false;
     484                 :            : }
     485                 :            : 
     486                 :            : /* Used through _FOR_EACH.  */
     487                 :            : static inline bool
     488                 :            : _list_iter_cond_x (_xlist_t l, rtx *xp)
     489                 :            : {
     490                 :            :   if (l)
     491                 :            :     {
     492                 :            :       *xp = _XLIST_X (l);
     493                 :            :       return true;
     494                 :            :     }
     495                 :            : 
     496                 :            :   return false;
     497                 :            : }
     498                 :            : 
     499                 :            : #define _xlist_iter_remove(IP) (_list_iter_remove (IP))
     500                 :            : 
     501                 :            : typedef _list_iterator _xlist_iterator;
     502                 :            : #define _FOR_EACH_X(X, I, L) _FOR_EACH (x, (X), (I), (L))
     503                 :            : #define _FOR_EACH_X_1(X, I, LP) _FOR_EACH_1 (x, (X), (I), (LP))
     504                 :            : 
     505                 :            : 
     506                 :            : /* ilist_t functions.  */
     507                 :            : 
     508                 :            : static inline void
     509                 :      66747 : ilist_add (ilist_t *lp, insn_t insn)
     510                 :            : {
     511                 :      66747 :   _list_add (lp);
     512                 :      65777 :   ILIST_INSN (*lp) = insn;
     513                 :        970 : }
     514                 :            : #define ilist_remove(LP) (_list_remove (LP))
     515                 :            : #define ilist_clear(LP) (_list_clear (LP))
     516                 :            : 
     517                 :            : static inline bool
     518                 :       1059 : ilist_is_in_p (ilist_t l, insn_t insn)
     519                 :            : {
     520                 :      32049 :   while (l)
     521                 :            :     {
     522                 :      27008 :       if (ILIST_INSN (l) == insn)
     523                 :            :         return true;
     524                 :      26919 :       l = ILIST_NEXT (l);
     525                 :            :     }
     526                 :            : 
     527                 :            :   return false;
     528                 :            : }
     529                 :            : 
     530                 :            : /* Used through _FOR_EACH.  */
     531                 :            : static inline bool
     532                 :       8295 : _list_iter_cond_insn (ilist_t l, insn_t *ip)
     533                 :            : {
     534                 :       8295 :   if (l)
     535                 :            :     {
     536                 :       5774 :       *ip = ILIST_INSN (l);
     537                 :       5774 :       return true;
     538                 :            :     }
     539                 :            : 
     540                 :            :   return false;
     541                 :            : }
     542                 :            : 
     543                 :            : #define ilist_iter_remove(IP) (_list_iter_remove (IP))
     544                 :            : 
     545                 :            : typedef _list_iterator ilist_iterator;
     546                 :            : #define FOR_EACH_INSN(INSN, I, L) _FOR_EACH (insn, (INSN), (I), (L))
     547                 :            : #define FOR_EACH_INSN_1(INSN, I, LP) _FOR_EACH_1 (insn, (INSN), (I), (LP))
     548                 :            : 
     549                 :            : 
     550                 :            : /* Av set iterators.  */
     551                 :            : typedef _list_iterator av_set_iterator;
     552                 :            : #define FOR_EACH_EXPR(EXPR, I, AV) _FOR_EACH (expr, (EXPR), (I), (AV))
     553                 :            : #define FOR_EACH_EXPR_1(EXPR, I, AV) _FOR_EACH_1 (expr, (EXPR), (I), (AV))
     554                 :            : 
     555                 :            : inline bool
     556                 :    1761869 : _list_iter_cond_expr (av_set_t av, expr_t *exprp)
     557                 :            : {
     558                 :    1761869 :   if (av)
     559                 :            :     {
     560                 :    1128706 :       *exprp = _AV_SET_EXPR (av);
     561                 :    1128706 :       return true;
     562                 :            :     }
     563                 :            : 
     564                 :            :   return false;
     565                 :            : }
     566                 :            : 
     567                 :            : 
     568                 :            : /* Def list iterators.  */
     569                 :            : typedef _list_t def_list_t;
     570                 :            : typedef _list_iterator def_list_iterator;
     571                 :            : 
     572                 :            : #define DEF_LIST_NEXT(L) (_LIST_NEXT (L))
     573                 :            : #define DEF_LIST_DEF(L) (&(L)->u.def)
     574                 :            : 
     575                 :            : #define FOR_EACH_DEF(DEF, I, DEF_LIST) _FOR_EACH (def, (DEF), (I), (DEF_LIST))
     576                 :            : 
     577                 :            : static inline bool
     578                 :      13719 : _list_iter_cond_def (def_list_t def_list, def_t *def)
     579                 :            : {
     580                 :      13719 :   if (def_list)
     581                 :            :     {
     582                 :       8190 :       *def = DEF_LIST_DEF (def_list);
     583                 :       8190 :       return true;
     584                 :            :     }
     585                 :            : 
     586                 :            :   return false;
     587                 :            : }
     588                 :            : 
     589                 :            : 
     590                 :            : /* InstructionData.  Contains information about insn pattern.  */
     591                 :            : struct idata_def
     592                 :            : {
     593                 :            :   /* Type of the insn.
     594                 :            :      o CALL_INSN - Call insn
     595                 :            :      o JUMP_INSN - Jump insn
     596                 :            :      o INSN - INSN that cannot be cloned
     597                 :            :      o USE - INSN that can be cloned
     598                 :            :      o SET - INSN that can be cloned and separable into lhs and rhs
     599                 :            :      o PC - simplejump.  Insns that simply redirect control flow should not
     600                 :            :      have any dependencies.  Sched-deps.c, though, might consider them as
     601                 :            :      producers or consumers of certain registers.  To avoid that we handle
     602                 :            :      dependency for simple jumps ourselves.  */
     603                 :            :   int type;
     604                 :            : 
     605                 :            :   /* If insn is a SET, this is its left hand side.  */
     606                 :            :   rtx lhs;
     607                 :            : 
     608                 :            :   /* If insn is a SET, this is its right hand side.  */
     609                 :            :   rtx rhs;
     610                 :            : 
     611                 :            :   /* Registers that are set/used by this insn.  This info is now gathered
     612                 :            :      via sched-deps.c.  The downside of this is that we also use live info
     613                 :            :      from flow that is accumulated in the basic blocks.  These two infos
     614                 :            :      can be slightly inconsistent, hence in the beginning we make a pass
     615                 :            :      through CFG and calculating the conservative solution for the info in
     616                 :            :      basic blocks.  When this scheduler will be switched to use dataflow,
     617                 :            :      this can be unified as df gives us both per basic block and per
     618                 :            :      instruction info.  Actually, we don't do that pass and just hope
     619                 :            :      for the best.  */
     620                 :            :   regset reg_sets;
     621                 :            : 
     622                 :            :   regset reg_clobbers;
     623                 :            : 
     624                 :            :   regset reg_uses;
     625                 :            : };
     626                 :            : 
     627                 :            : #define IDATA_TYPE(ID) ((ID)->type)
     628                 :            : #define IDATA_LHS(ID) ((ID)->lhs)
     629                 :            : #define IDATA_RHS(ID) ((ID)->rhs)
     630                 :            : #define IDATA_REG_SETS(ID) ((ID)->reg_sets)
     631                 :            : #define IDATA_REG_USES(ID) ((ID)->reg_uses)
     632                 :            : #define IDATA_REG_CLOBBERS(ID) ((ID)->reg_clobbers)
     633                 :            : 
     634                 :            : /* Type to represent all needed info to emit an insn.
     635                 :            :    This is a virtual equivalent of the insn.
     636                 :            :    Every insn in the stream has an associated vinsn.  This is used
     637                 :            :    to reduce memory consumption basing on the fact that many insns
     638                 :            :    don't change through the scheduler.
     639                 :            : 
     640                 :            :    vinsn can be either normal or unique.
     641                 :            :    * Normal vinsn is the one, that can be cloned multiple times and typically
     642                 :            :    corresponds to normal instruction.
     643                 :            : 
     644                 :            :    * Unique vinsn derivates from CALL, ASM, JUMP (for a while) and other
     645                 :            :    unusual stuff.  Such a vinsn is described by its INSN field, which is a
     646                 :            :    reference to the original instruction.  */
     647                 :            : struct vinsn_def
     648                 :            : {
     649                 :            :   /* Associated insn.  */
     650                 :            :   rtx_insn *insn_rtx;
     651                 :            : 
     652                 :            :   /* Its description.  */
     653                 :            :   struct idata_def id;
     654                 :            : 
     655                 :            :   /* Hash of vinsn.  It is computed either from pattern or from rhs using
     656                 :            :      hash_rtx.  It is not placed in ID for faster compares.  */
     657                 :            :   unsigned hash;
     658                 :            : 
     659                 :            :   /* Hash of the insn_rtx pattern.  */
     660                 :            :   unsigned hash_rtx;
     661                 :            : 
     662                 :            :   /* Smart pointer counter.  */
     663                 :            :   int count;
     664                 :            : 
     665                 :            :   /* Cached cost of the vinsn.  To access it please use vinsn_cost ().  */
     666                 :            :   int cost;
     667                 :            : 
     668                 :            :   /* Mark insns that may trap so we don't move them through jumps.  */
     669                 :            :   bool may_trap_p;
     670                 :            : };
     671                 :            : 
     672                 :            : #define VINSN_INSN_RTX(VI) ((VI)->insn_rtx)
     673                 :            : #define VINSN_PATTERN(VI) (PATTERN (VINSN_INSN_RTX (VI)))
     674                 :            : 
     675                 :            : #define VINSN_ID(VI) (&((VI)->id))
     676                 :            : #define VINSN_HASH(VI) ((VI)->hash)
     677                 :            : #define VINSN_HASH_RTX(VI) ((VI)->hash_rtx)
     678                 :            : #define VINSN_TYPE(VI) (IDATA_TYPE (VINSN_ID (VI)))
     679                 :            : #define VINSN_SEPARABLE_P(VI) (VINSN_TYPE (VI) == SET)
     680                 :            : #define VINSN_CLONABLE_P(VI) (VINSN_SEPARABLE_P (VI) || VINSN_TYPE (VI) == USE)
     681                 :            : #define VINSN_UNIQUE_P(VI) (!VINSN_CLONABLE_P (VI))
     682                 :            : #define VINSN_LHS(VI) (IDATA_LHS (VINSN_ID (VI)))
     683                 :            : #define VINSN_RHS(VI) (IDATA_RHS (VINSN_ID (VI)))
     684                 :            : #define VINSN_REG_SETS(VI) (IDATA_REG_SETS (VINSN_ID (VI)))
     685                 :            : #define VINSN_REG_USES(VI) (IDATA_REG_USES (VINSN_ID (VI)))
     686                 :            : #define VINSN_REG_CLOBBERS(VI) (IDATA_REG_CLOBBERS (VINSN_ID (VI)))
     687                 :            : #define VINSN_COUNT(VI) ((VI)->count)
     688                 :            : #define VINSN_MAY_TRAP_P(VI) ((VI)->may_trap_p)
     689                 :            : 
     690                 :            : 
     691                 :            : /* An entry of the hashtable describing transformations happened when
     692                 :            :    moving up through an insn.  */
     693                 :            : struct transformed_insns
     694                 :            : {
     695                 :            :   /* Previous vinsn.  Used to find the proper element.  */
     696                 :            :   vinsn_t vinsn_old;
     697                 :            : 
     698                 :            :   /* A new vinsn.  */
     699                 :            :   vinsn_t vinsn_new;
     700                 :            : 
     701                 :            :   /* Speculative status.  */
     702                 :            :   ds_t ds;
     703                 :            : 
     704                 :            :   /* Type of transformation happened.  */
     705                 :            :   enum local_trans_type type;
     706                 :            : 
     707                 :            :   /* Whether a conflict on the target register happened.  */
     708                 :            :   BOOL_BITFIELD was_target_conflict : 1;
     709                 :            : 
     710                 :            :   /* Whether a check was needed.  */
     711                 :            :   BOOL_BITFIELD needs_check : 1;
     712                 :            : };
     713                 :            : 
     714                 :            : /* Indexed by INSN_LUID, the collection of all data associated with
     715                 :            :    a single instruction that is in the stream.  */
     716                 :       8388 : class _sel_insn_data
     717                 :            : {
     718                 :            : public:
     719                 :            :   /* The expression that contains vinsn for this insn and some
     720                 :            :      flow-sensitive data like priority.  */
     721                 :            :   expr_def expr;
     722                 :            : 
     723                 :            :   /* If (WS_LEVEL == GLOBAL_LEVEL) then AV is empty.  */
     724                 :            :   int ws_level;
     725                 :            : 
     726                 :            :   /* A number that helps in defining a traversing order for a region.  */
     727                 :            :   int seqno;
     728                 :            : 
     729                 :            :   /* A liveness data computed above this insn.  */
     730                 :            :   regset live;
     731                 :            : 
     732                 :            :   /* An INSN_UID bit is set when deps analysis result is already known.  */
     733                 :            :   bitmap analyzed_deps;
     734                 :            : 
     735                 :            :   /* An INSN_UID bit is set when a hard dep was found, not set when
     736                 :            :      no dependence is found.  This is meaningful only when the analyzed_deps
     737                 :            :      bitmap has its bit set.  */
     738                 :            :   bitmap found_deps;
     739                 :            : 
     740                 :            :   /* An INSN_UID bit is set when this is a bookkeeping insn generated from
     741                 :            :      a parent with this uid.  If a parent is a bookkeeping copy, all its
     742                 :            :      originators are transitively included in this set.  */
     743                 :            :   bitmap originators;
     744                 :            : 
     745                 :            :   /* A hashtable caching the result of insn transformations through this one.  */
     746                 :            :   htab_t transformed_insns;
     747                 :            : 
     748                 :            :   /* A context incapsulating this insn.  */
     749                 :            :   class deps_desc deps_context;
     750                 :            : 
     751                 :            :   /* This field is initialized at the beginning of scheduling and is used
     752                 :            :      to handle sched group instructions.  If it is non-null, then it points
     753                 :            :      to the instruction, which should be forced to schedule next.  Such
     754                 :            :      instructions are unique.  */
     755                 :            :   insn_t sched_next;
     756                 :            : 
     757                 :            :   /* Cycle at which insn was scheduled.  It is greater than zero if insn was
     758                 :            :      scheduled.  This is used for bundling.  */
     759                 :            :   int sched_cycle;
     760                 :            : 
     761                 :            :   /* Cycle at which insn's data will be fully ready.  */
     762                 :            :   int ready_cycle;
     763                 :            : 
     764                 :            :   /* Speculations that are being checked by this insn.  */
     765                 :            :   ds_t spec_checked_ds;
     766                 :            : 
     767                 :            :   /* Whether the live set valid or not.  */
     768                 :            :   BOOL_BITFIELD live_valid_p : 1;
     769                 :            :   /* Insn is an ASM.  */
     770                 :            :   BOOL_BITFIELD asm_p : 1;
     771                 :            : 
     772                 :            :   /* True when an insn is scheduled after we've determined that a stall is
     773                 :            :      required.
     774                 :            :      This is used when emulating the Haifa scheduler for bundling.  */
     775                 :            :   BOOL_BITFIELD after_stall_p : 1;
     776                 :            : };
     777                 :            : 
     778                 :            : typedef class _sel_insn_data sel_insn_data_def;
     779                 :            : typedef sel_insn_data_def *sel_insn_data_t;
     780                 :            : 
     781                 :            : extern vec<sel_insn_data_def> s_i_d;
     782                 :            : 
     783                 :            : /* Accessor macros for s_i_d.  */
     784                 :            : #define SID(INSN) (&s_i_d[INSN_LUID (INSN)])
     785                 :            : #define SID_BY_UID(UID) (&s_i_d[LUID_BY_UID (UID)])
     786                 :            : 
     787                 :            : extern sel_insn_data_def insn_sid (insn_t);
     788                 :            : 
     789                 :            : #define INSN_ASM_P(INSN) (SID (INSN)->asm_p)
     790                 :            : #define INSN_SCHED_NEXT(INSN) (SID (INSN)->sched_next)
     791                 :            : #define INSN_ANALYZED_DEPS(INSN) (SID (INSN)->analyzed_deps)
     792                 :            : #define INSN_FOUND_DEPS(INSN) (SID (INSN)->found_deps)
     793                 :            : #define INSN_DEPS_CONTEXT(INSN) (SID (INSN)->deps_context)
     794                 :            : #define INSN_ORIGINATORS(INSN) (SID (INSN)->originators)
     795                 :            : #define INSN_ORIGINATORS_BY_UID(UID) (SID_BY_UID (UID)->originators)
     796                 :            : #define INSN_TRANSFORMED_INSNS(INSN) (SID (INSN)->transformed_insns)
     797                 :            : 
     798                 :            : #define INSN_EXPR(INSN) (&SID (INSN)->expr)
     799                 :            : #define INSN_LIVE(INSN) (SID (INSN)->live)
     800                 :            : #define INSN_LIVE_VALID_P(INSN) (SID (INSN)->live_valid_p)
     801                 :            : #define INSN_VINSN(INSN) (EXPR_VINSN (INSN_EXPR (INSN)))
     802                 :            : #define INSN_TYPE(INSN) (VINSN_TYPE (INSN_VINSN (INSN)))
     803                 :            : #define INSN_SIMPLEJUMP_P(INSN) (INSN_TYPE (INSN) == PC)
     804                 :            : #define INSN_LHS(INSN) (VINSN_LHS (INSN_VINSN (INSN)))
     805                 :            : #define INSN_RHS(INSN) (VINSN_RHS (INSN_VINSN (INSN)))
     806                 :            : #define INSN_REG_SETS(INSN) (VINSN_REG_SETS (INSN_VINSN (INSN)))
     807                 :            : #define INSN_REG_CLOBBERS(INSN) (VINSN_REG_CLOBBERS (INSN_VINSN (INSN)))
     808                 :            : #define INSN_REG_USES(INSN) (VINSN_REG_USES (INSN_VINSN (INSN)))
     809                 :            : #define INSN_SCHED_TIMES(INSN) (EXPR_SCHED_TIMES (INSN_EXPR (INSN)))
     810                 :            : #define INSN_SEQNO(INSN) (SID (INSN)->seqno)
     811                 :            : #define INSN_AFTER_STALL_P(INSN) (SID (INSN)->after_stall_p)
     812                 :            : #define INSN_SCHED_CYCLE(INSN) (SID (INSN)->sched_cycle)
     813                 :            : #define INSN_READY_CYCLE(INSN) (SID (INSN)->ready_cycle)
     814                 :            : #define INSN_SPEC_CHECKED_DS(INSN) (SID (INSN)->spec_checked_ds)
     815                 :            : 
     816                 :            : /* A global level shows whether an insn is valid or not.  */
     817                 :            : extern int global_level;
     818                 :            : 
     819                 :            : #define INSN_WS_LEVEL(INSN) (SID (INSN)->ws_level)
     820                 :            : 
     821                 :            : extern av_set_t get_av_set (insn_t);
     822                 :            : extern int get_av_level (insn_t);
     823                 :            : 
     824                 :            : #define AV_SET(INSN) (get_av_set (INSN))
     825                 :            : #define AV_LEVEL(INSN) (get_av_level (INSN))
     826                 :            : #define AV_SET_VALID_P(INSN) (AV_LEVEL (INSN) == global_level)
     827                 :            : 
     828                 :            : /* A list of fences currently in the works.  */
     829                 :            : extern flist_t fences;
     830                 :            : 
     831                 :            : /* A NOP pattern used as a placeholder for real insns.  */
     832                 :            : extern rtx nop_pattern;
     833                 :            : 
     834                 :            : /* An insn that 'contained' in EXIT block.  */
     835                 :            : extern rtx_insn *exit_insn;
     836                 :            : 
     837                 :            : /* Provide a separate luid for the insn.  */
     838                 :            : #define INSN_INIT_TODO_LUID (1)
     839                 :            : 
     840                 :            : /* Initialize s_s_i_d.  */
     841                 :            : #define INSN_INIT_TODO_SSID (2)
     842                 :            : 
     843                 :            : /* Initialize data for simplejump.  */
     844                 :            : #define INSN_INIT_TODO_SIMPLEJUMP (4)
     845                 :            : 
     846                 :            : /* Return true if INSN is a local NOP.  The nop is local in the sense that
     847                 :            :    it was emitted by the scheduler as a temporary insn and will soon be
     848                 :            :    deleted.  These nops are identified by their pattern.  */
     849                 :            : #define INSN_NOP_P(INSN) (PATTERN (INSN) == nop_pattern)
     850                 :            : 
     851                 :            : /* Return true if INSN is linked into instruction stream.
     852                 :            :    NB: It is impossible for INSN to have one field null and the other not
     853                 :            :    null: gcc_assert ((PREV_INSN (INSN) == NULL_RTX)
     854                 :            :    == (NEXT_INSN (INSN) == NULL_RTX)) is valid.  */
     855                 :            : #define INSN_IN_STREAM_P(INSN) (PREV_INSN (INSN) && NEXT_INSN (INSN))
     856                 :            : 
     857                 :            : /* Return true if INSN is in current fence.  */
     858                 :            : #define IN_CURRENT_FENCE_P(INSN) (flist_lookup (fences, INSN) != NULL)
     859                 :            : 
     860                 :            : /* Marks loop as being considered for pipelining.  */
     861                 :            : #define MARK_LOOP_FOR_PIPELINING(LOOP) ((LOOP)->aux = (void *)(size_t)(1))
     862                 :            : #define LOOP_MARKED_FOR_PIPELINING_P(LOOP) ((size_t)((LOOP)->aux))
     863                 :            : 
     864                 :            : /* Saved loop preheader to transfer when scheduling the loop.  */
     865                 :            : #define LOOP_PREHEADER_BLOCKS(LOOP) ((size_t)((LOOP)->aux) == 1         \
     866                 :            :                                      ? NULL                             \
     867                 :            :                                      : ((vec<basic_block> *) (LOOP)->aux))
     868                 :            : #define SET_LOOP_PREHEADER_BLOCKS(LOOP,BLOCKS) ((LOOP)->aux             \
     869                 :            :                                                 = (BLOCKS != NULL       \
     870                 :            :                                                    ? BLOCKS             \
     871                 :            :                                                    : (LOOP)->aux))
     872                 :            : 
     873                 :            : extern bitmap blocks_to_reschedule;
     874                 :            : 
     875                 :            : 
     876                 :            : /* A variable to track which part of rtx we are scanning in
     877                 :            :    sched-deps.c: sched_analyze_insn ().  */
     878                 :            : enum deps_where_t
     879                 :            : {
     880                 :            :   DEPS_IN_INSN,
     881                 :            :   DEPS_IN_LHS,
     882                 :            :   DEPS_IN_RHS,
     883                 :            :   DEPS_IN_NOWHERE
     884                 :            : };
     885                 :            : 
     886                 :            : 
     887                 :            : /* Per basic block data for the whole CFG.  */
     888                 :            : struct sel_global_bb_info_def
     889                 :            : {
     890                 :            :   /* For each bb header this field contains a set of live registers.
     891                 :            :      For all other insns this field has a NULL.
     892                 :            :      We also need to know LV sets for the instructions, that are immediately
     893                 :            :      after the border of the region.  */
     894                 :            :   regset lv_set;
     895                 :            : 
     896                 :            :   /* Status of LV_SET.
     897                 :            :      true - block has usable LV_SET.
     898                 :            :      false - block's LV_SET should be recomputed.  */
     899                 :            :   bool lv_set_valid_p;
     900                 :            : };
     901                 :            : 
     902                 :            : typedef sel_global_bb_info_def *sel_global_bb_info_t;
     903                 :            : 
     904                 :            : 
     905                 :            : /* Per basic block data.  This array is indexed by basic block index.  */
     906                 :            : extern vec<sel_global_bb_info_def> sel_global_bb_info;
     907                 :            : 
     908                 :            : extern void sel_extend_global_bb_info (void);
     909                 :            : extern void sel_finish_global_bb_info (void);
     910                 :            : 
     911                 :            : /* Get data for BB.  */
     912                 :            : #define SEL_GLOBAL_BB_INFO(BB)                                  \
     913                 :            :   (&sel_global_bb_info[(BB)->index])
     914                 :            : 
     915                 :            : /* Access macros.  */
     916                 :            : #define BB_LV_SET(BB) (SEL_GLOBAL_BB_INFO (BB)->lv_set)
     917                 :            : #define BB_LV_SET_VALID_P(BB) (SEL_GLOBAL_BB_INFO (BB)->lv_set_valid_p)
     918                 :            : 
     919                 :            : /* Per basic block data for the region.  */
     920                 :            : struct sel_region_bb_info_def
     921                 :            : {
     922                 :            :   /* This insn stream is constructed in such a way that it should be
     923                 :            :      traversed by PREV_INSN field - (*not* NEXT_INSN).  */
     924                 :            :   rtx_insn *note_list;
     925                 :            : 
     926                 :            :   /* Cached availability set at the beginning of a block.
     927                 :            :      See also AV_LEVEL () for conditions when this av_set can be used.  */
     928                 :            :   av_set_t av_set;
     929                 :            : 
     930                 :            :   /* If (AV_LEVEL == GLOBAL_LEVEL) then AV is valid.  */
     931                 :            :   int av_level;
     932                 :            : };
     933                 :            : 
     934                 :            : typedef sel_region_bb_info_def *sel_region_bb_info_t;
     935                 :            : 
     936                 :            : 
     937                 :            : /* Per basic block data.  This array is indexed by basic block index.  */
     938                 :            : extern vec<sel_region_bb_info_def> sel_region_bb_info;
     939                 :            : 
     940                 :            : /* Get data for BB.  */
     941                 :            : #define SEL_REGION_BB_INFO(BB) (&sel_region_bb_info[(BB)->index])
     942                 :            : 
     943                 :            : /* Get BB's note_list.
     944                 :            :    A note_list is a list of various notes that was scattered across BB
     945                 :            :    before scheduling, and will be appended at the beginning of BB after
     946                 :            :    scheduling is finished.  */
     947                 :            : #define BB_NOTE_LIST(BB) (SEL_REGION_BB_INFO (BB)->note_list)
     948                 :            : 
     949                 :            : #define BB_AV_SET(BB) (SEL_REGION_BB_INFO (BB)->av_set)
     950                 :            : #define BB_AV_LEVEL(BB) (SEL_REGION_BB_INFO (BB)->av_level)
     951                 :            : #define BB_AV_SET_VALID_P(BB) (BB_AV_LEVEL (BB) == global_level)
     952                 :            : 
     953                 :            : /* Used in bb_in_ebb_p.  */
     954                 :            : extern bitmap_head *forced_ebb_heads;
     955                 :            : 
     956                 :            : /* The loop nest being pipelined.  */
     957                 :            : extern class loop *current_loop_nest;
     958                 :            : 
     959                 :            : /* Saves pipelined blocks.  Bitmap is indexed by bb->index.  */
     960                 :            : extern sbitmap bbs_pipelined;
     961                 :            : 
     962                 :            : /* Various flags.  */
     963                 :            : extern bool enable_moveup_set_path_p;
     964                 :            : extern bool pipelining_p;
     965                 :            : extern bool bookkeeping_p;
     966                 :            : extern int max_insns_to_rename;
     967                 :            : extern bool preheader_removed;
     968                 :            : 
     969                 :            : /* Software lookahead window size.
     970                 :            :    According to the results in Nakatani and Ebcioglu [1993], window size of 16
     971                 :            :    is enough to extract most ILP in integer code.  */
     972                 :            : #define MAX_WS (param_selsched_max_lookahead)
     973                 :            : 
     974                 :            : extern regset sel_all_regs;
     975                 :            : 
     976                 :            : 
     977                 :            : /* Successor iterator backend.  */
     978                 :            : struct succ_iterator
     979                 :            : {
     980                 :            :   /* True if we're at BB end.  */
     981                 :            :   bool bb_end;
     982                 :            : 
     983                 :            :   /* An edge on which we're iterating.  */
     984                 :            :   edge e1;
     985                 :            : 
     986                 :            :   /* The previous edge saved after skipping empty blocks.  */
     987                 :            :   edge e2;
     988                 :            : 
     989                 :            :   /* Edge iterator used when there are successors in other basic blocks.  */
     990                 :            :   edge_iterator ei;
     991                 :            : 
     992                 :            :   /* Successor block we're traversing.  */
     993                 :            :   basic_block bb;
     994                 :            : 
     995                 :            :   /* Flags that are passed to the iterator.  We return only successors
     996                 :            :      that comply to these flags.  */
     997                 :            :   short flags;
     998                 :            : 
     999                 :            :   /* When flags include SUCCS_ALL, this will be set to the exact type
    1000                 :            :      of the successor we're traversing now.  */
    1001                 :            :   short current_flags;
    1002                 :            : 
    1003                 :            :   /* If skip to loop exits, save here information about loop exits.  */
    1004                 :            :   int current_exit;
    1005                 :            :   vec<edge> loop_exits;
    1006                 :            : };
    1007                 :            : 
    1008                 :            : /* A structure returning all successor's information.  */
    1009                 :            : struct succs_info
    1010                 :            : {
    1011                 :            :   /* Flags that these succcessors were computed with.  */
    1012                 :            :   short flags;
    1013                 :            : 
    1014                 :            :   /* Successors that correspond to the flags.  */
    1015                 :            :   insn_vec_t succs_ok;
    1016                 :            : 
    1017                 :            :   /* Their probabilities.  As of now, we don't need this for other
    1018                 :            :      successors.  */
    1019                 :            :   vec<int> probs_ok;
    1020                 :            : 
    1021                 :            :   /* Other successors.  */
    1022                 :            :   insn_vec_t succs_other;
    1023                 :            : 
    1024                 :            :   /* Probability of all successors.  */
    1025                 :            :   int all_prob;
    1026                 :            : 
    1027                 :            :   /* The number of all successors.  */
    1028                 :            :   int all_succs_n;
    1029                 :            : 
    1030                 :            :   /* The number of good successors.  */
    1031                 :            :   int succs_ok_n;
    1032                 :            : };
    1033                 :            : 
    1034                 :            : /* Some needed definitions.  */
    1035                 :            : extern basic_block after_recovery;
    1036                 :            : 
    1037                 :            : extern rtx_insn *sel_bb_head (basic_block);
    1038                 :            : extern rtx_insn *sel_bb_end (basic_block);
    1039                 :            : extern bool sel_bb_empty_p (basic_block);
    1040                 :            : extern bool in_current_region_p (basic_block);
    1041                 :            : 
    1042                 :            : /* True when BB is a header of the inner loop.  */
    1043                 :            : static inline bool
    1044                 :        262 : inner_loop_header_p (basic_block bb)
    1045                 :            : {
    1046                 :        262 :   class loop *inner_loop;
    1047                 :            : 
    1048                 :        262 :   if (!current_loop_nest)
    1049                 :            :     return false;
    1050                 :            : 
    1051                 :        186 :   if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
    1052                 :            :     return false;
    1053                 :            : 
    1054                 :        186 :   inner_loop = bb->loop_father;
    1055                 :        186 :   if (inner_loop == current_loop_nest)
    1056                 :            :     return false;
    1057                 :            : 
    1058                 :            :   /* If successor belongs to another loop.  */
    1059                 :         74 :   if (bb == inner_loop->header
    1060                 :         74 :       && flow_bb_inside_loop_p (current_loop_nest, bb))
    1061                 :            :     {
    1062                 :            :       /* Could be '=' here because of wrong loop depths.  */
    1063                 :         81 :       gcc_assert (loop_depth (inner_loop) >= loop_depth (current_loop_nest));
    1064                 :            :       return true;
    1065                 :            :     }
    1066                 :            : 
    1067                 :            :   return false;
    1068                 :            : }
    1069                 :            : 
    1070                 :            : /* Return exit edges of LOOP, filtering out edges with the same dest bb.  */
    1071                 :            : static inline vec<edge> 
    1072                 :            : get_loop_exit_edges_unique_dests (const class loop *loop)
    1073                 :            : {
    1074                 :            :   vec<edge> edges = vNULL;
    1075                 :            :   struct loop_exit *exit;
    1076                 :            : 
    1077                 :            :   gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun)
    1078                 :            :               && current_loops->state & LOOPS_HAVE_RECORDED_EXITS);
    1079                 :            : 
    1080                 :            :   for (exit = loop->exits->next; exit->e; exit = exit->next)
    1081                 :            :     {
    1082                 :            :       int i;
    1083                 :            :       edge e;
    1084                 :            :       bool was_dest = false;
    1085                 :            : 
    1086                 :            :       for (i = 0; edges.iterate (i, &e); i++)
    1087                 :            :         if (e->dest == exit->e->dest)
    1088                 :            :           {
    1089                 :            :             was_dest = true;
    1090                 :            :             break;
    1091                 :            :           }
    1092                 :            : 
    1093                 :            :       if (!was_dest)
    1094                 :            :         edges.safe_push (exit->e);
    1095                 :            :     }
    1096                 :            :   return edges;
    1097                 :            : }
    1098                 :            : 
    1099                 :            : static bool
    1100                 :      33526 : sel_bb_empty_or_nop_p (basic_block bb)
    1101                 :            : {
    1102                 :      33526 :   insn_t first = sel_bb_head (bb), last;
    1103                 :            : 
    1104                 :      33526 :   if (first == NULL_RTX)
    1105                 :            :     return true;
    1106                 :            : 
    1107                 :      33521 :   if (!INSN_NOP_P (first))
    1108                 :            :     return false;
    1109                 :            : 
    1110                 :       1094 :   if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
    1111                 :            :     return false;
    1112                 :            : 
    1113                 :        113 :   last = sel_bb_end (bb);
    1114                 :        113 :   if (first != last)
    1115                 :         52 :     return false;
    1116                 :            : 
    1117                 :            :   return true;
    1118                 :            : }
    1119                 :            : 
    1120                 :            : /* Collect all loop exits recursively, skipping empty BBs between them.
    1121                 :            :    E.g. if BB is a loop header which has several loop exits,
    1122                 :            :    traverse all of them and if any of them turns out to be another loop header
    1123                 :            :    (after skipping empty BBs), add its loop exits to the resulting vector
    1124                 :            :    as well.  */
    1125                 :            : static inline vec<edge> 
    1126                 :        253 : get_all_loop_exits (basic_block bb)
    1127                 :            : {
    1128                 :        253 :   vec<edge> exits = vNULL;
    1129                 :            : 
    1130                 :            :   /* If bb is empty, and we're skipping to loop exits, then
    1131                 :            :      consider bb as a possible gate to the inner loop now.  */
    1132                 :        253 :   while (sel_bb_empty_or_nop_p (bb)
    1133                 :          5 :          && in_current_region_p (bb)
    1134                 :        253 :          && EDGE_COUNT (bb->succs) > 0)
    1135                 :            :     {
    1136                 :          0 :       bb = single_succ (bb);
    1137                 :            : 
    1138                 :            :       /* This empty block could only lead outside the region.  */
    1139                 :          0 :       gcc_assert (! in_current_region_p (bb));
    1140                 :            :     }
    1141                 :            : 
    1142                 :            :   /* And now check whether we should skip over inner loop.  */
    1143                 :        253 :   if (inner_loop_header_p (bb))
    1144                 :            :     {
    1145                 :         27 :       class loop *this_loop;
    1146                 :         27 :       class loop *pred_loop = NULL;
    1147                 :         27 :       int i;
    1148                 :         27 :       unsigned this_depth;
    1149                 :         27 :       edge e;
    1150                 :            : 
    1151                 :         27 :       for (this_loop = bb->loop_father;
    1152                 :         54 :            this_loop && this_loop != current_loop_nest;
    1153                 :         27 :            this_loop = loop_outer (this_loop))
    1154                 :         27 :         pred_loop = this_loop;
    1155                 :            : 
    1156                 :         27 :       this_loop = pred_loop;
    1157                 :         27 :       gcc_assert (this_loop != NULL);
    1158                 :            : 
    1159                 :         27 :       exits = get_loop_exit_edges_unique_dests (this_loop);
    1160                 :         27 :       this_depth = loop_depth (this_loop);
    1161                 :            : 
    1162                 :            :       /* Traverse all loop headers.  Be careful not to go back
    1163                 :            :          to the outer loop's header (see PR 84206).  */
    1164                 :         63 :       for (i = 0; exits.iterate (i, &e); i++)
    1165                 :         36 :         if ((in_current_region_p (e->dest)
    1166                 :          9 :              || (inner_loop_header_p (e->dest)))
    1167                 :         63 :             && loop_depth (e->dest->loop_father) >= this_depth)
    1168                 :            :           {
    1169                 :          0 :             vec<edge> next_exits = get_all_loop_exits (e->dest);
    1170                 :            : 
    1171                 :          0 :             if (next_exits.exists ())
    1172                 :            :               {
    1173                 :            :                 int j;
    1174                 :            :                 edge ne;
    1175                 :            : 
    1176                 :            :                 /* Add all loop exits for the current edge into the
    1177                 :            :                    resulting vector.  */
    1178                 :          0 :                 for (j = 0; next_exits.iterate (j, &ne); j++)
    1179                 :          0 :                   exits.safe_push (ne);
    1180                 :            : 
    1181                 :            :                 /* Remove the original edge.  */
    1182                 :          0 :                 exits.ordered_remove (i);
    1183                 :            : 
    1184                 :            :                 /*  Decrease the loop counter so we won't skip anything.  */
    1185                 :          0 :                 i--;
    1186                 :          0 :                 continue;
    1187                 :            :               }
    1188                 :            :           }
    1189                 :            :     }
    1190                 :            : 
    1191                 :        253 :   return exits;
    1192                 :            : }
    1193                 :            : 
    1194                 :            : /* Flags to pass to compute_succs_info and FOR_EACH_SUCC.
    1195                 :            :    Any successor will fall into exactly one category.   */
    1196                 :            : 
    1197                 :            : /* Include normal successors.  */
    1198                 :            : #define SUCCS_NORMAL (1)
    1199                 :            : 
    1200                 :            : /* Include back-edge successors.  */
    1201                 :            : #define SUCCS_BACK (2)
    1202                 :            : 
    1203                 :            : /* Include successors that are outside of the current region.  */
    1204                 :            : #define SUCCS_OUT (4)
    1205                 :            : 
    1206                 :            : /* When pipelining of the outer loops is enabled, skip innermost loops
    1207                 :            :    to their exits.  */
    1208                 :            : #define SUCCS_SKIP_TO_LOOP_EXITS (8)
    1209                 :            : 
    1210                 :            : /* Include all successors.  */
    1211                 :            : #define SUCCS_ALL (SUCCS_NORMAL | SUCCS_BACK | SUCCS_OUT)
    1212                 :            : 
    1213                 :            : /* We need to return a succ_iterator to avoid 'unitialized' warning
    1214                 :            :    during bootstrap.  */
    1215                 :            : static inline succ_iterator
    1216                 :      32292 : _succ_iter_start (insn_t *succp, insn_t insn, int flags)
    1217                 :            : {
    1218                 :      32292 :   succ_iterator i;
    1219                 :            : 
    1220                 :      32292 :   basic_block bb = BLOCK_FOR_INSN (insn);
    1221                 :            : 
    1222                 :      32292 :   gcc_assert (INSN_P (insn) || NOTE_INSN_BASIC_BLOCK_P (insn));
    1223                 :            : 
    1224                 :      32292 :   i.flags = flags;
    1225                 :            : 
    1226                 :            :   /* Avoid 'uninitialized' warning.  */
    1227                 :      32292 :   *succp = NULL;
    1228                 :      32292 :   i.e1 = NULL;
    1229                 :      32292 :   i.e2 = NULL;
    1230                 :      32292 :   i.bb = bb;
    1231                 :      32292 :   i.current_flags = 0;
    1232                 :      32292 :   i.current_exit = -1;
    1233                 :      32292 :   i.loop_exits.create (0);
    1234                 :            : 
    1235                 :      32292 :   if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun) && BB_END (bb) != insn)
    1236                 :            :     {
    1237                 :      11989 :       i.bb_end = false;
    1238                 :            : 
    1239                 :            :       /* Avoid 'uninitialized' warning.  */
    1240                 :      11989 :       i.ei.index = 0;
    1241                 :      11989 :       i.ei.container = 0;
    1242                 :            :     }
    1243                 :            :   else
    1244                 :            :     {
    1245                 :      20303 :       i.ei = ei_start (bb->succs);
    1246                 :      20303 :       i.bb_end = true;
    1247                 :            :     }
    1248                 :            : 
    1249                 :      32292 :   return i;
    1250                 :            : }
    1251                 :            : 
    1252                 :            : static inline bool
    1253                 :      74898 : _succ_iter_cond (succ_iterator *ip, insn_t *succp, insn_t insn,
    1254                 :            :                  bool check (edge, succ_iterator *))
    1255                 :            : {
    1256                 :      74898 :   if (!ip->bb_end)
    1257                 :            :     {
    1258                 :            :       /* When we're in a middle of a basic block, return
    1259                 :            :          the next insn immediately, but only when SUCCS_NORMAL is set.  */
    1260                 :      23978 :       if (*succp != NULL || (ip->flags & SUCCS_NORMAL) == 0)
    1261                 :            :         return false;
    1262                 :            : 
    1263                 :      11989 :       *succp = NEXT_INSN (insn);
    1264                 :      11989 :       ip->current_flags = SUCCS_NORMAL;
    1265                 :      11989 :       return true;
    1266                 :            :     }
    1267                 :            :   else
    1268                 :            :     {
    1269                 :      50947 :       while (1)
    1270                 :            :         {
    1271                 :      50947 :           edge e_tmp = NULL;
    1272                 :            : 
    1273                 :            :           /* First, try loop exits, if we have them.  */
    1274                 :      50947 :           if (ip->loop_exits.exists ())
    1275                 :            :             {
    1276                 :         63 :               do
    1277                 :            :                 {
    1278                 :         63 :                   ip->loop_exits.iterate (ip->current_exit, &e_tmp);
    1279                 :         63 :                   ip->current_exit++;
    1280                 :            :                 }
    1281                 :         63 :               while (e_tmp && !check (e_tmp, ip));
    1282                 :            : 
    1283                 :         54 :               if (!e_tmp)
    1284                 :         27 :                 ip->loop_exits.release ();
    1285                 :            :             }
    1286                 :            : 
    1287                 :            :           /* If we have found a successor, then great.  */
    1288                 :         54 :           if (e_tmp)
    1289                 :            :             {
    1290                 :         27 :               ip->e1 = e_tmp;
    1291                 :         27 :               break;
    1292                 :            :             }
    1293                 :            : 
    1294                 :            :           /* If not, then try the next edge.  */
    1295                 :      53254 :           while (ei_cond (ip->ei, &(ip->e1)))
    1296                 :            :             {
    1297                 :      33242 :               basic_block bb = ip->e1->dest;
    1298                 :            : 
    1299                 :            :               /* Consider bb as a possible loop header.  */
    1300                 :      33242 :               if ((ip->flags & SUCCS_SKIP_TO_LOOP_EXITS)
    1301                 :       3521 :                   && flag_sel_sched_pipelining_outer_loops
    1302                 :      33533 :                   && (!in_current_region_p (bb)
    1303                 :        156 :                       || BLOCK_TO_BB (ip->bb->index)
    1304                 :        156 :                          < BLOCK_TO_BB (bb->index)))
    1305                 :            :                 {
    1306                 :            :                   /* Get all loop exits recursively.  */
    1307                 :        253 :                   ip->loop_exits = get_all_loop_exits (bb);
    1308                 :            : 
    1309                 :        253 :                   if (ip->loop_exits.exists ())
    1310                 :            :                     {
    1311                 :         27 :                       ip->current_exit = 0;
    1312                 :            :                       /* Move the iterator now, because we won't do
    1313                 :            :                          succ_iter_next until loop exits will end.  */
    1314                 :         27 :                       ei_next (&(ip->ei));
    1315                 :         27 :                       break;
    1316                 :            :                     }
    1317                 :            :                 }
    1318                 :            : 
    1319                 :            :               /* bb is not a loop header, check as usual.  */
    1320                 :      33215 :               if (check (ip->e1, ip))
    1321                 :            :                 break;
    1322                 :            : 
    1323                 :       2334 :               ei_next (&(ip->ei));
    1324                 :            :             }
    1325                 :            : 
    1326                 :            :           /* If loop_exits are non null, we have found an inner loop;
    1327                 :            :              do one more iteration to fetch an edge from these exits.  */
    1328                 :      50920 :           if (ip->loop_exits.exists ())
    1329                 :         27 :             continue;
    1330                 :            : 
    1331                 :            :           /* Otherwise, we've found an edge in a usual way.  Break now.  */
    1332                 :            :           break;
    1333                 :            :         }
    1334                 :            : 
    1335                 :      50920 :       if (ip->e1)
    1336                 :            :         {
    1337                 :      30908 :           basic_block bb = ip->e2->dest;
    1338                 :            : 
    1339                 :      30908 :           if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb == after_recovery)
    1340                 :        708 :             *succp = exit_insn;
    1341                 :            :           else
    1342                 :            :             {
    1343                 :      30200 :               *succp = sel_bb_head (bb);
    1344                 :            : 
    1345                 :      30200 :               gcc_assert (ip->flags != SUCCS_NORMAL
    1346                 :            :                           || *succp == NEXT_INSN (bb_note (bb)));
    1347                 :      30200 :               gcc_assert (BLOCK_FOR_INSN (*succp) == bb);
    1348                 :            :             }
    1349                 :            : 
    1350                 :      30908 :           return true;
    1351                 :            :         }
    1352                 :            :       else
    1353                 :            :         return false;
    1354                 :            :     }
    1355                 :            : }
    1356                 :            : 
    1357                 :            : static inline void
    1358                 :      42606 : _succ_iter_next (succ_iterator *ip)
    1359                 :            : {
    1360                 :      42606 :   gcc_assert (!ip->e2 || ip->e1);
    1361                 :            : 
    1362                 :      42606 :   if (ip->bb_end && ip->e1 && !ip->loop_exits.exists ())
    1363                 :      30590 :     ei_next (&(ip->ei));
    1364                 :      42606 : }
    1365                 :            : 
    1366                 :            : /* Returns true when E1 is an eligible successor edge, possibly skipping
    1367                 :            :    empty blocks.  When E2P is not null, the resulting edge is written there.
    1368                 :            :    FLAGS are used to specify whether back edges and out-of-region edges
    1369                 :            :    should be considered.  */
    1370                 :            : static inline bool
    1371                 :      33251 : _eligible_successor_edge_p (edge e1, succ_iterator *ip)
    1372                 :            : {
    1373                 :      33251 :   edge e2 = e1;
    1374                 :      33251 :   basic_block bb;
    1375                 :      33251 :   int flags = ip->flags;
    1376                 :      33251 :   bool src_outside_rgn = !in_current_region_p (e1->src);
    1377                 :            : 
    1378                 :      33251 :   gcc_assert (flags != 0);
    1379                 :            : 
    1380                 :      33251 :   if (src_outside_rgn)
    1381                 :            :     {
    1382                 :            :       /* Any successor of the block that is outside current region is
    1383                 :            :          ineligible, except when we're skipping to loop exits.  */
    1384                 :         36 :       gcc_assert (flags & (SUCCS_OUT | SUCCS_SKIP_TO_LOOP_EXITS));
    1385                 :            : 
    1386                 :         36 :       if (flags & SUCCS_OUT)
    1387                 :            :         return false;
    1388                 :            :     }
    1389                 :            : 
    1390                 :      33251 :   bb = e2->dest;
    1391                 :            : 
    1392                 :            :   /* Skip empty blocks, but be careful not to leave the region.  */
    1393                 :      33391 :   while (1)
    1394                 :            :     {
    1395                 :      33391 :       if (!sel_bb_empty_p (bb))
    1396                 :            :         {
    1397                 :      33273 :           edge ne;
    1398                 :      33273 :           basic_block nbb;
    1399                 :            : 
    1400                 :      33273 :           if (!sel_bb_empty_or_nop_p (bb))
    1401                 :            :             break;
    1402                 :            : 
    1403                 :         61 :           ne = EDGE_SUCC (bb, 0);
    1404                 :         61 :           nbb = ne->dest;
    1405                 :            : 
    1406                 :         61 :           if (!in_current_region_p (nbb)
    1407                 :         61 :               && !(flags & SUCCS_OUT))
    1408                 :            :             break;
    1409                 :            : 
    1410                 :         61 :           e2 = ne;
    1411                 :         61 :           bb = nbb;
    1412                 :         61 :           continue;
    1413                 :            :         }
    1414                 :            : 
    1415                 :        118 :       if (!in_current_region_p (bb)
    1416                 :        118 :           && !(flags & SUCCS_OUT))
    1417                 :            :         return false;
    1418                 :            : 
    1419                 :         79 :       if (EDGE_COUNT (bb->succs) == 0)
    1420                 :            :         return false;
    1421                 :            : 
    1422                 :         79 :       e2 = EDGE_SUCC (bb, 0);
    1423                 :         79 :       bb = e2->dest;
    1424                 :            :     }
    1425                 :            : 
    1426                 :            :   /* Save the second edge for later checks.  */
    1427                 :      33212 :   ip->e2 = e2;
    1428                 :            : 
    1429                 :      33212 :   if (in_current_region_p (bb))
    1430                 :            :     {
    1431                 :            :       /* BLOCK_TO_BB sets topological order of the region here.
    1432                 :            :          It is important to use real predecessor here, which is ip->bb,
    1433                 :            :          as we may well have e1->src outside current region,
    1434                 :            :          when skipping to loop exits.  */
    1435                 :      22225 :       bool succeeds_in_top_order = (BLOCK_TO_BB (ip->bb->index)
    1436                 :      22225 :                                     < BLOCK_TO_BB (bb->index));
    1437                 :            : 
    1438                 :            :       /* This is true for the all cases except the last one.  */
    1439                 :      22225 :       ip->current_flags = SUCCS_NORMAL;
    1440                 :            : 
    1441                 :            :       /* We are advancing forward in the region, as usual.  */
    1442                 :      22225 :       if (succeeds_in_top_order)
    1443                 :            :         {
    1444                 :            :           /* We are skipping to loop exits here.  */
    1445                 :      19992 :           gcc_assert (!src_outside_rgn
    1446                 :            :                       || flag_sel_sched_pipelining_outer_loops);
    1447                 :      19992 :           return !!(flags & SUCCS_NORMAL);
    1448                 :            :         }
    1449                 :            : 
    1450                 :            :       /* This is a back edge.  During pipelining we ignore back edges,
    1451                 :            :          but only when it leads to the same loop.  It can lead to the header
    1452                 :            :          of the outer loop, which will also be the preheader of
    1453                 :            :          the current loop.  */
    1454                 :       2233 :       if (pipelining_p
    1455                 :       1750 :            && e1->src->loop_father == bb->loop_father)
    1456                 :       1750 :         return !!(flags & SUCCS_NORMAL);
    1457                 :            : 
    1458                 :            :       /* A back edge should be requested explicitly.  */
    1459                 :        483 :       ip->current_flags = SUCCS_BACK;
    1460                 :        483 :       return !!(flags & SUCCS_BACK);
    1461                 :            :     }
    1462                 :            : 
    1463                 :      10987 :   ip->current_flags = SUCCS_OUT;
    1464                 :      10987 :   return !!(flags & SUCCS_OUT);
    1465                 :            : }
    1466                 :            : 
    1467                 :            : #define FOR_EACH_SUCC_1(SUCC, ITER, INSN, FLAGS)                        \
    1468                 :            :   for ((ITER) = _succ_iter_start (&(SUCC), (INSN), (FLAGS));            \
    1469                 :            :        _succ_iter_cond (&(ITER), &(SUCC), (INSN), _eligible_successor_edge_p); \
    1470                 :            :        _succ_iter_next (&(ITER)))
    1471                 :            : 
    1472                 :            : #define FOR_EACH_SUCC(SUCC, ITER, INSN)                 \
    1473                 :            :   FOR_EACH_SUCC_1 (SUCC, ITER, INSN, SUCCS_NORMAL)
    1474                 :            : 
    1475                 :            : /* Return the current edge along which a successor was built.  */
    1476                 :            : #define SUCC_ITER_EDGE(ITER) ((ITER)->e1)
    1477                 :            : 
    1478                 :            : /* Return the next block of BB not running into inconsistencies.  */
    1479                 :            : static inline basic_block
    1480                 :       1554 : bb_next_bb (basic_block bb)
    1481                 :            : {
    1482                 :       1554 :   switch (EDGE_COUNT (bb->succs))
    1483                 :            :     {
    1484                 :         15 :     case 0:
    1485                 :         15 :       return bb->next_bb;
    1486                 :            : 
    1487                 :        489 :     case 1:
    1488                 :        489 :       return single_succ (bb);
    1489                 :            : 
    1490                 :       1042 :     case 2:
    1491                 :       1042 :       return FALLTHRU_EDGE (bb)->dest;
    1492                 :            : 
    1493                 :          8 :     default:
    1494                 :          8 :       return bb->next_bb;
    1495                 :            :     }
    1496                 :            : 
    1497                 :            :   gcc_unreachable ();
    1498                 :            : }
    1499                 :            : 
    1500                 :            : 
    1501                 :            : 
    1502                 :            : /* Functions that are used in sel-sched.c.  */
    1503                 :            : 
    1504                 :            : /* List functions.  */
    1505                 :            : extern ilist_t ilist_copy (ilist_t);
    1506                 :            : extern ilist_t ilist_invert (ilist_t);
    1507                 :            : extern void blist_add (blist_t *, insn_t, ilist_t, deps_t);
    1508                 :            : extern void blist_remove (blist_t *);
    1509                 :            : extern void flist_tail_init (flist_tail_t);
    1510                 :            : 
    1511                 :            : extern fence_t flist_lookup (flist_t, insn_t);
    1512                 :            : extern void flist_clear (flist_t *);
    1513                 :            : extern void def_list_add (def_list_t *, insn_t, unsigned int);
    1514                 :            : 
    1515                 :            : /* Target context functions.  */
    1516                 :            : extern tc_t create_target_context (bool);
    1517                 :            : extern void set_target_context (tc_t);
    1518                 :            : extern void reset_target_context (tc_t, bool);
    1519                 :            : 
    1520                 :            : /* Deps context functions.  */
    1521                 :            : extern void advance_deps_context (deps_t, insn_t);
    1522                 :            : 
    1523                 :            : /* Fences functions.  */
    1524                 :            : extern void init_fences (insn_t);
    1525                 :            : extern void add_clean_fence_to_fences (flist_tail_t, insn_t, fence_t);
    1526                 :            : extern void add_dirty_fence_to_fences (flist_tail_t, insn_t, fence_t);
    1527                 :            : extern void move_fence_to_fences (flist_t, flist_tail_t);
    1528                 :            : 
    1529                 :            : /* Pool functions.  */
    1530                 :            : extern regset get_regset_from_pool (void);
    1531                 :            : extern regset get_clear_regset_from_pool (void);
    1532                 :            : extern void return_regset_to_pool (regset);
    1533                 :            : extern void free_regset_pool (void);
    1534                 :            : 
    1535                 :            : extern insn_t get_nop_from_pool (insn_t);
    1536                 :            : extern void return_nop_to_pool (insn_t, bool);
    1537                 :            : extern void free_nop_pool (void);
    1538                 :            : 
    1539                 :            : /* Vinsns functions.  */
    1540                 :            : extern bool vinsn_separable_p (vinsn_t);
    1541                 :            : extern bool vinsn_cond_branch_p (vinsn_t);
    1542                 :            : extern void recompute_vinsn_lhs_rhs (vinsn_t);
    1543                 :            : extern int sel_vinsn_cost (vinsn_t);
    1544                 :            : extern insn_t sel_gen_insn_from_rtx_after (rtx, expr_t, int, insn_t);
    1545                 :            : extern insn_t sel_gen_recovery_insn_from_rtx_after (rtx, expr_t, int, insn_t);
    1546                 :            : extern insn_t sel_gen_insn_from_expr_after (expr_t, vinsn_t, int, insn_t);
    1547                 :            : extern insn_t  sel_move_insn (expr_t, int, insn_t);
    1548                 :            : extern void vinsn_attach (vinsn_t);
    1549                 :            : extern void vinsn_detach (vinsn_t);
    1550                 :            : extern vinsn_t vinsn_copy (vinsn_t, bool);
    1551                 :            : extern bool vinsn_equal_p (vinsn_t, vinsn_t);
    1552                 :            : 
    1553                 :            : /* EXPR functions.  */
    1554                 :            : extern void copy_expr (expr_t, expr_t);
    1555                 :            : extern void copy_expr_onside (expr_t, expr_t);
    1556                 :            : extern void merge_expr_data (expr_t, expr_t, insn_t);
    1557                 :            : extern void merge_expr (expr_t, expr_t, insn_t);
    1558                 :            : extern void clear_expr (expr_t);
    1559                 :            : extern unsigned expr_dest_regno (expr_t);
    1560                 :            : extern rtx expr_dest_reg (expr_t);
    1561                 :            : extern int find_in_history_vect (vec<expr_history_def> ,
    1562                 :            :                                  rtx, vinsn_t, bool);
    1563                 :            : extern void insert_in_history_vect (vec<expr_history_def> *,
    1564                 :            :                                     unsigned, enum local_trans_type,
    1565                 :            :                                     vinsn_t, vinsn_t, ds_t);
    1566                 :            : extern void mark_unavailable_targets (av_set_t, av_set_t, regset);
    1567                 :            : extern int speculate_expr (expr_t, ds_t);
    1568                 :            : 
    1569                 :            : /* Av set functions.  */
    1570                 :            : extern void av_set_add (av_set_t *, expr_t);
    1571                 :            : extern void av_set_iter_remove (av_set_iterator *);
    1572                 :            : extern expr_t av_set_lookup (av_set_t, vinsn_t);
    1573                 :            : extern expr_t merge_with_other_exprs (av_set_t *, av_set_iterator *, expr_t);
    1574                 :            : extern bool av_set_is_in_p (av_set_t, vinsn_t);
    1575                 :            : extern av_set_t av_set_copy (av_set_t);
    1576                 :            : extern void av_set_union_and_clear (av_set_t *, av_set_t *, insn_t);
    1577                 :            : extern void av_set_union_and_live (av_set_t *, av_set_t *, regset, regset, insn_t);
    1578                 :            : extern void av_set_clear (av_set_t *);
    1579                 :            : extern void av_set_leave_one_nonspec (av_set_t *);
    1580                 :            : extern expr_t av_set_element (av_set_t, int);
    1581                 :            : extern void av_set_substract_cond_branches (av_set_t *);
    1582                 :            : extern void av_set_split_usefulness (av_set_t, int, int);
    1583                 :            : extern void av_set_code_motion_filter (av_set_t *, av_set_t);
    1584                 :            : 
    1585                 :            : extern void sel_save_haifa_priorities (void);
    1586                 :            : 
    1587                 :            : extern void sel_init_global_and_expr (bb_vec_t);
    1588                 :            : extern void sel_finish_global_and_expr (void);
    1589                 :            : 
    1590                 :            : extern regset compute_live (insn_t);
    1591                 :            : extern bool register_unavailable_p (regset, rtx);
    1592                 :            : 
    1593                 :            : /* Dependence analysis functions.  */
    1594                 :            : extern void sel_clear_has_dependence (void);
    1595                 :            : extern ds_t has_dependence_p (expr_t, insn_t, ds_t **);
    1596                 :            : 
    1597                 :            : extern int tick_check_p (expr_t, deps_t, fence_t);
    1598                 :            : 
    1599                 :            : /* Functions to work with insns.  */
    1600                 :            : extern bool lhs_of_insn_equals_to_dest_p (insn_t, rtx);
    1601                 :            : extern bool insn_eligible_for_subst_p (insn_t);
    1602                 :            : extern void get_dest_and_mode (rtx, rtx *, machine_mode *);
    1603                 :            : 
    1604                 :            : extern bool bookkeeping_can_be_created_if_moved_through_p (insn_t);
    1605                 :            : extern bool sel_remove_insn (insn_t, bool, bool);
    1606                 :            : extern bool bb_header_p (insn_t);
    1607                 :            : extern void sel_init_invalid_data_sets (insn_t);
    1608                 :            : extern bool insn_at_boundary_p (insn_t);
    1609                 :            : 
    1610                 :            : /* Basic block and CFG functions.  */
    1611                 :            : 
    1612                 :            : extern rtx_insn *sel_bb_head (basic_block);
    1613                 :            : extern bool sel_bb_head_p (insn_t);
    1614                 :            : extern rtx_insn *sel_bb_end (basic_block);
    1615                 :            : extern bool sel_bb_end_p (insn_t);
    1616                 :            : extern bool sel_bb_empty_p (basic_block);
    1617                 :            : 
    1618                 :            : extern bool in_current_region_p (basic_block);
    1619                 :            : extern basic_block fallthru_bb_of_jump (const rtx_insn *);
    1620                 :            : 
    1621                 :            : extern void sel_init_bbs (bb_vec_t);
    1622                 :            : extern void sel_finish_bbs (void);
    1623                 :            : 
    1624                 :            : extern struct succs_info * compute_succs_info (insn_t, short);
    1625                 :            : extern void free_succs_info (struct succs_info *);
    1626                 :            : extern bool sel_insn_has_single_succ_p (insn_t, int);
    1627                 :            : extern bool sel_num_cfg_preds_gt_1 (insn_t);
    1628                 :            : extern int get_seqno_by_preds (rtx_insn *);
    1629                 :            : 
    1630                 :            : extern bool bb_ends_ebb_p (basic_block);
    1631                 :            : extern bool in_same_ebb_p (insn_t, insn_t);
    1632                 :            : 
    1633                 :            : extern bool tidy_control_flow (basic_block, bool);
    1634                 :            : extern void free_bb_note_pool (void);
    1635                 :            : 
    1636                 :            : extern void purge_empty_blocks (void);
    1637                 :            : extern basic_block sel_split_edge (edge);
    1638                 :            : extern basic_block sel_create_recovery_block (insn_t);
    1639                 :            : extern bool sel_redirect_edge_and_branch (edge, basic_block);
    1640                 :            : extern void sel_redirect_edge_and_branch_force (edge, basic_block);
    1641                 :            : extern void sel_init_pipelining (void);
    1642                 :            : extern void sel_finish_pipelining (void);
    1643                 :            : extern void sel_sched_region (int);
    1644                 :            : extern loop_p get_loop_nest_for_rgn (unsigned int);
    1645                 :            : extern bool considered_for_pipelining_p (class loop *);
    1646                 :            : extern void make_region_from_loop_preheader (vec<basic_block> *&);
    1647                 :            : extern void sel_add_loop_preheaders (bb_vec_t *);
    1648                 :            : extern bool sel_is_loop_preheader_p (basic_block);
    1649                 :            : extern void clear_outdated_rtx_info (basic_block);
    1650                 :            : extern void free_data_sets (basic_block);
    1651                 :            : extern void exchange_data_sets (basic_block, basic_block);
    1652                 :            : extern void copy_data_sets (basic_block, basic_block);
    1653                 :            : 
    1654                 :            : extern void sel_register_cfg_hooks (void);
    1655                 :            : extern void sel_unregister_cfg_hooks (void);
    1656                 :            : 
    1657                 :            : /* Expression transformation routines.  */
    1658                 :            : extern rtx_insn *create_insn_rtx_from_pattern (rtx, rtx);
    1659                 :            : extern vinsn_t create_vinsn_from_insn_rtx (rtx_insn *, bool);
    1660                 :            : extern rtx_insn *create_copy_of_insn_rtx (rtx);
    1661                 :            : extern void change_vinsn_in_expr (expr_t, vinsn_t);
    1662                 :            : 
    1663                 :            : /* Various initialization functions.  */
    1664                 :            : extern void init_lv_sets (void);
    1665                 :            : extern void free_lv_sets (void);
    1666                 :            : extern void setup_nop_and_exit_insns (void);
    1667                 :            : extern void free_nop_and_exit_insns (void);
    1668                 :            : extern void free_data_for_scheduled_insn (insn_t);
    1669                 :            : extern void setup_nop_vinsn (void);
    1670                 :            : extern void free_nop_vinsn (void);
    1671                 :            : extern void sel_set_sched_flags (void);
    1672                 :            : extern void sel_setup_sched_infos (void);
    1673                 :            : extern void alloc_sched_pools (void);
    1674                 :            : extern void free_sched_pools (void);
    1675                 :            : 
    1676                 :            : #endif /* GCC_SEL_SCHED_IR_H */

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.