| 1 | //===- OpenACCUtilsLoop.cpp - OpenACC Loop Utilities ----------------------===// |
| 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 contains utility functions for converting OpenACC loops to SCF. |
| 10 | // |
| 11 | //===----------------------------------------------------------------------===// |
| 12 | |
| 13 | #include "mlir/Dialect/OpenACC/OpenACCUtilsLoop.h" |
| 14 | |
| 15 | #include "mlir/Dialect/Arith/IR/Arith.h" |
| 16 | #include "mlir/Dialect/Arith/Utils/Utils.h" |
| 17 | #include "mlir/Dialect/LLVMIR/LLVMAttrs.h" |
| 18 | #include "mlir/Dialect/OpenACC/OpenACC.h" |
| 19 | #include "mlir/Dialect/SCF/IR/SCF.h" |
| 20 | #include "mlir/Dialect/SCF/Utils/Utils.h" |
| 21 | #include "mlir/IR/IRMapping.h" |
| 22 | #include "mlir/Transforms/RegionUtils.h" |
| 23 | #include "llvm/ADT/SmallPtrSet.h" |
| 24 | #include "llvm/Support/ErrorHandling.h" |
| 25 | |
| 26 | using namespace mlir; |
| 27 | |
| 28 | /// Calculate trip count for a loop: (ub - lb + step) / step |
| 29 | /// If inclusiveUpperbound is false, subtracts 1 from ub first. |
| 30 | Value acc::calculateTripCount(OpBuilder &b, Location loc, Value lb, Value ub, |
| 31 | Value step, bool inclusiveUpperbound) { |
| 32 | Type type = b.getIndexType(); |
| 33 | |
| 34 | // Convert original loop arguments to index type |
| 35 | lb = getValueOrCreateCastToIndexLike(b, loc, targetType: type, value: lb); |
| 36 | ub = getValueOrCreateCastToIndexLike(b, loc, targetType: type, value: ub); |
| 37 | step = getValueOrCreateCastToIndexLike(b, loc, targetType: type, value: step); |
| 38 | |
| 39 | if (!inclusiveUpperbound) { |
| 40 | Value one = arith::ConstantIndexOp::create(builder&: b, location: loc, value: 1); |
| 41 | ub = b.createOrFold<arith::SubIOp>(location: loc, args&: ub, args&: one, |
| 42 | args: arith::IntegerOverflowFlags::nsw); |
| 43 | } |
| 44 | |
| 45 | Value sub = b.createOrFold<arith::SubIOp>(location: loc, args&: ub, args&: lb, |
| 46 | args: arith::IntegerOverflowFlags::nsw); |
| 47 | Value add = b.createOrFold<arith::AddIOp>(location: loc, args&: sub, args&: step, |
| 48 | args: arith::IntegerOverflowFlags::nsw); |
| 49 | return b.createOrFold<arith::DivSIOp>(location: loc, args&: add, args&: step); |
| 50 | } |
| 51 | |
| 52 | /// Handle differing types between SCF (index) and ACC loops. |
| 53 | /// Creates casts from the new SCF IVs to the original ACC IV types and updates |
| 54 | /// the mapping. The newIVs should correspond 1:1 with the ACC loop's IVs. |
| 55 | static void mapACCLoopIVsToSCFIVs(acc::LoopOp accLoop, ValueRange newIVs, |
| 56 | OpBuilder &b, IRMapping &mapping) { |
| 57 | for (auto [origIV, newIV] : |
| 58 | llvm::zip(t: accLoop.getBody().getArguments(), u&: newIVs)) { |
| 59 | Value replacementIV = getValueOrCreateCastToIndexLike( |
| 60 | b, loc: accLoop->getLoc(), targetType: origIV.getType(), value: newIV); |
| 61 | mapping.map(from: origIV, to: replacementIV); |
| 62 | } |
| 63 | } |
| 64 | |
| 65 | /// Normalize IV uses after converting to normalized loop form. |
| 66 | /// For normalized loops (lb=0, step=1), we need to denormalize the IV: |
| 67 | /// original_iv = new_iv * orig_step + orig_lb |
| 68 | void acc::normalizeIVUses(OpBuilder &b, Location loc, Value iv, Value origLB, |
| 69 | Value origStep) { |
| 70 | Type indexType = b.getIndexType(); |
| 71 | Value lb = getValueOrCreateCastToIndexLike(b, loc, targetType: indexType, value: origLB); |
| 72 | Value step = getValueOrCreateCastToIndexLike(b, loc, targetType: indexType, value: origStep); |
| 73 | |
| 74 | // new_iv * step + lb |
| 75 | Value scaled = |
| 76 | arith::MulIOp::create(builder&: b, location: loc, lhs: iv, rhs: step, overflowFlags: arith::IntegerOverflowFlags::nsw); |
| 77 | Value denormalized = arith::AddIOp::create(builder&: b, location: loc, lhs: scaled, rhs: lb, |
| 78 | overflowFlags: arith::IntegerOverflowFlags::nsw); |
| 79 | |
| 80 | // Replace uses of iv with denormalized value, except for the ops that |
| 81 | // compute the denormalized value itself (muli and addi) |
| 82 | llvm::SmallPtrSet<Operation *, 2> exceptions; |
| 83 | exceptions.insert(Ptr: scaled.getDefiningOp()); |
| 84 | exceptions.insert(Ptr: denormalized.getDefiningOp()); |
| 85 | iv.replaceAllUsesExcept(newValue: denormalized, exceptions); |
| 86 | } |
| 87 | |
| 88 | /// Helper used by loop conversion: clone region and return insertion point |
| 89 | /// only. |
| 90 | static Block::iterator cloneACCRegionIntoForLoop(Region *src, Block *dest, |
| 91 | Block::iterator insertionPoint, |
| 92 | IRMapping &mapping, |
| 93 | RewriterBase &rewriter) { |
| 94 | auto [replacements, ip] = |
| 95 | acc::cloneACCRegionInto(src, dest, inlinePoint: insertionPoint, mapping, resultsToReplace: ValueRange{}); |
| 96 | (void)replacements; |
| 97 | return ip; |
| 98 | } |
| 99 | |
| 100 | /// Copy the discardable LLVM loop annotation attribute from an acc.loop to the |
| 101 | /// lowered SCF op so later SCF to CFG/LLVM lowering can emit !llvm.loop |
| 102 | /// metadata. |
| 103 | static void copyLoopAnnotationAttr(Operation *from, Operation *to) { |
| 104 | if (Attribute ann = |
| 105 | from->getDiscardableAttr(name: LLVM::getLoopAnnotationAttrName())) |
| 106 | to->setDiscardableAttr(name: LLVM::getLoopAnnotationAttrName(), value: ann); |
| 107 | } |
| 108 | |
| 109 | namespace mlir { |
| 110 | namespace acc { |
| 111 | |
| 112 | std::pair<SmallVector<Value>, Block::iterator> |
| 113 | cloneACCRegionInto(Region *src, Block *dest, Block::iterator inlinePoint, |
| 114 | IRMapping &mapping, ValueRange resultsToReplace) { |
| 115 | if (!src->hasOneBlock()) |
| 116 | llvm_unreachable("cloneACCRegionInto: multi-block region not supported " |
| 117 | "(requires scf.execute_region)" ); |
| 118 | |
| 119 | Region *insertRegion = dest->getParent(); |
| 120 | Block *postInsertBlock = dest->splitBlock(splitBefore: inlinePoint); |
| 121 | src->cloneInto(dest: insertRegion, destPos: postInsertBlock->getIterator(), mapper&: mapping); |
| 122 | |
| 123 | SmallVector<Value> replacements; |
| 124 | Block *lastNewBlock = &*std::prev(x: postInsertBlock->getIterator()); |
| 125 | |
| 126 | Block::iterator ip; |
| 127 | if (auto yieldOp = dyn_cast<acc::YieldOp>(Val: lastNewBlock->getTerminator())) { |
| 128 | for (auto [replacement, orig] : |
| 129 | llvm::zip(t: yieldOp.getOperands(), u&: resultsToReplace)) { |
| 130 | replaceAllUsesInRegionWith(orig, replacement, region&: *dest->getParent()); |
| 131 | } |
| 132 | replacements.append(in_start: yieldOp.getOperands().begin(), |
| 133 | in_end: yieldOp.getOperands().end()); |
| 134 | ip = std::prev(x: yieldOp->getIterator()); |
| 135 | yieldOp.erase(); |
| 136 | } else { |
| 137 | auto terminatorOp = |
| 138 | dyn_cast<acc::TerminatorOp>(Val: lastNewBlock->getTerminator()); |
| 139 | if (!terminatorOp) |
| 140 | llvm_unreachable( |
| 141 | "cloneACCRegionInto: expected acc.yield or acc.terminator" ); |
| 142 | ip = std::prev(x: terminatorOp->getIterator()); |
| 143 | terminatorOp.erase(); |
| 144 | } |
| 145 | |
| 146 | lastNewBlock->getOperations().splice(where: lastNewBlock->end(), |
| 147 | L2&: postInsertBlock->getOperations()); |
| 148 | postInsertBlock->erase(); |
| 149 | |
| 150 | Block *firstNewBlock = &*std::next(x: dest->getIterator()); |
| 151 | dest->getOperations().splice(where: dest->end(), L2&: firstNewBlock->getOperations()); |
| 152 | firstNewBlock->erase(); |
| 153 | return {replacements, ip}; |
| 154 | } |
| 155 | |
| 156 | /// Wrap a multi-block region with scf.execute_region. |
| 157 | scf::ExecuteRegionOp |
| 158 | wrapMultiBlockRegionWithSCFExecuteRegion(Region ®ion, IRMapping &mapping, |
| 159 | Location loc, RewriterBase &rewriter) { |
| 160 | SmallVector<Operation *> terminators; |
| 161 | for (Block &block : region.getBlocks()) { |
| 162 | if (block.empty()) |
| 163 | continue; |
| 164 | Operation *term = block.getTerminator(); |
| 165 | if (term->getNumSuccessors() == 0) |
| 166 | terminators.push_back(Elt: term); |
| 167 | } |
| 168 | SmallVector<Type> resultTypes; |
| 169 | if (!terminators.empty()) |
| 170 | for (Value operand : terminators.front()->getOperands()) |
| 171 | resultTypes.push_back(Elt: operand.getType()); |
| 172 | |
| 173 | auto exeRegionOp = |
| 174 | scf::ExecuteRegionOp::create(builder&: rewriter, location: loc, resultType0: TypeRange(resultTypes)); |
| 175 | |
| 176 | rewriter.cloneRegionBefore(region, parent&: exeRegionOp.getRegion(), |
| 177 | before: exeRegionOp.getRegion().end(), mapping); |
| 178 | |
| 179 | for (Operation *term : terminators) { |
| 180 | Operation *blockTerminator = mapping.lookup(from: term); |
| 181 | assert(blockTerminator && "expected terminator to be in mapping" ); |
| 182 | rewriter.setInsertionPoint(blockTerminator); |
| 183 | (void)scf::YieldOp::create(builder&: rewriter, location: blockTerminator->getLoc(), |
| 184 | results: blockTerminator->getOperands()); |
| 185 | rewriter.eraseOp(op: blockTerminator); |
| 186 | } |
| 187 | |
| 188 | return exeRegionOp; |
| 189 | } |
| 190 | |
| 191 | scf::ForOp convertACCLoopToSCFFor(LoopOp loopOp, RewriterBase &rewriter, |
| 192 | bool enableCollapse) { |
| 193 | assert(!loopOp.getUnstructured() && |
| 194 | "use convertUnstructuredACCLoopToSCFExecuteRegion for unstructured " |
| 195 | "loops" ); |
| 196 | |
| 197 | Location loc = loopOp->getLoc(); |
| 198 | |
| 199 | IRMapping mapping; |
| 200 | SmallVector<scf::ForOp> forOps; |
| 201 | |
| 202 | OpBuilder::InsertionGuard guard(rewriter); |
| 203 | rewriter.setInsertionPoint(loopOp); |
| 204 | |
| 205 | // Normalize all loops: lb=0, step=1, ub=tripCount. |
| 206 | // scf.for requires a positive step, but acc.loop may have arbitrary steps |
| 207 | // (including negative). Normalizing unconditionally keeps this consistent |
| 208 | // with convertACCLoopToSCFParallel and lets later passes fold constants. |
| 209 | Value zero = arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: 0); |
| 210 | Value one = arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: 1); |
| 211 | |
| 212 | SmallVector<Value> tripCounts; |
| 213 | for (auto [idx, iv] : llvm::enumerate(First: loopOp.getBody().getArguments())) { |
| 214 | bool inclusiveUpperbound = false; |
| 215 | if (loopOp.getInclusiveUpperbound().has_value()) |
| 216 | inclusiveUpperbound = |
| 217 | loopOp.getInclusiveUpperboundAttr().asArrayRef()[idx]; |
| 218 | |
| 219 | Value tc = calculateTripCount(b&: rewriter, loc, lb: loopOp.getLowerbound()[idx], |
| 220 | ub: loopOp.getUpperbound()[idx], |
| 221 | step: loopOp.getStep()[idx], inclusiveUpperbound); |
| 222 | tripCounts.push_back(Elt: tc); |
| 223 | } |
| 224 | |
| 225 | for (auto [idx, iv] : llvm::enumerate(First: loopOp.getBody().getArguments())) { |
| 226 | // For nested loops, insert inside the previous loop's body |
| 227 | if (idx > 0) |
| 228 | rewriter.setInsertionPointToStart(forOps.back().getBody()); |
| 229 | |
| 230 | scf::ForOp forOp = |
| 231 | scf::ForOp::create(builder&: rewriter, location: loc, lowerBound: zero, upperBound: tripCounts[idx], step: one); |
| 232 | forOps.push_back(Elt: forOp); |
| 233 | mapping.map(from: iv, to: forOp.getInductionVar()); |
| 234 | } |
| 235 | |
| 236 | // Set insertion point inside the innermost loop for IV casts and body cloning |
| 237 | rewriter.setInsertionPointToStart(forOps.back().getBody()); |
| 238 | |
| 239 | // Handle IV type conversion (index -> original type) |
| 240 | SmallVector<Value> scfIVs; |
| 241 | for (scf::ForOp forOp : forOps) |
| 242 | scfIVs.push_back(Elt: forOp.getInductionVar()); |
| 243 | mapACCLoopIVsToSCFIVs(accLoop: loopOp, newIVs: scfIVs, b&: rewriter, mapping); |
| 244 | |
| 245 | // Clone the loop body into the innermost scf.for. scf.for has a single-block |
| 246 | // region, so a multi-block body is wrapped in scf.execute_region, matching |
| 247 | // convertACCLoopToSCFParallel. |
| 248 | if (!loopOp.getRegion().hasOneBlock()) { |
| 249 | auto exeRegion = wrapMultiBlockRegionWithSCFExecuteRegion( |
| 250 | region&: loopOp.getRegion(), mapping, loc, rewriter); |
| 251 | if (!exeRegion) { |
| 252 | rewriter.eraseOp(op: forOps.front()); |
| 253 | return nullptr; |
| 254 | } |
| 255 | } else { |
| 256 | cloneACCRegionIntoForLoop(src: &loopOp.getRegion(), dest: forOps.back().getBody(), |
| 257 | insertionPoint: rewriter.getInsertionPoint(), mapping, rewriter); |
| 258 | } |
| 259 | |
| 260 | // Denormalize IV uses: original_iv = normalized_iv * orig_step + orig_lb |
| 261 | for (size_t idx = 0; idx < forOps.size(); ++idx) { |
| 262 | Value iv = forOps[idx].getInductionVar(); |
| 263 | if (!iv.use_empty()) { |
| 264 | rewriter.setInsertionPointToStart(forOps[idx].getBody()); |
| 265 | normalizeIVUses(b&: rewriter, loc, iv, origLB: loopOp.getLowerbound()[idx], |
| 266 | origStep: loopOp.getStep()[idx]); |
| 267 | } |
| 268 | } |
| 269 | |
| 270 | // Optionally collapse nested loops |
| 271 | if (enableCollapse && forOps.size() > 1) { |
| 272 | unsigned numCollapsed = forOps.size(); |
| 273 | if (failed(Result: coalesceLoops(rewriter, forOps))) |
| 274 | loopOp.emitError(message: "failed to collapse acc.loop" ); |
| 275 | else |
| 276 | setCollapseCountAttr(op: forOps.front(), count: numCollapsed); |
| 277 | } |
| 278 | |
| 279 | copyLoopAnnotationAttr(from: loopOp, to: forOps.front()); |
| 280 | return forOps.front(); |
| 281 | } |
| 282 | |
| 283 | scf::ParallelOp convertACCLoopToSCFParallel(LoopOp loopOp, |
| 284 | RewriterBase &rewriter) { |
| 285 | assert(!loopOp.getUnstructured() && |
| 286 | "use convertUnstructuredACCLoopToSCFExecuteRegion for unstructured " |
| 287 | "loops" ); |
| 288 | assert( |
| 289 | rewriter.getInsertionBlock() && |
| 290 | !loopOp->isProperAncestor(rewriter.getInsertionBlock()->getParentOp()) && |
| 291 | "builder insertion point must not be inside the loop being converted" ); |
| 292 | |
| 293 | Location loc = loopOp->getLoc(); |
| 294 | |
| 295 | SmallVector<Value> lowerBounds, upperBounds, steps; |
| 296 | |
| 297 | // Normalize all loops: lb=0, step=1, ub=tripCount |
| 298 | Value lb = arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: 0); |
| 299 | Value step = arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: 1); |
| 300 | |
| 301 | for (auto [idx, iv] : llvm::enumerate(First: loopOp.getBody().getArguments())) { |
| 302 | bool inclusiveUpperbound = false; |
| 303 | if (loopOp.getInclusiveUpperbound().has_value()) |
| 304 | inclusiveUpperbound = loopOp.getInclusiveUpperbound().value()[idx]; |
| 305 | |
| 306 | Value ub = calculateTripCount(b&: rewriter, loc, lb: loopOp.getLowerbound()[idx], |
| 307 | ub: loopOp.getUpperbound()[idx], |
| 308 | step: loopOp.getStep()[idx], inclusiveUpperbound); |
| 309 | |
| 310 | lowerBounds.push_back(Elt: lb); |
| 311 | upperBounds.push_back(Elt: ub); |
| 312 | steps.push_back(Elt: step); |
| 313 | } |
| 314 | |
| 315 | auto parallelOp = |
| 316 | scf::ParallelOp::create(builder&: rewriter, location: loc, lowerBounds, upperBounds, steps); |
| 317 | |
| 318 | // Create IV type conversions |
| 319 | IRMapping mapping; |
| 320 | rewriter.setInsertionPointToStart(parallelOp.getBody()); |
| 321 | mapACCLoopIVsToSCFIVs(accLoop: loopOp, newIVs: parallelOp.getInductionVars(), b&: rewriter, |
| 322 | mapping); |
| 323 | |
| 324 | if (!loopOp.getRegion().hasOneBlock()) { |
| 325 | auto exeRegion = wrapMultiBlockRegionWithSCFExecuteRegion( |
| 326 | region&: loopOp.getRegion(), mapping, loc, rewriter); |
| 327 | if (!exeRegion) { |
| 328 | rewriter.eraseOp(op: parallelOp); |
| 329 | return nullptr; |
| 330 | } |
| 331 | } else { |
| 332 | cloneACCRegionIntoForLoop(src: &loopOp.getRegion(), dest: parallelOp.getBody(), |
| 333 | insertionPoint: rewriter.getInsertionPoint(), mapping, rewriter); |
| 334 | } |
| 335 | |
| 336 | // Denormalize IV uses |
| 337 | rewriter.setInsertionPointToStart(parallelOp.getBody()); |
| 338 | for (auto [idx, iv] : llvm::enumerate(First: parallelOp.getBody()->getArguments())) |
| 339 | if (!iv.use_empty()) |
| 340 | normalizeIVUses(b&: rewriter, loc, iv, origLB: loopOp.getLowerbound()[idx], |
| 341 | origStep: loopOp.getStep()[idx]); |
| 342 | |
| 343 | setCollapseCountAttr(op: parallelOp, count: parallelOp.getNumLoops()); |
| 344 | copyLoopAnnotationAttr(from: loopOp, to: parallelOp); |
| 345 | return parallelOp; |
| 346 | } |
| 347 | |
| 348 | scf::ExecuteRegionOp |
| 349 | convertUnstructuredACCLoopToSCFExecuteRegion(LoopOp loopOp, |
| 350 | RewriterBase &rewriter) { |
| 351 | assert(loopOp.getUnstructured() && |
| 352 | "use convertACCLoopToSCFFor for structured loops" ); |
| 353 | assert( |
| 354 | rewriter.getInsertionBlock() && |
| 355 | !loopOp->isProperAncestor(rewriter.getInsertionBlock()->getParentOp()) && |
| 356 | "builder insertion point must not be inside the loop being converted" ); |
| 357 | |
| 358 | IRMapping mapping; |
| 359 | return wrapMultiBlockRegionWithSCFExecuteRegion(region&: loopOp.getRegion(), mapping, |
| 360 | loc: loopOp->getLoc(), rewriter); |
| 361 | } |
| 362 | |
| 363 | void setCollapseCountAttr(Operation *op, uint64_t count) { |
| 364 | op->setDiscardableAttr( |
| 365 | name: getCollapseCountAttrName(), |
| 366 | value: IntegerAttr::get(type: IntegerType::get(context: op->getContext(), width: 64), value: count)); |
| 367 | } |
| 368 | |
| 369 | uint64_t getCollapseCount(Operation *op) { |
| 370 | if (auto attr = |
| 371 | op->getDiscardableAttrOfType<IntegerAttr>(name: getCollapseCountAttrName())) |
| 372 | return attr.getValue().getZExtValue(); |
| 373 | return 1; |
| 374 | } |
| 375 | |
| 376 | } // namespace acc |
| 377 | } // namespace mlir |
| 378 | |