llvm-reduce: Add opcode reduction pass

[arsenm]

Summary

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.

[arsenm]

Add a few more cases

[arsenm]

Handle a few easy cases where it's easy to replace a target specific intrinsic with a structurally identical generic intrinsic

[aeubanks]

nice!

llvm/tools/llvm-reduce/DeltaManager.cpp

91

looks like this patch is on top of something not in LLVM

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

8

extra line

[arsenm]

573a5de7551cd33d00e67e4653d8c4e9e886b68b

llvm/test/tools/llvm-reduce/reduce-opcodes.ll

+; RUN: llvm-reduce --abort-on-invalid-reduction --delta-passes=opcodes --test FileCheck --test-arg --check-prefixes=CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
+; RUN: FileCheck -check-prefix=RESULT %s < %t
+
+; CHECK-INTERESTINGNESS: @fdiv_fast(
+; RESULT: %op = fmul fast float %a, %b, !dbg !7, !fpmath !13
+define float @fdiv_fast(float %a, float %b) {
+  %op = fdiv fast float %a, %b, !dbg !7, !fpmath !13
+  ret float %op
+}
+
+; CHECK-INTERESTINGNESS: @frem_nnan(
+; RESULT: %op = fmul nnan float %a, %b, !dbg !7, !fpmath !13
+define float @frem_nnan(float %a, float %b) {
+  %op = frem nnan float %a, %b, !dbg !7, !fpmath !13
+  ret float %op
+}
+
+; CHECK-INTERESTINGNESS: @udiv(
+; RESULT: %op = mul i32 %a, %b, !dbg !7
+define i32 @udiv(i32 %a, i32 %b) {
+  %op = udiv i32 %a, %b, !dbg !7
+  ret i32 %op
+}
+
+; CHECK-INTERESTINGNESS: @sdiv(
+; RESULT: %op = mul i32 %a, %b{{$}}
+define i32 @sdiv(i32 %a, i32 %b) {
+  %op = sdiv i32 %a, %b
+  ret i32 %op
+}
+
+; CHECK-INTERESTINGNESS: @sdiv_exact(
+; RESULT: %op = mul i32 %a, %b, !dbg !7
+define i32 @sdiv_exact(i32 %a, i32 %b) {
+  %op = sdiv exact i32 %a, %b, !dbg !7
+  ret i32 %op
+}
+
+; CHECK-INTERESTINGNESS: @urem(
+; RESULT: %op = mul i32 %a, %b, !dbg !7
+define i32 @urem(i32 %a, i32 %b) {
+  %op = urem i32 %a, %b, !dbg !7
+  ret i32 %op
+}
+
+; CHECK-INTERESTINGNESS: @srem(
+; RESULT: %op = mul i32 %a, %b, !dbg !7
+define i32 @srem(i32 %a, i32 %b) {
+  %op = srem i32 %a, %b, !dbg !7
+  ret i32 %op
+}
+
+; Make sure there's no crash if the IRBuilder decided to constant fold something
+; CHECK-INTERESTINGNESS: @add_constant_fold(
+; RESULT: %op = add i32 0, 0, !dbg !7
+define i32 @add_constant_fold() {
+  %op = add i32 0, 0, !dbg !7
+  ret i32 %op
+}
+
+; CHECK-INTERESTINGNESS: @add(
+; RESULT: %op = or i32 %a, %b, !dbg !7
+define i32 @add(i32 %a, i32 %b) {
+  %op = add i32 %a, %b, !dbg !7
+  ret i32 %op
+}
+
+; CHECK-INTERESTINGNESS: @add_nuw(
+; RESULT: %op = or i32 %a, %b, !dbg !7
+define i32 @add_nuw(i32 %a, i32 %b) {
+  %op = add nuw i32 %a, %b, !dbg !7
+  ret i32 %op
+}
+
+; CHECK-INTERESTINGNESS: @add_nsw(
+; RESULT: %op = or i32 %a, %b, !dbg !7
+define i32 @add_nsw(i32 %a, i32 %b) {
+  %op = add nsw i32 %a, %b, !dbg !7
+  ret i32 %op
+}
+
+; CHECK-INTERESTINGNESS: @sub_nuw_nsw(
+; RESULT: %op = or i32 %a, %b, !dbg !7
+define i32 @sub_nuw_nsw(i32 %a, i32 %b) {
+  %op = sub nuw nsw i32 %a, %b, !dbg !7
+  ret i32 %op
+}
+
+; CHECK-INTERESTINGNESS: @workitem_id_y(
+; RESULT: %id = call i32 @llvm.amdgcn.workitem.id.x(), !dbg !7
+define i32 @workitem_id_y() {
+  %id = call i32 @llvm.amdgcn.workitem.id.y(), !dbg !7
+  ret i32 %id
+}
+
+; CHECK-INTERESTINGNESS: @workitem_id_z(
+; RESULT: %id = call i32 @llvm.amdgcn.workitem.id.x(), !dbg !7
+define i32 @workitem_id_z() {
+  %id = call i32 @llvm.amdgcn.workitem.id.z(), !dbg !7
+  ret i32 %id
+}
+
+; CHECK-INTERESTINGNESS: @workgroup_id_y(
+; RESULT: %id = call i32 @llvm.amdgcn.workgroup.id.x(), !dbg !7
+define i32 @workgroup_id_y() {
+  %id = call i32 @llvm.amdgcn.workgroup.id.y(), !dbg !7
+  ret i32 %id
+}
+
+; CHECK-INTERESTINGNESS: @workgroup_id_z(
+; RESULT: %id = call i32 @llvm.amdgcn.workgroup.id.x(), !dbg !7
+define i32 @workgroup_id_z() {
+  %id = call i32 @llvm.amdgcn.workgroup.id.z(), !dbg !7
+  ret i32 %id
+}
+
+; CHECK-LABEL: @minnum_nsz(
+; RESULT: %op = fmul nsz float %a, %b, !dbg !7
+define float @minnum_nsz(float %a, float %b) {
+  %op = call nsz float @llvm.minnum.f32(float %a, float %b), !dbg !7
+  ret float %op
+}
+
+; CHECK-LABEL: @maxnum_nsz(
+; RESULT: %op = fmul nsz float %a, %b, !dbg !7
+define float @maxnum_nsz(float %a, float %b) {
+  %op = call nsz float @llvm.maxnum.f32(float %a, float %b), !dbg !7
+  ret float %op
+}
+
+; CHECK-LABEL: @minimum(
+; RESULT: %op = fmul nsz float %a, %b, !dbg !7
+define float @minimum_nsz(float %a, float %b) {
+  %op = call nsz float @llvm.minimum.f32(float %a, float %b), !dbg !7
+  ret float %op
+}
+
+; CHECK-LABEL: @maximum(
+; RESULT: %op = fmul nsz float %a, %b, !dbg !7
+define float @maximum_nsz(float %a, float %b) {
+  %op = call nsz float @llvm.maximum.f32(float %a, float %b), !dbg !7
+  ret float %op
+}
+
+; CHECK-LABEL: @sqrt_ninf(
+; RESULT: %op = fmul ninf float %a, 2.000000e+00, !dbg !7
+define float @sqrt_ninf(float %a, float %b) {
+  %op = call ninf float @llvm.sqrt.f32(float %a), !dbg !7
+  ret float %op
+}
+
+; CHECK-LABEL: @div_fixup(
+; RESULT: %op = call float @llvm.fma.f32(float %a, float %b, float %c)
+define float @div_fixup(float %a, float %b, float %c) {
+  %op = call float @llvm.amdgcn.div.fixup.f32(float %a, float %b, float %c)
+  ret float %op
+}
+
+; CHECK-LABEL: @fma_legacy(
+; RESULT: %op = call float @llvm.fma.f32(float %a, float %b, float %c)
+define float @fma_legacy(float %a, float %b, float %c) {
+  %op = call float @llvm.amdgcn.fma.legacy(float %a, float %b, float %c)
+  ret float %op
+}
+
+; CHECK-LABEL: @fmul_legacy(
+; RESULT: %op = fmul float %a, %b
+define float @fmul_legacy(float %a, float %b) {
+  %op = call float @llvm.amdgcn.fmul.legacy(float %a, float %b)
+  ret float %op
+}
+
+declare i32 @llvm.amdgcn.workitem.id.y()
+declare i32 @llvm.amdgcn.workitem.id.z()
+declare i32 @llvm.amdgcn.workgroup.id.y()
+declare i32 @llvm.amdgcn.workgroup.id.z()
+declare float @llvm.amdgcn.div.fixup.f32(float, float, float)
+declare float @llvm.amdgcn.fma.legacy(float, float, float)
+declare float @llvm.amdgcn.fmul.legacy(float, float)
+
+declare float @llvm.sqrt.f32(float)
+declare float @llvm.maxnum.f32(float, float)
+declare float @llvm.minnum.f32(float, float)
+declare float @llvm.maximum.f32(float, float)
+declare float @llvm.minimum.f32(float, float)
+
+!llvm.dbg.cu = !{!0}
+!opencl.ocl.version = !{!3, !3}
+!llvm.module.flags = !{!4, !5}
+!llvm.ident = !{!6}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
+!1 = !DIFile(filename: "arst.c", directory: "/some/random/directory")
+!2 = !{}
+!3 = !{i32 2, i32 0}
+!4 = !{i32 2, !"Dwarf Version", i32 2}
+!5 = !{i32 2, !"Debug Info Version", i32 3}
+!6 = !{!""}
+!7 = !DILocation(line: 2, column: 6, scope: !8)
+!8 = distinct !DISubprogram(name: "arst", scope: !1, file: !1, line: 1, type: !9, scopeLine: 1, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+!9 = !DISubroutineType(types: !10)
+!10 = !{null, !11}
+!11 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !12, size: 64)
+!12 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!13 = !{float 2.500000e+00}

llvm/tools/llvm-reduce/CMakeLists.txt

add_llvm_tool(llvm-reduce
   deltas/ReduceGlobalObjects.cpp
   deltas/ReduceGlobalValues.cpp
   deltas/ReduceGlobalVarInitializers.cpp
   deltas/ReduceGlobalVars.cpp
   deltas/ReduceInstructions.cpp
   deltas/ReduceMetadata.cpp
   deltas/ReduceModuleData.cpp
   deltas/ReduceOperandBundles.cpp
+  deltas/ReduceOpcodes.cpp
   deltas/ReduceSpecialGlobals.cpp
   deltas/ReduceOperands.cpp
   deltas/ReduceOperandsSkip.cpp
   deltas/ReduceOperandsToArgs.cpp
   deltas/ReduceInstructionsMIR.cpp
   deltas/ReduceInstructionFlagsMIR.cpp
   deltas/ReduceIRReferences.cpp
   deltas/ReduceVirtualRegisters.cpp

llvm/tools/llvm-reduce/DeltaManager.cpp

 #include "deltas/ReduceGlobalVarInitializers.h"
 #include "deltas/ReduceGlobalVars.h"
 #include "deltas/ReduceIRReferences.h"
 #include "deltas/ReduceInstructionFlagsMIR.h"
 #include "deltas/ReduceInstructions.h"
 #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"
 #include "deltas/ReduceOperandsToArgs.h"
 #include "deltas/ReduceRegisterDefs.h"
 #include "deltas/ReduceRegisterMasks.h"
 #include "deltas/ReduceRegisterUses.h"
 #include "deltas/ReduceSpecialGlobals.h"
do {                                                                         \
     DELTA_PASS("simplify-instructions", simplifyInstructionsDeltaPass)         \
     DELTA_PASS("ir-passes", runIRPassesDeltaPass)                              \
     DELTA_PASS("operands-zero", reduceOperandsZeroDeltaPass)                   \
     DELTA_PASS("operands-one", reduceOperandsOneDeltaPass)                     \
     DELTA_PASS("operands-nan", reduceOperandsNaNDeltaPass)                     \
     DELTA_PASS("operands-to-args", reduceOperandsToArgsDeltaPass)              \
     DELTA_PASS("operands-skip", reduceOperandsSkipDeltaPass)                   \
     DELTA_PASS("operand-bundles", reduceOperandBundesDeltaPass)                \
-    DELTA_PASS("simplify-cfg", reduceUsingSimplifyCFGDeltaPass)       \
-    DELTA_PASS("infinite-loops", reduceInfiniteLoopsDeltaPass)       \
+    DELTA_PASS("simplify-cfg", reduceUsingSimplifyCFGDeltaPass)                \
+    DELTA_PASS("infinite-loops", reduceInfiniteLoopsDeltaPass)                 \
     DELTA_PASS("attributes", reduceAttributesDeltaPass)                        \
     DELTA_PASS("module-data", reduceModuleDataDeltaPass)                       \
+    DELTA_PASS("opcodes", reduceOpcodesDeltaPass)                              \
   } while (false)
 
 #define DELTA_PASSES_MIR                                                       \
   do {                                                                         \
     DELTA_PASS("instructions", reduceInstructionsMIRDeltaPass)                 \
     DELTA_PASS("ir-instruction-references",                                    \
                reduceIRInstructionReferencesDeltaPass)                         \
     DELTA_PASS("ir-block-references", reduceIRBlockReferencesDeltaPass)        \

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

+//===- 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

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

+//===- 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);
+}