Advanced Backend Optimization

Appendix 4

Efficiency of Non-Positive Circuit Elimination in the SIRA Framework

A4.1. Experimental setup

These experiments were conducted by Sébastien Briais on the stand-alone data dependence graph (DDG) described in Appendix 1. We assume Τ = {GR, BR, FP}. We used a regular Linux workstation (Intel Xeon, 2.33 GHz, 9 GB of memory).

A4.1.1. Heuristics nomenclature

Our methods to avoid the creation of non-positive circuits are of three types:

1) UAL is the (pessimistic) naive heuristic that consists of applying SIRALINA with unit-assumed-latencies (UAL) semantics only. That is, we do not consider non-unit-assumed-latencies (NUAL) code semantics from the beginning.

2) CHECK is the reactive strategy that consists of first applying SIRALINA with NUAL semantics. If a non-positive circuit is detected, we apply a second pass, which applies SIRALINA but with a UAL semantics.

3) SPE is the proactive strategy, based on shortest paths equations (SPE). If n(n ≥ 1) is the bound on the maximal number of iterations used, we write SPE_n.

A4.1.2. Empirical efficiency measures

For each heuristic of non-positive circuit elimination, for each DDG and for each initiation interval II between MII and L (L is a fixed upper bound on the admissible values for II), we measured the execution time taken by each heuristic (listed above) to minimize the register requirement; we also recorded the number of registers computed by the three methods (UAL, CHECK and SPE). We are going to examine these results in the ...