llvm dev - Jan 2009 - [LLVMdev] HazardRecognizer and RegisterAllocation

Hi list,

in our LLVM-based-project we are writing a backend for our processor. The 
architecture is a quite straight-forward RISC, but it does not have 
hardware interlocks, i.e. data hazards involving memory access must be 
resolved by the compiler, either by scheduling unrelated instructions or 
by inserting NOOPs into the load delay slots:

----

For example, code which looks like that:

load 0x1234, reg1
noop
noop
add reg1, 1
load 0x1236, reg2

can be safely transformed to:

load 0x1234, reg1
load 0x1236, reg2
noop
add reg1, 1

----

It pleased us quite a lot when we found the HazardRecognizer-class.
Without much effort we could assist LLVM to transform code like shown
above (with simple (SDUse, delayCount)-map).

Unfortunately we found now out that the HazardRecognizer is used only
before register allocation, and the register allocator obviously may
reschedule instructions, but doesn't take hazard recognition into account.

Is there a switch/option we overlooked to bind the hazardRecognizer to the
register-allocator?

And more generally: Is the hazardRecognizer the right and only way to 
solve our NOOP-minimizing problem?

thanks for your help in advance,
Patrick and Christian

On Jan 19, 2009, at 9:17 AM, Patrick Boettcher wrote:
> Hi list,
>
> in our LLVM-based-project we are writing a backend for our  
> processor. The
> architecture is a quite straight-forward RISC, but it does not have
> hardware interlocks, i.e. data hazards involving memory access must be
> resolved by the compiler, either by scheduling unrelated  
> instructions or
> by inserting NOOPs into the load delay slots:
>
> ----
>
> For example, code which looks like that:
>
> load 0x1234, reg1
> noop
> noop
> add reg1, 1
> load 0x1236, reg2
>
> can be safely transformed to:
>
> load 0x1234, reg1
> load 0x1236, reg2
> noop
> add reg1, 1
>
> ----
>
> It pleased us quite a lot when we found the HazardRecognizer-class.
> Without much effort we could assist LLVM to transform code like shown
> above (with simple (SDUse, delayCount)-map).
>
> Unfortunately we found now out that the HazardRecognizer is used only
> before register allocation, and the register allocator obviously may
> reschedule instructions, but doesn't take hazard recognition into  
> account.
The register allocator doesn't reschedule code. It can coalesce  
copies, commute instructions, and do re-materialization, etc. It's not  
clear what kind of problems you are running it.
>
>
> Is there a switch/option we overlooked to bind the hazardRecognizer  
> to the
> register-allocator?
>
> And more generally: Is the hazardRecognizer the right and only way to
> solve our NOOP-minimizing problem?
Perhaps you want to do this after register allocation is done. Dan is  
developing the post-allocation scheduler. You can try it out.

Evan
>
>
> thanks for your help in advance,
> Patrick and Christian
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Hi Evan,

thanks for your response.

On Mon, 19 Jan 2009, Evan Cheng wrote:
>> For example, code which looks like that:
>>
>> load 0x1234, reg1
>> noop
>> noop
>> add reg1, 1
>> load 0x1236, reg2
>>
>> can be safely transformed to:
>>
>> load 0x1234, reg1
>> load 0x1236, reg2
>> noop
>> add reg1, 1
>>
> The register allocator doesn't reschedule code. It can coalesce
> copies, commute instructions, and do re-materialization, etc.
Sorry for using the wrong vocabulary.
> It's not clear what kind of problems you are running it.
When we limited our target to have only 3 registers available the
code post-hazard-recognized looks like that:

load 0x1234, reg1024
load 0x1236, reg1025
load 0x1238, reg1026
load 0x1240, reg1027
add reg1024, 1
add reg1025, 2
add reg1026, 3
add reg1027, 4

after register allocation:

load 0x1234, reg1
load 0x1236, reg2
load 0x1238, reg3
add reg1, 1
add reg2, 2
add reg3, 3
store reg1, 0x1234
load 0x1240, reg1
add reg1, 4

Which won't work on our platform. It is missing 2 NOOPs after the last 
load. The DelaySlotFiller could add the two NOOPs, but that would be less 
optimal than doing the store-load before the add of reg2 and reg3 (no NOOP 
in that case).
>> And more generally: Is the hazardRecognizer the right and only way to
>> solve our NOOP-minimizing problem?
>
> Perhaps you want to do this after register allocation is done. Dan is
> developing the post-allocation scheduler. You can try it out.
Interesting. Can it already be found SVN? I will search the mail archive 
later, if not.

regards,
Patrick.