[AST] Store the value of CharacterLiteral in the bit-fields of Stmt if possible

[riccibruno]

Summary

The vast majority of CharacterLiterals have a value which fits into 8 bits
(in the 2666 CharacterLiterals in all of Boost, only 2 don't).
When possible, use the space in the bit-fields of Stmt to store the value
and otherwise store it in a trailing object.

This saves 1 pointer per CharacterLiteral when the value fits into 8 bits.

Note that in itself this do not save that much space, but this is part of
a larger effort to pack the statements/expressions classes.

[shafik]

include/clang/AST/Expr.h

1407

Minor comment, does it make sense to covert this to a scoped enum since it looks like it is being strictly used as a set of values.

[riccibruno]

include/clang/AST/Expr.h

1407

Does it really add anything ?
It means that instead of writing CharacterLiteral::UTF32
you have to write CharacterLiteral::CharacterKind::UTF32

Seems a bit verbose. But I don't have any strong opinion on this.

[shafik]

include/clang/AST/Expr.h

1407

It adds the protection against unintended conversions to and from the scoped enum, which in general is a good thing. The other benefits is not having the enumerators leak out into the surrounding scope but is limited in this case.

It does add verbosity though.

[riccibruno]

This is not worth doing.

include/clang/AST/Expr.h

public:
   child_range children() {
     return child_range(child_iterator(), child_iterator());
   }
   const_child_range children() const {
     return const_child_range(const_child_iterator(), const_child_iterator());
   }
 };
 
