1 //===-- BoxAnalyzer.h -------------------------------------------*- C++ -*-===//
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 #ifndef FORTRAN_LOWER_BOXANALYZER_H
14 #define FORTRAN_LOWER_BOXANALYZER_H
15
16 #include "flang/Evaluate/fold.h"
17 #include "flang/Lower/Support/Utils.h"
18 #include "flang/Optimizer/Dialect/FIRType.h"
19 #include "flang/Optimizer/Support/Matcher.h"
20 #include <optional>
21
22 namespace Fortran::lower {
23
24 //===----------------------------------------------------------------------===//
25 // Classifications of a symbol.
26 //
27 // Each classification is a distinct class and can be used in pattern matching.
28 //===----------------------------------------------------------------------===//
29
30 namespace details {
31
32 using FromBox = std::monostate;
33
34 /// Base class for all box analysis results.
35 struct ScalarSym {
ScalarSymScalarSym36 ScalarSym(const Fortran::semantics::Symbol &sym) : sym{&sym} {}
37 ScalarSym &operator=(const ScalarSym &) = default;
38
symbolScalarSym39 const Fortran::semantics::Symbol &symbol() const { return *sym; }
40
staticSizeScalarSym41 static constexpr bool staticSize() { return true; }
isCharScalarSym42 static constexpr bool isChar() { return false; }
isArrayScalarSym43 static constexpr bool isArray() { return false; }
44
45 private:
46 const Fortran::semantics::Symbol *sym;
47 };
48
49 /// Scalar of dependent type CHARACTER, constant LEN.
50 struct ScalarStaticChar : ScalarSym {
ScalarStaticCharScalarStaticChar51 ScalarStaticChar(const Fortran::semantics::Symbol &sym, int64_t len)
52 : ScalarSym{sym}, len{len} {}
53
charLenScalarStaticChar54 int64_t charLen() const { return len; }
55
isCharScalarStaticChar56 static constexpr bool isChar() { return true; }
57
58 private:
59 int64_t len;
60 };
61
62 /// Scalar of dependent type Derived, constant LEN(s).
63 struct ScalarStaticDerived : ScalarSym {
ScalarStaticDerivedScalarStaticDerived64 ScalarStaticDerived(const Fortran::semantics::Symbol &sym,
65 llvm::SmallVectorImpl<int64_t> &&lens)
66 : ScalarSym{sym}, lens{std::move(lens)} {}
67
68 private:
69 llvm::SmallVector<int64_t> lens;
70 };
71
72 /// Scalar of dependent type CHARACTER, dynamic LEN.
73 struct ScalarDynamicChar : ScalarSym {
ScalarDynamicCharScalarDynamicChar74 ScalarDynamicChar(const Fortran::semantics::Symbol &sym,
75 const Fortran::lower::SomeExpr &len)
76 : ScalarSym{sym}, len{len} {}
ScalarDynamicCharScalarDynamicChar77 ScalarDynamicChar(const Fortran::semantics::Symbol &sym)
78 : ScalarSym{sym}, len{FromBox{}} {}
79
charLenScalarDynamicChar80 std::optional<Fortran::lower::SomeExpr> charLen() const {
81 if (auto *l = std::get_if<Fortran::lower::SomeExpr>(&len))
82 return {*l};
83 return std::nullopt;
84 }
85
staticSizeScalarDynamicChar86 static constexpr bool staticSize() { return false; }
isCharScalarDynamicChar87 static constexpr bool isChar() { return true; }
88
89 private:
90 std::variant<FromBox, Fortran::lower::SomeExpr> len;
91 };
92
93 /// Scalar of dependent type Derived, dynamic LEN(s).
94 struct ScalarDynamicDerived : ScalarSym {
ScalarDynamicDerivedScalarDynamicDerived95 ScalarDynamicDerived(const Fortran::semantics::Symbol &sym,
96 llvm::SmallVectorImpl<Fortran::lower::SomeExpr> &&lens)
97 : ScalarSym{sym}, lens{std::move(lens)} {}
98
99 private:
100 llvm::SmallVector<Fortran::lower::SomeExpr, 1> lens;
101 };
102
103 struct LBoundsAndShape {
LBoundsAndShapeLBoundsAndShape104 LBoundsAndShape(llvm::SmallVectorImpl<int64_t> &&lbounds,
105 llvm::SmallVectorImpl<int64_t> &&shapes)
106 : lbounds{std::move(lbounds)}, shapes{std::move(shapes)} {}
107
staticSizeLBoundsAndShape108 static constexpr bool staticSize() { return true; }
isArrayLBoundsAndShape109 static constexpr bool isArray() { return true; }
lboundAllOnesLBoundsAndShape110 bool lboundAllOnes() const {
111 return llvm::all_of(lbounds, [](int64_t v) { return v == 1; });
112 }
113
114 llvm::SmallVector<int64_t> lbounds;
115 llvm::SmallVector<int64_t> shapes;
116 };
117
118 /// Array of T with statically known origin (lbounds) and shape.
119 struct StaticArray : ScalarSym, LBoundsAndShape {
StaticArrayStaticArray120 StaticArray(const Fortran::semantics::Symbol &sym,
121 llvm::SmallVectorImpl<int64_t> &&lbounds,
122 llvm::SmallVectorImpl<int64_t> &&shapes)
123 : ScalarSym{sym}, LBoundsAndShape{std::move(lbounds), std::move(shapes)} {
124 }
125
staticSizeStaticArray126 static constexpr bool staticSize() { return LBoundsAndShape::staticSize(); }
127 };
128
129 struct DynamicBound {
DynamicBoundDynamicBound130 DynamicBound(
131 llvm::SmallVectorImpl<const Fortran::semantics::ShapeSpec *> &&bounds)
132 : bounds{std::move(bounds)} {}
133
staticSizeDynamicBound134 static constexpr bool staticSize() { return false; }
isArrayDynamicBound135 static constexpr bool isArray() { return true; }
lboundAllOnesDynamicBound136 bool lboundAllOnes() const {
137 return llvm::all_of(bounds, [](const Fortran::semantics::ShapeSpec *p) {
138 if (auto low = p->lbound().GetExplicit())
139 if (auto lb = Fortran::evaluate::ToInt64(*low))
140 return *lb == 1;
141 return false;
142 });
143 }
144
145 llvm::SmallVector<const Fortran::semantics::ShapeSpec *> bounds;
146 };
147
148 /// Array of T with dynamic origin and/or shape.
149 struct DynamicArray : ScalarSym, DynamicBound {
DynamicArrayDynamicArray150 DynamicArray(
151 const Fortran::semantics::Symbol &sym,
152 llvm::SmallVectorImpl<const Fortran::semantics::ShapeSpec *> &&bounds)
153 : ScalarSym{sym}, DynamicBound{std::move(bounds)} {}
154
staticSizeDynamicArray155 static constexpr bool staticSize() { return DynamicBound::staticSize(); }
156 };
157
158 /// Array of CHARACTER with statically known LEN, origin, and shape.
159 struct StaticArrayStaticChar : ScalarStaticChar, LBoundsAndShape {
StaticArrayStaticCharStaticArrayStaticChar160 StaticArrayStaticChar(const Fortran::semantics::Symbol &sym, int64_t len,
161 llvm::SmallVectorImpl<int64_t> &&lbounds,
162 llvm::SmallVectorImpl<int64_t> &&shapes)
163 : ScalarStaticChar{sym, len}, LBoundsAndShape{std::move(lbounds),
164 std::move(shapes)} {}
165
staticSizeStaticArrayStaticChar166 static constexpr bool staticSize() {
167 return ScalarStaticChar::staticSize() && LBoundsAndShape::staticSize();
168 }
169 };
170
171 /// Array of CHARACTER with dynamic LEN but constant origin, shape.
172 struct StaticArrayDynamicChar : ScalarDynamicChar, LBoundsAndShape {
StaticArrayDynamicCharStaticArrayDynamicChar173 StaticArrayDynamicChar(const Fortran::semantics::Symbol &sym,
174 const Fortran::lower::SomeExpr &len,
175 llvm::SmallVectorImpl<int64_t> &&lbounds,
176 llvm::SmallVectorImpl<int64_t> &&shapes)
177 : ScalarDynamicChar{sym, len}, LBoundsAndShape{std::move(lbounds),
178 std::move(shapes)} {}
StaticArrayDynamicCharStaticArrayDynamicChar179 StaticArrayDynamicChar(const Fortran::semantics::Symbol &sym,
180 llvm::SmallVectorImpl<int64_t> &&lbounds,
181 llvm::SmallVectorImpl<int64_t> &&shapes)
182 : ScalarDynamicChar{sym}, LBoundsAndShape{std::move(lbounds),
183 std::move(shapes)} {}
184
staticSizeStaticArrayDynamicChar185 static constexpr bool staticSize() {
186 return ScalarDynamicChar::staticSize() && LBoundsAndShape::staticSize();
187 }
188 };
189
190 /// Array of CHARACTER with constant LEN but dynamic origin, shape.
191 struct DynamicArrayStaticChar : ScalarStaticChar, DynamicBound {
DynamicArrayStaticCharDynamicArrayStaticChar192 DynamicArrayStaticChar(
193 const Fortran::semantics::Symbol &sym, int64_t len,
194 llvm::SmallVectorImpl<const Fortran::semantics::ShapeSpec *> &&bounds)
195 : ScalarStaticChar{sym, len}, DynamicBound{std::move(bounds)} {}
196
staticSizeDynamicArrayStaticChar197 static constexpr bool staticSize() {
198 return ScalarStaticChar::staticSize() && DynamicBound::staticSize();
199 }
200 };
201
202 /// Array of CHARACTER with dynamic LEN, origin, and shape.
203 struct DynamicArrayDynamicChar : ScalarDynamicChar, DynamicBound {
DynamicArrayDynamicCharDynamicArrayDynamicChar204 DynamicArrayDynamicChar(
205 const Fortran::semantics::Symbol &sym,
206 const Fortran::lower::SomeExpr &len,
207 llvm::SmallVectorImpl<const Fortran::semantics::ShapeSpec *> &&bounds)
208 : ScalarDynamicChar{sym, len}, DynamicBound{std::move(bounds)} {}
DynamicArrayDynamicCharDynamicArrayDynamicChar209 DynamicArrayDynamicChar(
210 const Fortran::semantics::Symbol &sym,
211 llvm::SmallVectorImpl<const Fortran::semantics::ShapeSpec *> &&bounds)
212 : ScalarDynamicChar{sym}, DynamicBound{std::move(bounds)} {}
213
staticSizeDynamicArrayDynamicChar214 static constexpr bool staticSize() {
215 return ScalarDynamicChar::staticSize() && DynamicBound::staticSize();
216 }
217 };
218
219 // TODO: Arrays of derived types with LEN(s)...
220
221 } // namespace details
222
symIsChar(const Fortran::semantics::Symbol & sym)223 inline bool symIsChar(const Fortran::semantics::Symbol &sym) {
224 return sym.GetType()->category() ==
225 Fortran::semantics::DeclTypeSpec::Character;
226 }
227
symIsArray(const Fortran::semantics::Symbol & sym)228 inline bool symIsArray(const Fortran::semantics::Symbol &sym) {
229 const auto *det =
230 sym.GetUltimate().detailsIf<Fortran::semantics::ObjectEntityDetails>();
231 return det && det->IsArray();
232 }
233
isExplicitShape(const Fortran::semantics::Symbol & sym)234 inline bool isExplicitShape(const Fortran::semantics::Symbol &sym) {
235 const auto *det =
236 sym.GetUltimate().detailsIf<Fortran::semantics::ObjectEntityDetails>();
237 return det && det->IsArray() && det->shape().IsExplicitShape();
238 }
239
isAssumedSize(const Fortran::semantics::Symbol & sym)240 inline bool isAssumedSize(const Fortran::semantics::Symbol &sym) {
241 return Fortran::semantics::IsAssumedSizeArray(sym.GetUltimate());
242 }
243
244 //===----------------------------------------------------------------------===//
245 // Perform analysis to determine a box's parameter values
246 //===----------------------------------------------------------------------===//
247
248 /// Analyze a symbol, classify it as to whether it just a scalar, a CHARACTER
249 /// scalar, an array entity, a combination thereof, and whether the LEN, shape,
250 /// and lbounds are constant or not.
251 class BoxAnalyzer : public fir::details::matcher<BoxAnalyzer> {
252 public:
253 // Analysis default state
254 using None = std::monostate;
255
256 using ScalarSym = details::ScalarSym;
257 using ScalarStaticChar = details::ScalarStaticChar;
258 using ScalarDynamicChar = details::ScalarDynamicChar;
259 using StaticArray = details::StaticArray;
260 using DynamicArray = details::DynamicArray;
261 using StaticArrayStaticChar = details::StaticArrayStaticChar;
262 using StaticArrayDynamicChar = details::StaticArrayDynamicChar;
263 using DynamicArrayStaticChar = details::DynamicArrayStaticChar;
264 using DynamicArrayDynamicChar = details::DynamicArrayDynamicChar;
265 // TODO: derived types
266
267 using VT = std::variant<None, ScalarSym, ScalarStaticChar, ScalarDynamicChar,
268 StaticArray, DynamicArray, StaticArrayStaticChar,
269 StaticArrayDynamicChar, DynamicArrayStaticChar,
270 DynamicArrayDynamicChar>;
271
272 //===--------------------------------------------------------------------===//
273 // Constructor
274 //===--------------------------------------------------------------------===//
275
BoxAnalyzer()276 BoxAnalyzer() : box{None{}} {}
277
278 operator bool() const { return !std::holds_alternative<None>(box); }
279
isTrivial()280 bool isTrivial() const { return std::holds_alternative<ScalarSym>(box); }
281
282 /// Returns true for any sort of CHARACTER.
isChar()283 bool isChar() const {
284 return match([](const ScalarStaticChar &) { return true; },
285 [](const ScalarDynamicChar &) { return true; },
286 [](const StaticArrayStaticChar &) { return true; },
287 [](const StaticArrayDynamicChar &) { return true; },
288 [](const DynamicArrayStaticChar &) { return true; },
289 [](const DynamicArrayDynamicChar &) { return true; },
290 [](const auto &) { return false; });
291 }
292
293 /// Returns true for any sort of array.
isArray()294 bool isArray() const {
295 return match([](const StaticArray &) { return true; },
296 [](const DynamicArray &) { return true; },
297 [](const StaticArrayStaticChar &) { return true; },
298 [](const StaticArrayDynamicChar &) { return true; },
299 [](const DynamicArrayStaticChar &) { return true; },
300 [](const DynamicArrayDynamicChar &) { return true; },
301 [](const auto &) { return false; });
302 }
303
304 /// Returns true iff this is an array with constant extents and lbounds. This
305 /// returns true for arrays of CHARACTER, even if the LEN is not a constant.
isStaticArray()306 bool isStaticArray() const {
307 return match([](const StaticArray &) { return true; },
308 [](const StaticArrayStaticChar &) { return true; },
309 [](const StaticArrayDynamicChar &) { return true; },
310 [](const auto &) { return false; });
311 }
312
isConstant()313 bool isConstant() const {
314 return match(
315 [](const None &) -> bool {
316 llvm::report_fatal_error("internal: analysis failed");
317 },
318 [](const auto &x) { return x.staticSize(); });
319 }
320
getCharLenConst()321 std::optional<int64_t> getCharLenConst() const {
322 using A = std::optional<int64_t>;
323 return match(
324 [](const ScalarStaticChar &x) -> A { return {x.charLen()}; },
325 [](const StaticArrayStaticChar &x) -> A { return {x.charLen()}; },
326 [](const DynamicArrayStaticChar &x) -> A { return {x.charLen()}; },
327 [](const auto &) -> A { return std::nullopt; });
328 }
329
getCharLenExpr()330 std::optional<Fortran::lower::SomeExpr> getCharLenExpr() const {
331 using A = std::optional<Fortran::lower::SomeExpr>;
332 return match([](const ScalarDynamicChar &x) { return x.charLen(); },
333 [](const StaticArrayDynamicChar &x) { return x.charLen(); },
334 [](const DynamicArrayDynamicChar &x) { return x.charLen(); },
335 [](const auto &) -> A { return std::nullopt; });
336 }
337
338 /// Is the origin of this array the default of vector of `1`?
lboundIsAllOnes()339 bool lboundIsAllOnes() const {
340 return match(
341 [&](const StaticArray &x) { return x.lboundAllOnes(); },
342 [&](const DynamicArray &x) { return x.lboundAllOnes(); },
343 [&](const StaticArrayStaticChar &x) { return x.lboundAllOnes(); },
344 [&](const StaticArrayDynamicChar &x) { return x.lboundAllOnes(); },
345 [&](const DynamicArrayStaticChar &x) { return x.lboundAllOnes(); },
346 [&](const DynamicArrayDynamicChar &x) { return x.lboundAllOnes(); },
347 [](const auto &) -> bool { llvm::report_fatal_error("not an array"); });
348 }
349
350 /// Get the static lbound values (the origin of the array).
staticLBound()351 llvm::ArrayRef<int64_t> staticLBound() const {
352 using A = llvm::ArrayRef<int64_t>;
353 return match([](const StaticArray &x) -> A { return x.lbounds; },
354 [](const StaticArrayStaticChar &x) -> A { return x.lbounds; },
355 [](const StaticArrayDynamicChar &x) -> A { return x.lbounds; },
356 [](const auto &) -> A {
357 llvm::report_fatal_error("does not have static lbounds");
358 });
359 }
360
361 /// Get the static extents of the array.
staticShape()362 llvm::ArrayRef<int64_t> staticShape() const {
363 using A = llvm::ArrayRef<int64_t>;
364 return match([](const StaticArray &x) -> A { return x.shapes; },
365 [](const StaticArrayStaticChar &x) -> A { return x.shapes; },
366 [](const StaticArrayDynamicChar &x) -> A { return x.shapes; },
367 [](const auto &) -> A {
368 llvm::report_fatal_error("does not have static shape");
369 });
370 }
371
372 /// Get the dynamic bounds information of the array (both origin, shape).
dynamicBound()373 llvm::ArrayRef<const Fortran::semantics::ShapeSpec *> dynamicBound() const {
374 using A = llvm::ArrayRef<const Fortran::semantics::ShapeSpec *>;
375 return match([](const DynamicArray &x) -> A { return x.bounds; },
376 [](const DynamicArrayStaticChar &x) -> A { return x.bounds; },
377 [](const DynamicArrayDynamicChar &x) -> A { return x.bounds; },
378 [](const auto &) -> A {
379 llvm::report_fatal_error("does not have bounds");
380 });
381 }
382
383 /// Run the analysis on `sym`.
analyze(const Fortran::semantics::Symbol & sym)384 void analyze(const Fortran::semantics::Symbol &sym) {
385 if (Fortran::semantics::IsProcedurePointer(sym))
386 return;
387 if (symIsArray(sym)) {
388 bool isConstant = !isAssumedSize(sym);
389 llvm::SmallVector<int64_t> lbounds;
390 llvm::SmallVector<int64_t> shapes;
391 llvm::SmallVector<const Fortran::semantics::ShapeSpec *> bounds;
392 for (const Fortran::semantics::ShapeSpec &subs : getSymShape(sym)) {
393 bounds.push_back(&subs);
394 if (!isConstant)
395 continue;
396 if (auto low = subs.lbound().GetExplicit()) {
397 if (auto lb = Fortran::evaluate::ToInt64(*low)) {
398 lbounds.push_back(*lb); // origin for this dim
399 if (auto high = subs.ubound().GetExplicit()) {
400 if (auto ub = Fortran::evaluate::ToInt64(*high)) {
401 int64_t extent = *ub - *lb + 1;
402 shapes.push_back(extent < 0 ? 0 : extent);
403 continue;
404 }
405 } else if (subs.ubound().isStar()) {
406 assert(Fortran::semantics::IsNamedConstant(sym) &&
407 "expect implied shape constant");
408 shapes.push_back(fir::SequenceType::getUnknownExtent());
409 continue;
410 }
411 }
412 }
413 isConstant = false;
414 }
415
416 // sym : array<CHARACTER>
417 if (symIsChar(sym)) {
418 if (auto len = charLenConstant(sym)) {
419 if (isConstant)
420 box = StaticArrayStaticChar(sym, *len, std::move(lbounds),
421 std::move(shapes));
422 else
423 box = DynamicArrayStaticChar(sym, *len, std::move(bounds));
424 return;
425 }
426 if (auto var = charLenVariable(sym)) {
427 if (isConstant)
428 box = StaticArrayDynamicChar(sym, *var, std::move(lbounds),
429 std::move(shapes));
430 else
431 box = DynamicArrayDynamicChar(sym, *var, std::move(bounds));
432 return;
433 }
434 if (isConstant)
435 box = StaticArrayDynamicChar(sym, std::move(lbounds),
436 std::move(shapes));
437 else
438 box = DynamicArrayDynamicChar(sym, std::move(bounds));
439 return;
440 }
441
442 // sym : array<other>
443 if (isConstant)
444 box = StaticArray(sym, std::move(lbounds), std::move(shapes));
445 else
446 box = DynamicArray(sym, std::move(bounds));
447 return;
448 }
449
450 // sym : CHARACTER
451 if (symIsChar(sym)) {
452 if (auto len = charLenConstant(sym))
453 box = ScalarStaticChar(sym, *len);
454 else if (auto var = charLenVariable(sym))
455 box = ScalarDynamicChar(sym, *var);
456 else
457 box = ScalarDynamicChar(sym);
458 return;
459 }
460
461 // sym : other
462 box = ScalarSym(sym);
463 }
464
matchee()465 const VT &matchee() const { return box; }
466
467 private:
468 // Get the shape of a symbol.
469 const Fortran::semantics::ArraySpec &
getSymShape(const Fortran::semantics::Symbol & sym)470 getSymShape(const Fortran::semantics::Symbol &sym) {
471 return sym.GetUltimate()
472 .get<Fortran::semantics::ObjectEntityDetails>()
473 .shape();
474 }
475
476 // Get the constant LEN of a CHARACTER, if it exists.
477 std::optional<int64_t>
charLenConstant(const Fortran::semantics::Symbol & sym)478 charLenConstant(const Fortran::semantics::Symbol &sym) {
479 if (std::optional<Fortran::lower::SomeExpr> expr = charLenVariable(sym))
480 if (std::optional<int64_t> asInt = Fortran::evaluate::ToInt64(*expr)) {
481 // Length is max(0, *asInt) (F2018 7.4.4.2 point 5.).
482 if (*asInt < 0)
483 return 0;
484 return *asInt;
485 }
486 return std::nullopt;
487 }
488
489 // Get the `SomeExpr` that describes the CHARACTER's LEN.
490 std::optional<Fortran::lower::SomeExpr>
charLenVariable(const Fortran::semantics::Symbol & sym)491 charLenVariable(const Fortran::semantics::Symbol &sym) {
492 const Fortran::semantics::ParamValue &lenParam =
493 sym.GetType()->characterTypeSpec().length();
494 if (Fortran::semantics::MaybeIntExpr expr = lenParam.GetExplicit())
495 return {Fortran::evaluate::AsGenericExpr(std::move(*expr))};
496 // For assumed LEN parameters, the length comes from the initialization
497 // expression.
498 if (sym.attrs().test(Fortran::semantics::Attr::PARAMETER))
499 if (const auto *objectDetails =
500 sym.GetUltimate()
501 .detailsIf<Fortran::semantics::ObjectEntityDetails>())
502 if (objectDetails->init())
503 if (const auto *charExpr = std::get_if<
504 Fortran::evaluate::Expr<Fortran::evaluate::SomeCharacter>>(
505 &objectDetails->init()->u))
506 if (Fortran::semantics::MaybeSubscriptIntExpr expr =
507 charExpr->LEN())
508 return {Fortran::evaluate::AsGenericExpr(std::move(*expr))};
509 return std::nullopt;
510 }
511
512 VT box;
513 }; // namespace Fortran::lower
514
515 } // namespace Fortran::lower
516
517 #endif // FORTRAN_LOWER_BOXANALYZER_H
518