## make-final-basic-block-order-list.api
#
# The fastest jump is the jump eliminated by having one basic block fall
# through to the next. Consequently, one important code improvment technique
# ("optimization") is to order the basic blocks in a controlflow graph so that
# the most-frequently-used jumps vanish in this way.
#
# Earlier phases provide hints toward this goal by setting to FALLSTHRU
# or (BRANCH FALSE) those edges in the controlflow graph which they estimate
# to be most worth eliminating in this way.
#
# Here we define the API to the modules which complete this task by actually
# selecting a final global ordering for all basic blocks in a controlflow graph.
#
# This code appears to use pretty naive algorithms.
# For a more sophisticated analysis of the block ordering
# problem and dynamic programming algorithm see:
#
# Jump Minimization In Linear Time
# M V S Ramanath, University of Western Ontario,
# Marvin Solomon, University of Wisconsin
# ACM Transactions on Programming Languages and Systems
# Vol 6 #4 Oct 1984 pages 527-545
# http://dl.acm.org/citation.cfm?id=357262
#
# -- 2011-12-02 CrT
# Compiled by:
# src/lib/compiler/back/low/lib/lowhalf.lib# Perform code block placement
# When several blocks are successors to the unique entry node,
# then block with the lowest block id appears first.
# This usually corresponds to what one wants when doing dynamic
# code generation.
# "The advantage of the experienced programmer is not
# so much that he is better at solving difficult
# problems -- although he usually is -- as that he
# is better at avoiding them in the first place."
# This api is implemented in:
#
# src/lib/compiler/back/low/block-placement/make-final-basic-block-order-list-g.pkg# src/lib/compiler/back/low/block-placement/default-block-placement-g.pkg# src/lib/compiler/back/low/block-placement/weighted-block-placement-g.pkg#
# (The first just selects one of the other two.)
#
api Make_Final_Basic_Block_Order_List {
#
package mcg: Machcode_Controlflow_Graph; # Machcode_Controlflow_Graph is from src/lib/compiler/back/low/mcg/machcode-controlflow-graph.api make_final_basic_block_order_list
:
mcg::Machcode_Controlflow_Graph
->
( mcg::Machcode_Controlflow_Graph,
List( mcg::Node )
);
};
## COPYRIGHT (c) 2001 Bell Labs, Lucent Technologies
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2015,
## released per terms of SMLNJ-COPYRIGHT.