| 1 | //===- OffloadLiveInValueCanonicalization.cpp -----------------------------===// |
| 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 pass canonicalizes live-in values for regions destined for offloading. |
| 10 | // |
| 11 | // Overview: |
| 12 | // --------- |
| 13 | // When a region is outlined (extracted into a separate function for device |
| 14 | // execution), values defined outside the region but used inside become |
| 15 | // arguments to the outlined function. However, some values cannot be passed |
| 16 | // as arguments because they represent synthetic types (e.g., shape metadata, |
| 17 | // field indices) or are better handled by recreating them inside the region. |
| 18 | // |
| 19 | // This pass identifies such values and either: |
| 20 | // 1. Sinks the defining operation into the region (if all uses are inside) |
| 21 | // 2. Rematerializes (clones) the operation inside the region (if there are |
| 22 | // uses both inside and outside) |
| 23 | // |
| 24 | // Transforms: |
| 25 | // ----------- |
| 26 | // The pass performs two main transformations on live-in values: |
| 27 | // |
| 28 | // 1. Sinking: If a candidate operation's result is only used inside the |
| 29 | // offload region, the operation is moved into the region. |
| 30 | // |
| 31 | // 2. Rematerialization: If a candidate operation's result is used both |
| 32 | // inside and outside the region, the operation is cloned inside the |
| 33 | // region and uses within the region are updated to use the clone. |
| 34 | // |
| 35 | // Candidate operations are: |
| 36 | // - Constants (matching arith.constant, etc.) |
| 37 | // - Operations implementing `acc::OutlineRematerializationOpInterface` |
| 38 | // - Address-of operations (`acc::AddressOfGlobalOpInterface`) referencing |
| 39 | // symbols that are valid in GPU regions or constant globals |
| 40 | // |
| 41 | // The pass traces through view-like operations (`ViewLikeOpInterface`) and |
| 42 | // partial entity access operations (`acc::PartialEntityAccessOpInterface`) |
| 43 | // to find the original defining operation before making candidate decisions. |
| 44 | // |
| 45 | // Requirements: |
| 46 | // ------------- |
| 47 | // To use this pass in a pipeline, the following requirements must be met: |
| 48 | // |
| 49 | // 1. Target Region Identification: Operations representing offload regions |
| 50 | // must implement `acc::OffloadRegionOpInterface`. This interface marks |
| 51 | // regions that will be outlined for device execution. |
| 52 | // |
| 53 | // 2. Rematerialization Candidates: Operations producing values that should |
| 54 | // be rematerialized (rather than passed as arguments) should implement |
| 55 | // `acc::OutlineRematerializationOpInterface`. Examples include operations |
| 56 | // producing shape metadata, field indices, or other synthetic types. |
| 57 | // |
| 58 | // 3. Analysis Registration (Optional): If custom behavior is needed for |
| 59 | // symbol validation (e.g., determining if a global is valid on device), |
| 60 | // pre-register `acc::OpenACCSupport` analysis on the parent module. |
| 61 | // If not registered, default behavior will be used. |
| 62 | // |
| 63 | // 4. View-Like Operations: Operations that create views or casts should |
| 64 | // implement `ViewLikeOpInterface` or `acc::PartialEntityAccessOpInterface` |
| 65 | // to allow the pass to trace through to the original defining operation. |
| 66 | // |
| 67 | //===----------------------------------------------------------------------===// |
| 68 | |
| 69 | #include "mlir/Dialect/OpenACC/Extensions/AllExtensions.h" |
| 70 | #include "mlir/Dialect/OpenACC/Transforms/Passes.h" |
| 71 | |
| 72 | #include "mlir/Analysis/TopologicalSortUtils.h" |
| 73 | #include "mlir/Dialect/Func/IR/FuncOps.h" |
| 74 | #include "mlir/Dialect/OpenACC/Analysis/OpenACCSupport.h" |
| 75 | #include "mlir/Dialect/OpenACC/OpenACC.h" |
| 76 | #include "mlir/IR/Builders.h" |
| 77 | #include "mlir/IR/Matchers.h" |
| 78 | #include "mlir/IR/Operation.h" |
| 79 | #include "mlir/IR/Region.h" |
| 80 | #include "mlir/IR/SymbolTable.h" |
| 81 | #include "mlir/IR/Value.h" |
| 82 | #include "mlir/Interfaces/SideEffectInterfaces.h" |
| 83 | #include "mlir/Interfaces/ViewLikeInterface.h" |
| 84 | #include "mlir/Pass/Pass.h" |
| 85 | #include "mlir/Support/LLVM.h" |
| 86 | #include "mlir/Transforms/RegionUtils.h" |
| 87 | |
| 88 | namespace mlir { |
| 89 | namespace acc { |
| 90 | #define GEN_PASS_DEF_OFFLOADLIVEINVALUECANONICALIZATION |
| 91 | #include "mlir/Dialect/OpenACC/Transforms/Passes.h.inc" |
| 92 | } // namespace acc |
| 93 | } // namespace mlir |
| 94 | |
| 95 | #define DEBUG_TYPE "offload-livein-value-canonicalization" |
| 96 | |
| 97 | using namespace mlir; |
| 98 | |
| 99 | namespace { |
| 100 | /// Returns true if all users of the given value are inside the region. |
| 101 | static bool allUsersAreInsideRegion(Value val, Region ®ion) { |
| 102 | for (Operation *user : val.getUsers()) |
| 103 | if (!region.isAncestor(other: user->getParentRegion())) |
| 104 | return false; |
| 105 | return true; |
| 106 | } |
| 107 | |
| 108 | /// Traces through view-like and partial entity access operations to find the |
| 109 | /// original defining value. |
| 110 | static Value getOriginalValue(Value val) { |
| 111 | Value prev; |
| 112 | while (val && val != prev) { |
| 113 | prev = val; |
| 114 | if (auto viewLikeOp = val.getDefiningOp<ViewLikeOpInterface>()) |
| 115 | val = viewLikeOp.getViewSource(); |
| 116 | if (auto partialAccess = |
| 117 | val.getDefiningOp<acc::PartialEntityAccessOpInterface>()) { |
| 118 | Value base = partialAccess.getBaseEntity(); |
| 119 | if (base) |
| 120 | val = base; |
| 121 | } |
| 122 | } |
| 123 | return val; |
| 124 | } |
| 125 | |
| 126 | /// Returns true if the operation is a candidate for rematerialization. |
| 127 | /// Candidates are operations that: |
| 128 | /// 1. Match the constant pattern (arith.constant, etc.) |
| 129 | /// 2. Implement OutlineRematerializationOpInterface |
| 130 | /// 3. Are address-of operations referencing valid symbols or constant globals |
| 131 | /// The function traces through view-like operations (casts, reinterpret_cast) |
| 132 | /// to find the original defining operation before making the determination. |
| 133 | static bool isRematerializationCandidate(Value val, |
| 134 | acc::OpenACCSupport &accSupport) { |
| 135 | // Trace through view-like operations to find the original value. |
| 136 | Value origVal = getOriginalValue(val); |
| 137 | Operation *definingOp = origVal.getDefiningOp(); |
| 138 | if (!definingOp && !(definingOp = val.getDefiningOp())) |
| 139 | return false; |
| 140 | |
| 141 | LLVM_DEBUG(llvm::dbgs() << "\tChecking candidate: " << *definingOp << "\n" ); |
| 142 | |
| 143 | // Constants are trivial and useful to rematerialize. |
| 144 | if (matchPattern(op: definingOp, pattern: m_Constant())) { |
| 145 | LLVM_DEBUG(llvm::dbgs() << "\t\t-> constant pattern matched\n" ); |
| 146 | return true; |
| 147 | } |
| 148 | |
| 149 | // Operations implementing OutlineRematerializationOpInterface are candidates. |
| 150 | if (isa<acc::OutlineRematerializationOpInterface>(Val: definingOp)) { |
| 151 | LLVM_DEBUG(llvm::dbgs() << "\t\t-> OutlineRematerializationOpInterface\n" ); |
| 152 | return true; |
| 153 | } |
| 154 | |
| 155 | // Address-of operations referencing globals that are valid in GPU regions |
| 156 | // or referencing constant globals should be rematerialized. |
| 157 | if (auto addrOfOp = dyn_cast<acc::AddressOfGlobalOpInterface>(Val: definingOp)) { |
| 158 | SymbolRefAttr symbol = addrOfOp.getSymbol(); |
| 159 | LLVM_DEBUG(llvm::dbgs() |
| 160 | << "\t\tAddressOfGlobalOpInterface, symbol: " << symbol << "\n" ); |
| 161 | |
| 162 | // If the symbol is already valid in GPU regions (e.g., has acc.declare), |
| 163 | // rematerializing ensures the address refers to the device copy. |
| 164 | Operation *globalOp = nullptr; |
| 165 | if (accSupport.isValidSymbolUse(user: definingOp, symbol, definingOpPtr: &globalOp)) { |
| 166 | LLVM_DEBUG(llvm::dbgs() << "\t\t-> isValidSymbolUse: true\n" ); |
| 167 | return true; |
| 168 | } |
| 169 | LLVM_DEBUG(llvm::dbgs() << "\t\t-> isValidSymbolUse: false\n" ); |
| 170 | |
| 171 | // If the referenced global is constant, prefer rematerialization so the |
| 172 | // constant can be placed in GPU memory. |
| 173 | if (globalOp) { |
| 174 | if (auto globalVarOp = |
| 175 | dyn_cast<acc::GlobalVariableOpInterface>(Val: globalOp)) { |
| 176 | if (globalVarOp.isConstant()) { |
| 177 | LLVM_DEBUG(llvm::dbgs() << "\t\t-> constant global\n" ); |
| 178 | return true; |
| 179 | } |
| 180 | } |
| 181 | } |
| 182 | } |
| 183 | |
| 184 | // An op implementing both ViewLikeOpInterface and |
| 185 | // OutlineRematerializationOpInterface may have been traced through by |
| 186 | // getOriginalValue. If the traced op is not a candidate, check the direct |
| 187 | // defining op of the live-in value. |
| 188 | if (origVal != val) { |
| 189 | if (isa_and_nonnull<acc::OutlineRematerializationOpInterface>( |
| 190 | Val: val.getDefiningOp())) { |
| 191 | LLVM_DEBUG(llvm::dbgs() |
| 192 | << "\t\t-> OutlineRematerializationOpInterface (direct)\n" ); |
| 193 | return true; |
| 194 | } |
| 195 | } |
| 196 | |
| 197 | LLVM_DEBUG(llvm::dbgs() << "\t\t-> not a candidate\n" ); |
| 198 | return false; |
| 199 | } |
| 200 | |
| 201 | class OffloadLiveInValueCanonicalization |
| 202 | : public acc::impl::OffloadLiveInValueCanonicalizationBase< |
| 203 | OffloadLiveInValueCanonicalization> { |
| 204 | public: |
| 205 | using acc::impl::OffloadLiveInValueCanonicalizationBase< |
| 206 | OffloadLiveInValueCanonicalization>:: |
| 207 | OffloadLiveInValueCanonicalizationBase; |
| 208 | |
| 209 | void getDependentDialects(DialectRegistry ®istry) const override { |
| 210 | acc::impl::OffloadLiveInValueCanonicalizationBase< |
| 211 | OffloadLiveInValueCanonicalization>::getDependentDialects(registry); |
| 212 | acc::registerAllExtensions(registry); |
| 213 | } |
| 214 | |
| 215 | /// Canonicalizes live-in values for a region by sinking or rematerializing |
| 216 | /// operations. Returns true if any changes were made. |
| 217 | bool canonicalizeLiveInValues(Region ®ion, |
| 218 | acc::OpenACCSupport &accSupport) { |
| 219 | // 1) Collect live-in values. |
| 220 | SetVector<Value> liveInValues; |
| 221 | getUsedValuesDefinedAbove(regions: region, values&: liveInValues); |
| 222 | LLVM_DEBUG(llvm::dbgs() |
| 223 | << "\tFound " << liveInValues.size() << " live-in value(s)\n" ); |
| 224 | |
| 225 | auto isSinkCandidate = [®ion, &accSupport](Value val) -> bool { |
| 226 | return isRematerializationCandidate(val, accSupport) && |
| 227 | allUsersAreInsideRegion(val, region); |
| 228 | }; |
| 229 | auto isCloneCandidate = [®ion, &accSupport](Value val) -> bool { |
| 230 | return isRematerializationCandidate(val, accSupport) && |
| 231 | !allUsersAreInsideRegion(val, region); |
| 232 | }; |
| 233 | |
| 234 | // 2) Filter values into two sets - sink and rematerialization candidates. |
| 235 | SmallVector<Value> sinkCandidates( |
| 236 | llvm::make_filter_range(Range&: liveInValues, Pred: isSinkCandidate)); |
| 237 | SmallVector<Value> rematerializationCandidates( |
| 238 | llvm::make_filter_range(Range&: liveInValues, Pred: isCloneCandidate)); |
| 239 | |
| 240 | LLVM_DEBUG(llvm::dbgs() << "\tSink candidates: " << sinkCandidates.size() |
| 241 | << ", clone candidates: " |
| 242 | << rematerializationCandidates.size() << "\n" ); |
| 243 | |
| 244 | if (rematerializationCandidates.empty() && sinkCandidates.empty()) |
| 245 | return false; |
| 246 | |
| 247 | LLVM_DEBUG(llvm::dbgs() << "\tCanonicalizing values into " |
| 248 | << *region.getParentOp() << "\n" ); |
| 249 | |
| 250 | // 3) Handle the sink set by moving the operations into the region. |
| 251 | for (Value sinkCandidate : sinkCandidates) { |
| 252 | Operation *sinkOp = sinkCandidate.getDefiningOp(); |
| 253 | assert(sinkOp && "must have op to be considered" ); |
| 254 | sinkOp->moveBefore(existingOp: ®ion.front().front()); |
| 255 | // Some operations (e.g. fir.declare) may carry identity operands that |
| 256 | // must not be left referencing a value defined outside the region. |
| 257 | // Unlike other operands, such identity operands cannot simply be |
| 258 | // treated as new live-ins to legalize; they must be dropped instead. |
| 259 | if (auto identityOp = |
| 260 | dyn_cast<acc::OutlineIdentityOperandOpInterface>(Val: sinkOp)) |
| 261 | identityOp.dropOutlinedIdentityOperands(); |
| 262 | LLVM_DEBUG(llvm::dbgs() << "\t\tSunk: " << *sinkOp << "\n" ); |
| 263 | } |
| 264 | |
| 265 | // 4) Handle the rematerialization set by copying the operations into |
| 266 | // the region. |
| 267 | OpBuilder builder(region); |
| 268 | SmallVector<Operation *> opsToRematerialize; |
| 269 | for (Value rematerializationCandidate : rematerializationCandidates) { |
| 270 | Operation *rematerializationOp = |
| 271 | rematerializationCandidate.getDefiningOp(); |
| 272 | assert(rematerializationOp && "must have op to be considered" ); |
| 273 | opsToRematerialize.push_back(Elt: rematerializationOp); |
| 274 | } |
| 275 | computeTopologicalSorting(ops: opsToRematerialize); |
| 276 | for (Operation *rematerializationOp : opsToRematerialize) { |
| 277 | Operation *clonedOp = builder.clone(op&: *rematerializationOp); |
| 278 | // See the comment above: identity operands must be dropped from the |
| 279 | // clone rather than duplicated, since duplicating them would make the |
| 280 | // clone appear to belong to a different instantiation than the |
| 281 | // original operation (and any of its siblings left outside the |
| 282 | // region). |
| 283 | if (auto identityOp = |
| 284 | dyn_cast<acc::OutlineIdentityOperandOpInterface>(Val: clonedOp)) |
| 285 | identityOp.dropOutlinedIdentityOperands(); |
| 286 | for (auto [oldResult, newResult] : llvm::zip( |
| 287 | t: rematerializationOp->getResults(), u: clonedOp->getResults())) { |
| 288 | replaceAllUsesInRegionWith(orig: oldResult, replacement: newResult, region); |
| 289 | } |
| 290 | LLVM_DEBUG(llvm::dbgs() << "\t\tCloned: " << *clonedOp << "\n" ); |
| 291 | } |
| 292 | |
| 293 | return true; |
| 294 | } |
| 295 | |
| 296 | void runOnOperation() override { |
| 297 | LLVM_DEBUG(llvm::dbgs() << "Enter OffloadLiveInValueCanonicalization\n" ); |
| 298 | |
| 299 | // Since OpenACCSupport is normally registered on modules, attempt to |
| 300 | // get it from the parent module first (if available), then fallback |
| 301 | // to the per-function analysis. |
| 302 | acc::OpenACCSupport *accSupportPtr = nullptr; |
| 303 | if (auto parentAnalysis = getCachedParentAnalysis<acc::OpenACCSupport>()) |
| 304 | accSupportPtr = &parentAnalysis->get(); |
| 305 | else |
| 306 | accSupportPtr = &getAnalysis<acc::OpenACCSupport>(); |
| 307 | acc::OpenACCSupport &accSupport = *accSupportPtr; |
| 308 | |
| 309 | func::FuncOp func = getOperation(); |
| 310 | LLVM_DEBUG(llvm::dbgs() |
| 311 | << "Processing function: " << func.getName() << "\n" ); |
| 312 | |
| 313 | func.walk(callback: [&](Operation *op) { |
| 314 | if (isa<acc::OffloadRegionOpInterface>(Val: op)) { |
| 315 | LLVM_DEBUG(llvm::dbgs() |
| 316 | << "Found offload region: " << op->getName() << "\n" ); |
| 317 | assert(op->getNumRegions() == 1 && "must have 1 region" ); |
| 318 | |
| 319 | // Canonicalization of values changes live-in set. |
| 320 | // Rerun the algorithm until convergence. |
| 321 | bool changes = false; |
| 322 | [[maybe_unused]] int iteration = 0; |
| 323 | do { |
| 324 | LLVM_DEBUG(llvm::dbgs() << "\tIteration " << iteration++ << "\n" ); |
| 325 | changes = canonicalizeLiveInValues(region&: op->getRegion(index: 0), accSupport); |
| 326 | } while (changes); |
| 327 | LLVM_DEBUG(llvm::dbgs() |
| 328 | << "\tConverged after " << iteration << " iteration(s)\n" ); |
| 329 | } |
| 330 | }); |
| 331 | |
| 332 | LLVM_DEBUG(llvm::dbgs() << "Exit OffloadLiveInValueCanonicalization\n" ); |
| 333 | } |
| 334 | }; |
| 335 | } // namespace |
| 336 | |