[llvm-reduce] Introduce operands-to-args pass.

[Meinersbur]

Summary

Instead of setting operands to undef as the operands pass does, convert the operands to a function argument. This avoids having to introduce undef values into the IR which have some unpredictability during optimizations.

For instance,

define void @func() {
entry:
  %val = add i32 32, 21
  store i32 %val, i32* null
  ret void
}

is reduced to

define void @func(i32 %val) {
entry:
  %val1 = add i32 32, 21
  store i32 %val, i32* null
  ret void
}

(note that the instruction %val is renamed to %val1 when printing the IR to avoid ambiguity; ideally %val1 would be removed by dce or the instruction reduction pass)

Any call to @func is replaced with a call to the function with the new signature and filled with undef. This is not ideal for IPA passes, but those out-of-scope for now.

[dblaikie]

generally sounds good to me - though I'll probably leave more detailed review/approval to other folks who have been working more closely on llvm-reduce

llvm/test/tools/llvm-reduce/operands-to-args.ll

18–22

I think the dominant terminology here is "interesting" rather than "exciting" - probably best to keep with that for consistency?

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

22–30

could potentially rephrase this with llvm::all_of

58–59

Generally I'd sink these into the loop (usual keeping variables with the smallest scope necessary - simplifies the code/logic/reasoning) unless there's especially strong evidence that the memory reuse has observable performance improvements?

Alternatively, could the new arguments be created once, and the call-site-specific argument be copied over the start of the SmallVector, without the need to clear/rebuild it each time?

171–179

Any particular reason these loops can't be combined (removing the "Funcs" SmallVector in the process) like the countOperands function below?

[Meinersbur]

• EXCITING->INTERESTING
• sink SmallVector declaration into loop.
• Use all_of

[Meinersbur]

llvm/test/tools/llvm-reduce/operands-to-args.ll

18–22

I used exciting/boring already for D110534. The reason is that interesting is a substring of uninteresting and therefore pretty much unusable with FileCheck. It does not apply here, so I changed it to INTERESTING.

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

171–179

The Module's function list is modified in substituteOperandWithArgument and invalidates iterators.

[Meinersbur]

• Use make_early_inc_range

[Meinersbur]

• Consistent (non-)use of auto

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

171–179

Using make_early_inc_range now to avoid the invalidated iterator.

[Meinersbur]

• Fix function passed to calll of itself.
• Fix SmallVectorBase::set_size();
• Be more permissive with what can be replaced. In particular, allow replacing constants derived from GlobalValues.

[dblaikie]

Generally sounds about right to me - I'll leave final sign off to other folks more connected to llvm-reduce.

[aeubanks]

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

22

unused F

32

leftover debugging?

35

does isa<Instruction> || isa<GlobalValue> work, instead of these various checks?

47

if this pass runs after the operands pass and the operands pass reduces a bunch of things to undef, doesn't that mostly defeat the purpose of this since we're skipping constants?
and the description mentions that the instruction reduction pass should hopefully clean up dead instructions, but that runs before this pass

[Meinersbur]

• Remove leftovers

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

35

Just isa<GlobalValue> unfortunately does not catch constants such as bitcast (i32* @Global to float*).

47

I myself do not run anything that results in undefs being introduced using the --passes switch. Which passes run are enabled by default currently cannot be defined independently of which passes are available. I myself run llvm-reduce in a fixpoint loop until no more reductions are found, which is already necessary now to get a maximally reduced output.

I'd work on upstreaming more patches supporting this workflow. Until then maybe you could suggest an alternative position in the current pass pipeline? In any case, there is still use in running it after the operands pass in reducing arguments that cannot just set to Undef (or zero with in D110274), but needs a non-constant value.

[aeubanks]

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

47

Makes sense.

llvm/test/tools/llvm-reduce/operands-to-args.ll

