Add initial support for debug counting

[• dberlin]

Summary

(Note: I named it debug counting because that's what we called it in
GCC. I'm also mostly leaving this here until i get back to it because
i promised some folks who wanted to use it. I'll ping the review when
it's cleaned up a bit).

We have support for bisection, and bugpoint can reduce testcases
often to a single pass. But that doesn't help reduce it to a single
transform by a single pass. Which debug counting lets us do.

Debug counting lets you instrument a pass so that it only executes a
certain thing (rwhatever you want) after skipping it a certain time of
times, and then only does a certain number of executions before saying
"skip" again.

To make it concrete, for predicateinfo, if i instrument use renaming,
i can make it so it skips renaming the first N uses, renames the next
N, and then skips the rest.

This lets you narrow down a miscompilation to, often, a single
transformation, and then also debug it (by using the same command line
parameters).

[• dberlin]

A few notes:

1. I have scripts that automate binary searching the counters that i'll

upload at some point.

My current scripts only binary search a single counter, but actually, if your
miscompile requires multiple transforms, you can binary search all the
counters.

2. Not sure what to do about counter registration.

It's easy for passes, i think.
For utilities, right now you have to just create a static object that calls registerCounter.

Right now, nothing prints the list of counters.

I could set up some macros like we have STATISTIC to register them, if folks think that is the right approach.

[mehdi_amini]

In D29998#677673, @dberlin wrote:

A few notes:

1. I have scripts that automate binary searching the counters that i'll upload at some point.

llvm/utils/bisect ?

[• dberlin]

In D29998#677742, @mehdi_amini wrote:

In D29998#677673, @dberlin wrote:

A few notes:

1. I have scripts that automate binary searching the counters that i'll upload at some point.

llvm/utils/bisect ?

Right, it's a variant of that that

1. Knows how to format the counters
2. Binary searches the skip, then the count.

[• dberlin]

• Add my current hacked up script to bisect skip and count

[• dberlin]

• Update to be cleaner

[davide]

When I saw this GCC feature I was really jealous =) Thanks for working on this, reviewing it now.

[davide]

include/llvm/Support/DebugCounter.h

70–71

Add a diagnostic? ("enable debug if you want counters!") or something?

79–80

Can counter ever go below zero?

lib/Support/DebugCounter.cpp

72–74

At least can we output something to stderr, here, I think

[• dberlin]

include/llvm/Support/DebugCounter.h

70–71

