[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.


Hi Arnaud,

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


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 J) — 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.



0002-PBQP-Do-not-add-and-edge-between-nodes-with-totally-.patch (1.99 KB)