394 lines · cpp
1//===- TestDenseBackwardDataFlowAnalysis.cpp - Test pass ------------------===//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// Test pass for backward dense dataflow analysis.10//11//===----------------------------------------------------------------------===//12 13#include "TestDenseDataFlowAnalysis.h"14#include "TestOps.h"15#include "mlir/Analysis/DataFlow/DenseAnalysis.h"16#include "mlir/Analysis/DataFlow/Utils.h"17#include "mlir/Analysis/DataFlowFramework.h"18#include "mlir/IR/Builders.h"19#include "mlir/IR/SymbolTable.h"20#include "mlir/Interfaces/CallInterfaces.h"21#include "mlir/Interfaces/ControlFlowInterfaces.h"22#include "mlir/Interfaces/SideEffectInterfaces.h"23#include "mlir/Pass/Pass.h"24#include "mlir/Support/TypeID.h"25#include "llvm/Support/DebugLog.h"26#include "llvm/Support/raw_ostream.h"27 28using namespace mlir;29using namespace mlir::dataflow;30using namespace mlir::dataflow::test;31 32#define DEBUG_TYPE "test-next-access"33 34namespace {35 36class NextAccess : public AbstractDenseLattice, public AccessLatticeBase {37public:38 MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(NextAccess)39 40 using dataflow::AbstractDenseLattice::AbstractDenseLattice;41 42 ChangeResult meet(const AbstractDenseLattice &lattice) override {43 return AccessLatticeBase::merge(static_cast<AccessLatticeBase>(44 static_cast<const NextAccess &>(lattice)));45 }46 47 void print(raw_ostream &os) const override {48 return AccessLatticeBase::print(os);49 }50};51 52class NextAccessAnalysis : public DenseBackwardDataFlowAnalysis<NextAccess> {53public:54 NextAccessAnalysis(DataFlowSolver &solver, SymbolTableCollection &symbolTable,55 bool assumeFuncReads = false)56 : DenseBackwardDataFlowAnalysis(solver, symbolTable),57 assumeFuncReads(assumeFuncReads) {}58 59 LogicalResult visitOperation(Operation *op, const NextAccess &after,60 NextAccess *before) override;61 62 void visitCallControlFlowTransfer(CallOpInterface call,63 CallControlFlowAction action,64 const NextAccess &after,65 NextAccess *before) override;66 67 void visitRegionBranchControlFlowTransfer(RegionBranchOpInterface branch,68 RegionBranchPoint regionFrom,69 RegionSuccessor regionTo,70 const NextAccess &after,71 NextAccess *before) override;72 73 // TODO: this isn't ideal for the analysis. When there is no next access, it74 // means "we don't know what the next access is" rather than "there is no next75 // access". But it's unclear how to differentiate the two cases...76 void setToExitState(NextAccess *lattice) override {77 LDBG() << "setToExitState: setting lattice to unknown state";78 propagateIfChanged(lattice, lattice->setKnownToUnknown());79 }80 81 /// Visit an operation. If this analysis can confirm that lattice content82 /// of lattice anchors around operation are necessarily identical, join83 /// them into the same equivalent class.84 void buildOperationEquivalentLatticeAnchor(Operation *op) override;85 86 const bool assumeFuncReads;87};88} // namespace89 90LogicalResult NextAccessAnalysis::visitOperation(Operation *op,91 const NextAccess &after,92 NextAccess *before) {93 LDBG() << "visitOperation: "94 << OpWithFlags(op, OpPrintingFlags().skipRegions());95 LDBG() << " after state: " << after;96 LDBG() << " before state: " << *before;97 98 auto memory = dyn_cast<MemoryEffectOpInterface>(op);99 // If we can't reason about the memory effects, conservatively assume we can't100 // say anything about the next access.101 if (!memory) {102 LDBG() << " No memory effect interface, setting to exit state";103 setToExitState(before);104 return success();105 }106 107 SmallVector<MemoryEffects::EffectInstance> effects;108 memory.getEffects(effects);109 LDBG() << " Found " << effects.size() << " memory effects";110 111 // First, check if all underlying values are already known. Otherwise, avoid112 // propagating and stay in the "undefined" state to avoid incorrectly113 // propagating values that may be overwritten later on as that could be114 // problematic for convergence based on monotonicity of lattice updates.115 SmallVector<Value> underlyingValues;116 underlyingValues.reserve(effects.size());117 for (const MemoryEffects::EffectInstance &effect : effects) {118 Value value = effect.getValue();119 120 // Effects with unspecified value are treated conservatively and we cannot121 // assume anything about the next access.122 if (!value) {123 LDBG() << " Effect has unspecified value, setting to exit state";124 setToExitState(before);125 return success();126 }127 128 // If cannot find the most underlying value, we cannot assume anything about129 // the next accesses.130 std::optional<Value> underlyingValue =131 UnderlyingValueAnalysis::getMostUnderlyingValue(132 value, [&](Value value) {133 return getOrCreateFor<UnderlyingValueLattice>(134 getProgramPointBefore(op), value);135 });136 137 // If the underlying value is not known yet, don't propagate.138 if (!underlyingValue) {139 LDBG() << " Underlying value not known for " << value140 << ", skipping propagation";141 return success();142 }143 144 LDBG() << " Found underlying value " << *underlyingValue << " for "145 << value;146 underlyingValues.push_back(*underlyingValue);147 }148 149 // Update the state if all underlying values are known.150 LDBG() << " All underlying values known, updating state";151 ChangeResult result = before->meet(after);152 for (const auto &[effect, value] : llvm::zip(effects, underlyingValues)) {153 // If the underlying value is known to be unknown, set to fixpoint.154 if (!value) {155 LDBG() << " Underlying value is unknown, setting to exit state";156 setToExitState(before);157 return success();158 }159 160 LDBG() << " Setting next access for value " << value << " to operation "161 << OpWithFlags(op, OpPrintingFlags().skipRegions());162 result |= before->set(value, op);163 }164 LDBG() << " Final result: "165 << (result == ChangeResult::Change ? "changed" : "no change");166 propagateIfChanged(before, result);167 return success();168}169 170void NextAccessAnalysis::buildOperationEquivalentLatticeAnchor(Operation *op) {171 LDBG() << "buildOperationEquivalentLatticeAnchor: "172 << OpWithFlags(op, OpPrintingFlags().skipRegions());173 if (isMemoryEffectFree(op)) {174 LDBG() << " Operation is memory effect free, unioning lattice anchors";175 unionLatticeAnchors<NextAccess>(getProgramPointBefore(op),176 getProgramPointAfter(op));177 } else {178 LDBG() << " Operation has memory effects, not unioning lattice anchors";179 }180}181 182void NextAccessAnalysis::visitCallControlFlowTransfer(183 CallOpInterface call, CallControlFlowAction action, const NextAccess &after,184 NextAccess *before) {185 LDBG() << "visitCallControlFlowTransfer: "186 << OpWithFlags(call.getOperation(), OpPrintingFlags().skipRegions());187 LDBG() << " action: "188 << (action == CallControlFlowAction::ExternalCallee ? "ExternalCallee"189 : action == CallControlFlowAction::EnterCallee ? "EnterCallee"190 : "ExitCallee");191 LDBG() << " assumeFuncReads: " << assumeFuncReads;192 193 if (action == CallControlFlowAction::ExternalCallee && assumeFuncReads) {194 LDBG() << " Handling external callee with assumed function reads";195 SmallVector<Value> underlyingValues;196 underlyingValues.reserve(call->getNumOperands());197 for (Value operand : call.getArgOperands()) {198 std::optional<Value> underlyingValue =199 UnderlyingValueAnalysis::getMostUnderlyingValue(200 operand, [&](Value value) {201 return getOrCreateFor<UnderlyingValueLattice>(202 getProgramPointBefore(call.getOperation()), value);203 });204 if (!underlyingValue) {205 LDBG() << " Underlying value not known for operand " << operand206 << ", returning";207 return;208 }209 LDBG() << " Found underlying value " << *underlyingValue210 << " for operand " << operand;211 underlyingValues.push_back(*underlyingValue);212 }213 214 LDBG() << " Setting next access for " << underlyingValues.size()215 << " operands";216 ChangeResult result = before->meet(after);217 for (Value operand : underlyingValues) {218 LDBG() << " Setting next access for operand " << operand << " to call "219 << call;220 result |= before->set(operand, call);221 }222 LDBG() << " Call control flow result: "223 << (result == ChangeResult::Change ? "changed" : "no change");224 return propagateIfChanged(before, result);225 }226 auto testCallAndStore =227 dyn_cast<::test::TestCallAndStoreOp>(call.getOperation());228 if (testCallAndStore && ((action == CallControlFlowAction::EnterCallee &&229 testCallAndStore.getStoreBeforeCall()) ||230 (action == CallControlFlowAction::ExitCallee &&231 !testCallAndStore.getStoreBeforeCall()))) {232 LDBG() << " Handling TestCallAndStoreOp with special logic";233 (void)visitOperation(call, after, before);234 } else {235 LDBG() << " Using default call control flow transfer logic";236 AbstractDenseBackwardDataFlowAnalysis::visitCallControlFlowTransfer(237 call, action, after, before);238 }239}240 241void NextAccessAnalysis::visitRegionBranchControlFlowTransfer(242 RegionBranchOpInterface branch, RegionBranchPoint regionFrom,243 RegionSuccessor regionTo, const NextAccess &after, NextAccess *before) {244 LDBG() << "visitRegionBranchControlFlowTransfer: "245 << OpWithFlags(branch.getOperation(), OpPrintingFlags().skipRegions());246 LDBG() << " regionFrom: " << (regionFrom.isParent() ? "parent" : "region");247 LDBG() << " regionTo: " << (regionTo.isParent() ? "parent" : "region");248 249 auto testStoreWithARegion =250 dyn_cast<::test::TestStoreWithARegion>(branch.getOperation());251 252 if (testStoreWithARegion &&253 ((regionTo.isParent() && !testStoreWithARegion.getStoreBeforeRegion()) ||254 (regionFrom.isParent() &&255 testStoreWithARegion.getStoreBeforeRegion()))) {256 LDBG() << " Handling TestStoreWithARegion with special logic";257 (void)visitOperation(branch, static_cast<const NextAccess &>(after),258 static_cast<NextAccess *>(before));259 } else {260 LDBG() << " Using default region branch control flow transfer logic";261 propagateIfChanged(before, before->meet(after));262 }263}264 265namespace {266struct TestNextAccessPass267 : public PassWrapper<TestNextAccessPass, OperationPass<>> {268 TestNextAccessPass() = default;269 TestNextAccessPass(const TestNextAccessPass &other) : PassWrapper(other) {270 interprocedural = other.interprocedural;271 assumeFuncReads = other.assumeFuncReads;272 }273 274 MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(TestNextAccessPass)275 276 StringRef getArgument() const override { return "test-next-access"; }277 278 Option<bool> interprocedural{279 *this, "interprocedural", llvm::cl::init(true),280 llvm::cl::desc("perform interprocedural analysis")};281 Option<bool> assumeFuncReads{282 *this, "assume-func-reads", llvm::cl::init(false),283 llvm::cl::desc(284 "assume external functions have read effect on all arguments")};285 286 static constexpr llvm::StringLiteral kTagAttrName = "name";287 static constexpr llvm::StringLiteral kNextAccessAttrName = "next_access";288 static constexpr llvm::StringLiteral kAtEntryPointAttrName =289 "next_at_entry_point";290 291 static Attribute makeNextAccessAttribute(Operation *op,292 const DataFlowSolver &solver,293 const NextAccess *nextAccess) {294 if (!nextAccess)295 return StringAttr::get(op->getContext(), "not computed");296 297 // Note that if the underlying value could not be computed or is unknown, we298 // conservatively treat the result also unknown.299 SmallVector<Attribute> attrs;300 for (Value operand : op->getOperands()) {301 std::optional<Value> underlyingValue =302 UnderlyingValueAnalysis::getMostUnderlyingValue(303 operand, [&](Value value) {304 return solver.lookupState<UnderlyingValueLattice>(value);305 });306 if (!underlyingValue) {307 attrs.push_back(StringAttr::get(op->getContext(), "unknown"));308 continue;309 }310 Value value = *underlyingValue;311 const AdjacentAccess *nextAcc = nextAccess->getAdjacentAccess(value);312 if (!nextAcc || !nextAcc->isKnown()) {313 attrs.push_back(StringAttr::get(op->getContext(), "unknown"));314 continue;315 }316 317 SmallVector<Attribute> innerAttrs;318 innerAttrs.reserve(nextAcc->get().size());319 for (Operation *nextAccOp : nextAcc->get()) {320 if (auto nextAccTag =321 nextAccOp->getAttrOfType<StringAttr>(kTagAttrName)) {322 innerAttrs.push_back(nextAccTag);323 continue;324 }325 std::string repr;326 llvm::raw_string_ostream os(repr);327 nextAccOp->print(os);328 innerAttrs.push_back(StringAttr::get(op->getContext(), os.str()));329 }330 attrs.push_back(ArrayAttr::get(op->getContext(), innerAttrs));331 }332 return ArrayAttr::get(op->getContext(), attrs);333 }334 335 void runOnOperation() override {336 Operation *op = getOperation();337 LDBG() << "runOnOperation: Starting test-next-access pass on "338 << OpWithFlags(op, OpPrintingFlags().skipRegions());339 LDBG() << " interprocedural: " << interprocedural;340 LDBG() << " assumeFuncReads: " << assumeFuncReads;341 342 SymbolTableCollection symbolTable;343 344 auto config = DataFlowConfig().setInterprocedural(interprocedural);345 DataFlowSolver solver(config);346 loadBaselineAnalyses(solver);347 solver.load<NextAccessAnalysis>(symbolTable, assumeFuncReads);348 solver.load<UnderlyingValueAnalysis>();349 LDBG() << " Initializing and running dataflow solver";350 if (failed(solver.initializeAndRun(op))) {351 emitError(op->getLoc(), "dataflow solver failed");352 return signalPassFailure();353 }354 LDBG() << " Dataflow solver completed successfully";355 LDBG() << " Walking operations to set next access attributes";356 op->walk([&](Operation *op) {357 auto tag = op->getAttrOfType<StringAttr>(kTagAttrName);358 if (!tag)359 return;360 361 LDBG() << " Processing tagged operation: "362 << OpWithFlags(op, OpPrintingFlags().skipRegions());363 const NextAccess *nextAccess =364 solver.lookupState<NextAccess>(solver.getProgramPointAfter(op));365 op->setAttr(kNextAccessAttrName,366 makeNextAccessAttribute(op, solver, nextAccess));367 368 auto iface = dyn_cast<RegionBranchOpInterface>(op);369 if (!iface)370 return;371 372 SmallVector<Attribute> entryPointNextAccess;373 SmallVector<RegionSuccessor> regionSuccessors;374 iface.getSuccessorRegions(RegionBranchPoint::parent(), regionSuccessors);375 for (const RegionSuccessor &successor : regionSuccessors) {376 if (!successor.getSuccessor() || successor.getSuccessor()->empty())377 continue;378 Block &successorBlock = successor.getSuccessor()->front();379 ProgramPoint *successorPoint =380 solver.getProgramPointBefore(&successorBlock);381 entryPointNextAccess.push_back(makeNextAccessAttribute(382 op, solver, solver.lookupState<NextAccess>(successorPoint)));383 }384 op->setAttr(kAtEntryPointAttrName,385 ArrayAttr::get(op->getContext(), entryPointNextAccess));386 });387 }388};389} // namespace390 391namespace mlir::test {392void registerTestNextAccessPass() { PassRegistration<TestNextAccessPass>(); }393} // namespace mlir::test394