[MC] Fix PR45805: infinite recursion in assembler

[thopre]

Summary

Give up folding an expression if the fragment of one of the operands
would require laying out a fragment already being laid out. This
prevents hitting an infinite recursion when a fill size expression
refers to a later fragment since computing the offset of that fragment
would require laying out the fill fragment and thus computing its size
expression.

[thopre]

Default initialize InsertionSuccess

[thopre]

clang-tidy errors are:

llvm-project/llvm/include/llvm/ADT/SmallPtrSet.h:377:48: error: incomplete definition of type 'llvm::PointerLikeTypeTraits<const llvm::MCFragment *>' [clang-diagnostic-error]

return makeIterator(find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)));
                                           ^

llvm-project/llvm/include/llvm/MC/MCAsmLayout.h:57:34: note: in instantiation of member function 'llvm::SmallPtrSetImpl<llvm::MCFragment *>::find' requested here

return LayingOutFragmentsSet.find(F) != LayingOutFragmentsSet.end();
                             ^

llvm-project/llvm/include/llvm/Support/PointerLikeTypeTraits.h:61:28: error: invalid application of 'alignof' to an incomplete type 'llvm::MCFragment' [clang-diagnostic-error]

detail::ConstantLog2<alignof(T)>::value;
                     ^

llvm-project/llvm/include/llvm/Support/PointerLikeTypeTraits.h:101:46: note: in instantiation of template class 'llvm::PointerLikeTypeTraits<llvm::MCFragment *>' requested here

static constexpr int NumLowBitsAvailable = NonConst::NumLowBitsAvailable;
                                           ^

llvm-project/llvm/include/llvm/ADT/SmallPtrSet.h:377:34: note: in instantiation of template class 'llvm::PointerLikeTypeTraits<const llvm::MCFragment *>' requested here

return makeIterator(find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)));
                             ^

llvm-project/llvm/include/llvm/MC/MCAsmLayout.h:57:34: note: in instantiation of member function 'llvm::SmallPtrSetImpl<llvm::MCFragment *>::find' requested here

return LayingOutFragmentsSet.find(F) != LayingOutFragmentsSet.end();
                             ^

llvm-project/llvm/include/llvm/MC/MCAsmLayout.h:18:7: note: forward declaration of 'llvm::MCFragment'
class MCFragment;

^

Does that mean SmallPtrSet cannot be used for a pointer to incomplete type?

[MaskRay]

Thanks for the patch. This approach may be fine.

llvm/include/llvm/MC/MCAsmLayout.h

53

count

Why is called Validating instead of layouting?

llvm/lib/MC/MCAssembler.cpp

401

bool Inserted = LayingOutFragmentsSet.insert(F).second;
assert(Inserted && "Already being laid out!");
(void)Inserted;

llvm/lib/MC/MCExpr.cpp

581

Add a comment along the lines of: the enclosing fragment is being layouted. Avoid self loop.

llvm/test/MC/AsmParser/pr45805.s

1 ↗

