llvm dev - Feb 2015 - [LLVMdev] [PBQP] Are edges between nodes from totally disjoint register classes necessary ?

Hi Lang,

 

While working on improving the debug dumps of the PBQP graphs, I found out
that we can have some edges between nodes which belong to totally disjoint
register classes (for example, on AArch64, this would be an int and a
floating point register). Although it is true those 2 registers interferes,
in the sense they are alive at the same time, they never have any physical
interference, and this shows up as a zero matrix.

 

I was wondering if it could make sense to skip adding such edges to the
graph, as they do not add useful information, they increases the nodes
degrees . and ultimately make the allocation take longer time.

 

I have a patch ready prototyping this. It unfortunately breaks with the last
fix you made (@ r227942), but if I revert it, it just works fine. if you
believe this could be worth it, then I will investigate where the failure
comes from.

 

Cheers,

--

Arnaud A. de Grandmaison

 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150204/81de0a94/attachment.html>

Hi Arnaud,

That sounds good to me. If you send me the patch I'd like to have a look
too.

Cheers,
Lang.


On Tue, Feb 3, 2015 at 4:06 PM, Arnaud A. de Grandmaison <
arnaud.degrandmaison at arm.com> wrote:
> Hi Lang,
>
>
>
> While working on improving the debug dumps of the PBQP graphs, I found out
> that we can have some edges between nodes which belong to totally disjoint
> register classes (for example, on AArch64, this would be an int and a
> floating point register). Although it is true those 2 registers interferes,
> in the sense they are alive at the same time, they never have any physical
> interference, and this shows up as a zero matrix.
>
>
>
> I was wondering if it could make sense to skip adding such edges to the
> graph, as they do not add useful information, they increases the nodes
> degrees … and ultimately make the allocation take longer time.
>
>
>
> I have a patch ready prototyping this. It unfortunately breaks with the
> last fix you made (@ r227942), but if I revert it, it just works fine. if
> you believe this could be worth it, then I will investigate where the
> failure comes from.
>
>
>
> Cheers,
>
> --
>
> Arnaud A. de Grandmaison
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150203/f8570109/attachment.html>

So here is the patch. For now, my computing of the register class intersection
assumes register classes are either disjoint, or nicely nested; I will have to
modify it to support weird architecture, where you can have overlapping register
classes. I am thinking of doing that by modifying createInterferenceEdge to
detect when a zero matrix would be added, cache the empty-intersection result
between the register classes (and not add the edge ☺) --- unless there is an
easier way to compute if 2 register classes are disjoint.

The failing regression test (when you apply my patch) is in-tree:
test/CodeGen/AArch64/PBQP-csr.ll. It fails the machine instr verification step.
Reverting your fix (r227942) is enough to make it pass.

Cheers,
Arnaud

From: Lang Hames [mailto:lhames at gmail.com]
Sent: 04 February 2015 00:33
To: Arnaud De Grandmaison
Cc: LLVM Developers Mailing List
Subject: Re: [PBQP] Are edges between nodes from totally disjoint register
classes necessary ?

Hi Arnaud,

That sounds good to me. If you send me the patch I'd like to have a look
too.

Cheers,
Lang.


On Tue, Feb 3, 2015 at 4:06 PM, Arnaud A. de Grandmaison
<arnaud.degrandmaison at arm.com<mailto:arnaud.degrandmaison at
arm.com>> wrote:
Hi Lang,

While working on improving the debug dumps of the PBQP graphs, I found out that
we can have some edges between nodes which belong to totally disjoint register
classes (for example, on AArch64, this would be an int and a floating point
register). Although it is true those 2 registers interferes, in the sense they
are alive at the same time, they never have any physical interference, and this
shows up as a zero matrix.

I was wondering if it could make sense to skip adding such edges to the graph,
as they do not add useful information, they increases the nodes degrees … and
ultimately make the allocation take longer time.

I have a patch ready prototyping this. It unfortunately breaks with the last fix
you made (@ r227942), but if I revert it, it just works fine. if you believe
this could be worth it, then I will investigate where the failure comes from.

Cheers,
--
Arnaud A. de Grandmaison



-- IMPORTANT NOTICE: The contents of this email and any attachments are
confidential and may also be privileged. If you are not the intended recipient,
please notify the sender immediately and do not disclose the contents to any
other person, use it for any purpose, or store or copy the information in any
medium. Thank you.

ARM Limited, Registered office 110 Fulbourn Road, Cambridge CB1 9NJ, Registered
in England & Wales, Company No: 2557590
ARM Holdings plc, Registered office 110 Fulbourn Road, Cambridge CB1 9NJ,
Registered in England & Wales, Company No: 2548782
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150204/6b229dba/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0002-PBQP-Do-not-add-and-edge-between-nodes-with-totally-.patch
Type: application/octet-stream
Size: 2036 bytes
Desc: 0002-PBQP-Do-not-add-and-edge-between-nodes-with-totally-.patch
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150204/6b229dba/attachment.obj>