[llvm-reduce] Introduce operands-skip pass.

[Meinersbur]

Summary

Add a new "operands-skip" pass whose goal is to remove instructions in the middle of dependency chains. For instance:

%baseptr = alloca i32
%arrayidx = getelementptr i32, i32* %baseptr, i32 %idxprom
store i32 42, i32* %arrayidx

might be reducible to

%baseptr = alloca i32
%arrayidx = getelementptr ...  ; now dead, together with the computation of %idxprom
store i32 42, i32* %baseptr

Other passes would either replace %baseptr with undef (operands, instructions) or move it to become a function argument (operands-to-args), both of which might fail the interestingness check.

In principle the implementation allows operand replacement with any value or instruction in the function that passes the filter constraints (same type, dominance, "more reduced"), but is limited in this patch to values that are directly or indirectly used to compute the current operand value, motivated by the example above. Additionally, function arguments are added to the candidate set which helps reducing the number of relevant arguments mitigating a concern of too many arguments mentioned in https://reviews.llvm.org/D110274#3025013.

Possible future extensions:

• Instead of requiring the same type, bitcast/trunc/zext could be automatically inserted for some more flexibility.
• If undef is added to the candidate set, "operands-skip"is able to produce any reduction that "operands" can do. Additional candidates might be zero and one, where the "reductive power" classification can prefer one over the other. If undefined behaviour should not be introduced, undef can be removed from the candidate set.

[aeubanks]

this looks very cool!

llvm/test/tools/llvm-reduce/operands-skip.ll

3

leftover debugging?

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

23

49

I thought we preferred ConstantData over undef

76

consistency

78

I'd prefer a function_ref<void(Use &, ArrayRef<Value *>)> over templates

81–84

DominatorTree DT(F);
the pass manager infra doesn't give us anything here

86

117

133

is && necessary? the result of collectReferencedValues() should be moved into a local variable

[Meinersbur]

• Address revier comments
• Skip over declarations

[Meinersbur]

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

49

You mentioned this as "reduce to undef/1/0, probably in that order" in https://reviews.llvm.org/D110274#3062642, but I didn't interpret this as consensus. My approach here was to mimic the current behaviour where everything is reduced to undef if possible. If introducing undef is not desired, then an option could avoid adding it to the set of possibilities. In this approach, it could only be added if there there is already an undef somewhere.

Changing the order of preference might still be better. I changed it accordingly.

133

It's not necessary, but would save the invocation of move-ctor.

143

removed && here too

[aeubanks]

the latest diff also contains the reduce-operands-to-args pass

[Meinersbur]

• Rebase
• Remove operands-to-args pass from diff

[aeubanks]

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

56

an UndefValue is a ConstantData, so this should be moved into the ConstantData if block above

[Meinersbur]

Address last comment before landing

llvm/test/tools/llvm-reduce/operands-skip.ll

