Work Package 1
Revision as of 17:00, 1 August 2014 by James
- Identify code that can be superoptimized (for speed, size or energy) focussing on finding awkward constructs.
- Use rapid prototyping to evaluate key algorithms. Consider novel constructive techniques as well as exploring existing approaches.
- Possibly not too difficult if only considering a single basic block
- Memory liveness needs to be taken into account (To discuss next week)
- Skip instructions
- Possibly difficult to encode. Consider as seperate basic blocks for now?
- Naively modelling flags results in a large number of constraints
- However, the constraints should fall naturally out of the bitvector arithmetic in most cases.
- Increase in constraint-generator complexity for reduction in final constraint complexity (which should reduce superoptimization time)
- Few instructions that use the flags (except branches), so maybe low effectiveness in superoptimization
How can we handle larger basic blocks?
- Hopefully be able to generate instruction sequences up to length 10 (maybe 15).
- The set of instructions used for superoptimization should be restricted (conservatively).
- E.g. if the sequence does not load or store memory, then perhaps we do not need the memory instructions
- Some basic blocks are larger, however we may be able to split the basic block
- Consider the dataflow DAG, cyclomatic complexity. Can the DAG be partitioned (possibly make a cut which cuts the shortest amount of edges – where, how, how many?)
- The edges represent the live registers/flags. The search can be restricted based on liveness information