/* Instruction scheduling pass.  This file contains definitions used
   internally in the scheduler.
   Copyright (C) 2006-2018 Free Software Foundation, Inc.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#ifndef GCC_SEL_SCHED_IR_H
#define GCC_SEL_SCHED_IR_H

/* For state_t.  */
/* For reg_note.  */

/* tc_t is a short for target context.  This is a state of the target
   backend.  */
typedef void *tc_t;

/* List data types used for av sets, fences, paths, and boundaries.  */

/* Forward declarations for types that are part of some list nodes.  */
struct _list_node;

/* List backend.  */
typedef struct _list_node *_list_t;
#define _LIST_NEXT(L) ((L)->next)

/* Instruction data that is part of vinsn type.  */
struct idata_def;
typedef struct idata_def *idata_t;

/* A virtual instruction, i.e. an instruction as seen by the scheduler.  */
struct vinsn_def;
typedef struct vinsn_def *vinsn_t;

/* RTX list.
   This type is the backend for ilist.  */
typedef _list_t _xlist_t;
#define _XLIST_X(L) ((L)->u.x)
#define _XLIST_NEXT(L) (_LIST_NEXT (L))

/* Instruction.  */
typedef rtx_insn *insn_t;

/* List of insns.  */
typedef _list_t ilist_t;
#define ILIST_INSN(L) ((L)->u.insn)
#define ILIST_NEXT(L) (_LIST_NEXT (L))

/* This lists possible transformations that done locally, i.e. in
   moveup_expr.  */
enum local_trans_type
  {
    TRANS_SUBSTITUTION,
    TRANS_SPECULATION
  };

/* This struct is used to record the history of expression's
   transformations.  */
struct expr_history_def_1
{
  /* UID of the insn.  */
  unsigned uid;

  /* How the expression looked like.  */
  vinsn_t old_expr_vinsn;

  /* How the expression looks after the transformation.  */
  vinsn_t new_expr_vinsn;

  /* And its speculative status.  */
  ds_t spec_ds;

  /* Type of the transformation.  */
  enum local_trans_type type;
};

typedef struct expr_history_def_1 expr_history_def;


/* Expression information.  */
struct _expr
{
  /* Insn description.  */
  vinsn_t vinsn;

  /* SPEC is the degree of speculativeness.
     FIXME: now spec is increased when an rhs is moved through a
     conditional, thus showing only control speculativeness.  In the
     future we'd like to count data spec separately to allow a better
     control on scheduling.  */
  int spec;

  /* Degree of speculativeness measured as probability of executing
     instruction's original basic block given relative to
     the current scheduling point.  */
  int usefulness;

  /* A priority of this expression.  */
  int priority;

  /* A priority adjustment of this expression.  */
  int priority_adj;

  /* Number of times the insn was scheduled.  */
  int sched_times;

  /* A basic block index this was originated from.  Zero when there is
     more than one originator.  */
  int orig_bb_index;

  /* Instruction should be of SPEC_DONE_DS type in order to be moved to this
     point.  */
  ds_t spec_done_ds;

  /* SPEC_TO_CHECK_DS hold speculation types that should be checked
     (used only during move_op ()).  */
  ds_t spec_to_check_ds;

  /* Cycle on which original insn was scheduled.  Zero when it has not yet
     been scheduled or more than one originator.  */
  int orig_sched_cycle;

  /* This vector contains the history of insn's transformations.  */
  vec<expr_history_def> history_of_changes;

  /* True (1) when original target (register or memory) of this instruction
     is available for scheduling, false otherwise.  -1 means we're not sure;
     please run find_used_regs to clarify.  */
  signed char target_available;

  /* True when this expression needs a speculation check to be scheduled.
     This is used during find_used_regs.  */
  BOOL_BITFIELD needs_spec_check_p : 1;

  /* True when the expression was substituted.  Used for statistical
     purposes.  */
  BOOL_BITFIELD was_substituted : 1;

  /* True when the expression was renamed.  */
  BOOL_BITFIELD was_renamed : 1;

  /* True when expression can't be moved.  */
  BOOL_BITFIELD cant_move : 1;
};

