[llvm-reduce] Reducing call operand bundles

[lebedev.ri]

Summary

This would have been marginally useful to me during/for rG7ea46aee3670981827c04df89b2c3a1cbdc7561b.

With ongoing migration to representing assumes via operand bundles on the assume, this will be gradually more useful.

[lebedev.ri]

I must say, i found the reduction infra to be a little bit rough.
What do people think about the following:

[nickdesaulniers]

llvm/lib/IR/Instructions.cpp

251

unused param?

llvm/tools/llvm-reduce/deltas/ReduceOperandBundles.cpp

35

if you move this up, then you don't need to wrap the forward declaration of class Module above.

79

explicit for one operand constructors?

[lebedev.ri]

@nickdesaulniers thank you for taking a look!
Addressing review nits.

[nickdesaulniers]

llvm/include/llvm/IR/InstrTypes.h

1145

If we're going to create a new interface to CallBase, I kind of want to use it in more than just one place. In particular, at least InlineFunction() in llvm/lib/Transforms/Utils/InlineFunction.cpp looks like a perfect candidate to use this. There may be more, if you grep for the casts. In that way, this change might help DRY up and also remove a repetitious pattern. WDYT?

[lebedev.ri]

Split CallBase::Create() into a separate patch.

[lebedev.ri]

llvm/include/llvm/IR/InstrTypes.h

1145

Doesn't really sound interesting to me.

[nickdesaulniers]

Doesn't really sound interesting to me.

LOL, then why did you split it?

[lebedev.ri]

Actually upload up-to-date patch now.

llvm/tools/llvm-reduce/deltas/ReduceOperandBundles.cpp

35

Hold up, that's actually bogus.
https://godbolt.org/z/0qTwwz

[nickdesaulniers]

llvm/tools/llvm-reduce/deltas/ReduceOperandBundles.cpp

35

or just include the appropriate header for llvm::Module and forget forward declaration?

[lebedev.ri]

llvm/tools/llvm-reduce/deltas/ReduceOperandBundles.cpp

35

But here we don't need to know what Module actually is though, just a pointer to it.
The current include list is what IWYU suggests,
and i believe cleanup elsewhere in codebase is ongoing in the same direction.

[Tyker]

Thank you for reducing rG7ea46aee3670981827c04df89b2c3a1cbdc7561b
this seems quite useful.

llvm/tools/llvm-reduce/deltas/ReduceOperandBundles.cpp

139

Maybe we should make CallsToRefine a MapVector since the association from a index to a Bundle depends on its order in the map.
and the key depends on a pointer value that will change when the Module gets cloned.

[lebedev.ri]

llvm/tools/llvm-reduce/deltas/ReduceOperandBundles.cpp

139

No, the current logic is correct, that map doesn't live that long.

[Tyker]

llvm/tools/llvm-reduce/deltas/ReduceOperandBundles.cpp

139

here is the situation i think fails.

extractOperandBundesFromModule is called a first time and generate a reduction.
the reduction isn't considered interesting.
extractOperandBundesFromModule is called a second time with different chunks to keep.
but the association from an index to a Bundle is different from the first time because the module isn't the same
the association from a index to a Bundle isn't the same,
so extractOperandBundesFromModule can remove the same operand bundle a second time and not have tried every operand bundles at the end of the passe.

[lebedev.ri]

llvm/tools/llvm-reduce/deltas/ReduceOperandBundles.cpp

139

In reduceOperandBundesDeltaPass(), we tell runDeltaPass() how many features (here: bundles)
we have in this module M0. It then comes with different chunks to keep and tells us
to mutate the module Mc (which is a perfect clone of M0).

It is up to us to actually enumerate the features (here: bundles).
As long as the mapping is stable, i.e. we get the same result
when calling extractOperandBundesFromModule() on the same input,
we're good.

[Tyker]

llvm/tools/llvm-reduce/deltas/ReduceOperandBundles.cpp

139

when calling extractOperandBundesFromModule() on the same input, we're good.