We can't, really.
Because the shouldExecute call happens all the time, whether you are in debug mode or not. It just does nothing with debugging off.
(or at least, that's how GCC works)

79–80

We use -1 to say "always execute".
I'll update.

[Bigcheese]

lib/Support/DebugCounter.cpp

19

I believe this should be:

explicit DebugCounterList(Mods &&... Ms) : Base(std::forward<Mods>(Ms)...) {}

Which is the idiomatic way to forward arguments.

[• dberlin]

• Update for review comments, make it print options properly and warn.

[• dberlin]

• Add comments

[davide]

LGTM! (after some minor comments inline have been addressed).
I used this (yesterday) to track down an issue internally, so very happy about this feature already.
I'd commit the PredicateInfo bits separately (it would be awesome if you can actually a test for that).

include/llvm/Support/CommandLine.h

1444–1445

Do you need all these member variables to be protected?

lib/Support/DebugCounter.cpp

26

Add a small comment to explain the hardcoded 6.

29–31

Same here.

33

NumSpaces can probably be folded here, but up to you (if you think it's less readable)

51

full stop at the end of the comment

[mehdi_amini]

I think some documentation in the dev guide would be welcome!

[davide]

In D29998#681089, @mehdi_amini wrote:

I think some documentation in the dev guide would be welcome!

Yes, I agree.

[• dberlin]

I'll commit the predicateinfo bit separately. I added it to the CL as a demo, as everything gets dead-stripped on Darwin if you don't register a counter somewhere.
(it took me a good 30 minutes to figure out what was going on, as the debug-counter option disappears from opt you have no counters.
I'm actually fairly surprised this is legal, but ....)

I believe i can test the predicateinfo piece pretty easily, because we can just have a test where it skips renaming a use and verify that it skips the rename.

include/llvm/Support/CommandLine.h

1444–1445

Actually, i don't think we need any of them any more.
I'll check and revert if i can.

lib/Support/DebugCounter.cpp

26

It appears to be the option width used in CommandLine.cpp,but it's uncommented there too.
I've at least commented where it comes from.

33

I tried and it creates a really weird line split, so i'm going to leave it ATM.

51

fixed

include/llvm/Support/CommandLine.h

 };
 
 //===----------------------------------------------------------------------===//
 // list - A list of command line options.
 //
 template <class DataType, class StorageClass = bool,
           class ParserClass = parser<DataType>>
 class list : public Option, public list_storage<DataType, StorageClass> {
+protected:
   std::vector<unsigned> Positions;
   ParserClass Parser;
 
   enum ValueExpected getValueExpectedFlagDefault() const override {
     return Parser.getValueExpectedFlagDefault();
   }
   void getExtraOptionNames(SmallVectorImpl<StringRef> &OptionNames) override {
     return Parser.getExtraOptionNames(OptionNames);
   }

include/llvm/Support/DebugCounter.h

+//===- llvm/Support/DebugCounter.h - Debug counter support ------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// \file This file provides an implementation of debug counters.  Debug counters
+// are a tool that let you narrow down a miscompilation to a specific thing
+// happening.  To give a use case: Imagine you have a file, very large, and you
+// are trying to understand the minimal transformation that breaks it.  Bugpoint
+// and bisection is often helpful here in narrowing it down to a specific pass,
+// but it's still a very large file, and a very complicated pass to try to
+// debug.  That is where debug counting steps in.  You can instrument the pass
+// with a debug counter before it does a certain thing, and depending on the
+// counts, it will either execute that thing or not.  The debug counter itself
+// consists of a skip and a count.  Skip is the number of times shouldExecute
+// needs to be called before it returns true.  Count is the number of times to
+// return true once Skip is 0.  So a skip=47, count=2 ,would skip the first 47
+// executions by returning false from shouldExecute, then execute twice, and
+// then return false again.
+
+// For a concrete example, during predicateinfo creation, the renaming pass
+// replaces each use with a renamed use.
+///
+// If I use DEBUG_COUNTER to create a counter called "predicateinfo", and
+// variable name RenameCounter, and then instrument this renaming with a debug
+// counter, like so:
+//
+// if (!DebugCounter::shouldExecute(RenameCounter)
+// <continue or return or whatever not executing looks like>
+//
+// Now I can, from the command line, make it rename or not rename certain uses
+// by setting the skip and count.
+// So for example
+// bin/opt -debug-counter=predicateinfo-skip=47,predicateinfo-count=1
+// will skip renaming the first 47 uses, then rename one, then skip the rest.
+
+#ifndef LLVM_SUPPORT_DEBUGCOUNTER_H
+#define LLVM_SUPPORT_DEBUGCOUNTER_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/UniqueVector.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include <string>
+
+namespace llvm {
+
+class DebugCounter {
+public:
+  /// \brief Returns a reference to the singleton instance.
+  static DebugCounter &instance();
+
+  // Used by the command line option parser to push a new value it parsed.
+  void push_back(const std::string &);
+
+  // Register a counter with the specified name.
+  //
+  // FIXME: Currently, counter registration is required to happen before command
+  // line option parsing. The main reason to register counters is to produce a
+  // nice list of them on the command line, but i'm not sure this is worth it.
+  static unsigned registerCounter(StringRef Name, StringRef Desc) {
+    return instance().addCounter(Name, Desc);
+  }
+  inline static bool shouldExecute(unsigned CounterName) {
+// Compile to nothing when debugging is off
+#ifdef NDEBUG
+    return true;
+#else
+    auto &Us = instance();
+    auto Result = Us.Counters.find(CounterName);
+    if (Result != Us.Counters.end()) {
+      auto &CounterPair = Result->second;
+      // We only execute while the skip (first) is zero and the count (second)
+      // is non-zero
+      if (CounterPair.first < 0)
+        return true;
+      if (CounterPair.first != 0) {
+        --CounterPair.first;
+        return false;
+      }
+      if (CounterPair.second < 0)
+        return true;
+      if (CounterPair.second != 0) {
+        --CounterPair.second;
+        return true;
+      }
+      return false;
+    }
+    // Didn't find the counter, should we warn?
+    return true;
+#endif // NDEBUG
+  }
+
+  // Dump or print the current counter set.
+  LLVM_DUMP_METHOD void dump() { print(dbgs()); }
+
+  void print(raw_ostream &OS);
+  // Get the counter ID for a given named counter, or return 0 if none is found.
+  unsigned getCounterId(const std::string &Name) const {
+    return RegisteredCounters.idFor(Name);
+  }
+  unsigned int getNumCounters() const { return Counters.size(); }
+
+  std::pair<StringRef, StringRef> getCounterInfo(unsigned ID) {
+    return std::make_pair(RegisteredCounters[ID], CounterDesc[ID]);
+  }
+
+private:
+  unsigned addCounter(const std::string &Name, const std::string &Desc) {
+    unsigned Result = RegisteredCounters.insert(Name);
+    CounterDesc[Result] = Desc;
+    return Result;
+  }
+  DenseMap<unsigned, std::pair<long, long>> Counters;
+  DenseMap<unsigned, std::string> CounterDesc;
+  UniqueVector<std::string> RegisteredCounters;
+};
+
+#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)                              \
+  static const unsigned VARNAME =                                              \
+      DebugCounter::registerCounter(COUNTERNAME, DESC);
+
+} // namespace llvm
+#endif

lib/Support/CMakeLists.txt

add_llvm_library(LLVMSupport
   COM.cpp
   CommandLine.cpp
   Compression.cpp
   ConvertUTF.cpp
   ConvertUTFWrapper.cpp
   CrashRecoveryContext.cpp
   DataExtractor.cpp
   Debug.cpp
+  DebugCounter.cpp
   DeltaAlgorithm.cpp
   DAGDeltaAlgorithm.cpp
   Dwarf.cpp
   Error.cpp
   ErrorHandling.cpp
   FileUtilities.cpp
   FileOutputBuffer.cpp
   FoldingSet.cpp

lib/Support/DebugCounter.cpp

+#include "llvm/Support/DebugCounter.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Format.h"
+#include "llvm/Support/ManagedStatic.h"
+#include "llvm/Support/Options.h"
+
+using namespace llvm;
+
+// This class overrides the default list implementation of printing so we
+// can pretty print the list of debug counter options.  This type of
+// dynamic option is pretty rare (basically this and pass lists).
+
+class DebugCounterList : public cl::list<std::string, DebugCounter> {
+private:
+  using Base = cl::list<std::string, DebugCounter>;
+
+public:
+  template <class... Mods>
+  explicit DebugCounterList(const Mods &... Ms) : Base(Ms...) {}
+
+private:
+  void printOptionInfo(size_t GlobalWidth) const override {
+    auto CounterInstance = DebugCounter::instance();
+    for (unsigned i = 0; i < CounterInstance.getNumCounters(); ++i) {
+      const auto Info = CounterInstance.getCounterInfo(i);
+    }
+    // FIXME: Print options
+    this->Base::printOptionInfo(GlobalWidth);
+  }
+};
+
+// Create our command line option
+static DebugCounterList DebugCounterOption(
+    "debug-counter",
+    cl::desc("Comma separated list of debug counter skip and count"),
+    cl::CommaSeparated, cl::ZeroOrMore, cl::location(DebugCounter::instance()));
+
+static ManagedStatic<DebugCounter> DC;
+
+DebugCounter &DebugCounter::instance() { return *DC; }
+
+void DebugCounter::push_back(const std::string &Val) {
+  if (Val.empty())
+    return;
+  // The strings should come in as counter=value
+  auto CounterPair = StringRef(Val).split('=');
+  if (CounterPair.second.empty())
+    // TODO: Figure out proper way to warn user on command line
+    return;
+  // Now we have counter=value.
+  // First, process value.
+  long CounterVal;
+  if (CounterPair.second.getAsInteger(0, CounterVal))
+    // Ditto above
+    return;
+  // Now we need to see if this is the skip or the count, remove the suffix, and
+  // add it to the counter values.
+  if (CounterPair.first.endswith("-skip")) {
+    auto CounterName = CounterPair.first.drop_back(5);
+    unsigned CounterID = RegisteredCounters.idFor(CounterName);
+    if (!CounterID)
+      return;
+    auto Res = Counters.insert({CounterID, {-1, -1}});
+    Res.first->second.first = CounterVal;
+  } else if (CounterPair.first.endswith("-count")) {
+    auto CounterName = CounterPair.first.drop_back(6);
+    unsigned CounterID = RegisteredCounters.idFor(CounterName);
+    if (!CounterID)
+      return;
+    auto Res = Counters.insert({CounterID, {-1, -1}});
+    Res.first->second.second = CounterVal;
+  } else {
+    // FIXME: Issue warning?
+  }
+}
+
+void DebugCounter::print(raw_ostream &OS) {
+  OS << "Counters and values:\n";
+  for (const auto &KV : Counters)
+    OS << left_justify(RegisteredCounters[KV.first], 32) << ": {"
+       << KV.second.first << "," << KV.second.second << "}\n";
+}

lib/Transforms/Utils/PredicateInfo.cpp

 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/Support/DebugCounter.h"
 #include "llvm/Support/FormattedStream.h"
 #include "llvm/Transforms/Scalar.h"
 #include <algorithm>
 #define DEBUG_TYPE "predicateinfo"
 using namespace llvm;
 using namespace PatternMatch;
 using namespace llvm::PredicateInfoClasses;
 
 INITIALIZE_PASS_BEGIN(PredicateInfoPrinterLegacyPass, "print-predicateinfo",
                       "PredicateInfo Printer", false, false)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_END(PredicateInfoPrinterLegacyPass, "print-predicateinfo",
                     "PredicateInfo Printer", false, false)
 static cl::opt<bool> VerifyPredicateInfo(
     "verify-predicateinfo", cl::init(false), cl::Hidden,
     cl::desc("Verify PredicateInfo in legacy printer pass."));
+DEBUG_COUNTER(RenameCounter, "predicateinfo-rename",
+              "Controls which variables are renamed with predicateinfo");
+
 namespace llvm {
 namespace PredicateInfoClasses {
 enum LocalNum {
   // Operations that must appear first in the block.
   LN_First,
   // Operations that are somewhere in the middle of the block, and are sorted on
   // demand.
   LN_Middle,
for (auto &VD : OrderedUses) {
       }
       // If we get to this point, and the stack is empty we must have a use
       // with no renaming needed, just skip it.
       if (RenameStack.empty())
         continue;
       // Skip values, only want to rename the uses
       if (VD.Def || PossibleCopy)
         continue;
+      if (!DebugCounter::shouldExecute(RenameCounter)) {
+        DEBUG(dbgs() << "Skipping execution due to debug counter\n");
+        continue;
+      }
       ValueDFS &Result = RenameStack.back();
 
       // If the possible copy dominates something, materialize our stack up to
       // this point. This ensures every comparison that affects our operation
       // ends up with predicateinfo.
       if (!Result.Def)
         Result.Def = materializeStack(Counter, RenameStack, Op);
 

utils/bisect-skip-count

+#!/usr/bin/env python
+
+import os
+import sys
+import argparse
+import subprocess32 as subprocess
+
+parser = argparse.ArgumentParser()
+
+parser.add_argument('--skipstart', type=int, default=0)
+parser.add_argument('--skipend', type=int, default=(1 << 32))
+parser.add_argument('--countstart', type=int, default=0)
+parser.add_argument('--countend', type=int, default=(1 << 32))
+parser.add_argument('--timeout', type=int, default=None)
+parser.add_argument('command', nargs='+')
+
+args = parser.parse_args()
+
+start = args.skipstart
+end = args.skipend
+
+print("Bisect Starting!")
+print("Start: %d" % start)
+print("End: %d" % end)
+
+last = None
+while start != end and start != end-1:
+    count = start + (end - start)/2
+    print("Visiting Skip: %d with (Start, End) = (%d,%d)" % (count, start, end))
+    cmd = [x % {'skip':count, 'count':-1} for x in args.command]
+    print cmd
+    try:
+        result = subprocess.call(cmd, shell=True, timeout=args.timeout)
+        if result == 0:
+           print("    PASSES! Setting start to count")
+           end = count
+        else:
+           print("    FAILS! Setting end to count")
+           start = count
+    except:
+        print(" TIMEOUT, setting end to count")
+        end = count
+firstcount = start
+print("Last good count: %d" % start)
+start = args.countstart
+end = args.countend
+while start != end and start != end-1:
+    count = start + (end - start)/2
+    print("Visiting Count: %d with (Start, End) = (%d,%d)" % (count, start, end))
+    cmd = [x % {'count':count, 'skip':firstcount } for x in args.command]
+    print cmd
+    try:
+        result = subprocess.call(cmd, shell=True, timeout=20)
+        if result == 0:
+           print("    PASSES! Setting start to count")
+           start = count
+        else:
+           print("    FAILS! Setting end to count")
+           end = count
+    except:
+        print(" TIMEOUT, setting end to count")
+        start = count
+
+print("Last good count: %d" % start)