[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

130

Expand this comment a little?

137

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.cpp

#endif
   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 the new index is not aligned on an 8-byte boundary, adjust the
+    // current index.
+    bool AdjustIndex = (Index - LocalSize) % 8;
+
+    if (AdjustIndex) {
+      // We know there is a 4-byte padding if an 8-byte aligned element has been
+      // inserted and the total size of the 4-byte aligned elements that have
+      // been inserted since the last 8-byte aligned element was inserted is not
+      // a multiple of 4.
+      bool CurrentlyHasPadding = NumBytesAtAlign8 && NumBytesAtAlign4 % 8;
+
+      if (CurrentlyHasPadding) {
+        // There is a 4-byte padding that starts at Index+NumBytesAtAlign4, so
+        // we can remove it and shift the 4-byte elements backwards to make sure
+        // the new element is 8-byte aligned.
+        memmove(&Buffer[Index + 4], &Buffer[Index], NumBytesAtAlign4);
+        Index += 4;
+      } else {
+        // There is no 4-byte padding we can remove, so we have to insert a
+        // 4-byte padding and shift the 4-byte elements forward to make sure
+        // the new element is 8-byte aligned.
         memmove(&Buffer[Index - 4], &Buffer[Index], NumBytesAtAlign4);
         Index -= 4;
       }
+    }
+
     // Forget about any padding.
     NumBytesAtAlign4 = 0;
     NumBytesAtAlign8 += LocalSize;
   } else {
     assert(LocalSize == 0);
   }
 
   Index -= LocalSize;
 
   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);
+}