Distinguish between different forms of "address-taken" MachineBasicBlocks

[efriedma]

Summary

There are two different senses in which a block can be "address-taken". There can be a BlockAddress involved, which means we need to map the IR-level value to some specific block of machine code. Or there can be constructs inside a function which involve using the address of a basic block to implement certain kinds of control flow.

Mixing these together causes a problem: if target-specific passes are marking random blocks "address-taken", if we have a BlockAddress, we can't actually tell which MachineBasicBlock corresponds to the BlockAddress.

So split this into two separate bits: one for BlockAddress, and one for the machine-specific bits. And try to clarify when, exactly, it's appropriate to use the new setMBBLabelUsed().

Discovered while trying to sort out related stuff on D102817.

[craig.topper]

llvm/include/llvm/CodeGen/MachineBasicBlock.h

272

Did clang-format format this differently than setMBBLabelUsed()? It's not over 80 columns on one line is it?

[efriedma]

Fix formatting

[kparzysz]

The IR spec states that the value of blockaddress can only be used in an indirect branch/call, or in a comparison against null. The latter seems to fall under the "address materialized somewhere" that you mention in the referenced review. Is the motivation behind BlockAddressTarget to identify blocks that are targets of indirect branches? Otherwise, it's not clear to me why blockaddress(bb) == null is any different from storing the address of bb in an exception table, for example.

[efriedma]

The problem that I spotted that led me to actually submitting this patch is the use of hasAddressTaken() in AsmPrinter::emitBasicBlockStart. It's ambiguous: in general, there could be mulitple "address-taken" MachineBasicBlocks that map to a given BasicBlock. (Maybe there's some other way to disambiguate, but this seems like the simplest.)

