llvm-reduce: Don't write out IR to score IR complexity

[arsenm]

Summary

In a testcase I'm working on, the old write out and count IR lines
was taking about 200-300ms per iteration. This drops it out of the
profile.

This doesn't account for everything, but it doesn't seem to matter.
We should probably try to account for metadata and constantexpr tree
depths.

[regehr]

so at some level here we're scoring a test case based on how simple it is for a human being to understand. I mean, that's what we should be doing. from that point of view, I dislike assigning a small cost to poison and undef -- they're probably the most semantically challenging concepts in this entire IR, in terms of the number of compiler bugs they have caused.

I think that fast-math and other flags (especially ones like NSW) should be accounted for here, but if that's left for future work that's OK.

note that there exist some flags where the presence of the flag is semantically simpler than the absence of the flag! for example, a noundef function parameter can make a function considerably easier to understand. that's one of the things I disliked about the previous "file size" approach. could you please add some TODO/FIXME items regarding that sort of thing?

finally I agree that this should be unified with the quite similar code found elsewhere. I don't think that needs to block this pull request, but that's a displeasing kind of redundancy to have in our tool here.

[aeubanks]

note that there exist some flags where the presence of the flag is semantically simpler than the absence of the flag! for example, a noundef function parameter can make a function considerably easier to understand. that's one of the things I disliked about the previous "file size" approach. could you please add some TODO/FIXME items regarding that sort of thing?

IMO we should still be reducing away those attributes, if somebody submitted a test case I'd request irrelevant attributes to be removed

llvm/tools/llvm-reduce/ReducerWorkItem.cpp

607

a poison value is an undef value, isa<UndefValue>(V) is enough

608

I thought we wanted undef to be more expensive than 0?

644

do we want to add a flat cost to every instruction? (same with globals below)

[arsenm]

In D135539#3847581, @aeubanks wrote:

note that there exist some flags where the presence of the flag is semantically simpler than the absence of the flag! for example, a noundef function parameter can make a function considerably easier to understand. that's one of the things I disliked about the previous "file size" approach. could you please add some TODO/FIXME items regarding that sort of thing?

IMO we should still be reducing away those attributes, if somebody submitted a test case I'd request irrelevant attributes to be removed

My struggle is I don't actually care about the IR on most failures I end up looking at, and want to minimize the MIR that comes out of it. Any annotations that decrease the emitted machine code are useful. One simple example is marking globals as internal/protected to avoid the GOT lookup

[arsenm]

Count flags

[aeubanks]

lgtm with one more question

llvm/tools/llvm-reduce/ReducerWorkItem.cpp

608

ping, maybe lump undef into return 3?

[arsenm]

llvm/tools/llvm-reduce/ReducerWorkItem.cpp

608

Why would undef be treated as complex?

So far the actual scoring doesn't matter and we could probably do as well with a content agnostic hash that indicates some change occurred

[aeubanks]

llvm/tools/llvm-reduce/ReducerWorkItem.cpp

608

we'd rather reduce to 0 than undef

if we're going the route of hashing, then we should do that, but right now we're rerunning the reduction pipeline if the complexity has decreased. we try to reduce to 0 over undef, and if we do that but also make another reduction that decreases the complexity by one, the net complexity change will be zero and we won't rerun the pipeline.

[arsenm]

c23ac22f0ed9b76f127794534b3dfd5557389aed

llvm/tools/llvm-reduce/ReducerWorkItem.h

public:
 
   const Module &getModule() const { return *M; }
 
   void print(raw_ostream &ROS, void *p = nullptr) const;
   operator Module &() const { return *M; }
 
   /// Return a number to indicate whether there was any reduction progress.
   uint64_t getComplexityScore() const {
-    return isMIR() ? computeMIRComplexityScore() : getIRSize();
+    return isMIR() ? computeMIRComplexityScore() : computeIRComplexityScore();
   }
 
 private:
+  uint64_t computeIRComplexityScore() const;
   uint64_t computeMIRComplexityScore() const;
-  uint64_t getIRSize() const;
 };
 
 std::unique_ptr<ReducerWorkItem>
 parseReducerWorkItem(const char *ToolName, StringRef Filename,
                      LLVMContext &Ctxt, std::unique_ptr<TargetMachine> &TM,
                      bool IsMIR);
 
 std::unique_ptr<ReducerWorkItem>
 cloneReducerWorkItem(const ReducerWorkItem &MMM, const TargetMachine *TM);
 
 bool verifyReducerWorkItem(const ReducerWorkItem &MMM, raw_fd_ostream *OS);
 
 #endif

llvm/tools/llvm-reduce/ReducerWorkItem.cpp

 #include "llvm/CodeGen/MIRPrinter.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Instructions.h"
 #include "llvm/IR/ModuleSummaryIndex.h"
+#include "llvm/IR/Operator.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/IRReader/IRReader.h"
 #include "llvm/MC/TargetRegistry.h"
 #include "llvm/Support/Host.h"
 #include "llvm/Support/MemoryBufferRef.h"
 #include "llvm/Support/SourceMgr.h"
 #include "llvm/Support/TargetSelect.h"
 #include "llvm/Support/WithColor.h"