typedef struct _expr expr_def;
typedef expr_def *expr_t;

#define EXPR_VINSN(EXPR) ((EXPR)->vinsn)
#define EXPR_INSN_RTX(EXPR) (VINSN_INSN_RTX (EXPR_VINSN (EXPR)))
#define EXPR_PATTERN(EXPR) (VINSN_PATTERN (EXPR_VINSN (EXPR)))
#define EXPR_LHS(EXPR) (VINSN_LHS (EXPR_VINSN (EXPR)))
#define EXPR_RHS(EXPR) (VINSN_RHS (EXPR_VINSN (EXPR)))
#define EXPR_TYPE(EXPR) (VINSN_TYPE (EXPR_VINSN (EXPR)))
#define EXPR_SEPARABLE_P(EXPR) (VINSN_SEPARABLE_P (EXPR_VINSN (EXPR)))

#define EXPR_SPEC(EXPR) ((EXPR)->spec)
#define EXPR_USEFULNESS(EXPR) ((EXPR)->usefulness)
#define EXPR_PRIORITY(EXPR) ((EXPR)->priority)
#define EXPR_PRIORITY_ADJ(EXPR) ((EXPR)->priority_adj)
#define EXPR_SCHED_TIMES(EXPR) ((EXPR)->sched_times)
#define EXPR_ORIG_BB_INDEX(EXPR) ((EXPR)->orig_bb_index)
#define EXPR_ORIG_SCHED_CYCLE(EXPR) ((EXPR)->orig_sched_cycle)
#define EXPR_SPEC_DONE_DS(EXPR) ((EXPR)->spec_done_ds)
#define EXPR_SPEC_TO_CHECK_DS(EXPR) ((EXPR)->spec_to_check_ds)
#define EXPR_HISTORY_OF_CHANGES(EXPR) ((EXPR)->history_of_changes)
#define EXPR_TARGET_AVAILABLE(EXPR) ((EXPR)->target_available)
#define EXPR_NEEDS_SPEC_CHECK_P(EXPR) ((EXPR)->needs_spec_check_p)
#define EXPR_WAS_SUBSTITUTED(EXPR) ((EXPR)->was_substituted)
#define EXPR_WAS_RENAMED(EXPR) ((EXPR)->was_renamed)
#define EXPR_CANT_MOVE(EXPR) ((EXPR)->cant_move)

/* Insn definition for list of original insns in find_used_regs.  */
struct _def
{
  insn_t orig_insn;

  /* FIXME: Get rid of CROSSES_CALL in each def, since if we're moving up
     rhs from two different places, but only one of the code motion paths
     crosses a call, we can't use any of the call_used_regs, no matter which
     path or whether all paths crosses a call.  Thus we should move CROSSES_CALL
     to static params.  */
  bool crosses_call;
};
typedef struct _def *def_t;


/* Availability sets are sets of expressions we're scheduling.  */
typedef _list_t av_set_t;
#define _AV_SET_EXPR(L) (&(L)->u.expr)
#define _AV_SET_NEXT(L) (_LIST_NEXT (L))


/* Boundary of the current fence group.  */
struct _bnd
{
  /* The actual boundary instruction.  */
  insn_t to;

  /* Its path to the fence.  */
  ilist_t ptr;

  /* Availability set at the boundary.  */
  av_set_t av;

  /* This set moved to the fence.  */
  av_set_t av1;

  /* Deps context at this boundary.  As long as we have one boundary per fence,
     this is just a pointer to the same deps context as in the corresponding
     fence.  */
  deps_t dc;
};
typedef struct _bnd *bnd_t;
#define BND_TO(B) ((B)->to)

/* PTR stands not for pointer as you might think, but as a Path To Root of the
   current instruction group from boundary B.  */
#define BND_PTR(B) ((B)->ptr)
#define BND_AV(B) ((B)->av)
#define BND_AV1(B) ((B)->av1)
#define BND_DC(B) ((B)->dc)

/* List of boundaries.  */
typedef _list_t blist_t;
#define BLIST_BND(L) (&(L)->u.bnd)
#define BLIST_NEXT(L) (_LIST_NEXT (L))