+; RUN: llvm-reduce %s -o %t --delta-passes=operands-skip --test FileCheck --test-arg %s --test-arg --match-full-lines --test-arg --check-prefix=INTERESTING --test-arg --input-file
+; RUN: FileCheck %s --input-file %t --check-prefixes=REDUCED
+
+; INTERESTING: store i32 43, i32* {{(%imm|%indirect)}}, align 4
+; REDUCED:     store i32 43, i32* %imm, align 4
+
+; INTERESTING: store i32 44, i32* {{(%imm|%indirect|%phi)}}, align 4
+; REDUCED:     store i32 44, i32* %phi, align 4
+
+; INTERESTING: store i32 45, i32* {{(%imm|%indirect|%phi|%val)}}, align 4
+; REDUCED:     store i32 45, i32* %val, align 4
+
+; INTERESTING: store i32 46, i32* {{(%imm|%indirect|%phi|%val|@Global)}}, align 4
+; REDUCED:     store i32 46, i32* @Global, align 4
+
+; INTERESTING: store i32 47, i32* {{(%imm|%indirect|%phi|%val|@Global|%arg2)}}, align 4
+; REDUCED:     store i32 47, i32* %arg2, align 4
+
+; INTERESTING: store i32 48, i32* {{(%imm|%indirect|%phi|%val|@Global|%arg2|%arg1)}}, align 4
+; REDUCED:     store i32 48, i32* %arg1, align 4
+
+; INTERESTING: store i32 49, i32* {{(%imm|%indirect|%phi|%val|@Global|%arg2|%arg1|null)}}, align 4
+; REDUCED:     store i32 49, i32* null, align 4
+
+; REDUCED:     store i32 50, i32* %arg1, align 4
+; REDUCED:     store i32 51, i32* %arg1, align 4
+
+@Global = global i32 42
+
+define void @func(i32* %arg1, i32* %arg2) {
+entry:
+  %val = getelementptr i32, i32* getelementptr (i32, i32* @Global, i32 1), i32 2
+  br i1 undef, label %branch, label %loop
+
+branch:
+  %nondominating1 = getelementptr i32, i32* %val, i32 3
+  br label %loop
+
+loop:
+  %phi = phi i32* [ null, %entry ], [ %nondominating1, %branch ], [ %nondominating2, %loop ]
+  %imm = getelementptr i32, i32* %phi, i32 4
+  %indirect = getelementptr i32, i32* %imm, i32 5
+
+  store i32 43, i32* %imm, align 4 ; Don't reduce to %indirect (not "more reduced" than %imm)
+  store i32 44, i32* %imm, align 4 ; Reduce to %phi
+  store i32 45, i32* %imm, align 4 ; Reduce to %val
+  store i32 46, i32* %imm, align 4 ; Reduce to @Global
+  store i32 47, i32* %imm, align 4 ; Reduce to %arg1
+  store i32 48, i32* %imm, align 4 ; Reduce to %arg2
+  store i32 49, i32* %imm, align 4 ; Reduce to null
+
+  %nondominating2 = getelementptr i32, i32* %indirect, i32 6
+  br i1 undef, label %loop, label %exit
+
+exit:
+  store i32 50, i32* %arg2, align 4 ; Reduce to %arg1 (compactify function arguments)
+  store i32 51, i32* %arg1, align 4 ; Don't reduce
+  ret void
+}

llvm/tools/llvm-reduce/CMakeLists.txt

add_llvm_tool(llvm-reduce
   deltas/ReduceGlobalVarInitializers.cpp
   deltas/ReduceGlobalVars.cpp
   deltas/ReduceInstructions.cpp
   deltas/ReduceMetadata.cpp
   deltas/ReduceModuleData.cpp
   deltas/ReduceOperandBundles.cpp
   deltas/ReduceSpecialGlobals.cpp
   deltas/ReduceOperands.cpp
+  deltas/ReduceOperandsSkip.cpp
   deltas/ReduceOperandsToArgs.cpp
   deltas/ReduceInstructionsMIR.cpp
   llvm-reduce.cpp
 
   DEPENDS
   intrinsics_gen
   )

llvm/tools/llvm-reduce/DeltaManager.cpp

 #include "deltas/ReduceGlobalVarInitializers.h"
 #include "deltas/ReduceGlobalVars.h"
 #include "deltas/ReduceInstructions.h"
 #include "deltas/ReduceInstructionsMIR.h"
 #include "deltas/ReduceMetadata.h"
 #include "deltas/ReduceModuleData.h"
 #include "deltas/ReduceOperandBundles.h"
 #include "deltas/ReduceOperands.h"