for (Function &F : *M) {
         printMIR(ROS, *MF);
     }
   } else {
     M->print(ROS, /*AssemblyAnnotationWriter=*/nullptr,
              /*ShouldPreserveUseListOrder=*/true);
   }
 }
 
-// FIXME: We might want to use a different metric than "number of
-// bytes in serialized IR" to detect non-progress of the main delta
-// loop
-uint64_t ReducerWorkItem::getIRSize() const {
-  std::string Str;
-  raw_string_ostream SS(Str);
-  print(SS, /*AnnotationWriter=*/nullptr);
-  return Str.length();
-}
-
 /// Try to produce some number that indicates a function is getting smaller /
 /// simpler.
 static uint64_t computeMIRComplexityScoreImpl(const MachineFunction &MF) {
   uint64_t Score = 0;
   const MachineFrameInfo &MFI = MF.getFrameInfo();
 
   // Add for stack objects
   Score += MFI.getNumObjects();
uint64_t ReducerWorkItem::computeMIRComplexityScore() const {
 
   for (const Function &F : getModule()) {
     if (auto *MF = MMI->getMachineFunction(F))
       Score += computeMIRComplexityScoreImpl(*MF);
   }
 
   return Score;
 }
+
+// FIXME: ReduceOperandsSkip has similar function, except it uses larger numbers
+// for more reduced.
+static unsigned classifyReductivePower(const Value *V) {
+  if (auto *C = dyn_cast<ConstantData>(V)) {
+    if (isa<UndefValue>(V))
+      return 0;
+    if (C->isNullValue())
+      return 1;
+    if (C->isOneValue())
+      return 2;
+    return 3;
+  }
+
+  if (isa<GlobalValue>(V))
+    return 4;
+
+  // TODO: Treat constantexprs as more complex
+  if (isa<Constant>(V))
+    return 1;
+
+  if (isa<Argument>(V))
+    return 5;
+
+  if (isa<Instruction>(V))
+    return 6;
+
+  return 0;
+}
+
+// TODO: Additional flags and attributes may be complexity reducing. If we start
+// adding flags and attributes, they could have negative cost.
+static uint64_t computeIRComplexityScoreImpl(const Function &F) {
+  uint64_t Score = 1; // Count the function itself
+  SmallVector<std::pair<unsigned, MDNode *>> MDs;
+
+  AttributeList Attrs = F.getAttributes();
+  for (AttributeSet AttrSet : Attrs)
+    Score += AttrSet.getNumAttributes();
+
+  for (const BasicBlock &BB : F) {
+    ++Score;
+
+    for (const Instruction &I : BB) {
+      ++Score;
+
+      if (const auto *OverflowOp = dyn_cast<OverflowingBinaryOperator>(&I)) {
+        if (OverflowOp->hasNoUnsignedWrap())
+          ++Score;
+        if (OverflowOp->hasNoSignedWrap())
+          ++Score;
+      } else if (const auto *GEP = dyn_cast<GEPOperator>(&I)) {
+        if (GEP->isInBounds())
+          ++Score;
+      } else if (const auto *ExactOp = dyn_cast<PossiblyExactOperator>(&I)) {
+        if (ExactOp->isExact())
+          ++Score;
+      } else if (const auto *FPOp = dyn_cast<FPMathOperator>(&I)) {
+        FastMathFlags FMF = FPOp->getFastMathFlags();
+        if (FMF.allowReassoc())
+          ++Score;
+        if (FMF.noNaNs())
+          ++Score;
+        if (FMF.noInfs())
+          ++Score;
+        if (FMF.noSignedZeros())
+          ++Score;
+        if (FMF.allowReciprocal())
+          ++Score;
+        if (FMF.allowContract())
+          ++Score;
+        if (FMF.approxFunc())
+          ++Score;
+      }
+
+      for (const Value *Operand : I.operands()) {
+        ++Score;
+        Score += classifyReductivePower(Operand);
+      }
+
+      I.getAllMetadata(MDs);
+      Score += MDs.size();
+      MDs.clear();
+    }
+  }
+
+  return Score;
+}
+
+uint64_t ReducerWorkItem::computeIRComplexityScore() const {
+  uint64_t Score = 0;
+
+  const Module &M = getModule();
+  Score += M.named_metadata_size();
+
+  SmallVector<std::pair<unsigned, MDNode *>, 32> GlobalMetadata;
+  for (const GlobalVariable &GV : M.globals()) {
+    ++Score;
+
+    if (GV.hasInitializer())
+      ++Score;
+
+    // TODO: Account for linkage?
+
+    GV.getAllMetadata(GlobalMetadata);
+    Score += GlobalMetadata.size();
+    GlobalMetadata.clear();
+  }
+
+  for (const Function &F : M)
+    Score += computeIRComplexityScoreImpl(F);
+
+  return Score;
+}