MLIR  22.0.0git
DataFlowFramework.h
Go to the documentation of this file.
1 //===- DataFlowFramework.h - A generic framework for data-flow analysis ---===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines a generic framework for writing data-flow analysis in MLIR.
10 // The framework consists of a solver, which runs the fixed-point iteration and
11 // manages analysis dependencies, and a data-flow analysis class used to
12 // implement specific analyses.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef MLIR_ANALYSIS_DATAFLOWFRAMEWORK_H
17 #define MLIR_ANALYSIS_DATAFLOWFRAMEWORK_H
18 
19 #include "mlir/IR/Operation.h"
21 #include "llvm/ADT/EquivalenceClasses.h"
22 #include "llvm/ADT/Hashing.h"
23 #include "llvm/ADT/SetVector.h"
24 #include "llvm/Support/Compiler.h"
25 #include "llvm/Support/TypeName.h"
26 #include <queue>
27 #include <tuple>
28 
29 namespace mlir {
30 
31 //===----------------------------------------------------------------------===//
32 // ChangeResult
33 //===----------------------------------------------------------------------===//
34 
35 /// A result type used to indicate if a change happened. Boolean operations on
36 /// ChangeResult behave as though `Change` is truth.
37 enum class [[nodiscard]] ChangeResult {
38  NoChange,
39  Change,
40 };
42  return lhs == ChangeResult::Change ? lhs : rhs;
43 }
45  lhs = lhs | rhs;
46  return lhs;
47 }
49  return lhs == ChangeResult::NoChange ? lhs : rhs;
50 }
51 
52 /// Forward declare the analysis state class.
53 class AnalysisState;
54 
55 /// Program point represents a specific location in the execution of a program.
56 /// A sequence of program points can be combined into a control flow graph.
58  /// Creates a new program point at the given location.
60  : block(parentBlock), point(pp) {}
61 
62  /// Creates a new program point at the given operation.
63  ProgramPoint(Operation *op) : op(op) {}
64 
65  /// The concrete key type used by the storage uniquer. This class is uniqued
66  /// by its contents.
67  using KeyTy = std::tuple<Block *, Block::iterator, Operation *>;
68 
69  /// Create a empty program point.
71 
72  /// Create a new program point from the given program point.
73  ProgramPoint(const ProgramPoint &point) {
74  this->block = point.getBlock();
75  this->point = point.getPoint();
76  this->op = point.getOperation();
77  }
78 
80  KeyTy &&key) {
81  if (std::get<0>(key)) {
82  return new (alloc.allocate<ProgramPoint>())
83  ProgramPoint(std::get<0>(key), std::get<1>(key));
84  }
85  return new (alloc.allocate<ProgramPoint>()) ProgramPoint(std::get<2>(key));
86  }
87 
88  /// Returns true if this program point is set.
89  bool isNull() const { return block == nullptr && op == nullptr; }
90 
91  /// Two program points are equal if their block and iterator are equal.
92  bool operator==(const KeyTy &key) const {
93  return block == std::get<0>(key) && point == std::get<1>(key) &&
94  op == std::get<2>(key);
95  }
96 
97  bool operator==(const ProgramPoint &pp) const {
98  return block == pp.block && point == pp.point && op == pp.op;
99  }
100 
101  /// Get the block contains this program point.
102  Block *getBlock() const { return block; }
103 
104  /// Get the the iterator this program point refers to.
105  Block::iterator getPoint() const { return point; }
106 
107  /// Get the the iterator this program point refers to.
108  Operation *getOperation() const { return op; }
109 
110  /// Get the next operation of this program point.
111  Operation *getNextOp() const {
112  assert(!isBlockEnd());
113  // If the current program point has no parent block, both the next op and
114  // the previous op point to the op corresponding to the current program
115  // point.
116  if (block == nullptr) {
117  return op;
118  }
119  return &*point;
120  }
121 
122  /// Get the previous operation of this program point.
123  Operation *getPrevOp() const {
124  assert(!isBlockStart());
125  // If the current program point has no parent block, both the next op and
126  // the previous op point to the op corresponding to the current program
127  // point.
128  if (block == nullptr) {
129  return op;
130  }
131  return &*(--Block::iterator(point));
132  }
133 
134  bool isBlockStart() const { return block && block->begin() == point; }
135 
136  bool isBlockEnd() const { return block && block->end() == point; }
137 
138  /// Print the program point.
139  void print(raw_ostream &os) const;
140 
141 private:
142  Block *block = nullptr;
143  Block::iterator point;
144 
145  /// For operations without a parent block, we record the operation itself as
146  /// its program point.
147  Operation *op = nullptr;
148 };
149 
150 inline raw_ostream &operator<<(raw_ostream &os, const ProgramPoint &point) {
151  point.print(os);
152  return os;
153 }
154 
155 //===----------------------------------------------------------------------===//
156 // GenericLatticeAnchor
157 //===----------------------------------------------------------------------===//
158 
159 /// Abstract class for generic lattice anchor. In classical data-flow analysis,
160 /// lattice anchor represent positions in a program to which lattice elements
161 /// are attached. In sparse data-flow analysis, these can be SSA values, and in
162 /// dense data-flow analysis, these are the program points before and after
163 /// every operation.
164 ///
165 /// Lattice anchor are implemented using MLIR's storage uniquer framework and
166 /// type ID system to provide RTTI.
168 public:
170 
171  /// Get the abstract lattice anchor's type identifier.
172  TypeID getTypeID() const { return typeID; }
173 
174  /// Get a derived source location for the lattice anchor.
175  virtual Location getLoc() const = 0;
176 
177  /// Print the lattice anchor.
178  virtual void print(raw_ostream &os) const = 0;
179 
180 protected:
181  /// Create an abstract lattice anchor with type identifier.
182  explicit GenericLatticeAnchor(TypeID typeID) : typeID(typeID) {}
183 
184 private:
185  /// The type identifier of the lattice anchor.
186  TypeID typeID;
187 };
188 
189 //===----------------------------------------------------------------------===//
190 // GenericLatticeAnchorBase
191 //===----------------------------------------------------------------------===//
192 
193 /// Base class for generic lattice anchor based on a concrete lattice anchor
194 /// type and a content key. This class defines the common methods required for
195 /// operability with the storage uniquer framework.
196 ///
197 /// The provided key type uniquely identifies the concrete lattice anchor
198 /// instance and are the data members of the class.
199 template <typename ConcreteT, typename Value>
201 public:
202  /// The concrete key type used by the storage uniquer. This class is uniqued
203  /// by its contents.
204  using KeyTy = Value;
205  /// Alias for the base class.
207 
208  /// Construct an instance of the lattice anchor using the provided value and
209  /// the type ID of the concrete type.
210  template <typename ValueT>
211  explicit GenericLatticeAnchorBase(ValueT &&value)
212  : GenericLatticeAnchor(TypeID::get<ConcreteT>()),
213  value(std::forward<ValueT>(value)) {}
214 
215  /// Get a uniqued instance of this lattice anchor class with the given
216  /// arguments.
217  template <typename... Args>
218  static ConcreteT *get(StorageUniquer &uniquer, Args &&...args) {
219  return uniquer.get<ConcreteT>(/*initFn=*/{}, std::forward<Args>(args)...);
220  }
221 
222  /// Allocate space for a lattice anchor and construct it in-place.
223  template <typename ValueT>
224  static ConcreteT *construct(StorageUniquer::StorageAllocator &alloc,
225  ValueT &&value) {
226  return new (alloc.allocate<ConcreteT>())
227  ConcreteT(std::forward<ValueT>(value));
228  }
229 
230  /// Two lattice anchors are equal if their values are equal.
231  bool operator==(const Value &value) const { return this->value == value; }
232 
233  /// Provide LLVM-style RTTI using type IDs.
234  static bool classof(const GenericLatticeAnchor *point) {
235  return point->getTypeID() == TypeID::get<ConcreteT>();
236  }
237 
238  /// Get the contents of the lattice anchor.
239  const Value &getValue() const { return value; }
240 
241 private:
242  /// The lattice anchor value.
243  Value value;
244 };
245 
246 //===----------------------------------------------------------------------===//
247 // LatticeAnchor
248 //===----------------------------------------------------------------------===//
249 
250 /// Fundamental IR components are supported as first-class lattice anchor.
252  : public PointerUnion<GenericLatticeAnchor *, ProgramPoint *, Value> {
254  /// Inherit constructors.
255  using ParentTy::PointerUnion;
256  /// Allow implicit conversion from the parent type.
257  LatticeAnchor(ParentTy point = nullptr) : ParentTy(point) {}
258 
259  /// Print the lattice anchor.
260  void print(raw_ostream &os) const;
261 
262  /// Get the source location of the lattice anchor.
263  Location getLoc() const;
264 };
265 
266 /// Forward declaration of the data-flow analysis class.
267 class DataFlowAnalysis;
268 
269 } // namespace mlir
270 
271 template <>
272 struct llvm::DenseMapInfo<mlir::LatticeAnchor>
273  : public llvm::DenseMapInfo<mlir::LatticeAnchor::ParentTy> {};
274 
275 namespace mlir {
276 
277 //===----------------------------------------------------------------------===//
278 // DataFlowConfig
279 //===----------------------------------------------------------------------===//
280 
281 /// Configuration class for data flow solver and child analyses. Follows the
282 /// fluent API pattern.
284 public:
285  DataFlowConfig() = default;
286 
287  /// Set whether the solver should operate interpocedurally, i.e. enter the
288  /// callee body when available. Interprocedural analyses may be more precise,
289  /// but also more expensive as more states need to be computed and the
290  /// fixpoint convergence takes longer.
292  interprocedural = enable;
293  return *this;
294  }
295 
296  /// Return `true` if the solver operates interprocedurally, `false` otherwise.
297  bool isInterprocedural() const { return interprocedural; }
298 
299 private:
300  bool interprocedural = true;
301 };
302 
303 //===----------------------------------------------------------------------===//
304 // DataFlowSolver
305 //===----------------------------------------------------------------------===//
306 
307 /// The general data-flow analysis solver. This class is responsible for
308 /// orchestrating child data-flow analyses, running the fixed-point iteration
309 /// algorithm, managing analysis state and lattice anchor memory, and tracking
310 /// dependencies between analyses, lattice anchor, and analysis states.
311 ///
312 /// Steps to run a data-flow analysis:
313 ///
314 /// 1. Load and initialize children analyses. Children analyses are instantiated
315 /// in the solver and initialized, building their dependency relations.
316 /// 2. Configure and run the analysis. The solver invokes the children analyses
317 /// according to their dependency relations until a fixed point is reached.
318 /// 3. Query analysis state results from the solver.
319 ///
320 /// Steps to re-run a data-flow analysis when IR changes:
321 /// 1. Erase all analysis states as they are no longer valid.
322 /// 2. Re-run the analysis using `initializeAndRun`.
323 ///
324 /// TODO: Optimize the internal implementation of the solver.
326 public:
327  explicit DataFlowSolver(const DataFlowConfig &config = DataFlowConfig())
328  : config(config) {
330  }
331 
332  /// Load an analysis into the solver. Return the analysis instance.
333  template <typename AnalysisT, typename... Args>
334  AnalysisT *load(Args &&...args);
335 
336  /// Initialize the children analyses starting from the provided top-level
337  /// operation and run the analysis until fixpoint.
338  LogicalResult initializeAndRun(Operation *top);
339 
340  /// Lookup an analysis state for the given lattice anchor. Returns null if one
341  /// does not exist.
342  template <typename StateT, typename AnchorT>
343  const StateT *lookupState(AnchorT anchor) const {
344  LatticeAnchor latticeAnchor =
345  getLeaderAnchorOrSelf<StateT>(LatticeAnchor(anchor));
346  const auto &mapIt = analysisStates.find(latticeAnchor);
347  if (mapIt == analysisStates.end())
348  return nullptr;
349  auto it = mapIt->second.find(TypeID::get<StateT>());
350  if (it == mapIt->second.end())
351  return nullptr;
352  return static_cast<const StateT *>(it->second.get());
353  }
354 
355  /// Erase any analysis state associated with the given lattice anchor.
356  template <typename AnchorT>
357  void eraseState(AnchorT anchor);
358 
359  /// Erase all analysis states.
360  void eraseAllStates() {
361  analysisStates.clear();
362  equivalentAnchorMap.clear();
363  }
364 
365  /// Get a uniqued lattice anchor instance. If one is not present, it is
366  /// created with the provided arguments.
367  template <typename AnchorT, typename... Args>
368  AnchorT *getLatticeAnchor(Args &&...args) {
369  return AnchorT::get(uniquer, std::forward<Args>(args)...);
370  }
371 
372  /// Get a uniqued program point instance.
374  if (op->getBlock())
375  return uniquer.get<ProgramPoint>(/*initFn*/ {}, op->getBlock(),
376  Block::iterator(op), nullptr);
377  else
378  return uniquer.get<ProgramPoint>(/*initFn*/ {}, nullptr,
379  Block::iterator(), op);
380  }
381 
383  return uniquer.get<ProgramPoint>(/*initFn*/ {}, block, block->begin(),
384  nullptr);
385  }
386 
388  if (op->getBlock())
389  return uniquer.get<ProgramPoint>(/*initFn*/ {}, op->getBlock(),
390  ++Block::iterator(op), nullptr);
391  else
392  return uniquer.get<ProgramPoint>(/*initFn*/ {}, nullptr,
393  Block::iterator(), op);
394  }
395 
397  return uniquer.get<ProgramPoint>(/*initFn*/ {}, block, block->end(),
398  nullptr);
399  }
400 
401  /// A work item on the solver queue is a program point, child analysis pair.
402  /// Each item is processed by invoking the child analysis at the program
403  /// point.
404  using WorkItem = std::pair<ProgramPoint *, DataFlowAnalysis *>;
405  /// Push a work item onto the worklist.
406  void enqueue(WorkItem item) { worklist.push(std::move(item)); }
407 
408  /// Get the state associated with the given lattice anchor. If it does not
409  /// exist, create an uninitialized state.
410  template <typename StateT, typename AnchorT>
411  StateT *getOrCreateState(AnchorT anchor);
412 
413  /// Get leader lattice anchor in equivalence lattice anchor group, return
414  /// input lattice anchor if input not found in equivalece lattice anchor
415  /// group.
416  template <typename StateT>
418 
419  /// Union input anchors under the given state.
420  template <typename StateT, typename AnchorT>
421  void unionLatticeAnchors(AnchorT anchor, AnchorT other);
422 
423  /// Return given lattice is equivalent on given state.
424  template <typename StateT>
425  bool isEquivalent(LatticeAnchor lhs, LatticeAnchor rhs) const;
426 
427  /// Propagate an update to an analysis state if it changed by pushing
428  /// dependent work items to the back of the queue.
429  /// This should only be used when DataFlowSolver is running.
430  /// Otherwise, the solver won't process the work items.
432 
433  /// Get the configuration of the solver.
434  const DataFlowConfig &getConfig() const { return config; }
435 
436 private:
437  /// Configuration of the dataflow solver.
438  DataFlowConfig config;
439 
440  /// The solver is working on the worklist.
441  bool isRunning = false;
442 
443  /// The solver's work queue. Work items can be inserted to the front of the
444  /// queue to be processed greedily, speeding up computations that otherwise
445  /// quickly degenerate to quadratic due to propagation of state updates.
446  std::queue<WorkItem> worklist;
447 
448  /// Type-erased instances of the children analyses.
450 
451  /// The storage uniquer instance that owns the memory of the allocated lattice
452  /// anchors
453  StorageUniquer uniquer;
454 
455  /// A type-erased map of lattice anchors to associated analysis states for
456  /// first-class lattice anchors.
458  analysisStates;
459 
460  /// A map of Ananlysis state type to the equivalent lattice anchors.
461  /// Lattice anchors are considered equivalent under a certain analysis state
462  /// type if and only if, the analysis states pointed to by these lattice
463  /// anchors necessarily contain identical value.
465 
466  /// Allow the base child analysis class to access the internals of the solver.
467  friend class DataFlowAnalysis;
468 };
469 
470 //===----------------------------------------------------------------------===//
471 // AnalysisState
472 //===----------------------------------------------------------------------===//
473 
474 /// Base class for generic analysis states. Analysis states contain data-flow
475 /// information that are attached to lattice anchors and which evolve as the
476 /// analysis iterates.
477 ///
478 /// This class places no restrictions on the semantics of analysis states beyond
479 /// these requirements.
480 ///
481 /// 1. Querying the state of a lattice anchor prior to visiting that anchor
482 /// results in uninitialized state. Analyses must be aware of unintialized
483 /// states.
484 /// 2. Analysis states can reach fixpoints, where subsequent updates will never
485 /// trigger a change in the state.
486 /// 3. Analysis states that are uninitialized can be forcefully initialized to a
487 /// default value.
489 public:
490  virtual ~AnalysisState();
491 
492  /// Create the analysis state on the given lattice anchor.
494 
495  /// Returns the lattice anchor this state is located at.
496  LatticeAnchor getAnchor() const { return anchor; }
497 
498  /// Print the contents of the analysis state.
499  virtual void print(raw_ostream &os) const = 0;
500  LLVM_DUMP_METHOD void dump() const;
501 
502  /// Add a dependency to this analysis state on a lattice anchor and an
503  /// analysis. If this state is updated, the analysis will be invoked on the
504  /// given lattice anchor again (in onUpdate()).
506 
507 protected:
508  /// This function is called by the solver when the analysis state is updated
509  /// to enqueue more work items. For example, if a state tracks dependents
510  /// through the IR (e.g. use-def chains), this function can be implemented to
511  /// push those dependents on the worklist.
512  virtual void onUpdate(DataFlowSolver *solver) const {
513  for (const DataFlowSolver::WorkItem &item : dependents)
514  solver->enqueue(item);
515  }
516 
517  /// The lattice anchor to which the state belongs.
519 
520 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
521  /// When compiling with debugging, keep a name for the analysis state.
522  StringRef debugName;
523 #endif // LLVM_ENABLE_ABI_BREAKING_CHECKS
524 
525 private:
526  /// The dependency relations originating from this analysis state. An entry
527  /// `state -> (analysis, anchor)` is created when `analysis` queries `state`
528  /// when updating `anchor`.
529  ///
530  /// When this state is updated, all dependent child analysis invocations are
531  /// pushed to the back of the queue. Use a `SetVector` to keep the analysis
532  /// deterministic.
533  ///
534  /// Store the dependents on the analysis state for efficiency.
536 
537  /// Allow the framework to access the dependents.
538  friend class DataFlowSolver;
539 };
540 
541 //===----------------------------------------------------------------------===//
542 // DataFlowSolver definition
543 //===----------------------------------------------------------------------===//
544 // This method is defined outside `DataFlowSolver` and after `AnalysisState`
545 // to prevent issues around `AnalysisState` being used before it is defined.
546 template <typename AnchorT>
547 void DataFlowSolver::eraseState(AnchorT anchor) {
548  LatticeAnchor latticeAnchor(anchor);
549 
550  // Update equivalentAnchorMap.
551  for (auto &&[TypeId, eqClass] : equivalentAnchorMap) {
552  if (!eqClass.contains(latticeAnchor)) {
553  continue;
554  }
555  llvm::EquivalenceClasses<LatticeAnchor>::member_iterator leaderIt =
556  eqClass.findLeader(latticeAnchor);
557 
558  // Update analysis states with new leader if needed.
559  if (*leaderIt == latticeAnchor && ++leaderIt != eqClass.member_end()) {
560  analysisStates[*leaderIt][TypeId] =
561  std::move(analysisStates[latticeAnchor][TypeId]);
562  }
563 
564  eqClass.erase(latticeAnchor);
565  }
566 
567  // Update analysis states.
568  analysisStates.erase(latticeAnchor);
569 }
570 
571 //===----------------------------------------------------------------------===//
572 // DataFlowAnalysis
573 //===----------------------------------------------------------------------===//
574 
575 /// Base class for all data-flow analyses. A child analysis is expected to build
576 /// an initial dependency graph (and optionally provide an initial state) when
577 /// initialized and define transfer functions when visiting program points.
578 ///
579 /// In classical data-flow analysis, the dependency graph is fixed and analyses
580 /// define explicit transfer functions between input states and output states.
581 /// In this framework, however, the dependency graph can change during the
582 /// analysis, and transfer functions are opaque such that the solver doesn't
583 /// know what states calling `visit` on an analysis will be updated. This allows
584 /// multiple analyses to plug in and provide values for the same state.
585 ///
586 /// Generally, when an analysis queries an uninitialized state, it is expected
587 /// to "bail out", i.e., not provide any updates. When the value is initialized,
588 /// the solver will re-invoke the analysis. If the solver exhausts its worklist,
589 /// however, and there are still uninitialized states, the solver "nudges" the
590 /// analyses by default-initializing those states.
592 public:
593  virtual ~DataFlowAnalysis();
594 
595  /// Create an analysis with a reference to the parent solver.
596  explicit DataFlowAnalysis(DataFlowSolver &solver);
597 
598  /// Initialize the analysis from the provided top-level operation by building
599  /// an initial dependency graph between all lattice anchors of interest. This
600  /// can be implemented by calling `visit` on all program points of interest
601  /// below the top-level operation.
602  ///
603  /// An analysis can optionally provide initial values to certain analysis
604  /// states to influence the evolution of the analysis.
605  virtual LogicalResult initialize(Operation *top) = 0;
606 
607  /// Visit the given program point. This function is invoked by the solver on
608  /// this analysis with a given program point when a dependent analysis state
609  /// is updated. The function is similar to a transfer function; it queries
610  /// certain analysis states and sets other states.
611  ///
612  /// The function is expected to create dependencies on queried states and
613  /// propagate updates on changed states. A dependency can be created by
614  /// calling `addDependency` between the input state and a program point,
615  /// indicating that, if the state is updated, the solver should invoke `solve`
616  /// on the program point. The dependent point does not have to be the same as
617  /// the provided point. An update to a state is propagated by calling
618  /// `propagateIfChange` on the state. If the state has changed, then all its
619  /// dependents are placed on the worklist.
620  ///
621  /// The dependency graph does not need to be static. Each invocation of
622  /// `visit` can add new dependencies, but these dependencies will not be
623  /// dynamically added to the worklist because the solver doesn't know what
624  /// will provide a value for then.
625  virtual LogicalResult visit(ProgramPoint *point) = 0;
626 
627  /// Initialize lattice anchor equivalence class from the provided top-level
628  /// operation.
629  ///
630  /// This function will union lattice anchor to same equivalent class if the
631  /// analysis can determine the lattice content of lattice anchor is
632  /// necessarily identical under the corrensponding lattice type.
634 
635 protected:
636  /// Create a dependency between the given analysis state and lattice anchor
637  /// on this analysis.
638  void addDependency(AnalysisState *state, ProgramPoint *point);
639 
640  /// Propagate an update to a state if it changed.
642 
643  /// Register a custom lattice anchor class.
644  template <typename AnchorT>
646  solver.uniquer.registerParametricStorageType<AnchorT>();
647  }
648 
649  /// Get or create a custom lattice anchor.
650  template <typename AnchorT, typename... Args>
651  AnchorT *getLatticeAnchor(Args &&...args) {
652  return solver.getLatticeAnchor<AnchorT>(std::forward<Args>(args)...);
653  }
654 
655  /// Union input anchors under the given state.
656  template <typename StateT, typename AnchorT>
657  void unionLatticeAnchors(AnchorT anchor, AnchorT other) {
658  return solver.unionLatticeAnchors<StateT>(anchor, other);
659  }
660 
661  /// Get the analysis state associated with the lattice anchor. The returned
662  /// state is expected to be "write-only", and any updates need to be
663  /// propagated by `propagateIfChanged`.
664  template <typename StateT, typename AnchorT>
665  StateT *getOrCreate(AnchorT anchor) {
666  return solver.getOrCreateState<StateT>(anchor);
667  }
668 
669  /// Get a read-only analysis state for the given point and create a dependency
670  /// on `dependent`. If the return state is updated elsewhere, this analysis is
671  /// re-invoked on the dependent.
672  template <typename StateT, typename AnchorT>
673  const StateT *getOrCreateFor(ProgramPoint *dependent, AnchorT anchor) {
674  StateT *state = getOrCreate<StateT>(anchor);
675  if (!solver.isEquivalent<StateT>(LatticeAnchor(anchor),
676  LatticeAnchor(dependent)))
677  addDependency(state, dependent);
678  return state;
679  }
680 
681  /// Get a uniqued program point instance.
683  return solver.getProgramPointBefore(op);
684  }
685 
687  return solver.getProgramPointBefore(block);
688  }
689 
691  return solver.getProgramPointAfter(op);
692  }
693 
695  return solver.getProgramPointAfter(block);
696  }
697 
698  /// Return the configuration of the solver used for this analysis.
699  const DataFlowConfig &getSolverConfig() const { return solver.getConfig(); }
700 
701 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
702  /// When compiling with debugging, keep a name for the analyis.
703  StringRef debugName;
704 #endif // LLVM_ENABLE_ABI_BREAKING_CHECKS
705 
706 private:
707  /// The parent data-flow solver.
708  DataFlowSolver &solver;
709 
710  /// Allow the data-flow solver to access the internals of this class.
711  friend class DataFlowSolver;
712 };
713 
714 template <typename AnalysisT, typename... Args>
715 AnalysisT *DataFlowSolver::load(Args &&...args) {
716  childAnalyses.emplace_back(new AnalysisT(*this, std::forward<Args>(args)...));
717 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
718  childAnalyses.back()->debugName = llvm::getTypeName<AnalysisT>();
719 #endif // LLVM_ENABLE_ABI_BREAKING_CHECKS
720  return static_cast<AnalysisT *>(childAnalyses.back().get());
721 }
722 
723 template <typename StateT>
726  if (!equivalentAnchorMap.contains(TypeID::get<StateT>())) {
727  return latticeAnchor;
728  }
729  const llvm::EquivalenceClasses<LatticeAnchor> &eqClass =
730  equivalentAnchorMap.at(TypeID::get<StateT>());
731  llvm::EquivalenceClasses<LatticeAnchor>::member_iterator leaderIt =
732  eqClass.findLeader(latticeAnchor);
733  if (leaderIt != eqClass.member_end()) {
734  return *leaderIt;
735  }
736  return latticeAnchor;
737 }
738 
739 template <typename StateT, typename AnchorT>
740 StateT *DataFlowSolver::getOrCreateState(AnchorT anchor) {
741  // Replace to leader anchor if found.
742  LatticeAnchor latticeAnchor(anchor);
743  latticeAnchor = getLeaderAnchorOrSelf<StateT>(latticeAnchor);
744  std::unique_ptr<AnalysisState> &state =
745  analysisStates[latticeAnchor][TypeID::get<StateT>()];
746  if (!state) {
747  state = std::unique_ptr<StateT>(new StateT(anchor));
748 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
749  state->debugName = llvm::getTypeName<StateT>();
750 #endif // LLVM_ENABLE_ABI_BREAKING_CHECKS
751  }
752  return static_cast<StateT *>(state.get());
753 }
754 
755 template <typename StateT>
757  if (!equivalentAnchorMap.contains(TypeID::get<StateT>())) {
758  return false;
759  }
760  const llvm::EquivalenceClasses<LatticeAnchor> &eqClass =
761  equivalentAnchorMap.at(TypeID::get<StateT>());
762  if (!eqClass.contains(lhs) || !eqClass.contains(rhs))
763  return false;
764  return eqClass.isEquivalent(lhs, rhs);
765 }
766 
767 template <typename StateT, typename AnchorT>
768 void DataFlowSolver::unionLatticeAnchors(AnchorT anchor, AnchorT other) {
769  llvm::EquivalenceClasses<LatticeAnchor> &eqClass =
770  equivalentAnchorMap[TypeID::get<StateT>()];
771  eqClass.unionSets(LatticeAnchor(anchor), LatticeAnchor(other));
772 }
773 
774 inline raw_ostream &operator<<(raw_ostream &os, const AnalysisState &state) {
775  state.print(os);
776  return os;
777 }
778 
779 inline raw_ostream &operator<<(raw_ostream &os, const LatticeAnchor &anchor) {
780  anchor.print(os);
781  return os;
782 }
783 
784 } // end namespace mlir
785 
786 namespace llvm {
787 /// Allow hashing of lattice anchors and program points.
788 template <>
789 struct DenseMapInfo<mlir::ProgramPoint> {
791  void *pointer = llvm::DenseMapInfo<void *>::getEmptyKey();
792  return mlir::ProgramPoint(
793  (mlir::Block *)pointer,
795  }
798  return mlir::ProgramPoint(
799  (mlir::Block *)pointer,
801  }
802  static unsigned getHashValue(mlir::ProgramPoint pp) {
803  return hash_combine(pp.getBlock(), pp.getPoint().getNodePtr());
804  }
806  return lhs == rhs;
807  }
808 };
809 
810 // Allow llvm::cast style functions.
811 template <typename To>
812 struct CastInfo<To, mlir::LatticeAnchor>
813  : public CastInfo<To, mlir::LatticeAnchor::PointerUnion> {};
814 
815 template <typename To>
816 struct CastInfo<To, const mlir::LatticeAnchor>
817  : public CastInfo<To, const mlir::LatticeAnchor::PointerUnion> {};
818 
819 } // end namespace llvm
820 
821 #endif // MLIR_ANALYSIS_DATAFLOWFRAMEWORK_H
Base class for generic analysis states.
AnalysisState(LatticeAnchor anchor)
Create the analysis state on the given lattice anchor.
LLVM_DUMP_METHOD void dump() const
LatticeAnchor getAnchor() const
Returns the lattice anchor this state is located at.
void addDependency(ProgramPoint *point, DataFlowAnalysis *analysis)
Add a dependency to this analysis state on a lattice anchor and an analysis.
virtual void print(raw_ostream &os) const =0
Print the contents of the analysis state.
virtual void onUpdate(DataFlowSolver *solver) const
This function is called by the solver when the analysis state is updated to enqueue more work items.
virtual ~AnalysisState()
LatticeAnchor anchor
The lattice anchor to which the state belongs.
Block represents an ordered list of Operations.
Definition: Block.h:33
OpListType::iterator iterator
Definition: Block.h:140
iterator end()
Definition: Block.h:144
iterator begin()
Definition: Block.h:143
Base class for all data-flow analyses.
void addDependency(AnalysisState *state, ProgramPoint *point)
Create a dependency between the given analysis state and lattice anchor on this analysis.
void unionLatticeAnchors(AnchorT anchor, AnchorT other)
Union input anchors under the given state.
void propagateIfChanged(AnalysisState *state, ChangeResult changed)
Propagate an update to a state if it changed.
const StateT * getOrCreateFor(ProgramPoint *dependent, AnchorT anchor)
Get a read-only analysis state for the given point and create a dependency on dependent.
ProgramPoint * getProgramPointAfter(Operation *op)
ProgramPoint * getProgramPointBefore(Operation *op)
Get a uniqued program point instance.
virtual void initializeEquivalentLatticeAnchor(Operation *top)
Initialize lattice anchor equivalence class from the provided top-level operation.
AnchorT * getLatticeAnchor(Args &&...args)
Get or create a custom lattice anchor.
StateT * getOrCreate(AnchorT anchor)
Get the analysis state associated with the lattice anchor.
const DataFlowConfig & getSolverConfig() const
Return the configuration of the solver used for this analysis.
ProgramPoint * getProgramPointAfter(Block *block)
DataFlowAnalysis(DataFlowSolver &solver)
Create an analysis with a reference to the parent solver.
virtual LogicalResult initialize(Operation *top)=0
Initialize the analysis from the provided top-level operation by building an initial dependency graph...
ProgramPoint * getProgramPointBefore(Block *block)
virtual LogicalResult visit(ProgramPoint *point)=0
Visit the given program point.
void registerAnchorKind()
Register a custom lattice anchor class.
Configuration class for data flow solver and child analyses.
DataFlowConfig()=default
DataFlowConfig & setInterprocedural(bool enable)
Set whether the solver should operate interpocedurally, i.e.
bool isInterprocedural() const
Return true if the solver operates interprocedurally, false otherwise.
The general data-flow analysis solver.
void unionLatticeAnchors(AnchorT anchor, AnchorT other)
Union input anchors under the given state.
void enqueue(WorkItem item)
Push a work item onto the worklist.
bool isEquivalent(LatticeAnchor lhs, LatticeAnchor rhs) const
Return given lattice is equivalent on given state.
void eraseState(AnchorT anchor)
Erase any analysis state associated with the given lattice anchor.
void propagateIfChanged(AnalysisState *state, ChangeResult changed)
Propagate an update to an analysis state if it changed by pushing dependent work items to the back of...
const StateT * lookupState(AnchorT anchor) const
Lookup an analysis state for the given lattice anchor.
ProgramPoint * getProgramPointAfter(Operation *op)
const DataFlowConfig & getConfig() const
Get the configuration of the solver.
ProgramPoint * getProgramPointBefore(Operation *op)
Get a uniqued program point instance.
void eraseAllStates()
Erase all analysis states.
AnchorT * getLatticeAnchor(Args &&...args)
Get a uniqued lattice anchor instance.
ProgramPoint * getProgramPointBefore(Block *block)
StateT * getOrCreateState(AnchorT anchor)
Get the state associated with the given lattice anchor.
LatticeAnchor getLeaderAnchorOrSelf(LatticeAnchor latticeAnchor) const
Get leader lattice anchor in equivalence lattice anchor group, return input lattice anchor if input n...
ProgramPoint * getProgramPointAfter(Block *block)
AnalysisT * load(Args &&...args)
Load an analysis into the solver. Return the analysis instance.
LogicalResult initializeAndRun(Operation *top)
Initialize the children analyses starting from the provided top-level operation and run the analysis ...
DataFlowSolver(const DataFlowConfig &config=DataFlowConfig())
std::pair< ProgramPoint *, DataFlowAnalysis * > WorkItem
A work item on the solver queue is a program point, child analysis pair.
Base class for generic lattice anchor based on a concrete lattice anchor type and a content key.
bool operator==(const Value &value) const
Two lattice anchors are equal if their values are equal.
static ConcreteT * construct(StorageUniquer::StorageAllocator &alloc, ValueT &&value)
Allocate space for a lattice anchor and construct it in-place.
static bool classof(const GenericLatticeAnchor *point)
Provide LLVM-style RTTI using type IDs.
GenericLatticeAnchorBase(ValueT &&value)
Construct an instance of the lattice anchor using the provided value and the type ID of the concrete ...
const Value & getValue() const
Get the contents of the lattice anchor.
static ConcreteT * get(StorageUniquer &uniquer, Args &&...args)
Get a uniqued instance of this lattice anchor class with the given arguments.
Abstract class for generic lattice anchor.
virtual void print(raw_ostream &os) const =0
Print the lattice anchor.
TypeID getTypeID() const
Get the abstract lattice anchor's type identifier.
virtual Location getLoc() const =0
Get a derived source location for the lattice anchor.
GenericLatticeAnchor(TypeID typeID)
Create an abstract lattice anchor with type identifier.
This class defines the main interface for locations in MLIR and acts as a non-nullable wrapper around...
Definition: Location.h:76
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
Block * getBlock()
Returns the operation block that contains this operation.
Definition: Operation.h:213
This class acts as the base storage that all storage classes must derived from.
This is a utility allocator used to allocate memory for instances of derived types.
T * allocate()
Allocate an instance of the provided type.
A utility class to get or create instances of "storage classes".
Storage * get(function_ref< void(Storage *)> initFn, TypeID id, Args &&...args)
Gets a uniqued instance of 'Storage'.
void registerParametricStorageType(TypeID id)
Register a new parametric storage class, this is necessary to create instances of this class type.
This class provides an efficient unique identifier for a specific C++ type.
Definition: TypeID.h:107
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
The OpAsmOpInterface, see OpAsmInterface.td for more details.
Definition: CallGraph.h:229
detail::InFlightRemark analysis(Location loc, RemarkOpts opts)
Report an optimization analysis remark.
Definition: Remarks.h:497
Include the generated interface declarations.
ChangeResult & operator|=(ChangeResult &lhs, ChangeResult rhs)
const FrozenRewritePatternSet GreedyRewriteConfig bool * changed
ChangeResult
A result type used to indicate if a change happened.
ChangeResult operator&(ChangeResult lhs, ChangeResult rhs)
ChangeResult operator|(ChangeResult lhs, ChangeResult rhs)
auto get(MLIRContext *context, Ts &&...params)
Helper method that injects context only if needed, this helps unify some of the attribute constructio...
raw_ostream & operator<<(raw_ostream &os, const AliasResult &result)
Definition: AliasAnalysis.h:78
static unsigned getHashValue(mlir::ProgramPoint pp)
static mlir::ProgramPoint getEmptyKey()
static mlir::ProgramPoint getTombstoneKey()
static bool isEqual(mlir::ProgramPoint lhs, mlir::ProgramPoint rhs)
Fundamental IR components are supported as first-class lattice anchor.
LatticeAnchor(ParentTy point=nullptr)
Allow implicit conversion from the parent type.
Location getLoc() const
Get the source location of the lattice anchor.
void print(raw_ostream &os) const
Print the lattice anchor.
Program point represents a specific location in the execution of a program.
bool isNull() const
Returns true if this program point is set.
bool isBlockStart() const
ProgramPoint(Block *parentBlock, Block::iterator pp)
Creates a new program point at the given location.
Block::iterator getPoint() const
Get the the iterator this program point refers to.
ProgramPoint()
Create a empty program point.
Operation * getOperation() const
Get the the iterator this program point refers to.
Operation * getPrevOp() const
Get the previous operation of this program point.
static ProgramPoint * construct(StorageUniquer::StorageAllocator &alloc, KeyTy &&key)
bool operator==(const ProgramPoint &pp) const
bool operator==(const KeyTy &key) const
Two program points are equal if their block and iterator are equal.
ProgramPoint(const ProgramPoint &point)
Create a new program point from the given program point.
std::tuple< Block *, Block::iterator, Operation * > KeyTy
The concrete key type used by the storage uniquer.
void print(raw_ostream &os) const
Print the program point.
Operation * getNextOp() const
Get the next operation of this program point.
Block * getBlock() const
Get the block contains this program point.
ProgramPoint(Operation *op)
Creates a new program point at the given operation.