i agree but runDeltaPass makes clones of modules before giving them to extractOperandBundesFromModule to modify.
so the pointer values of Modules will not be the same across runs of extractOperandBundesFromModule even if the Modules are identical.

[lebedev.ri]

llvm/tools/llvm-reduce/deltas/ReduceOperandBundles.cpp

139

Sure, but can you point me at the spot where you believe that would matter?

[Tyker]

llvm/tools/llvm-reduce/deltas/ReduceOperandBundles.cpp

139

the key of the Map depends on pointer values

[lebedev.ri]

llvm/tools/llvm-reduce/deltas/ReduceOperandBundles.cpp

139

R.CallsToRefine is indeed a map, with key being CallBase *.
We *just* built that map, for this very Mc we were provided.
I'm still not seeing where pointer order would matter..

[Tyker]

llvm/tools/llvm-reduce/deltas/ReduceOperandBundles.cpp

139

the map depends on pointer values so its ordering is different on each run.
the map is iterated upon and the iteration order affects the mapping from Index to Feature(Bundles)
so every run of has a different mapping.

[lebedev.ri]

llvm/tools/llvm-reduce/deltas/ReduceOperandBundles.cpp

139

Ahh, that is what you mean. No, it's the other way around.
Do you agree that the only place we iterate over the map is:

for_each(R.CallsToRefine, [](const auto &P) {
  return maybeRewriteCallWithDifferentBundles(P.first, P.second);
});

?

But as you can see in maybeRewriteCallWithDifferentBundles(),
it's second param is the indexes of bundle to preserve.
So we have already performed the mapping before iterating over the map.

[Tyker]

llvm/tools/llvm-reduce/deltas/ReduceOperandBundles.cpp

139

you are right, sorry for my confusion.

[lebedev.ri]

llvm/tools/llvm-reduce/deltas/ReduceOperandBundles.cpp

139

NP, thank you for taking a look!

llvm/include/llvm/IR/InstrTypes.h

protected:
 
   /// Get the number of extra operands for instructions that don't have a fixed
   /// number of extra operands.
   unsigned getNumSubclassExtraOperandsDynamic() const;
 
 public:
   using Instruction::getContext;
 
+  /// Create a clone of \p CB with a different set of operand bundles and
+  /// insert it before \p InsertPt.
+  ///
+  /// The returned call instruction is identical \p CB in every way except that
+  /// the operand bundles for the new instruction are set to the operand bundles
+  /// in \p Bundles.
+  static CallBase *Create(CallBase *CB, ArrayRef<OperandBundleDef> Bundles,
+                          Instruction *InsertPt = nullptr);
+
   static bool classof(const Instruction *I) {
     return I->getOpcode() == Instruction::Call ||
            I->getOpcode() == Instruction::Invoke ||
            I->getOpcode() == Instruction::CallBr;
   }
   static bool classof(const Value *V) {
     return isa<Instruction>(V) && classof(cast<Instruction>(V));
   }

llvm/lib/IR/Instructions.cpp

void LandingPadInst::addClause(Constant *Val) {
   setNumHungOffUseOperands(getNumOperands() + 1);
   getOperandList()[OpNo] = Val;
 }
 
 //===----------------------------------------------------------------------===//
 //                        CallBase Implementation
 //===----------------------------------------------------------------------===//
 
