[Attributor][WIP] Attribute scheduling visualization.

[kuter]

Summary

This patch is meant to be used for creating videos of the attributor scheduling.

Usage:

1. Create dot files (--attribute-seed-allow-list recommended)
2. Render the dot files.

for f in *.dot
do
  dot -Tpng "$f" -o "$f.png"
done

3. concatenate the images with ffmpeg.

ffmpeg -r 1 -pattern_type glob -i '*.png' -codec:v libx264 out.mp4

(TODO: Find options that don't break the aspect ratio)

[bbn]

Can we just merge the dependency graph and the "SchedulingGraph" because I think they are quite similar.

[jdoerfert]

You think it makes sense to merge the two graphes, as @bbn mentioned?

Can you create a script that, given a source file and maybe some options creates the video? Maybe place it in llvm/utils/Attributor.

[bbn]

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

906

Is this patch based on D83185 ? But I think those are 2 irrelevant patches, right? Maybe you should create a branch from master and apply changes to that.

[sstefan1]

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

906

That is fine, as long as allow list goes in first.

[kuter]

In D83297#2138744, @bbn wrote:

Can we just merge the dependency graph and the "SchedulingGraph" because I think they are quite similar.

Thank you for the idea. There are some problems with how the end result looks like and to fix that I
will change this significantly. My answer is late because it took some time for me to decide what I am going to do with this.

This is how it looks like right now: https://streamable.com/qguha8

The layout is not consistent across the frames. To fix this I will
record the state of scheduling (or the changes that are happening to the state) at each step
and output the scheduling graphs after the fix point iteration is complete hiding the nodes and edges that are not
visible at each step.

[kuter]

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

906

@bbn
Seeding allow list was originally meant for this patch 😄 .

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

 #include "llvm/Support/DOTGraphTraits.h"
 #include "llvm/Support/GraphWriter.h"
 #include "llvm/Transforms/Utils/CallGraphUpdater.h"
 
 namespace llvm {
 
 struct AADepGraphNode;
 struct AADepGraph;
+struct AASchedulingGraph;
 struct Attributor;
 struct AbstractAttribute;
 struct InformationCache;
 struct AAIsDead;
 
 class Function;
 
 /// Simple enum classes that forces properties to be spelled out explicitly.
struct AADepGraph {
 
   /// Dump graph to file
   void dumpGraph();
 
   /// Print dependency graph
   void print();
 };
 
+struct AASchedulingGraph {
+  AASchedulingGraph(AADepGraph *DepGraph) : DepGraph(DepGraph) {}
+  ~AASchedulingGraph() {}
+  void dumpGraph();
+
+  enum SchedulingState { IDLE_OR_FIXPOINT, UPDATING, NEEDS_UPDATE };
+
+  DenseMap<const AbstractAttribute *, SchedulingState> AttributeSchedulingState;
+  AADepGraph *DepGraph;
+};
+
 /// Helper to describe and deal with positions in the LLVM-IR.
 ///
 /// A position in the IR is described by an anchor value and an "offset" that
 /// could be the argument number, for call sites and arguments, or an indicator
 /// of the "position kind". The kinds, specified in the Kind enum below, include
 /// the locations in the attribute list, i.a., function scope and return value,
 /// as well as a distinction between call sites and functions. Finally, there
 /// are floating values that do not have a corresponding attribute list
struct Attributor {
   /// \param InfoCache Cache to hold various information accessible for
   ///                  the abstract attributes.
   /// \param CGUpdater Helper to update an underlying call graph.
   /// \param Allowed If not null, a set limiting the attribute opportunities.
   Attributor(SetVector<Function *> &Functions, InformationCache &InfoCache,
              CallGraphUpdater &CGUpdater,
              DenseSet<const char *> *Allowed = nullptr)
       : Allocator(InfoCache.Allocator), Functions(Functions),
-        InfoCache(InfoCache), CGUpdater(CGUpdater), Allowed(Allowed),
+        InfoCache(InfoCache), CGUpdater(CGUpdater), SG(&DG), Allowed(Allowed),
         SeedingPeriod(true) {}
 
   ~Attributor();
 
   /// Run the analyses until a fixpoint is reached or enforced (timeout).
   ///
   /// The attributes registered with this Attributor can be used after as long
   /// as the Attributor is not destroyed (it owns the attributes now).
   ///
private:
   /// Deletes dead functions, blocks and instructions.
   /// Rewrites function signitures and updates the call graph.
   ChangeStatus cleanupIR();
 
   /// Run `::update` on \p AA and track the dependences queried while doing so.
   /// Also adjust the state if we know further updates are not necessary.
   ChangeStatus updateAA(AbstractAttribute &AA);
 
+  /// Dump a new scheduling graph.
+  void invalidateSchedulingGraph();
+
   /// Remember the dependences on the top of the dependence stack such that they
   /// may trigger further updates. (\see DependenceStack)
   void rememberDependences();
 
   /// Check \p Pred on all call sites of \p Fn.
   ///
   /// This method will evaluate \p Pred on call sites and return
   /// true if \p Pred holds in every call sites. However, this is only possible
private:
   InformationCache &InfoCache;
 
   /// Helper to update an underlying call graph.
   CallGraphUpdater &CGUpdater;
 
   /// Abstract Attribute dependency graph
   AADepGraph DG;
 
+  /// Abstract Attribute scheduling graph. Used for visualizing the way the
+  /// Schedules Abstarct Attributes.
+  AASchedulingGraph SG;
+
   /// Set of functions for which we modified the content such that it might
   /// impact the call graph.
   SmallPtrSet<Function *, 8> CGModifiedFunctions;
 
   /// Information about a dependence. If FromAA is changed ToAA needs to be
   /// updated as well.
   struct DepInfo {
     const AbstractAttribute *FromAA;

llvm/lib/Transforms/IPO/Attributor.cpp

static cl::opt<bool> PrintDependencies("attributor-print-dep", cl::Hidden,
                                        cl::init(false));
 
 static cl::list<std::string>
     SeedAllowList("attributor-seed-allow-list", cl::Hidden,
                   cl::desc("Comma seperated list of attrbute names that are "
                            "allowed to be seeded."),
                   cl::ZeroOrMore, cl::CommaSeparated);
 
+static cl::opt<bool>
+    DumpSchedulingGraph("attributor-dump-scheduling-graph", cl::Hidden,
+                        cl::desc("Dump the scheduling graph to dot files."),
+                        cl::init(false));
+
 /// Logic operators for the change status enum class.
 ///
 ///{
 ChangeStatus llvm::operator|(ChangeStatus l, ChangeStatus r) {
   return l == ChangeStatus::CHANGED ? l : r;
 }
 ChangeStatus llvm::operator&(ChangeStatus l, ChangeStatus r) {
   return l == ChangeStatus::UNCHANGED ? l : r;
for (unsigned u = 0; u < ChangedAAs.size(); u++) {
     }
 
     while (!ChangedAA->Deps.empty()) {
       ChangedAAs.push_back(
           cast<AbstractAttribute>(ChangedAA->Deps.back().getPointer()));
       ChangedAA->Deps.pop_back();
     }
   }
+  invalidateSchedulingGraph();
 
   LLVM_DEBUG({
     if (!Visited.empty())
       dbgs() << "\n[Attributor] Finalized " << Visited.size()
              << " abstract attributes.\n";
   });
 
   if (VerifyMaxFixpointIterations &&
for (auto depAA : DG.SyntheticRoot.Deps) {
     LLVM_DEBUG(dbgs() << "[Attributor] Manifest " << LocalChange << " : " << *AA
                       << "\n");
 
     ManifestChange = ManifestChange | LocalChange;
 
     NumAtFixpoint++;
     NumManifested += (LocalChange == ChangeStatus::CHANGED);
   }
+  invalidateSchedulingGraph();
 
   (void)NumManifested;
   (void)NumAtFixpoint;
   LLVM_DEBUG(dbgs() << "\n[Attributor] Manifested " << NumManifested
                     << " arguments while " << NumAtFixpoint
                     << " were in a valid fixpoint state\n");
 
   NumAttributesManifested += NumManifested;
ChangeStatus Attributor::run() {
   if (PrintDependencies)
     DG.print();
 
   ChangeStatus ManifestChange = manifestAttributes();
   ChangeStatus CleanupChange = cleanupIR();
   return ManifestChange | CleanupChange;
 }
 
+void Attributor::invalidateSchedulingGraph() {
+  if (DumpSchedulingGraph) {
+    SG.dumpGraph();
+  }
+}
+
 ChangeStatus Attributor::updateAA(AbstractAttribute &AA) {
   // Use a new dependence vector for this update.
   DependenceVector DV;
   DependenceStack.push_back(&DV);
 
+  if (DumpSchedulingGraph)
+    SG.AttributeSchedulingState[&AA] = AASchedulingGraph::UPDATING;
+  invalidateSchedulingGraph();
+
   auto &AAState = AA.getState();
   ChangeStatus CS = ChangeStatus::UNCHANGED;
   if (!isAssumedDead(AA, nullptr, /* CheckBBLivenessOnly */ true))
     CS = AA.update(*this);
 
   if (DV.empty()) {
     // If the attribute did not query any non-fix information, the state
     // will not change and we can indicate that right away.
     AAState.indicateOptimisticFixpoint();
   }
 
+  if (DumpSchedulingGraph) {
+    for (DepInfo depInfo : DV) {
+      SG.AttributeSchedulingState[depInfo.ToAA] =
+          AASchedulingGraph::NEEDS_UPDATE;
+    }
+  }
+
   if (!AAState.isAtFixpoint())
     rememberDependences();
 
+  if (DumpSchedulingGraph)
+    SG.AttributeSchedulingState[AA] = AASchedulingGraph::IDLE_OR_FIXPOINT;
+  invalidateSchedulingGraph();
+
   // Verify the stack was used properly, that is we pop the dependence vector we
   // put there earlier.
   DependenceVector *PoppedDV = DependenceStack.pop_back_val();
   (void)PoppedDV;
   assert(PoppedDV == &DV && "Inconsistent usage of the dependence stack!");
 
   return CS;
 }
void AADepGraph::print() {
   llvm::sort(AAs, [](AbstractAttribute *LHS, AbstractAttribute *RHS) {
     return LHS->getName() < RHS->getName();
   });
 
   for (AbstractAttribute *AA : AAs)
     AA->printDeps(errs());
 }
 
+void AASchedulingGraph::dumpGraph() {
+  static int CallTimes = 0;
+
+  // Pad the number for names to sort properly.
+  std::string Number = std::to_string(CallTimes);
+  std::string Filename =
+      "sg_dot_file_" + std::string(10 - Number.size(), '0') + Number + ".dot";
+  errs() << "Scheduling graph dump to " << Filename << ".\n";
+
+  std::error_code EC;
+
+  raw_fd_ostream File(Filename, EC, sys::fs::OF_Text);
+  if (!EC)
+    llvm::WriteGraph(File, this);
+
+  CallTimes++;
+}
+
 PreservedAnalyses AttributorPass::run(Module &M, ModuleAnalysisManager &AM) {
   FunctionAnalysisManager &FAM =
       AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
   AnalysisGetter AG(FAM);
 
   SetVector<Function *> Functions;
   for (Function &F : M)
     Functions.insert(&F);
static std::string getNodeLabel(const AADepGraphNode *Node,
                                   const AADepGraph *DG) {
     std::string AAString = "";
     raw_string_ostream O(AAString);
     Node->print(O);
     return AAString;
   }
 };
 
+template <>
+struct GraphTraits<AASchedulingGraph *> : public GraphTraits<AADepGraphNode *> {
+  static NodeRef getEntryNode(AADepGraph *DG) { return DG->GetEntryNode(); }
+
+  using nodes_iterator =
+      mapped_iterator<TinyPtrVector<DepTy>::iterator, decltype(&DepGetVal)>;
+
+  static nodes_iterator nodes_begin(AASchedulingGraph *SG) {
+    return SG->DepGraph->begin();
+  }
+
+  static nodes_iterator nodes_end(AASchedulingGraph *SG) {
+    return SG->DepGraph->end();
+  }
+};
+
+template <>
+struct DOTGraphTraits<AASchedulingGraph *> : public DefaultDOTGraphTraits {
+  DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
+
+  static std::string getNodeLabel(const AADepGraphNode *Node,
+                                  const AASchedulingGraph *DG) {
+    std::string AAString = "";
+    raw_string_ostream O(AAString);
+    Node->print(O);
+    return AAString;
+  }
+
+  static std::string getNodeAttributes(const AADepGraphNode *DepNode,
+                                       AASchedulingGraph *SG) {
+    const AbstractAttribute *Node = (const AbstractAttribute *)DepNode;
+    if (Node->getState().isAtFixpoint())
+      return "color=\"blue\"";
+    if (!Node->getState().isValidState())
+      return "color=\"red\"";
+
+    switch (SG->AttributeSchedulingState[Node]) {
+    case AASchedulingGraph::IDLE_OR_FIXPOINT:
+      return "color=\"white\"";
+    case AASchedulingGraph::UPDATING:
+      return "color=\"green\"";
+    case AASchedulingGraph::NEEDS_UPDATE:
+      return "color=\"brown\"";
+    }
+    llvm_unreachable("All cases covered!");
+  }
+};
 } // end namespace llvm
 
 namespace {
 
 struct AttributorLegacyPass : public ModulePass {
   static char ID;
 
   AttributorLegacyPass() : ModulePass(ID) {