Don't leave unused divs/rems sitting around in BypassSlowDivision.

[jlebar]

Summary

This "pass" eagerly creates div and rem instructions even when only one
is needed -- it relies on a later pass (machine DCE?) to clean them up.

This is problematic not just from a cleanliness perspective (this pass
is running during CodeGenPrepare, so should leave the IR in a better
state), but it also creates a problem for instruction selection. If we
always have a div+rem, isel will always select a divrem instruction (if
possible), even when a single div or rem would do.

Specifically, in NVPTX, we want to compute rem from the output of div,
if available. But if a div is not available, we want to leave the rem
alone. This transformation is overeager if div is always available.

Because this code runs as part of CodeGenPrepare, it's nontrivial to
write a test for this change. But this will effectively be tested by
a later patch which adds the aforementioned change to NVPTX isel.

[tra]

llvm/lib/Transforms/Utils/BypassSlowDivision.cpp

251 ↗

(On Diff #76217)

Should it be "erase any unused divs/rems..."?

260 ↗

(On Diff #76217)

What's supposed to happen with operands that are not instructions?
Destruction of unused subgraph sounds like a common operation, perhaps we already have a function to do it?

[jlebar]

Use helper function to delete dead code, and add an IR test.

[jlebar]

llvm/lib/Transforms/Utils/BypassSlowDivision.cpp

251 ↗

(On Diff #76217)

Indeed, thanks!

260 ↗

(On Diff #76217)

What's supposed to happen with operands that are not instructions?

We don't need to delete them if they're constants.

Destruction of unused subgraph sounds like a common operation, perhaps we already have a function to do it?

Aha, found it. Thanks. Also, this fixes a bug -- we weren't trying hard enough to delete trivially-dead things here. mkuper pointed me in the right direction and I now have a test.

[tra]

LGTM

llvm/trunk/lib/Transforms/Utils/BypassSlowDivision.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/BypassSlowDivision.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/Transforms/Utils/Local.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "bypass-slow-division"
 
 namespace {
   struct DivOpInfo {
     bool SignedOp;
if (BI == BypassWidths.end())
       continue;
 
     // Get type for div/rem instruction with bypass bitwidth
     IntegerType *BT = IntegerType::get(I->getContext(), BI->second);
 
     MadeChange |= reuseOrInsertFastDiv(I, BT, UseDivOp, UseSignedOp, DivCache);
   }
 
+  // Above we eagerly create divs and rems, as pairs, so that we can efficiently
+  // create divrem machine instructions.  Now erase any unused divs / rems so we
+  // don't leave extra instructions sitting around.
+  for (auto &KV : DivCache)
+    for (Instruction *Phi : {KV.second.Quotient, KV.second.Remainder})
+      RecursivelyDeleteTriviallyDeadInstructions(Phi);
+
   return MadeChange;
 }

llvm/trunk/test/Transforms/CodeGenPrepare/NVPTX/bypass-slow-div.ll

+; RUN: opt -S -codegenprepare < %s | FileCheck %s
+
+target datalayout = "e-i64:64-v16:16-v32:32-n16:32:64"
+target triple = "nvptx64-nvidia-cuda"
+
+; We only use the div instruction -- the rem should be DCE'ed.
+; CHECK-LABEL: @div_only
+define void @div_only(i64 %a, i64 %b, i64* %retptr) {
+  ; CHECK: udiv i32
+  ; CHECK-NOT: urem
+  ; CHECK: sdiv i64
+  ; CHECK-NOT: rem
+  %d = sdiv i64 %a, %b
+  store i64 %d, i64* %retptr
+  ret void
+}
+
+; We only use the rem instruction -- the div should be DCE'ed.
+; CHECK-LABEL: @rem_only
+define void @rem_only(i64 %a, i64 %b, i64* %retptr) {
+  ; CHECK-NOT: div
+  ; CHECK: urem i32
+  ; CHECK-NOT: div
+  ; CHECK: rem i64
+  ; CHECK-NOT: div
+  %d = srem i64 %a, %b
+  store i64 %d, i64* %retptr
+  ret void
+}