[llvm-reduce] Add reduction passes to reduce operands to undef/1/0

[aeubanks]

Summary

Having non-undef constants in a final llvm-reduce output is nicer than
having undefs.

This splits the existing reduce-operands pass into three, one which does
the same as the current pass of reducing to undef, and two more to
reduce to the constant 1 and the constant 0. Do not reduce to undef if
the operand is a ConstantData, and do not reduce 0s to 1s.

Reducing GEP operands very frequently causes invalid IR (since types may
not match up if we index differently into a struct), so don't touch GEPs.

[Meinersbur]

Thanks for the patch, looks useful to me.

I have a concern in that this will repeatedly replace undef->one->zero->undef->... (if possible) when running the passes multiple times. Ideally, I'd run the reduction passes until no more changes can be applied. This can either be done by comparing the Module before & after a round, or checking whether no pass has applied any chunk while still being interesting. In my experimental setup I am using textual comparison of the dumped Module, so this would not a problem, but think we'd want the latter approach for llvm-reduce.

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

23–25

37–39

[aeubanks]

address comments
don't replace ConstantData with undef
don't replace 0 with 1

[Meinersbur]

LGTM

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

23

According to the LLVM coding standard, auto is used only in specific cases.

llvm/test/tools/llvm-reduce/remove-invoked-functions.ll

 ; 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-INTERESTINGNESS: define i32 @maybe_throwing_callee(
 ; CHECK-FINAL: define i32 @maybe_throwing_callee()
 define i32 @maybe_throwing_callee(i32 %arg) {
 ; CHECK-ALL: call void @thrown()
 ; CHECK-INTERESTINGNESS: ret i32
-; CHECK-FINAL: ret i32 undef
+; CHECK-FINAL: ret i32 0
   call void @thrown()
   ret i32 %arg
 }
 
 ; CHECK-ALL: declare void @did_not_throw(i32)
 declare void @did_not_throw(i32)
 
 ; CHECK-ALL: declare void @thrown()

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

-; Test that llvm-reduce can reduce operands to their default values.
+; Test that llvm-reduce can reduce operands
 ;
-; RUN: llvm-reduce --delta-passes=operands --test FileCheck --test-arg --check-prefixes=CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
-; RUN: cat %t | FileCheck %s
+; RUN: llvm-reduce --abort-on-invalid-reduction --delta-passes=operands-undef --test FileCheck --test-arg --check-prefixes=CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
+; RUN: cat %t | FileCheck %s --check-prefixes=CHECK,UNDEF
+; RUN: llvm-reduce --abort-on-invalid-reduction --delta-passes=operands-one --test FileCheck --test-arg --check-prefixes=CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
+; RUN: cat %t | FileCheck %s --check-prefixes=CHECK,ONE
+; RUN: llvm-reduce --abort-on-invalid-reduction --delta-passes=operands-zero --test FileCheck --test-arg --check-prefixes=CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
+; RUN: cat %t | FileCheck %s --check-prefixes=CHECK,ZERO
+; RUN: llvm-reduce --test FileCheck --test-arg --check-prefixes=CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
+; RUN: cat %t | FileCheck %s --check-prefixes=CHECK,ZERO
 
+; CHECK-INTERESTINGNESS: inttoptr
+; CHECK-INTERESTINGNESS: inttoptr
+; CHECK-INTERESTINGNESS: inttoptr
+; CHECK-INTERESTINGNESS: inttoptr
+; CHECK-INTERESTINGNESS: br label
 ; CHECK-INTERESTINGNESS: ret i32
 
-; CHECK-LABEL: define i32 @main() {
-define i32 @main() {
+%t = type { i32, i8 }
+
+; CHECK-LABEL: define i32 @main
+define i32 @main(%t* %a, i32 %a2) {
 
 ; CHECK-LABEL: lb1:
-; CHECK-NEXT: br label %lb2
+; UNDEF: inttoptr i16 0
+; UNDEF: inttoptr i16 1
+; UNDEF: inttoptr i16 2
+; UNDEF: inttoptr i16 undef
+; ONE: inttoptr i16 0
+; ONE: inttoptr i16 1
+; ONE: inttoptr i16 1
+; ONE: inttoptr i16 1
+; ZERO: inttoptr i16 0
+; ZERO: inttoptr i16 0
+; ZERO: inttoptr i16 0
+; ZERO: inttoptr i16 0
+; CHECK: br label %lb2
 lb1:
+  %b = getelementptr %t, %t* %a, i32 1, i32 0
+  %i1 = inttoptr i16 0 to i8*
+  %i2 = inttoptr i16 1 to i8*
+  %i3 = inttoptr i16 2 to i8*
+  %i4 = inttoptr i16 undef to i8*
   br label %lb2
 
 ; CHECK-LABEL: lb2:
-; CHECK-NEXT: ret i32 undef
+; UNDEF: ret i32 undef
+; ONE: ret i32 1
+; ZERO: ret i32 0
 lb2:
-  ret i32 10
+  ret i32 %a2
 }

llvm/tools/llvm-reduce/DeltaManager.cpp

#define DELTA_PASSES                                                           \
   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-zero", reduceOperandsZeroDeltaPass)                     \
+  DELTA_PASS("operands-one", reduceOperandsOneDeltaPass)                       \
+  DELTA_PASS("operands-undef", reduceOperandsUndefDeltaPass)                   \
   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

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

-//===- ReduceOperands.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 to reduce operands to undef.
-//
-//===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEOPERANDS_H
 #define LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEOPERANDS_H
 
 #include "Delta.h"
 
 namespace llvm {
-void reduceOperandsDeltaPass(TestRunner &Test);
+void reduceOperandsUndefDeltaPass(TestRunner &Test);
+void reduceOperandsOneDeltaPass(TestRunner &Test);
+void reduceOperandsZeroDeltaPass(TestRunner &Test);
 } // namespace llvm
 
 #endif

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

-//===- ReduceOperands.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 to reduce operands to undef.
-//
-//===----------------------------------------------------------------------===//
 
 #include "ReduceOperands.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/InstIterator.h"
+#include "llvm/IR/Operator.h"
+#include "llvm/IR/Type.h"
 
 using namespace llvm;
 
-/// Returns if the given operand is undef.
-static bool operandIsUndefValue(Use &Op) {
-  if (auto *C = dyn_cast<Constant>(Op)) {
-    return isa<UndefValue>(C);
-  }
-  return false;
-}
-
-/// Returns if an operand can be reduced to undef.
-/// TODO: make this logic check what types are reducible rather than
-/// check what types that are not reducible.
-static bool canReduceOperand(Use &Op) {
-  auto *Ty = Op->getType();
-  // Can't reduce labels to undef
-  return !Ty->isLabelTy() && !operandIsUndefValue(Op);
-}
-
-/// Sets Operands to undef.
-static void extractOperandsFromModule(Oracle &O, Module &Program) {
-  // Extract Operands from the module.
+static void
+extractOperandsFromModule(Oracle &O, Module &Program,
+                          function_ref<Value *(Use &)> ReduceValue) {
   for (auto &F : Program.functions()) {
     for (auto &I : instructions(&F)) {
       for (auto &Op : I.operands()) {
-        // Filter Operands then set to undef.
-        if (canReduceOperand(Op) && !O.shouldKeep()) {
-          auto *Ty = Op->getType();
-          Op.set(UndefValue::get(Ty));
-        }
+        auto *Reduced = ReduceValue(Op);
+        if (Reduced && !O.shouldKeep())
+          Op.set(Reduced);
       }
     }
   }
 }
 
-/// Counts the amount of operands in the module that can be reduced.
-static int countOperands(Module &Program) {
+static int countOperands(Module &Program,
+                         function_ref<Value *(Use &)> ReduceValue) {
   int Count = 0;
   for (auto &F : Program.functions()) {
     for (auto &I : instructions(&F)) {
       for (auto &Op : I.operands()) {
-        if (canReduceOperand(Op)) {
+        if (ReduceValue(Op))
           Count++;
-        }
-      }
-    }
-  }
   return Count;
 }
 
-void llvm::reduceOperandsDeltaPass(TestRunner &Test) {
-  errs() << "*** Reducing Operands...\n";
-  int Count = countOperands(Test.getProgram());
-  runDeltaPass(Test, Count, extractOperandsFromModule);
+static bool isOne(Use &Op) {
+  auto *C = dyn_cast<Constant>(Op);
+  return C && C->isOneValue();
+}
+
+static bool isZero(Use &Op) {
+  auto *C = dyn_cast<Constant>(Op);
+  return C && C->isNullValue();
+}
+
+void llvm::reduceOperandsUndefDeltaPass(TestRunner &Test) {
+  errs() << "*** Reducing Operands to undef...\n";
+  auto ReduceValue = [](Use &Op) -> Value * {
+    if (isa<GEPOperator>(Op.getUser()))
+      return nullptr;
+    if (Op->getType()->isLabelTy())
+      return nullptr;
+    // Don't replace existing ConstantData Uses.
+    return isa<ConstantData>(*Op) ? nullptr : UndefValue::get(Op->getType());
+  };
+  int Count = countOperands(Test.getProgram(), ReduceValue);
+  runDeltaPass(Test, Count, [ReduceValue](Oracle &O, Module &Program) {
+    extractOperandsFromModule(O, Program, ReduceValue);
+  });
+}
+
+void llvm::reduceOperandsOneDeltaPass(TestRunner &Test) {
+  errs() << "*** Reducing Operands to one...\n";
+  auto ReduceValue = [](Use &Op) -> Value * {
+    // TODO: support floats
+    if (isa<GEPOperator>(Op.getUser()))
+      return nullptr;
+    auto *Ty = dyn_cast<IntegerType>(Op->getType());
+    if (!Ty)
+      return nullptr;
+    // Don't replace existing ones and zeroes.
+    return (isOne(Op) || isZero(Op)) ? nullptr : ConstantInt::get(Ty, 1);
+  };
+  int Count = countOperands(Test.getProgram(), ReduceValue);
+  runDeltaPass(Test, Count, [ReduceValue](Oracle &O, Module &Program) {
+    extractOperandsFromModule(O, Program, ReduceValue);
+  });
+}
+
+void llvm::reduceOperandsZeroDeltaPass(TestRunner &Test) {
+  errs() << "*** Reducing Operands to zero...\n";
+  auto ReduceValue = [](Use &Op) -> Value * {
+    // TODO: be more precise about which GEP operands we can reduce (e.g. array
+    // indexes)
+    if (isa<GEPOperator>(Op.getUser()))
+      return nullptr;
+    if (Op->getType()->isLabelTy())
+      return nullptr;
+    // Don't replace existing zeroes.
+    return isZero(Op) ? nullptr : Constant::getNullValue(Op->getType());
+  };
+  int Count = countOperands(Test.getProgram(), ReduceValue);
+  runDeltaPass(Test, Count, [ReduceValue](Oracle &O, Module &Program) {
+    extractOperandsFromModule(O, Program, ReduceValue);
+  });
 }