Subversion Repositories scarts

; Semantic fragments.
; Copyright (C) 2000, 2009 Red Hat, Inc.
; This file is part of CGEN.
; See file COPYING.CGEN for details.
; Background info:
; Some improvement in pbb simulator efficiency is obtained in cases like
; the ARM where for example operand2 computation is expensive in terms of
; cpu cost, code size, and subroutine call overhead if the code is put in
; a subroutine.  It could be inlined, but there are numerous occurences
; resulting in poor icache usage.
; If the computation is put in its own fragment then code size is reduced
; [improving icache usage] and subroutine call overhead is removed in a
; computed-goto simulator [arguments are passed in machine generated local
; variables].
;
; The basic procedure here is to:
; - break all insns up into a set of statements
;   This is either one statement in the case of insns that don't begin with a
;   sequence, or a list of statements, one for each element in the sequence.
; - find a profitable set of common leading statements (called the "header")
;   and a profitable set of common trailing statements (called the "trailer")
;   What is "profitable" depends on
;   - how expensive the statement is
;   - how long the statement is
;   - the number of insns using the statement
;   - what fraction of the total insn the statement is
; - rewrite insn semantics in terms of the new header and trailer fragments
;   plus a "middle" part that is whatever is left over
;   - there is always a header, the middle and trailer parts are optional
;   - cti insns require a header and trailer, though they can be the same
;     fragment
;
; TODO:
; - check ARM orr insns which come out as header, tiny middle, trailer
;   - the tiny middle seems like a waste (combine with trailer?)
; - there are 8 trailers consisting of just `nop' for ARM
; - rearranging statements to increase number and length of common sets
; - combine common middle fragments
; - parallel's not handled yet (only have to handle parallel's at the
;   top level)
; - insns can also be split on timing-sensitive boundaries (pipeline, memory,
;   whatever) though that is not implemented yet.  This may involve rtl
;   additions.
;
; Usage:
; - call sim-sfrag-init! first, to initialize
; - call sim-sfrag-analyze-insns! to create the semantic fragments
; - afterwards, call
;   - sim-sfrag-insn-list
;   - sim-sfrag-frag-table
;   - sim-sfrag-usage-table
;   - sim-sfrag-locals-list
; Statement computation.
; Set to #t to collect various statistics.
; Collection of computed stats.  Only set if -stmt-stats? = #t.
; Collection of computed statement data.  Only set if -stmt-stats? = #t.
; Create a structure recording data of all statements.
; A pair of (next-ordinal . table).
; Accessors.
; A single statement.
; INSN semantics either consist of a single statement or a sequence of them.
; RTL code
; Local variables of the sequence `expr' is in.
; Ordinal of the statement.
; Costs.
; SPEED-COST is the cost of executing fragment, relative to a
; simple add.
; SIZE-COST is the size of the fragment, relative to a simple
; add.
; ??? The cost numbers are somewhat arbitrary and subject to
; review.
; Users of this statement.
; Each element is (owner-number . owner-object),
; where owner-number is an index into the initial insn table
; (e.g. insn-list arg of sfrag-create-cse-mapping), and
; owner-object is the corresponding object.
; Make a <statement> object of EXPR.
; LOCALS is a list of local variables of the sequence EXPR is in.
; NUM is the ordinal of EXPR.
; SPEED-COST is the cost of executing the statement, relative to a simple add.
; SIZE-COST is the size of the fragment, relative to a simple add.
; ??? The cost numbers are somewhat arbitrary and subject to review.
;
; The user list is set to nil.
; Add a user of STMT.
; Lookup STMT in DATA.
; CHAIN-NUM is an argument so it need only be computed once.
; The result is the found <statement> object or #f.
; ??? equal? should be appropriate rtx-equal?, blah blah blah.
; Hash a statement.
; Computed hash value.
; Global 'cus -frag-hash-compute! is defined globally so we can use
; /fastcall (FIXME: Need /fastcall to work on non-global procs).
; Keep number small.
; #f -> "continue with normal traversing"
; FIXME: (/fastcall-make -frag-hash-compute!))
; Compute the speed/size costs of a statement.
; Compute speed/size costs.
; Global 'cus -frag-cost-compute! is defined globally so we can use
; /fastcall (FIXME: Need /fastcall to work on non-global procs).
; FIXME: wip
; these don't contribute to costs (at least for now)
; FIXME: speed/size = 0?
; #f -> "continue with normal traversing"
; FIXME: (/fastcall-make -frag-cost-compute!))
; Add STMT to statement table DATA.
; CHAIN-NUM is the chain in the hash table to add STMT to.
; {SPEED,SIZE}-COST are passed through to -stmt-make.
; The result is the newly created <statement> object.
; Return the locals in EXPR.
; If a sequence, return locals.
; Otherwise, return nil.
; The result is in assq'able form.
; Return the statements in EXPR.
; If a sequence, return the sequence's expressions.
; Otherwise, return (list expr).
; Analyze statement STMT.
; If STMT is already in STMT-DATA increment its frequency count.
; Otherwise add it.
; LOCALS are locals of the sequence STMT is in.
; USAGE-TABLE is a vector of statement index lists for each expression.
; USAGE-INDEX is the index of USAGE-TABLE to use.
; OWNER is the object of the owner of the statement.
"Analyzing statement: ""\n""  chain #""\n""  new statement, #""\n""  existing statement, #""\n"; If first entry, initialize list, otherwise append to existing list.
; Analyze each statement in EXPR and add it to STMT-DATA.
; OWNER is the object of the owner of the expression.
; USAGE-TABLE is a vector of statement index lists for each expression.
; USAGE-INDEX is the index of the USAGE-TABLE entry to use.
; As each statement's ordinal is computed it is added to the usage list.
"Analyzing "": ""\n"; Compute statement data from EXPRS, a list of expressions.
; OWNERS is a vector of objects that "own" each corresponding element in EXPRS.
; The owner is usually an <insn> object.  Actually it'll probably always be
; an <insn> object but for now I want the disassociation.
;
; The result contains:
; - vector of statement lists of each expression
;   - each element is (stmt1-index stmt2-index ...) where each stmtN-index is
;     an index into the statement table
; - vector of statements (the statement table of the previous item)
;   - each element is a <statement> object
"Computing statement table ...\n"; FIXME: This is just a quick hack to put something down on paper.
; blah blah blah.  Revisit as necessary.
; Hash table of expressions.
; Statement index lists for each expression.
; Scan each expr, filling in stmt-data and usage-table.
; Convert statement hash table to vector.
; All done.  Compute stats if asked to.
; See how well the hashing worked.
; Result.
; Semantic fragment selection.
;
; "semantic fragment" is the name assigned to each header/middle/trailer
; "fragment" as each may consist of more than one statement, though not
; necessarily all statements of the original sequence.
; List of insn's using this frag.
; Ordinal's of each element of `users'.
; Semantic format of insns using this fragment.
; List of statement numbers that make up `semantics'.
; Each element is an index into the stmt-table arg of
; -frag-pick-best.
; This is #f if the sfrag wasn't derived from some set of
; statements.
; Raw rtl source of fragment.
; Compiled source.
; Boolean indicating if this frag is for parallel exec support.
; Boolean indicating if this is a header frag.
; This includes all frags that begin a sequence.
; Boolean indicating if this is a trailer frag.
; This includes all frags that end a sequence.
; Sorter to merge common fragments together.
; A and B are lists of statement numbers.
; =
; Return a boolean indicating if L1,L2 match in the first LEN elements.
; Each element is an integer.
; Return the number of expressions that match in the first LEN statements.
; Return a boolean indicating if making STMT-LIST a common fragment
; among several owners is profitable.
; STMT-LIST is a list of statement numbers, indices into STMT-TABLE.
; NUM-EXPRS is the number of expressions with STMT-LIST in common.
; FIXME: wip
; No need to include speed costs yet.
;(>= (-frag-list-speed-cost stmt-table stmt-list) 10)
; Return the cost of executing STMT-LIST.
; STMT-LIST is a list of statment numbers, indices into STMT-TABLE.
;
; FIXME: The yardstick to use is wip.  Currently we measure things relative
; to a simple add insn which is given the value 1.
; FIXME: wip
; FIXME: wip
; Compute the longest set of fragments it is desirable/profitable to create.
; The result is (number-of-matching-exprs . stmt-number-list)
; or #f if there isn't one (the longest set is the empty set).
;
; What is desirable depends on a few things:
; - how often is it used?
; - how expensive is it (size-wise and speed-wise)
; - relationship to other frags
;
; STMT-TABLE is a vector of all statements.
; STMT-USAGE-TABLE is a vector of all expressions.  Each element is a list of
; statement numbers (indices into STMT-TABLE).
; INDICES is a sorted list of indices into STMT-USAGE-TABLE.
; STMT-USAGE-TABLE is processed in the order specified by INDICES.
;
; FIXME: Choosing a statement list should depend on whether there are existing
; chosen statement lists only slightly shorter.
; STMT-LIST is the list of statements in the first expression.
; See how many subsequent expressions match at length LEN.
; If there aren't any, we're done.
; If LEN-1 is usable, return that.
; Otherwise there is no profitable list of fragments.
; Found at least 1 subsequent matching expression.
; Extend LEN and see if we still find matching expressions.
; Return list of lists of objects for each unique <sformat-argbuf> in
; USER-LIST.
; Each element of USER-LIST is (insn-num . <insn> object).
; The result is a list of lists.  Each element in the top level list is
; a list of elements of USER-LIST that have the same <sformat-argbuf>.
; Insns are also distinguished by being a CTI insn vs a non-CTI insn.
; CTI insns require special handling in the semantics.
; Sanity check.
"sformats not computed""sformat argbufs not computed"; Find INSN in SFMT-LIST.  The result is the list INSN belongs in
; or #f.
; Done
; Return a list of desired fragments to create.
; These consist of the longest set of profitable leading statements in EXPRS.
; Each element of the result is an <sfrag> object.
;
; STMT-TABLE is a vector of all statements.
; STMT-USAGE-TABLE is a vector of statement number lists of each expression.
; OWNER-TABLE is a vector of owner objects of each corresponding expression
; in STMT-USAGE-TABLE.
; KIND is one of 'header or 'trailer.
;
; This works for trailing fragments too as we do the computation based on the
; reversed statement lists.
"Computing desired "" frags ...\n"; Sort STMT-USAGE-TABLE.  That will bring exprs with common fragments
; together.
; List of statement lists that together yield the fragment to create,
; plus associated users.
; Update STMT-USAGE-TABLE in case we reversed the contents.
"Iteration ""\n"; Found an acceptable frag to create.
; Reverse statement numbers back if trailer.
; Need one copy of the frag for each sbuf, as structure
; offsets will be different in generated C/C++ code.
"Creating frag of length "", "" users\n""Indices: ""\n"; Create an sfrag for each sbuf.
""; compiled-semantics
; parallel?
; Continue, dropping statements we've put into the frag.
; Couldn't find an acceptable statement list.
; Try again with next one.
"No acceptable frag found.\n"; Done.
; Return the set of desired fragments to create.
; STMT-TABLE is a vector of each statement.
; STMT-USAGE-TABLE is a vector of (stmt1-index stmt2-index ...) elements for
; each expression, where each stmtN-index is an index into STMT-TABLE.
; OWNER-TABLE is a vector of owner objects of each corresponding expression
; in STMT-USAGE-TABLE.
;
; Each expression is split in up to three pieces: header, middle, trailer.
; This computes pseudo-optimal headers and trailers (if they exist).
; The "middle" part is whatever is leftover.
;
; The result is a vector of 4 elements:
; - vector of (header middle trailer) semantic fragments for each expression
;   - each element is an index into the respective table or #f if not present
; - list of header fragments, each element is an <sfrag> object
; - same but for trailer fragments
; - same but for middle fragments
;
; ??? While this is a big function, each piece is simple and straightforward.
; It's kept as one big function so we can compute each expression's sfrag list
; as we go.  Though it's not much extra expense to not do this.
; FIXME: Shouldn't have to do vector->list.
; Specify result holders here, simplifies code.
; Also allocate space for expression sfrag usage table.
; We compute it as we go to save scanning the header and trailer
; lists twice.
; copy-tree is needed to avoid shared storage.
; Compute desired headers.
; Compute the header used by each expression.
; Truncate each expression by the header it will use and then find
; the set of desired trailers.
; FIXME: Shouldn't have to use list->vector.
; [still pass a vector, but use vector-map here instead of map]
; Record the trailer used by each expression.
; We have the desired headers and trailers, now compute the middle
; part for each expression.  This is just what's left over.
; ??? We don't try to cse the middle part.  Though we can in the
; future should it prove useful enough.
"Computing middle frags ...\n"; Finally, record the middle sfrags used by each expression.
; Done!
; [The next statement executed after this is the one at the
; end that builds the result.  Maybe it should be built here
; and this should be the last statement, but I'm trying this
; style out for awhile.]
; Does this expr have a middle sfrag?
; Nope.
; Yep.
", middle part"; compiled-semantics
; parallel?
; header?
; trailer?
; Result.
; Given a list of expressions, return list of locals in top level sequences.
; ??? Collisions will be handled by rewriting rtl (renaming locals).
;
; This has to be done now as the cse pass must (currently) take into account
; the rewritten rtl.
; ??? This can be done later, with an appropriate enhancement to rtx-equal?
; ??? cse can be improved by ignoring local variable name (of course).
"Computing common locals ...\n"; already present
; Done.
; Common subexpression computation.
; Given a list of rtl expressions and their owners, return a pseudo-optimal
; set of fragments and a usage list for each owner.
; Common fragments are combined and the original expressions become a sequence
; of these fragments.  The result is "pseudo-optimal" in the sense that the
; desired result is somewhat optimal, though no attempt is made at precise
; optimality.
;
; OWNERS is a list of objects that "own" each corresponding element in EXPRS.
; The owner is usually an <insn> object.  Actually it'll probably always be
; an <insn> object but for now I want the disassociation.
;
; The result is a vector of six elements:
; - sfrag usage table for each owner #(header middle trailer)
; - statement table (vector of all statements, made with -stmt-make)
; - list of sequence locals used by header sfrags
;   - these locals are defined at the top level so that all fragments have
;     access to them
;   - ??? Need to handle collisions among incompatible types.
; - header sfrags
; - trailer sfrags
; - middle sfrags
; Sanity check.
"sformats not computed"; A simple procedure that calls, in order:
; -frag-compute-locals!
; -frag-compute-statements
; -frag-pick-best
; The rest is shuffling of results.
; Internally it's easier if OWNERS is a vector.
; Collect statement usage data.
; Compute the frags we want to create.
; These are in general sequences of statements.
; Result.
; Cover proc of -sem-find-common-frags-1.
; See its documentation.
"Simplifying/canonicalizing rtl ...\n"; Subroutine of sfrag-create-cse-mapping to compute INSN's fragment list.
; FRAG-USAGE is a vector of 3 elements: #(header middle trailer).
; Each element is a fragment number or #f if not present.
; Numbers in FRAG-USAGE are indices relative to their respective subtables
; of FRAG-TABLE (which is a vector of all 3 tables concatenated together).
; NUM-HEADERS,NUM-TRAILERS are used to compute absolute indices.
;
; No header may have been created.  This happens when
; it's not profitable (or possible) to merge this insn's
; leading statements with other insns.  Ditto for
; trailer.  However, each cti insn must have a header
; and a trailer (for pc handling setup and change).
; Try to use the middle fragment if present.  Otherwise,
; use the x-header,x-trailer virtual insns.
; `(list #f)' is so append! works.  The #f is deleted before returning.
; cse'd header created?
; Yep.
; Nope.  Use the middle frag if present, otherwise use x-header.
; Can't use the trailer fragment because by definition it is shared
; among several insns.
; Mark the middle frag as the header frag.
; No middle, use x-header.
; middle fragment present?
; cse'd trailer created?
; Yep.
; Nope.  Use the middle frag if present, otherwise use x-trailer.
; Can't use the header fragment because by definition it is shared
; among several insns.
; Mark the middle frag as the trailer frag.
; No middle, use x-trailer.
; Done.
; Subroutine of sfrag-create-cse-mapping to find the fragment number of the
; x-header/x-trailer virtual frags.
"expected virtual insn not present"; Handle complex case, find set of common header and trailer fragments.
; The result is a vector of:
; - fragment table (a vector)
; - table mapping used fragments for each insn (a list)
; - locals list
"Creating semantic fragments for pbb engine ...\n"; Extract the results of sem-find-common-frags.
; Create two special frags: x-header, x-trailer.
; These are used by insns that don't have one or the other.
; Header/trailer table indices are already computed for each insn
; so append x-header/x-trailer to the end.
"header fragment for insns without one""semantic frag computation"""; users
; user ordinals
; stmt-numbers
; compiled-semantics
; parallel?
; header?
; trailer?
"trailer fragment for insns without one""semantic frag computation"""; users
; user ordinals
; stmt-numbers
; compiled-semantics
; parallel?
; header?
; trailer?
; Combine the three sfrag tables (headers, trailers, middles) into
; one big one.
; Convert sfrag-usage-table to one that refers to the one big
; sfrag table.
"Computing insn frag usage ...\n"; FIXME: vector->list
"Done fragment creation.\n"; Data analysis interface.
; Keep in globals for now, simplifies debugging.
; evil globals, blah blah blah.
; Testing support.