Hi,

[actual question is in the last paragraph of this post]

I recently stumbled over an old (closed) bug in the bug tracker where the solution was to remove ASMCSE from O3, this bug report was later referred to as "the final drop in the bucket" to not longer have this optimization enabled by default.

I have googled the mailing lists and searched the bug tracker but I could not find much discussion about this topic, the few postings I found suggested that the consensus seems to be that this particular optimizer has become totally unmaintainable and after reading this I fear that it will eventually be removed completely. IMHO this would be a big loss.

I have some code that when enabling -OoASMCSE will run 20..30% faster. I tried to reproduce it with a smaller demo program (attached proect1.lpr), the effect only becomes visible when using much more local variables than there are registers. The attached program does not do anything useful, its only purpose is to provoke a lot of redundant register reloading. The loop looks like this:

  for I := 0 to ITER do begin
    // use much more local variables than there are registers
    J := I and $0F;
    K := (I+1) and $0F;
    L := (I+2) and $0F;
    M := J xor $0F;
    N := K xor $0F;
    O := L xor $0F;
    // and now provoke a lot of redundant register reloads
    U := A[J] or A[K] or A[L] or A[M];
    V := B[K] or B[L] or B[M] or B[N];
    W := C[L] or C[M] or C[N] or C[O];
  end;

U,V,W and the arrays are QWords, (and I am using it on i386) this is because my real world application also does a lot of bitwise operations on QWords that are all looked up in different arrays and some of the functions are quite long and have expressions even more complicated than above (where the array indices themselves are looked up in other arrays).

The above code (just one line of it) without ASMCSE would compile like this:

    U := A[J] or A[K] or A[L] or A[M];

0x80480f8 mov eax,DWORD PTR [ebp-0x3c] // <------- could have used edi instead...
0x80480fb mov esi,DWORD PTR [eax*8+0x80e2ca0]
0x8048102 mov edi,DWORD PTR [ebp-0x3c] // <------- ...then this would be redundant!
0x8048105 mov eax,DWORD PTR [edi*8+0x80e2ca4]
0x804810c mov edi,DWORD PTR [ebp-0x38]
0x804810f or esi,DWORD PTR [edi*8+0x80e2ca0]
0x8048116 mov edi,DWORD PTR [ebp-0x38] // <------- redundant! 0x8048119 or eax,DWORD PTR [edi*8+0x80e2ca4]
0x8048120 mov edi,DWORD PTR [ebp-0x34]
0x8048123 or esi,DWORD PTR [edi*8+0x80e2ca0]
0x804812a mov edi,DWORD PTR [ebp-0x34] // <------- redundant! 0x804812d or eax,DWORD PTR [edi*8+0x80e2ca4]
0x8048134 mov edi,DWORD PTR [ebp-0x30]
0x8048137 or esi,DWORD PTR [edi*8+0x80e2ca0]
0x804813e mov edi,DWORD PTR [ebp-0x30] // <------- redundant! 0x8048141 or eax,DWORD PTR [edi*8+0x80e2ca4]
0x8048148 mov DWORD PTR [ebp-0x24],esi
0x804814b mov DWORD PTR [ebp-0x20],eax

same code with ASMCSE:

    U := A[J] or A[K] or A[L] or A[M];

0x80482c8 mov eax,DWORD PTR [ebp-0x3c]
0x80482cb mov esi,DWORD PTR [eax*8+0x80e2ca0]
0x80482d2 mov edi,DWORD PTR [eax*8+0x80e2ca4]
0x80482d9 mov eax,DWORD PTR [ebp-0x38]
0x80482dc or esi,DWORD PTR [eax*8+0x80e2ca0]
0x80482e3 or edi,DWORD PTR [eax*8+0x80e2ca4]
0x80482ea mov eax,DWORD PTR [ebp-0x34]
0x80482ed or esi,DWORD PTR [eax*8+0x80e2ca0]
0x80482f4 or edi,DWORD PTR [eax*8+0x80e2ca4]
0x80482fb mov eax,DWORD PTR [ebp-0x30]
0x80482fe or esi,DWORD PTR [eax*8+0x80e2ca0]
0x8048305 or edi,DWORD PTR [eax*8+0x80e2ca4]
0x804830c mov DWORD PTR [ebp-0x24],esi
0x804830f mov DWORD PTR [ebp-0x20],edi

The difference in execution time is extreme (see the attached program): $ ./test
3682
2813

This is milliseconds for the above code 100 millions of times, first is without, second with asmcse. Without ASMCSE the attached program takes 30% more time! CPU is one of these old Pentium-M, 1300MHz that were built into the legendary ThinkPad T40.

My question is now: Will ASMCSE eventually be completely removed? And if this happens, will there be a replacement? IMHO this optimization is really needed. Is it really so difficult to make an optimizer that simply (is it simple?) eliminates these redundant register reloads without being overly complicated and unmaintainable? The last question is only because I don't yet know how the code generation and optimization of FPC even works, I wouldn't even know where to start looking for it in the compiler sources.

Bernd

Bernd wrote

My question is now: Will ASMCSE eventually be completely removed?

Probably, yes.

And if this happens, will there be a replacement?

As far as I'm concerned: an LLVM backend (although that's sort of independent of when/whether the ASMCSE optimizer will be removed, because there will probably never be an LLVM port that can e.g. target go32v2, but that in itself won't stop the removal of the ASMCSE optimizer).

IMHO this optimization is really needed. Is it really so difficult to make an optimizer that simply (is it simple?) eliminates these redundant register reloads without being overly complicated and unmaintainable?

It's undoubtedly possible to implement this in a way that is much less complex, much easier and much simpler than the current ASMCSE implementation (although I don't think it will ever be really simple, because machine code was never designed to be easily analysable). Apart from being the first somewhat complex code that I ever wrote (it was started 14.5 years ago!) and organically grown over the years, it also does much more than removing simple loads (it can remove entire subsequences and perform register renaming).