There are other reasons it might make sense to have this separation, anyway: we have robust support for "orphaned" blockaddresses (which don't actually map to any MachineBasicBlock), but for target-specific uses of setHasAddressTaken(), we probably end up with a use-after-free. So some places in the code generator might want to check for a "target-specific" address-taken, but not uses of blockaddress.

[kparzysz]

I'm not questioning the splitting, I'm just wondering if the terminology could be more self-explanatory. In AsmPrinter there is a check that an address-taken block must actually be present, but that's a hard requirement really only when there is a branch to it. So I was thinking that maybe "isIndirectBranchTarget" could be a better name, but I wasn't sure if it captured the intent.

[efriedma]

The way things currently work, the significant thing is whether the block is actually referred to by a blockaddress constant. isel doesn't actually check whether the block is the target of an indirectbr. So the naming reflects the current behavior; we treat the block as "address-taken" based on whether there's a blockaddress.

Given the LangRef rules, blocks that have an blockaddress pointing at them are generally also the target of an indirectbr, but we don't actually enforce that anywhere.

The LangRef rule is written the way it is to avoid promising anything about the way blockaddress constants are lowered. For example, if a block is unreachable, we can replace the associated blockaddress constant with a constant "1". Or on some targets like wasm, we convert indirectbrs to switches because we can't jump to arbitrary addresses. (We could implement an optimization to explicitly eliminate blockaddresses that refer to blocks that don't have an indirectbr predecessor... but it's not really important, so nobody has.)

[tentzen]

How about AddressTaken_Internal and AddressTaken_External?

the _Internal is used for blockAddress-constant, jump table, etc where it's targeted by IR internal user code domain.
the latter indicates that the address is taken and can be targeted externally by Runtime (EH case), OS or even HW (like the retpoline case).

Or AddressTaken_User and AddressTaken_System that refer to user mode and system mode.

[arsenm]

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

3552–3557

I don't like this hard requirement on the IR. CodeGen passes should try to avoid depending on the block being present (In particular llvm-reduce is now stripping out IR block references).

llvm/test/tools/llvm-reduce/mir/preserve-block-info.mir

11

Probably should add another case and check for the second flavor

[efriedma]

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

3552–3557

I'm not sure what alternative you're suggesting here. There's a contract based on the BasicBlock: we emit a symbol here, and uses of the BlockAddress constant refer to it. To emit the correct symbol we need the BasicBlock. If we skip emitting the symbol here, we miscompile.

[arsenm]

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

3552–3557

This needs to do something to handle the null block. Can it emit an __unnamed symbol or something like for anonymous functions? If this is going to assert on null the verifier at least has to check it

[efriedma]

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

3552–3557

If we're not concerned about emitting code that actually works, we can skip emitting the symbol. The blockaddress will point to the end of the function.

I think I'd prefer to have a verifier check; I'll look into adding that.

[efriedma]

Add verifier check

[efriedma]

Make the verifier check more strict, to match the asmprinter.

Alternatively, I guess we could drop both of the hasAddressTaken() assertions in AsmPrinter, but ensuring people don't use the wrong APIs seems more important than the resulting consequences for testcase reduction.

[efriedma]

In D124697#3498401, @tentzen wrote:

How about AddressTaken_Internal and AddressTaken_External?

the _Internal is used for blockAddress-constant, jump table, etc where it's targeted by IR internal user code domain.
the latter indicates that the address is taken and can be targeted externally by Runtime (EH case), OS or even HW (like the retpoline case).

Or AddressTaken_User and AddressTaken_System that refer to user mode and system mode.

This isn't really the distinction I'm trying making here. The distinction here is between LLVM IR uses of blockaddress (for indirectbr), and MachineFunction uses of MachineBasicBlock labels (for retpoline etc.). Jump tables would fall into the latter category, except that we have explicit code to update jump tables in the places where it would matter.

[tentzen]

This isn't really the distinction I'm trying making here. The distinction here is between LLVM IR uses of blockaddress (for indirectbr), and MachineFunction uses of MachineBasicBlock labels (for retpoline etc.). Jump tables would fall into the latter category, except that we have explicit code to update jump tables in the places where it would matter.

OK. How about IRBlockAddressTaken and MachineBlockAddressTaken. I think having "AddressTaken" explicitly spelled out here can avoid future confusions.

[efriedma]

Updated names according to suggestion from @tentzen

[arsenm]

llvm/include/llvm/CodeGen/MachineBasicBlock.h

152

If you're going to depend on the underlying IR block, you don't really need another field inside MachineBasicBlock. You can just query directly from the IR

[efriedma]

llvm/include/llvm/CodeGen/MachineBasicBlock.h

152

In general, there are multiple MachineBasicBlocks which correspond to a single IR BasicBlock; when we split a block for whatever reason, getBasicBlock() is the same for both halves. We need to know which one is the jump destination.

[arsenm]

llvm/include/llvm/CodeGen/MachineBasicBlock.h

152

Does it actually make sense to preserve the IR block if the block is split? Is the IR block used for anything else? Maybe for block splitting the second half of the block shouldn't have the IR link

[efriedma]

llvm/include/llvm/CodeGen/MachineBasicBlock.h

152

It might be possible to mess with the value stored as getBasicBlock(); as far as I can tell, the result is mostly used for debug prints and as an argument to CreateMachineBasicBlock(). It is used for a few other (possibly dubious) things: to get MD_loop/MD_make_implicit metadata, to get debug locations, to get the LandingPadInst for a landing pad. Nothing we couldn't handle some other way, I think.

If we want to go in that direction, though, I might as well just replace bool IRBlockAddressTaken with BasicBlock *IRBlockAddress", and avoid the dependency on getBasicBlock() altogether.

[efriedma]

llvm/include/llvm/CodeGen/MachineBasicBlock.h

152

@arsenm Ping

[asmith]

@arsenm @efriedma we'll update the SEH patch with this change if it's ready?

[efriedma]

I was hoping to hear back from @arsenm about the review comment, but I think this is ready otherwise.

[arsenm]

llvm/include/llvm/CodeGen/MachineBasicBlock.h

152

Right, that's what I was suggesting. Just go through the IR block. I suspect the IR block is misleading in the split case anyway

[efriedma]

For ir-block-address-taken basic blocks, don't depend on MachineBasicBlock::getBasicBlock(); store the corresponding BasicBlock separately. This ensures it stays isolated from any future cleanups related to getBasicBlock(). (The MIR ir-block-address-taken now takes a basic block argument.)

[efriedma]

@arsenm Ping

[arsenm]

llvm/include/llvm/CodeGen/MachineBasicBlock.h

152

I meant go from the underlying IR block that's already there, not introduce a second reference. Blocks split from the end of of the block would not have an IR block reference

[efriedma]

llvm/include/llvm/CodeGen/MachineBasicBlock.h

152

Directly hacking at getBasicBlock() would be basically impossible to land in a single patch. There are a bunch of places that use getBasicBlock(); we'd need to ensure that every existing use of getBasicBlock() doesn't depend on the existing splitting behavior. We'd need to land a patch similar to this, then audit/modify various users of getBasicBlock(), then hack at the code that creates MBBs.

I agree that the concept of the "corresponding IR block" is a bit fuzzy for a random basic block once you've started to run MachineFunction optimizations. But I'm not sure changing the rule for splitting BBs is helpful; we do a bunch of work to change the rules, and the result is that it's still fuzzy. I mean, knowing the BB tied to the initial MBB is useful specifically if you want some IR element tied to the beginning of the block, like a blockaddress or landingpad. But not so useful if you want to query the terminator the IR block used, like some other places do.

[efriedma]

@arsenm ping

[efriedma]

@arsenm ping

[arsenm]

LGTM. I agree it's more work to drop the second block but would leave less clutter