Cleanups having to do with fidelity of sets of instructions

[macrologist]

Move defs near to use sites; refactor instrs fidelity

Fidelity calculations used by the compressor and by the fidelity addresser were needlessly constructing logical schedules.

Peeking at the logical schedule fidelity calculations, they too have been cleaned up and refatored for clarity and performance.

[macrologist]

Some of the changes I have made here have to do with removing needless logical schedule construction. The assessment of needlessness was based on looking at the code as it actually is (and determining that extra work was being done), but not necessarily what it was intended to be.

Specifically, all of these fidelity calculations first construct a logical schedule, but then use that schedule to iterate over every instruction, adding up the (log squared) fidelities of each, and then either using that sum or using the (exp -sum) in some kind of comparison. In the calculations as they exist presently, the ordering of operations in a logical schedule doesn't seem to be relevant.

But! maybe they're meant to be. Maybe it was decided that the logical schedule is the place to calculate fidelities b/c there may at some point be a better model of whole-program fidelity calculation that takes into account the logical ordering of operations.

I now have some doubts about the eventual emergence of such a model based on what @ecpeterson mentioned above: that fidelities don't generally compose well.

So, I don't know if this PR should remove the instantiation of logical schedules from the pipeline of instructions -> fidelity score because doing so may or may not be a violation of intended design. @stylewarning

[ecpeterson]

In the calculations as they exist presently, the ordering of operations in a logical schedule doesn't seem to be relevant. ...

Something else to bear in mind is that the addresser has a cross-competing concern about instruction ordering: it wants to make good decisions so that the total resulting schedule has good fidelity, but it also needs to make a decision about what SWAPs to immediately insert, and so it can't get too wistful about instructions down the line. We dealt with this by adding a decay factor to logically-temporally distant instructions, which is fine for this scheduling application but less fine for calculating the total fidelity of a schedule.

I only bring this up to say (1) that there is a place where we jam in ordering info into these values + (2) something like that jamming is unavoidable in greedy-ish scheduling, so it's always going to distort the compiler's internal perspective on these values, and so maybe it isn't so important to come up with a really nice (/ computationally expensive) formula. (Users' external perspectives on these values are another matter! They probably do want meaningful values.)

[macrologist]

Sorry I don't know if I made my concern clear. My question has to do with a very specific case: Several of these fidelity calculations start with a sequence of instructions, build a logical schedule out of them, calculate fidelity, then throw the recently built logical schedule away. In these situations, the logical schedule is only being built so that it can be passed to a fidelity calculation routine. (This is the situation in some of the compressor code as well as a sub-step in the fidelity-addresser code. )

Maybe this is fine if what you want to do is to take into account the ordering of operations in your calculation of fidelity. Right now that is not happening - the actual computation doesn't take order into account. But perhaps one might in the future expect order to be significant - if that is the case, it makes sense to create disposable logical schedules.

I just don't know if there is a meaningful way to think about fidelity on a logical schedule that doesn't also apply to simple sequences of instructions.

[ecpeterson]

I myself think it is fine not to bother calculating these small logical schedules and to use a fairly dumb fidelity estimate which need not rely on logical ordering.

One last comment: Certain Places care foremost about coherence limitations and so only really care about the “longest chain” of instructions. I guess this is comparable to what we’re doing with the temporal strategy? It would be nice to have a similarly clear objective for the “fidelity strategy” if it’s not, in fact, computing fidelities.

[macrologist]

I opted to replace most of the

(exp (- (sqrt (reduce #'+ FIDELITIES :key (lambda (f) (* (log f) (log f))))))) 

calculations with a simpler

(reduce #'min FIDELITIES) 

expression. Both will yield values in the interval (0, 1] when each member of FIDELITIES is also in (0, 1].

The first has the added benefit of getting worse as more "bad" fidelities enter and so is perhaps more reflective of compounding bad-upon-bad. The downside is that more computation is required for empirically uncertain benefit.

Today I have pushed the most recent version of these changes as a kind of indication of life. I am considering what next to do.

Some thoughts that have occurred to me:

• re-refactor to make the (presently excised) construction of logical-schedules significant by considering, perhaps, fidelity on longest paths
• generalize the selection of the fidelity-composition-routine into a PRAGMA for, e.g., compression strategies.
• OR instead of foisting this choice onto users, do the work to produce evidence on the effect of choices to compilation output, and based on those, select one over the other.