[Bitcode] materialize Functions early when BlockAddress taken

[nickdesaulniers]

Summary

IRLinker builds a work list of functions to materialize, then moves them
from a source module to a destination module one at a time.

This is a problem for blockaddress Constants, since they need not refer
to the function they are used in; IPSCCP is quite good at sinking these
constants deep into other functions when passed as arguments.

This would lead to curious errors during LTO:

ld.lld: error: Never resolved function from blockaddress ...

based on the ordering of function definitions in IR.

The problem was that IRLinker would basically do:

for function f in worklist:
  materialize f
  splice f from source module to destination module

in one pass, with Functions being lazily added to the running worklist.
This confuses BitcodeReader, which cannot disambiguate whether a
blockaddress is referring to a function which has not yet been parsed
("materialized") or is simply empty because its body was spliced out.
This causes BitcodeReader to insert Functions into its BasicBlockFwdRefs
list incorrectly, as it will never re-materialize an already
materialized (but spliced out) function.

Because of the possibility that blockaddress Constants may appear in
Functions other than the ones they reference, this patch adds a new
bitcode function code FUNC_CODE_BLOCKADDR_USERS that is a simple list of
Functions that contain BlockAddress Constants that refer back to this
Function, rather then the Function they are scoped in. We then
materialize those functions when materializing f from the example loop
above. This might over-materialize Functions should the user of
BitcodeReader ultimately decide not to link those Functions, but we can
at least now we can avoid this ordering related issue with blockaddresses.

Fixes: https://github.com/llvm/llvm-project/issues/52787
Fixes: https://github.com/ClangBuiltLinux/linux/issues/1215

[nickdesaulniers]

sigh, --verbatim and --update can't be used together

llvm/include/llvm/Bitcode/LLVMBitCodes.h

enum FunctionCodes {
   FUNC_CODE_INST_CLEANUPRET = 48,  // CLEANUPRET: [val] or [val,bb#]
   FUNC_CODE_INST_CATCHRET = 49,    // CATCHRET: [val,bb#]
   FUNC_CODE_INST_CATCHPAD = 50,    // CATCHPAD: [bb#,bb#,num,args...]
   FUNC_CODE_INST_CLEANUPPAD = 51,  // CLEANUPPAD: [num,args...]
   FUNC_CODE_INST_CATCHSWITCH =
       52, // CATCHSWITCH: [num,args...] or [num,args...,bb]
   // 53 is unused.
   // 54 is unused.
-  FUNC_CODE_OPERAND_BUNDLE = 55, // OPERAND_BUNDLE: [tag#, value...]
-  FUNC_CODE_INST_UNOP = 56,      // UNOP:       [opcode, ty, opval]
-  FUNC_CODE_INST_CALLBR = 57,    // CALLBR:     [attr, cc, norm, transfs,
+  FUNC_CODE_OPERAND_BUNDLE = 55,  // OPERAND_BUNDLE: [tag#, value...]
+  FUNC_CODE_INST_UNOP = 56,       // UNOP:       [opcode, ty, opval]
+  FUNC_CODE_INST_CALLBR = 57,     // CALLBR:     [attr, cc, norm, transfs,
                                   //              fnty, fnid, args...]
-  FUNC_CODE_INST_FREEZE = 58,    // FREEZE: [opty, opval]
-  FUNC_CODE_INST_ATOMICRMW = 59, // ATOMICRMW: [ptrty, ptr, valty, val,
+  FUNC_CODE_INST_FREEZE = 58,     // FREEZE: [opty, opval]
+  FUNC_CODE_INST_ATOMICRMW = 59,  // ATOMICRMW: [ptrty, ptr, valty, val,
                                   //             operation, align, vol,
                                   //             ordering, synchscope]
+  FUNC_CODE_BLOCKADDR_USERS = 60, // BLOCKADDR_USERS: [value...]
 };
 
 enum UseListCodes {
   USELIST_CODE_DEFAULT = 1, // DEFAULT: [index..., value-id]
   USELIST_CODE_BB = 2       // BB: [index..., bb-id]
 };
 
 enum AttributeKindCodes {

llvm/lib/Bitcode/Reader/BitcodeAnalyzer.cpp

default:
       STRINGIFY_CODE(FUNC_CODE, INST_GEP)
       STRINGIFY_CODE(FUNC_CODE, OPERAND_BUNDLE)
       STRINGIFY_CODE(FUNC_CODE, INST_FENCE)
       STRINGIFY_CODE(FUNC_CODE, INST_ATOMICRMW)
       STRINGIFY_CODE(FUNC_CODE, INST_LOADATOMIC)
       STRINGIFY_CODE(FUNC_CODE, INST_STOREATOMIC)
       STRINGIFY_CODE(FUNC_CODE, INST_CMPXCHG)
       STRINGIFY_CODE(FUNC_CODE, INST_CALLBR)
+      STRINGIFY_CODE(FUNC_CODE, BLOCKADDR_USERS)
     }
   case bitc::VALUE_SYMTAB_BLOCK_ID:
     switch (CodeID) {
     default:
       return None;
       STRINGIFY_CODE(VST_CODE, ENTRY)
       STRINGIFY_CODE(VST_CODE, BBENTRY)
       STRINGIFY_CODE(VST_CODE, FNENTRY)

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

case bitc::FUNC_CODE_DECLAREBLOCKS: {   // DECLAREBLOCKS: [nblocks]
         // Erase from the table.
         BasicBlockFwdRefs.erase(BBFRI);
       }
 
       CurBB = FunctionBBs[0];
       continue;
     }
 
