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