#include "config.h"#include "system.h"#include "coretypes.h"#include "tm.h"#include "diagnostic-core.h"#include "hard-reg-set.h"#include "rtl.h"#include "tm_p.h"#include "regs.h"#include "function.h"#include "flags.h"#include "insn-config.h"#include "insn-attr.h"#include "except.h"#include "recog.h"#include "sched-int.h"#include "target.h"#include "common/common-target.h"#include "params.h"#include "dbgcnt.h"#include "cfgloop.h"#include "ira.h"#include "emit-rtl.h"#include "hash-table.h"#include "dumpfile.h"
Functions | |
| void | schedule_insns () |
Variables | |
| struct haifa_sched_info * | current_sched_info |
Function Documentation
| void schedule_insns | ( | void | ) |
In sched-rgn.c.
Variable Documentation
| struct haifa_sched_info* current_sched_info |
Instruction scheduling pass. Copyright (C) 1992-2013 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.c, contains the generic parts. The actual entry point is found for the normal instruction scheduling pass is found in sched-rgn.c.
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:
- choose insn with the longest path to end of bb, ties broken by
- choose insn with least contribution to register pressure, ties broken by
- prefer in-block upon interblock motion, ties broken by
- prefer useful upon speculative motion, ties broken by
- choose insn with largest control flow probability, ties broken by
- 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.
- 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_backward_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 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.
