Page MenuHomePhabricator

[IR] CallBrInst: scan+update arg list when indirect dest list changes
ClosedPublic

Authored by nickdesaulniers on Sep 5 2019, 6:22 PM.

Details

Summary

There's an unspoken invariant of callbr that the list of BlockAddress
Constants in the "function args" list match the BasicBlocks in the
"other labels" list. (This invariant is being added to the LangRef in
https://reviews.llvm.org/D67196).

When modifying the any of the indirect destinations of a callbr
instruction (possible jump targets), we need to update the function
arguments if the argument is a BlockAddress whose BasicBlock refers to
the indirect destination BasicBlock being replaced. Otherwise, many
transforms that modify successors will end up violating that invariant.
A recent change to the arm64 Linux kernel exposed this bug, which
prevents the kernel from booting.

I considered maintaining a mapping from indirect destination BasicBlock
to argument operand BlockAddress, but this ends up being a one to
potentially many (though usually one) mapping. Also, the list of
arguments to a function (or more typically inline assembly) ends up
being less than 10. The implementation is significantly simpler to just
rescan the full list of arguments. Because of the one to potentially
many relationship, the full arg list must be scanned (we can't stop at
the first instance).

Thanks to the following folks that reported the issue and helped debug
it:

  • Nathan Chancellor
  • Will Deacon
  • Andrew Murray
  • Craig Topper

Link: https://bugs.llvm.org/show_bug.cgi?id=43222
Link: https://github.com/ClangBuiltLinux/linux/issues/649
Link: https://lists.infradead.org/pipermail/linux-arm-kernel/2019-September/678330.html

Diff Detail

Repository
rL LLVM

Event Timeline

nickdesaulniers created this revision.Sep 5 2019, 6:22 PM
craig.topper added inline comments.Sep 6 2019, 9:55 AM
llvm/include/llvm/IR/Instructions.h
4085 ↗(On Diff #219020)

Why is this change needed?

llvm/lib/IR/Instructions.cpp
827 ↗(On Diff #219020)

When would this fail?

nickdesaulniers marked 2 inline comments as done.Sep 6 2019, 10:13 AM
nickdesaulniers added inline comments.
llvm/include/llvm/IR/Instructions.h
4085 ↗(On Diff #219020)

This change requires careful analysis of CallBrInst::init. CallBrInst::init calls CallBrInst::setIndirectDest while initializing the instruction. Calling CallBrInst::getIndirectDest via CallBrInst::updateArgBlockAddresses via CallBrInst::setIndirectDest leads to a compiler crash (IIUC, it's not safe to pass cast a nullptr). Essentially, it's not safe to getIndirectDest before setIndirectDest without this change.

llvm/lib/IR/Instructions.cpp
827 ↗(On Diff #219020)

There's two scenarios that could call CallBrInst::updateArgBlockAddresses via CallBrInst::setIndirectDest.

  1. We're initializing the instruction. CallBrInst::init calls CallBrInst::setIndirectDest calls CallBrInst::updateArgBlockAddresses. There is no OldBB, because we're initializing the instruction, so there's nothing to do.
  2. We're updating the successor. CallBrInst::setSuccessor now calls CallBrInst::setIndirectDest calls CallBrInst::updateArgBlockAddresses. Now there is an OldBB which implies there should be a BlockAddress Constant argument operand we need to update as well.
  • rebase, add/clean up the commit message
nickdesaulniers added a comment.EditedSep 6 2019, 12:06 PM

I have verified this allows me to boot:

  • arm64 linux-next (this patch fixes this regression, the below I verified are not regressed)
  • x86_64 linux-next
  • arm linux-next
  • arm linux-next + CONFIG_JUMP_LABEL
  • arm64 linux
  • x86_64 linux
  • arm linux
  • arm linux + CONFIG_JUMP_LABEL
  • updated commit message
nickdesaulniers edited the summary of this revision. (Show Details)Sep 6 2019, 12:29 PM
This revision is now accepted and ready to land.Sep 6 2019, 12:42 PM
nickdesaulniers marked 2 inline comments as done.Sep 6 2019, 2:08 PM
  • git-clang-format HEAD~
This revision was automatically updated to reflect the committed changes.