+; RUN: llvm-reduce %s -o %t --delta-passes=operands-to-args --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
+
+; REDUCED-LABEL: define void @func(i32 %k, i32* %Local, i32* %Global, float* %0) {
+
+; Keep one reference to the original value.
+; INTERESTING: %[[LOCAL:Local[0-9]*]] = alloca i32, align 4
+; INTERESTING: store i32 42, i32* %[[LOCAL]], align 4
+; INTERESTING: store i32 42, i32* @Global, align 4
+
+; Everything else must use the function argument.
+; REDUCED: store i32 21, i32* %Local, align 4
+; REDUCED: store i32 21, i32* %Global, align 4
+; REDUCED: store i32 0, i32* %Local, align 4
+; REDUCED: store i32 0, i32* %Global, align 4
+; REDUCED: store float 0.000000e+00, float* %0, align 4
+
+; Do not add any arguments for %Keep and @GlobalKeep.
+; INTERESTING: %[[KEEP:LocalKeep[0-9]*]] = add i32 %k, 21
+; INTERESTING: store i32 %[[KEEP]], i32* @GlobalKeep, align 4
+
+; INTERESTING-LABEL: define void @func_caller() {
+; REDUCED:             call void @func(i32 21, i32* undef, i32* undef, float* undef)
+
+
+@Global = global i32 42
+@GlobalKeep = global i32 42
+
+define void @func(i32 %k) {
+entry:
+  %Local = alloca i32, align 4
+
+  store i32 42, i32* %Local, align 4
+  store i32 42, i32* @Global, align 4
+
+  store i32 21, i32* %Local, align 4
+  store i32 21, i32* @Global, align 4
+
+  store i32 0, i32* %Local, align 4
+  store i32 0, i32* @Global, align 4
+
+  store float 0.000000e+00,  float* bitcast (i32* @Global to float*), align 4
+
+  %LocalKeep = add i32 %k, 21
+  store i32 %LocalKeep, i32* @GlobalKeep, align 4
+
+  ret void
+}
+
+
+define void @func_caller() {
+entry:
+  call void @func(i32 21)
+  ret void
+}
+

llvm/test/tools/llvm-reduce/remove-call-site-attributes.ll

 ; Test that llvm-reduce can remove uninteresting operand bundles from calls.
 ;
-; RUN: llvm-reduce --test FileCheck --test-arg --check-prefixes=CHECK-ALL,CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
+; RUN: llvm-reduce --delta-passes=operand-bundles,attributes --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 i32 @f1(i32, i32)
 declare i32 @f1(i32, i32)
 
 ; CHECK-FINAL-LABEL: define i32 @interesting(i32 %arg0, i32 %arg1) {
 ; CHECK-FINAL-NEXT:  entry:
 ; CHECK-FINAL-NEXT:    %r = call "attr0" i32 @f1(i32 "attr4" %arg0, i32 %arg1) #0

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/ReduceOperandsToArgs.cpp
   llvm-reduce.cpp
 
   DEPENDS
   intrinsics_gen
   )

llvm/tools/llvm-reduce/DeltaManager.cpp

 #include "deltas/ReduceGlobalValues.h"
 #include "deltas/ReduceGlobalVarInitializers.h"
 #include "deltas/ReduceGlobalVars.h"
 #include "deltas/ReduceInstructions.h"
 #include "deltas/ReduceMetadata.h"
 #include "deltas/ReduceModuleData.h"
 #include "deltas/ReduceOperandBundles.h"
 #include "deltas/ReduceOperands.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",
                 cl::desc("Delta passes to run, separated by commas. By "
                          "default, run all delta passes."));
 
 #define DELTA_PASSES                                                           \
   DELTA_PASS("special-globals", reduceSpecialGlobalsDeltaPass)                 \
   DELTA_PASS("aliases", reduceAliasesDeltaPass)                                \
   DELTA_PASS("function-bodies", reduceFunctionBodiesDeltaPass)                 \
   DELTA_PASS("functions", reduceFunctionsDeltaPass)                            \
   DELTA_PASS("basic-blocks", reduceBasicBlocksDeltaPass)                       \
   DELTA_PASS("global-values", reduceGlobalValuesDeltaPass)                     \
   DELTA_PASS("global-initializers", reduceGlobalsInitializersDeltaPass)        \
   DELTA_PASS("global-variables", reduceGlobalsDeltaPass)                       \
   DELTA_PASS("metadata", reduceMetadataDeltaPass)                              \
   DELTA_PASS("arguments", reduceArgumentsDeltaPass)                            \
   DELTA_PASS("instructions", reduceInstructionsDeltaPass)                      \
   DELTA_PASS("operands", reduceOperandsDeltaPass)                              \
+  DELTA_PASS("operands-to-args", reduceOperandsToArgsDeltaPass)                \
   DELTA_PASS("operand-bundles", reduceOperandBundesDeltaPass)                  \
   DELTA_PASS("attributes", reduceAttributesDeltaPass)                          \
   DELTA_PASS("module-data", reduceModuleDataDeltaPass)
 
 static void runAllDeltaPasses(TestRunner &Tester) {
 #define DELTA_PASS(NAME, FUNC) FUNC(Tester);
   DELTA_PASSES
 #undef DELTA_PASS

llvm/tools/llvm-reduce/deltas/ReduceOperandsToArgs.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_REDUCEOPERANDSTOARGS_H
+#define LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEOPERANDSTOARGS_H
+
+#include "Delta.h"
+
+namespace llvm {
+void reduceOperandsToArgsDeltaPass(TestRunner &Test);
+} // namespace llvm
+
+#endif /* LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEOPERANDSTOARGS_H */

llvm/tools/llvm-reduce/deltas/ReduceOperandsToArgs.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 "ReduceOperandsToArgs.h"
+#include "Delta.h"
+#include "llvm/ADT/Sequence.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/InstrTypes.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+
+using namespace llvm;
+
+static bool canReplaceFunction(Function *F) {
+  return all_of(F->uses(), [](Use &Op) {
+    if (auto *CI = dyn_cast<CallBase>(Op.getUser()))
+      return &CI->getCalledOperandUse() == &Op;
+    return false;
+  });
+}
+
+static bool canReduceUse(Use &Op) {
+  Value *Val = Op.get();
+  Type *Ty = Val->getType();
+
+  // Only replace operands that can be passed-by-value.
+  if (!Ty->isFirstClassType())
+    return false;
+
+  // Don't pass labels as arguments.
+  if (Ty->isLabelTy())
+    return false;
+
+  // No need to replace values that are already arguments.
+  if (isa<Argument>(Val))
+    return false;
+
+  // Do not replace literals.
+  if (isa<ConstantData>(Val))
+    return false;
+
+  // Do not convert direct function calls to indirect calls.
+  if (auto *CI = dyn_cast<CallBase>(Op.getUser()))
+    if (&CI->getCalledOperandUse() == &Op)
+      return false;
+
+  return true;
+}
+
+/// Goes over OldF calls and replaces them with a call to NewF.
+static void replaceFunctionCalls(Function *OldF, Function *NewF) {
+  SmallVector<CallBase *> Callers;
+  for (Use &U : OldF->uses()) {
+    auto *CI = cast<CallBase>(U.getUser());
+    assert(&U == &CI->getCalledOperandUse());
+    assert(CI->getCalledFunction() == OldF);
+    Callers.push_back(CI);
+  }
+
+  // Call arguments for NewF.
+  SmallVector<Value *> Args(NewF->arg_size(), nullptr);
+
+  // Fill up the additional parameters with undef values.
+  for (auto ArgIdx : llvm::seq<size_t>(OldF->arg_size(), NewF->arg_size())) {
+    Type *NewArgTy = NewF->getArg(ArgIdx)->getType();
+    Args[ArgIdx] = UndefValue::get(NewArgTy);
+  }
+
+  for (CallBase *CI : Callers) {
+    // Preserve the original function arguments.
+    for (auto Z : zip_first(CI->args(), Args))
+      std::get<1>(Z) = std::get<0>(Z);
+
+    // Also preserve operand bundles.
+    SmallVector<OperandBundleDef> OperandBundles;
+    CI->getOperandBundlesAsDefs(OperandBundles);
+
+    // Create the new function call.
+    CallBase *NewCI;
+    if (auto *II = dyn_cast<InvokeInst>(CI)) {
+      NewCI = InvokeInst::Create(NewF, cast<InvokeInst>(II)->getNormalDest(),
+                                 cast<InvokeInst>(II)->getUnwindDest(), Args,
+                                 OperandBundles, CI->getName());
+    } else {
+      assert(isa<CallInst>(CI));
+      NewCI = CallInst::Create(NewF, Args, OperandBundles, CI->getName());
+    }
+    NewCI->setCallingConv(NewF->getCallingConv());
+
+    // Do the replacement for this use.
+    if (!CI->use_empty())
+      CI->replaceAllUsesWith(NewCI);
+    ReplaceInstWithInst(CI, NewCI);
+  }
+}
+
+/// Add a new function argument to @p F for each use in @OpsToReplace, and
+/// replace those operand values with the new function argument.
+static void substituteOperandWithArgument(Function *OldF,
+                                          ArrayRef<Use *> OpsToReplace) {
+  if (OpsToReplace.empty())
+    return;
+
+  SetVector<Value *> UniqueValues;
+  for (Use *Op : OpsToReplace)
+    UniqueValues.insert(Op->get());
+
+  // Determine the new function's signature.
+  SmallVector<Type *> NewArgTypes;
+  llvm::append_range(NewArgTypes, OldF->getFunctionType()->params());
+  size_t ArgOffset = NewArgTypes.size();
+  for (Value *V : UniqueValues)
+    NewArgTypes.push_back(V->getType());
+  FunctionType *FTy =
+      FunctionType::get(OldF->getFunctionType()->getReturnType(), NewArgTypes,
+                        OldF->getFunctionType()->isVarArg());
+
+  // Create the new function...
+  Function *NewF =
+      Function::Create(FTy, OldF->getLinkage(), OldF->getAddressSpace(),
+                       OldF->getName(), OldF->getParent());
+
+  // In order to preserve function order, we move NewF behind OldF
+  NewF->removeFromParent();
+  OldF->getParent()->getFunctionList().insertAfter(OldF->getIterator(), NewF);
+
+  // Preserve the parameters of OldF.
+  ValueToValueMapTy VMap;
+  for (auto Z : zip_first(OldF->args(), NewF->args())) {
+    Argument &OldArg = std::get<0>(Z);
+    Argument &NewArg = std::get<1>(Z);
+
+    NewArg.setName(OldArg.getName()); // Copy the name over...
+    VMap[&OldArg] = &NewArg;          // Add mapping to VMap
+  }
+
+  // Adjust the new parameters.
+  ValueToValueMapTy OldValMap;
+  for (auto Z : zip_first(UniqueValues, drop_begin(NewF->args(), ArgOffset))) {
+    Value *OldVal = std::get<0>(Z);
+    Argument &NewArg = std::get<1>(Z);
+
+    NewArg.setName(OldVal->getName());
+    OldValMap[OldVal] = &NewArg;
+  }
+
+  SmallVector<ReturnInst *, 8> Returns; // Ignore returns cloned.
+  CloneFunctionInto(NewF, OldF, VMap, CloneFunctionChangeType::LocalChangesOnly,
+                    Returns, "", /*CodeInfo=*/nullptr);
+
+  // Replace the actual operands.
+  for (Use *Op : OpsToReplace) {
+    Value *NewArg = OldValMap.lookup(Op->get());
+    auto *NewUser = cast<Instruction>(VMap.lookup(Op->getUser()));
+    NewUser->setOperand(Op->getOperandNo(), NewArg);
+  }
+
+  // Replace all OldF uses with NewF.
+  replaceFunctionCalls(OldF, NewF);
+
+  // Rename NewF to OldF's name.
+  std::string FName = OldF->getName().str();
+  OldF->replaceAllUsesWith(ConstantExpr::getBitCast(NewF, OldF->getType()));
+  OldF->eraseFromParent();
+  NewF->setName(FName);
+}
+
+static void reduceOperandsToArgs(Oracle &O, Module &Program) {
+  SmallVector<Use *> OperandsToReduce;
+  for (Function &F : make_early_inc_range(Program.functions())) {
+    OperandsToReduce.clear();
+    for (Instruction &I : instructions(&F)) {
+      for (Use &Op : I.operands()) {
+        if (!canReduceUse(Op))
+          continue;
+        if (O.shouldKeep())
+          continue;
+
+        OperandsToReduce.push_back(&Op);
+      }
+    }
+
+    substituteOperandWithArgument(&F, OperandsToReduce);
+  }
+}
+
+/// Counts the amount of operands in the module that can be reduced.
+static int countOperands(Module &Program) {
+  int Count = 0;
+
+  for (Function &F : Program.functions()) {
+    if (!canReplaceFunction(&F))
+      continue;
+    for (Instruction &I : instructions(&F)) {
+      for (Use &Op : I.operands()) {
+        if (!canReduceUse(Op))
+          continue;
+        Count += 1;
+      }
+    }
+  }
+
+  return Count;
+}
+
+void llvm::reduceOperandsToArgsDeltaPass(TestRunner &Test) {
+  outs() << "*** Converting operands to function arguments ...\n";
+  int ArgCount = countOperands(Test.getProgram());
+  return runDeltaPass(Test, ArgCount, reduceOperandsToArgs);
+}