/* Fence information.  A fence represents current scheduling point and also
   blocks code motion through it when pipelining.  */
struct _fence
{
  /* Insn before which we gather an instruction group.*/
  insn_t insn;

  /* Modeled state of the processor pipeline.  */
  state_t state;

  /* Current cycle that is being scheduled on this fence.  */
  int cycle;

  /* Number of insns that were scheduled on the current cycle.
     This information has to be local to a fence.  */
  int cycle_issued_insns;

  /* At the end of fill_insns () this field holds the list of the instructions
     that are inner boundaries of the scheduled parallel group.  */
  ilist_t bnds;

  /* Deps context at this fence.  It is used to model dependencies at the
     fence so that insn ticks can be properly evaluated.  */
  deps_t dc;

  /* Target context at this fence.  Used to save and load any local target
     scheduling information when changing fences.  */
  tc_t tc;

  /* A vector of insns that are scheduled but not yet completed.  */
  vec<rtx_insn *, va_gc> *executing_insns;

  /* A vector indexed by UIDs that caches the earliest cycle on which
     an insn can be scheduled on this fence.  */
  int *ready_ticks;

  /* Its size.  */
  int ready_ticks_size;

  /* Insn, which has been scheduled last on this fence.  */
  rtx_insn *last_scheduled_insn;

  /* The last value of can_issue_more variable on this fence.  */
  int issue_more;

  /* If non-NULL force the next scheduled insn to be SCHED_NEXT.  */
  rtx_insn *sched_next;

  /* True if fill_insns processed this fence.  */
  BOOL_BITFIELD processed_p : 1;

  /* True if fill_insns actually scheduled something on this fence.  */
  BOOL_BITFIELD scheduled_p : 1;

  /* True when the next insn scheduled here would start a cycle.  */
  BOOL_BITFIELD starts_cycle_p : 1;

  /* True when the next insn scheduled here would be scheduled after a stall.  */
  BOOL_BITFIELD after_stall_p : 1;
};
typedef struct _fence *fence_t;

#define FENCE_INSN(F) ((F)->insn)
#define FENCE_STATE(F) ((F)->state)
#define FENCE_BNDS(F) ((F)->bnds)
#define FENCE_PROCESSED_P(F) ((F)->processed_p)
#define FENCE_SCHEDULED_P(F) ((F)->scheduled_p)
#define FENCE_ISSUED_INSNS(F) ((F)->cycle_issued_insns)
#define FENCE_CYCLE(F) ((F)->cycle)
#define FENCE_STARTS_CYCLE_P(F) ((F)->starts_cycle_p)
#define FENCE_AFTER_STALL_P(F) ((F)->after_stall_p)
#define FENCE_DC(F) ((F)->dc)
#define FENCE_TC(F) ((F)->tc)
#define FENCE_LAST_SCHEDULED_INSN(F) ((F)->last_scheduled_insn)
#define FENCE_ISSUE_MORE(F) ((F)->issue_more)
#define FENCE_EXECUTING_INSNS(F) ((F)->executing_insns)
#define FENCE_READY_TICKS(F) ((F)->ready_ticks)
#define FENCE_READY_TICKS_SIZE(F) ((F)->ready_ticks_size)
#define FENCE_SCHED_NEXT(F) ((F)->sched_next)

/* List of fences.  */
typedef _list_t flist_t;
#define FLIST_FENCE(L) (&(L)->u.fence)
#define FLIST_NEXT(L) (_LIST_NEXT (L))

/* List of fences with pointer to the tail node.  */
struct flist_tail_def
{
  flist_t head;
  flist_t *tailp;
};

typedef struct flist_tail_def *flist_tail_t;
#define FLIST_TAIL_HEAD(L) ((L)->head)
#define FLIST_TAIL_TAILP(L) ((L)->tailp)

/* List node information.  A list node can be any of the types above.  */
struct _list_node
{
  _list_t next;

  union
  {
    rtx x;
    insn_t insn;
    struct _bnd bnd;
    expr_def expr;
    struct _fence fence;
    struct _def def;
    void *data;
  } u;
};