(On Diff #262635)

# is simpler

1 ↗

(On Diff #262635)

binutils use prXXXX.s for regression tests. I find the names not very descriptive. How about layout-*.s? I currently haven't thought of a good name for the -* part.

7 ↗

(On Diff #262635)

The test covers Layout->isFragmentValidating(FA) . You also need

.fill (fct_end - data_start), 1, 42

to test Layout->isFragmentValidating(FB)

10 ↗

(On Diff #262635)

Delete the unneeded .long

[thopre]

Rework patch to catch to handle more complex layout interdependencies

llvm/include/llvm/MC/MCAsmLayout.h

53

To echo the isFragmentValid but yeah isFragmentLayouting is clearer.

[MaskRay]

llvm/include/llvm/MC/MCAsmLayout.h

35

I feel uneasy that we are adding another mutable member. Can mutable be avoided?

llvm/test/MC/AsmParser/layout-interdependency.s

7

Change the line number to [[#@LINE+1]]

9

Doesn't the second line have an error?

[thopre]

Record whether a fragment is being laid out in the fragment itself to avoid a mutable field in MCAsmLayout

[thopre]

• Check for error message of second fill line
• Check line number in error message based on CHECK directive's line number

[thopre]

Initialize IsBeingLaidOut member variable.

[thopre]

Remove no longer needed include

[thopre]

Ping?

[MaskRay]

In D79570#2046558, @thopre wrote:

Ping?

The code and test look good to me now, but hope someone with MC experience can confirm.

[thopre]

Ping? Can anyone with MC experience review this? Am I missing someone as reviewer?

[echristo]

In D79570#2062583, @thopre wrote:

Ping? Can anyone with MC experience review this? Am I missing someone as reviewer?

I'll try to get to this today.

[thopre]

In D79570#2063727, @echristo wrote:

In D79570#2062583, @thopre wrote:

Ping? Can anyone with MC experience review this? Am I missing someone as reviewer?

I'll try to get to this today.

Ping?

[thopre]

In D79570#2063727, @echristo wrote:

In D79570#2062583, @thopre wrote:

Ping? Can anyone with MC experience review this? Am I missing someone as reviewer?

I'll try to get to this today.

Ping @echristo ?

[thopre]

In D79570#2092787, @thopre wrote:

In D79570#2063727, @echristo wrote:

In D79570#2062583, @thopre wrote:

Ping? Can anyone with MC experience review this? Am I missing someone as reviewer?

I'll try to get to this today.

Ping @echristo ?

Ping?

[echristo]

One inline code comment otherwise lgtm.

llvm/lib/MC/MCFragment.cpp

61

A bit of vertical space here and bring the comment before the variable declaration here?

[thopre]

Address review comment

llvm/include/llvm/MC/MCAsmLayout.h

 /// even during the relaxation process.
 class MCAsmLayout {
   MCAssembler &Assembler;
 
   /// List of sections in layout order.
   llvm::SmallVector<MCSection *, 16> SectionOrder;
 
   /// The last fragment which was laid out, or 0 if nothing has been laid
   /// out. Fragments are always laid out in order, so all fragments with a
   /// lower ordinal will be valid.
   mutable DenseMap<const MCSection *, MCFragment *> LastValidFragment;
 
   /// Make sure that the layout for the given fragment is valid, lazily
   /// computing it if necessary.
   void ensureValid(const MCFragment *F) const;
 
   /// Is the layout for this fragment valid?
   bool isFragmentValid(const MCFragment *F) const;
 
 public:
   MCAsmLayout(MCAssembler &Assembler);
 
   /// Get the assembler object this is a layout for.
   MCAssembler &getAssembler() const { return Assembler; }
 
+  /// \returns whether the offset of fragment \p F can be obtained via
+  /// getFragmentOffset.
+  bool canGetFragmentOffset(const MCFragment *F) const;
+
   /// Invalidate the fragments starting with F because it has been
   /// resized. The fragment's size should have already been updated, but
   /// its bundle padding will be recomputed.
   void invalidateFragmentsFrom(MCFragment *F);
 
   /// Perform layout for a single fragment, assuming that the previous
   /// fragment has already been laid out correctly, and the parent section has
   /// been initialized.

llvm/include/llvm/MC/MCFragment.h

private:
   /// initialized.
   uint64_t Offset;
 
   /// The layout order of this fragment.
   unsigned LayoutOrder;
 
   FragmentType Kind;
 
+  /// Whether fragment is being laid out.
+  bool IsBeingLaidOut;
+
 protected:
   bool HasInstructions;
 
   MCFragment(FragmentType Kind, bool HasInstructions,
              MCSection *Parent = nullptr);
 
 public:
   MCFragment() = delete;

llvm/lib/MC/MCAssembler.cpp

void MCAsmLayout::layoutFragment(MCFragment *F) {
 
   // We should never try to recompute something which is valid.
   assert(!isFragmentValid(F) && "Attempt to recompute a valid fragment!");
   // We should never try to compute the fragment layout if its predecessor
   // isn't valid.
   assert((!Prev || isFragmentValid(Prev)) &&
          "Attempt to compute fragment before its predecessor!");
 
+  assert(!F->IsBeingLaidOut && "Already being laid out!");
+  F->IsBeingLaidOut = true;
+
   ++stats::FragmentLayouts;
 
   // Compute fragment offset and size.
   if (Prev)
     F->Offset = Prev->Offset + getAssembler().computeFragmentSize(*this, *Prev);
   else
     F->Offset = 0;
+  F->IsBeingLaidOut = false;
   LastValidFragment[F->getParent()] = F;
 
   // If bundling is enabled and this fragment has instructions in it, it has to
   // obey the bundling restrictions. With padding, we'll have:
   //
   //
   //        BundlePadding
   //             |||

llvm/lib/MC/MCExpr.cpp

static void AttemptToFoldSymbolOffsetDifference(
   const MCSymbol &SB = B->getSymbol();
 
   if (SA.isUndefined() || SB.isUndefined())
     return;
 
   if (!Asm->getWriter().isSymbolRefDifferenceFullyResolved(*Asm, A, B, InSet))
     return;
 
-  if (SA.getFragment() == SB.getFragment() && !SA.isVariable() &&
-      !SA.isUnset() && !SB.isVariable() && !SB.isUnset()) {
+  MCFragment *FA = SA.getFragment();
+  MCFragment *FB = SB.getFragment();
+  if (FA == FB && !SA.isVariable() && !SA.isUnset() && !SB.isVariable() &&
+      !SB.isUnset()) {
     Addend += (SA.getOffset() - SB.getOffset());
 
     // Pointers to Thumb symbols need to have their low-bit set to allow
     // for interworking.
     if (Asm->isThumbFunc(&SA))
       Addend |= 1;
 
     // If symbol is labeled as micromips, we set low-bit to ensure
     // correct offset in .gcc_except_table
     if (Asm->getBackend().isMicroMips(&SA))
       Addend |= 1;
 
     // Clear the symbol expr pointers to indicate we have folded these
     // operands.
     A = B = nullptr;
     return;
   }
 
   if (!Layout)
     return;
 
-  const MCSection &SecA = *SA.getFragment()->getParent();
-  const MCSection &SecB = *SB.getFragment()->getParent();
+  const MCSection &SecA = *FA->getParent();
+  const MCSection &SecB = *FB->getParent();
 
   if ((&SecA != &SecB) && !Addrs)
     return;
 
+  // One of the symbol involved is part of a fragment being laid out. Quit now
+  // to avoid a self loop.
+  if (!Layout->canGetFragmentOffset(FA) || !Layout->canGetFragmentOffset(FB))
+    return;
+
   // Eagerly evaluate.
   Addend += Layout->getSymbolOffset(A->getSymbol()) -
             Layout->getSymbolOffset(B->getSymbol());
   if (Addrs && (&SecA != &SecB))
     Addend += (Addrs->lookup(&SecA) - Addrs->lookup(&SecB));
 
   // Pointers to Thumb symbols need to have their low-bit set to allow
   // for interworking.

llvm/lib/MC/MCFragment.cpp

bool MCAsmLayout::isFragmentValid(const MCFragment *F) const {
   const MCSection *Sec = F->getParent();
   const MCFragment *LastValid = LastValidFragment.lookup(Sec);
   if (!LastValid)
     return false;
   assert(LastValid->getParent() == Sec);
   return F->getLayoutOrder() <= LastValid->getLayoutOrder();
 }
 
+bool MCAsmLayout::canGetFragmentOffset(const MCFragment *F) const {
+  MCSection *Sec = F->getParent();
+  MCSection::iterator I;
+  if (MCFragment *LastValid = LastValidFragment[Sec]) {
+    // Fragment already valid, offset is available.
+    if (F->getLayoutOrder() <= LastValid->getLayoutOrder())
+      return true;
+    I = ++MCSection::iterator(LastValid);
+  } else
+    I = Sec->begin();
+  const MCFragment *FirstInvalidFragment = &*I;
+
+  // A fragment ordered before F is currently being laid out.
+  if (FirstInvalidFragment->IsBeingLaidOut)
+    return false;
+
+  return true;
+}
+
 void MCAsmLayout::invalidateFragmentsFrom(MCFragment *F) {
   // If this fragment wasn't already valid, we don't need to do anything.
   if (!isFragmentValid(F))
     return;
 
   // Otherwise, reset the last valid fragment to the previous fragment
   // (if this is the first fragment, it will be NULL).
   LastValidFragment[F->getParent()] = F->getPrevNode();

 
 /* *** */
 
 void ilist_alloc_traits<MCFragment>::deleteNode(MCFragment *V) { V->destroy(); }
 
 MCFragment::MCFragment(FragmentType Kind, bool HasInstructions,
                        MCSection *Parent)
     : Parent(Parent), Atom(nullptr), Offset(~UINT64_C(0)), LayoutOrder(0),
-      Kind(Kind), HasInstructions(HasInstructions) {
+      Kind(Kind), IsBeingLaidOut(false), HasInstructions(HasInstructions) {
   if (Parent && !isa<MCDummyFragment>(*this))
     Parent->getFragmentList().push_back(this);
 }
 
 void MCFragment::destroy() {
   // First check if we are the sentinal.
   if (Kind == FragmentType(~0)) {
     delete this;

llvm/test/MC/AsmParser/layout-interdependency.s

+# RUN: not llvm-mc --filetype=obj %s -o /dev/null 2>&1 | FileCheck %s
+
+fct_end:
+
+# CHECK: layout-interdependency.s:[[#@LINE+1]]:7: error: expected assembly-time absolute expression
+.fill (data_start - fct_end), 1, 42
+# CHECK: layout-interdependency.s:[[#@LINE+1]]:7: error: expected assembly-time absolute expression
+.fill (fct_end - data_start), 1, 42
+
+data_start: