[Sema] Fix bug in TypeLocBuilder::pushImpl

[ahatanak]

Summary

This patch fixes a bug in the code between line 117-126 of TypeLocBuilder.cpp which was causing the assert in line 132.

The bug manifests itself when an element of size=4 and alignment=4 is inserted first and then an element of size=28 and alignment=8 is inserted next. The code inserts a 4-byte padding at the tail of the first element before the second element is inserted, but that is incorrect and unnecessary since the second element is correctly aligned without any paddings (it can start at Index=32 because it's size is 28-bytes).

[ahatanak]

Fixed a couple of bugs:

• Make sure Capacity is a multiple of 8-byte.
• "||=" isn't a valid operator. Use "||" instead.

[ahatanak]

Rename and add variables. Add comments to make it clearer what the code is doing.

[manmanren]

Hi Akira,

Can you give a high-level explanation of how this patch fixes the problem? This patch enforces that the capacity is 8-byte aligned, is it required to solve the alignment issue here?

Thanks,
Manman

[manmanren]

Thanks for working on this!

Manman

lib/Sema/TypeLocBuilder.cpp

96

This patch seems to do two things:
1> simplify the logic of deciding when to remove padding and when to insert padding (via RemoveOrInsertPadding)
2> fix the correctness issue

We can fix the correctness issue first and then simplify the logic.

[ahatanak]

The bug is in the handling of elements whose LocalAlignment is 8, so I've fixed just that part.

I'll resend a patch to simplify the logic of TypeLocBuilder::pushImpl later as it's not urgent.

[manmanren]

lib/Sema/TypeLocBuilder.cpp

115

Expand this comment a little?

122

The logic looks correct.

The above if, else if, else can be simplified by combining the first condition with the last else condition, because memmove(xx, xx, 0) will just do nothing.

if (CurrentlyHasPadding) {

// remove padding

} else {

// insert padding

}

If you write this part (LocalAlignment == 8) in the same form as how we handle LocalAlignment == 4, it may be better to understand. i.e depending on the following conditions (NumBytesAtAlign8 == 0) (Padding == 0) (LocalSize % 8 == 0)

To help understanding, we can add some high-level comments to the original code of handling "LocalAlignment == 4":
When NumBytesAtAlign8 is not zero, we make sure Index is 8-byte aligned at function exit by adding a 4-byte padding if necessary.

[ahatanak]

Address some of Manman's review comments.

• Add comments that explain what the code is doing (I should add some high-level comments too later).
• Simplify the if-else statement.

I haven't implemented the other changes you've suggested, because I wasn't sure whether imitating the code in "LocalAlignment == 4" would improve readability of the code. For example, I can declare variable "unsigned Padding = NumBytesAtAlign4 %8", but the variable alone doesn't tell you whether there is padding or not (if we haven't inserted any 8-byte elements, we won't have any paddings, but NumBytesAtAlign4 % 8 can still be non-zero).

Maybe I didn't understand what you were suggesting. Could you elaborate a bit more on which part of this code is perhaps hard to understand and how we can improve it?

[manmanren]

Hi Akira,

How about the following?

else if (LocalAlignment == 8) {
  if (NumBytesAtAlign8 == 0) {
    // We have not seen any 8-byte aligned element yet. There is no padding and we are either 4-byte
    // aligned or 8-byte aligned depending on NumBytesAtAlign4.
    // Add in 4 bytes padding if we are not 8-byte aligned including this element.
    if ((LocalSize + NumBytesAtAlign4) % 8 != 0) {
      memmove(&Buffer[Index - 4], &Buffer[Index], NumBytesAtAlign4);
      Index -= 4;
    }
  } else {
    unsigned Padding = NumBytesAtAlign4 % 8;
    if (Padding == 0) { 
      if (LocalSize % 8 == 0) {
        // Everything is set: there's no padding and we don't need to add
        // any.
      } else {
        assert(LocalSize % 8 == 4);
        // No existing padding; add in 4 bytes padding
        memmove(&Buffer[Index - 4], &Buffer[Index], NumBytesAtAlign4);
        Index -= 4;
      }
    } else {
      assert(Padding == 4);
      if (LocalSize % 8 == 0) {
        // Everything is set: there's 4 bytes padding and we don't need
        // to add any.
      } else {
        assert(LocalSize % 8 == 4);
        // There are 4 bytes padding, but we don't need any; remove it.
        memmove(&Buffer[Index + 4], &Buffer[Index], NumBytesAtAlign4);
        Index += 4;
      }
    }
  }
  // Forget about any padding.
  NumBytesAtAlign4 = 0;
  NumBytesAtAlign8 += LocalSize;
}

Note that the handling of NumBytesAtAlign8 != 0 is the same for LocalAlignment == 4 vs. LocalAlignment == 8.
Also mention in the commit message that the original code seems to assume LocalSize is a multiple of 8 when LocalAlignment is 8.

Cheers,
Manman

[ahatanak]

OK, I now understand what you meant.

How about the following?

else if (LocalAlignment == 8) {
  if (NumBytesAtAlign8 == 0) {
    // We have not seen any 8-byte aligned element yet. There is no padding and we are either 4-byte
    // aligned or 8-byte aligned depending on NumBytesAtAlign4.
    // Add in 4 bytes padding if we are not 8-byte aligned including this element.
    if ((LocalSize + NumBytesAtAlign4) % 8 != 0) {
      memmove(&Buffer[Index - 4], &Buffer[Index], NumBytesAtAlign4);
      Index -= 4;
    }

If Capacity is not a multiple of 8, (LocalSize + NumBytesAtAlign4) % 8 doesn't tell you whether the new element will be 8-byte aligned. For example, if Capacity==36, NumBytesAtAlign4==4, and LocalSize==8, (LocalSize + NumBytesAtAlign4) equals 12 but padding is not needed as the new element can start at Index=24. Note that it's possible to have a Capacity that isn't a multiple of 8 by calling TypeLocBuilder::reserve. I think padding is needed if the new index (Index - LocalSize) is not a multiple of 8.

[manmanren]

If Capacity is not a multiple of 8, (LocalSize + NumBytesAtAlign4) % 8 doesn't tell you whether the new element will be 8-byte aligned. For example, if Capacity==36, NumBytesAtAlign4==4, and LocalSize==8, (LocalSize + NumBytesAtAlign4) equals 12 but padding is not needed as the new element can start at Index=24.

I was reading the numbers wrong.

Note that it's possible to have a Capacity that isn't a multiple of 8 by calling TypeLocBuilder::reserve. I think padding is needed if the new index (Index - LocalSize) is not a multiple of 8.

You are right, I missed the case where Capacity may not be 8-byte aligned.

[ahatanak]

Address Manman's review comments. Handle elements with "LocalAlignment == 8" similarly to those with "LocalAlignment == 4".

[ahatanak]

Fix indentation.

[manmanren]

Thanks Akira,

LGTM.

Manman

lib/Sema/TypeLocBuilder.h

 #ifndef NDEBUG
   /// The last type pushed on this builder.
   QualType LastTy;
 #endif
     
   /// The inline buffer.
   enum { BufferMaxAlignment = llvm::AlignOf<void*>::Alignment };
   llvm::AlignedCharArray<BufferMaxAlignment, InlineCapacity> InlineBuffer;
-  unsigned NumBytesAtAlign4, NumBytesAtAlign8;
+  unsigned NumBytesAtAlign4;
+  bool SeenAlign8;
 
  public:
   TypeLocBuilder()
     : Buffer(InlineBuffer.buffer), Capacity(InlineCapacity),
-      Index(InlineCapacity), NumBytesAtAlign4(0), NumBytesAtAlign8(0)
+      Index(InlineCapacity), NumBytesAtAlign4(0), SeenAlign8(false)
   {
   }
 
   ~TypeLocBuilder() {
     if (Buffer != InlineBuffer.buffer)
       delete[] Buffer;
   }
 
public:
   }
 
   /// Resets this builder to the newly-initialized state.
   void clear() {
 #ifndef NDEBUG
     LastTy = QualType();
 #endif
     Index = Capacity;
-    NumBytesAtAlign4 = NumBytesAtAlign8 = 0;
+    NumBytesAtAlign4 = 0;
+    SeenAlign8 = false;
   }  
 
   /// \brief Tell the TypeLocBuilder that the type it is storing has been
   /// modified in some safe way that doesn't affect type-location information.
   void TypeWasModifiedSafely(QualType T) {
 #ifndef NDEBUG
     LastTy = T;
 #endif

lib/Sema/TypeLocBuilder.cpp

 TypeLoc TypeLocBuilder::pushImpl(QualType T, size_t LocalSize, unsigned LocalAlignment) {
 #ifndef NDEBUG
   QualType TLast = TypeLoc(T, nullptr).getNextTypeLoc().getType();
   assert(TLast == LastTy &&
          "mismatch between last type and new type's inner type");
   LastTy = T;
 #endif
 
-  assert(LocalAlignment <= BufferMaxAlignment && "Unexpected alignment");
+  assert(Capacity % 8 == 0 && "Capacity must be a multiple of 8");
+  assert(LocalSize % 4 == 0 && "LocalSize must be a multiple of 4");
+  assert(LocalAlignment <= BufferMaxAlignment &&
+         (LocalAlignment == 8 || LocalAlignment == 4 || LocalSize == 0) &&
+         "Unexpected alignment");
+
+  // Check whether there is padding at the tail of the 4-byte elements.
+  bool HasPadding = (Index + NumBytesAtAlign4) % 8;
+  bool RemoveOrInsertPadding = false;
+  unsigned RequiredCapacity = Capacity - Index + LocalSize;
+
+  // The element being pushed has to be aligned at an 8-byte boundary if its
+  // alignment is 8-byte or an 8-byte aligned element has already been pushed.
+  // In that case, make sure RequiredCapacity is a multiple of 8.
+  if ((SeenAlign8 || LocalAlignment == 8) && RequiredCapacity % 8) {
+    RequiredCapacity += (HasPadding ? -4 : 4);
+    RemoveOrInsertPadding = NumBytesAtAlign4 != 0;
+  }
+
+  unsigned NewCapacity = Capacity;
 
   // If we need to grow, grow by a factor of 2.
-  if (LocalSize > Index) {
-    size_t RequiredCapacity = Capacity + (LocalSize - Index);
-    size_t NewCapacity = Capacity * 2;
-    while (RequiredCapacity > NewCapacity)
-      NewCapacity *= 2;
+
+  if (NewCapacity != Capacity)
     grow(NewCapacity);
-  }
 
-  // Because we're adding elements to the TypeLoc backwards, we have to
-  // do some extra work to keep everything aligned appropriately.
-  // FIXME: This algorithm is a absolute mess because every TypeLoc returned
-  // needs to be valid.  Partial TypeLocs are a terrible idea.
-  // FIXME: 4 and 8 are sufficient at the moment, but it's pretty ugly to
-  // hardcode them.
-  if (LocalAlignment == 4) {
-    if (NumBytesAtAlign8 == 0) {
-      NumBytesAtAlign4 += LocalSize;
-    } else {
-      unsigned Padding = NumBytesAtAlign4 % 8;
-      if (Padding == 0) {
-        if (LocalSize % 8 == 0) {
-          // Everything is set: there's no padding and we don't need to add
-          // any.
-        } else {
-          assert(LocalSize % 8 == 4);
-          // No existing padding; add in 4 bytes padding
-          memmove(&Buffer[Index - 4], &Buffer[Index], NumBytesAtAlign4);
-          Index -= 4;
-        }
-      } else {
-        assert(Padding == 4);
-        if (LocalSize % 8 == 0) {
-          // Everything is set: there's 4 bytes padding and we don't need
-          // to add any.
-        } else {
-          assert(LocalSize % 8 == 4);
-          // There are 4 bytes padding, but we don't need any; remove it.
-          memmove(&Buffer[Index + 4], &Buffer[Index], NumBytesAtAlign4);
-          Index += 4;
-        }
-      }
-      NumBytesAtAlign4 += LocalSize;
-    }
-  } else if (LocalAlignment == 8) {
-    if (!NumBytesAtAlign8 && NumBytesAtAlign4 % 8 != 0) {
-      // No existing padding and misaligned members; add in 4 bytes padding
+  if (RemoveOrInsertPadding) {
+    if (HasPadding) // Remove padding.
+    else // Insert padding.
       memmove(&Buffer[Index - 4], &Buffer[Index], NumBytesAtAlign4);
-      Index -= 4;
-    }
-    // Forget about any padding.
+
+  if (LocalAlignment == 8) {
+    SeenAlign8 ||= LocalSize != 0;
     NumBytesAtAlign4 = 0;
-    NumBytesAtAlign8 += LocalSize;
-  } else {
-    assert(LocalSize == 0);
+  } else if (LocalAlignment == 4) {
+    NumBytesAtAlign4 += LocalSize;
   }
 
-  Index -= LocalSize;
+  Index = Capacity - RequiredCapacity;
 
   assert(Capacity - Index == TypeLoc::getFullDataSizeForType(T) &&
          "incorrect data size provided to CreateTypeSourceInfo!");
 
   return getTemporaryTypeLoc(T);
 }

test/SemaObjCXX/typeloc-data-alignment.mm

+// RUN: %clang_cc1 -fsyntax-only -verify %s
+// expected-no-diagnostics
+
+// Make sure this doesn't crash.
+
+@protocol P
+@end
+template <class T>
+id<P> foo(T) {
+  int i;
+  foo(i);
+}