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