Index of values

Set a1 + l in (pc, dst) after eventually updating with the old value at (pc, a1).

Set a1 + a2 in (pc, dst) after eventually updating with the old values of {(pc, a1), (pc, a2)}.

Fold computing the overall compensation value to add for a given list of arguments cargs, seeking for defined affine forms in block pc first, and in replace_pts otherwise (in case some values are out of the block's scope; it happens in practice).

Finds the first defined affine form with key (pt, arg) for each pt in pts.

Grab the constant of affine form with key tup; Used for injuring operations.

Compute the sum of all Aff_term(ci, ri, ...) with ci * (aff_inj_const_int64 (pc, ri)).

If force, replace the value at tup by aff, else, add it only if tup is not already defined.

Set a1 * l in (pc, dst) after eventually updating with the old value at (pc, a1).

Addition over affine values with type 'a.

Maps a tuple (block pc, register) to its int64 affine value, if applicable.

Affine value times a constant of type 'a.

returns true if and only if the vector only contains ones

returns true if and only if the vector only contains zeros

(Bitv.append v1 v2) returns a fresh vector containing the concatenation of the vectors v1 and v2.

This function performs an analysis over a single basic-block ib.

(Bitv.blit v1 o1 v2 o2 len) copies len elements from vector v1, starting at element number o1, to vector v2, starting at element number o2.

Translate a virtual candidate to a concrete BTL instruction.

Build all the needed invariants for LCT: for each candidate in the list, with a defined vaux: g1 = (N-REPLACE /\ not N-INSERT) \/ (X-REPLACE /\ not X-INSERT) g2 = (not N-ISOLATED /\ not X-ISOLATED) g3 = (not N-DELAYED /\ not X-DELAYED) pp = g1 \/ (g2 /\ g3) if the candidate is trapping: pp = pp /\ N-U-SAFE for blk_pc in CFG if blk_pc <> entry: if candidate is a SRmul && candidate is not immediate SR op && candidate was reduced: r = constant_reg of candidate cop, cpc = obtain the constant operation and first appearance block pc if blk_pc < cpc && r <= last_reg (ie is not a fresh variable) && (blk_pc in pp || r live in blk_pc) add an history invariant based on the constant operation, along with a corresponding liveness entry.

bitwise AND; raises Invalid_argument if the two vectors do not have the same length

bitwise NOT

bitwise OR; raises Invalid_argument if the two vectors do not have the same length

bitwise XOR; raises Invalid_argument if the two vectors do not have the same length

Maps candidates keys to candidate type cand_t.

Apply line scheduler then advanced solver

Check that a problem is well-formed.

Validate that a solution is truly a solution of a scheduling problem.

Clone a list of instructions into free pc indexes * * The list of instructions should be contiguous, and not include any loop.

Applies code motion using the information in insert_pred and replace_pred.

Compute the insertion point for a given basic-block and candidate.

Non-trapping insertion points: Insert(n) = Latest(n) /\ not Isolated(n)

Trapping insertion points: First computes a set P = , For each pc_p, build the set I = /\ (N-Comp(pc_i) \/ X-Comp(pc_i)) /\ exists (p : path), p = (pc_i, pc_p) /\ forall n, n in p /\ n > pc_i /\ n < pc_p -> Transp(n) Then, it applies the below rules: |I| > 0 -> N-Replace(pc_p) <- true X-Comp(pc_p) = true -> X-Insert(pc_p) <- true /\ X-replace(pc_p) <- true For each pc_i, N-Comp(pc_i) -> N-Insert(pc_i) <- true /\ N-Replace(pc_i) <- true, X-Comp(pc_i) -> X-Insert(pc_i) <- true /\ X-Replace(pc_i) <- true

Bitv.concat is similar to Bitv.append, but catenates a list of vectors.

Maps registers to immediate constant operation (if they are unchanged over the whole function).

(Bitv.copy v) returns a copy of v, that is, a fresh vector containing the same elements as v.

(Bitv.create n b) creates a new bit vector of length n, initialized with b.

Critical transfer function sols.(0) should be xcritical and sols.(1) should be ncritical.

D_Safe transfer function sols.(0) should be xdsafe and sols.(1) should be ndsafe.

Main dataflow analysis.

Default predicate value, this setting is very important and quite touchy...

Delayed transfer function sols.(0) should be ndelayed and sols.(1) should be xdelayed.

Detect candidates (transfer function to be used with apply_over_function).

Detect constants over the whole function (never erased) A constant that is defined multiple times is still a constant, and in this case we keep the oldest (former) one.

Returns true if two bit vectors are of the same length and with the same bits.

Compare both cand and old_cand according to their position, update the lhs field of the earlier, and and erase the last one by emptying lhs.

Returns true if the argument exceeds the maximum length of a bit vector (System dependent).

(Bitv.fill v ofs len b) modifies the vector v in place, storing b in elements number ofs to ofs + len - 1.

Limit the number of candidates according to the user flag.

Push critical insertion points forward to the first non critical but substitution critical point, in the direction of the control-flow.

(Bitv.fold_left f x v) computes f (... (f (f x (get v 0)) (get v 1)) ...) (get v (n-1)), where n is the length of the vector v.

(Bitv.fold_right f a x) computes f (get v 0) (f (get v 1) ( ... (f (get v (n-1)) x) ...)), where n is the length of the vector v.

Forward substitution of auxiliary variables, and candidate replacement procedure.

(Bitv.get v n) returns the nth bit of v.

Get max latency from solution

Get the number of instructions in a problem

Get the number of resources in a problem

Form a list containing both sources and destination regs of a block

gray_iter f n iterates function f on all bit vectors of length n, once each, using a Gray code.

Schedule the problem using the order of instructions without any reordering.

This function builds two mappings from block ids to bitvector ids and its reverse, to facilitate bitvector manipulation.

(Bitv.init n f) returns a fresh vector of length n, with bit number i initialized to the result of (f i).

Init non-recursive predicates and computes local ones for a whole function.

Initialize local and non-recursive predicates.

If the ckey already exist, we check if the candidate was already seen in block pc, ifso, we add it to the offset set, ifnot, we create a singleton.

Insert inst in ib at offset_target, using offset as iterator.

Is the predicate requiring a forward analysis?

If a candidate for strength-reduction is never injured, then we can perform the code-motion dataflow analysis only.

Isolated transfer function sols.(0) should be xisolated and sols.(1) should be nisolated.

(Bitv.iter f v) applies function f in turn to all the elements of v.

iteri_true f v applies function f in turn to all indexes of the elements of v which are set (i.e.

Launch according to cli args.

Bitv.length returns the length (number of elements) of the given vector.

Schedule the problem using a greedy list scheduling algorithm, from the start.

Computes transp, injure, ncomp and xcomp predicates.

Build a candidate from a btl operation.

Given a function f, (Bitv.map f v) applies f to all the elements of v, and builds a vector with the results returned by f.

Bitv.iteri and Bitv.mapi are similar to Bitv.iter and Bitv.map respectively, but the function is applied to the index of the element as first argument, and the element itself as second argument.

Get the length of a maximal critical path

Get the number the last scheduling time used for an instruction in a solution.

Downgrading an SRadd candidate to a LCM one.

Merge an eventually existing candidate at ckey with cand, and erase the latest one.

Initialize a new candidate appearing at pc, offset with _memdep, args and default values.

At the beginning, every predicate option is set to None.

Population count, i.e., number of 1 bits

Print every predicates of every candidates in a CSV-like format separated with semicolumns.

Print problem for human readability.

the useful one.

WIP : Same as list_scheduler, but schedules instructions which decrease register pressure when it gets too high.

Schedule a problem from the end using a list scheduler.

moves bits from least to most significant with wraparound

moves bits from most to least significant with wraparound

Main dataflow function: a unidirectionnal round-robin worklist (in wl) based dataflow algorithm taking a transfer function tf as parameter, and working on a single candidate cand at a time.

Main translation function, that can either build basic-blocks or superblocks, and that can optionnaly insert synthetic nodes

Translate from RTL to BTL with basic-blocks

Translate from RTL to BTL with basic-blocks and synthetic nodes

Translate from RTL to BTL with superblocks

Schedule a problem using a scheduler applied in the opposite direction, e.g.

Schedule a problem using a scheduler given by a string name

(Bitv.set v n b) sets the nth bit of v to the value b.

Set insertion and replacement points in the candidate record.

Write an array of predicates preds with an array of solutions sols.

moves bits from least to most significant; introduces zeros

moves bits from most to least significant; introduces zeros

Insert update assignments for strength reduction candidates

(Bitv.sub v start len) returns a fresh vector of length len, containing the bits number start to start + len - 1 of vector v.

Subst-Crit transfer function sols.(0) should be nsubstcrit and sols.(1) should be xsubstcrit.

U_Safe transfer function sols.(0) should be nusafe and sols.(1) should be xusafe.

Update transfer function sols contains the single equation.

Apply a scheduler and validate the result against the input problem.