[SLSR] garbage-collect unused instructions

[jingyue]

Summary

After we rewrite a candidate, the instructions used by the old form may
become unused. This patch cleans up these unused instructions so that we
needn't run DCE after SLSR.

[meheff]

LGTM

llvm/trunk/lib/Transforms/Scalar/StraightLineStrengthReduce.cpp

 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/Local.h"
 
 using namespace llvm;
 using namespace PatternMatch;
 
 namespace {
 
 class StraightLineStrengthReduce : public FunctionPass {
 public:
void StraightLineStrengthReduce::rewriteCandidateWithBasis(
 
   IRBuilder<> Builder(C.Ins);
   bool BumpWithUglyGEP;
   Value *Bump = emitBump(Basis, C, Builder, DL, BumpWithUglyGEP);
   Value *Reduced = nullptr; // equivalent to but weaker than C.Ins
   switch (C.CandidateKind) {
   case Candidate::Add:
   case Candidate::Mul:
+    // C = Basis + Bump
     if (BinaryOperator::isNeg(Bump)) {
+      // If Bump is a neg instruction, emit C = Basis - (-Bump).
       Reduced =
           Builder.CreateSub(Basis.Ins, BinaryOperator::getNegArgument(Bump));
+      // We only use the negative argument of Bump, and Bump itself may be
+      // trivially dead.
+      RecursivelyDeleteTriviallyDeadInstructions(Bump);
     } else {
       Reduced = Builder.CreateAdd(Basis.Ins, Bump);
     }
     break;
   case Candidate::GEP:
     {
       Type *IntPtrTy = DL->getIntPtrType(C.Ins->getType());
       bool InBounds = cast<GetElementPtrInst>(C.Ins)->isInBounds();
case Candidate::GEP:
       }
     }
     break;
   default:
     llvm_unreachable("C.CandidateKind is invalid");
   };
   Reduced->takeName(C.Ins);
   C.Ins->replaceAllUsesWith(Reduced);
-  C.Ins->dropAllReferences();
   // Unlink C.Ins so that we can skip other candidates also corresponding to
   // C.Ins. The actual deletion is postponed to the end of runOnFunction.
   C.Ins->removeFromParent();
   UnlinkedInstructions.push_back(C.Ins);
 }
 
 bool StraightLineStrengthReduce::runOnFunction(Function &F) {
   if (skipOptnoneFunction(F))
while (!Candidates.empty()) {
     const Candidate &C = Candidates.back();
     if (C.Basis != nullptr) {
       rewriteCandidateWithBasis(C, *C.Basis);
     }
     Candidates.pop_back();
   }
 
   // Delete all unlink instructions.
-  for (auto I : UnlinkedInstructions) {
-    delete I;
+  for (auto *UnlinkedInst : UnlinkedInstructions) {
+    for (unsigned I = 0, E = UnlinkedInst->getNumOperands(); I != E; ++I) {
+      Value *Op = UnlinkedInst->getOperand(I);
+      UnlinkedInst->setOperand(I, nullptr);
+      RecursivelyDeleteTriviallyDeadInstructions(Op);
+    }
+    delete UnlinkedInst;
   }
   bool Ret = !UnlinkedInstructions.empty();
   UnlinkedInstructions.clear();
   return Ret;
 }

llvm/trunk/test/Transforms/StraightLineStrengthReduce/X86/no-slsr.ll

-; RUN: opt < %s -slsr -gvn -dce -S | FileCheck %s
+; RUN: opt < %s -slsr -gvn -S | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Do not perform SLSR on &input[s] and &input[s * 2] which fit into addressing
 ; modes of X86.
 define i32 @no_slsr_gep(i32* %input, i64 %s) {
 ; CHECK-LABEL: @no_slsr_gep(

llvm/trunk/test/Transforms/StraightLineStrengthReduce/slsr-add.ll

-; RUN: opt < %s -slsr -gvn -dce -S | FileCheck %s
+; RUN: opt < %s -slsr -gvn -S | FileCheck %s
 
 target datalayout = "e-i64:64-v16:16-v32:32-n16:32:64"
 
 define void @shl(i32 %b, i32 %s) {
 ; CHECK-LABEL: @shl(
   %1 = add i32 %b, %s
 ; [[BASIS:%[a-zA-Z0-9]+]] = add i32 %b, %s
   call void @foo(i32 %1)

llvm/trunk/test/Transforms/StraightLineStrengthReduce/slsr-gep.ll

-; RUN: opt < %s -slsr -gvn -dce -S | FileCheck %s
+; RUN: opt < %s -slsr -gvn -S | FileCheck %s
 
 target datalayout = "e-i64:64-v16:16-v32:32-n16:32:64"
 
 ; foo(input[0]);
 ; foo(input[s]);
 ; foo(input[s * 2]);
 ;   =>
 ; p0 = &input[0];

llvm/trunk/test/Transforms/StraightLineStrengthReduce/slsr-mul.ll

-; RUN: opt < %s -slsr -gvn -dce -S | FileCheck %s
+; RUN: opt < %s -slsr -gvn -S | FileCheck %s
 
 target datalayout = "e-i64:64-v16:16-v32:32-n16:32:64"
 
 define void @slsr1(i32 %b, i32 %s) {
 ; CHECK-LABEL: @slsr1(
   ; foo(b * s);
   %mul0 = mul i32 %b, %s
 ; CHECK: mul i32