+#include "deltas/ReduceOperandsSkip.h"
 #include "deltas/ReduceOperandsToArgs.h"
 #include "deltas/ReduceSpecialGlobals.h"
 #include "llvm/Support/CommandLine.h"
 
 using namespace llvm;
 
 static cl::opt<std::string>
     DeltaPasses("delta-passes",
#define DELTA_PASSES                                                           \
   DELTA_PASS("global-variables", reduceGlobalsDeltaPass)                       \
   DELTA_PASS("metadata", reduceMetadataDeltaPass)                              \
   DELTA_PASS("arguments", reduceArgumentsDeltaPass)                            \
   DELTA_PASS("instructions", reduceInstructionsDeltaPass)                      \
   DELTA_PASS("operands-zero", reduceOperandsZeroDeltaPass)                     \
   DELTA_PASS("operands-one", reduceOperandsOneDeltaPass)                       \
   DELTA_PASS("operands-undef", reduceOperandsUndefDeltaPass)                   \
   DELTA_PASS("operands-to-args", reduceOperandsToArgsDeltaPass)                \
+  DELTA_PASS("operands-skip", reduceOperandsSkipDeltaPass)                     \
   DELTA_PASS("operand-bundles", reduceOperandBundesDeltaPass)                  \
   DELTA_PASS("attributes", reduceAttributesDeltaPass)                          \
   DELTA_PASS("module-data", reduceModuleDataDeltaPass)
 
 #define DELTA_PASSES_MIR                                                       \
   DELTA_PASS("instructions", reduceInstructionsMIRDeltaPass)
 
 static void runAllDeltaPasses(TestRunner &Tester) {

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

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEOPERANDSSKIP_H
+#define LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEOPERANDSSKIP_H
+
+#include "Delta.h"
+
+namespace llvm {
+void reduceOperandsSkipDeltaPass(TestRunner &Test);
+} // namespace llvm
+
+#endif /* LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEOPERANDSSKIP_H */

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

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "ReduceOperandsSkip.h"
+#include "llvm/ADT/Sequence.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Operator.h"
+
+using namespace llvm;
+
+/// Collect all values that are directly or indirectly referenced by @p Root,
+/// including Root itself. This is a BF search such that the more steps needed
+/// to get to the reference, the more behind it is found in @p Collection. Each
+/// step could be its own reduction, therefore we consider later values "more
+/// reduced".
+static SetVector<Value *> collectReferencedValues(Value *Root) {
+  SetVector<Value *> Refs;
+  std::deque<Value *> Worklist;
+  Worklist.push_back(Root);
+
+  while (!Worklist.empty()) {
+    Value *Val = Worklist.front();
+    Worklist.pop_front();
+    if (!Refs.insert(Val))
+      continue;
+
+    if (auto *O = dyn_cast<Operator>(Val)) {
+      for (Use &Op : O->operands())
+        Worklist.push_back(Op.get());
+    }
+  }
+
+  return Refs;
+}
+
+/// Return a reduction priority for @p V. A higher values means "more reduced".
+static int classifyReductivePower(Value *V) {
+  if (auto *C = dyn_cast<ConstantData>(V)) {
+    if (isa<UndefValue>(V))
+      return 4;
+    if (C->isNullValue())
+      return 7;
+    if (C->isOneValue())
+      return 6;
+    return 5;
+  }
+
+  if (isa<Argument>(V))
+    return 3;
+
+  if (isa<GlobalValue>(V))
+    return 2;
+
+  if (isa<Constant>(V))
+    return 1;
+
+  if (isa<Instruction>(V))
+    return -1;
+
+  return 0;
+}
+
+/// Calls @p Callback for every reduction opportunity in @p F. Used by
+/// countOperands() and extractOperandsFromModule() to ensure consistency
+/// between the two.
+static void
+opportunities(Function &F,
+              function_ref<void(Use &, ArrayRef<Value *>)> Callback) {
+  if (F.isDeclaration())
+    return;
+
+  // Need DominatorTree to find out whether an SSA value can be referenced.
+  DominatorTree DT(F);
+
+  // Return whether @p LHS is "more reduced" that @p RHS. That is, whether
+  // @p RHS should be preferred over @p LHS in a reduced output. This is a
+  // partial order, a Value may not be preferable over another.
+  auto IsMoreReduced = [&DT](Value *LHS, Value *RHS) -> bool {
+    // A value is not more reduced than itself.
+    if (LHS == RHS)
+      return false;
+
+    int ReductivePowerDiff =
+        classifyReductivePower(RHS) - classifyReductivePower(LHS);
+    if (ReductivePowerDiff != 0)
+      return ReductivePowerDiff < 0;
+
+    // LHS is more reduced if it is defined further up the dominance tree. In a
+    // chain of definitions,
+    //
+    // %a = ..
+    // %b = op %a
+    // %c = op %b
+    //
+    // every use of %b can be replaced by %a, but not by a use of %c. That is, a
+    // use %c can be replaced in steps first by %b, then by %a, making %a the
+    // "more reduced" choice that skips over more instructions.
+    auto *LHSInst = dyn_cast<Instruction>(LHS);
+    auto *RHSInst = dyn_cast<Instruction>(RHS);
+    if (LHSInst && RHSInst) {
+      if (DT.dominates(LHSInst, RHSInst))
+        return true;
+    }
+
+    // Compress the number of used arguments by prefering the first ones. Unused
+    // trailing argument can be removed by the arguments pass.
+    auto *LHSArg = dyn_cast<Argument>(LHS);
+    auto *RHSArg = dyn_cast<Argument>(RHS);
+    if (LHSArg && RHSArg) {
+      if (LHSArg->getArgNo() < RHSArg->getArgNo())
+        return true;
+    }
+
+    return false;
+  };
+
+  for (Instruction &I : instructions(&F)) {
+    for (Use &Op : I.operands()) {
+      Value *OpVal = Op.get();
+
+      // Collect refenced values as potential replacement candidates.
+      SetVector<Value *> ReferencedVals = collectReferencedValues(OpVal);
+
+      // Regardless whether referenced, add the function arguments as
+      // replacement possibility with the goal of reducing the number of (used)
+      // function arguments, possibly created by the the operands-to-args.
+      for (Argument &Arg : F.args())
+        ReferencedVals.insert(&Arg);
+
+      // After all candidates have been added, it doesn't need to be a set
+      // anymore.
+      std::vector<Value *> Candidates = ReferencedVals.takeVector();
+
+      // Remove ineligible candidates.
+      llvm::erase_if(Candidates, [&, OpVal](Value *V) {
+        // Candidate value must have the same type.
+        if (OpVal->getType() != V->getType())
+          return true;
+
+        // Only consider candidates that are "more reduced" than the original
+        // value. This explicitly also rules out candidates with the same
+        // reduction power. This is to ensure that repeated invocations of this
+        // pass eventually reach a fixpoint without switch back and forth
+        // between two opportunities with the same reductive power.
+        return !IsMoreReduced(V, OpVal);
+      });
+
+      if (Candidates.empty())
+        continue;
+
+      // collectReferencedValues pushed the more reductive values to the end of
+      // the collection, but we need them at the front.
+      std::reverse(Candidates.begin(), Candidates.end());
+
+      // Independency of collectReferencedValues's idea of reductive power,
+      // ensure the the partial order of IsMoreReduced is enforced.
+      llvm::stable_sort(Candidates, IsMoreReduced);
+
+      Callback(Op, Candidates);
+    }
+  }
+}
+
+static void extractOperandsFromModule(Oracle &O, Module &Program) {
+  for (Function &F : Program.functions()) {
+    SmallVector<std::pair<Use *, Value *>> Replacements;
+    opportunities(F, [&](Use &Op, ArrayRef<Value *> Candidates) {
+      // Only apply the candidate the Oracle selected to keep that is the most
+      // reduced. Candidates with less reductive power can be interpreted as an
+      // intermediate step that is immediately replaced with the more reduced
+      // one. The number of shouldKeep() calls must be independent of the result
+      // of previous shouldKeep() calls to keep the total number of calls
+      // in-sync with what countOperands() has computed.
+      bool AlreadyReplaced = false;
+      for (Value *C : Candidates) {
+        bool Keep = O.shouldKeep();
+        if (AlreadyReplaced || Keep)
+          continue;
+
+        // Replacing the operand value immediately would influence the candidate
+        // set for the following operands. Delay it until after all candidates
+        // have been determined.
+        Replacements.push_back({&Op, C});
+
+        AlreadyReplaced = true;
+      }
+    });
+
+    for (std::pair<Use *, Value *> P : Replacements)
+      P.first->set(P.second);
+  }
+}
+
+static int countOperands(Module *Program) {
+  int Count = 0;
+
+  for (Function &F : Program->functions()) {
+    opportunities(F, [&](Use &Op, ArrayRef<Value *> Candidates) {
+      Count += llvm::size(Candidates);
+    });
+  }
+
+  return Count;
+}
+
+void llvm::reduceOperandsSkipDeltaPass(TestRunner &Test) {
+  errs() << "*** Reducing operands by skipping over instructions ...\n";
+  int Count = countOperands(&Test.getProgram());
+  runDeltaPass(Test, Count, extractOperandsFromModule);
+}