[clang] Add time profile for constant evaluation

[Izaron]

Summary

Add time profiler for various constexpr evaluation events
so that slow event could be visible on the visualized flame chart.

[Izaron]

We can use this file as an example: ConstProfiler.cpp https://reviews.llvm.org/P8296
The code does a really big constant evaluation.

This is the generated json before the patch: before.json https://reviews.llvm.org/P8294
Giving this json to https://www.speedscope.app/, we get a big empty gap where the constant evaluation is being done.
link to screenshot

This is the generated json after the patch: after.json https://reviews.llvm.org/P8295
The empty gap is filled with four events.
link to screenshot

You can use this command for generating the json:

clang++ ConstProfiler.cpp -std=c++20 -c -ftime-trace -ftime-trace-granularity=50

P.S. I'm not sure how to write tests to cover the patch, but I'll find this out =)

[jloser]

I like the idea of this — +1 for the direction. I'd like to see some tests through before I approve.

Thanks for working on this!

[tbaeder]

clang/lib/AST/ExprConstant.cpp

15289

what about Expr::EvaluateASRvalue and Expr::isPotentialConstantExpression?

[aaron.ballman]

Thank you for working on this, having more detailed timing information for where we're spending time in the frontend will really help us to evaluate where we need to work on frontend performance.

clang/lib/AST/ExprConstant.cpp

15289

Agreed; I think we should cover all the Expr::Evaluate* functions as well as related potentially expensive constant expression functions like Expr::isPotentialConstantExpression and Expr::isIntegerConstantExpr.

clang/lib/Sema/SemaDeclCXX.cpp

1740–1746 ↗

(On Diff #468028)

Huh, I'm a bit surprised that the checking in this function isn't dominated by the time spent in Expr::isPotentialConstantExpr() -- if you add the time tracing to all of the constant expression evaluation functions, do you still need a time trace here in Sema?

clang/lib/Sema/SemaExpr.cpp

17544 ↗

(On Diff #468028)

Why not push this down into EvaluateAsConstantExpr()? (Then the name you give the scope will also be more accurate.)

[Izaron]

Add time profiler test.

[Izaron]

In D136022#3861245, @jloser wrote:

I'd like to see some tests through before I approve.

Thanks for the greenlight!

I added a test that compiles a chunk of code and then checks the time trace graph in a human-readable form.

clang/lib/Sema/SemaDeclCXX.cpp

1740–1746 ↗

(On Diff #468028)

Thanks! Removed trace here, added to Expr::isPotentialConstantExpr(). This method is called inside of CheckConstexprFunctionDefinition and really takes almost all the time.

clang/lib/Sema/SemaExpr.cpp

17544 ↗

(On Diff #468028)

Thanks! I wrote on this level because I didn't manage to get SemaRef.getSourceManager() without SemaRef (we pass down SemaRef.getASTContext()).

Anyway I found out that we can use SemaRef.getASTContext().getSourceManager() =)

[Izaron]

The test doesn't cover exactly all new traces though. For example I couldn't write a code that runs into the EvaluateAsInt method 🤔

If you have an idea for some funky constexpr code that can be tested, please write here =)

[Izaron]

Fix CMakeLists.txt

[Izaron]

Fix optionals with value_or

[aaron.ballman]

clang/unittests/Support/TimeProfilerTest.cpp

198–199

This bit worries me because I suspect we'll get pretty wide variation between test bots in the build lab. Do you have an idea of how likely it is that this test will have different behavior depending on the machine?

[Izaron]

clang/unittests/Support/TimeProfilerTest.cpp

198–199

I'd say, the test's outcome varies if behaviour of CompilerInstance varies. From my (imperfect) understanding of Clang/LLVM's architecture, its interface is pretty hermetic and we won't get inconsistent behaviour depending on the current machine as soon as we ran Compiler.ExecuteAction(Action);.
Since the code is machine-independents, I expect the same behaviour everywhere.

If we look on other tests, there are tests that seemingly take the machine's target triple https://github.com/llvm/llvm-project/blob/3fee9358baab54e4ed646a106297e7fb6f1b4cff/clang/unittests/CodeGen/TestCompiler.h#L40-L48 to fill some info in CompilerInstance.

But this is not the case in our test. Seems like the AST parsing is machine-independent 😃

[aaron.ballman]

LGTM! Please be sure to add a release note to alert folks to the time profiler becoming more awesome. :-)

clang/unittests/Support/TimeProfilerTest.cpp

198–199

Excellent, thank you for the explanation!

[Izaron]

Mention this in the release notes. Thanks to Aaron for reviewing!

[thakis]

clang/unittests/Support/TimeProfilerTest.cpp

11

Why is this in clang/unittests/Support (a new binary to boot)? This doesn't use any code form clang/lib/Support as far as I can tell.

[Izaron]

clang/unittests/Support/TimeProfilerTest.cpp

11

It uses code from llvm/Support.

There are already tests with similar names: clang/unittest/CodeGen and llvm/unittests/CodeGen, both are pretty close in spirit.

So I decided to make clang/unittests/Support as a counterpart to llvm/unittests/Support. There is a time profiler test too - https://github.com/llvm/llvm-project/blob/main/llvm/unittests/Support/TimeProfilerTest.cpp

[dyung]

Hi @Izaron, several of our internal tests that run tests using -ftime-trace started crashing when run which I bisected back to your change. I have filed issue #58551 for it, can you take a look?

[Izaron]

In D136022#3877399, @dyung wrote:

Hi @Izaron, several of our internal tests that run tests using -ftime-trace started crashing when run which I bisected back to your change. I have filed issue #58551 for it, can you take a look?

Hi! Thank you for filling the issue! I will fix it as soon as I can!

[Trass3r]

Thanks for this!
When I experimented with this for #42754 I also came across functions like
Expr::isConstantInitializer
ExprConstant.cpp HandleFunctionCall/HandleConstructorCall
ByteCodeEmitter::compileFunc

Worth checking out if these are already covered or potentially useful.

clang/docs/ReleaseNotes.rst

- Default configuration paths were partially changed. Clang now attempts to load
   in the executable.
 - If the environment variable ``SOURCE_DATE_EPOCH`` is set, it specifies a UNIX
   timestamp to be used in replacement of the current date and time in
   the ``__DATE__``, ``__TIME__``, and ``__TIMESTAMP__`` macros. See
   `<https://reproducible-builds.org/docs/source-date-epoch/>`_.
 - Clang now supports ``__has_constexpr_builtin`` function-like macro that
   evaluates to 1 if the builtin is supported and can be constant evaluated.
   It can be used to writing conditionally constexpr code that uses builtins.
+- The time profiler (using ``-ftime-trace`` option) now traces various constant
+  evaluation events.
 
 New Compiler Flags
 ------------------
 
 - Implemented `-fcoro-aligned-allocation` flag. This flag implements
   Option 2 of P2014R0 aligned allocation of coroutine frames
   (`P2014R0 <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p2014r0.pdf>`_).
   With this flag, the coroutines will try to lookup aligned allocation

clang/lib/AST/ExprConstant.cpp

 #include "clang/AST/TypeLoc.h"
 #include "clang/Basic/Builtins.h"
 #include "clang/Basic/TargetInfo.h"
 #include "llvm/ADT/APFixedPoint.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallBitVector.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/SaveAndRestore.h"
+#include "llvm/Support/TimeProfiler.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cstring>
 #include <functional>
 
 #define DEBUG_TYPE "exprconstant"
 
 using namespace clang;
 using llvm::APFixedPoint;
public:
     }
     ~ThisOverrideRAII() {
       Frame.This = OldThis;
     }
   private:
     CallStackFrame &Frame;
     const LValue *OldThis;
   };
+
+  // A shorthand time trace scope struct, prints source range, for example
+  // {"name":"EvaluateAsRValue","args":{"detail":"<test.cc:8:21, col:25>"}}}
+  class ExprTimeTraceScope {
+  public:
+    ExprTimeTraceScope(const Expr *E, const ASTContext &Ctx, StringRef Name)
+        : TimeScope(Name, [E, &Ctx] {
+            return E->getSourceRange().printToString(Ctx.getSourceManager());
+          }) {}
+
+  private:
+    llvm::TimeTraceScope TimeScope;
+  };
 }
 
 static bool HandleDestruction(EvalInfo &Info, const Expr *E,
                               const LValue &This, QualType ThisType);
 static bool HandleDestruction(EvalInfo &Info, SourceLocation Loc,
                               APValue::LValueBase LVBase, APValue &Value,
                               QualType T);
 

 /// any crazy technique (that has nothing to do with language standards) that
 /// we want to.  If this function returns true, it returns the folded constant
 /// in Result. If this expression is a glvalue, an lvalue-to-rvalue conversion
 /// will be applied to the result.
 bool Expr::EvaluateAsRValue(EvalResult &Result, const ASTContext &Ctx,
                             bool InConstantContext) const {
   assert(!isValueDependent() &&
          "Expression evaluator can't be called on a dependent expression.");
+  ExprTimeTraceScope TimeScope(this, Ctx, "EvaluateAsRValue");
   EvalInfo Info(Ctx, Result, EvalInfo::EM_IgnoreSideEffects);
   Info.InConstantContext = InConstantContext;
   return ::EvaluateAsRValue(this, Result, Ctx, Info);
 }
 
 bool Expr::EvaluateAsBooleanCondition(bool &Result, const ASTContext &Ctx,
                                       bool InConstantContext) const {
   assert(!isValueDependent() &&
          "Expression evaluator can't be called on a dependent expression.");
+  ExprTimeTraceScope TimeScope(this, Ctx, "EvaluateAsBooleanCondition");
   EvalResult Scratch;
   return EvaluateAsRValue(Scratch, Ctx, InConstantContext) &&
          HandleConversionToBool(Scratch.Val, Result);
 }
 
 bool Expr::EvaluateAsInt(EvalResult &Result, const ASTContext &Ctx,
                          SideEffectsKind AllowSideEffects,
                          bool InConstantContext) const {
   assert(!isValueDependent() &&
          "Expression evaluator can't be called on a dependent expression.");
+  ExprTimeTraceScope TimeScope(this, Ctx, "EvaluateAsInt");
   EvalInfo Info(Ctx, Result, EvalInfo::EM_IgnoreSideEffects);
   Info.InConstantContext = InConstantContext;
   return ::EvaluateAsInt(this, Result, Ctx, AllowSideEffects, Info);
 }
 
 bool Expr::EvaluateAsFixedPoint(EvalResult &Result, const ASTContext &Ctx,
                                 SideEffectsKind AllowSideEffects,
                                 bool InConstantContext) const {
   assert(!isValueDependent() &&
          "Expression evaluator can't be called on a dependent expression.");
+  ExprTimeTraceScope TimeScope(this, Ctx, "EvaluateAsFixedPoint");
   EvalInfo Info(Ctx, Result, EvalInfo::EM_IgnoreSideEffects);
   Info.InConstantContext = InConstantContext;
   return ::EvaluateAsFixedPoint(this, Result, Ctx, AllowSideEffects, Info);
 }
 
 bool Expr::EvaluateAsFloat(APFloat &Result, const ASTContext &Ctx,
                            SideEffectsKind AllowSideEffects,
                            bool InConstantContext) const {
   assert(!isValueDependent() &&
          "Expression evaluator can't be called on a dependent expression.");
 
   if (!getType()->isRealFloatingType())
     return false;
 
+  ExprTimeTraceScope TimeScope(this, Ctx, "EvaluateAsFloat");
   EvalResult ExprResult;
   if (!EvaluateAsRValue(ExprResult, Ctx, InConstantContext) ||
       !ExprResult.Val.isFloat() ||
       hasUnacceptableSideEffect(ExprResult, AllowSideEffects))
     return false;
 
   Result = ExprResult.Val.getFloat();
   return true;
 }
 
 bool Expr::EvaluateAsLValue(EvalResult &Result, const ASTContext &Ctx,
                             bool InConstantContext) const {
   assert(!isValueDependent() &&
          "Expression evaluator can't be called on a dependent expression.");
 
+  ExprTimeTraceScope TimeScope(this, Ctx, "EvaluateAsLValue");
   EvalInfo Info(Ctx, Result, EvalInfo::EM_ConstantFold);
   Info.InConstantContext = InConstantContext;
   LValue LV;
   CheckedTemporaries CheckedTemps;
   if (!EvaluateLValue(this, LV, Info) || !Info.discardCleanups() ||
       Result.HasSideEffects ||
       !CheckLValueConstantExpression(Info, getExprLoc(),
                                      Ctx.getLValueReferenceType(getType()), LV,
static bool EvaluateDestruction(const ASTContext &Ctx, APValue::LValueBase Base,
   return true;
 }
 
 bool Expr::EvaluateAsConstantExpr(EvalResult &Result, const ASTContext &Ctx,
                                   ConstantExprKind Kind) const {
   assert(!isValueDependent() &&
          "Expression evaluator can't be called on a dependent expression.");
 
+  ExprTimeTraceScope TimeScope(this, Ctx, "EvaluateAsConstantExpr");
   EvalInfo::EvaluationMode EM = EvalInfo::EM_ConstantExpression;
   EvalInfo Info(Ctx, Result, EM);
   Info.InConstantContext = true;
 
   // The type of the object we're initializing is 'const T' for a class NTTP.
   QualType T = getType();
   if (Kind == ConstantExprKind::ClassTemplateArgument)
     T.addConst();

 
 bool Expr::EvaluateAsInitializer(APValue &Value, const ASTContext &Ctx,
                                  const VarDecl *VD,
                                  SmallVectorImpl<PartialDiagnosticAt> &Notes,
                                  bool IsConstantInitialization) const {
   assert(!isValueDependent() &&
          "Expression evaluator can't be called on a dependent expression.");
 
+  llvm::TimeTraceScope TimeScope("EvaluateAsInitializer", [&] {
+    std::string Name;
+    llvm::raw_string_ostream OS(Name);
+    VD->printQualifiedName(OS);
+    return Name;
+  });
+
   // FIXME: Evaluating initializers for large array and record types can cause
   // performance problems. Only do so in C++11 for now.
   if (isPRValue() && (getType()->isArrayType() || getType()->isRecordType()) &&
       !Ctx.getLangOpts().CPlusPlus11)
     return false;
 
   Expr::EvalStatus EStatus;
   EStatus.Diag = &Notes;
return EvaluateAsRValue(Result, Ctx, /* in constant context */ true) &&
          !hasUnacceptableSideEffect(Result, SEK);
 }
 
 APSInt Expr::EvaluateKnownConstInt(const ASTContext &Ctx,
                     SmallVectorImpl<PartialDiagnosticAt> *Diag) const {
   assert(!isValueDependent() &&
          "Expression evaluator can't be called on a dependent expression.");
 
+  ExprTimeTraceScope TimeScope(this, Ctx, "EvaluateKnownConstInt");
   EvalResult EVResult;
   EVResult.Diag = Diag;
   EvalInfo Info(Ctx, EVResult, EvalInfo::EM_IgnoreSideEffects);
   Info.InConstantContext = true;
 
   bool Result = ::EvaluateAsRValue(this, EVResult, Ctx, Info);
   (void)Result;
   assert(Result && "Could not evaluate expression");
   assert(EVResult.Val.isInt() && "Expression did not evaluate to integer");
 
   return EVResult.Val.getInt();
 }
 
 APSInt Expr::EvaluateKnownConstIntCheckOverflow(
     const ASTContext &Ctx, SmallVectorImpl<PartialDiagnosticAt> *Diag) const {
   assert(!isValueDependent() &&
          "Expression evaluator can't be called on a dependent expression.");
 
+  ExprTimeTraceScope TimeScope(this, Ctx, "EvaluateKnownConstIntCheckOverflow");
   EvalResult EVResult;
   EVResult.Diag = Diag;
   EvalInfo Info(Ctx, EVResult, EvalInfo::EM_IgnoreSideEffects);
   Info.InConstantContext = true;
   Info.CheckingForUndefinedBehavior = true;
 
   bool Result = ::EvaluateAsRValue(Info, this, EVResult.Val);
   (void)Result;
   assert(Result && "Could not evaluate expression");
   assert(EVResult.Val.isInt() && "Expression did not evaluate to integer");
 
   return EVResult.Val.getInt();
 }
 
 void Expr::EvaluateForOverflow(const ASTContext &Ctx) const {
   assert(!isValueDependent() &&
          "Expression evaluator can't be called on a dependent expression.");
 
+  ExprTimeTraceScope TimeScope(this, Ctx, "EvaluateForOverflow");
   bool IsConst;
   EvalResult EVResult;
   if (!FastEvaluateAsRValue(this, EVResult, Ctx, IsConst)) {
     EvalInfo Info(Ctx, EVResult, EvalInfo::EM_IgnoreSideEffects);
     Info.CheckingForUndefinedBehavior = true;
     (void)::EvaluateAsRValue(Info, this, EVResult.Val);
   }
 }
static bool EvaluateCPlusPlus11IntegralConstantExpr(const ASTContext &Ctx,
   return true;
 }
 
 bool Expr::isIntegerConstantExpr(const ASTContext &Ctx,
                                  SourceLocation *Loc) const {
   assert(!isValueDependent() &&
          "Expression evaluator can't be called on a dependent expression.");
 
+  llvm::TimeTraceScope TimeScope("isIntegerConstantExpr", [&] {
+    return Loc->printToString(Ctx.getSourceManager());
+  });
+
   if (Ctx.getLangOpts().CPlusPlus11)
     return EvaluateCPlusPlus11IntegralConstantExpr(Ctx, this, nullptr, Loc);
 
   ICEDiag D = CheckICE(this, Ctx);
   if (D.Kind != IK_ICE) {
     if (Loc) *Loc = D.Loc;
     return false;
   }

 
 bool Expr::EvaluateWithSubstitution(APValue &Value, ASTContext &Ctx,
                                     const FunctionDecl *Callee,
                                     ArrayRef<const Expr*> Args,
                                     const Expr *This) const {
   assert(!isValueDependent() &&
          "Expression evaluator can't be called on a dependent expression.");
 
+  llvm::TimeTraceScope TimeScope("EvaluateWithSubstitution", [&] {
+    std::string Name;
+    llvm::raw_string_ostream OS(Name);
+    Callee->getNameForDiagnostic(OS, Ctx.getPrintingPolicy(),
+                                 /*Qualified=*/true);
+    return Name;
+  });
+
   Expr::EvalStatus Status;
   EvalInfo Info(Ctx, Status, EvalInfo::EM_ConstantExpressionUnevaluated);
   Info.InConstantContext = true;
 
   LValue ThisVal;
   const LValue *ThisPtr = nullptr;
   if (This) {
 #ifndef NDEBUG
bool Expr::isPotentialConstantExpr(const FunctionDecl *FD,
                                    SmallVectorImpl<
                                      PartialDiagnosticAt> &Diags) {
   // FIXME: It would be useful to check constexpr function templates, but at the
   // moment the constant expression evaluator cannot cope with the non-rigorous
   // ASTs which we build for dependent expressions.
   if (FD->isDependentContext())
     return true;
 
+  llvm::TimeTraceScope TimeScope("isPotentialConstantExpr", [&] {
+    std::string Name;
+    llvm::raw_string_ostream OS(Name);
+    FD->getNameForDiagnostic(OS, FD->getASTContext().getPrintingPolicy(),
+                             /*Qualified=*/true);
+    return Name;
+  });
+
   Expr::EvalStatus Status;
   Status.Diag = &Diags;
 
   EvalInfo Info(FD->getASTContext(), Status, EvalInfo::EM_ConstantExpression);
   Info.InConstantContext = true;
   Info.CheckingPotentialConstantExpression = true;
 
   // The constexpr VM attempts to compile all methods to bytecode here.

clang/unittests/CMakeLists.txt

 # to failures, mostly in libclang.VirtualFileOverlay_*.
 if(NOT WIN32 AND CLANG_TOOL_LIBCLANG_BUILD) 
   add_subdirectory(libclang)
 endif()
 add_subdirectory(DirectoryWatcher)
 add_subdirectory(Rename)
 add_subdirectory(Index)
 add_subdirectory(Serialization)
+add_subdirectory(Support)

clang/unittests/Support/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  Support
+  )
+
+add_clang_unittest(ClangSupportTests
+  TimeProfilerTest.cpp
+  )
+
+clang_target_link_libraries(ClangSupportTests
+  PRIVATE
+  clangFrontend
+  )

clang/unittests/Support/TimeProfilerTest.cpp

+//===- unittests/Support/TimeProfilerTest.cpp -----------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Frontend/CompilerInstance.h"
+#include "clang/Frontend/FrontendActions.h"
+#include "clang/Lex/PreprocessorOptions.h"
+
+#include "llvm/Support/JSON.h"
+#include "llvm/Support/TimeProfiler.h"
+
+#include "gtest/gtest.h"
+
+using namespace clang;
+using namespace llvm;
+
+namespace {
+
+// Should be called before testing.
+void setupProfiler() {
+  timeTraceProfilerInitialize(/*TimeTraceGranularity=*/0, "test");
+}
+
+// Should be called after `compileFromString()`.
+// Returns profiler's JSON dump.
+std::string teardownProfiler() {
+  SmallVector<char, 1024> SmallVec;
+  raw_svector_ostream OS(SmallVec);
+  timeTraceProfilerWrite(OS);
+  timeTraceProfilerCleanup();
+  return OS.str().str();
+}
+
+// Returns true if code compiles successfully.
+// We only parse AST here. This is enough for constexpr evaluation.
+bool compileFromString(StringRef Code) {
+  CompilerInstance Compiler;
+  Compiler.createDiagnostics();
+
+  auto Invocation = std::make_shared<CompilerInvocation>();
+  Invocation->getPreprocessorOpts().addRemappedFile(
+      "test.cc", MemoryBuffer::getMemBuffer(Code).release());
+  const char *Args[] = {"-std=c++20", "test.cc"};
+  CompilerInvocation::CreateFromArgs(*Invocation, Args,
+                                     Compiler.getDiagnostics());
+  Compiler.setInvocation(std::move(Invocation));
+
+  class TestFrontendAction : public ASTFrontendAction {
+  private:
+    std::unique_ptr<ASTConsumer> CreateASTConsumer(CompilerInstance &CI,
+                                                   StringRef InFile) override {
+      return std::make_unique<ASTConsumer>();
+    }
+  } Action;
+  return Compiler.ExecuteAction(Action);
+}
+
+// Returns pretty-printed trace graph.
+std::string buildTraceGraph(StringRef Json) {
+  struct EventRecord {
+    int64_t TimestampBegin;
+    int64_t TimestampEnd;
+    StringRef Name;
+    StringRef Detail;
+  };
+  std::vector<EventRecord> Events;
+
+  // Parse `EventRecord`s from JSON dump.
+  Expected<json::Value> Root = json::parse(Json);
+  if (!Root)
+    return "";
+  for (json::Value &TraceEventValue :
+       *Root->getAsObject()->getArray("traceEvents")) {
+    json::Object *TraceEventObj = TraceEventValue.getAsObject();
+
+    int64_t TimestampBegin = TraceEventObj->getInteger("ts").value_or(0);
+    int64_t TimestampEnd =
+        TimestampBegin + TraceEventObj->getInteger("dur").value_or(0);
+    StringRef Name = TraceEventObj->getString("name").value_or("");
+    StringRef Detail = "";
+    if (json::Object *Args = TraceEventObj->getObject("args"))
+      Detail = Args->getString("detail").value_or("");
+
+    // This is a "summary" event, like "Total PerformPendingInstantiations",
+    // skip it
+    if (TimestampBegin == 0)
+      continue;
+
+    Events.emplace_back(
+        EventRecord{TimestampBegin, TimestampEnd, Name, Detail});
+  }
+
+  // There can be nested events that are very fast, for example:
+  // {"name":"EvaluateAsBooleanCondition",... ,"ts":2380,"dur":1}
+  // {"name":"EvaluateAsRValue",... ,"ts":2380,"dur":1}
+  // Therefore we should reverse the events list, so that events that have
+  // started earlier are first in the list.
+  // Then do a stable sort, we need it for the trace graph.
+  std::reverse(Events.begin(), Events.end());
+  std::stable_sort(
+      Events.begin(), Events.end(), [](const auto &lhs, const auto &rhs) {
+        return std::make_pair(lhs.TimestampBegin, -lhs.TimestampEnd) <
+               std::make_pair(rhs.TimestampBegin, -rhs.TimestampEnd);
+      });
+
+  std::stringstream Stream;
+  // Write a newline for better testing with multiline string literal.
+  Stream << "\n";
+
+  // Keep the current event stack.
+  std::stack<const EventRecord *> EventStack;
+  for (const auto &Event : Events) {
+    // Pop every event in the stack until meeting the parent event.
+    while (!EventStack.empty()) {
+      bool InsideCurrentEvent =
+          Event.TimestampBegin >= EventStack.top()->TimestampBegin &&
+          Event.TimestampEnd <= EventStack.top()->TimestampEnd;
+      if (!InsideCurrentEvent)
+        EventStack.pop();
+      else
+        break;
+    }
+    EventStack.push(&Event);
+
+    // Write indentaion, name, detail, newline.
+    for (size_t i = 1; i < EventStack.size(); ++i) {
+      Stream << "| ";
+    }
+    Stream.write(Event.Name.data(), Event.Name.size());
+    if (!Event.Detail.empty()) {
+      Stream << " (";
+      Stream.write(Event.Detail.data(), Event.Detail.size());
+      Stream << ")";
+    }
+    Stream << "\n";
+  }
+  return Stream.str();
+}
+
+} // namespace
+
+TEST(TimeProfilerTest, ConstantEvaluation) {
+  constexpr StringRef Code = R"(
+void print(double value);
+
+namespace slow_namespace {
+
+consteval double slow_func() {
+    double d = 0.0;
+    for (int i = 0; i < 100; ++i) { // 8th line
+        d += i;                     // 9th line
+    }
+    return d;
+}
+
+} // namespace slow_namespace
+
+void slow_test() {
+    constexpr auto slow_value = slow_namespace::slow_func(); // 17th line
+    print(slow_namespace::slow_func());                      // 18th line
+    print(slow_value);
+}
+
+int slow_arr[12 + 34 * 56 +                                  // 22nd line
+             static_cast<int>(slow_namespace::slow_func())]; // 23rd line
+
+constexpr int slow_init_list[] = {1, 1, 2, 3, 5, 8, 13, 21}; // 25th line
+    )";
+
+  setupProfiler();
+  ASSERT_TRUE(compileFromString(Code));
+  std::string Json = teardownProfiler();
+  std::string TraceGraph = buildTraceGraph(Json);
+  ASSERT_TRUE(TraceGraph == R"(
+Frontend
+| EvaluateAsRValue (<test.cc:8:21>)
+| EvaluateForOverflow (<test.cc:8:21, col:25>)
+| EvaluateAsRValue (<test.cc:9:14>)
+| EvaluateForOverflow (<test.cc:9:9, col:14>)
+| isPotentialConstantExpr (slow_namespace::slow_func)
+| EvaluateAsBooleanCondition (<test.cc:8:21, col:25>)
+| | EvaluateAsRValue (<test.cc:8:21, col:25>)
+| EvaluateAsBooleanCondition (<test.cc:8:21, col:25>)
+| | EvaluateAsRValue (<test.cc:8:21, col:25>)
+| EvaluateAsInitializer (slow_value)
+| EvaluateAsConstantExpr (<test.cc:17:33, col:59>)
+| EvaluateAsConstantExpr (<test.cc:18:11, col:37>)
+| EvaluateAsRValue (<test.cc:22:14, line:23:58>)
+| EvaluateAsInitializer (slow_init_list)
+| PerformPendingInstantiations
+)");
+
+  // NOTE: If this test is failing, run this test with
+  // `llvm::errs() << TraceGraph;` and change the assert above.
+}