llvm-reduce: Add opcode reduction pass

Try some dumb strength reductions to "simpler" opcodes.
Make some opcode substitutions I typically try to get smaller
MIR out of codegen. This is a bit target specific and I have a
lot of increasingly target specific modifications I try
during manual reduction.

4 files changed, 133 insertions, 0 deletions

diff --git a/llvm/tools/llvm-reduce/CMakeLists.txt b/llvm/tools/llvm-reduce/CMakeLists.txt
index 0dafd88..6f70806 100644
--- a/llvm/tools/llvm-reduce/CMakeLists.txt
+++ b/llvm/tools/llvm-reduce/CMakeLists.txt
@@ -39,6 +39,7 @@ add_llvm_tool(llvm-reduce
   deltas/ReduceMetadata.cpp
   deltas/ReduceModuleData.cpp
   deltas/ReduceOperandBundles.cpp
+  deltas/ReduceOpcodes.cpp
   deltas/ReduceSpecialGlobals.cpp
   deltas/ReduceOperands.cpp
   deltas/ReduceOperandsSkip.cpp
diff --git a/llvm/tools/llvm-reduce/DeltaManager.cpp b/llvm/tools/llvm-reduce/DeltaManager.cpp
index 2bd9b28..e544d27 100644
--- a/llvm/tools/llvm-reduce/DeltaManager.cpp
+++ b/llvm/tools/llvm-reduce/DeltaManager.cpp
@@ -32,6 +32,7 @@
 #include "deltas/ReduceInstructionsMIR.h"
 #include "deltas/ReduceMetadata.h"
 #include "deltas/ReduceModuleData.h"
+#include "deltas/ReduceOpcodes.h"
 #include "deltas/ReduceOperandBundles.h"
 #include "deltas/ReduceOperands.h"
 #include "deltas/ReduceOperandsSkip.h"
@@ -89,6 +90,7 @@ static cl::list<std::string>
     DELTA_PASS("simplify-cfg", reduceUsingSimplifyCFGDeltaPass)                \
     DELTA_PASS("attributes", reduceAttributesDeltaPass)                        \
     DELTA_PASS("module-data", reduceModuleDataDeltaPass)                       \
+    DELTA_PASS("opcodes", reduceOpcodesDeltaPass)                              \
   } while (false)
 
 #define DELTA_PASSES_MIR                                                       \
diff --git a/llvm/tools/llvm-reduce/deltas/ReduceOpcodes.cpp b/llvm/tools/llvm-reduce/deltas/ReduceOpcodes.cpp
new file mode 100644
index 0000000..a834034
--- /dev/null
+++ b/llvm/tools/llvm-reduce/deltas/ReduceOpcodes.cpp
@@ -0,0 +1,112 @@
+//===- ReduceOpcodes.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
+//
+//===----------------------------------------------------------------------===//
+//
+// Try to replace instructions that are likely to codegen to simpler or smaller
+// sequences. This is a fuzzy and target specific concept.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ReduceOpcodes.h"
+#include "Delta.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/IntrinsicsAMDGPU.h"
+
+static Value *replaceIntrinsic(Module &M, IntrinsicInst *II,
+                               Intrinsic::ID NewIID,
+                               ArrayRef<Type *> Tys = None) {
+  Function *NewFunc = Intrinsic::getDeclaration(&M, NewIID, Tys);
+  II->setCalledFunction(NewFunc);
+  return II;
+}
+
+static Value *reduceInstruction(Module &M, Instruction &I) {
+  IRBuilder<> B(&I);
+  switch (I.getOpcode()) {
+  case Instruction::FDiv:
+  case Instruction::FRem:
+    // Divisions tends to codegen into a long sequence or a library call.
+    return B.CreateFMul(I.getOperand(0), I.getOperand(1));
+  case Instruction::UDiv:
+  case Instruction::SDiv:
+  case Instruction::URem:
+  case Instruction::SRem:
+    // Divisions tends to codegen into a long sequence or a library call.
+    return B.CreateMul(I.getOperand(0), I.getOperand(1));
+  case Instruction::Add:
+  case Instruction::Sub: {
+    // Add/sub are more likely codegen to instructions with carry out side
+    // effects.
+    return B.CreateOr(I.getOperand(0), I.getOperand(1));
+  }
+  case Instruction::Call: {
+    IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I);
+    if (!II)
+      return nullptr;
+
+    switch (II->getIntrinsicID()) {
+    case Intrinsic::sqrt:
+      return B.CreateFMul(II->getArgOperand(0),
+                          ConstantFP::get(I.getType(), 2.0));
+    case Intrinsic::minnum:
+    case Intrinsic::maxnum:
+    case Intrinsic::minimum:
+    case Intrinsic::maximum:
+    case Intrinsic::amdgcn_fmul_legacy:
+      return B.CreateFMul(II->getArgOperand(0), II->getArgOperand(1));
+    case Intrinsic::amdgcn_workitem_id_y:
+    case Intrinsic::amdgcn_workitem_id_z:
+      return replaceIntrinsic(M, II, Intrinsic::amdgcn_workitem_id_x);
+    case Intrinsic::amdgcn_workgroup_id_y:
+    case Intrinsic::amdgcn_workgroup_id_z:
+      return replaceIntrinsic(M, II, Intrinsic::amdgcn_workgroup_id_x);
+    case Intrinsic::amdgcn_div_fixup:
+    case Intrinsic::amdgcn_fma_legacy:
+      return replaceIntrinsic(M, II, Intrinsic::fma, {II->getType()});
+    default:
+      return nullptr;
+    }
+
+    return nullptr;
+  }
+  default:
+    return nullptr;
+  }
+
+  return nullptr;
+}
+
+static void replaceOpcodesInModule(Oracle &O, Module &Mod) {
+  for (Function &F : Mod) {
+    for (BasicBlock &BB : F)
+      for (Instruction &I : make_early_inc_range(BB)) {
+        if (O.shouldKeep())
+          continue;
+
+        Instruction *Replacement =
+            dyn_cast_or_null<Instruction>(reduceInstruction(Mod, I));
+        if (Replacement && Replacement != &I) {
+          if (auto *Op = dyn_cast<FPMathOperator>(Replacement))
+            Replacement->copyFastMathFlags(&I);
+
+          Replacement->copyIRFlags(&I);
+          Replacement->copyMetadata(I);
+          Replacement->takeName(&I);
+          I.replaceAllUsesWith(Replacement);
+          I.eraseFromParent();
+        }
+      }
+  }
+}
+
+void llvm::reduceOpcodesDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing Opcodes...\n";
+  runDeltaPass(Test, replaceOpcodesInModule);
+}
diff --git a/llvm/tools/llvm-reduce/deltas/ReduceOpcodes.h b/llvm/tools/llvm-reduce/deltas/ReduceOpcodes.h
new file mode 100644
index 0000000..79edc7f
--- /dev/null
+++ b/llvm/tools/llvm-reduce/deltas/ReduceOpcodes.h
@@ -0,0 +1,18 @@
+//===- ReduceOpcodes.h - Specialized Delta Pass -----------------*- C++ -*-===//
+//
+// 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_REDUCEOPCODES_H
+#define LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEOPCODES_H
+
+#include "TestRunner.h"
+
+namespace llvm {
+void reduceOpcodesDeltaPass(TestRunner &Test);
+} // namespace llvm
+
+#endif