[SeparateConstOffsetFromGEP] garbage-collect intermediate instructions

[jingyue]

Summary

so that we needn't run DCE after this pass.

[meheff]

lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp

632–633

Is this reuse going to cause problems with your garbage collection? When you go to recusively delete UserChain you'll encounter this reused (and now live) instruction and deletion will stop there. However, deeper in the UserChain[] it seems like you could still have dead instructions. The problem would be is that these dead instructions are no longer in the expression tree for UserChain.back()

test/Transforms/SeparateConstOffsetFromGEP/NVPTX/split-gep.ll

1

Should any extra checks be added to verify we're removing dead code?

[jingyue]

removeConstOffset stops reusing instructions in UserChain

This ensures RecursivelyDeleteTriviallyDeadInstructions(UserChain.back()) can
remove all dead instructions in UserChain.

[jingyue]

Added a -gep-reassociate-verify-no-dead-code flag to detect dead code. This flag is supposed to be used in test only.

test/Transforms/SeparateConstOffsetFromGEP/NVPTX/split-gep.ll

1

Good catch! Fixed by cloning BO even if it can be reused.

[meheff]

LGTM with the addition of the new flag to the unit tests.

test/Transforms/SeparateConstOffsetFromGEP/NVPTX/split-gep-and-gvn.ll

2

Did you mean to add your new dead code checking flag here?

test/Transforms/SeparateConstOffsetFromGEP/NVPTX/split-gep.ll

1

And here?

[jingyue]

Done. Thanks for the review!

lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp

 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 #include "llvm/IR/IRBuilder.h"
 
 using namespace llvm;
 
 static cl::opt<bool> DisableSeparateConstOffsetFromGEP(
     "disable-separate-const-offset-from-gep", cl::init(false),
     cl::desc("Do not separate the constant offset from a GEP instruction"),
     cl::Hidden);
