[MC] Recalculate fragment offsets after relaxation

[jcai19]

Summary

The current relaxation implementation is not correctly adjusting the
size and offsets of fragements in one section based on changes in size
of another if the layout order of the two happened to be such that the
former was visited before the later. Therefore, we need to invalidate
the fragments in all sections after each iteration of relaxation, and
possibly further relax some of them in the next ieration. This fixes
PR#45190.

[jcai19]

Attach bug id.

[jcai19]

Update the patch.

[MaskRay]

llvm/test/MC/X86/relax-offset.s

15

NOT pattern should be carefully used. Without a positive check with the same diagnostic, a negative check can easily get stale and don't check anything.

For this case (a regression test), an error will cause llvm-mc to return 1 instead of 0,

llvm-mc -filetype=obj -triple=i386 %s -o /dev/null is sufficient.

[nickdesaulniers]

llvm/test/MC/X86/relax-offset.s

15

NOT pattern should be carefully used. Without a positive check with the same diagnostic, a negative check can easily get stale and don't check anything.

Just to second this, and add my negative experiences with CHECK-NOT; make sure the test is red before your patch is applied, then green after it's applied. Test Driven Development. I too have seen CHECK-NOT's not actually test anything.

Also, @MaskRay , this check is for an assertion failure. Is it common to test for asserts, which may not be enabled when running the tests in release mode?

[jcai19]

Update tests based on comments.

[reames]

Reduced test case:

.section .entry.text, "ax"

.skip 144f-143f,0x0
.pushsection .altinstr_replacement,"ax"
143:
jmp .Lint80_keep_stack
144:
.popsection

.Lint80_keep_stack:

This does not appear to relate to the recent alignment padding work. Test continues to fail with -x86-pad-for-align=0 -x86-pad-for-branch-align=0

[reames]

The proposed fix is insufficient. Consider the case where a change in size of the skip requires further relaxation in that section or another. This needs to cause another iteration of relaxation.

[jcai19]

Agreed. In that case we can probably check whether the offset of any valid fragment is changed, and if so trigger another pass on the layout. Although I am not sure on (1) how to come up with a test case, and (2) if that will eventually converge.

[jcai19]

Update test case.

[jcai19]

This does not appear to relate to the recent alignment padding work. Test continues to fail with -x86-pad-for-align=0 -x86-pad-for-branch-align=0

I am not sure I followed here but I ran the test case as follows and it still passed.

llvm-mc -filetype=obj -triple=i386 relax-offset.s -o /dev/null -x86-pad-for-align=0 -x86-pad-for-branch-align=0

[reames]

In D76114#1922553, @jcai19 wrote:

This does not appear to relate to the recent alignment padding work. Test continues to fail with -x86-pad-for-align=0 -x86-pad-for-branch-align=0

I am not sure I followed here but I ran the test case as follows and it still passed.

llvm-mc -filetype=obj -triple=i386 relax-offset.s -o /dev/null -x86-pad-for-align=0 -x86-pad-for-branch-align=0

Er, I assume you mean "passed on the build with your change" correct?

I specifically meant "continued to fail on top of tree with those padding flags disabled (set to 0)".

[jcai19]

Update based on comments from https://reviews.llvm.org/D76166.

[reames]

LGTM, though please make sure you update the description when landing! The description is incomplete, and doesn't cover the iterative part.

[jcai19]

Update commit message.

[MaskRay]

llvm/test/MC/X86/relax-offset.s

2

llvm-objdump --headers -> llvm-readelf -S

llvm-objdump --headers does not match GNU and can cause confusion.

[skan]

LGTM

[MaskRay]

Do we know which commit caused the regression? Is it related to one of the recent x86 instruction padding patches?

[MaskRay]

llvm/test/MC/X86/relax-offset.s

7

.section .text1,"ax" is slightly better, otherwise objdump -d does not disassemble.

[skan]

In D76114#1925719, @MaskRay wrote:

Do we know which commit caused the regression? Is it related to one of the recent x86 instruction padding patches?

It's not a regression. The current relaxation implementation has never considered (or intended to support) this corner case.

[skan]

In D76114#1925746, @skan wrote:

In D76114#1925719, @MaskRay wrote:

Do we know which commit caused the regression? Is it related to one of the recent x86 instruction padding patches?

It's not a regression. The current relaxation implementation has never considered (or intended to support) this corner case.

The main reason for the newly added test case fail is that MCFragment caches its offset (for faster layout), but does not cache its size. So when the size of a fragment changes, the offset of the fragment behind it will change. So if the subsequent fragment does not update its cached offset (because it is considered as valid), some checks will fail.

llvm/lib/MC/MCAssembler.cpp

uint64_t MCAssembler::computeFragmentSize(const MCAsmLayout &Layout,
   }
 
   llvm_unreachable("invalid fragment kind");
 }
 
 void MCAsmLayout::layoutFragment(MCFragment *F) {
   MCFragment *Prev = F->getPrevNode();
 
-  // 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!");
 
+  // We may need to recompute the offset of valid framents if relaxation changes
+  // the offset of some fragments. PR#45190
+  if (!isFragmentValid(F))
     ++stats::FragmentLayouts;
 
   // Compute fragment offset and size.
   if (Prev)
     F->Offset = Prev->Offset + getAssembler().computeFragmentSize(*this, *Prev);
   else
     F->Offset = 0;
   LastValidFragment[F->getParent()] = F;
 
for (unsigned i = 0, e = Layout.getSectionOrder().size(); i != e; ++i) {
     Sec->setLayoutOrder(i);
 
     unsigned FragmentIndex = 0;
     for (MCFragment &Frag : *Sec)
       Frag.setLayoutOrder(FragmentIndex++);
   }
 
   // Layout until everything fits.
-  while (layoutOnce(Layout))
+  bool WasRelaxed = false;
+  while (layoutOnce(Layout)) {
     if (getContext().hadError())
       return;
+    WasRelaxed = true;
+  }
+  // recalculate the offsets of fragments if relaxation happens. PR#45190
+  if (WasRelaxed) {
+    for (MCSection &Sec : *this)
+      for (MCFragment &F : Sec)
+        Layout.layoutFragment(&F);
+  }
+
 
   DEBUG_WITH_TYPE("mc-dump", {
       errs() << "assembler backend - post-relaxation\n--\n";
       dump(); });
 
   // Finalize the layout, including fragment lowering.
   finishLayout(Layout);
 
   DEBUG_WITH_TYPE("mc-dump", {

llvm/test/MC/X86/relax-offset.s

+# RUN: llvm-mc -triple i386-unknown-unknown %s -filetype=obj -o /dev/null 2>&1 | FileCheck --allow-empty %s
+
+.macro ALTERNATIVE newinstr
+ .skip 144f-143f,0x0
+ .pushsection .altinstr_replacement,"ax"
+143:
+ \newinstr
+144:
+ .popsection
+.endm
+
+ .section .entry.text, "ax"
+  ALTERNATIVE "jmp .Lint80_keep_stack"
+.Lint80_keep_stack:
+# CHECK-NOT: error: Assertion `OS.tell() - Start == Layout.getSectionAddressSize(Sec)' failed