176 lines · cpp
1//===- DataFlowFramework.cpp - 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-exception6//7//===----------------------------------------------------------------------===//8 9#include "mlir/Analysis/DataFlowFramework.h"10#include "mlir/IR/Location.h"11#include "mlir/IR/Operation.h"12#include "mlir/IR/SymbolTable.h"13#include "mlir/IR/Value.h"14#include "llvm/ADT/ScopeExit.h"15#include "llvm/ADT/iterator.h"16#include "llvm/Config/abi-breaking.h"17#include "llvm/Support/Casting.h"18#include "llvm/Support/DebugLog.h"19#include "llvm/Support/raw_ostream.h"20 21#define DEBUG_TYPE "dataflow"22#if LLVM_ENABLE_ABI_BREAKING_CHECKS23#define DATAFLOW_DEBUG(X) LLVM_DEBUG(X)24#else25#define DATAFLOW_DEBUG(X)26#endif // LLVM_ENABLE_ABI_BREAKING_CHECKS27 28using namespace mlir;29 30//===----------------------------------------------------------------------===//31// GenericLatticeAnchor32//===----------------------------------------------------------------------===//33 34GenericLatticeAnchor::~GenericLatticeAnchor() = default;35 36//===----------------------------------------------------------------------===//37// AnalysisState38//===----------------------------------------------------------------------===//39 40AnalysisState::~AnalysisState() = default;41 42void AnalysisState::addDependency(ProgramPoint *dependent,43 DataFlowAnalysis *analysis) {44 auto inserted = dependents.insert({dependent, analysis});45 (void)inserted;46 DATAFLOW_DEBUG({47 if (inserted) {48 LDBG() << "Creating dependency between " << debugName << " of " << anchor49 << "\nand " << debugName << " on " << *dependent;50 }51 });52}53 54void AnalysisState::dump() const { print(llvm::errs()); }55 56//===----------------------------------------------------------------------===//57// ProgramPoint58//===----------------------------------------------------------------------===//59 60void ProgramPoint::print(raw_ostream &os) const {61 if (isNull()) {62 os << "<NULL POINT>";63 return;64 }65 if (!isBlockStart()) {66 os << "<after operation>:"67 << OpWithFlags(getPrevOp(), OpPrintingFlags().skipRegions());68 return;69 }70 os << "<before operation>:"71 << OpWithFlags(getNextOp(), OpPrintingFlags().skipRegions());72}73 74//===----------------------------------------------------------------------===//75// LatticeAnchor76//===----------------------------------------------------------------------===//77 78void LatticeAnchor::print(raw_ostream &os) const {79 if (isNull()) {80 os << "<NULL POINT>";81 return;82 }83 if (auto *latticeAnchor = llvm::dyn_cast<GenericLatticeAnchor *>(*this))84 return latticeAnchor->print(os);85 if (auto value = llvm::dyn_cast<Value>(*this)) {86 return value.print(os, OpPrintingFlags().skipRegions());87 }88 89 return llvm::cast<ProgramPoint *>(*this)->print(os);90}91 92Location LatticeAnchor::getLoc() const {93 if (auto *latticeAnchor = llvm::dyn_cast<GenericLatticeAnchor *>(*this))94 return latticeAnchor->getLoc();95 if (auto value = llvm::dyn_cast<Value>(*this))96 return value.getLoc();97 98 ProgramPoint *pp = llvm::cast<ProgramPoint *>(*this);99 if (!pp->isBlockStart())100 return pp->getPrevOp()->getLoc();101 return pp->getBlock()->getParent()->getLoc();102}103 104//===----------------------------------------------------------------------===//105// DataFlowSolver106//===----------------------------------------------------------------------===//107 108LogicalResult DataFlowSolver::initializeAndRun(Operation *top) {109 // Enable enqueue to the worklist.110 isRunning = true;111 auto guard = llvm::make_scope_exit([&]() { isRunning = false; });112 113 bool isInterprocedural = config.isInterprocedural();114 auto restoreInterprocedural = llvm::make_scope_exit(115 [&]() { config.setInterprocedural(isInterprocedural); });116 if (isInterprocedural && !top->hasTrait<OpTrait::SymbolTable>())117 config.setInterprocedural(false);118 119 // Initialize equivalent lattice anchors.120 for (DataFlowAnalysis &analysis : llvm::make_pointee_range(childAnalyses)) {121 analysis.initializeEquivalentLatticeAnchor(top);122 }123 124 // Initialize the analyses.125 for (DataFlowAnalysis &analysis : llvm::make_pointee_range(childAnalyses)) {126 DATAFLOW_DEBUG(LDBG() << "Priming analysis: " << analysis.debugName);127 if (failed(analysis.initialize(top)))128 return failure();129 }130 131 // Run the analysis until fixpoint.132 // Iterate until all states are in some initialized state and the worklist133 // is exhausted.134 while (!worklist.empty()) {135 auto [point, analysis] = worklist.front();136 worklist.pop();137 138 DATAFLOW_DEBUG(LDBG() << "Invoking '" << analysis->debugName139 << "' on: " << *point);140 if (failed(analysis->visit(point)))141 return failure();142 }143 144 return success();145}146 147void DataFlowSolver::propagateIfChanged(AnalysisState *state,148 ChangeResult changed) {149 assert(isRunning &&150 "DataFlowSolver is not running, should not use propagateIfChanged");151 if (changed == ChangeResult::Change) {152 DATAFLOW_DEBUG(LDBG() << "Propagating update to " << state->debugName153 << " of " << state->anchor << "\n"154 << "Value: " << *state);155 state->onUpdate(this);156 }157}158 159//===----------------------------------------------------------------------===//160// DataFlowAnalysis161//===----------------------------------------------------------------------===//162 163DataFlowAnalysis::~DataFlowAnalysis() = default;164 165DataFlowAnalysis::DataFlowAnalysis(DataFlowSolver &solver) : solver(solver) {}166 167void DataFlowAnalysis::addDependency(AnalysisState *state,168 ProgramPoint *point) {169 state->addDependency(point, this);170}171 172void DataFlowAnalysis::propagateIfChanged(AnalysisState *state,173 ChangeResult changed) {174 solver.propagateIfChanged(state, changed);175}176