+// Setting this flag may emit false positives when the input module already
+// contains dead instructions. Therefore, we set it only in unit tests that are
+// free of dead code.
+static cl::opt<bool>
+    VerifyNoDeadCode("reassociate-geps-verify-no-dead-code", cl::init(false),
+                     cl::desc("Verify this pass produces no dead code"),
+                     cl::Hidden);
 
 namespace {
 
 /// \brief A helper class for separating a constant offset from a GEP index.
 ///
 /// In real programs, a GEP index may be more complicated than a simple addition
 /// of something and a constant integer which can be trivially splitted. For
 /// example, to split ((a << 3) | 5) + b, we need to search deeper for the
 /// constant offset, so that we can separate the index to (a << 3) + b and 5.
 ///
 /// Therefore, this class looks into the expression that computes a given GEP
 /// index, and tries to find a constant integer that can be hoisted to the
 /// outermost level of the expression as an addition. Not every constant in an
 /// expression can jump out. e.g., we cannot transform (b * (a + 5)) to (b * a +
 /// 5); nor can we transform (3 * (a + 5)) to (3 * a + 5), however in this case,
 /// -instcombine probably already optimized (3 * (a + 5)) to (3 * a + 15).
 class ConstantOffsetExtractor {
  public:
   /// Extracts a constant offset from the given GEP index. It returns the
   /// new index representing the remainder (equal to the original index minus
   /// the constant offset), or nullptr if we cannot extract a constant offset.
-  /// \p Idx    The given GEP index
-  /// \p GEP    The given GEP
-   static Value *Extract(Value *Idx, GetElementPtrInst *GEP);
+  /// \p Idx The given GEP index
+  /// \p GEP The given GEP
+  /// \p UserChainTail Outputs the tail of UserChain so that we can
+  ///                  garbage-collect unused instructions in UserChain.
+   static Value *Extract(Value *Idx, GetElementPtrInst *GEP,
+                         User *&UserChainTail);
   /// Looks for a constant offset from the given GEP index without extracting
   /// it. It returns the numeric value of the extracted constant offset (0 if
   /// failed). The meaning of the arguments are the same as Extract.
    static int64_t Find(Value *Idx, GetElementPtrInst *GEP);
 
  private:
    ConstantOffsetExtractor(Instruction *InsertionPt) : IP(InsertionPt) {}
   /// Searches the expression that computes V for a non-zero constant C s.t.
private:
   ///
   /// This canonicalization is very likely already done in clang and
   /// instcombine. Therefore, the program will probably remain the same.
   ///
   /// Returns true if the module changes.
   ///
   /// Verified in @i32_add in split-gep.ll
   bool canonicalizeArrayIndicesToPointerSize(GetElementPtrInst *GEP);
+  /// Verify F is free of dead code.
+  void verifyNoDeadCode(Function &F);
 
   const TargetMachine *TM;
   /// Whether to lower a GEP with multiple indices into arithmetic operations or
   /// multiple GEPs with a single index.
   bool LowerGEP;
 };
 }  // anonymous namespace
 

 
 Value *ConstantOffsetExtractor::removeConstOffset(unsigned ChainIndex) {
   if (ChainIndex == 0) {
     assert(isa<ConstantInt>(UserChain[ChainIndex]));
     return ConstantInt::getNullValue(UserChain[ChainIndex]->getType());
   }
 
   BinaryOperator *BO = cast<BinaryOperator>(UserChain[ChainIndex]);
+  assert(BO->getNumUses() <= 1 &&
+         "distributeExtsAndCloneChain clones each BinaryOperator in "
+         "UserChain, so no one should be used more than "
+         "once");
+
   unsigned OpNo = (BO->getOperand(0) == UserChain[ChainIndex - 1] ? 0 : 1);
   assert(BO->getOperand(OpNo) == UserChain[ChainIndex - 1]);
   Value *NextInChain = removeConstOffset(ChainIndex - 1);
   Value *TheOther = BO->getOperand(1 - OpNo);
 
   // If NextInChain is 0 and not the LHS of a sub, we can simplify the
   // sub-expression to be just TheOther.
   if (ConstantInt *CI = dyn_cast<ConstantInt>(NextInChain)) {
     if (CI->isZero() && !(BO->getOpcode() == Instruction::Sub && OpNo == 0))
       return TheOther;
   }
 
+  BinaryOperator::BinaryOps NewOp = BO->getOpcode();
   if (BO->getOpcode() == Instruction::Or) {
     // Rebuild "or" as "add", because "or" may be invalid for the new
     // epxression.
     //
     // For instance, given
     //   a | (b + 5) where a and b + 5 have no common bits,
     // we can extract 5 as the constant offset.
     //
     // However, reusing the "or" in the new index would give us
     //   (a | b) + 5
     // which does not equal a | (b + 5).
     //
     // Replacing the "or" with "add" is fine, because
     //   a | (b + 5) = a + (b + 5) = (a + b) + 5
-    if (OpNo == 0) {
-      return BinaryOperator::CreateAdd(NextInChain, TheOther, BO->getName(),
-                                       IP);
-    } else {
-      return BinaryOperator::CreateAdd(TheOther, NextInChain, BO->getName(),
-                                       IP);
-    }
+    NewOp = Instruction::Add;
+  }
+
+  BinaryOperator *NewBO;
+    NewBO = BinaryOperator::Create(NewOp, NextInChain, TheOther, "", IP);
+    NewBO = BinaryOperator::Create(NewOp, TheOther, NextInChain, "", IP);
   }
-
-  // We can reuse BO in this case, because the new expression shares the same
-  // instruction type and BO is used at most once.
-  assert(BO->getNumUses() <= 1 &&
-         "distributeExtsAndCloneChain clones each BinaryOperator in "
-         "UserChain, so no one should be used more than "
-         "once");
-  BO->setOperand(OpNo, NextInChain);
-  BO->setHasNoSignedWrap(false);
-  BO->setHasNoUnsignedWrap(false);
-  // Make sure it appears after all instructions we've inserted so far.
-  BO->moveBefore(IP);
-  return BO;
+  NewBO->takeName(BO);
+  return NewBO;
 }
 
