What's the basic block layout algorithm ?

[eric...@arm.com]

Hi,

I was looking at the layout pass recently, but I didn't find any documents about it. I would like to ask what algorithm is used for this pass? There is not much code for this pass, but if there is some documentation, it will be more convenient to understand it.

The layout pass has something to do with register allocation. I know that register allocation uses linear scan algorithm. If anyone could tell me a document, presentation or blog describing its implementation, I would be very grateful.

Thanks

Eric

[Keith Randall]

It's not a fancy algorithm. It tries to layout blocks connected by high-likelihood edges together. It also tries to keep panic paths at the end.

I don't know of any documentation for it, other than the code.

There's nothing particularly important in the layout pass to help with register allocation. It helps a linear-scan allocator to have blocks connected by high-likelihood edges be adjacent. But that layout is independently useful to avoid branch instructions, and non-linear-scan allocators probably like that layout also.

[eric...@arm.com]

Thanks Keith, then I will just read the code directly. Fortunately, the code does not seem to be a lot. I think branch is a bit too much in some cases, such as the math.IsInf function, so I want to see if I can optimize it somewhere.