Subzero: Deal with substitutions in the primitive remangler.

src/IceGlobalContext.cpp

 //===- subzero/src/IceGlobalContext.cpp - Global context defs ---*- C++ -*-===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines aspects of the compilation that persist across
 // multiple functions.
 //
 //===----------------------------------------------------------------------===//
 
-#include <ctype.h> // isdigit()
+#include <ctype.h> // isdigit(), isupper()
 
 #include "IceDefs.h"
 #include "IceTypes.h"
 #include "IceCfg.h"
 #include "IceGlobalContext.h"
 #include "IceOperand.h"
 #include "IceTargetLowering.h"
 
 namespace Ice {
 
@@ skipping 87 matching lines @@
 };
 
 GlobalContext::GlobalContext(llvm::raw_ostream *OsDump,
                              llvm::raw_ostream *OsEmit, VerboseMask Mask,
                              TargetArch Arch, OptLevel Opt,
                              IceString TestPrefix)
     : StrDump(OsDump), StrEmit(OsEmit), VMask(Mask),
       ConstPool(new ConstantPool()), Arch(Arch), Opt(Opt),
       TestPrefix(TestPrefix), HasEmittedFirstMethod(false) {}
 
+// Scan a string for S[0-9A-Z]*_ patterns and replace them with
+// S<num>_ where <num> is the next base-36 value.  If a type name
+// legitimately contains that pattern, then the substitution will be
+// made in error and most likely the link will fail.  In this case,
+// the test classes can be rewritten not to use that pattern, which is
+// much simpler and more reliable than implementing a full demangling
+// parser.  Another substitution-in-error may occur if a type
+// identifier ends with the pattern S[0-9A-Z]*, because an immediately
+// following substitution string like "S1_" or "PS1_" may be combined
+// with the previous type.
+void GlobalContext::incrementSubstitutions(ManglerVector &OldName) const {
+  // Provide extra space in case the length of <num> increases.
+  ManglerVector NewName(OldName.size() * 2);
+  size_t OldPos = 0;
+  size_t NewPos = 0;
+  size_t OldLen = OldName.size();
+  for (; OldPos < OldLen; ++OldPos, ++NewPos) {
+    if (OldName[OldPos] == '\0')
+      break;
+    if (OldName[OldPos] == 'S') {
+      // Search forward until we find _ or invalid character (including \0).
+      bool AllZs = true;
+      bool Valid = true;
+      bool Found = false;
+      size_t Last;
+      for (Last = OldPos + 1; Last < OldLen && Valid; ++Last) {

[jvoung (off chromium), 2014/07/11 20:40:08]

There's an explicit break; when Valid is set to false, so could probably leave
this && Valid out?

It also seems like "Found" is the only variable that's checked after the break,
so the "Valid" variable can be removed too?

[Jim Stichnoth, 2014/07/11 21:05:11]

Done.  BTW, it would also be possible to remove the Found variable by moving the
if(Found){...} code inside the if(Ch=='_'){...} block, but I think it's more
readable the current way.

+        char Ch = OldName[Last];
+        if (Ch == '_') {
+          Found = true;
+          break;
+        } else if (std::isdigit(Ch) || std::isupper(Ch)) {

[jvoung (off chromium), 2014/07/11 20:40:08]

Should this explicitly pass as parameter the "C" locale, to make sure this is
just A-Z?

[Jim Stichnoth, 2014/07/11 21:05:12]

Done.

+          if (Ch != 'Z')
+            AllZs = false;
+        } else {
+          // Invalid character, stop searching.
+          Valid = false;
+          break;
+        }
+      }
+      if (Found) {
+        NewName[NewPos++] = OldName[OldPos++]; // 'S'
+        size_t Length = Last - OldPos;
+        // NewPos and OldPos point just past the 'S'.
+        assert(NewName[NewPos - 1] == 'S');
+        assert(OldName[OldPos - 1] == 'S');
+        assert(OldName[OldPos + Length] == '_');
+        if (AllZs) {
+          // Replace N 'Z' characters with N+1 '0' characters.

[jvoung (off chromium), 2014/07/11 20:40:08]

This case also handles the "S_" ?

[Jim Stichnoth, 2014/07/11 21:05:11]

Yes.  Added a comment to clarify.

+          for (size_t i = 0; i < Length + 1; ++i) {
+            NewName[NewPos++] = '0';
+          }
+        } else {
+          // Iterate right-to-left and increment the base-36 number.
+          bool Carry = true;
+          for (size_t i = 0; i < Length; ++i) {
+            size_t Offset = Length - 1 - i;
+            char Ch = OldName[OldPos + Offset];
+            if (Carry) {
+              Carry = false;
+              switch (Ch) {
+              case '9':
+                Ch = 'A';
+                break;
+              case 'Z':
+                Ch = '0';
+                Carry = true;
+                break;
+              default:
+                ++Ch;
+                break;
+              }
+            }
+            NewName[NewPos + Offset] = Ch;
+          }
+          NewPos += Length;
+        }
+        OldPos = Last;
+        // Fall through and let the '_' be copied across.
+      }
+    }
+    NewName[NewPos] = OldName[OldPos];
+  }
+  assert(NewName[NewPos] == '\0');
+  OldName = NewName;
+}
+
 // In this context, name mangling means to rewrite a symbol using a
 // given prefix.  For a C++ symbol, nest the original symbol inside
 // the "prefix" namespace.  For other symbols, just prepend the
 // prefix.
 IceString GlobalContext::mangleName(const IceString &Name) const {
   // An already-nested name like foo::bar() gets pushed down one
   // level, making it equivalent to Prefix::foo::bar().
   //   _ZN3foo3barExyz ==> _ZN6Prefix3foo3barExyz
   // A non-nested but mangled name like bar() gets nested, making it
   // equivalent to Prefix::bar().
   //   _Z3barxyz ==> ZN6Prefix3barExyz
   // An unmangled, extern "C" style name, gets a simple prefix:
   //   bar ==> Prefixbar
   if (getTestPrefix().empty())
     return Name;
 
   unsigned PrefixLength = getTestPrefix().length();
-  llvm::SmallVector<char, 32> NameBase(1 + Name.length());
+  ManglerVector NameBase(1 + Name.length());
   const size_t BufLen = 30 + Name.length() + PrefixLength;
-  llvm::SmallVector<char, 32> NewName(BufLen);
+  ManglerVector NewName(BufLen);
   uint32_t BaseLength = 0; // using uint32_t due to sscanf format string
 
   int ItemsParsed = sscanf(Name.c_str(), "_ZN%s", NameBase.data());
   if (ItemsParsed == 1) {
     // Transform _ZN3foo3barExyz ==> _ZN6Prefix3foo3barExyz
     //   (splice in "6Prefix")          ^^^^^^^
     snprintf(NewName.data(), BufLen, "_ZN%u%s%s", PrefixLength,
              getTestPrefix().c_str(), NameBase.data());
     // We ignore the snprintf return value (here and below).  If we
     // somehow miscalculated the output buffer length, the output will
     // be truncated, but it will be truncated consistently for all
     // mangleName() calls on the same input string.
+    incrementSubstitutions(NewName);
     return NewName.data();
   }
 
   // Artificially limit BaseLength to 9 digits (less than 1 billion)
   // because sscanf behavior is undefined on integer overflow.  If
   // there are more than 9 digits (which we test by looking at the
   // beginning of NameBase), then we consider this a failure to parse
   // a namespace mangling, and fall back to the simple prefixing.
   ItemsParsed = sscanf(Name.c_str(), "_Z%9u%s", &BaseLength, NameBase.data());
   if (ItemsParsed == 2 && BaseLength <= strlen(NameBase.data()) &&
       !isdigit(NameBase[0])) {
     // Transform _Z3barxyz ==> _ZN6Prefix3barExyz
     //                           ^^^^^^^^    ^
     // (splice in "N6Prefix", and insert "E" after "3bar")
     // But an "I" after the identifier indicates a template argument
     // list terminated with "E"; insert the new "E" before/after the
     // old "E".  E.g.:
     // Transform _Z3barIabcExyz ==> _ZN6Prefix3barIabcEExyz
     //                                ^^^^^^^^         ^
     // (splice in "N6Prefix", and insert "E" after "3barIabcE")
-    llvm::SmallVector<char, 32> OrigName(Name.length());
-    llvm::SmallVector<char, 32> OrigSuffix(Name.length());
+    ManglerVector OrigName(Name.length());
+    ManglerVector OrigSuffix(Name.length());
     uint32_t ActualBaseLength = BaseLength;
     if (NameBase[ActualBaseLength] == 'I') {
       ++ActualBaseLength;
       while (NameBase[ActualBaseLength] != 'E' &&
              NameBase[ActualBaseLength] != '\0')
         ++ActualBaseLength;
     }
     strncpy(OrigName.data(), NameBase.data(), ActualBaseLength);
     OrigName[ActualBaseLength] = '\0';
     strcpy(OrigSuffix.data(), NameBase.data() + ActualBaseLength);
     snprintf(NewName.data(), BufLen, "_ZN%u%s%u%sE%s", PrefixLength,
              getTestPrefix().c_str(), BaseLength, OrigName.data(),
              OrigSuffix.data());
+    incrementSubstitutions(NewName);
     return NewName.data();
   }
 
   // Transform bar ==> Prefixbar
   //                   ^^^^^^
   return getTestPrefix() + Name;
 }
 
 GlobalContext::~GlobalContext() {}
 
@@ skipping 86 matching lines @@
 
 void Timer::printElapsedUs(GlobalContext *Ctx, const IceString &Tag) const {
   if (Ctx->isVerbose(IceV_Timing)) {
     // Prefixing with '#' allows timing strings to be included
     // without error in textual assembly output.
     Ctx->getStrDump() << "# " << getElapsedUs() << " usec " << Tag << "\n";
   }
 }
 
 } // end of namespace Ice