But such a new implementation would require time, and I'm not aware of anyone willing to invest that time.

he last question is only because I don't yet know how the code generation and optimization of FPC even works, I wouldn't even know where to start looking for it in the compiler sources.

* compiler/i386/daopt386.pas: data flow analysis (DFA, collects information about what each register holds)
* compiler/i386/csopt386.pas: common subexpression elimination based on information collected by DFA
* compiler/i386/rropt386.pas: register renaming based on the information collected by DFA

Jonas

2011/12/31 Jonas Maebe :

* compiler/i386/daopt386.pas: data flow analysis (DFA, collects information about what each register holds) * compiler/i386/csopt386.pas: common subexpression elimination based on information collected by DFA * compiler/i386/rropt386.pas: register renaming based on the information collected by DFA

Ok, this is a lot of code.
I have removed it all ;-)

I'm now playing around with this, trying to understand how the data looks like. I have replaced the original CSE() function with the following:

function RemoveReload(asml: TAsmList; first, last: tai; pass: longint): boolean;
var
  p : taicpu;
begin
  if pass > 0 then exit;
  writeln;
  writeln('block:');
  p := taicpu(first);
  repeat
    case p.typ of
      ait_label:
      begin
        writeln('label');
      end;
      ait_instruction:
      begin
        writeln(p.GetString);
      end;
    end;
    if p  last then
      p := taicpu(p.Next);
  until p = last;
  Result := False;
end;

This does nothing (I hope), only print something to the console:

Compiling i386/testus.pas

block:
label
[sub ???,???]
label
[mov ???,???]
[mov ???,???]
[mov ???,???]
[mov ???,???]
[dec ???]
label
[inc ???]
[movsx ???,???]
[mov ???,???]
[sar ???,???]
[mov ???,???]
[mov ???,???]
[movsx ???,???]
[mov ???,???]
[sar ???,???]
[mov ???,???]
[mov ???,???]
[mov ???,???]
[mov ???,???]
[add ???,???]
[adc ???,???]
[mov ???,???]
[mov ???,???]
label
[cmp ???,???]
[j ???]
label
label
[mov ???,???]
[mov ???,???]
[mov ???,???]
[add ???,???]
[ret]

This looks good already ;-) I can even recognize my short test program (the for loop, the qword addition) even with all the question marks. This leads me to the first question: why are there question marks? Is it not yet known which registers will be used at this stage of compilation or am I just using the wrong method to dump it to the console?

I have the following simple algorithm in mind:
start at the beginning of the block, one instruction after the other, maintain a list of instructions, its empty at the beginning.

repeat
* if i come across a mov instruction and the exact same instruction is in my list
already then remove it from the code.

* if there comes a label then clear the list

* if an instruction changes something (register or memory) that any of the instructions in my list depend upon then remove the affected instruction from the list.

next instruction
until end of block

Would something like this work already?

Now I need to find out the following things or how do I get them out of the properties of the taicpu class:
* which registers does an instruction write to (if any)
* which memory does it write to (if any)
* which registers does it read from
* which memory does it read from

and:
how can I for debugging purposes dump the instructions to the console, so that its easier for me so see what I have, are there any helper functions?

more questions certainly to come...

Bernd

Basically yes.

Well, this is what most of the code in daopt386 already provides.

I use typically -al to debug assembler generation

This seems to work:

http://pastebin.com/E3LYfJCx (used with 2.6.0)

Is this how it should look like or am I doing something completely stupid or did I forget something important? With this code (as a replacement for asmcse) the compiler would pass the complete bootstrap cycles without errors and it is removing quite a lot redundant mov instructions.

BTW: wouldn't it be possible to make it not generate this redundant code in the first place or would this again be some kind of impossible / overly complicated thing?

It seems to me the code is not really meant for performing complicated analysis and operations on the generated assembly code, even the simplest things like comparing two instructions or getting a list of input and output registers seems so incredibly cumbersome, or is this only my impression because I am not very familiar with this kind of things?

Bernd

At first sight, one important thing you forgot is that a single memory location can be aliased by multiple pointers. Simply checking whether the base register and offsets match is not enough to determine whether a write invalidates register contents, since a write via a pointer could overwrite any other memory location.

BTW: wouldn't it be possible to make it not generate this redundant code in the first place or would this again be some kind of impossible / overly complicated thing?

A better register allocator undoubtedly result in less spilling code (by e.g. performing live range splitting).

Originally it was probably about as simple as your code. Afterwards, much more functionality was added beyond removing single loads.

Jonas

2012/1/2 Jonas Maebe :

At first sight, one important thing you forgot is that a single memory location can be aliased by multiple pointers. Simply checking whether the base register and offsets match is not enough

I have not yet found out how to accomplish this. Wouldn't I need to also know which values the registers would contain at runtime to make this fool-proof? Is this even possible?

To minimized this danger i only considered mov reg, [ofs+reg] (and nothing else and nothing with index register) and I also compare only the offsets and everything with the same offset is immediately considered "suspicious" (and therefore invalidated), no matter which base register is used.

(I haven't yet understood the original asmcse implementation, not even partially, it looks incredibly complicated to me, it will immediately induce a coma-like trance whenever I try to read through it)

2012/1/2 Bernd :

(I haven't yet understood the original asmcse implementation, not even partially, it looks incredibly complicated to me, it will immediately induce a coma-like trance whenever I try to read through it)

This wasn't meant as a criticism of the code, it was rather meant to illustrate my own inability to understand it. It is simply causing some kind of mental stack overflow, causing my thought processes to crash and freeze. I have difficulties understanding how it works.