Misc cleanups and simplifications for NewGVN. Mostly use a bit more idiomatic C++ where we can, so we can combine some things later.

[davide]

include/llvm/Transforms/Scalar/GVNExpression.h

232–233 ↗

(On Diff #82482)

hmm, this is a quite peculiar implementation of operator preincrement/postincrement as they actually don't increment anything.

438–453 ↗

(On Diff #82482)

op_inserter and int_op_inserter are nearly identical. Is there any chance you can templatize to reduce the duplication?

lib/Transforms/Scalar/NewGVN.cpp

418–425 ↗

(On Diff #82482)

Very nice use of std::transform.

1475–1482 ↗

(On Diff #82482)

This is a very minor nit, but (almost) everywhere else in llvm we use BB for a BasicBlock variable. Here we had B to distinguish between it and BB, but I think it makes sense to use BB instead.

1753–1770 ↗

(On Diff #82482)

Thanks for expanding the comment. You can consider committing this separately to reduce the diff (as it's fairly independent change).

[davide]

Side note, there are some spurious whitespace changes so you may want to clang-format the patch while you're there.

[• dberlin]

include/llvm/Transforms/Scalar/GVNExpression.h

232–233 ↗

(On Diff #82482)

This is standard for inserters.
See https://gcc.gnu.org/onlinedocs/gcc-4.6.2/libstdc++/api/a01052_source.html#l00408
and
http://en.cppreference.com/w/cpp/iterator/back_insert_iterator
" Incrementing the std::back_insert_iterator is a no-op."

438–453 ↗

(On Diff #82482)

yeah, i'll try to fix this.

lib/Transforms/Scalar/NewGVN.cpp

1475–1482 ↗

(On Diff #82482)

Fixed

[davide]

include/llvm/Transforms/Scalar/GVNExpression.h

232–233 ↗

(On Diff #82482)

yeah, makes sense, maybe adding a comment (up to you, not feeling strong about it).

[• dberlin]

include/llvm/Transforms/Scalar/GVNExpression.h

438–453 ↗

(On Diff #82482)

This is pretty much beyond my C++ knowledge to fix sanely :)
The problem is that we want both to work.
IE we don't want op_inserter to call int_op_push_back on aggregatevalues, because aggregatevalues have both ops and int_ops.

Even sharing the base functions is non-trivial

[davide]

LGTM

include/llvm/Transforms/Scalar/GVNExpression.h

438–453 ↗

(On Diff #82482)

Don't worry then =)

llvm/trunk/include/llvm/Transforms/Scalar/GVNExpression.h

virtual void printInternal(raw_ostream &OS, bool PrintEType) const override {
     for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
       OS << "[" << i << "] = ";
       Operands[i]->printAsOperand(OS);
       OS << "  ";
     }
     OS << "} ";
   }
 };
+class op_inserter
+    : public std::iterator<std::output_iterator_tag, void, void, void, void> {
+private:
+  typedef BasicExpression Container;
+  Container *BE;
+public:
+  explicit op_inserter(BasicExpression &E) : BE(&E) {}
+  explicit op_inserter(BasicExpression *E) : BE(E) {}
+
+  op_inserter &operator=(Value *val) {
+    BE->op_push_back(val);
+    return *this;
+  }
+  op_inserter &operator*() { return *this; }
+  op_inserter &operator++() { return *this; }
+  op_inserter &operator++(int) { return *this; }
+};
+
 
 class CallExpression final : public BasicExpression {
 private:
   CallInst *Call;
   MemoryAccess *DefiningAccess;
 
 public:
   static bool classof(const Expression *EB) {
virtual void printInternal(raw_ostream &OS, bool PrintEType) const override {
     this->BasicExpression::printInternal(OS, false);
     OS << ", intoperands = {";
     for (unsigned i = 0, e = int_op_size(); i != e; ++i) {
       OS << "[" << i << "] = " << IntOperands[i] << "  ";
     }
     OS << "}";
   }
 };
+class int_op_inserter
+    : public std::iterator<std::output_iterator_tag, void, void, void, void> {
+private:
+  typedef AggregateValueExpression Container;
+  Container *AVE;
+
+public:
+  explicit int_op_inserter(AggregateValueExpression &E) : AVE(&E) {}
+  explicit int_op_inserter(AggregateValueExpression *E) : AVE(E) {}
+  int_op_inserter &operator=(unsigned int val) {
+    AVE->int_op_push_back(val);
+    return *this;
+  }
+  int_op_inserter &operator*() { return *this; }
+  int_op_inserter &operator++() { return *this; }
+  int_op_inserter &operator++(int) { return *this; }
+};
+
 
 class PHIExpression final : public BasicExpression {
 private:
   BasicBlock *BB;
 
 public:
   static bool classof(const Expression *EB) {
     return EB->getExpressionType() == ET_Phi;

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

PHIExpression *NewGVN::createPHIExpression(Instruction *I) {
   BasicBlock *PhiBlock = I->getParent();
   PHINode *PN = cast<PHINode>(I);
   PHIExpression *E = new (ExpressionAllocator)
       PHIExpression(PN->getNumOperands(), I->getParent());
 
   E->allocateOperands(ArgRecycler, ExpressionAllocator);
   E->setType(I->getType());
   E->setOpcode(I->getOpcode());
-  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
-    BasicBlock *B = PN->getIncomingBlock(i);
-    if (!ReachableBlocks.count(B)) {
-      DEBUG(dbgs() << "Skipping unreachable block " << getBlockName(B)
-                   << " in PHI node " << *PN << "\n");
-      continue;
-    }
-    if (I->getOperand(i) != I) {
-      const BasicBlockEdge BBE(B, PhiBlock);
-      E->op_push_back(lookupOperandLeader(I->getOperand(i), I, BBE));
-    } else {
-      E->op_push_back(I->getOperand(i));
-    }
-  }
+
+  auto ReachablePhiArg = [&](const Use &U) {
+    return ReachableBlocks.count(PN->getIncomingBlock(U));
+  };
+
+  // Filter out unreachable operands
+  auto Filtered = make_filter_range(PN->operands(), ReachablePhiArg);
+
+  std::transform(Filtered.begin(), Filtered.end(), op_inserter(E),
+                 [&](const Use &U) -> Value * {
+                   // Don't try to transform self-defined phis
+                   if (U == PN)
+                     return PN;
+                   const BasicBlockEdge BBE(PN->getIncomingBlock(U), PhiBlock);
+                   return lookupOperandLeader(U, I, BBE);
+                 });
   return E;
 }
 
 // Set basic expression info (Arguments, type, opcode) for Expression
 // E from Instruction I in block B.
 bool NewGVN::setBasicExpressionInfo(Instruction *I, BasicExpression *E,
                                     const BasicBlock *B) {
   bool AllConstant = true;
   if (auto *GEP = dyn_cast<GetElementPtrInst>(I))
     E->setType(GEP->getSourceElementType());
   else
     E->setType(I->getType());
   E->setOpcode(I->getOpcode());
   E->allocateOperands(ArgRecycler, ExpressionAllocator);
 
-  for (auto &O : I->operands()) {
+  // Transform the operand array into an operand leader array, and keep track of
+  // whether all members are constant.
+  std::transform(I->op_begin(), I->op_end(), op_inserter(E), [&](Value *O) {
     auto Operand = lookupOperandLeader(O, I, B);
-    if (!isa<Constant>(Operand))
-      AllConstant = false;
-    E->op_push_back(Operand);
-  }
+    AllConstant &= isa<Constant>(Operand);
+    return Operand;
+  });
+
   return AllConstant;
 }
 
 const Expression *NewGVN::createBinaryExpression(unsigned Opcode, Type *T,
                                                  Value *Arg1, Value *Arg2,
                                                  const BasicBlock *B) {
   BasicExpression *E = new (ExpressionAllocator) BasicExpression(2);
 

 
 const AggregateValueExpression *
 NewGVN::createAggregateValueExpression(Instruction *I, const BasicBlock *B) {
   if (auto *II = dyn_cast<InsertValueInst>(I)) {
     AggregateValueExpression *E = new (ExpressionAllocator)
         AggregateValueExpression(I->getNumOperands(), II->getNumIndices());
     setBasicExpressionInfo(I, E, B);
     E->allocateIntOperands(ExpressionAllocator);
-
-    for (auto &Index : II->indices())
-      E->int_op_push_back(Index);
+    std::copy(II->idx_begin(), II->idx_end(), int_op_inserter(E));
     return E;
-
   } else if (auto *EI = dyn_cast<ExtractValueInst>(I)) {
     AggregateValueExpression *E = new (ExpressionAllocator)
         AggregateValueExpression(I->getNumOperands(), EI->getNumIndices());
     setBasicExpressionInfo(EI, E, B);
     E->allocateIntOperands(ExpressionAllocator);
-
-    for (auto &Index : EI->indices())
-      E->int_op_push_back(Index);
+    std::copy(EI->idx_begin(), EI->idx_end(), int_op_inserter(E));
     return E;
   }
   llvm_unreachable("Unhandled type of aggregate value operation");
 }
 
 const VariableExpression *
 NewGVN::createVariableExpression(Value *V) {
   VariableExpression *E = new (ExpressionAllocator) VariableExpression(V);

 }
 
 // Evaluate read only and pure calls, and create an expression result.
 const Expression *NewGVN::performSymbolicCallEvaluation(Instruction *I,
                                                         const BasicBlock *B) {
   CallInst *CI = cast<CallInst>(I);
   if (AA->doesNotAccessMemory(CI))
     return createCallExpression(CI, nullptr, B);
-  else if (AA->onlyReadsMemory(CI))
-    return createCallExpression(CI, MSSAWalker->getClobberingMemoryAccess(CI),
+  else if (AA->onlyReadsMemory(CI)) {
+    MemoryAccess *DefiningAccess = MSSAWalker->getClobberingMemoryAccess(CI);
+    return createCallExpression(CI, lookupMemoryAccessEquiv(DefiningAccess),
                                 B);
+  }
   else
     return nullptr;
 }
 
 // Update the memory access equivalence table to say that From is equal to To,
 // and return true if this is different from what already existed in the table.
 bool NewGVN::setMemoryAccessEquivTo(MemoryAccess *From, MemoryAccess *To) {
   auto LookupResult = MemoryAccessEquiv.insert({From, nullptr});

 // The algorithm initially places the values of the routine in the INITIAL congruence
 // class. The leader of INITIAL is the undetermined value `TOP`.
 // When the algorithm has finished, values still in INITIAL are unreachable.
 void NewGVN::initializeCongruenceClasses(Function &F) {
   // FIXME now i can't remember why this is 2
   NextCongruenceNum = 2;
   // Initialize all other instructions to be in INITIAL class.
   CongruenceClass::MemberSet InitialValues;
+  InitialClass = createCongruenceClass(NULL, NULL);
   for (auto &B : F)
-    for (auto &I : B)
+    for (auto &I : B) {
       InitialValues.insert(&I);
-
-  InitialClass = createCongruenceClass(NULL, NULL);
-  for (auto L : InitialValues)
-    ValueToClass[L] = InitialClass;
+      ValueToClass[&I] = InitialClass;
+    }
   InitialClass->Members.swap(InitialValues);
 
   // Initialize arguments to be in their own unique congruence classes
   for (auto &FA : F.args())
     createSingletonCongruenceClass(&FA);
 }
 
 void NewGVN::cleanupTables() {
bool NewGVN::runGVN(Function &F, DominatorTree *_DT, AssumptionCache *_AC,
   for (Instruction *ToErase : InstructionsToErase) {
     if (!ToErase->use_empty())
       ToErase->replaceAllUsesWith(UndefValue::get(ToErase->getType()));
 
     ToErase->eraseFromParent();
   }
 
   // Delete all unreachable blocks.
-  for (auto &B : F) {
-    BasicBlock *BB = &B;
-    if (!ReachableBlocks.count(BB)) {
-      DEBUG(dbgs() << "We believe block " << getBlockName(BB)
-                   << " is unreachable\n");
-      deleteInstructionsInBlock(BB);
-      Changed = true;
-    }
-  }
+  auto UnreachableBlockPred =
+      [&](const BasicBlock &BB) { return !ReachableBlocks.count(&BB); };
+
+  for (auto &BB : make_filter_range(F, UnreachableBlockPred)) {
+    DEBUG(dbgs() << "We believe block " << getBlockName(&BB)
+    deleteInstructionsInBlock(&BB);
 
   cleanupTables();
   return Changed;
 }
 
 bool NewGVN::runOnFunction(Function &F) {
   if (skipFunction(F))
     return false;

 }
 
 bool NewGVN::eliminateInstructions(Function &F) {
   // This is a non-standard eliminator. The normal way to eliminate is
   // to walk the dominator tree in order, keeping track of available
   // values, and eliminating them.  However, this is mildly
   // pointless. It requires doing lookups on every instruction,
   // regardless of whether we will ever eliminate it.  For
-  // instructions part of most singleton congruence class, we know we
-  // will never eliminate it.
+  // instructions part of most singleton congruence classes, we know we
+  // will never eliminate them.
 
   // Instead, this eliminator looks at the congruence classes directly, sorts
   // them into a DFS ordering of the dominator tree, and then we just
-  // perform eliminate straight on the sets by walking the congruence
+  // perform elimination straight on the sets by walking the congruence
   // class member uses in order, and eliminate the ones dominated by the
-  // last member.   This is technically O(N log N) where N = number of
-  // instructions (since in theory all instructions may be in the same
-  // congruence class).
+  // last member.   This is worst case O(E log E) where E = number of
+  // instructions in a single congruence class.  In theory, this is all
+  // instructions.   In practice, it is much faster, as most instructions are
+  // either in singleton congruence classes or can't possibly be eliminated
+  // anyway (if there are no overlapping DFS ranges in class).
   // When we find something not dominated, it becomes the new leader
-  // for elimination purposes
+  // for elimination purposes.
+  // TODO: If we wanted to be faster, We could remove any members with no
+  // overlapping ranges while sorting, as we will never eliminate anything
+  // with those members, as they don't dominate anything else in our set.
+
 
   bool AnythingReplaced = false;
 
   // Since we are going to walk the domtree anyway, and we can't guarantee the
   // DFS numbers are updated, we compute some ourselves.
   DT->updateDFSNumbers();
 
   for (auto &B : F) {