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
26using namespace mlir;
27
28/// Calculate trip count for a loop: (ub - lb + step) / step
29/// If inclusiveUpperbound is false, subtracts 1 from ub first.
30Value 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.
55static 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
68void 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.
90static 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.
103static 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
109namespace mlir {
110namespace acc {
111
112std::pair<SmallVector<Value>, Block::iterator>
113cloneACCRegionInto(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.
157scf::ExecuteRegionOp
158wrapMultiBlockRegionWithSCFExecuteRegion(Region &region, 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
191scf::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
283scf::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
348scf::ExecuteRegionOp
349convertUnstructuredACCLoopToSCFExecuteRegion(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
363void 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
369uint64_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