[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

57

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

2

# is simpler

2

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.

8

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

.fill (fct_end - data_start), 1, 42

to test Layout->isFragmentValidating(FB)

11

Delete the unneeded .long

[thopre]

Rework patch to catch to handle more complex layout interdependencies

llvm/include/llvm/MC/MCAsmLayout.h

57

To echo the isFragmentValid but yeah isFragmentLayouting is clearer.

[MaskRay]

llvm/include/llvm/MC/MCAsmLayout.h

36

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

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

6 ↗

(On Diff #263225)

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

8 ↗

(On Diff #263225)

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 ↗

(On Diff #263706)

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

 //===- MCAsmLayout.h - Assembly Layout Object -------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_MC_MCASMLAYOUT_H
 #define LLVM_MC_MCASMLAYOUT_H
 
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 
 namespace llvm {
 class MCAssembler;
 class MCFragment;
 class MCSection;
 class MCSymbol;
 
 /// Encapsulates the layout of an assembly file at a particular point in time.
 ///
 /// Assembly may require computing multiple layouts for a particular assembly
 /// file as part of the relaxation process. This class encapsulates the layout
 /// at a single point in time in such a way that it is always possible to
 /// efficiently compute the exact address of any symbol in the assembly file,
 /// even during the relaxation process.
 class MCAsmLayout {
   MCAssembler &Assembler;
 
   /// List of sections in layout order.
   llvm::SmallVector<MCSection *, 16> SectionOrder;
 
+  /// Set of fragments currently being laid out.
+  mutable SmallPtrSet<MCFragment *, 4> LayingOutFragmentsSet;
+
   /// 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; }
 
+  bool isFragmentValidating(const MCFragment *F) const {
+    return LayingOutFragmentsSet.find(F) != LayingOutFragmentsSet.end();
+  }
+
   /// 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/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!");
 
+  bool InsertionSuccess;
+  std::tie(std::ignore, InsertionSuccess) = LayingOutFragmentsSet.insert(F);
+  assert(InsertionSuccess && "Already being laid out!");
+
   ++stats::FragmentLayouts;
 
   // Compute fragment offset and size.
   if (Prev)
     F->Offset = Prev->Offset + getAssembler().computeFragmentSize(*this, *Prev);
   else
     F->Offset = 0;
+  LayingOutFragmentsSet.erase(F);
   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;
 
+  if (Layout &&
+      (Layout->isFragmentValidating(FA) || Layout->isFragmentValidating(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/test/MC/AsmParser/pr45805.s

+// RUN: not llvm-mc --filetype=obj %s -o /dev/null 2>&1 | FileCheck %s
+
+
+fct_end:
+
+// CHECK: pr45805.s:7:7: error: expected assembly-time absolute expression
+.fill (data_start - fct_end), 1, 42
+
+data_start:
+.long 0x42424242