1 //===----------------------------------------------------------------------===//
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 #include "compute-offsets.h"
10 #include "../../runtime/descriptor.h"
11 #include "flang/Evaluate/fold.h"
12 #include "flang/Evaluate/shape.h"
13 #include "flang/Evaluate/type.h"
14 #include "flang/Semantics/scope.h"
15 #include "flang/Semantics/semantics.h"
16 #include "flang/Semantics/symbol.h"
17 #include "flang/Semantics/tools.h"
18 #include "flang/Semantics/type.h"
19 #include <algorithm>
20 #include <vector>
21 
22 namespace Fortran::semantics {
23 
24 class ComputeOffsetsHelper {
25 public:
26   // TODO: configure based on target
27   static constexpr int maxAlignment{8};
28 
29   ComputeOffsetsHelper(SemanticsContext &context) : context_{context} {}
30   void Compute() { Compute(context_.globalScope()); }
31 
32 private:
33   struct SizeAndAlignment {
34     SizeAndAlignment() {}
35     SizeAndAlignment(std::size_t size) : size{size}, alignment{size} {}
36     SizeAndAlignment(std::size_t size, std::size_t alignment)
37         : size{size}, alignment{alignment} {}
38     std::size_t size{0};
39     std::size_t alignment{0};
40   };
41   struct SymbolAndOffset {
42     Symbol *symbol{nullptr};
43     std::size_t offset{0};
44   };
45 
46   void Compute(Scope &);
47   void DoScope(Scope &);
48   void DoCommonBlock(Symbol &);
49   void DoEquivalenceSet(EquivalenceSet &);
50   std::size_t GetOffset(SymbolAndOffset &);
51   std::size_t ComputeOffset(const EquivalenceObject &);
52   void DoSymbol(Symbol &);
53   SizeAndAlignment GetSizeAndAlignment(const Symbol &);
54   SizeAndAlignment GetElementSize(const Symbol &, bool isSubstring = false);
55   std::size_t CountElements(const Symbol &);
56   static std::size_t Align(std::size_t, std::size_t);
57   static SizeAndAlignment GetIntrinsicSizeAndAlignment(TypeCategory, int);
58 
59   SemanticsContext &context_;
60   evaluate::FoldingContext &foldingContext_{context_.foldingContext()};
61   std::size_t offset_{0};
62   std::size_t alignment_{0};
63   // symbol -> symbol+offset that determines its location, from EQUIVALENCE
64   std::map<MutableSymbolRef, SymbolAndOffset> dependents_;
65 };
66 
67 void ComputeOffsetsHelper::Compute(Scope &scope) {
68   for (Scope &child : scope.children()) {
69     Compute(child);
70   }
71   DoScope(scope);
72 }
73 
74 static bool InCommonBlock(const Symbol &symbol) {
75   const auto *details{symbol.detailsIf<ObjectEntityDetails>()};
76   return details && details->commonBlock();
77 }
78 
79 void ComputeOffsetsHelper::DoScope(Scope &scope) {
80   if (scope.symbol() && scope.IsParameterizedDerivedType()) {
81     return; // only process instantiations of parameterized derived types
82   }
83   // Symbols in common block get offsets from the beginning of the block
84   for (auto &pair : scope.commonBlocks()) {
85     DoCommonBlock(*pair.second);
86   }
87   // Build dependents_ from equivalences: symbol -> symbol+offset
88   for (EquivalenceSet &set : scope.equivalenceSets()) {
89     DoEquivalenceSet(set);
90   }
91   offset_ = 0;
92   alignment_ = 0;
93   for (auto &symbol : scope.GetSymbols()) {
94     if (!InCommonBlock(*symbol) &&
95         dependents_.find(symbol) == dependents_.end()) {
96       DoSymbol(*symbol);
97     }
98   }
99   for (auto &[symbol, dep] : dependents_) {
100     if (symbol->size() == 0) {
101       SizeAndAlignment s{GetSizeAndAlignment(*symbol)};
102       symbol->set_size(s.size);
103       symbol->set_offset(GetOffset(dep));
104       offset_ = std::max(offset_, symbol->offset() + symbol->size());
105     }
106   }
107   scope.set_size(offset_);
108   scope.set_alignment(alignment_);
109 }
110 
111 std::size_t ComputeOffsetsHelper::GetOffset(SymbolAndOffset &dep) {
112   auto it{dependents_.find(*dep.symbol)};
113   if (it == dependents_.end()) {
114     return dep.symbol->offset() + dep.offset;
115   } else {
116     return GetOffset(it->second) + dep.offset;
117   }
118 }
119 
120 void ComputeOffsetsHelper::DoCommonBlock(Symbol &commonBlock) {
121   auto &details{commonBlock.get<CommonBlockDetails>()};
122   offset_ = 0;
123   alignment_ = 0;
124   for (auto &object : details.objects()) {
125     DoSymbol(*object);
126   }
127   commonBlock.set_size(offset_);
128   details.set_alignment(alignment_);
129 }
130 
131 void ComputeOffsetsHelper::DoEquivalenceSet(EquivalenceSet &set) {
132   std::vector<SymbolAndOffset> symbolOffsets;
133   SymbolAndOffset max;
134   for (EquivalenceObject &object : set) {
135     std::size_t offset{ComputeOffset(object)};
136     symbolOffsets.push_back({&object.symbol, offset});
137     if (offset >= max.offset) {
138       max.offset = offset;
139       max.symbol = &object.symbol;
140     }
141   }
142   CHECK(max.symbol);
143   for (auto &[symbol, offset] : symbolOffsets) {
144     if (symbol != max.symbol) {
145       dependents_.emplace(
146           *symbol, SymbolAndOffset{max.symbol, max.offset - offset});
147     }
148   }
149 }
150 
151 // Offset of this equivalence object from the start of its variable.
152 std::size_t ComputeOffsetsHelper::ComputeOffset(
153     const EquivalenceObject &object) {
154   std::size_t offset{0};
155   if (object.substringStart) {
156     offset = *object.substringStart - 1;
157   }
158   if (!object.subscripts.empty()) {
159     const ArraySpec &shape{object.symbol.get<ObjectEntityDetails>().shape()};
160     auto lbound{[&](std::size_t i) {
161       return *ToInt64(shape[i].lbound().GetExplicit());
162     }};
163     auto ubound{[&](std::size_t i) {
164       return *ToInt64(shape[i].ubound().GetExplicit());
165     }};
166     for (std::size_t i{object.subscripts.size() - 1};;) {
167       offset += object.subscripts[i] - lbound(i);
168       if (i == 0) {
169         break;
170       }
171       --i;
172       offset *= ubound(i) - lbound(i) + 1;
173     }
174   }
175   return offset *
176       GetElementSize(object.symbol, object.substringStart.has_value()).size;
177 }
178 
179 void ComputeOffsetsHelper::DoSymbol(Symbol &symbol) {
180   if (symbol.has<TypeParamDetails>() || symbol.has<SubprogramDetails>() ||
181       symbol.has<UseDetails>() || symbol.has<ProcBindingDetails>()) {
182     return; // these have type but no size
183   }
184   SizeAndAlignment s{GetSizeAndAlignment(symbol)};
185   if (s.size == 0) {
186     return;
187   }
188   offset_ = Align(offset_, s.alignment);
189   symbol.set_size(s.size);
190   symbol.set_offset(offset_);
191   offset_ += s.size;
192   alignment_ = std::max(alignment_, s.alignment);
193 }
194 
195 auto ComputeOffsetsHelper::GetSizeAndAlignment(const Symbol &symbol)
196     -> SizeAndAlignment {
197   SizeAndAlignment result{GetElementSize(symbol)};
198   std::size_t elements{CountElements(symbol)};
199   if (elements > 1) {
200     result.size = Align(result.size, result.alignment);
201   }
202   result.size *= elements;
203   return result;
204 }
205 
206 auto ComputeOffsetsHelper::GetElementSize(
207     const Symbol &symbol, bool isSubstring) -> SizeAndAlignment {
208   const DeclTypeSpec *type{symbol.GetType()};
209   if (!type) {
210     return {};
211   }
212   if (IsDescriptor(symbol) || IsProcedure(symbol)) {
213     int lenParams{0};
214     if (const DerivedTypeSpec * derived{type->AsDerived()}) {
215       lenParams = CountLenParameters(*derived);
216     }
217     std::size_t size{
218         runtime::Descriptor::SizeInBytes(symbol.Rank(), false, lenParams)};
219     return {size, maxAlignment};
220   }
221   SizeAndAlignment result;
222   if (const IntrinsicTypeSpec * intrinsic{type->AsIntrinsic()}) {
223     if (auto kind{ToInt64(intrinsic->kind())}) {
224       result = GetIntrinsicSizeAndAlignment(intrinsic->category(), *kind);
225     }
226     if (!isSubstring && type->category() == DeclTypeSpec::Character) {
227       ParamValue length{type->characterTypeSpec().length()};
228       CHECK(length.isExplicit()); // else should be descriptor
229       if (MaybeIntExpr lengthExpr{length.GetExplicit()}) {
230         if (auto lengthInt{ToInt64(*lengthExpr)}) {
231           result.size *= *lengthInt;
232         }
233       }
234     }
235   } else if (const DerivedTypeSpec * derived{type->AsDerived()}) {
236     if (derived->scope()) {
237       result.size = derived->scope()->size();
238       result.alignment = derived->scope()->alignment();
239     }
240   } else {
241     DIE("not intrinsic or derived");
242   }
243   return result;
244 }
245 
246 std::size_t ComputeOffsetsHelper::CountElements(const Symbol &symbol) {
247   if (auto shape{GetShape(foldingContext_, symbol)}) {
248     if (auto sizeExpr{evaluate::GetSize(std::move(*shape))}) {
249       if (auto size{ToInt64(Fold(foldingContext_, std::move(*sizeExpr)))}) {
250         return *size;
251       }
252     }
253   }
254   return 1;
255 }
256 
257 // Align a size to its natural alignment, up to maxAlignment.
258 std::size_t ComputeOffsetsHelper::Align(std::size_t x, std::size_t alignment) {
259   if (alignment > maxAlignment) {
260     alignment = maxAlignment;
261   }
262   return (x + alignment - 1) & -alignment;
263 }
264 
265 auto ComputeOffsetsHelper::GetIntrinsicSizeAndAlignment(
266     TypeCategory category, int kind) -> SizeAndAlignment {
267   // TODO: does kind==10 need special handling?
268   std::size_t size{kind == 3 ? 2 : static_cast<std::size_t>(kind)};
269   if (category == TypeCategory::Complex) {
270     return {2 * size, size};
271   } else {
272     return {size};
273   }
274 }
275 
276 void ComputeOffsets(SemanticsContext &context) {
277   ComputeOffsetsHelper{context}.Compute();
278 }
279 
280 } // namespace Fortran::semantics
281