Basecase assembly optimisation project

[Ondřej Bílka]

On Wed, Oct 02, 2013 at 07:14:24PM +0200, Torbjorn Granlund wrote:
>   
> It sounds a lot like David Harvey's and my tool, which we call the
> "loopmixer".  We never wrote it neatly enough for public release, but
> we've used it for the last 4 years or so for tweaking the assembly code
> of GMP.  (There is a slightly cryptic message in many asm files in GMP
> about this.)
> 
> We don't handle alternatives currently, except with a loop around the
> loopmixer.  One could think of several classes, some known to the tool,
> others not-always-valid only by source file annotation.  Examples of the
> former would be "xor rax,rax" vs "xor eax,eax" and "mov reg,reg" vs lea
> (reg),reg.
>
This is possible but I prefer to create them by separate program,
most interesting transformations are one-way like
bsf %eax, %eax => bsf %rax, %rax

Another aspect is that variants change size which could help with
alignments.
 
> For x86-64, CPUs are affected more or less by which register is used,
> which could be understood by the tool.  (E.g., rbp and r13 lack he
> shorter 0-offset address for; rsp and r12 require an extra 0x24 when
> used as base ptrs; r8-r15 require REX prefix.)
> 
> Taking all this into account might through us out in the land of
> combinatorial explosion.
> 
It is possible enchancement, but I am not yet at stage of calculating
register dependencies on jumps.

If I knew input/output/free registers then register renaming inside
basic block is relatively straigthforward. As I already use heuristic
algorithms adding these would not be problem. 


> Keeping software pipeline depth down would also be useful.  Our tool
> doesn't understand that.  When one give instruction choices, manual
> preferences and automatic preferences would be useful.  Automatic
> preferences could be to use a short insn, manual could be to prefer mov
> over lea to make code more readable.  (Not that mov is much more
> readable, but to avoid a random mix of he two in similar contexts.)
> 
> -- 
> Torbjörn