+    case bitc::FUNC_CODE_BLOCKADDR_USERS: // BLOCKADDR_USERS: [vals...]
+      // The record should not be emitted if it's an empty list.
+      if (Record.empty())
+        return error("Invalid record");
+      // When we have the RARE case of a BlockAddress Constant that is not
+      // scoped to the Function it refers to, we need to conservatively
+      // materialize the referred to Function, regardless of whether or not
+      // that Function will ultimately be linked, otherwise users of
+      // BitcodeReader might start splicing out Function bodies such that we
+      // might no longer be able to materialize the BlockAddress since the
+      // BasicBlock (and entire body of the Function) the BlockAddress refers
+      // to may have been moved. In the case that the user of BitcodeReader
+      // decides ultimately not to link the Function body, materializing here
+      // could be considered wasteful, but it's better than a deserialization
+      // failure as described. This keeps BitcodeReader unaware of complex
+      // linkage policy decisions such as those use by LTO, leaving those
+      // decisions "one layer up."
+      for (uint64_t ValID : Record)
+        if (auto *F = dyn_cast<Function>(ValueList[ValID])) {
+          if (Error Err = materialize(F))
+            return Err;
+        } else
+          return error("Invalid record");
+      continue;
+
     case bitc::FUNC_CODE_DEBUG_LOC_AGAIN:  // DEBUG_LOC_AGAIN
       // This record indicates that the last instruction is at the same
       // location as the previous instruction with a location.
       I = getLastInstruction();
 
       if (!I)
         return error("Invalid record");
       I->setDebugLoc(LastLoc);

llvm/lib/Bitcode/Writer/BitcodeWriter.cpp

 #include "ValueEnumerator.h"
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/Bitcode/BitcodeCommon.h"
 #include "llvm/Bitcode/BitcodeReader.h"
 #include "llvm/Bitcode/LLVMBitCodes.h"
void ModuleBitcodeWriter::writeFunction(
   writeFunctionMetadata(F);
 
   // Keep a running idea of what the instruction ID is.
   unsigned InstID = CstEnd;
 
   bool NeedsMetadataAttachment = F.hasMetadata();
 
   DILocation *LastDL = nullptr;
+  SmallPtrSet<Function *, 4> BlockAddressUsers;
+
   // Finally, emit all the instructions, in order.
-  for (const BasicBlock &BB : F)
+  for (const BasicBlock &BB : F) {
     for (const Instruction &I : BB) {
       writeInstruction(I, InstID, Vals);
 
       if (!I.getType()->isVoidTy())
         ++InstID;
 
       // If the instruction has metadata, write a metadata attachment later.
       NeedsMetadataAttachment |= I.hasMetadataOtherThanDebugLoc();
for (const Instruction &I : BB) {
       Vals.push_back(VE.getMetadataOrNullID(DL->getInlinedAt()));
       Vals.push_back(DL->isImplicitCode());
       Stream.EmitRecord(bitc::FUNC_CODE_DEBUG_LOC, Vals);
       Vals.clear();
 
       LastDL = DL;
     }
 
+    if (BlockAddress *BA = BlockAddress::lookup(&BB))
+      for (User *U : BA->users())
+        if (auto *I = dyn_cast<Instruction>(U)) {
+          Function *P = I->getParent()->getParent();
+          if (P != &F)
+            BlockAddressUsers.insert(P);
+        }
+  }
+
+  if (!BlockAddressUsers.empty()) {
+    SmallVector<uint64_t, 4> Record;
+    Record.reserve(BlockAddressUsers.size());
+    for (Function *F : BlockAddressUsers)
+      Record.push_back(VE.getValueID(F));
+    Stream.EmitRecord(bitc::FUNC_CODE_BLOCKADDR_USERS, Record);
+  }
+
   // Emit names for all the instructions etc.
   if (auto *Symtab = F.getValueSymbolTable())
     writeFunctionLevelValueSymbolTable(*Symtab);
 
   if (NeedsMetadataAttachment)
     writeFunctionMetadataAttachment(F);
   if (VE.shouldPreserveUseListOrder())
     writeUseListBlock(&F);