+CallBase *CallBase::Create(CallBase *CB, ArrayRef<OperandBundleDef> Bundles,
+                           Instruction *InsertPt) {
+  switch (CB->getOpcode()) {
+  case Instruction::Call:
+    return CallInst::Create(cast<CallInst>(CB), Bundles, InsertPt);
+  case Instruction::Invoke:
+    return InvokeInst::Create(cast<InvokeInst>(CB), Bundles, InsertPt);
+  case Instruction::CallBr:
+    return CallBrInst::Create(cast<CallBrInst>(CB), Bundles, InsertPt);
+  default:
+    llvm_unreachable("Unknown CallBase sub-class!");
+  }
+}
+
 Function *CallBase::getCaller() { return getParent()->getParent(); }
 
 unsigned CallBase::getNumSubclassExtraOperandsDynamic() const {
   assert(getOpcode() == Instruction::CallBr && "Unexpected opcode!");
   return cast<CallBrInst>(this)->getNumIndirectDests() + 1;
 }
 
 bool CallBase::isIndirectCall() const {

llvm/test/Reduce/remove-operand-bundles.ll

+; Test that llvm-reduce can remove uninteresting operand bundles from calls.
+;
+; RUN: rm -rf %t
+; RUN: llvm-reduce --test FileCheck --test-arg --check-prefixes=CHECK-ALL,CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
+; RUN: cat %t | FileCheck --check-prefixes=CHECK-ALL,CHECK-FINAL %s
+
+; CHECK-ALL: declare void @f1()
+; CHECK-ALL: declare void @f2()
+; CHECK-ALL: declare void @f3()
+declare void @f1()
+declare void @f2()
+declare void @f3()
+
+; CHECK-FINAL-LABEL: define void @interesting(i32 %arg0, i32 %arg1, i32 %arg2) {
+; CHECK-FINAL-NEXT:  entry:
+; CHECK-FINAL-NEXT:    call void @f1() [ "bundle0"(), "align"(i32 %arg0), "whatever0"() ]
+; CHECK-FINAL-NEXT:    call void @f2()
+; CHECK-FINAL-NEXT:    call void @f3() [ "align"(i32 %arg2) ]
+; CHECK-FINAL-NEXT:    ret void
+; CHECK-FINAL-NEXT:  }
+define void @interesting(i32 %arg0, i32 %arg1, i32 %arg2) {
+entry:
+; CHECK-INTERESTINGNESS-LABEL: @interesting(
+
+; CHECK-INTERESTINGNESS: call void @f1()
+; CHECK-INTERESTINGNESS: "bundle0"()
+; CHECK-INTERESTINGNESS: "align"(i32 %arg0)
+; CHECK-INTERESTINGNESS: "whatever0"()
+
+; CHECK-INTERESTINGNESS: call void @f2()
+
+; CHECK-INTERESTINGNESS: call void @f3()
+; CHECK-INTERESTINGNESS: "align"(i32 %arg2)
+
+; CHECK-INTERESTINGNESS: ret
+
+  call void @f1() [ "bundle0"(),        "align"(i32 %arg0), "whatever0"() ]
+  call void @f2() [ "align"(i32 %arg1), "whatever1"(),      "bundle1"() ]
+  call void @f3() [ "whatever2"(),      "bundle2"(),        "align"(i32 %arg2) ]
+  ret void
+}

llvm/tools/llvm-reduce/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   AllTargetsAsmParsers
   AllTargetsCodeGens
   AllTargetsDescs
   AllTargetsInfos
   Core
   IRReader
   Support
   Target
   TransformUtils
   )
 
 add_llvm_tool(llvm-reduce
-  llvm-reduce.cpp
   TestRunner.cpp
   deltas/Delta.cpp
-  deltas/ReduceFunctions.cpp
-  deltas/ReduceGlobalVars.cpp
-  deltas/ReduceMetadata.cpp
   deltas/ReduceArguments.cpp
   deltas/ReduceBasicBlocks.cpp
+  deltas/ReduceFunctions.cpp
+  deltas/ReduceGlobalVars.cpp
   deltas/ReduceInstructions.cpp
+  deltas/ReduceMetadata.cpp
+  deltas/ReduceOperandBundles.cpp
+  llvm-reduce.cpp
 
   DEPENDS
   intrinsics_gen
   )

llvm/tools/llvm-reduce/DeltaManager.h

 //===----------------------------------------------------------------------===//
 
 #include "TestRunner.h"
 #include "deltas/Delta.h"
 #include "deltas/ReduceArguments.h"
 #include "deltas/ReduceBasicBlocks.h"
 #include "deltas/ReduceFunctions.h"
 #include "deltas/ReduceGlobalVars.h"
-#include "deltas/ReduceMetadata.h"
 #include "deltas/ReduceInstructions.h"
+#include "deltas/ReduceMetadata.h"
+#include "deltas/ReduceOperandBundles.h"
 
 namespace llvm {
 
 // TODO: Add CLI option to run only specified Passes (for unit tests)
 inline void runDeltaPasses(TestRunner &Tester) {
   reduceFunctionsDeltaPass(Tester);
   reduceBasicBlocksDeltaPass(Tester);
   reduceGlobalsDeltaPass(Tester);
   reduceMetadataDeltaPass(Tester);
   reduceArgumentsDeltaPass(Tester);
   reduceInstructionsDeltaPass(Tester);
+  reduceOperandBundesDeltaPass(Tester);
   // TODO: Implement the remaining Delta Passes
 }
 
 } // namespace llvm

llvm/tools/llvm-reduce/deltas/ReduceOperandBundles.h

+//===- ReduceOperandBundes.h - Specialized Delta Pass ---------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a function which calls the Generic Delta pass in order
+// to reduce uninteresting operand bundes from calls.
+//
+//===----------------------------------------------------------------------===//
+
+namespace llvm {
+
+class TestRunner;
+
+void reduceOperandBundesDeltaPass(TestRunner &Test);
+
+} // namespace llvm

llvm/tools/llvm-reduce/deltas/ReduceOperandBundles.cpp

+//===- ReduceOperandBundes.cpp - Specialized Delta Pass -------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a function which calls the Generic Delta pass in order
+// to reduce uninteresting operand bundes from calls.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ReduceOperandBundles.h"
+#include "Delta.h"
+#include "TestRunner.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/ScopeExit.h"
+#include "llvm/ADT/Sequence.h"
+#include "llvm/ADT/iterator_range.h"
+#include "llvm/IR/InstVisitor.h"
+#include "llvm/IR/InstrTypes.h"
+#include "llvm/Support/raw_ostream.h"
+#include <algorithm>
+#include <iterator>
+#include <vector>
+
+using namespace llvm;
+
+class Module;
+
+namespace {
+
+/// Provides opaque interface for querying into ChunksToKeep without having to
+/// actually understand what is going on.
+struct Oracle {
+  /// Out of all the features that we promised to be,
+  /// how many have we already processed? 1-based!
+  int Index = 1;
+
+  /// The actual workhorse, contains the knowledge whether or not
+  /// some particular feature should be preserved this time.
+  ArrayRef<Chunk> ChunksToKeep;
+
+public:
+  Oracle(ArrayRef<Chunk> ChunksToKeep_) : ChunksToKeep(ChunksToKeep_) {}
+
+  /// Should be called for each feature on which we are operating.
+  /// Name is self-explanatory - if returns true, then it should be preserved.
+  bool shouldKeep() {
+    if (ChunksToKeep.empty())
+      return false; // All further features are to be discarded.
+
+    // Does the current (front) chunk contain such a feature?
+    bool ShouldKeep = ChunksToKeep.front().contains(Index);
+    auto _ = make_scope_exit([&]() { ++Index; }); // Next time - next feature.
+
+    // Is this the last feature in the chunk?
+    if (ChunksToKeep.front().end == Index)
+      ChunksToKeep = ChunksToKeep.drop_front(); // Onto next chunk.
+
+    return ShouldKeep;
+  }
+};
+
+/// Given ChunksToKeep, produce a map of calls and indexes of operand bundles
+/// to be preserved for each call.
+class OperandBundleRemapper : public InstVisitor<OperandBundleRemapper> {
+  Oracle O;
+
+public:
+  DenseMap<CallBase *, std::vector<unsigned>> CallsToRefine;
+
+  explicit OperandBundleRemapper(ArrayRef<Chunk> ChunksToKeep)
+      : O(ChunksToKeep) {}
+
+  /// So far only CallBase sub-classes can have operand bundles.
+  /// Let's see which of the operand bundles of this call are to be kept.
+  void visitCallBase(CallBase &Call) {
+    if (!Call.hasOperandBundles())
+      return; // No bundles to begin with.
+
+    // Insert this call into map, we will likely want to rebuild it.
+    auto &OperandBundlesToKeepIndexes = CallsToRefine[&Call];
+    OperandBundlesToKeepIndexes.reserve(Call.getNumOperandBundles());
+
+    // Enumerate every operand bundle on this call.
+    for_each(seq(0U, Call.getNumOperandBundles()), [&](unsigned BundleIndex) {
+      if (O.shouldKeep()) // Should we keep this one?
+        OperandBundlesToKeepIndexes.emplace_back(BundleIndex);
+    });
+  }
+};
+
+struct OperandBundleCounter : public InstVisitor<OperandBundleCounter> {
+  /// How many features (in this case, operand bundles) did we count, total?
+  int OperandBundeCount = 0;
+
+  OperandBundleCounter() {}
+
+  /// So far only CallBase sub-classes can have operand bundles.
+  void visitCallBase(CallBase &Call) {
+    // Just accumulate the total number of operand bundles.
+    OperandBundeCount += Call.getNumOperandBundles();
+  }
+};
+
+} // namespace
+
+static void maybeRewriteCallWithDifferentBundles(
+    CallBase *OrigCall, ArrayRef<unsigned> OperandBundlesToKeepIndexes) {
+  if (OperandBundlesToKeepIndexes.size() == OrigCall->getNumOperandBundles())
+    return; // Not modifying operand bundles of this call after all.
+
+  std::vector<OperandBundleDef> NewBundles;
+  NewBundles.reserve(OperandBundlesToKeepIndexes.size());
+
+  // Actually copy over the bundles that we want to keep.
+  transform(OperandBundlesToKeepIndexes, std::back_inserter(NewBundles),
+            [OrigCall](unsigned Index) {
+              return OperandBundleDef(OrigCall->getOperandBundleAt(Index));
+            });
+
+  // Finally actually replace the bundles on the call.
+  CallBase *NewCall = CallBase::Create(OrigCall, NewBundles);
+  OrigCall->replaceAllUsesWith(NewCall);
+  OrigCall->eraseFromParent();
+}
+
+/// Removes out-of-chunk operand bundles from calls.
+static void extractOperandBundesFromModule(std::vector<Chunk> ChunksToKeep,
+                                           Module *Program) {
+  OperandBundleRemapper R(ChunksToKeep);
+  R.visit(Program);
+
+  for_each(R.CallsToRefine, [](const auto &P) {
+    return maybeRewriteCallWithDifferentBundles(P.first, P.second);
+  });
+}
+
+/// Counts the amount of operand bundles.
+static int countOperandBundes(Module *Program) {
+  OperandBundleCounter C;
+
+  // TODO: Silence index with --quiet flag
+  outs() << "----------------------------\n";
+  C.visit(Program);
+  outs() << "Number of operand bundles: " << C.OperandBundeCount << "\n";
+
+  return C.OperandBundeCount;
+}
+
+void llvm::reduceOperandBundesDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing OperandBundes...\n";
+  int OperandBundeCount = countOperandBundes(Test.getProgram());
+  runDeltaPass(Test, OperandBundeCount, extractOperandBundesFromModule);
+}

llvm/utils/gn/secondary/llvm/tools/llvm-reduce/BUILD.gn

sources = [
     "TestRunner.cpp",
     "deltas/Delta.cpp",
     "deltas/ReduceArguments.cpp",
     "deltas/ReduceBasicBlocks.cpp",
     "deltas/ReduceFunctions.cpp",
     "deltas/ReduceGlobalVars.cpp",
     "deltas/ReduceInstructions.cpp",
     "deltas/ReduceMetadata.cpp",
+    "deltas/ReduceOperandBundes.cpp",
     "llvm-reduce.cpp",
   ]
 }