-Value *ConstantOffsetExtractor::Extract(Value *Idx, GetElementPtrInst *GEP) {
+Value *ConstantOffsetExtractor::Extract(Value *Idx, GetElementPtrInst *GEP,
+                                        User *&UserChainTail) {
   ConstantOffsetExtractor Extractor(GEP);
   // Find a non-zero constant offset first.
   APInt ConstantOffset =
       Extractor.find(Idx, /* SignExtended */ false, /* ZeroExtended */ false,
                      GEP->isInBounds());
-  if (ConstantOffset == 0)
+  if (ConstantOffset == 0) {
+    UserChainTail = nullptr;
     return nullptr;
+  }
   // Separates the constant offset from the GEP index.
-  return Extractor.rebuildWithoutConstOffset();
+  Value *IdxWithoutConstOffset = Extractor.rebuildWithoutConstOffset();
+  UserChainTail = Extractor.UserChain.back();
+  return IdxWithoutConstOffset;
 }
 
 int64_t ConstantOffsetExtractor::Find(Value *Idx, GetElementPtrInst *GEP) {
   // If Idx is an index of an inbound GEP, Idx is guaranteed to be non-negative.
   return ConstantOffsetExtractor(GEP)
       .find(Idx, /* SignExtended */ false, /* ZeroExtended */ false,
             GEP->isInBounds())
       .getSExtValue();
bool SeparateConstOffsetFromGEP::splitGEP(GetElementPtrInst *GEP) {
   // one. If LowerGEP is enabled, a structure index is accumulated in the
   // constant offset. LowerToSingleIndexGEPs or lowerToArithmetics will later
   // handle the constant offset and won't need a new structure index.
   gep_type_iterator GTI = gep_type_begin(*GEP);
   for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {
     if (isa<SequentialType>(*GTI)) {
       // Splits this GEP index into a variadic part and a constant offset, and
       // uses the variadic part as the new index.
-      Value *NewIdx = ConstantOffsetExtractor::Extract(GEP->getOperand(I), GEP);
+      Value *OldIdx = GEP->getOperand(I);
+      User *UserChainTail;
+      Value *NewIdx =
+          ConstantOffsetExtractor::Extract(OldIdx, GEP, UserChainTail);
       if (NewIdx != nullptr) {
+        // Switches to the index with the constant offset removed.
         GEP->setOperand(I, NewIdx);
+        // After switching to the new index, we can garbage-collect UserChain
+        // and the old index if they are not used.
+        RecursivelyDeleteTriviallyDeadInstructions(UserChainTail);
+        RecursivelyDeleteTriviallyDeadInstructions(OldIdx);
       }
     }
   }
 
   // Clear the inbounds attribute because the new index may be off-bound.
   // e.g.,
   //
   // b = add i64 a, 5
for (Function::iterator B = F.begin(), BE = F.end(); B != BE; ++B) {
     for (BasicBlock::iterator I = B->begin(), IE = B->end(); I != IE; ) {
       if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I++)) {
         Changed |= splitGEP(GEP);
       }
       // No need to split GEP ConstantExprs because all its indices are constant
       // already.
     }
   }
+
+  if (VerifyNoDeadCode)
+    verifyNoDeadCode(F);
+
   return Changed;
 }
+
+void SeparateConstOffsetFromGEP::verifyNoDeadCode(Function &F) {
+  for (auto &B : F) {
+    for (auto &I : B) {
+      if (isInstructionTriviallyDead(&I)) {
+        std::string ErrMessage;
+        raw_string_ostream RSO(ErrMessage);
+        RSO << "Dead instruction detected!\n" << I << "\n";
+        llvm_unreachable(RSO.str().c_str());
+      }
+    }
+  }
+}

test/Transforms/SeparateConstOffsetFromGEP/NVPTX/split-gep-and-gvn.ll

 ; RUN: llc < %s -march=nvptx64 -mcpu=sm_20 | FileCheck %s --check-prefix=PTX
-; RUN: opt < %s -S -separate-const-offset-from-gep -gvn -dce | FileCheck %s --check-prefix=IR
+; RUN: opt < %s -S -separate-const-offset-from-gep -reassociate-geps-verify-no-dead-code -gvn | FileCheck %s --check-prefix=IR
 
 ; Verifies the SeparateConstOffsetFromGEP pass.
 ; The following code computes
 ; *output = array[x][y] + array[x][y+1] + array[x+1][y] + array[x+1][y+1]
 ;
 ; We expect SeparateConstOffsetFromGEP to transform it to
 ;
 ; float *base = &a[x][y];

test/Transforms/SeparateConstOffsetFromGEP/NVPTX/split-gep.ll

-; RUN: opt < %s -separate-const-offset-from-gep -dce -S | FileCheck %s
+; RUN: opt < %s -separate-const-offset-from-gep -reassociate-geps-verify-no-dead-code -S | FileCheck %s
 
 ; Several unit tests for -separate-const-offset-from-gep. The transformation
 ; heavily relies on TargetTransformInfo, so we put these tests under
 ; target-specific folders.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 ; target triple is necessary; otherwise TargetTransformInfo rejects any
 ; addressing mode.