Instruction scheduling pass.
Copyright (C) 1992-2024 Free Software Foundation, Inc.
Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
and currently maintained by, Jim Wilson (wilson@cygnus.com)
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/>.
Instruction scheduling pass. This file, along with sched-deps.cc,
contains the generic parts. The actual entry point for
the normal instruction scheduling pass is found in sched-rgn.cc.
We compute insn priorities based on data dependencies. Flow
analysis only creates a fraction of the data-dependencies we must
observe: namely, only those dependencies which the combiner can be
expected to use. For this pass, we must therefore create the
remaining dependencies we need to observe: register dependencies,
memory dependencies, dependencies to keep function calls in order,
and the dependence between a conditional branch and the setting of
condition codes are all dealt with here.
The scheduler first traverses the data flow graph, starting with
the last instruction, and proceeding to the first, assigning values
to insn_priority as it goes. This sorts the instructions
topologically by data dependence.
Once priorities have been established, we order the insns using
list scheduling. This works as follows: starting with a list of
all the ready insns, and sorted according to priority number, we
schedule the insn from the end of the list by placing its
predecessors in the list according to their priority order. We
consider this insn scheduled by setting the pointer to the "end" of
the list to point to the previous insn. When an insn has no
predecessors, we either queue it until sufficient time has elapsed
or add it to the ready list. As the instructions are scheduled or
when stalls are introduced, the queue advances and dumps insns into
the ready list. When all insns down to the lowest priority have
been scheduled, the critical path of the basic block has been made
as short as possible. The remaining insns are then scheduled in
remaining slots.
The following list shows the order in which we want to break ties
among insns in the ready list:
1. choose insn with the longest path to end of bb, ties
broken by
2. choose insn with least contribution to register pressure,
ties broken by
3. prefer in-block upon interblock motion, ties broken by
4. prefer useful upon speculative motion, ties broken by
5. choose insn with largest control flow probability, ties
broken by
6. choose insn with the least dependences upon the previously
scheduled insn, or finally
7 choose the insn which has the most insns dependent on it.
8. choose insn with lowest UID.
Memory references complicate matters. Only if we can be certain
that memory references are not part of the data dependency graph
(via true, anti, or output dependence), can we move operations past
memory references. To first approximation, reads can be done
independently, while writes introduce dependencies. Better
approximations will yield fewer dependencies.
Before reload, an extended analysis of interblock data dependences
is required for interblock scheduling. This is performed in
compute_block_dependences ().
Dependencies set up by memory references are treated in exactly the
same way as other dependencies, by using insn backward dependences
INSN_BACK_DEPS. INSN_BACK_DEPS are translated into forward dependences
INSN_FORW_DEPS for the purpose of forward list scheduling.
Having optimized the critical path, we may have also unduly
extended the lifetimes of some registers. If an operation requires
that constants be loaded into registers, it is certainly desirable
to load those constants as early as necessary, but no earlier.
I.e., it will not do to load up a bunch of registers at the
beginning of a basic block only to use them at the end, if they
could be loaded later, since this may result in excessive register
utilization.
Note that since branches are never in basic blocks, but only end
basic blocks, this pass will not move branches. But that is ok,
since we can use GNU's delayed branch scheduling pass to take care
of this case.
Also note that no further optimizations based on algebraic
identities are performed, so this pass would be a good one to
perform instruction splitting, such as breaking up a multiply
instruction into shifts and adds where that is profitable.
Given the memory aliasing analysis that this pass should perform,
it should be possible to remove redundant stores to memory, and to
load values from registers instead of hitting memory.
Before reload, speculative insns are moved only if a 'proof' exists
that no exception will be caused by this, and if no live registers
exist that inhibit the motion (live registers constraints are not
represented by data dependence edges).
This pass must update information that subsequent passes expect to
be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
reg_n_calls_crossed, and reg_live_length. Also, BB_HEAD, BB_END.
The information in the line number notes is carefully retained by
this pass. Notes that refer to the starting and ending of
exception regions are also carefully retained by this pass. All
other NOTE insns are grouped in their same relative order at the
beginning of basic blocks and regions that have been scheduled.
Point to state used for the current scheduling pass.
