1 //===-- CodeGen.cpp -- bridge to lower to LLVM ----------------------------===//
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 // Coding style: https://mlir.llvm.org/getting_started/DeveloperGuide/
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "flang/Optimizer/CodeGen/CodeGen.h"
14 #include "PassDetail.h"
15 #include "flang/Optimizer/Dialect/FIROps.h"
16 #include "flang/Optimizer/Dialect/FIRType.h"
17 #include "mlir/Conversion/ArithmeticToLLVM/ArithmeticToLLVM.h"
18 #include "mlir/Conversion/LLVMCommon/Pattern.h"
19 #include "mlir/Conversion/LLVMCommon/TypeConverter.h"
20 #include "mlir/Conversion/StandardToLLVM/ConvertStandardToLLVM.h"
21 #include "mlir/IR/BuiltinTypes.h"
22 #include "mlir/IR/Matchers.h"
23 #include "mlir/Pass/Pass.h"
24 #include "llvm/ADT/ArrayRef.h"
25 
26 #define DEBUG_TYPE "flang-codegen"
27 
28 // fir::LLVMTypeConverter for converting to LLVM IR dialect types.
29 #include "TypeConverter.h"
30 
31 namespace {
32 /// FIR conversion pattern template
33 template <typename FromOp>
34 class FIROpConversion : public mlir::ConvertOpToLLVMPattern<FromOp> {
35 public:
36   explicit FIROpConversion(fir::LLVMTypeConverter &lowering)
37       : mlir::ConvertOpToLLVMPattern<FromOp>(lowering) {}
38 
39 protected:
40   mlir::Type convertType(mlir::Type ty) const {
41     return lowerTy().convertType(ty);
42   }
43 
44   fir::LLVMTypeConverter &lowerTy() const {
45     return *static_cast<fir::LLVMTypeConverter *>(this->getTypeConverter());
46   }
47 };
48 
49 /// FIR conversion pattern template
50 template <typename FromOp>
51 class FIROpAndTypeConversion : public FIROpConversion<FromOp> {
52 public:
53   using FIROpConversion<FromOp>::FIROpConversion;
54   using OpAdaptor = typename FromOp::Adaptor;
55 
56   mlir::LogicalResult
57   matchAndRewrite(FromOp op, OpAdaptor adaptor,
58                   mlir::ConversionPatternRewriter &rewriter) const final {
59     mlir::Type ty = this->convertType(op.getType());
60     return doRewrite(op, ty, adaptor, rewriter);
61   }
62 
63   virtual mlir::LogicalResult
64   doRewrite(FromOp addr, mlir::Type ty, OpAdaptor adaptor,
65             mlir::ConversionPatternRewriter &rewriter) const = 0;
66 };
67 
68 // Lower `fir.address_of` operation to `llvm.address_of` operation.
69 struct AddrOfOpConversion : public FIROpConversion<fir::AddrOfOp> {
70   using FIROpConversion::FIROpConversion;
71 
72   mlir::LogicalResult
73   matchAndRewrite(fir::AddrOfOp addr, OpAdaptor adaptor,
74                   mlir::ConversionPatternRewriter &rewriter) const override {
75     auto ty = convertType(addr.getType());
76     rewriter.replaceOpWithNewOp<mlir::LLVM::AddressOfOp>(
77         addr, ty, addr.symbol().getRootReference().getValue());
78     return success();
79   }
80 };
81 
82 /// Lower `fir.has_value` operation to `llvm.return` operation.
83 struct HasValueOpConversion : public FIROpConversion<fir::HasValueOp> {
84   using FIROpConversion::FIROpConversion;
85 
86   mlir::LogicalResult
87   matchAndRewrite(fir::HasValueOp op, OpAdaptor adaptor,
88                   mlir::ConversionPatternRewriter &rewriter) const override {
89     rewriter.replaceOpWithNewOp<LLVM::ReturnOp>(op, adaptor.getOperands());
90     return success();
91   }
92 };
93 
94 /// Lower `fir.global` operation to `llvm.global` operation.
95 /// `fir.insert_on_range` operations are replaced with constant dense attribute
96 /// if they are applied on the full range.
97 struct GlobalOpConversion : public FIROpConversion<fir::GlobalOp> {
98   using FIROpConversion::FIROpConversion;
99 
100   mlir::LogicalResult
101   matchAndRewrite(fir::GlobalOp global, OpAdaptor adaptor,
102                   mlir::ConversionPatternRewriter &rewriter) const override {
103     auto tyAttr = convertType(global.getType());
104     if (global.getType().isa<fir::BoxType>())
105       tyAttr = tyAttr.cast<mlir::LLVM::LLVMPointerType>().getElementType();
106     auto loc = global.getLoc();
107     mlir::Attribute initAttr{};
108     if (global.initVal())
109       initAttr = global.initVal().getValue();
110     auto linkage = convertLinkage(global.linkName());
111     auto isConst = global.constant().hasValue();
112     auto g = rewriter.create<mlir::LLVM::GlobalOp>(
113         loc, tyAttr, isConst, linkage, global.sym_name(), initAttr);
114     auto &gr = g.getInitializerRegion();
115     rewriter.inlineRegionBefore(global.region(), gr, gr.end());
116     if (!gr.empty()) {
117       // Replace insert_on_range with a constant dense attribute if the
118       // initialization is on the full range.
119       auto insertOnRangeOps = gr.front().getOps<fir::InsertOnRangeOp>();
120       for (auto insertOp : insertOnRangeOps) {
121         if (isFullRange(insertOp.coor(), insertOp.getType())) {
122           auto seqTyAttr = convertType(insertOp.getType());
123           auto *op = insertOp.val().getDefiningOp();
124           auto constant = mlir::dyn_cast<mlir::arith::ConstantOp>(op);
125           if (!constant) {
126             auto convertOp = mlir::dyn_cast<fir::ConvertOp>(op);
127             if (!convertOp)
128               continue;
129             constant = cast<mlir::arith::ConstantOp>(
130                 convertOp.value().getDefiningOp());
131           }
132           mlir::Type vecType = mlir::VectorType::get(
133               insertOp.getType().getShape(), constant.getType());
134           auto denseAttr = mlir::DenseElementsAttr::get(
135               vecType.cast<ShapedType>(), constant.value());
136           rewriter.setInsertionPointAfter(insertOp);
137           rewriter.replaceOpWithNewOp<mlir::arith::ConstantOp>(
138               insertOp, seqTyAttr, denseAttr);
139         }
140       }
141     }
142     rewriter.eraseOp(global);
143     return success();
144   }
145 
146   bool isFullRange(mlir::ArrayAttr indexes, fir::SequenceType seqTy) const {
147     auto extents = seqTy.getShape();
148     if (indexes.size() / 2 != extents.size())
149       return false;
150     for (unsigned i = 0; i < indexes.size(); i += 2) {
151       if (indexes[i].cast<IntegerAttr>().getInt() != 0)
152         return false;
153       if (indexes[i + 1].cast<IntegerAttr>().getInt() != extents[i / 2] - 1)
154         return false;
155     }
156     return true;
157   }
158 
159   // TODO: String comparaison should be avoided. Replace linkName with an
160   // enumeration.
161   mlir::LLVM::Linkage convertLinkage(Optional<StringRef> optLinkage) const {
162     if (optLinkage.hasValue()) {
163       auto name = optLinkage.getValue();
164       if (name == "internal")
165         return mlir::LLVM::Linkage::Internal;
166       if (name == "linkonce")
167         return mlir::LLVM::Linkage::Linkonce;
168       if (name == "common")
169         return mlir::LLVM::Linkage::Common;
170       if (name == "weak")
171         return mlir::LLVM::Linkage::Weak;
172     }
173     return mlir::LLVM::Linkage::External;
174   }
175 };
176 
177 template <typename OP>
178 void selectMatchAndRewrite(fir::LLVMTypeConverter &lowering, OP select,
179                            typename OP::Adaptor adaptor,
180                            mlir::ConversionPatternRewriter &rewriter) {
181   unsigned conds = select.getNumConditions();
182   auto cases = select.getCases().getValue();
183   mlir::Value selector = adaptor.selector();
184   auto loc = select.getLoc();
185   assert(conds > 0 && "select must have cases");
186 
187   llvm::SmallVector<mlir::Block *> destinations;
188   llvm::SmallVector<mlir::ValueRange> destinationsOperands;
189   mlir::Block *defaultDestination;
190   mlir::ValueRange defaultOperands;
191   llvm::SmallVector<int32_t> caseValues;
192 
193   for (unsigned t = 0; t != conds; ++t) {
194     mlir::Block *dest = select.getSuccessor(t);
195     auto destOps = select.getSuccessorOperands(adaptor.getOperands(), t);
196     const mlir::Attribute &attr = cases[t];
197     if (auto intAttr = attr.template dyn_cast<mlir::IntegerAttr>()) {
198       destinations.push_back(dest);
199       destinationsOperands.push_back(destOps.hasValue() ? *destOps
200                                                         : ValueRange());
201       caseValues.push_back(intAttr.getInt());
202       continue;
203     }
204     assert(attr.template dyn_cast_or_null<mlir::UnitAttr>());
205     assert((t + 1 == conds) && "unit must be last");
206     defaultDestination = dest;
207     defaultOperands = destOps.hasValue() ? *destOps : ValueRange();
208   }
209 
210   // LLVM::SwitchOp takes a i32 type for the selector.
211   if (select.getSelector().getType() != rewriter.getI32Type())
212     selector =
213         rewriter.create<LLVM::TruncOp>(loc, rewriter.getI32Type(), selector);
214 
215   rewriter.replaceOpWithNewOp<mlir::LLVM::SwitchOp>(
216       select, selector,
217       /*defaultDestination=*/defaultDestination,
218       /*defaultOperands=*/defaultOperands,
219       /*caseValues=*/caseValues,
220       /*caseDestinations=*/destinations,
221       /*caseOperands=*/destinationsOperands,
222       /*branchWeights=*/ArrayRef<int32_t>());
223 }
224 
225 /// conversion of fir::SelectOp to an if-then-else ladder
226 struct SelectOpConversion : public FIROpConversion<fir::SelectOp> {
227   using FIROpConversion::FIROpConversion;
228 
229   mlir::LogicalResult
230   matchAndRewrite(fir::SelectOp op, OpAdaptor adaptor,
231                   mlir::ConversionPatternRewriter &rewriter) const override {
232     selectMatchAndRewrite<fir::SelectOp>(lowerTy(), op, adaptor, rewriter);
233     return success();
234   }
235 };
236 
237 /// conversion of fir::SelectRankOp to an if-then-else ladder
238 struct SelectRankOpConversion : public FIROpConversion<fir::SelectRankOp> {
239   using FIROpConversion::FIROpConversion;
240 
241   mlir::LogicalResult
242   matchAndRewrite(fir::SelectRankOp op, OpAdaptor adaptor,
243                   mlir::ConversionPatternRewriter &rewriter) const override {
244     selectMatchAndRewrite<fir::SelectRankOp>(lowerTy(), op, adaptor, rewriter);
245     return success();
246   }
247 };
248 
249 // convert to LLVM IR dialect `undef`
250 struct UndefOpConversion : public FIROpConversion<fir::UndefOp> {
251   using FIROpConversion::FIROpConversion;
252 
253   mlir::LogicalResult
254   matchAndRewrite(fir::UndefOp undef, OpAdaptor,
255                   mlir::ConversionPatternRewriter &rewriter) const override {
256     rewriter.replaceOpWithNewOp<mlir::LLVM::UndefOp>(
257         undef, convertType(undef.getType()));
258     return success();
259   }
260 };
261 
262 // convert to LLVM IR dialect `unreachable`
263 struct UnreachableOpConversion : public FIROpConversion<fir::UnreachableOp> {
264   using FIROpConversion::FIROpConversion;
265 
266   mlir::LogicalResult
267   matchAndRewrite(fir::UnreachableOp unreach, OpAdaptor adaptor,
268                   mlir::ConversionPatternRewriter &rewriter) const override {
269     rewriter.replaceOpWithNewOp<mlir::LLVM::UnreachableOp>(unreach);
270     return success();
271   }
272 };
273 
274 struct ZeroOpConversion : public FIROpConversion<fir::ZeroOp> {
275   using FIROpConversion::FIROpConversion;
276 
277   mlir::LogicalResult
278   matchAndRewrite(fir::ZeroOp zero, OpAdaptor,
279                   mlir::ConversionPatternRewriter &rewriter) const override {
280     auto ty = convertType(zero.getType());
281     if (ty.isa<mlir::LLVM::LLVMPointerType>()) {
282       rewriter.replaceOpWithNewOp<mlir::LLVM::NullOp>(zero, ty);
283     } else if (ty.isa<mlir::IntegerType>()) {
284       rewriter.replaceOpWithNewOp<mlir::LLVM::ConstantOp>(
285           zero, ty, mlir::IntegerAttr::get(zero.getType(), 0));
286     } else if (mlir::LLVM::isCompatibleFloatingPointType(ty)) {
287       rewriter.replaceOpWithNewOp<mlir::LLVM::ConstantOp>(
288           zero, ty, mlir::FloatAttr::get(zero.getType(), 0.0));
289     } else {
290       // TODO: create ConstantAggregateZero for FIR aggregate/array types.
291       return rewriter.notifyMatchFailure(
292           zero,
293           "conversion of fir.zero with aggregate type not implemented yet");
294     }
295     return success();
296   }
297 };
298 
299 // Code shared between insert_value and extract_value Ops.
300 struct ValueOpCommon {
301   // Translate the arguments pertaining to any multidimensional array to
302   // row-major order for LLVM-IR.
303   static void toRowMajor(SmallVectorImpl<mlir::Attribute> &attrs,
304                          mlir::Type ty) {
305     assert(ty && "type is null");
306     const auto end = attrs.size();
307     for (std::remove_const_t<decltype(end)> i = 0; i < end; ++i) {
308       if (auto seq = ty.dyn_cast<mlir::LLVM::LLVMArrayType>()) {
309         const auto dim = getDimension(seq);
310         if (dim > 1) {
311           auto ub = std::min(i + dim, end);
312           std::reverse(attrs.begin() + i, attrs.begin() + ub);
313           i += dim - 1;
314         }
315         ty = getArrayElementType(seq);
316       } else if (auto st = ty.dyn_cast<mlir::LLVM::LLVMStructType>()) {
317         ty = st.getBody()[attrs[i].cast<mlir::IntegerAttr>().getInt()];
318       } else {
319         llvm_unreachable("index into invalid type");
320       }
321     }
322   }
323 
324   static llvm::SmallVector<mlir::Attribute>
325   collectIndices(mlir::ConversionPatternRewriter &rewriter,
326                  mlir::ArrayAttr arrAttr) {
327     llvm::SmallVector<mlir::Attribute> attrs;
328     for (auto i = arrAttr.begin(), e = arrAttr.end(); i != e; ++i) {
329       if (i->isa<mlir::IntegerAttr>()) {
330         attrs.push_back(*i);
331       } else {
332         auto fieldName = i->cast<mlir::StringAttr>().getValue();
333         ++i;
334         auto ty = i->cast<mlir::TypeAttr>().getValue();
335         auto index = ty.cast<fir::RecordType>().getFieldIndex(fieldName);
336         attrs.push_back(mlir::IntegerAttr::get(rewriter.getI32Type(), index));
337       }
338     }
339     return attrs;
340   }
341 
342 private:
343   static unsigned getDimension(mlir::LLVM::LLVMArrayType ty) {
344     unsigned result = 1;
345     for (auto eleTy = ty.getElementType().dyn_cast<mlir::LLVM::LLVMArrayType>();
346          eleTy;
347          eleTy = eleTy.getElementType().dyn_cast<mlir::LLVM::LLVMArrayType>())
348       ++result;
349     return result;
350   }
351 
352   static mlir::Type getArrayElementType(mlir::LLVM::LLVMArrayType ty) {
353     auto eleTy = ty.getElementType();
354     while (auto arrTy = eleTy.dyn_cast<mlir::LLVM::LLVMArrayType>())
355       eleTy = arrTy.getElementType();
356     return eleTy;
357   }
358 };
359 
360 /// Extract a subobject value from an ssa-value of aggregate type
361 struct ExtractValueOpConversion
362     : public FIROpAndTypeConversion<fir::ExtractValueOp>,
363       public ValueOpCommon {
364   using FIROpAndTypeConversion::FIROpAndTypeConversion;
365 
366   mlir::LogicalResult
367   doRewrite(fir::ExtractValueOp extractVal, mlir::Type ty, OpAdaptor adaptor,
368             mlir::ConversionPatternRewriter &rewriter) const override {
369     auto attrs = collectIndices(rewriter, extractVal.coor());
370     toRowMajor(attrs, adaptor.getOperands()[0].getType());
371     auto position = mlir::ArrayAttr::get(extractVal.getContext(), attrs);
372     rewriter.replaceOpWithNewOp<mlir::LLVM::ExtractValueOp>(
373         extractVal, ty, adaptor.getOperands()[0], position);
374     return success();
375   }
376 };
377 
378 /// InsertValue is the generalized instruction for the composition of new
379 /// aggregate type values.
380 struct InsertValueOpConversion
381     : public FIROpAndTypeConversion<fir::InsertValueOp>,
382       public ValueOpCommon {
383   using FIROpAndTypeConversion::FIROpAndTypeConversion;
384 
385   mlir::LogicalResult
386   doRewrite(fir::InsertValueOp insertVal, mlir::Type ty, OpAdaptor adaptor,
387             mlir::ConversionPatternRewriter &rewriter) const override {
388     auto attrs = collectIndices(rewriter, insertVal.coor());
389     toRowMajor(attrs, adaptor.getOperands()[0].getType());
390     auto position = mlir::ArrayAttr::get(insertVal.getContext(), attrs);
391     rewriter.replaceOpWithNewOp<mlir::LLVM::InsertValueOp>(
392         insertVal, ty, adaptor.getOperands()[0], adaptor.getOperands()[1],
393         position);
394     return success();
395   }
396 };
397 
398 /// InsertOnRange inserts a value into a sequence over a range of offsets.
399 struct InsertOnRangeOpConversion
400     : public FIROpAndTypeConversion<fir::InsertOnRangeOp> {
401   using FIROpAndTypeConversion::FIROpAndTypeConversion;
402 
403   // Increments an array of subscripts in a row major fasion.
404   void incrementSubscripts(const SmallVector<uint64_t> &dims,
405                            SmallVector<uint64_t> &subscripts) const {
406     for (size_t i = dims.size(); i > 0; --i) {
407       if (++subscripts[i - 1] < dims[i - 1]) {
408         return;
409       }
410       subscripts[i - 1] = 0;
411     }
412   }
413 
414   mlir::LogicalResult
415   doRewrite(fir::InsertOnRangeOp range, mlir::Type ty, OpAdaptor adaptor,
416             mlir::ConversionPatternRewriter &rewriter) const override {
417 
418     llvm::SmallVector<uint64_t> dims;
419     auto type = adaptor.getOperands()[0].getType();
420 
421     // Iteratively extract the array dimensions from the type.
422     while (auto t = type.dyn_cast<mlir::LLVM::LLVMArrayType>()) {
423       dims.push_back(t.getNumElements());
424       type = t.getElementType();
425     }
426 
427     SmallVector<uint64_t> lBounds;
428     SmallVector<uint64_t> uBounds;
429 
430     // Extract integer value from the attribute
431     SmallVector<int64_t> coordinates = llvm::to_vector<4>(
432         llvm::map_range(range.coor(), [](Attribute a) -> int64_t {
433           return a.cast<IntegerAttr>().getInt();
434         }));
435 
436     // Unzip the upper and lower bound and convert to a row major format.
437     for (auto i = coordinates.rbegin(), e = coordinates.rend(); i != e; ++i) {
438       uBounds.push_back(*i++);
439       lBounds.push_back(*i);
440     }
441 
442     auto &subscripts = lBounds;
443     auto loc = range.getLoc();
444     mlir::Value lastOp = adaptor.getOperands()[0];
445     mlir::Value insertVal = adaptor.getOperands()[1];
446 
447     auto i64Ty = rewriter.getI64Type();
448     while (subscripts != uBounds) {
449       // Convert uint64_t's to Attribute's.
450       SmallVector<mlir::Attribute> subscriptAttrs;
451       for (const auto &subscript : subscripts)
452         subscriptAttrs.push_back(IntegerAttr::get(i64Ty, subscript));
453       lastOp = rewriter.create<mlir::LLVM::InsertValueOp>(
454           loc, ty, lastOp, insertVal,
455           ArrayAttr::get(range.getContext(), subscriptAttrs));
456 
457       incrementSubscripts(dims, subscripts);
458     }
459 
460     // Convert uint64_t's to Attribute's.
461     SmallVector<mlir::Attribute> subscriptAttrs;
462     for (const auto &subscript : subscripts)
463       subscriptAttrs.push_back(
464           IntegerAttr::get(rewriter.getI64Type(), subscript));
465     mlir::ArrayRef<mlir::Attribute> arrayRef(subscriptAttrs);
466 
467     rewriter.replaceOpWithNewOp<mlir::LLVM::InsertValueOp>(
468         range, ty, lastOp, insertVal,
469         ArrayAttr::get(range.getContext(), arrayRef));
470 
471     return success();
472   }
473 };
474 } // namespace
475 
476 namespace {
477 /// Convert FIR dialect to LLVM dialect
478 ///
479 /// This pass lowers all FIR dialect operations to LLVM IR dialect. An
480 /// MLIR pass is used to lower residual Std dialect to LLVM IR dialect.
481 ///
482 /// This pass is not complete yet. We are upstreaming it in small patches.
483 class FIRToLLVMLowering : public fir::FIRToLLVMLoweringBase<FIRToLLVMLowering> {
484 public:
485   mlir::ModuleOp getModule() { return getOperation(); }
486 
487   void runOnOperation() override final {
488     auto *context = getModule().getContext();
489     fir::LLVMTypeConverter typeConverter{getModule()};
490     mlir::OwningRewritePatternList pattern(context);
491     pattern.insert<
492         AddrOfOpConversion, ExtractValueOpConversion, HasValueOpConversion,
493         GlobalOpConversion, InsertOnRangeOpConversion, InsertValueOpConversion,
494         SelectOpConversion, SelectRankOpConversion, UndefOpConversion,
495         UnreachableOpConversion, ZeroOpConversion>(typeConverter);
496     mlir::populateStdToLLVMConversionPatterns(typeConverter, pattern);
497     mlir::arith::populateArithmeticToLLVMConversionPatterns(typeConverter,
498                                                             pattern);
499     mlir::ConversionTarget target{*context};
500     target.addLegalDialect<mlir::LLVM::LLVMDialect>();
501 
502     // required NOPs for applying a full conversion
503     target.addLegalOp<mlir::ModuleOp>();
504 
505     // apply the patterns
506     if (mlir::failed(mlir::applyFullConversion(getModule(), target,
507                                                std::move(pattern)))) {
508       signalPassFailure();
509     }
510   }
511 };
512 } // namespace
513 
514 std::unique_ptr<mlir::Pass> fir::createFIRToLLVMPass() {
515   return std::make_unique<FIRToLLVMLowering>();
516 }
517