1 //===-- lib/Semantics/compute-offsets.cpp -----------------------*- 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 #include "compute-offsets.h"
10 #include "../../runtime/descriptor.h"
11 #include "flang/Evaluate/fold-designator.h"
12 #include "flang/Evaluate/fold.h"
13 #include "flang/Evaluate/shape.h"
14 #include "flang/Evaluate/type.h"
15 #include "flang/Semantics/scope.h"
16 #include "flang/Semantics/semantics.h"
17 #include "flang/Semantics/symbol.h"
18 #include "flang/Semantics/tools.h"
19 #include "flang/Semantics/type.h"
20 #include <algorithm>
21 #include <vector>
22 
23 namespace Fortran::semantics {
24 
25 class ComputeOffsetsHelper {
26 public:
27   // TODO: configure based on target
28   static constexpr std::size_t maxAlignment{8};
29 
30   ComputeOffsetsHelper(SemanticsContext &context) : context_{context} {}
31   void Compute() { Compute(context_.globalScope()); }
32 
33 private:
34   struct SizeAndAlignment {
35     SizeAndAlignment() {}
36     SizeAndAlignment(std::size_t bytes) : size{bytes}, alignment{bytes} {}
37     SizeAndAlignment(std::size_t bytes, std::size_t align)
38         : size{bytes}, alignment{align} {}
39     std::size_t size{0};
40     std::size_t alignment{0};
41   };
42   struct SymbolAndOffset {
43     SymbolAndOffset(Symbol &s, std::size_t off, const EquivalenceObject &obj)
44         : symbol{&s}, offset{off}, object{&obj} {}
45     SymbolAndOffset(const SymbolAndOffset &) = default;
46     Symbol *symbol;
47     std::size_t offset;
48     const EquivalenceObject *object;
49   };
50 
51   void Compute(Scope &);
52   void DoScope(Scope &);
53   void DoCommonBlock(Symbol &);
54   void DoEquivalenceSet(const EquivalenceSet &);
55   SymbolAndOffset Resolve(const SymbolAndOffset &);
56   std::size_t ComputeOffset(const EquivalenceObject &);
57   void DoSymbol(Symbol &);
58   SizeAndAlignment GetSizeAndAlignment(const Symbol &);
59   SizeAndAlignment GetElementSize(const Symbol &);
60   std::size_t CountElements(const Symbol &);
61   static std::size_t Align(std::size_t, std::size_t);
62   static SizeAndAlignment GetIntrinsicSizeAndAlignment(TypeCategory, int);
63 
64   SemanticsContext &context_;
65   evaluate::FoldingContext &foldingContext_{context_.foldingContext()};
66   std::size_t offset_{0};
67   std::size_t alignment_{0};
68   // symbol -> symbol+offset that determines its location, from EQUIVALENCE
69   std::map<MutableSymbolRef, SymbolAndOffset> dependents_;
70 };
71 
72 void ComputeOffsetsHelper::Compute(Scope &scope) {
73   for (Scope &child : scope.children()) {
74     Compute(child);
75   }
76   DoScope(scope);
77 }
78 
79 static bool InCommonBlock(const Symbol &symbol) {
80   const auto *details{symbol.detailsIf<ObjectEntityDetails>()};
81   return details && details->commonBlock();
82 }
83 
84 void ComputeOffsetsHelper::DoScope(Scope &scope) {
85   if (scope.symbol() && scope.IsParameterizedDerivedType()) {
86     return; // only process instantiations of parameterized derived types
87   }
88   // Symbols in common block get offsets from the beginning of the block
89   for (auto &pair : scope.commonBlocks()) {
90     DoCommonBlock(*pair.second);
91   }
92   // Build dependents_ from equivalences: symbol -> symbol+offset
93   for (const EquivalenceSet &set : scope.equivalenceSets()) {
94     DoEquivalenceSet(set);
95   }
96   offset_ = 0;
97   alignment_ = 0;
98   for (auto &symbol : scope.GetSymbols()) {
99     if (!InCommonBlock(*symbol) &&
100         dependents_.find(symbol) == dependents_.end()) {
101       DoSymbol(*symbol);
102     }
103   }
104   for (auto &[symbol, dep] : dependents_) {
105     if (symbol->size() == 0) {
106       SizeAndAlignment s{GetSizeAndAlignment(*symbol)};
107       symbol->set_size(s.size);
108       SymbolAndOffset resolved{Resolve(dep)};
109       symbol->set_offset(dep.symbol->offset() + resolved.offset);
110       offset_ = std::max(offset_, symbol->offset() + symbol->size());
111     }
112   }
113   scope.set_size(offset_);
114   scope.set_alignment(alignment_);
115 }
116 
117 auto ComputeOffsetsHelper::Resolve(const SymbolAndOffset &dep)
118     -> SymbolAndOffset {
119   auto it{dependents_.find(*dep.symbol)};
120   if (it == dependents_.end()) {
121     return dep;
122   } else {
123     SymbolAndOffset result{Resolve(it->second)};
124     result.offset += dep.offset;
125     result.object = dep.object;
126     return result;
127   }
128 }
129 
130 void ComputeOffsetsHelper::DoCommonBlock(Symbol &commonBlock) {
131   auto &details{commonBlock.get<CommonBlockDetails>()};
132   offset_ = 0;
133   alignment_ = 0;
134   for (auto &object : details.objects()) {
135     DoSymbol(*object);
136   }
137   commonBlock.set_size(offset_);
138   details.set_alignment(alignment_);
139 }
140 
141 void ComputeOffsetsHelper::DoEquivalenceSet(const EquivalenceSet &set) {
142   std::vector<SymbolAndOffset> symbolOffsets;
143   std::optional<std::size_t> representative;
144   for (const EquivalenceObject &object : set) {
145     std::size_t offset{ComputeOffset(object)};
146     SymbolAndOffset resolved{
147         Resolve(SymbolAndOffset{object.symbol, offset, object})};
148     symbolOffsets.push_back(resolved);
149     if (!representative ||
150         resolved.offset >= symbolOffsets[*representative].offset) {
151       // The equivalenced object with the largest offset from its resolved
152       // symbol will be the representative of this set, since the offsets
153       // of the other objects will be positive relative to it.
154       representative = symbolOffsets.size() - 1;
155     }
156   }
157   CHECK(representative);
158   const SymbolAndOffset &base{symbolOffsets[*representative]};
159   for (const auto &[symbol, offset, object] : symbolOffsets) {
160     if (symbol == base.symbol) {
161       if (offset != base.offset) {
162         auto x{evaluate::OffsetToDesignator(
163             context_.foldingContext(), *symbol, base.offset, 1)};
164         auto y{evaluate::OffsetToDesignator(
165             context_.foldingContext(), *symbol, offset, 1)};
166         if (x && y) {
167           context_
168               .Say(base.object->source,
169                   "'%s' and '%s' cannot have the same first storage unit"_err_en_US,
170                   x->AsFortran(), y->AsFortran())
171               .Attach(object->source, "Incompatible reference to '%s'"_en_US,
172                   y->AsFortran());
173         } else { // error recovery
174           context_
175               .Say(base.object->source,
176                   "'%s' (offset %zd bytes and %zd bytes) cannot have the same first storage unit"_err_en_US,
177                   symbol->name(), base.offset, offset)
178               .Attach(object->source,
179                   "Incompatible reference to '%s' offset %zd bytes"_en_US,
180                   symbol->name(), offset);
181         }
182       }
183     } else {
184       dependents_.emplace(*symbol,
185           SymbolAndOffset{*base.symbol, base.offset - offset, *object});
186     }
187   }
188 }
189 
190 // Offset of this equivalence object from the start of its variable.
191 std::size_t ComputeOffsetsHelper::ComputeOffset(
192     const EquivalenceObject &object) {
193   std::size_t offset{0};
194   if (!object.subscripts.empty()) {
195     const ArraySpec &shape{object.symbol.get<ObjectEntityDetails>().shape()};
196     auto lbound{[&](std::size_t i) {
197       return *ToInt64(shape[i].lbound().GetExplicit());
198     }};
199     auto ubound{[&](std::size_t i) {
200       return *ToInt64(shape[i].ubound().GetExplicit());
201     }};
202     for (std::size_t i{object.subscripts.size() - 1};;) {
203       offset += object.subscripts[i] - lbound(i);
204       if (i == 0) {
205         break;
206       }
207       --i;
208       offset *= ubound(i) - lbound(i) + 1;
209     }
210   }
211   auto result{offset * GetElementSize(object.symbol).size};
212   if (object.substringStart) {
213     int kind{context_.defaultKinds().GetDefaultKind(TypeCategory::Character)};
214     if (const DeclTypeSpec * type{object.symbol.GetType()}) {
215       if (const IntrinsicTypeSpec * intrinsic{type->AsIntrinsic()}) {
216         kind = ToInt64(intrinsic->kind()).value_or(kind);
217       }
218     }
219     result += kind * (*object.substringStart - 1);
220   }
221   return result;
222 }
223 
224 void ComputeOffsetsHelper::DoSymbol(Symbol &symbol) {
225   if (symbol.has<TypeParamDetails>() || symbol.has<SubprogramDetails>() ||
226       symbol.has<UseDetails>() || symbol.has<ProcBindingDetails>()) {
227     return; // these have type but no size
228   }
229   SizeAndAlignment s{GetSizeAndAlignment(symbol)};
230   if (s.size == 0) {
231     return;
232   }
233   offset_ = Align(offset_, s.alignment);
234   symbol.set_size(s.size);
235   symbol.set_offset(offset_);
236   offset_ += s.size;
237   alignment_ = std::max(alignment_, s.alignment);
238 }
239 
240 auto ComputeOffsetsHelper::GetSizeAndAlignment(const Symbol &symbol)
241     -> SizeAndAlignment {
242   SizeAndAlignment result{GetElementSize(symbol)};
243   std::size_t elements{CountElements(symbol)};
244   if (elements > 1) {
245     result.size = Align(result.size, result.alignment);
246   }
247   result.size *= elements;
248   return result;
249 }
250 
251 auto ComputeOffsetsHelper::GetElementSize(const Symbol &symbol)
252     -> SizeAndAlignment {
253   const DeclTypeSpec *type{symbol.GetType()};
254   if (!type) {
255     return {};
256   }
257   // TODO: The size of procedure pointers is not yet known
258   // and is independent of rank (and probably also the number
259   // of length type parameters).
260   if (IsDescriptor(symbol) || IsProcedurePointer(symbol)) {
261     int lenParams{0};
262     if (const DerivedTypeSpec * derived{type->AsDerived()}) {
263       lenParams = CountLenParameters(*derived);
264     }
265     std::size_t size{
266         runtime::Descriptor::SizeInBytes(symbol.Rank(), false, lenParams)};
267     return {size, maxAlignment};
268   }
269   if (IsProcedure(symbol)) {
270     return {};
271   }
272   SizeAndAlignment result;
273   if (const IntrinsicTypeSpec * intrinsic{type->AsIntrinsic()}) {
274     if (auto kind{ToInt64(intrinsic->kind())}) {
275       result = GetIntrinsicSizeAndAlignment(intrinsic->category(), *kind);
276     }
277     if (type->category() == DeclTypeSpec::Character) {
278       ParamValue length{type->characterTypeSpec().length()};
279       CHECK(length.isExplicit()); // else should be descriptor
280       if (MaybeIntExpr lengthExpr{length.GetExplicit()}) {
281         if (auto lengthInt{ToInt64(*lengthExpr)}) {
282           result.size *= *lengthInt;
283         }
284       }
285     }
286   } else if (const DerivedTypeSpec * derived{type->AsDerived()}) {
287     if (derived->scope()) {
288       result.size = derived->scope()->size();
289       result.alignment = derived->scope()->alignment();
290     }
291   } else {
292     DIE("not intrinsic or derived");
293   }
294   return result;
295 }
296 
297 std::size_t ComputeOffsetsHelper::CountElements(const Symbol &symbol) {
298   if (auto shape{GetShape(foldingContext_, symbol)}) {
299     if (auto sizeExpr{evaluate::GetSize(std::move(*shape))}) {
300       if (auto size{ToInt64(Fold(foldingContext_, std::move(*sizeExpr)))}) {
301         return *size;
302       }
303     }
304   }
305   return 1;
306 }
307 
308 // Align a size to its natural alignment, up to maxAlignment.
309 std::size_t ComputeOffsetsHelper::Align(std::size_t x, std::size_t alignment) {
310   if (alignment > maxAlignment) {
311     alignment = maxAlignment;
312   }
313   return (x + alignment - 1) & -alignment;
314 }
315 
316 auto ComputeOffsetsHelper::GetIntrinsicSizeAndAlignment(
317     TypeCategory category, int kind) -> SizeAndAlignment {
318   if (category == TypeCategory::Character) {
319     return {static_cast<std::size_t>(kind)};
320   }
321   std::optional<std::size_t> size{
322       evaluate::DynamicType{category, kind}.MeasureSizeInBytes()};
323   CHECK(size.has_value());
324   if (category == TypeCategory::Complex) {
325     return {*size, *size >> 1};
326   } else {
327     return {*size};
328   }
329 }
330 
331 void ComputeOffsets(SemanticsContext &context) {
332   ComputeOffsetsHelper{context}.Compute();
333 }
334 
335 } // namespace Fortran::semantics
336