This is an archive of the discontinued LLVM Phabricator instance.

Distinguish between different forms of "address-taken" MachineBasicBlocks
ClosedPublic

Authored by efriedma on Apr 29 2022, 1:45 PM.

Details

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.

Diff Detail

Event Timeline

efriedma created this revision.Apr 29 2022, 1:45 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 29 2022, 1:45 PM
efriedma requested review of this revision.Apr 29 2022, 1:45 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 29 2022, 1:45 PM
Herald added a subscriber: wdng. · View Herald Transcript
craig.topper added inline comments.Apr 29 2022, 10:53 PM
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 updated this revision to Diff 426258.Apr 30 2022, 5:49 PM

Fix formatting

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.

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 added a comment.EditedMay 6 2022, 10:37 AM

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.

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

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 added inline comments.May 7 2022, 2:52 AM
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 added inline comments.May 8 2022, 7:06 PM
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 added inline comments.May 9 2022, 10:06 AM
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 added inline comments.May 9 2022, 10:33 AM
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 updated this revision to Diff 428177.May 9 2022, 12:55 PM

Add verifier check

efriedma updated this revision to Diff 428194.May 9 2022, 2:00 PM
efriedma marked 3 inline comments as done.

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.

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.

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 this revision to Diff 428535.May 10 2022, 4:58 PM

Updated names according to suggestion from @tentzen

kparzysz accepted this revision.May 13 2022, 2:44 PM
This revision is now accepted and ready to land.May 13 2022, 2:44 PM
arsenm added inline comments.May 16 2022, 2:44 PM
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 marked an inline comment as done.May 16 2022, 3:30 PM
efriedma added inline comments.
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 added inline comments.May 17 2022, 2:08 PM
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 marked an inline comment as done.May 17 2022, 4:39 PM
efriedma added inline comments.
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.

Patuti added a subscriber: Patuti.May 19 2022, 8:41 AM
efriedma added inline comments.May 24 2022, 12:33 PM
llvm/include/llvm/CodeGen/MachineBasicBlock.h
152

@arsenm Ping

bowang added a subscriber: bowang.Jun 23 2022, 12:50 AM
asmith added a subscriber: asmith.Jun 23 2022, 9:10 AM

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

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

arsenm added inline comments.Jun 23 2022, 6:05 PM
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 updated this revision to Diff 439861.Jun 24 2022, 12:44 PM

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

arsenm added inline comments.Jul 20 2022, 2:56 PM
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 added inline comments.Jul 21 2022, 11:20 AM
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.

arsenm accepted this revision.Aug 2 2022, 12:49 PM

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

This revision was landed with ongoing or failed builds.Aug 16 2022, 4:17 PM
This revision was automatically updated to reflect the committed changes.
llvm/test/CodeGen/AArch64/GlobalISel/select-blockaddress.mir