[NFC] Traverse function using dominator tree.

[zoecarver]

Summary

Iterate over the basic blocks in a function using a dominator tree instead of the function iterator.

This will be helpful when adding support for multiple blocks.

[lebedev.ri]

I'm not really sure as to the future of this DSE given the work on Mem-SSA-driven DSE.

[zoecarver]

@lebedev.ri you're right. I just took a look at the MSSA DSE and it looks much more powerful. I'll contribute changes to that in the future (looks like there's a lot of working being done already).

[fhahn]

In D79298#2016937, @zoecarver wrote:

@lebedev.ri you're right. I just took a look at the MSSA DSE and it looks much more powerful. I'll contribute changes to that in the future (looks like there's a lot of working being done already).

As @lebedev.ri pointed out, there's an effort to provide cross-basicblock DSE using MemorySSA. I've create an umbrella bug to track the effort: https://bugs.llvm.org/show_bug.cgi?id=45792. There are a few patches pending adding functionality, but there is at least one more feature missing (without any patches yet) to reach parity with legacy DSE: https://bugs.llvm.org/show_bug.cgi?id=45795. Please feel free to reach out if you are interested in helping out!

[zoecarver]

@fhahn thanks for the links. Yes, I'm happy to help out. I can get started on the noop store bug this week. I'll post a comment over there (in that bug).

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

 //===- DeadStoreElimination.cpp - Fast Dead Store Elimination -------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements a trivial dead store elimination that only considers
 // basic-block local redundant stores.
 //
-// FIXME: This should eventually be extended to be a post-dominator tree
-// traversal.  Doing so would be pretty trivial.
-//
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/DeadStoreElimination.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SetVector.h"
static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA,
 
   return MadeChange;
 }
 
 static bool eliminateDeadStores(Function &F, AliasAnalysis *AA,
                                 MemoryDependenceResults *MD, DominatorTree *DT,
                                 const TargetLibraryInfo *TLI) {
   bool MadeChange = false;
-  for (BasicBlock &BB : F)
+  for (auto node = GraphTraits<DominatorTree *>::nodes_begin(DT);
+       node != GraphTraits<DominatorTree *>::nodes_end(DT); ++node) {
+    BasicBlock *BB = node->getBlock();
     // Only check non-dead blocks.  Dead blocks may have strange pointer
     // cycles that will confuse alias analysis.
-    if (DT->isReachableFromEntry(&BB))
-      MadeChange |= eliminateDeadStores(BB, AA, MD, DT, TLI);
-
+    if (DT->isReachableFromEntry(BB))
+      MadeChange |= eliminateDeadStores(*BB, AA, MD, DT, TLI);
+  }
   return MadeChange;
 }
 
 namespace {
 //=============================================================================
 // MemorySSA backed dead store elimination.
 //
 // The code below implements dead store elimination using MemorySSA. It uses