[deadcode analysis] move all the files arounddca

11 files changed, 543 insertions, 449 deletions

diff --git a/mlir/include/mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h b/mlir/include/mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h
new file mode 100644
index 000000000000..5e04516e310b
--- /dev/null
+++ b/mlir/include/mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h
@@ -0,0 +1,66 @@
+//===- ConstantPropagationAnalysis.h - Constant propagation analysis ------===//
+//
+// 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 constant propagation analysis. In this file are defined
+// the lattice value class that represents constant values in the program and
+// a sparse constant propagation analysis that uses operation folders to
+// speculate about constant values in the program.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef MLIR_ANALYSIS_DATAFLOW_CONSTANTPROPAGATIONANALYSIS_H
+#define MLIR_ANALYSIS_DATAFLOW_CONSTANTPROPAGATIONANALYSIS_H
+
+#include "mlir/Analysis/DataFlow/SparseAnalysis.h"
+
+namespace mlir {
+namespace dataflow {
+
+//===----------------------------------------------------------------------===//
+// ConstantValue
+//===----------------------------------------------------------------------===//
+
+/// This lattice value represents a known constant value of a lattice.
+class ConstantValue {
+public:
+  /// Construct a constant value with a known constant.
+  ConstantValue(Attribute knownValue = {}, Dialect *dialect = nullptr)
+      : constant(knownValue), dialect(dialect) {}
+
+  /// Get the constant value. Returns null if no value was determined.
+  Attribute getConstantValue() const { return constant; }
+
+  /// Get the dialect instance that can be used to materialize the constant.
+  Dialect *getConstantDialect() const { return dialect; }
+
+  /// Compare the constant values.
+  bool operator==(const ConstantValue &rhs) const {
+    return constant == rhs.constant;
+  }
+
+  /// The union with another constant value is null if they are different, and
+  /// the same if they are the same.
+  static ConstantValue join(const ConstantValue &lhs,
+                            const ConstantValue &rhs) {
+    return lhs == rhs ? lhs : ConstantValue();
+  }
+
+  /// Print the constant value.
+  void print(raw_ostream &os) const;
+
+private:
+  /// The constant value.
+  Attribute constant;
+  /// An dialect instance that can be used to materialize the constant.
+  Dialect *dialect;
+};
+
+} // end namespace dataflow
+} // end namespace mlir
+
+#endif // MLIR_ANALYSIS_DATAFLOW_CONSTANTPROPAGATIONANALYSIS_H
diff --git a/mlir/include/mlir/Analysis/DataFlow/DeadCodeAnalysis.h b/mlir/include/mlir/Analysis/DataFlow/DeadCodeAnalysis.h
new file mode 100644
index 000000000000..df8e445d8ea1
--- /dev/null
+++ b/mlir/include/mlir/Analysis/DataFlow/DeadCodeAnalysis.h
@@ -0,0 +1,229 @@
+//===- DeadCodeAnalysis.h - Dead code analysis ----------------------------===//
+//
+// 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 dead code analysis using the data-flow analysis
+// framework. This analysis uses the results of constant propagation to
+// determine live blocks, control-flow edges, and control-flow predecessors.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef MLIR_ANALYSIS_DATAFLOW_DEADCODEANALYSIS_H
+#define MLIR_ANALYSIS_DATAFLOW_DEADCODEANALYSIS_H
+
+#include "mlir/Analysis/DataFlowFramework.h"
+#include "mlir/IR/SymbolTable.h"
+#include "mlir/Interfaces/CallInterfaces.h"
+#include "mlir/Interfaces/ControlFlowInterfaces.h"
+#include "llvm/ADT/SmallPtrSet.h"
+
+namespace mlir {
+namespace dataflow {
+
+//===----------------------------------------------------------------------===//
+// Executable
+//===----------------------------------------------------------------------===//
+
+/// This is a simple analysis state that represents whether the associated
+/// program point (either a block or a control-flow edge) is live.
+class Executable : public AnalysisState {
+public:
+  using AnalysisState::AnalysisState;
+
+  /// The state is initialized by default.
+  bool isUninitialized() const override { return false; }
+
+  /// The state is always initialized.
+  ChangeResult defaultInitialize() override { return ChangeResult::NoChange; }
+
+  /// Set the state of the program point to live.
+  ChangeResult setToLive();
+
+  /// Get whether the program point is live.
+  bool isLive() const { return live; }
+
+  /// Print the liveness.
+  void print(raw_ostream &os) const override;
+
+  /// When the state of the program point is changed to live, re-invoke
+  /// subscribed analyses on the operations in the block and on the block
+  /// itself.
+  void onUpdate(DataFlowSolver *solver) const override;
+
+  /// Subscribe an analysis to changes to the liveness.
+  void blockContentSubscribe(DataFlowAnalysis *analysis) {
+    subscribers.insert(analysis);
+  }
+
+private:
+  /// Whether the program point is live. Optimistically assume that the program
+  /// point is dead.
+  bool live = false;
+
+  /// A set of analyses that should be updated when this state changes.
+  SetVector<DataFlowAnalysis *, SmallVector<DataFlowAnalysis *, 4>,
+            SmallPtrSet<DataFlowAnalysis *, 4>>
+      subscribers;
+};
+
+//===----------------------------------------------------------------------===//
+// PredecessorState
+//===----------------------------------------------------------------------===//
+
+/// This analysis state represents a set of live control-flow "predecessors" of
+/// a program point (either an operation or a block), which are the last
+/// operations along all execution paths that pass through this point.
+///
+/// For example, in dead-code analysis, an operation with region control-flow
+/// can be the predecessor of a region's entry block or itself, the exiting
+/// terminator of a region can be the predecessor of the parent operation or
+/// another region's entry block, the callsite of a callable operation can be
+/// the predecessor to its entry block, and the exiting terminator or a callable
+/// operation can be the predecessor of the call operation.
+///
+/// The state can indicate that it is underdefined, meaning that not all live
+/// control-flow predecessors can be known.
+class PredecessorState : public AnalysisState {
+public:
+  using AnalysisState::AnalysisState;
+
+  /// The state is initialized by default.
+  bool isUninitialized() const override { return false; }
+
+  /// The state is always initialized.
+  ChangeResult defaultInitialize() override { return ChangeResult::NoChange; }
+
+  /// Print the known predecessors.
+  void print(raw_ostream &os) const override;
+
+  /// Returns true if all predecessors are known.
+  bool allPredecessorsKnown() const { return allKnown; }
+
+  /// Indicate that there are potentially unknown predecessors.
+  ChangeResult setHasUnknownPredecessors() {
+    return std::exchange(allKnown, false) ? ChangeResult::Change
+                                          : ChangeResult::NoChange;
+  }
+
+  /// Get the known predecessors.
+  ArrayRef<Operation *> getKnownPredecessors() const {
+    return knownPredecessors.getArrayRef();
+  }
+
+  /// Add a known predecessor.
+  ChangeResult join(Operation *predecessor) {
+    return knownPredecessors.insert(predecessor) ? ChangeResult::Change
+                                                 : ChangeResult::NoChange;
+  }
+
+private:
+  /// Whether all predecessors are known. Optimistically assume that we know
+  /// all predecessors.
+  bool allKnown = true;
+
+  /// The known control-flow predecessors of this program point.
+  SetVector<Operation *, SmallVector<Operation *, 4>,
+            SmallPtrSet<Operation *, 4>>
+      knownPredecessors;
+};
+
+//===----------------------------------------------------------------------===//
+// CFGEdge
+//===----------------------------------------------------------------------===//
+
+/// This program point represents a control-flow edge between a block and one
+/// of its successors.
+class CFGEdge
+    : public GenericProgramPointBase<CFGEdge, std::pair<Block *, Block *>> {
+public:
+  using Base::Base;
+
+  /// Get the block from which the edge originates.
+  Block *getFrom() const { return getValue().first; }
+  /// Get the target block.
+  Block *getTo() const { return getValue().second; }
+
+  /// Print the blocks between the control-flow edge.
+  void print(raw_ostream &os) const override;
+  /// Get a fused location of both blocks.
+  Location getLoc() const override;
+};
+
+//===----------------------------------------------------------------------===//
+// DeadCodeAnalysis
+//===----------------------------------------------------------------------===//
+
+/// Dead code analysis analyzes control-flow, as understood by
+/// `RegionBranchOpInterface` and `BranchOpInterface`, and the callgraph, as
+/// understood by `CallableOpInterface` and `CallOpInterface`.
+///
+/// This analysis uses known constant values of operands to determine the
+/// liveness of each block and each edge between a block and its predecessors.
+/// For region control-flow, this analysis determines the predecessor operations
+/// for region entry blocks and region control-flow operations. For the
+/// callgraph, this analysis determines the callsites and live returns of every
+/// function.
+class DeadCodeAnalysis : public DataFlowAnalysis {
+public:
+  explicit DeadCodeAnalysis(DataFlowSolver &solver);
+
+  /// Initialize the analysis by visiting every operation with potential
+  /// control-flow semantics.
+  LogicalResult initialize(Operation *top) override;
+
+  /// Visit an operation with control-flow semantics and deduce which of its
+  /// successors are live.
+  LogicalResult visit(ProgramPoint point) override;
+
+private:
+  /// Find and mark symbol callables with potentially unknown callsites as
+  /// having overdefined predecessors. `top` is the top-level operation that the
+  /// analysis is operating on.
+  void initializeSymbolCallables(Operation *top);
+
+  /// Recursively Initialize the analysis on nested regions.
+  LogicalResult initializeRecursively(Operation *op);
+
+  /// Visit the given call operation and compute any necessary lattice state.
+  void visitCallOperation(CallOpInterface call);
+
+  /// Visit the given branch operation with successors and try to determine
+  /// which are live from the current block.
+  void visitBranchOperation(BranchOpInterface branch);
+
+  /// Visit the given region branch operation, which defines regions, and
+  /// compute any necessary lattice state. This also resolves the lattice state
+  /// of both the operation results and any nested regions.
+  void visitRegionBranchOperation(RegionBranchOpInterface branch);
+
+  /// Visit the given terminator operation that exits a region under an
+  /// operation with control-flow semantics. These are terminators with no CFG
+  /// successors.
+  void visitRegionTerminator(Operation *op, RegionBranchOpInterface branch);
+
+  /// Visit the given terminator operation that exits a callable region. These
+  /// are terminators with no CFG successors.
+  void visitCallableTerminator(Operation *op, CallableOpInterface callable);
+
+  /// Mark the edge between `from` and `to` as executable.
+  void markEdgeLive(Block *from, Block *to);
+
+  /// Mark the entry blocks of the operation as executable.
+  void markEntryBlocksLive(Operation *op);
+
+  /// Get the constant values of the operands of the operation. Returns none if
+  /// any of the operand lattices are uninitialized.
+  Optional<SmallVector<Attribute>> getOperandValues(Operation *op);
+
+  /// A symbol table used for O(1) symbol lookups during simplification.
+  SymbolTableCollection symbolTable;
+};
+
+} // end namespace dataflow
+} // end namespace mlir
+
+#endif // MLIR_ANALYSIS_DATAFLOW_DEADCODEANALYSIS_H
diff --git a/mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h b/mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h
new file mode 100644
index 000000000000..f15416a9cfad
--- /dev/null
+++ b/mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h
@@ -0,0 +1,185 @@
+//===- SparseAnalysis.h - Sparse data-flow analysis -----------------------===//
+//
+// 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 sparse data-flow analysis using the data-flow analysis
+// framework. The analysis is forward and conditional and uses the results of
+// dead code analysis to prune dead code during the analysis.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef MLIR_ANALYSIS_DATAFLOW_SPARSEANALYSIS_H
+#define MLIR_ANALYSIS_DATAFLOW_SPARSEANALYSIS_H
+
+#include "mlir/Analysis/DataFlowFramework.h"
+#include "llvm/ADT/SmallPtrSet.h"
+
+namespace mlir {
+namespace dataflow {
+
+//===----------------------------------------------------------------------===//
+// AbstractSparseLattice
+//===----------------------------------------------------------------------===//
+
+/// This class represents an abstract lattice. A lattice contains information
+/// about an SSA value and is what's propagated across the IR by sparse
+/// data-flow analysis.
+class AbstractSparseLattice : public AnalysisState {
+public:
+  /// Lattices can only be created for values.
+  AbstractSparseLattice(Value value) : AnalysisState(value) {}
+
+  /// Join the information contained in 'rhs' into this lattice. Returns
+  /// if the value of the lattice changed.
+  virtual ChangeResult join(const AbstractSparseLattice &rhs) = 0;
+
+  /// Returns true if the lattice element is at fixpoint and further calls to
+  /// `join` will not update the value of the element.
+  virtual bool isAtFixpoint() const = 0;
+
+  /// Mark the lattice element as having reached a pessimistic fixpoint. This
+  /// means that the lattice may potentially have conflicting value states, and
+  /// only the most conservative value should be relied on.
+  virtual ChangeResult markPessimisticFixpoint() = 0;
+
+  /// When the lattice gets updated, propagate an update to users of the value
+  /// using its use-def chain to subscribed analyses.
+  void onUpdate(DataFlowSolver *solver) const override;
+
+  /// Subscribe an analysis to updates of the lattice. When the lattice changes,
+  /// subscribed analyses are re-invoked on all users of the value. This is
+  /// more efficient than relying on the dependency map.
+  void useDefSubscribe(DataFlowAnalysis *analysis) {
+    useDefSubscribers.insert(analysis);
+  }
+
+private:
+  /// A set of analyses that should be updated when this lattice changes.
+  SetVector<DataFlowAnalysis *, SmallVector<DataFlowAnalysis *, 4>,
+            SmallPtrSet<DataFlowAnalysis *, 4>>
+      useDefSubscribers;
+};
+
+//===----------------------------------------------------------------------===//
+// Lattice
+//===----------------------------------------------------------------------===//
+
+/// This class represents a lattice holding a specific value of type `ValueT`.
+/// Lattice values (`ValueT`) are required to adhere to the following:
+///
+///   * static ValueT join(const ValueT &lhs, const ValueT &rhs);
+///     - This method conservatively joins the information held by `lhs`
+///       and `rhs` into a new value. This method is required to be monotonic.
+///   * bool operator==(const ValueT &rhs) const;
+///
+template <typename ValueT>
+class Lattice : public AbstractSparseLattice {
+public:
+  using AbstractSparseLattice::AbstractSparseLattice;
+
+  /// Get a lattice element with a known value.
+  Lattice(const ValueT &knownValue = ValueT())
+      : AbstractSparseLattice(Value()), knownValue(knownValue) {}
+
+  /// Return the value held by this lattice. This requires that the value is
+  /// initialized.
+  ValueT &getValue() {
+    assert(!isUninitialized() && "expected known lattice element");
+    return *optimisticValue;
+  }
+  const ValueT &getValue() const {
+    return const_cast<Lattice<ValueT> *>(this)->getValue();
+  }
+
+  /// Returns true if the value of this lattice hasn't yet been initialized.
+  bool isUninitialized() const override { return !optimisticValue.hasValue(); }
+  /// Force the initialization of the element by setting it to its pessimistic
+  /// fixpoint.
+  ChangeResult defaultInitialize() override {
+    return markPessimisticFixpoint();
+  }
+
+  /// Returns true if the lattice has reached a fixpoint. A fixpoint is when
+  /// the information optimistically assumed to be true is the same as the
+  /// information known to be true.
+  bool isAtFixpoint() const override { return optimisticValue == knownValue; }
+
+  /// Join the information contained in the 'rhs' lattice into this
+  /// lattice. Returns if the state of the current lattice changed.
+  ChangeResult join(const AbstractSparseLattice &rhs) override {
+    const Lattice<ValueT> &rhsLattice =
+        static_cast<const Lattice<ValueT> &>(rhs);
+
+    // If we are at a fixpoint, or rhs is uninitialized, there is nothing to do.
+    if (isAtFixpoint() || rhsLattice.isUninitialized())
+      return ChangeResult::NoChange;
+
+    // Join the rhs value into this lattice.
+    return join(rhsLattice.getValue());
+  }
+
+  /// Join the information contained in the 'rhs' value into this
+  /// lattice. Returns if the state of the current lattice changed.
+  ChangeResult join(const ValueT &rhs) {
+    // If the current lattice is uninitialized, copy the rhs value.
+    if (isUninitialized()) {
+      optimisticValue = rhs;
+      return ChangeResult::Change;
+    }
+
+    // Otherwise, join rhs with the current optimistic value.
+    ValueT newValue = ValueT::join(*optimisticValue, rhs);
+    assert(ValueT::join(newValue, *optimisticValue) == newValue &&
+           "expected `join` to be monotonic");
+    assert(ValueT::join(newValue, rhs) == newValue &&
+           "expected `join` to be monotonic");
+
+    // Update the current optimistic value if something changed.
+    if (newValue == optimisticValue)
+      return ChangeResult::NoChange;
+
+    optimisticValue = newValue;
+    return ChangeResult::Change;
+  }
+
+  /// Mark the lattice element as having reached a pessimistic fixpoint. This
+  /// means that the lattice may potentially have conflicting value states,
+  /// and only the conservatively known value state should be relied on.
+  ChangeResult markPessimisticFixpoint() override {
+    if (isAtFixpoint())
+      return ChangeResult::NoChange;
+
+    // For this fixed point, we take whatever we knew to be true and set that
+    // to our optimistic value.
+    optimisticValue = knownValue;
+    return ChangeResult::Change;
+  }
+
+  /// Print the lattice element.
+  void print(raw_ostream &os) const override {
+    os << "[";
+    knownValue.print(os);
+    os << ", ";
+    if (optimisticValue)
+      optimisticValue->print(os);
+    else
+      os << "<NULL>";
+    os << "]";
+  }
+
+private:
+  /// The value that is conservatively known to be true.
+  ValueT knownValue;
+  /// The currently computed value that is optimistically assumed to be true,
+  /// or None if the lattice element is uninitialized.
+  Optional<ValueT> optimisticValue;
+};
+
+} // end namespace dataflow
+} // end namespace mlir
+
+#endif // MLIR_ANALYSIS_DATAFLOW_SPARSEANALYSIS_H
diff --git a/mlir/include/mlir/Analysis/SparseDataFlowAnalysis.h b/mlir/include/mlir/Analysis/SparseDataFlowAnalysis.h
deleted file mode 100644
index ee9392b387e6..000000000000
--- a/mlir/include/mlir/Analysis/SparseDataFlowAnalysis.h
+++ /dev/null
@@ -1,418 +0,0 @@
-//===- SparseDataFlowAnalysis.h - Sparse data-flow analysis ---------------===//
-//
-// 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 sparse data-flow analysis using the data-flow analysis
-// framework. The analysis is forward and conditional and uses the results of
-// dead code analysis to prune dead code during the analysis.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef MLIR_ANALYSIS_SPARSEDATAFLOWANALYSIS_H
-#define MLIR_ANALYSIS_SPARSEDATAFLOWANALYSIS_H
-
-#include "mlir/Analysis/DataFlowFramework.h"
-#include "mlir/IR/SymbolTable.h"
-#include "mlir/Interfaces/CallInterfaces.h"
-#include "mlir/Interfaces/ControlFlowInterfaces.h"
-#include "llvm/ADT/SmallPtrSet.h"
-
-namespace mlir {
-
-//===----------------------------------------------------------------------===//
-// AbstractSparseLattice
-//===----------------------------------------------------------------------===//
-
-/// This class represents an abstract lattice. A lattice contains information
-/// about an SSA value and is what's propagated across the IR by sparse
-/// data-flow analysis.
-class AbstractSparseLattice : public AnalysisState {
-public:
-  /// Lattices can only be created for values.
-  AbstractSparseLattice(Value value) : AnalysisState(value) {}
-
-  /// Join the information contained in 'rhs' into this lattice. Returns
-  /// if the value of the lattice changed.
-  virtual ChangeResult join(const AbstractSparseLattice &rhs) = 0;
-
-  /// Returns true if the lattice element is at fixpoint and further calls to
-  /// `join` will not update the value of the element.
-  virtual bool isAtFixpoint() const = 0;
-
-  /// Mark the lattice element as having reached a pessimistic fixpoint. This
-  /// means that the lattice may potentially have conflicting value states, and
-  /// only the most conservative value should be relied on.
-  virtual ChangeResult markPessimisticFixpoint() = 0;
-
-  /// When the lattice gets updated, propagate an update to users of the value
-  /// using its use-def chain to subscribed analyses.
-  void onUpdate(DataFlowSolver *solver) const override;
-
-  /// Subscribe an analysis to updates of the lattice. When the lattice changes,
-  /// subscribed analyses are re-invoked on all users of the value. This is
-  /// more efficient than relying on the dependency map.
-  void useDefSubscribe(DataFlowAnalysis *analysis) {
-    useDefSubscribers.insert(analysis);
-  }
-
-private:
-  /// A set of analyses that should be updated when this lattice changes.
-  SetVector<DataFlowAnalysis *, SmallVector<DataFlowAnalysis *, 4>,
-            SmallPtrSet<DataFlowAnalysis *, 4>>
-      useDefSubscribers;
-};
-
-//===----------------------------------------------------------------------===//
-// Lattice
-//===----------------------------------------------------------------------===//
-
-/// This class represents a lattice holding a specific value of type `ValueT`.
-/// Lattice values (`ValueT`) are required to adhere to the following:
-///
-///   * static ValueT join(const ValueT &lhs, const ValueT &rhs);
-///     - This method conservatively joins the information held by `lhs`
-///       and `rhs` into a new value. This method is required to be monotonic.
-///   * bool operator==(const ValueT &rhs) const;
-///
-template <typename ValueT>
-class Lattice : public AbstractSparseLattice {
-public:
-  using AbstractSparseLattice::AbstractSparseLattice;
-
-  /// Get a lattice element with a known value.
-  Lattice(const ValueT &knownValue = ValueT())
-      : AbstractSparseLattice(Value()), knownValue(knownValue) {}
-
-  /// Return the value held by this lattice. This requires that the value is
-  /// initialized.
-  ValueT &getValue() {
-    assert(!isUninitialized() && "expected known lattice element");
-    return *optimisticValue;
-  }
-  const ValueT &getValue() const {
-    return const_cast<Lattice<ValueT> *>(this)->getValue();
-  }
-
-  /// Returns true if the value of this lattice hasn't yet been initialized.
-  bool isUninitialized() const override { return !optimisticValue.hasValue(); }
-  /// Force the initialization of the element by setting it to its pessimistic
-  /// fixpoint.
-  ChangeResult defaultInitialize() override {
-    return markPessimisticFixpoint();
-  }
-
-  /// Returns true if the lattice has reached a fixpoint. A fixpoint is when
-  /// the information optimistically assumed to be true is the same as the
-  /// information known to be true.
-  bool isAtFixpoint() const override { return optimisticValue == knownValue; }
-
-  /// Join the information contained in the 'rhs' lattice into this
-  /// lattice. Returns if the state of the current lattice changed.
-  ChangeResult join(const AbstractSparseLattice &rhs) override {
-    const Lattice<ValueT> &rhsLattice =
-        static_cast<const Lattice<ValueT> &>(rhs);
-
-    // If we are at a fixpoint, or rhs is uninitialized, there is nothing to do.
-    if (isAtFixpoint() || rhsLattice.isUninitialized())
-      return ChangeResult::NoChange;
-
-    // Join the rhs value into this lattice.
-    return join(rhsLattice.getValue());
-  }
-
-  /// Join the information contained in the 'rhs' value into this
-  /// lattice. Returns if the state of the current lattice changed.
-  ChangeResult join(const ValueT &rhs) {
-    // If the current lattice is uninitialized, copy the rhs value.
-    if (isUninitialized()) {
-      optimisticValue = rhs;
-      return ChangeResult::Change;
-    }
-
-    // Otherwise, join rhs with the current optimistic value.
-    ValueT newValue = ValueT::join(*optimisticValue, rhs);
-    assert(ValueT::join(newValue, *optimisticValue) == newValue &&
-           "expected `join` to be monotonic");
-    assert(ValueT::join(newValue, rhs) == newValue &&
-           "expected `join` to be monotonic");
-
-    // Update the current optimistic value if something changed.
-    if (newValue == optimisticValue)
-      return ChangeResult::NoChange;
-
-    optimisticValue = newValue;
-    return ChangeResult::Change;
-  }
-
-  /// Mark the lattice element as having reached a pessimistic fixpoint. This
-  /// means that the lattice may potentially have conflicting value states,
-  /// and only the conservatively known value state should be relied on.
-  ChangeResult markPessimisticFixpoint() override {
-    if (isAtFixpoint())
-      return ChangeResult::NoChange;
-
-    // For this fixed point, we take whatever we knew to be true and set that
-    // to our optimistic value.
-    optimisticValue = knownValue;
-    return ChangeResult::Change;
-  }
-
-  /// Print the lattice element.
-  void print(raw_ostream &os) const override {
-    os << "[";
-    knownValue.print(os);
-    os << ", ";
-    if (optimisticValue) {
-      optimisticValue->print(os);
-    } else {
-      os << "<NULL>";
-    }
-    os << "]";
-  }
-
-private:
-  /// The value that is conservatively known to be true.
-  ValueT knownValue;
-  /// The currently computed value that is optimistically assumed to be true,
-  /// or None if the lattice element is uninitialized.
-  Optional<ValueT> optimisticValue;
-};
-
-//===----------------------------------------------------------------------===//
-// Executable
-//===----------------------------------------------------------------------===//
-
-/// This is a simple analysis state that represents whether the associated
-/// program point (either a block or a control-flow edge) is live.
-class Executable : public AnalysisState {
-public:
-  using AnalysisState::AnalysisState;
-
-  /// The state is initialized by default.
-  bool isUninitialized() const override { return false; }
-
-  /// The state is always initialized.
-  ChangeResult defaultInitialize() override { return ChangeResult::NoChange; }
-
-  /// Set the state of the program point to live.
-  ChangeResult setToLive();
-
-  /// Get whether the program point is live.
-  bool isLive() const { return live; }
-
-  /// Print the liveness;
-  void print(raw_ostream &os) const override;
-
-  /// When the state of the program point is changed to live, re-invoke
-  /// subscribed analyses on the operations in the block and on the block
-  /// itself.
-  void onUpdate(DataFlowSolver *solver) const override;
-
-  /// Subscribe an analysis to changes to the liveness.
-  void blockContentSubscribe(DataFlowAnalysis *analysis) {
-    subscribers.insert(analysis);
-  }
-
-private:
-  /// Whether the program point is live. Optimistically assume that the program
-  /// point is dead.
-  bool live = false;
-
-  /// A set of analyses that should be updated when this state changes.
-  SetVector<DataFlowAnalysis *, SmallVector<DataFlowAnalysis *, 4>,
-            SmallPtrSet<DataFlowAnalysis *, 4>>
-      subscribers;
-};
-
-//===----------------------------------------------------------------------===//
-// ConstantValue
-//===----------------------------------------------------------------------===//
-
-/// This lattice value represents a known constant value of a lattice.
-class ConstantValue {
-public:
-  /// Construct a constant value with a known constant.
-  ConstantValue(Attribute knownValue = {}, Dialect *dialect = nullptr)
-      : constant(knownValue), dialect(dialect) {}
-
-  /// Get the constant value. Returns null if no value was determined.
-  Attribute getConstantValue() const { return constant; }
-
-  /// Get the dialect instance that can be used to materialize the constant.
-  Dialect *getConstantDialect() const { return dialect; }
-
-  /// Compare the constant values.
-  bool operator==(const ConstantValue &rhs) const {
-    return constant == rhs.constant;
-  }
-
-  /// The union with another constant value is null if they are different, and
-  /// the same if they are the same.
-  static ConstantValue join(const ConstantValue &lhs,
-                            const ConstantValue &rhs) {
-    return lhs == rhs ? lhs : ConstantValue();
-  }
-
-  /// Print the constant value.
-  void print(raw_ostream &os) const;
-
-private:
-  /// The constant value.
-  Attribute constant;
-  /// An dialect instance that can be used to materialize the constant.
-  Dialect *dialect;
-};
-
-//===----------------------------------------------------------------------===//
-// PredecessorState
-//===----------------------------------------------------------------------===//
-
-/// This analysis state represents a set of known predecessors. This state is
-/// used in sparse data-flow analysis to reason about region control-flow and
-/// callgraphs. The state may also indicate that not all predecessors can be
-/// known, if for example not all callsites of a callable are visible.
-class PredecessorState : public AnalysisState {
-public:
-  using AnalysisState::AnalysisState;
-
-  /// The state is initialized by default.
-  bool isUninitialized() const override { return false; }
-
-  /// The state is always initialized.
-  ChangeResult defaultInitialize() override { return ChangeResult::NoChange; }
-
-  /// Print the known predecessors.
-  void print(raw_ostream &os) const override;
-
-  /// Returns true if all predecessors are known.
-  bool allPredecessorsKnown() const { return allKnown; }
-
-  /// Indicate that there are potentially unknown predecessors.
-  ChangeResult setHasUnknownPredecessors() {
-    if (!allKnown)
-      return ChangeResult::NoChange;
-    allKnown = false;
-    return ChangeResult::Change;
-  }
-
-  /// Get the known predecessors.
-  ArrayRef<Operation *> getKnownPredecessors() const {
-    return knownPredecessors.getArrayRef();
-  }
-
-  /// Add a known predecessor.
-  ChangeResult join(Operation *predecessor) {
-    return knownPredecessors.insert(predecessor) ? ChangeResult::Change
-                                                 : ChangeResult::NoChange;
-  }
-
-private:
-  /// Whether all predecessors are known. Optimistically assume that we know
-  /// all predecessors.
-  bool allKnown = true;
-
-  /// The known control-flow predecessors of this program point.
-  SetVector<Operation *, SmallVector<Operation *, 4>,
-            SmallPtrSet<Operation *, 4>>
-      knownPredecessors;
-};
-
-//===----------------------------------------------------------------------===//
-// CFGEdge
-//===----------------------------------------------------------------------===//
-
-/// This program point represents a control-flow edge between a block and one
-/// of its successors.
-class CFGEdge
-    : public GenericProgramPointBase<CFGEdge, std::pair<Block *, Block *>> {
-public:
-  using Base::Base;
-
-  /// Get the block from which the edge originates.
-  Block *getFrom() const { return getValue().first; }
-  /// Get the target block.
-  Block *getTo() const { return getValue().second; }
-
-  /// Print the blocks between the control-flow edge.
-  void print(raw_ostream &os) const override;
-  /// Get a fused location of both blocks.
-  Location getLoc() const override;
-};
-
-//===----------------------------------------------------------------------===//
-// DeadCodeAnalysis
-//===----------------------------------------------------------------------===//
-
-/// Dead code analysis analyzes control-flow, as understood by
-/// `RegionBranchOpInterface` and `BranchOpInterface`, and the callgraph, as
-/// understood by `CallableOpInterface` and `CallOpInterface`.
-///
-/// This analysis uses known constant values of operands to determine the
-/// liveness of each block and each edge between a block and its predecessors.
-/// For region control-flow, this analysis determines the predecessor operations
-/// for region entry blocks and region control-flow operations. For the
-/// callgraph, this analysis determines the callsites and live returns of every
-/// function.
-class DeadCodeAnalysis : public DataFlowAnalysis {
-public:
-  explicit DeadCodeAnalysis(DataFlowSolver &solver);
-
-  /// Initialize the analysis by visiting every operation with potential
-  /// control-flow semantics.
-  LogicalResult initialize(Operation *top) override;
-
-  /// Visit an operation with control-flow semantics and deduce which of its
-  /// successors are live.
-  LogicalResult visit(ProgramPoint point) override;
-
-private:
-  /// Find and mark symbol callables with potentially unknown callsites as
-  /// having overdefined predecessors. `top` is the top-level operation that the
-  /// analysis is operating on.
-  void initializeSymbolCallables(Operation *top);
-
-  /// Recursively Initialize the analysis on nested regions.
-  LogicalResult initializeRecursively(Operation *op);
-
-  /// Visit the given call operation and compute any necessary lattice state.
-  void visitCallOperation(CallOpInterface call);
-
-  /// Visit the given branch operation with successors and try to determine
-  /// which are live from the current block.
-  void visitBranchOperation(BranchOpInterface branch);
-
-  /// Visit the given region branch operation, which defines regions, and
-  /// compute any necessary lattice state. This also resolves the lattice state
-  /// of both the operation results and any nested regions.
-  void visitRegionBranchOperation(RegionBranchOpInterface branch);
-
-  /// Visit the given terminator operation that exits a region under an
-  /// operation with control-flow semantics. These are terminators with no CFG
-  /// successors.
-  void visitRegionTerminator(Operation *op, RegionBranchOpInterface branch);
-
-  /// Visit the given terminator operation that exits a callable region. These
-  /// are terminators with no CFG successors.
-  void visitCallableTerminator(Operation *op, CallableOpInterface callable);
-
-  /// Mark the edge between `from` and `to` as executable.
-  void markEdgeLive(Block *from, Block *to);
-
-  /// Mark the entry blocks of the operation as executable.
-  void markEntryBlocksLive(Operation *op);
-
-  /// Get the constant values of the operands of the operation. Returns none if
-  /// any of the operand lattices are uninitialized.
-  Optional<SmallVector<Attribute>> getOperandValues(Operation *op);
-
-  /// A symbol table used for O(1) symbol lookups during simplification.
-  SymbolTableCollection symbolTable;
-};
-
-} // end namespace mlir
-
-#endif // MLIR_ANALYSIS_SPARSEDATAFLOWANALYSIS_H
diff --git a/mlir/lib/Analysis/CMakeLists.txt b/mlir/lib/Analysis/CMakeLists.txt
index 662bc1084c5f..2e37135adac4 100644
--- a/mlir/lib/Analysis/CMakeLists.txt
+++ b/mlir/lib/Analysis/CMakeLists.txt
@@ -7,9 +7,12 @@ set(LLVM_OPTIONAL_SOURCES
   IntRangeAnalysis.cpp
   Liveness.cpp
   SliceAnalysis.cpp
-  SparseDataFlowAnalysis.cpp
 
   AliasAnalysis/LocalAliasAnalysis.cpp
+
+  DataFlow/ConstantPropagationAnalysis.cpp
+  DataFlow/DeadCodeAnalysis.cpp
+  DataFlow/SparseAnalysis.cpp
   )
 
 add_mlir_library(MLIRAnalysis
@@ -22,10 +25,13 @@ add_mlir_library(MLIRAnalysis
   IntRangeAnalysis.cpp
   Liveness.cpp
   SliceAnalysis.cpp
-  SparseDataFlowAnalysis.cpp
 
   AliasAnalysis/LocalAliasAnalysis.cpp
 
+  DataFlow/ConstantPropagationAnalysis.cpp
+  DataFlow/DeadCodeAnalysis.cpp
+  DataFlow/SparseAnalysis.cpp
+
   ADDITIONAL_HEADER_DIRS
   ${MLIR_MAIN_INCLUDE_DIR}/mlir/Analysis
 
diff --git a/mlir/lib/Analysis/DataFlow/ConstantPropagationAnalysis.cpp b/mlir/lib/Analysis/DataFlow/ConstantPropagationAnalysis.cpp
new file mode 100644
index 000000000000..f97f8ccdb864
--- /dev/null
+++ b/mlir/lib/Analysis/DataFlow/ConstantPropagationAnalysis.cpp
@@ -0,0 +1,22 @@
+//===- ConstantPropagationAnalysis.cpp - Constant propagation analysis ----===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h"
+
+using namespace mlir;
+using namespace mlir::dataflow;
+
+//===----------------------------------------------------------------------===//
+// ConstantValue
+//===----------------------------------------------------------------------===//
+
+void ConstantValue::print(raw_ostream &os) const {
+  if (constant)
+    return constant.print(os);
+  os << "<NO VALUE>";
+}
diff --git a/mlir/lib/Analysis/SparseDataFlowAnalysis.cpp b/mlir/lib/Analysis/DataFlow/DeadCodeAnalysis.cpp
index 41ff8381b074..20c3b55f3293 100644
--- a/mlir/lib/Analysis/SparseDataFlowAnalysis.cpp
+++ b/mlir/lib/Analysis/DataFlow/DeadCodeAnalysis.cpp
@@ -1,4 +1,4 @@
-//===- SparseDataFlowAnalysis.cpp - Sparse data-flow analysis -------------===//
+//===- DeadCodeAnalysis.cpp - Dead code analysis --------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
@@ -6,22 +6,11 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "mlir/Analysis/SparseDataFlowAnalysis.h"
-
-#define DEBUG_TYPE "dataflow"
+#include "mlir/Analysis/DataFlow/DeadCodeAnalysis.h"
+#include "mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h"
 
 using namespace mlir;
-
-//===----------------------------------------------------------------------===//
-// AbstractSparseLattice
-//===----------------------------------------------------------------------===//
-
-void AbstractSparseLattice::onUpdate(DataFlowSolver *solver) const {
-  // Push all users of the value to the queue.
-  for (Operation *user : point.get<Value>().getUsers())
-    for (DataFlowAnalysis *analysis : useDefSubscribers)
-      solver->enqueue({user, analysis});
-}
+using namespace mlir::dataflow;
 
 //===----------------------------------------------------------------------===//
 // Executable
@@ -49,23 +38,14 @@ void Executable::onUpdate(DataFlowSolver *solver) const {
         solver->enqueue({&op, analysis});
   } else if (auto *programPoint = point.dyn_cast<GenericProgramPoint *>()) {
     // Re-invoke the analysis on the successor block.
-    if (auto *edge = dyn_cast<CFGEdge>(programPoint))
+    if (auto *edge = dyn_cast<CFGEdge>(programPoint)) {
       for (DataFlowAnalysis *analysis : subscribers)
         solver->enqueue({edge->getTo(), analysis});
+    }
   }
 }
 
 //===----------------------------------------------------------------------===//
-// ConstantValue
-//===----------------------------------------------------------------------===//
-
-void ConstantValue::print(raw_ostream &os) const {
-  if (constant)
-    return constant.print(os);
-  os << "<NO VALUE>";
-}
-
-//===----------------------------------------------------------------------===//
 // PredecessorState
 //===----------------------------------------------------------------------===//
 
@@ -350,7 +330,6 @@ void DeadCodeAnalysis::visitRegionBranchOperation(
 
   SmallVector<RegionSuccessor> successors;
   branch.getSuccessorRegions(/*index=*/{}, *operands, successors);
-
   for (const RegionSuccessor &successor : successors) {
     // Mark the entry block as executable.
     Region *region = successor.getSuccessor();
diff --git a/mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp b/mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp
new file mode 100644
index 000000000000..e2640280fffd
--- /dev/null
+++ b/mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp
@@ -0,0 +1,23 @@
+//===- SparseAnalysis.cpp - Sparse data-flow analysis ---------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "mlir/Analysis/DataFlow/SparseAnalysis.h"
+
+using namespace mlir;
+using namespace mlir::dataflow;
+
+//===----------------------------------------------------------------------===//
+// AbstractSparseLattice
+//===----------------------------------------------------------------------===//
+
+void AbstractSparseLattice::onUpdate(DataFlowSolver *solver) const {
+  // Push all users of the value to the queue.
+  for (Operation *user : point.get<Value>().getUsers())
+    for (DataFlowAnalysis *analysis : useDefSubscribers)
+      solver->enqueue({user, analysis});
+}
diff --git a/mlir/test/Analysis/test-dead-code-analysis.mlir b/mlir/test/Analysis/DataFlow/test-dead-code-analysis.mlir
index 2668b8349d1c..2668b8349d1c 100644
--- a/mlir/test/Analysis/test-dead-code-analysis.mlir
+++ b/mlir/test/Analysis/DataFlow/test-dead-code-analysis.mlir
diff --git a/mlir/test/lib/Analysis/CMakeLists.txt b/mlir/test/lib/Analysis/CMakeLists.txt
index 128615659cf3..8e9446c78bfc 100644
--- a/mlir/test/lib/Analysis/CMakeLists.txt
+++ b/mlir/test/lib/Analysis/CMakeLists.txt
@@ -4,7 +4,6 @@ add_mlir_library(MLIRTestAnalysis
   TestCallGraph.cpp
   TestDataFlow.cpp
   TestDataFlowFramework.cpp
-  TestDeadCodeAnalysis.cpp
   TestLiveness.cpp
   TestMatchReduction.cpp
   TestMemRefBoundCheck.cpp
@@ -12,6 +11,7 @@ add_mlir_library(MLIRTestAnalysis
   TestMemRefStrideCalculation.cpp
   TestSlice.cpp
 
+  DataFlow/TestDeadCodeAnalysis.cpp
 
   EXCLUDE_FROM_LIBMLIR
 
diff --git a/mlir/test/lib/Analysis/TestDeadCodeAnalysis.cpp b/mlir/test/lib/Analysis/DataFlow/TestDeadCodeAnalysis.cpp
index a7c33526c80d..8106c94d5736 100644
--- a/mlir/test/lib/Analysis/TestDeadCodeAnalysis.cpp
+++ b/mlir/test/lib/Analysis/DataFlow/TestDeadCodeAnalysis.cpp
@@ -6,11 +6,13 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "mlir/Analysis/SparseDataFlowAnalysis.h"
+#include "mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h"
+#include "mlir/Analysis/DataFlow/DeadCodeAnalysis.h"
 #include "mlir/IR/Matchers.h"
 #include "mlir/Pass/Pass.h"
 
 using namespace mlir;
+using namespace mlir::dataflow;
 
 /// Print the liveness of every block, control-flow edge, and the predecessors
 /// of all regions, callables, and calls.