-class CharacterLiteral : public Expr {
-public:
-  enum CharacterKind {
-    Ascii,
-    Wide,
-    UTF8,
-    UTF16,
-    UTF32
-  };
+class CharacterLiteral final
+    : public Expr,
+      private llvm::TrailingObjects<CharacterLiteral, unsigned> {
+  friend class ASTReader;
+  friend class ASTStmtReader;
+  friend TrailingObjects;
 
-private:
-  unsigned Value;
-  SourceLocation Loc;
 public:
-  // type should be IntTy
-  CharacterLiteral(unsigned value, CharacterKind kind, QualType type,
-                   SourceLocation l)
-    : Expr(CharacterLiteralClass, type, VK_RValue, OK_Ordinary, false, false,
-           false, false),
-      Value(value), Loc(l) {
-    CharacterLiteralBits.Kind = kind;
-  }
+  enum CharacterKind { Ascii, Wide, UTF8, UTF16, UTF32 };
 
-  /// Construct an empty character literal.
-  CharacterLiteral(EmptyShell Empty) : Expr(CharacterLiteralClass, Empty) { }
+private:
+  // The vast majority of character literals have a value which fits into
+  // 8 bits. For this reason in the common case the value is stored inline
+  // in CharacterLiteralBits and isSmallValue() is true. Otherwise the
+  // value is stored in a trailing unsigned and isSmallValue() is false.
+  // Note that the kind of the character literal do not matter for this.
+  // It is therefore perfectly possible to have an UTF32 character literal
+  // with its value stored inline, as long as the value is <= MaxSmallValue.
+  enum { MaxSmallValue = 255 };
+  static bool isSmallValue(unsigned Val) { return Val <= MaxSmallValue; }
+
+  /// True if the value of this character literal is stored inline.
+  bool isSmallValue() const { return CharacterLiteralBits.IsSmallValue; }
+
+
+  void setValue(unsigned Val) {
+    if (isSmallValue()) {
+      assert(isSmallValue(Val) &&
+             "This value is too large to be stored in this CharacterLiteral!");
+      CharacterLiteralBits.SmallValue = Val;
+    } else
+      *getTrailingObjects<unsigned>() = Val;
+  }
+
+  // Build a character literal.
+  CharacterLiteral(unsigned Value, CharacterKind Kind, QualType Type,
+                   SourceLocation Loc);
+
+  /// Build an empty character literal.
+  CharacterLiteral(EmptyShell Empty, bool IsSmallValue);
+
+public:
+  /// Create a character literal.
+  static CharacterLiteral *Create(const ASTContext &Ctx, unsigned Value,
+                                  CharacterKind Kind, QualType Type,
+                                  SourceLocation Loc);
+
+  /// Create a character literal, optionally with storage for a large value.
+  static CharacterLiteral *CreateEmpty(const ASTContext &Ctx,
+                                       bool IsSmallValue);
 
-  SourceLocation getLocation() const { return Loc; }
+  SourceLocation getLocation() const { return CharacterLiteralBits.Loc; }
   CharacterKind getKind() const {
     return static_cast<CharacterKind>(CharacterLiteralBits.Kind);
   }
 
-  SourceLocation getBeginLoc() const LLVM_READONLY { return Loc; }
-  SourceLocation getEndLoc() const LLVM_READONLY { return Loc; }
-
-  unsigned getValue() const { return Value; }
+  SourceLocation getBeginLoc() const { return getLocation(); }
+  SourceLocation getEndLoc() const { return getLocation(); }
 
-  void setLocation(SourceLocation Location) { Loc = Location; }
-  void setKind(CharacterKind kind) { CharacterLiteralBits.Kind = kind; }
-  void setValue(unsigned Val) { Value = Val; }
+  unsigned getValue() const {
+    return isSmallValue() ? CharacterLiteralBits.SmallValue
+                          : *getTrailingObjects<unsigned>();
+  }
 
   static bool classof(const Stmt *T) {
     return T->getStmtClass() == CharacterLiteralClass;
   }
 
   // Iterators
   child_range children() {
     return child_range(child_iterator(), child_iterator());

include/clang/AST/Stmt.h

class StringLiteralBitfields {
     unsigned IsPascal : 1;
 
     /// The number of concatenated token this string is made of.
     /// This is the number of trailing SourceLocation.
     unsigned NumConcatenated;
   };
 
   class CharacterLiteralBitfields {
+    friend class ASTStmtReader;
     friend class CharacterLiteral;
 
     unsigned : NumExprBits;
 
     unsigned Kind : 3;
+
+    /// The vast majority of character literals have a value which fits into
+    /// 8 bits. In this case this value is stored here and IsSmallValue
+    /// is true. Otherwise, the value is stored as a trailing object and
+    /// IsSmallValue is false.
+    unsigned SmallValue : 8;
+    unsigned IsSmallValue : 1;
+
+    SourceLocation Loc;
   };
 
   enum APFloatSemantics {
     IEEEhalf,
     IEEEsingle,
     IEEEdouble,
     x87DoubleExtended,
     IEEEquad,

lib/AST/ASTImporter.cpp

ExpectedStmt ASTNodeImporter::VisitCharacterLiteral(CharacterLiteral *E) {
   ExpectedType ToTypeOrErr = import(E->getType());
   if (!ToTypeOrErr)
     return ToTypeOrErr.takeError();
 
   ExpectedSLoc ToLocationOrErr = import(E->getLocation());
   if (!ToLocationOrErr)
     return ToLocationOrErr.takeError();
 
-  return new (Importer.getToContext()) CharacterLiteral(
-      E->getValue(), E->getKind(), *ToTypeOrErr, *ToLocationOrErr);
+  return CharacterLiteral::Create(Importer.getToContext(), E->getValue(),
+                                  E->getKind(), *ToTypeOrErr, *ToLocationOrErr);
 }
 
 ExpectedStmt ASTNodeImporter::VisitStringLiteral(StringLiteral *E) {
   ExpectedType ToTypeOrErr = import(E->getType());
   if (!ToTypeOrErr)
     return ToTypeOrErr.takeError();
 
   SmallVector<SourceLocation, 4> ToLocations(E->getNumConcatenated());

lib/AST/Expr.cpp

std::string FixedPointLiteral::getValueAsString(unsigned Radix) const {
   // unsigned long _Accum: 4294967295.99999999976716935634613037109375
   // which is 43 characters.
   SmallString<64> S;
   FixedPointValueToString(
       S, llvm::APSInt::getUnsigned(getValue().getZExtValue()), Scale);
   return S.str();
 }
 
+CharacterLiteral::CharacterLiteral(unsigned Value, CharacterKind Kind,
+                                   QualType Type, SourceLocation Loc)
+    : Expr(CharacterLiteralClass, Type, VK_RValue, OK_Ordinary, false, false,
+           false, false) {
+  CharacterLiteralBits.Kind = Kind;
+  CharacterLiteralBits.Loc = Loc;
+  CharacterLiteralBits.IsSmallValue = isSmallValue(Value);
+  setValue(Value);
+}
+
+CharacterLiteral::CharacterLiteral(EmptyShell Empty, bool IsSmallValue)
+    : Expr(CharacterLiteralClass, Empty) {
+  CharacterLiteralBits.IsSmallValue = IsSmallValue;
+}
+
+CharacterLiteral *CharacterLiteral::Create(const ASTContext &Ctx,
+                                           unsigned Value, CharacterKind Kind,
+                                           QualType Type, SourceLocation Loc) {
+  bool IsSmallValue = isSmallValue(Value);
+  void *Mem = Ctx.Allocate(totalSizeToAlloc<unsigned>(!IsSmallValue),
+                           alignof(CharacterLiteral));
+  return new (Mem) CharacterLiteral(Value, Kind, Type, Loc);
+}
+
+CharacterLiteral *CharacterLiteral::CreateEmpty(const ASTContext &Ctx,
+                                                bool IsSmallValue) {
+  void *Mem = Ctx.Allocate(totalSizeToAlloc<unsigned>(!IsSmallValue),
+                           alignof(CharacterLiteral));
+  return new (Mem) CharacterLiteral(EmptyShell(), IsSmallValue);
+}
+
 FloatingLiteral::FloatingLiteral(const ASTContext &C, const llvm::APFloat &V,
                                  bool isexact, QualType Type, SourceLocation L)
   : Expr(FloatingLiteralClass, Type, VK_RValue, OK_Ordinary, false, false,
          false, false), Loc(L) {
   setSemantics(V.getSemantics());
   FloatingLiteralBits.IsExact = isexact;
   setValue(C, V);
 }

lib/Sema/SemaExpr.cpp

if (Literal.isWide())
     Kind = CharacterLiteral::Wide;
   else if (Literal.isUTF16())
     Kind = CharacterLiteral::UTF16;
   else if (Literal.isUTF32())
     Kind = CharacterLiteral::UTF32;
   else if (Literal.isUTF8())
     Kind = CharacterLiteral::UTF8;
 
-  Expr *Lit = new (Context) CharacterLiteral(Literal.getValue(), Kind, Ty,
-                                             Tok.getLocation());
+  Expr *Lit = CharacterLiteral::Create(Context, Literal.getValue(), Kind, Ty,
 
   if (Literal.getUDSuffix().empty())
     return Lit;
 
   // We're building a user-defined literal.
   IdentifierInfo *UDSuffix = &Context.Idents.get(Literal.getUDSuffix());
   SourceLocation UDSuffixLoc =
     getUDSuffixLoc(*this, Tok.getLocation(), Literal.getUDSuffixOffset());
ExprResult Sema::ActOnObjCAvailabilityCheckExpr(
   if (getCurFunctionOrMethodDecl())
     getEnclosingFunction()->HasPotentialAvailabilityViolations = true;
   else if (getCurBlock() || getCurLambda())
     getCurFunction()->HasPotentialAvailabilityViolations = true;
 
   return new (Context)
       ObjCAvailabilityCheckExpr(Version, AtLoc, RParen, Context.BoolTy);
 }
 No newline at end of file

lib/Sema/SemaTemplate.cpp

else if (T->isChar8Type() && getLangOpts().Char8)
       Kind = CharacterLiteral::UTF8;
     else if (T->isChar16Type())
       Kind = CharacterLiteral::UTF16;
     else if (T->isChar32Type())
       Kind = CharacterLiteral::UTF32;
     else
       Kind = CharacterLiteral::Ascii;
 
-    E = new (Context) CharacterLiteral(Arg.getAsIntegral().getZExtValue(),
-                                       Kind, T, Loc);
+    E = CharacterLiteral::Create(Context, Arg.getAsIntegral().getZExtValue(),
+
   } else if (T->isBooleanType()) {
     E = new (Context) CXXBoolLiteralExpr(Arg.getAsIntegral().getBoolValue(),
                                          T, Loc);
   } else if (T->isNullPtrType()) {
     E = new (Context) CXXNullPtrLiteralExpr(Context.NullPtrTy, Loc);
   } else {
     E = IntegerLiteral::Create(Context, Arg.getAsIntegral(), T, Loc);
   }

lib/Serialization/ASTReaderStmt.cpp

void ASTStmtReader::VisitStringLiteral(StringLiteral *E) {
   char *StrData = E->getStrDataAsChar();
   for (unsigned I = 0; I < Length * CharByteWidth; ++I)
     StrData[I] = Record.readInt();
 }
 
 void ASTStmtReader::VisitCharacterLiteral(CharacterLiteral *E) {
   VisitExpr(E);
   E->setValue(Record.readInt());
-  E->setLocation(ReadSourceLocation());
-  E->setKind(static_cast<CharacterLiteral::CharacterKind>(Record.readInt()));
+  E->CharacterLiteralBits.Loc = ReadSourceLocation();
+  E->CharacterLiteralBits.Kind = Record.readInt();
 }
 
 void ASTStmtReader::VisitParenExpr(ParenExpr *E) {
   VisitExpr(E);
   E->setLParen(ReadSourceLocation());
   E->setRParen(ReadSourceLocation());
   E->setSubExpr(Record.readSubExpr());
 }
case EXPR_STRING_LITERAL:
       S = StringLiteral::CreateEmpty(
           Context,
           /* NumConcatenated=*/Record[ASTStmtReader::NumExprFields + 0],
           /* Length=*/Record[ASTStmtReader::NumExprFields + 1],
           /* CharByteWidth=*/Record[ASTStmtReader::NumExprFields + 2]);
       break;
 
     case EXPR_CHARACTER_LITERAL:
-      S = new (Context) CharacterLiteral(Empty);
+      S = CharacterLiteral::CreateEmpty(
+          Context,
+          /* IsSmallValue=*/CharacterLiteral::isSmallValue(
+              Record[ASTStmtReader::NumExprFields + 0]));
       break;
 
     case EXPR_PAREN:
       S = new (Context) ParenExpr(Empty);
       break;
 
     case EXPR_PAREN_LIST:
       S = ParenListExpr::CreateEmpty(