[Clang][BinaryOperator] memoize ICEKind for BinaryOperator Exprs

[justinstitt]

Summary

When building the Linux Kernel (x86_64) CheckICE is a particularly slow
method which results in 0.815% of all cpu cycles (~63 million cycles).
Much of this is due to repeat checks regarding the ICEKind of binary
expressions.

Storing ICEKind information within BinaryOperator and stopping future
CheckICE calls before they do repeat work shows a net speed increase of
~80% for CheckICE (~14 million cycles).

clang/include/clang/AST/Expr.h

 #include "clang/AST/TemplateBase.h"
 #include "clang/AST/Type.h"
 #include "clang/Basic/CharInfo.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SyncScope.h"
 #include "clang/Basic/TypeTraits.h"
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/APSInt.h"
+#include "llvm/ADT/None.h"
+#include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/AtomicOrdering.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/TrailingObjects.h"
 
public:
   static bool classof(const Stmt *T) {
     return T->getStmtClass() == CStyleCastExprClass;
   }
 
   friend TrailingObjects;
   friend class CastExpr;
 };
 
+namespace {
+
+enum ICEKind {
+  /// This expression is an ICE.
+  IK_ICE,
+  /// This expression is not an ICE, but if it isn't evaluated, it's
+  /// a legal subexpression for an ICE. This return value is used to handle
+  /// the comma operator in C99 mode, and non-constant subexpressions.
+  IK_ICEIfUnevaluated,
+  /// This expression is not an ICE, and is not a legal subexpression for one.
+  IK_NotICE,
+};
+
+}
+
 /// A builtin binary operation expression such as "x + y" or "x <= y".
 ///
 /// This expression node kind describes a builtin binary operation,
 /// such as "x + y" for integer values "x" and "y". The operands will
 /// already have been converted to appropriate types (e.g., by
 /// performing promotions or conversions).
 ///
 /// In C++, where operators may be overloaded, a different kind of
 /// expression node (CXXOperatorCallExpr) is used to express the
 /// invocation of an overloaded operator with operator syntax. Within
 /// a C++ template, whether BinaryOperator or CXXOperatorCallExpr is
 /// used to store an expression "x + y" depends on the subexpressions
 /// for x and y. If neither x or y is type-dependent, and the "+"
 /// operator resolves to a built-in operation, BinaryOperator will be
 /// used to express the computation (x and y may still be
 /// value-dependent). If either x or y is type-dependent, or if the
 /// "+" resolves to an overloaded operator, CXXOperatorCallExpr will
 /// be used to express the computation.
 class BinaryOperator : public Expr {
   enum { LHS, RHS, END_EXPR };
   Stmt *SubExprs[END_EXPR];
+  llvm::Optional<ICEKind> IK = llvm::None;
 
 public:
   typedef BinaryOperatorKind Opcode;
 
+  llvm::Optional<ICEKind> getICEKind() const { return IK; }
+
+  void setICEKind(ICEKind ik) {
+    assert(!IK && "ICEKind is already set.");
+    IK = ik;
+  }
+
 protected:
   size_t offsetOfTrailingStorage() const;
 
   /// Return a pointer to the trailing FPOptions
   FPOptionsOverride *getTrailingFPFeatures() {
     assert(BinaryOperatorBits.HasFPFeatures);
     return reinterpret_cast<FPOptionsOverride *>(
         reinterpret_cast<char *>(this) + offsetOfTrailingStorage());

clang/lib/AST/ExprConstant.cpp

 //
 // Note that to reduce code duplication, this helper does no evaluation
 // itself; the caller checks whether the expression is evaluatable, and
 // in the rare cases where CheckICE actually cares about the evaluated
 // value, it calls into Evaluate.
 
 namespace {
 
-enum ICEKind {
-  /// This expression is an ICE.
-  IK_ICE,
-  /// This expression is not an ICE, but if it isn't evaluated, it's
-  /// a legal subexpression for an ICE. This return value is used to handle
-  /// the comma operator in C99 mode, and non-constant subexpressions.
-  IK_ICEIfUnevaluated,
-  /// This expression is not an ICE, and is not a legal subexpression for one.
-  IK_NotICE
-};
-
 struct ICEDiag {
   ICEKind Kind;
   SourceLocation Loc;
 
   ICEDiag(ICEKind IK, SourceLocation l) : Kind(IK), Loc(l) {}
 };
 
 }
#include "clang/AST/StmtNodes.inc"
   case Expr::UnaryExprOrTypeTraitExprClass: {
     const UnaryExprOrTypeTraitExpr *Exp = cast<UnaryExprOrTypeTraitExpr>(E);
     if ((Exp->getKind() ==  UETT_SizeOf) &&
         Exp->getTypeOfArgument()->isVariableArrayType())
       return ICEDiag(IK_NotICE, E->getBeginLoc());
     return NoDiag();
   }
   case Expr::BinaryOperatorClass: {
-    const BinaryOperator *Exp = cast<BinaryOperator>(E);
+    BinaryOperator *Exp = const_cast<BinaryOperator*>(cast<BinaryOperator>(E));
+    if (auto Result = Exp->getICEKind())
+      return ICEDiag(*Result, E->getBeginLoc());
+
     switch (Exp->getOpcode()) {
     case BO_PtrMemD:
     case BO_PtrMemI:
     case BO_Assign:
     case BO_MulAssign:
     case BO_DivAssign:
     case BO_RemAssign:
     case BO_AddAssign:
     case BO_SubAssign:
     case BO_ShlAssign:
     case BO_ShrAssign:
     case BO_AndAssign:
     case BO_XorAssign:
     case BO_OrAssign:
       // C99 6.6/3 allows assignments within unevaluated subexpressions of
       // constant expressions, but they can never be ICEs because an ICE cannot
       // contain an lvalue operand.
+      Exp->setICEKind(IK_NotICE);
       return ICEDiag(IK_NotICE, E->getBeginLoc());
 
     case BO_Mul:
     case BO_Div:
     case BO_Rem:
     case BO_Add:
     case BO_Sub:
     case BO_Shl:
case BO_Cmp: {
       ICEDiag LHSResult = CheckICE(Exp->getLHS(), Ctx);
       ICEDiag RHSResult = CheckICE(Exp->getRHS(), Ctx);
       if (Exp->getOpcode() == BO_Div ||
           Exp->getOpcode() == BO_Rem) {
         // EvaluateAsRValue gives an error for undefined Div/Rem, so make sure
         // we don't evaluate one.
         if (LHSResult.Kind == IK_ICE && RHSResult.Kind == IK_ICE) {
           llvm::APSInt REval = Exp->getRHS()->EvaluateKnownConstInt(Ctx);
-          if (REval == 0)
+          if (REval == 0) {
+            Exp->setICEKind(IK_ICEIfUnevaluated);
             return ICEDiag(IK_ICEIfUnevaluated, E->getBeginLoc());
+          }
           if (REval.isSigned() && REval.isAllOnes()) {
             llvm::APSInt LEval = Exp->getLHS()->EvaluateKnownConstInt(Ctx);
-            if (LEval.isMinSignedValue())
+            if (LEval.isMinSignedValue()) {
+              Exp->setICEKind(IK_ICEIfUnevaluated);
               return ICEDiag(IK_ICEIfUnevaluated, E->getBeginLoc());
             }
           }
         }
+      }
       if (Exp->getOpcode() == BO_Comma) {
         if (Ctx.getLangOpts().C99) {
           // C99 6.6p3 introduces a strange edge case: comma can be in an ICE
           // if it isn't evaluated.
-          if (LHSResult.Kind == IK_ICE && RHSResult.Kind == IK_ICE)
+          if (LHSResult.Kind == IK_ICE && RHSResult.Kind == IK_ICE) {
+            Exp->setICEKind(IK_ICEIfUnevaluated);
             return ICEDiag(IK_ICEIfUnevaluated, E->getBeginLoc());
+          }
         } else {
           // In both C89 and C++, commas in ICEs are illegal.
+          Exp->setICEKind(IK_NotICE);
           return ICEDiag(IK_NotICE, E->getBeginLoc());
         }
       }
-      return Worst(LHSResult, RHSResult);
+      ICEDiag D = Worst(LHSResult, RHSResult);
+      Exp->setICEKind(D.Kind);
+      return D; 
     }
     case BO_LAnd:
     case BO_LOr: {
       ICEDiag LHSResult = CheckICE(Exp->getLHS(), Ctx);
       ICEDiag RHSResult = CheckICE(Exp->getRHS(), Ctx);
       if (LHSResult.Kind == IK_ICE && RHSResult.Kind == IK_ICEIfUnevaluated) {
         // Rare case where the RHS has a comma "side-effect"; we need
         // to actually check the condition to see whether the side
         // with the comma is evaluated.
         if ((Exp->getOpcode() == BO_LAnd) !=
-            (Exp->getLHS()->EvaluateKnownConstInt(Ctx) == 0))
+            (Exp->getLHS()->EvaluateKnownConstInt(Ctx) == 0)) {
+          Exp->setICEKind(RHSResult.Kind);
           return RHSResult;
+        }
+        Exp->setICEKind(RHSResult.Kind);
         return NoDiag();
       }
-
-      return Worst(LHSResult, RHSResult);
+      ICEDiag WorstResult = Worst(LHSResult, RHSResult);
+      Exp->setICEKind(WorstResult.Kind);
+      return WorstResult; 
     }
     }
     llvm_unreachable("invalid binary operator kind");
   }
   case Expr::ImplicitCastExprClass:
   case Expr::CStyleCastExprClass:
   case Expr::CXXFunctionalCastExprClass:
   case Expr::CXXStaticCastExprClass: