[Attributor] Add time trace support.

[kuter]

Summary

This patch addes time trace functionality to have a better understanding
of the analysis times.

[jdoerfert]

Really cool :) LGTM

llvm/lib/Transforms/IPO/Attributor.cpp

32

not needed.

[kuter]

In D84980#2185839, @jdoerfert wrote:

Really cool :) LGTM

Ok. As I said in the chat, when we create a attribute we update it once or we can force a update in the query function, Because of this
the time that it takes to do the update gets added to the time of the attribute that triggered it.

The time data we get doesn't accurately represent the amount of compute that the updateAA of a specific attribute does.
since the cost of updating a attribute when it's first created get's added on top of the time of the attribute that first asked for it.

We can keep track of the update times ourselves, We would stop the timer of the attribute before we start updating another one and restart it when we are done.
We can inject entries directly into the TimeTraceProfiler but that would require some changes with it.

I am not sure if we want to go that route, maybe we land this patch like this for now and if we have hard time interpreting this data, we can add that later ?

[jdoerfert]

I am not sure if we want to go that route, maybe we land this patch like this for now and if we have hard time interpreting this data, we can add that later ?

That sounds like a sensible solution :)

llvm/include/llvm/Transforms/IPO/Attributor.h

 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/AbstractCallSite.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/DOTGraphTraits.h"
 #include "llvm/Support/GraphWriter.h"
+#include "llvm/Support/TimeProfiler.h"
 #include "llvm/Transforms/Utils/CallGraphUpdater.h"
 
 namespace llvm {
 
 struct AADepGraphNode;
 struct AADepGraph;
 struct Attributor;
 struct AbstractAttribute;
const AAType &getOrCreateAAFor(const IRPosition &IRP,
     // Bootstrap the new attribute with an initial update to propagate
     // information, e.g., function -> call site. If it is not on a given
     // Allowed we will not perform updates at all.
     if (Invalidate) {
       AA.getState().indicatePessimisticFixpoint();
       return AA;
     }
 
+    {
+      TimeTraceScope TimeScope(AA.getName() + "::initialize");
       AA.initialize(*this);
-
+    }
     // We can initialize (=look at) code outside the current function set but
     // not call update because that would again spawn new abstract attributes in
     // potentially unconnected code regions (=SCCs).
     if (FnScope && !Functions.count(const_cast<Function *>(FnScope))) {
       AA.getState().indicatePessimisticFixpoint();
       return AA;
     }
 

llvm/lib/Transforms/IPO/Attributor.cpp

 #include "llvm/Analysis/MustExecute.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/NoFolder.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/GraphWriter.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
 
 #include <cassert>
 #include <string>
for (Instruction *I :
     if (!Pred(*I))
       return false;
   }
 
   return true;
 }
 
 void Attributor::runTillFixpoint() {
+  TimeTraceScope TimeScope("Attributor::runTillFixpoint");
   LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized "
                     << DG.SyntheticRoot.Deps.size()
                     << " abstract attributes.\n");
 
   // Now that all abstract attributes are collected and initialized we start
   // the abstract analysis.
 
   unsigned IterationCounter = 1;
errs() << "\n[Attributor] Fixpoint iteration done after: "
            << IterationCounter << "/" << MaxFixpointIterations
            << " iterations\n";
     llvm_unreachable("The fixpoint was not reached with exactly the number of "
                      "specified iterations!");
   }
 }
 
 ChangeStatus Attributor::manifestAttributes() {
+  TimeTraceScope TimeScope("Attributor::manifestAttributes");
   size_t NumFinalAAs = DG.SyntheticRoot.Deps.size();
 
   unsigned NumManifested = 0;
   unsigned NumAtFixpoint = 0;
   ChangeStatus ManifestChange = ChangeStatus::UNCHANGED;
   for (auto &DepAA : DG.SyntheticRoot.Deps) {
     AbstractAttribute *AA = cast<AbstractAttribute>(DepAA.getPointer());
     AbstractState &State = AA->getState();
for (unsigned u = NumFinalAAs; u < DG.SyntheticRoot.Deps.size(); ++u)
              << "\n";
     llvm_unreachable("Expected the final number of abstract attributes to "
                      "remain unchanged!");
   }
   return ManifestChange;
 }
 
 ChangeStatus Attributor::cleanupIR() {
+  TimeTraceScope TimeScope("Attributor::cleanupIR");
   // Delete stuff at the end to avoid invalid references and a nice order.
   LLVM_DEBUG(dbgs() << "\n[Attributor] Delete at least "
                     << ToBeDeletedFunctions.size() << " functions and "
                     << ToBeDeletedBlocks.size() << " blocks and "
                     << ToBeDeletedInsts.size() << " instructions and "
                     << ToBeChangedUses.size() << " uses\n");
 
   SmallVector<WeakTrackingVH, 32> DeadInsts;
for (Function *F : Functions) {
     assert(!verifyFunction(*F, &errs()) && "Module verification failed!");
   }
 #endif
 
   return ManifestChange;
 }
 
 ChangeStatus Attributor::run() {
+  TimeTraceScope TimeScope("Attributor::run");
+
   SeedingPeriod = false;
   runTillFixpoint();
 
   // dump graphs on demand
   if (DumpDepGraph)
     DG.dumpGraph();
 
   if (ViewDepGraph)
     DG.viewGraph();
 
   if (PrintDependencies)
     DG.print();
 
   ChangeStatus ManifestChange = manifestAttributes();
   ChangeStatus CleanupChange = cleanupIR();
   return ManifestChange | CleanupChange;
 }
 
 ChangeStatus Attributor::updateAA(AbstractAttribute &AA) {
+  TimeTraceScope TimeScope(AA.getName() + "::updateAA");
+
   // Use a new dependence vector for this update.
   DependenceVector DV;
   DependenceStack.push_back(&DV);
 
   auto &AAState = AA.getState();
   ChangeStatus CS = ChangeStatus::UNCHANGED;
   if (!isAssumedDead(AA, nullptr, /* CheckBBLivenessOnly */ true))
     CS = AA.update(*this);