llvm dev - Jul 2020 - is a MachineBasicBlock a kind of superblock?

MachineBasicBlock allows for multiple terminators. Unconditional branches
and returns are marked as terminators; the MIPS backend also marks
conditional branches as terminators. The MachineBasicBlock then has a
helper function getFirstTerminator which iterates from the first terminator
to the end of the MBB.

So it seems to me that an MBB is a kind of superblock, single entrance and
multiple side exits. There are also TailDuplication and BranchFolding
passes. While these two are technically not part of the superblock
definition, they are usually part of a superblock implementation because
you want a superblock to be as big as possible.

Of course, you could make a big superblock in the CFG and then tile it down
into basic MBBs. But the only reason that I can think of for that would be
codegen simplicity and with GlobalISel, I would think that would no longer
be the case.

Anyways, am I getting this right? If so, is there any way to control the
creation of these superblocks, that is, which basic blocks from the CFG go
into a given MBB?

I'm still in the MC layer, so I really don't know where in the MI layer
this sort of tiling of the CFG is done. (In a full blown superblock
formation that tiling would be a profile driven decision for finding the
hot trace.)

It's always good to just look at things. So I want to just display some
MBBs for some code for some backend at preEmit and just look at what they
look like. Any suggestions for that will be appreciated.

thanks,

Chris

BTW, this is at the MI-MC interface. The IR BasicBlock is a completely
different issue.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200711/44c1b258/attachment.html>

Hi, Chris,

As I think about it, no, MBBs are not superblocks. The important part here is
that semantically, while we may need multiple instructions at the end of the
block in order to encode the branches to the various successors, we don't
have other code in between these various terminators. There's an ordering:
PHIs, then other things, then terminators. Regarding tail duplication, etc. the
thing to realize is that, past a certain point in the pipeline, the blocks'
layout order is significant and blocks have implicit fallthrough branches. We
still maintain separate blocks, however.

 -Hal

Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

________________________________
From: llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of Chris
Sears via llvm-dev <llvm-dev at lists.llvm.org>
Sent: Saturday, July 11, 2020 1:41 PM
To: llvm-dev at lists.llvm.org <llvm-dev at lists.llvm.org>
Subject: [llvm-dev] is a MachineBasicBlock a kind of superblock?

MachineBasicBlock allows for multiple terminators. Unconditional branches and
returns are marked as terminators; the MIPS backend also marks conditional
branches as terminators. The MachineBasicBlock then has a helper function
getFirstTerminator which iterates from the first terminator to the end of the
MBB.

So it seems to me that an MBB is a kind of superblock, single entrance and
multiple side exits. There are also TailDuplication and BranchFolding passes.
While these two are technically not part of the superblock definition, they are
usually part of a superblock implementation because you want a superblock to be
as big as possible.

Of course, you could make a big superblock in the CFG and then tile it down into
basic MBBs. But the only reason that I can think of for that would be codegen
simplicity and with GlobalISel, I would think that would no longer be the case.

Anyways, am I getting this right? If so, is there any way to control the
creation of these superblocks, that is, which basic blocks from the CFG go into
a given MBB?

I'm still in the MC layer, so I really don't know where in the MI layer
this sort of tiling of the CFG is done. (In a full blown superblock formation
that tiling would be a profile driven decision for finding the hot trace.)

It's always good to just look at things. So I want to just display some MBBs
for some code for some backend at preEmit and just look at what they look like.
Any suggestions for that will be appreciated.

thanks,

Chris

BTW, this is at the MI-MC interface. The IR BasicBlock is a completely different
issue.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200711/eb6fd1ca/attachment.html>

Thanks Hal,

Ok, I think I get this now and so it makes sense that getFirstTerminal()
iterates from the terminal to the end. Also, I found a quote from Chris
Lattner on the dev list:

    This informs the code generator that any spill code has to go above the
instructions

Target.td says, somewhat tautologically:

    bit isTerminator = 0; // Is this part of the terminator for a basic
block?

Maybe that can be replaced with Chris Lattner's explanation.

C
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200711/7d0a9f30/attachment.html>

MBBs aren't superblocks, they generally represent a single IR block. The
MBB representation allowance for multiple terminators is so that a two-way
conditional branch can be emitted. There, you generally need two
instructions: a conditional branch, followed by an unconditional branch.

There is also allowance for control flow out of the middle of the
MachineBasicBlock, in a couple of limited circumstances: a CALL instruction
may throw to an EHPad successor (lowered from the "invoke" IR
instruction),
and an INLINEASM_BR instruction (lowered from an IR "callbr"
instruction)
may jump to one of its indirect successors. In both of those cases, the
instruction which was a terminator at the IR level, is not at the
MachineInstruction level. As the IR block is lowered to a MBB, the IR
terminator is the last "logical" thing that happens in the MBB, but
e.g.
the CALL instruction is not the literal end of the block. All of the return
handling for the call sequence (e.g. tearing down the stack frame, copying
registers, loading values, etc) all happens in the same basic block as the
CALL, despite that the CALL may in fact throw out to an exception-handling
basic-block, rather than continue the rest of its block. Similarly for
INLINEASM_BR.

If you want to get a concept of what's going on internally, the
"-print-after-all" flag to llc (or -mllvm -print-after-all in clang)
is a
great way to see the transformation of the code as it goes through every
pass, from the high-level IR transformations, down to the final assembly.



On Sat, Jul 11, 2020 at 2:41 PM Chris Sears via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> MachineBasicBlock allows for multiple terminators. Unconditional branches
> and returns are marked as terminators; the MIPS backend also marks
> conditional branches as terminators. The MachineBasicBlock then has a
> helper function getFirstTerminator which iterates from the first terminator
> to the end of the MBB.
>
> So it seems to me that an MBB is a kind of superblock, single entrance and
> multiple side exits. There are also TailDuplication and BranchFolding
> passes. While these two are technically not part of the superblock
> definition, they are usually part of a superblock implementation because
> you want a superblock to be as big as possible.
>
> Of course, you could make a big superblock in the CFG and then tile it
> down into basic MBBs. But the only reason that I can think of for that
> would be codegen simplicity and with GlobalISel, I would think that would
> no longer be the case.
>
> Anyways, am I getting this right? If so, is there any way to control the
> creation of these superblocks, that is, which basic blocks from the CFG
> go into a given MBB?
>
> I'm still in the MC layer, so I really don't know where in the MI
layer
> this sort of tiling of the CFG is done. (In a full blown superblock
> formation that tiling would be a profile driven decision for finding the
> hot trace.)
>
> It's always good to just look at things. So I want to just display some
> MBBs for some code for some backend at preEmit and just look at what they
> look like. Any suggestions for that will be appreciated.
>
> thanks,
>
> Chris
>
> BTW, this is at the MI-MC interface. The IR BasicBlock is a completely
> different issue.
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200711/615ecede/attachment.html>