/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/Transform/DeLICM.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===------ DeLICM.cpp -----------------------------------------*- C++ -*-===// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | // |
10 | | // Undo the effect of Loop Invariant Code Motion (LICM) and |
11 | | // GVN Partial Redundancy Elimination (PRE) on SCoP-level. |
12 | | // |
13 | | // Namely, remove register/scalar dependencies by mapping them back to array |
14 | | // elements. |
15 | | // |
16 | | //===----------------------------------------------------------------------===// |
17 | | |
18 | | #include "polly/DeLICM.h" |
19 | | #include "polly/Options.h" |
20 | | #include "polly/ScopInfo.h" |
21 | | #include "polly/ScopPass.h" |
22 | | #include "polly/Support/ISLOStream.h" |
23 | | #include "polly/Support/ISLTools.h" |
24 | | #include "polly/ZoneAlgo.h" |
25 | | #include "llvm/ADT/Statistic.h" |
26 | 19 | #define DEBUG_TYPE "polly-delicm" |
27 | | |
28 | | using namespace polly; |
29 | | using namespace llvm; |
30 | | |
31 | | namespace { |
32 | | |
33 | | cl::opt<int> |
34 | | DelicmMaxOps("polly-delicm-max-ops", |
35 | | cl::desc("Maximum number of isl operations to invest for " |
36 | | "lifetime analysis; 0=no limit"), |
37 | | cl::init(1000000), cl::cat(PollyCategory)); |
38 | | |
39 | | cl::opt<bool> DelicmOverapproximateWrites( |
40 | | "polly-delicm-overapproximate-writes", |
41 | | cl::desc( |
42 | | "Do more PHI writes than necessary in order to avoid partial accesses"), |
43 | | cl::init(false), cl::Hidden, cl::cat(PollyCategory)); |
44 | | |
45 | | cl::opt<bool> DelicmPartialWrites("polly-delicm-partial-writes", |
46 | | cl::desc("Allow partial writes"), |
47 | | cl::init(true), cl::Hidden, |
48 | | cl::cat(PollyCategory)); |
49 | | |
50 | | cl::opt<bool> |
51 | | DelicmComputeKnown("polly-delicm-compute-known", |
52 | | cl::desc("Compute known content of array elements"), |
53 | | cl::init(true), cl::Hidden, cl::cat(PollyCategory)); |
54 | | |
55 | | STATISTIC(DeLICMAnalyzed, "Number of successfully analyzed SCoPs"); |
56 | | STATISTIC(DeLICMOutOfQuota, |
57 | | "Analyses aborted because max_operations was reached"); |
58 | | STATISTIC(MappedValueScalars, "Number of mapped Value scalars"); |
59 | | STATISTIC(MappedPHIScalars, "Number of mapped PHI scalars"); |
60 | | STATISTIC(TargetsMapped, "Number of stores used for at least one mapping"); |
61 | | STATISTIC(DeLICMScopsModified, "Number of SCoPs optimized"); |
62 | | |
63 | | STATISTIC(NumValueWrites, "Number of scalar value writes after DeLICM"); |
64 | | STATISTIC(NumValueWritesInLoops, |
65 | | "Number of scalar value writes nested in affine loops after DeLICM"); |
66 | | STATISTIC(NumPHIWrites, "Number of scalar phi writes after DeLICM"); |
67 | | STATISTIC(NumPHIWritesInLoops, |
68 | | "Number of scalar phi writes nested in affine loops after DeLICM"); |
69 | | STATISTIC(NumSingletonWrites, "Number of singleton writes after DeLICM"); |
70 | | STATISTIC(NumSingletonWritesInLoops, |
71 | | "Number of singleton writes nested in affine loops after DeLICM"); |
72 | | |
73 | | isl::union_map computeReachingOverwrite(isl::union_map Schedule, |
74 | | isl::union_map Writes, |
75 | | bool InclPrevWrite, |
76 | 30 | bool InclOverwrite) { |
77 | 30 | return computeReachingWrite(Schedule, Writes, true, InclPrevWrite, |
78 | 30 | InclOverwrite); |
79 | 30 | } |
80 | | |
81 | | /// Compute the next overwrite for a scalar. |
82 | | /// |
83 | | /// @param Schedule { DomainWrite[] -> Scatter[] } |
84 | | /// Schedule of (at least) all writes. Instances not in @p |
85 | | /// Writes are ignored. |
86 | | /// @param Writes { DomainWrite[] } |
87 | | /// The element instances that write to the scalar. |
88 | | /// @param InclPrevWrite Whether to extend the timepoints to include |
89 | | /// the timepoint where the previous write happens. |
90 | | /// @param InclOverwrite Whether the reaching overwrite includes the timepoint |
91 | | /// of the overwrite itself. |
92 | | /// |
93 | | /// @return { Scatter[] -> DomainDef[] } |
94 | | isl::union_map computeScalarReachingOverwrite(isl::union_map Schedule, |
95 | | isl::union_set Writes, |
96 | | bool InclPrevWrite, |
97 | 30 | bool InclOverwrite) { |
98 | 30 | |
99 | 30 | // { DomainWrite[] } |
100 | 30 | auto WritesMap = give(isl_union_map_from_domain(Writes.take())); |
101 | 30 | |
102 | 30 | // { [Element[] -> Scatter[]] -> DomainWrite[] } |
103 | 30 | auto Result = computeReachingOverwrite( |
104 | 30 | std::move(Schedule), std::move(WritesMap), InclPrevWrite, InclOverwrite); |
105 | 30 | |
106 | 30 | return give(isl_union_map_domain_factor_range(Result.take())); |
107 | 30 | } |
108 | | |
109 | | /// Overload of computeScalarReachingOverwrite, with only one writing statement. |
110 | | /// Consequently, the result consists of only one map space. |
111 | | /// |
112 | | /// @param Schedule { DomainWrite[] -> Scatter[] } |
113 | | /// @param Writes { DomainWrite[] } |
114 | | /// @param InclPrevWrite Include the previous write to result. |
115 | | /// @param InclOverwrite Include the overwrite to the result. |
116 | | /// |
117 | | /// @return { Scatter[] -> DomainWrite[] } |
118 | | isl::map computeScalarReachingOverwrite(isl::union_map Schedule, |
119 | | isl::set Writes, bool InclPrevWrite, |
120 | 30 | bool InclOverwrite) { |
121 | 30 | isl::space ScatterSpace = getScatterSpace(Schedule); |
122 | 30 | isl::space DomSpace = Writes.get_space(); |
123 | 30 | |
124 | 30 | isl::union_map ReachOverwrite = computeScalarReachingOverwrite( |
125 | 30 | Schedule, isl::union_set(Writes), InclPrevWrite, InclOverwrite); |
126 | 30 | |
127 | 30 | isl::space ResultSpace = ScatterSpace.map_from_domain_and_range(DomSpace); |
128 | 30 | return singleton(std::move(ReachOverwrite), ResultSpace); |
129 | 30 | } |
130 | | |
131 | | /// Try to find a 'natural' extension of a mapped to elements outside its |
132 | | /// domain. |
133 | | /// |
134 | | /// @param Relevant The map with mapping that may not be modified. |
135 | | /// @param Universe The domain to which @p Relevant needs to be extended. |
136 | | /// |
137 | | /// @return A map with that associates the domain elements of @p Relevant to the |
138 | | /// same elements and in addition the elements of @p Universe to some |
139 | | /// undefined elements. The function prefers to return simple maps. |
140 | 11 | isl::union_map expandMapping(isl::union_map Relevant, isl::union_set Universe) { |
141 | 11 | Relevant = Relevant.coalesce(); |
142 | 11 | isl::union_set RelevantDomain = Relevant.domain(); |
143 | 11 | isl::union_map Simplified = Relevant.gist_domain(RelevantDomain); |
144 | 11 | Simplified = Simplified.coalesce(); |
145 | 11 | return Simplified.intersect_domain(Universe); |
146 | 11 | } |
147 | | |
148 | | /// Represent the knowledge of the contents of any array elements in any zone or |
149 | | /// the knowledge we would add when mapping a scalar to an array element. |
150 | | /// |
151 | | /// Every array element at every zone unit has one of two states: |
152 | | /// |
153 | | /// - Unused: Not occupied by any value so a transformation can change it to |
154 | | /// other values. |
155 | | /// |
156 | | /// - Occupied: The element contains a value that is still needed. |
157 | | /// |
158 | | /// The union of Unused and Unknown zones forms the universe, the set of all |
159 | | /// elements at every timepoint. The universe can easily be derived from the |
160 | | /// array elements that are accessed someway. Arrays that are never accessed |
161 | | /// also never play a role in any computation and can hence be ignored. With a |
162 | | /// given universe, only one of the sets needs to stored implicitly. Computing |
163 | | /// the complement is also an expensive operation, hence this class has been |
164 | | /// designed that only one of sets is needed while the other is assumed to be |
165 | | /// implicit. It can still be given, but is mostly ignored. |
166 | | /// |
167 | | /// There are two use cases for the Knowledge class: |
168 | | /// |
169 | | /// 1) To represent the knowledge of the current state of ScopInfo. The unused |
170 | | /// state means that an element is currently unused: there is no read of it |
171 | | /// before the next overwrite. Also called 'Existing'. |
172 | | /// |
173 | | /// 2) To represent the requirements for mapping a scalar to array elements. The |
174 | | /// unused state means that there is no change/requirement. Also called |
175 | | /// 'Proposed'. |
176 | | /// |
177 | | /// In addition to these states at unit zones, Knowledge needs to know when |
178 | | /// values are written. This is because written values may have no lifetime (one |
179 | | /// reason is that the value is never read). Such writes would therefore never |
180 | | /// conflict, but overwrite values that might still be required. Another source |
181 | | /// of problems are multiple writes to the same element at the same timepoint, |
182 | | /// because their order is undefined. |
183 | | class Knowledge { |
184 | | private: |
185 | | /// { [Element[] -> Zone[]] } |
186 | | /// Set of array elements and when they are alive. |
187 | | /// Can contain a nullptr; in this case the set is implicitly defined as the |
188 | | /// complement of #Unused. |
189 | | /// |
190 | | /// The set of alive array elements is represented as zone, as the set of live |
191 | | /// values can differ depending on how the elements are interpreted. |
192 | | /// Assuming a value X is written at timestep [0] and read at timestep [1] |
193 | | /// without being used at any later point, then the value is alive in the |
194 | | /// interval ]0,1[. This interval cannot be represented by an integer set, as |
195 | | /// it does not contain any integer point. Zones allow us to represent this |
196 | | /// interval and can be converted to sets of timepoints when needed (e.g., in |
197 | | /// isConflicting when comparing to the write sets). |
198 | | /// @see convertZoneToTimepoints and this file's comment for more details. |
199 | | isl::union_set Occupied; |
200 | | |
201 | | /// { [Element[] -> Zone[]] } |
202 | | /// Set of array elements when they are not alive, i.e. their memory can be |
203 | | /// used for other purposed. Can contain a nullptr; in this case the set is |
204 | | /// implicitly defined as the complement of #Occupied. |
205 | | isl::union_set Unused; |
206 | | |
207 | | /// { [Element[] -> Zone[]] -> ValInst[] } |
208 | | /// Maps to the known content for each array element at any interval. |
209 | | /// |
210 | | /// Any element/interval can map to multiple known elements. This is due to |
211 | | /// multiple llvm::Value referring to the same content. Examples are |
212 | | /// |
213 | | /// - A value stored and loaded again. The LoadInst represents the same value |
214 | | /// as the StoreInst's value operand. |
215 | | /// |
216 | | /// - A PHINode is equal to any one of the incoming values. In case of |
217 | | /// LCSSA-form, it is always equal to its single incoming value. |
218 | | /// |
219 | | /// Two Knowledges are considered not conflicting if at least one of the known |
220 | | /// values match. Not known values are not stored as an unnamed tuple (as |
221 | | /// #Written does), but maps to nothing. |
222 | | /// |
223 | | /// Known values are usually just defined for #Occupied elements. Knowing |
224 | | /// #Unused contents has no advantage as it can be overwritten. |
225 | | isl::union_map Known; |
226 | | |
227 | | /// { [Element[] -> Scatter[]] -> ValInst[] } |
228 | | /// The write actions currently in the scop or that would be added when |
229 | | /// mapping a scalar. Maps to the value that is written. |
230 | | /// |
231 | | /// Written values that cannot be identified are represented by an unknown |
232 | | /// ValInst[] (an unnamed tuple of 0 dimension). It conflicts with itself. |
233 | | isl::union_map Written; |
234 | | |
235 | | /// Check whether this Knowledge object is well-formed. |
236 | 613 | void checkConsistency() const { |
237 | | #ifndef NDEBUG |
238 | | // Default-initialized object |
239 | | if (!Occupied && !Unused && !Known && !Written) |
240 | | return; |
241 | | |
242 | | assert(Occupied || Unused); |
243 | | assert(Known); |
244 | | assert(Written); |
245 | | |
246 | | // If not all fields are defined, we cannot derived the universe. |
247 | | if (!Occupied || !Unused) |
248 | | return; |
249 | | |
250 | | assert(isl_union_set_is_disjoint(Occupied.keep(), Unused.keep()) == |
251 | | isl_bool_true); |
252 | | auto Universe = give(isl_union_set_union(Occupied.copy(), Unused.copy())); |
253 | | |
254 | | assert(!Known.domain().is_subset(Universe).is_false()); |
255 | | assert(!Written.domain().is_subset(Universe).is_false()); |
256 | | #endif |
257 | | } |
258 | | |
259 | | public: |
260 | | /// Initialize a nullptr-Knowledge. This is only provided for convenience; do |
261 | | /// not use such an object. |
262 | 72 | Knowledge() {} |
263 | | |
264 | | /// Create a new object with the given members. |
265 | | Knowledge(isl::union_set Occupied, isl::union_set Unused, |
266 | | isl::union_map Known, isl::union_map Written) |
267 | | : Occupied(std::move(Occupied)), Unused(std::move(Unused)), |
268 | 559 | Known(std::move(Known)), Written(std::move(Written)) { |
269 | 559 | checkConsistency(); |
270 | 559 | } |
271 | | |
272 | | /// Return whether this object was not default-constructed. |
273 | 35 | bool isUsable() const { return (Occupied || 35 Unused35 ) && Known34 && Written34 ; } |
274 | | |
275 | | /// Print the content of this object to @p OS. |
276 | 0 | void print(llvm::raw_ostream &OS, unsigned Indent = 0) const { |
277 | 0 | if (isUsable()) { |
278 | 0 | if (Occupied) |
279 | 0 | OS.indent(Indent) << "Occupied: " << Occupied << "\n"; |
280 | 0 | else |
281 | 0 | OS.indent(Indent) << "Occupied: <Everything else not in Unused>\n"; |
282 | 0 | if (Unused) |
283 | 0 | OS.indent(Indent) << "Unused: " << Unused << "\n"; |
284 | 0 | else |
285 | 0 | OS.indent(Indent) << "Unused: <Everything else not in Occupied>\n"; |
286 | 0 | OS.indent(Indent) << "Known: " << Known << "\n"; |
287 | 0 | OS.indent(Indent) << "Written : " << Written << '\n'; |
288 | 0 | } else { |
289 | 0 | OS.indent(Indent) << "Invalid knowledge\n"; |
290 | 0 | } |
291 | 0 | } |
292 | | |
293 | | /// Combine two knowledges, this and @p That. |
294 | 54 | void learnFrom(Knowledge That) { |
295 | 54 | assert(!isConflicting(*this, That)); |
296 | 54 | assert(Unused && That.Occupied); |
297 | 54 | assert( |
298 | 54 | !That.Unused && |
299 | 54 | "This function is only prepared to learn occupied elements from That"); |
300 | 54 | assert(!Occupied && "This function does not implement " |
301 | 54 | "`this->Occupied = " |
302 | 54 | "give(isl_union_set_union(this->Occupied.take(), " |
303 | 54 | "That.Occupied.copy()));`"); |
304 | 54 | |
305 | 54 | Unused = give(isl_union_set_subtract(Unused.take(), That.Occupied.copy())); |
306 | 54 | Known = give(isl_union_map_union(Known.take(), That.Known.copy())); |
307 | 54 | Written = give(isl_union_map_union(Written.take(), That.Written.take())); |
308 | 54 | |
309 | 54 | checkConsistency(); |
310 | 54 | } |
311 | | |
312 | | /// Determine whether two Knowledges conflict with each other. |
313 | | /// |
314 | | /// In theory @p Existing and @p Proposed are symmetric, but the |
315 | | /// implementation is constrained by the implicit interpretation. That is, @p |
316 | | /// Existing must have #Unused defined (use case 1) and @p Proposed must have |
317 | | /// #Occupied defined (use case 1). |
318 | | /// |
319 | | /// A conflict is defined as non-preserved semantics when they are merged. For |
320 | | /// instance, when for the same array and zone they assume different |
321 | | /// llvm::Values. |
322 | | /// |
323 | | /// @param Existing One of the knowledges with #Unused defined. |
324 | | /// @param Proposed One of the knowledges with #Occupied defined. |
325 | | /// @param OS Dump the conflict reason to this output stream; use |
326 | | /// nullptr to not output anything. |
327 | | /// @param Indent Indention for the conflict reason. |
328 | | /// |
329 | | /// @return True, iff the two knowledges are conflicting. |
330 | | static bool isConflicting(const Knowledge &Existing, |
331 | | const Knowledge &Proposed, |
332 | | llvm::raw_ostream *OS = nullptr, |
333 | 292 | unsigned Indent = 0) { |
334 | 292 | assert(Existing.Unused); |
335 | 292 | assert(Proposed.Occupied); |
336 | 292 | |
337 | | #ifndef NDEBUG |
338 | | if (Existing.Occupied && Proposed.Unused) { |
339 | | auto ExistingUniverse = give(isl_union_set_union(Existing.Occupied.copy(), |
340 | | Existing.Unused.copy())); |
341 | | auto ProposedUniverse = give(isl_union_set_union(Proposed.Occupied.copy(), |
342 | | Proposed.Unused.copy())); |
343 | | assert(isl_union_set_is_equal(ExistingUniverse.keep(), |
344 | | ProposedUniverse.keep()) == isl_bool_true && |
345 | | "Both inputs' Knowledges must be over the same universe"); |
346 | | } |
347 | | #endif |
348 | | |
349 | 292 | // Do the Existing and Proposed lifetimes conflict? |
350 | 292 | // |
351 | 292 | // Lifetimes are described as the cross-product of array elements and zone |
352 | 292 | // intervals in which they are alive (the space { [Element[] -> Zone[]] }). |
353 | 292 | // In the following we call this "element/lifetime interval". |
354 | 292 | // |
355 | 292 | // In order to not conflict, one of the following conditions must apply for |
356 | 292 | // each element/lifetime interval: |
357 | 292 | // |
358 | 292 | // 1. If occupied in one of the knowledges, it is unused in the other. |
359 | 292 | // |
360 | 292 | // - or - |
361 | 292 | // |
362 | 292 | // 2. Both contain the same value. |
363 | 292 | // |
364 | 292 | // Instead of partitioning the element/lifetime intervals into a part that |
365 | 292 | // both Knowledges occupy (which requires an expensive subtraction) and for |
366 | 292 | // these to check whether they are known to be the same value, we check only |
367 | 292 | // the second condition and ensure that it also applies when then first |
368 | 292 | // condition is true. This is done by adding a wildcard value to |
369 | 292 | // Proposed.Known and Existing.Unused such that they match as a common known |
370 | 292 | // value. We use the "unknown ValInst" for this purpose. Every |
371 | 292 | // Existing.Unused may match with an unknown Proposed.Occupied because these |
372 | 292 | // never are in conflict with each other. |
373 | 292 | auto ProposedOccupiedAnyVal = makeUnknownForDomain(Proposed.Occupied); |
374 | 292 | auto ProposedValues = Proposed.Known.unite(ProposedOccupiedAnyVal); |
375 | 292 | |
376 | 292 | auto ExistingUnusedAnyVal = makeUnknownForDomain(Existing.Unused); |
377 | 292 | auto ExistingValues = Existing.Known.unite(ExistingUnusedAnyVal); |
378 | 292 | |
379 | 292 | auto MatchingVals = ExistingValues.intersect(ProposedValues); |
380 | 292 | auto Matches = MatchingVals.domain(); |
381 | 292 | |
382 | 292 | // Any Proposed.Occupied must either have a match between the known values |
383 | 292 | // of Existing and Occupied, or be in Existing.Unused. In the latter case, |
384 | 292 | // the previously added "AnyVal" will match each other. |
385 | 292 | if (!Proposed.Occupied.is_subset(Matches)292 ) { |
386 | 44 | if (OS44 ) { |
387 | 0 | auto Conflicting = Proposed.Occupied.subtract(Matches); |
388 | 0 | auto ExistingConflictingKnown = |
389 | 0 | Existing.Known.intersect_domain(Conflicting); |
390 | 0 | auto ProposedConflictingKnown = |
391 | 0 | Proposed.Known.intersect_domain(Conflicting); |
392 | 0 |
|
393 | 0 | OS->indent(Indent) << "Proposed lifetime conflicting with Existing's\n"; |
394 | 0 | OS->indent(Indent) << "Conflicting occupied: " << Conflicting << "\n"; |
395 | 0 | if (!ExistingConflictingKnown.is_empty()) |
396 | 0 | OS->indent(Indent) |
397 | 0 | << "Existing Known: " << ExistingConflictingKnown << "\n"; |
398 | 0 | if (!ProposedConflictingKnown.is_empty()) |
399 | 0 | OS->indent(Indent) |
400 | 0 | << "Proposed Known: " << ProposedConflictingKnown << "\n"; |
401 | 0 | } |
402 | 44 | return true; |
403 | 44 | } |
404 | 248 | |
405 | 248 | // Do the writes in Existing conflict with occupied values in Proposed? |
406 | 248 | // |
407 | 248 | // In order to not conflict, it must either write to unused lifetime or |
408 | 248 | // write the same value. To check, we remove the writes that write into |
409 | 248 | // Proposed.Unused (they never conflict) and then see whether the written |
410 | 248 | // value is already in Proposed.Known. If there are multiple known values |
411 | 248 | // and a written value is known under different names, it is enough when one |
412 | 248 | // of the written values (assuming that they are the same value under |
413 | 248 | // different names, e.g. a PHINode and one of the incoming values) matches |
414 | 248 | // one of the known names. |
415 | 248 | // |
416 | 248 | // We convert here the set of lifetimes to actual timepoints. A lifetime is |
417 | 248 | // in conflict with a set of write timepoints, if either a live timepoint is |
418 | 248 | // clearly within the lifetime or if a write happens at the beginning of the |
419 | 248 | // lifetime (where it would conflict with the value that actually writes the |
420 | 248 | // value alive). There is no conflict at the end of a lifetime, as the alive |
421 | 248 | // value will always be read, before it is overwritten again. The last |
422 | 248 | // property holds in Polly for all scalar values and we expect all users of |
423 | 248 | // Knowledge to check this property also for accesses to MemoryKind::Array. |
424 | 248 | auto ProposedFixedDefs = |
425 | 248 | convertZoneToTimepoints(Proposed.Occupied, true, false); |
426 | 248 | auto ProposedFixedKnown = |
427 | 248 | convertZoneToTimepoints(Proposed.Known, isl::dim::in, true, false); |
428 | 248 | |
429 | 248 | auto ExistingConflictingWrites = |
430 | 248 | Existing.Written.intersect_domain(ProposedFixedDefs); |
431 | 248 | auto ExistingConflictingWritesDomain = ExistingConflictingWrites.domain(); |
432 | 248 | |
433 | 248 | auto CommonWrittenVal = |
434 | 248 | ProposedFixedKnown.intersect(ExistingConflictingWrites); |
435 | 248 | auto CommonWrittenValDomain = CommonWrittenVal.domain(); |
436 | 248 | |
437 | 248 | if (!ExistingConflictingWritesDomain.is_subset(CommonWrittenValDomain)248 ) { |
438 | 26 | if (OS26 ) { |
439 | 0 | auto ExistingConflictingWritten = |
440 | 0 | ExistingConflictingWrites.subtract_domain(CommonWrittenValDomain); |
441 | 0 | auto ProposedConflictingKnown = ProposedFixedKnown.subtract_domain( |
442 | 0 | ExistingConflictingWritten.domain()); |
443 | 0 |
|
444 | 0 | OS->indent(Indent) |
445 | 0 | << "Proposed a lifetime where there is an Existing write into it\n"; |
446 | 0 | OS->indent(Indent) << "Existing conflicting writes: " |
447 | 0 | << ExistingConflictingWritten << "\n"; |
448 | 0 | if (!ProposedConflictingKnown.is_empty()) |
449 | 0 | OS->indent(Indent) |
450 | 0 | << "Proposed conflicting known: " << ProposedConflictingKnown |
451 | 0 | << "\n"; |
452 | 0 | } |
453 | 26 | return true; |
454 | 26 | } |
455 | 222 | |
456 | 222 | // Do the writes in Proposed conflict with occupied values in Existing? |
457 | 222 | auto ExistingAvailableDefs = |
458 | 222 | convertZoneToTimepoints(Existing.Unused, true, false); |
459 | 222 | auto ExistingKnownDefs = |
460 | 222 | convertZoneToTimepoints(Existing.Known, isl::dim::in, true, false); |
461 | 222 | |
462 | 222 | auto ProposedWrittenDomain = Proposed.Written.domain(); |
463 | 222 | auto KnownIdentical = ExistingKnownDefs.intersect(Proposed.Written); |
464 | 222 | auto IdenticalOrUnused = |
465 | 222 | ExistingAvailableDefs.unite(KnownIdentical.domain()); |
466 | 222 | if (!ProposedWrittenDomain.is_subset(IdenticalOrUnused)222 ) { |
467 | 24 | if (OS24 ) { |
468 | 0 | auto Conflicting = ProposedWrittenDomain.subtract(IdenticalOrUnused); |
469 | 0 | auto ExistingConflictingKnown = |
470 | 0 | ExistingKnownDefs.intersect_domain(Conflicting); |
471 | 0 | auto ProposedConflictingWritten = |
472 | 0 | Proposed.Written.intersect_domain(Conflicting); |
473 | 0 |
|
474 | 0 | OS->indent(Indent) << "Proposed writes into range used by Existing\n"; |
475 | 0 | OS->indent(Indent) << "Proposed conflicting writes: " |
476 | 0 | << ProposedConflictingWritten << "\n"; |
477 | 0 | if (!ExistingConflictingKnown.is_empty()) |
478 | 0 | OS->indent(Indent) |
479 | 0 | << "Existing conflicting known: " << ExistingConflictingKnown |
480 | 0 | << "\n"; |
481 | 0 | } |
482 | 24 | return true; |
483 | 24 | } |
484 | 198 | |
485 | 198 | // Does Proposed write at the same time as Existing already does (order of |
486 | 198 | // writes is undefined)? Writing the same value is permitted. |
487 | 198 | auto ExistingWrittenDomain = |
488 | 198 | isl::manage(isl_union_map_domain(Existing.Written.copy())); |
489 | 198 | auto BothWritten = |
490 | 198 | Existing.Written.domain().intersect(Proposed.Written.domain()); |
491 | 198 | auto ExistingKnownWritten = filterKnownValInst(Existing.Written); |
492 | 198 | auto ProposedKnownWritten = filterKnownValInst(Proposed.Written); |
493 | 198 | auto CommonWritten = |
494 | 198 | ExistingKnownWritten.intersect(ProposedKnownWritten).domain(); |
495 | 198 | |
496 | 198 | if (!BothWritten.is_subset(CommonWritten)198 ) { |
497 | 24 | if (OS24 ) { |
498 | 0 | auto Conflicting = BothWritten.subtract(CommonWritten); |
499 | 0 | auto ExistingConflictingWritten = |
500 | 0 | Existing.Written.intersect_domain(Conflicting); |
501 | 0 | auto ProposedConflictingWritten = |
502 | 0 | Proposed.Written.intersect_domain(Conflicting); |
503 | 0 |
|
504 | 0 | OS->indent(Indent) << "Proposed writes at the same time as an already " |
505 | 0 | "Existing write\n"; |
506 | 0 | OS->indent(Indent) << "Conflicting writes: " << Conflicting << "\n"; |
507 | 0 | if (!ExistingConflictingWritten.is_empty()) |
508 | 0 | OS->indent(Indent) |
509 | 0 | << "Exiting write: " << ExistingConflictingWritten << "\n"; |
510 | 0 | if (!ProposedConflictingWritten.is_empty()) |
511 | 0 | OS->indent(Indent) |
512 | 0 | << "Proposed write: " << ProposedConflictingWritten << "\n"; |
513 | 0 | } |
514 | 24 | return true; |
515 | 24 | } |
516 | 174 | |
517 | 174 | return false; |
518 | 174 | } |
519 | | }; |
520 | | |
521 | | /// Implementation of the DeLICM/DePRE transformation. |
522 | | class DeLICMImpl : public ZoneAlgorithm { |
523 | | private: |
524 | | /// Knowledge before any transformation took place. |
525 | | Knowledge OriginalZone; |
526 | | |
527 | | /// Current knowledge of the SCoP including all already applied |
528 | | /// transformations. |
529 | | Knowledge Zone; |
530 | | |
531 | | /// Number of StoreInsts something can be mapped to. |
532 | | int NumberOfCompatibleTargets = 0; |
533 | | |
534 | | /// The number of StoreInsts to which at least one value or PHI has been |
535 | | /// mapped to. |
536 | | int NumberOfTargetsMapped = 0; |
537 | | |
538 | | /// The number of llvm::Value mapped to some array element. |
539 | | int NumberOfMappedValueScalars = 0; |
540 | | |
541 | | /// The number of PHIs mapped to some array element. |
542 | | int NumberOfMappedPHIScalars = 0; |
543 | | |
544 | | /// Determine whether two knowledges are conflicting with each other. |
545 | | /// |
546 | | /// @see Knowledge::isConflicting |
547 | 60 | bool isConflicting(const Knowledge &Proposed) { |
548 | 60 | raw_ostream *OS = nullptr; |
549 | 60 | DEBUG(OS = &llvm::dbgs()); |
550 | 60 | return Knowledge::isConflicting(Zone, Proposed, OS, 4); |
551 | 60 | } |
552 | | |
553 | | /// Determine whether @p SAI is a scalar that can be mapped to an array |
554 | | /// element. |
555 | 67 | bool isMappable(const ScopArrayInfo *SAI) { |
556 | 67 | assert(SAI); |
557 | 67 | |
558 | 67 | if (SAI->isValueKind()67 ) { |
559 | 43 | auto *MA = S->getValueDef(SAI); |
560 | 43 | if (!MA43 ) { |
561 | 2 | DEBUG(dbgs() |
562 | 2 | << " Reject because value is read-only within the scop\n"); |
563 | 2 | return false; |
564 | 2 | } |
565 | 41 | |
566 | 41 | // Mapping if value is used after scop is not supported. The code |
567 | 41 | // generator would need to reload the scalar after the scop, but it |
568 | 41 | // does not have the information to where it is mapped to. Only the |
569 | 41 | // MemoryAccesses have that information, not the ScopArrayInfo. |
570 | 41 | auto Inst = MA->getAccessInstruction(); |
571 | 69 | for (auto User : Inst->users()) { |
572 | 69 | if (!isa<Instruction>(User)) |
573 | 0 | return false; |
574 | 69 | auto UserInst = cast<Instruction>(User); |
575 | 69 | |
576 | 69 | if (!S->contains(UserInst)69 ) { |
577 | 1 | DEBUG(dbgs() << " Reject because value is escaping\n"); |
578 | 1 | return false; |
579 | 1 | } |
580 | 40 | } |
581 | 40 | |
582 | 40 | return true; |
583 | 40 | } |
584 | 24 | |
585 | 24 | if (24 SAI->isPHIKind()24 ) { |
586 | 24 | auto *MA = S->getPHIRead(SAI); |
587 | 24 | assert(MA); |
588 | 24 | |
589 | 24 | // Mapping of an incoming block from before the SCoP is not supported by |
590 | 24 | // the code generator. |
591 | 24 | auto PHI = cast<PHINode>(MA->getAccessInstruction()); |
592 | 48 | for (auto Incoming : PHI->blocks()) { |
593 | 48 | if (!S->contains(Incoming)48 ) { |
594 | 0 | DEBUG(dbgs() << " Reject because at least one incoming block is " |
595 | 0 | "not in the scop region\n"); |
596 | 0 | return false; |
597 | 0 | } |
598 | 24 | } |
599 | 24 | |
600 | 24 | return true; |
601 | 24 | } |
602 | 0 |
|
603 | 0 | DEBUG0 (dbgs() << " Reject ExitPHI or other non-value\n"); |
604 | 0 | return false; |
605 | 0 | } |
606 | | |
607 | | /// Compute the uses of a MemoryKind::Value and its lifetime (from its |
608 | | /// definition to the last use). |
609 | | /// |
610 | | /// @param SAI The ScopArrayInfo representing the value's storage. |
611 | | /// |
612 | | /// @return { DomainDef[] -> DomainUse[] }, { DomainDef[] -> Zone[] } |
613 | | /// First element is the set of uses for each definition. |
614 | | /// The second is the lifetime of each definition. |
615 | | std::tuple<isl::union_map, isl::map> |
616 | 37 | computeValueUses(const ScopArrayInfo *SAI) { |
617 | 37 | assert(SAI->isValueKind()); |
618 | 37 | |
619 | 37 | // { DomainRead[] } |
620 | 37 | auto Reads = makeEmptyUnionSet(); |
621 | 37 | |
622 | 37 | // Find all uses. |
623 | 37 | for (auto *MA : S->getValueUses(SAI)) |
624 | 54 | Reads = |
625 | 54 | give(isl_union_set_add_set(Reads.take(), getDomainFor(MA).take())); |
626 | 37 | |
627 | 37 | // { DomainRead[] -> Scatter[] } |
628 | 37 | auto ReadSchedule = getScatterFor(Reads); |
629 | 37 | |
630 | 37 | auto *DefMA = S->getValueDef(SAI); |
631 | 37 | assert(DefMA); |
632 | 37 | |
633 | 37 | // { DomainDef[] } |
634 | 37 | auto Writes = getDomainFor(DefMA); |
635 | 37 | |
636 | 37 | // { DomainDef[] -> Scatter[] } |
637 | 37 | auto WriteScatter = getScatterFor(Writes); |
638 | 37 | |
639 | 37 | // { Scatter[] -> DomainDef[] } |
640 | 37 | auto ReachDef = getScalarReachingDefinition(DefMA->getStatement()); |
641 | 37 | |
642 | 37 | // { [DomainDef[] -> Scatter[]] -> DomainUse[] } |
643 | 37 | auto Uses = give( |
644 | 37 | isl_union_map_apply_range(isl_union_map_from_map(isl_map_range_map( |
645 | 37 | isl_map_reverse(ReachDef.take()))), |
646 | 37 | isl_union_map_reverse(ReadSchedule.take()))); |
647 | 37 | |
648 | 37 | // { DomainDef[] -> Scatter[] } |
649 | 37 | auto UseScatter = |
650 | 37 | singleton(give(isl_union_set_unwrap(isl_union_map_domain(Uses.copy()))), |
651 | 37 | give(isl_space_map_from_domain_and_range( |
652 | 37 | isl_set_get_space(Writes.keep()), ScatterSpace.copy()))); |
653 | 37 | |
654 | 37 | // { DomainDef[] -> Zone[] } |
655 | 37 | auto Lifetime = betweenScatter(WriteScatter, UseScatter, false, true); |
656 | 37 | |
657 | 37 | // { DomainDef[] -> DomainRead[] } |
658 | 37 | auto DefUses = give(isl_union_map_domain_factor_domain(Uses.take())); |
659 | 37 | |
660 | 37 | return std::make_pair(DefUses, Lifetime); |
661 | 37 | } |
662 | | |
663 | | /// For each 'execution' of a PHINode, get the incoming block that was |
664 | | /// executed before. |
665 | | /// |
666 | | /// For each PHI instance we can directly determine which was the incoming |
667 | | /// block, and hence derive which value the PHI has. |
668 | | /// |
669 | | /// The returned relation generally is injective, meaning that every PHI write |
670 | | /// has at most one (or zero, if the incoming block's branch does not jump to |
671 | | /// the PHI's block) PHI Read that reads it. However, due to the SCoP's |
672 | | /// parameter context it is possible a statement instance that would overwrite |
673 | | /// the PHI scalar is not in the statement's domain and thus a PHI write |
674 | | /// appear to be used twice. This is a static property, at runtime the |
675 | | /// runtime condition should avoid that a configuration is executed. Although |
676 | | /// incorrect, it should not have any effect in DeLICM. If it passes the |
677 | | /// conflict check, there are multiple locations, one for each PHI Read it |
678 | | /// matches, it had to write to. MemoryAccess::getAddressFunction() will |
679 | | /// select only one of them. That is, statically, not all necessary value are |
680 | | /// written, but the runtime check guards it from ever being executed. |
681 | | /// |
682 | | /// @param SAI The ScopArrayInfo representing the PHI's storage. |
683 | | /// |
684 | | /// @return { DomainPHIRead[] -> DomainPHIWrite[] } |
685 | 24 | isl::union_map computePerPHI(const ScopArrayInfo *SAI) { |
686 | 24 | assert(SAI->isPHIKind()); |
687 | 24 | |
688 | 24 | // { DomainPHIWrite[] -> Scatter[] } |
689 | 24 | auto PHIWriteScatter = makeEmptyUnionMap(); |
690 | 24 | |
691 | 24 | // Collect all incoming block timepoint. |
692 | 48 | for (auto *MA : S->getPHIIncomings(SAI)) { |
693 | 48 | auto Scatter = getScatterFor(MA); |
694 | 48 | PHIWriteScatter = |
695 | 48 | give(isl_union_map_add_map(PHIWriteScatter.take(), Scatter.take())); |
696 | 48 | } |
697 | 24 | |
698 | 24 | // { DomainPHIRead[] -> Scatter[] } |
699 | 24 | auto PHIReadScatter = getScatterFor(S->getPHIRead(SAI)); |
700 | 24 | |
701 | 24 | // { DomainPHIRead[] -> Scatter[] } |
702 | 24 | auto BeforeRead = beforeScatter(PHIReadScatter, true); |
703 | 24 | |
704 | 24 | // { Scatter[] } |
705 | 24 | auto WriteTimes = singleton( |
706 | 24 | give(isl_union_map_range(PHIWriteScatter.copy())), ScatterSpace); |
707 | 24 | |
708 | 24 | // { DomainPHIRead[] -> Scatter[] } |
709 | 24 | auto PHIWriteTimes = |
710 | 24 | give(isl_map_intersect_range(BeforeRead.take(), WriteTimes.take())); |
711 | 24 | auto LastPerPHIWrites = give(isl_map_lexmax(PHIWriteTimes.take())); |
712 | 24 | |
713 | 24 | // { DomainPHIRead[] -> DomainPHIWrite[] } |
714 | 24 | auto Result = give(isl_union_map_apply_range( |
715 | 24 | isl_union_map_from_map(LastPerPHIWrites.take()), |
716 | 24 | isl_union_map_reverse(PHIWriteScatter.take()))); |
717 | 24 | assert(isl_union_map_is_single_valued(Result.keep()) == isl_bool_true); |
718 | 24 | return Result; |
719 | 24 | } |
720 | | |
721 | | /// Try to map a MemoryKind::Value to a given array element. |
722 | | /// |
723 | | /// @param SAI Representation of the scalar's memory to map. |
724 | | /// @param TargetElt { Scatter[] -> Element[] } |
725 | | /// Suggestion where to map a scalar to when at a timepoint. |
726 | | /// |
727 | | /// @return true if the scalar was successfully mapped. |
728 | 39 | bool tryMapValue(const ScopArrayInfo *SAI, isl::map TargetElt) { |
729 | 39 | assert(SAI->isValueKind()); |
730 | 39 | |
731 | 39 | auto *DefMA = S->getValueDef(SAI); |
732 | 39 | assert(DefMA->isValueKind()); |
733 | 39 | assert(DefMA->isMustWrite()); |
734 | 39 | auto *V = DefMA->getAccessValue(); |
735 | 39 | auto *DefInst = DefMA->getAccessInstruction(); |
736 | 39 | |
737 | 39 | // Stop if the scalar has already been mapped. |
738 | 39 | if (!DefMA->getLatestScopArrayInfo()->isValueKind()) |
739 | 1 | return false; |
740 | 38 | |
741 | 38 | // { DomainDef[] -> Scatter[] } |
742 | 38 | auto DefSched = getScatterFor(DefMA); |
743 | 38 | |
744 | 38 | // Where each write is mapped to, according to the suggestion. |
745 | 38 | // { DomainDef[] -> Element[] } |
746 | 38 | auto DefTarget = give(isl_map_apply_domain( |
747 | 38 | TargetElt.copy(), isl_map_reverse(DefSched.copy()))); |
748 | 38 | simplify(DefTarget); |
749 | 38 | DEBUG(dbgs() << " Def Mapping: " << DefTarget << '\n'); |
750 | 38 | |
751 | 38 | auto OrigDomain = getDomainFor(DefMA); |
752 | 38 | auto MappedDomain = give(isl_map_domain(DefTarget.copy())); |
753 | 38 | if (!isl_set_is_subset(OrigDomain.keep(), MappedDomain.keep())38 ) { |
754 | 1 | DEBUG(dbgs() |
755 | 1 | << " Reject because mapping does not encompass all instances\n"); |
756 | 1 | return false; |
757 | 1 | } |
758 | 37 | |
759 | 37 | // { DomainDef[] -> Zone[] } |
760 | 37 | isl::map Lifetime; |
761 | 37 | |
762 | 37 | // { DomainDef[] -> DomainUse[] } |
763 | 37 | isl::union_map DefUses; |
764 | 37 | |
765 | 37 | std::tie(DefUses, Lifetime) = computeValueUses(SAI); |
766 | 37 | DEBUG(dbgs() << " Lifetime: " << Lifetime << '\n'); |
767 | 37 | |
768 | 37 | /// { [Element[] -> Zone[]] } |
769 | 37 | auto EltZone = give( |
770 | 37 | isl_map_wrap(isl_map_apply_domain(Lifetime.copy(), DefTarget.copy()))); |
771 | 37 | simplify(EltZone); |
772 | 37 | |
773 | 37 | // When known knowledge is disabled, just return the unknown value. It will |
774 | 37 | // either get filtered out or conflict with itself. |
775 | 37 | // { DomainDef[] -> ValInst[] } |
776 | 37 | isl::map ValInst; |
777 | 37 | if (DelicmComputeKnown) |
778 | 37 | ValInst = makeValInst(V, DefMA->getStatement(), |
779 | 37 | LI->getLoopFor(DefInst->getParent())); |
780 | 37 | else |
781 | 0 | ValInst = makeUnknownForDomain(DefMA->getStatement()); |
782 | 37 | |
783 | 37 | // { DomainDef[] -> [Element[] -> Zone[]] } |
784 | 37 | auto EltKnownTranslator = |
785 | 37 | give(isl_map_range_product(DefTarget.copy(), Lifetime.copy())); |
786 | 37 | |
787 | 37 | // { [Element[] -> Zone[]] -> ValInst[] } |
788 | 37 | auto EltKnown = |
789 | 37 | give(isl_map_apply_domain(ValInst.copy(), EltKnownTranslator.take())); |
790 | 37 | simplify(EltKnown); |
791 | 37 | |
792 | 37 | // { DomainDef[] -> [Element[] -> Scatter[]] } |
793 | 37 | auto WrittenTranslator = |
794 | 37 | give(isl_map_range_product(DefTarget.copy(), DefSched.take())); |
795 | 37 | |
796 | 37 | // { [Element[] -> Scatter[]] -> ValInst[] } |
797 | 37 | auto DefEltSched = |
798 | 37 | give(isl_map_apply_domain(ValInst.copy(), WrittenTranslator.take())); |
799 | 37 | simplify(DefEltSched); |
800 | 37 | |
801 | 37 | Knowledge Proposed(EltZone, nullptr, filterKnownValInst(EltKnown), |
802 | 37 | DefEltSched); |
803 | 37 | if (isConflicting(Proposed)) |
804 | 4 | return false; |
805 | 33 | |
806 | 33 | // { DomainUse[] -> Element[] } |
807 | 33 | auto UseTarget = give( |
808 | 33 | isl_union_map_apply_range(isl_union_map_reverse(DefUses.take()), |
809 | 33 | isl_union_map_from_map(DefTarget.copy()))); |
810 | 33 | |
811 | 33 | mapValue(SAI, std::move(DefTarget), std::move(UseTarget), |
812 | 33 | std::move(Lifetime), std::move(Proposed)); |
813 | 33 | return true; |
814 | 33 | } |
815 | | |
816 | | /// After a scalar has been mapped, update the global knowledge. |
817 | 54 | void applyLifetime(Knowledge Proposed) { |
818 | 54 | Zone.learnFrom(std::move(Proposed)); |
819 | 54 | } |
820 | | |
821 | | /// Map a MemoryKind::Value scalar to an array element. |
822 | | /// |
823 | | /// Callers must have ensured that the mapping is valid and not conflicting. |
824 | | /// |
825 | | /// @param SAI The ScopArrayInfo representing the scalar's memory to |
826 | | /// map. |
827 | | /// @param DefTarget { DomainDef[] -> Element[] } |
828 | | /// The array element to map the scalar to. |
829 | | /// @param UseTarget { DomainUse[] -> Element[] } |
830 | | /// The array elements the uses are mapped to. |
831 | | /// @param Lifetime { DomainDef[] -> Zone[] } |
832 | | /// The lifetime of each llvm::Value definition for |
833 | | /// reporting. |
834 | | /// @param Proposed Mapping constraints for reporting. |
835 | | void mapValue(const ScopArrayInfo *SAI, isl::map DefTarget, |
836 | | isl::union_map UseTarget, isl::map Lifetime, |
837 | 33 | Knowledge Proposed) { |
838 | 33 | // Redirect the read accesses. |
839 | 45 | for (auto *MA : S->getValueUses(SAI)) { |
840 | 45 | // { DomainUse[] } |
841 | 45 | auto Domain = getDomainFor(MA); |
842 | 45 | |
843 | 45 | // { DomainUse[] -> Element[] } |
844 | 45 | auto NewAccRel = give(isl_union_map_intersect_domain( |
845 | 45 | UseTarget.copy(), isl_union_set_from_set(Domain.take()))); |
846 | 45 | simplify(NewAccRel); |
847 | 45 | |
848 | 45 | assert(isl_union_map_n_map(NewAccRel.keep()) == 1); |
849 | 45 | MA->setNewAccessRelation(isl::map::from_union_map(NewAccRel)); |
850 | 45 | } |
851 | 33 | |
852 | 33 | auto *WA = S->getValueDef(SAI); |
853 | 33 | WA->setNewAccessRelation(DefTarget); |
854 | 33 | applyLifetime(Proposed); |
855 | 33 | |
856 | 33 | MappedValueScalars++; |
857 | 33 | NumberOfMappedValueScalars += 1; |
858 | 33 | } |
859 | | |
860 | | isl::map makeValInst(Value *Val, ScopStmt *UserStmt, Loop *Scope, |
861 | 83 | bool IsCertain = true) { |
862 | 83 | // When known knowledge is disabled, just return the unknown value. It will |
863 | 83 | // either get filtered out or conflict with itself. |
864 | 83 | if (!DelicmComputeKnown) |
865 | 0 | return makeUnknownForDomain(UserStmt); |
866 | 83 | return ZoneAlgorithm::makeValInst(Val, UserStmt, Scope, IsCertain); |
867 | 83 | } |
868 | | |
869 | | /// Express the incoming values of a PHI for each incoming statement in an |
870 | | /// isl::union_map. |
871 | | /// |
872 | | /// @param SAI The PHI scalar represented by a ScopArrayInfo. |
873 | | /// |
874 | | /// @return { PHIWriteDomain[] -> ValInst[] } |
875 | 23 | isl::union_map determinePHIWrittenValues(const ScopArrayInfo *SAI) { |
876 | 23 | auto Result = makeEmptyUnionMap(); |
877 | 23 | |
878 | 23 | // Collect the incoming values. |
879 | 46 | for (auto *MA : S->getPHIIncomings(SAI)) { |
880 | 46 | // { DomainWrite[] -> ValInst[] } |
881 | 46 | isl::union_map ValInst; |
882 | 46 | auto *WriteStmt = MA->getStatement(); |
883 | 46 | |
884 | 46 | auto Incoming = MA->getIncoming(); |
885 | 46 | assert(!Incoming.empty()); |
886 | 46 | if (Incoming.size() == 146 ) { |
887 | 46 | ValInst = makeValInst(Incoming[0].second, WriteStmt, |
888 | 46 | LI->getLoopFor(Incoming[0].first)); |
889 | 46 | } else { |
890 | 0 | // If the PHI is in a subregion's exit node it can have multiple |
891 | 0 | // incoming values (+ maybe another incoming edge from an unrelated |
892 | 0 | // block). We cannot directly represent it as a single llvm::Value. |
893 | 0 | // We currently model it as unknown value, but modeling as the PHIInst |
894 | 0 | // itself could be OK, too. |
895 | 0 | ValInst = makeUnknownForDomain(WriteStmt); |
896 | 0 | } |
897 | 46 | |
898 | 46 | Result = give(isl_union_map_union(Result.take(), ValInst.take())); |
899 | 46 | } |
900 | 23 | |
901 | 23 | assert(isl_union_map_is_single_valued(Result.keep()) == isl_bool_true && |
902 | 23 | "Cannot have multiple incoming values for same incoming statement"); |
903 | 23 | return Result; |
904 | 23 | } |
905 | | |
906 | | /// Try to map a MemoryKind::PHI scalar to a given array element. |
907 | | /// |
908 | | /// @param SAI Representation of the scalar's memory to map. |
909 | | /// @param TargetElt { Scatter[] -> Element[] } |
910 | | /// Suggestion where to map the scalar to when at a |
911 | | /// timepoint. |
912 | | /// |
913 | | /// @return true if the PHI scalar has been mapped. |
914 | 24 | bool tryMapPHI(const ScopArrayInfo *SAI, isl::map TargetElt) { |
915 | 24 | auto *PHIRead = S->getPHIRead(SAI); |
916 | 24 | assert(PHIRead->isPHIKind()); |
917 | 24 | assert(PHIRead->isRead()); |
918 | 24 | |
919 | 24 | // Skip if already been mapped. |
920 | 24 | if (!PHIRead->getLatestScopArrayInfo()->isPHIKind()) |
921 | 0 | return false; |
922 | 24 | |
923 | 24 | // { DomainRead[] -> Scatter[] } |
924 | 24 | auto PHISched = getScatterFor(PHIRead); |
925 | 24 | |
926 | 24 | // { DomainRead[] -> Element[] } |
927 | 24 | auto PHITarget = |
928 | 24 | give(isl_map_apply_range(PHISched.copy(), TargetElt.copy())); |
929 | 24 | simplify(PHITarget); |
930 | 24 | DEBUG(dbgs() << " Mapping: " << PHITarget << '\n'); |
931 | 24 | |
932 | 24 | auto OrigDomain = getDomainFor(PHIRead); |
933 | 24 | auto MappedDomain = give(isl_map_domain(PHITarget.copy())); |
934 | 24 | if (!isl_set_is_subset(OrigDomain.keep(), MappedDomain.keep())24 ) { |
935 | 0 | DEBUG(dbgs() |
936 | 0 | << " Reject because mapping does not encompass all instances\n"); |
937 | 0 | return false; |
938 | 0 | } |
939 | 24 | |
940 | 24 | // { DomainRead[] -> DomainWrite[] } |
941 | 24 | auto PerPHIWrites = computePerPHI(SAI); |
942 | 24 | |
943 | 24 | // { DomainWrite[] -> Element[] } |
944 | 24 | auto WritesTarget = give(isl_union_map_reverse(isl_union_map_apply_domain( |
945 | 24 | PerPHIWrites.copy(), isl_union_map_from_map(PHITarget.copy())))); |
946 | 24 | simplify(WritesTarget); |
947 | 24 | |
948 | 24 | // { DomainWrite[] } |
949 | 24 | auto UniverseWritesDom = give(isl_union_set_empty(ParamSpace.copy())); |
950 | 24 | |
951 | 24 | for (auto *MA : S->getPHIIncomings(SAI)) |
952 | 48 | UniverseWritesDom = give(isl_union_set_add_set(UniverseWritesDom.take(), |
953 | 48 | getDomainFor(MA).take())); |
954 | 24 | |
955 | 24 | auto RelevantWritesTarget = WritesTarget; |
956 | 24 | if (DelicmOverapproximateWrites) |
957 | 11 | WritesTarget = expandMapping(WritesTarget, UniverseWritesDom); |
958 | 24 | |
959 | 24 | auto ExpandedWritesDom = give(isl_union_map_domain(WritesTarget.copy())); |
960 | 24 | if (!DelicmPartialWrites && |
961 | 3 | !isl_union_set_is_subset(UniverseWritesDom.keep(), |
962 | 24 | ExpandedWritesDom.keep())) { |
963 | 1 | DEBUG(dbgs() << " Reject because did not find PHI write mapping for " |
964 | 1 | "all instances\n"); |
965 | 1 | if (DelicmOverapproximateWrites) |
966 | 1 | DEBUG(dbgs() << " Relevant Mapping: " << RelevantWritesTarget |
967 | 1 | << '\n'); |
968 | 1 | DEBUG(dbgs() << " Deduced Mapping: " << WritesTarget << '\n'); |
969 | 1 | DEBUG(dbgs() << " Missing instances: " |
970 | 1 | << give(isl_union_set_subtract(UniverseWritesDom.copy(), |
971 | 1 | ExpandedWritesDom.copy())) |
972 | 1 | << '\n'); |
973 | 1 | return false; |
974 | 1 | } |
975 | 23 | |
976 | 23 | // { DomainRead[] -> Scatter[] } |
977 | 23 | auto PerPHIWriteScatter = give(isl_map_from_union_map( |
978 | 23 | isl_union_map_apply_range(PerPHIWrites.copy(), Schedule.copy()))); |
979 | 23 | |
980 | 23 | // { DomainRead[] -> Zone[] } |
981 | 23 | auto Lifetime = betweenScatter(PerPHIWriteScatter, PHISched, false, true); |
982 | 23 | simplify(Lifetime); |
983 | 23 | DEBUG(dbgs() << " Lifetime: " << Lifetime << "\n"); |
984 | 23 | |
985 | 23 | // { DomainWrite[] -> Zone[] } |
986 | 23 | auto WriteLifetime = give(isl_union_map_apply_domain( |
987 | 23 | isl_union_map_from_map(Lifetime.copy()), PerPHIWrites.copy())); |
988 | 23 | |
989 | 23 | // { DomainWrite[] -> ValInst[] } |
990 | 23 | auto WrittenValue = determinePHIWrittenValues(SAI); |
991 | 23 | |
992 | 23 | // { DomainWrite[] -> [Element[] -> Scatter[]] } |
993 | 23 | auto WrittenTranslator = |
994 | 23 | give(isl_union_map_range_product(WritesTarget.copy(), Schedule.copy())); |
995 | 23 | |
996 | 23 | // { [Element[] -> Scatter[]] -> ValInst[] } |
997 | 23 | auto Written = give(isl_union_map_apply_domain(WrittenValue.copy(), |
998 | 23 | WrittenTranslator.copy())); |
999 | 23 | simplify(Written); |
1000 | 23 | |
1001 | 23 | // { DomainWrite[] -> [Element[] -> Zone[]] } |
1002 | 23 | auto LifetimeTranslator = give( |
1003 | 23 | isl_union_map_range_product(WritesTarget.copy(), WriteLifetime.copy())); |
1004 | 23 | |
1005 | 23 | // { DomainWrite[] -> ValInst[] } |
1006 | 23 | auto WrittenKnownValue = filterKnownValInst(WrittenValue); |
1007 | 23 | |
1008 | 23 | // { [Element[] -> Zone[]] -> ValInst[] } |
1009 | 23 | auto EltLifetimeInst = give(isl_union_map_apply_domain( |
1010 | 23 | WrittenKnownValue.copy(), LifetimeTranslator.copy())); |
1011 | 23 | simplify(EltLifetimeInst); |
1012 | 23 | |
1013 | 23 | // { [Element[] -> Zone[] } |
1014 | 23 | auto Occupied = give(isl_union_map_range(LifetimeTranslator.copy())); |
1015 | 23 | simplify(Occupied); |
1016 | 23 | |
1017 | 23 | Knowledge Proposed(Occupied, nullptr, EltLifetimeInst, Written); |
1018 | 23 | if (isConflicting(Proposed)) |
1019 | 2 | return false; |
1020 | 21 | |
1021 | 21 | mapPHI(SAI, std::move(PHITarget), std::move(WritesTarget), |
1022 | 21 | std::move(Lifetime), std::move(Proposed)); |
1023 | 21 | return true; |
1024 | 21 | } |
1025 | | |
1026 | | /// Map a MemoryKind::PHI scalar to an array element. |
1027 | | /// |
1028 | | /// Callers must have ensured that the mapping is valid and not conflicting |
1029 | | /// with the common knowledge. |
1030 | | /// |
1031 | | /// @param SAI The ScopArrayInfo representing the scalar's memory to |
1032 | | /// map. |
1033 | | /// @param ReadTarget { DomainRead[] -> Element[] } |
1034 | | /// The array element to map the scalar to. |
1035 | | /// @param WriteTarget { DomainWrite[] -> Element[] } |
1036 | | /// New access target for each PHI incoming write. |
1037 | | /// @param Lifetime { DomainRead[] -> Zone[] } |
1038 | | /// The lifetime of each PHI for reporting. |
1039 | | /// @param Proposed Mapping constraints for reporting. |
1040 | | void mapPHI(const ScopArrayInfo *SAI, isl::map ReadTarget, |
1041 | | isl::union_map WriteTarget, isl::map Lifetime, |
1042 | 21 | Knowledge Proposed) { |
1043 | 21 | // { Element[] } |
1044 | 21 | isl::space ElementSpace = ReadTarget.get_space().range(); |
1045 | 21 | |
1046 | 21 | // Redirect the PHI incoming writes. |
1047 | 42 | for (auto *MA : S->getPHIIncomings(SAI)) { |
1048 | 42 | // { DomainWrite[] } |
1049 | 42 | auto Domain = getDomainFor(MA); |
1050 | 42 | |
1051 | 42 | // { DomainWrite[] -> Element[] } |
1052 | 42 | auto NewAccRel = give(isl_union_map_intersect_domain( |
1053 | 42 | WriteTarget.copy(), isl_union_set_from_set(Domain.copy()))); |
1054 | 42 | simplify(NewAccRel); |
1055 | 42 | |
1056 | 42 | isl::space NewAccRelSpace = |
1057 | 42 | Domain.get_space().map_from_domain_and_range(ElementSpace); |
1058 | 42 | isl::map NewAccRelMap = singleton(NewAccRel, NewAccRelSpace); |
1059 | 42 | MA->setNewAccessRelation(NewAccRelMap); |
1060 | 42 | } |
1061 | 21 | |
1062 | 21 | // Redirect the PHI read. |
1063 | 21 | auto *PHIRead = S->getPHIRead(SAI); |
1064 | 21 | PHIRead->setNewAccessRelation(ReadTarget); |
1065 | 21 | applyLifetime(Proposed); |
1066 | 21 | |
1067 | 21 | MappedPHIScalars++; |
1068 | 21 | NumberOfMappedPHIScalars++; |
1069 | 21 | } |
1070 | | |
1071 | | /// Search and map scalars to memory overwritten by @p TargetStoreMA. |
1072 | | /// |
1073 | | /// Start trying to map scalars that are used in the same statement as the |
1074 | | /// store. For every successful mapping, try to also map scalars of the |
1075 | | /// statements where those are written. Repeat, until no more mapping |
1076 | | /// opportunity is found. |
1077 | | /// |
1078 | | /// There is currently no preference in which order scalars are tried. |
1079 | | /// Ideally, we would direct it towards a load instruction of the same array |
1080 | | /// element. |
1081 | 30 | bool collapseScalarsToStore(MemoryAccess *TargetStoreMA) { |
1082 | 30 | assert(TargetStoreMA->isLatestArrayKind()); |
1083 | 30 | assert(TargetStoreMA->isMustWrite()); |
1084 | 30 | |
1085 | 30 | auto TargetStmt = TargetStoreMA->getStatement(); |
1086 | 30 | |
1087 | 30 | // { DomTarget[] } |
1088 | 30 | auto TargetDom = getDomainFor(TargetStmt); |
1089 | 30 | |
1090 | 30 | // { DomTarget[] -> Element[] } |
1091 | 30 | auto TargetAccRel = getAccessRelationFor(TargetStoreMA); |
1092 | 30 | |
1093 | 30 | // { Zone[] -> DomTarget[] } |
1094 | 30 | // For each point in time, find the next target store instance. |
1095 | 30 | auto Target = |
1096 | 30 | computeScalarReachingOverwrite(Schedule, TargetDom, false, true); |
1097 | 30 | |
1098 | 30 | // { Zone[] -> Element[] } |
1099 | 30 | // Use the target store's write location as a suggestion to map scalars to. |
1100 | 30 | auto EltTarget = |
1101 | 30 | give(isl_map_apply_range(Target.take(), TargetAccRel.take())); |
1102 | 30 | simplify(EltTarget); |
1103 | 30 | DEBUG(dbgs() << " Target mapping is " << EltTarget << '\n'); |
1104 | 30 | |
1105 | 30 | // Stack of elements not yet processed. |
1106 | 30 | SmallVector<MemoryAccess *, 16> Worklist; |
1107 | 30 | |
1108 | 30 | // Set of scalars already tested. |
1109 | 30 | SmallPtrSet<const ScopArrayInfo *, 16> Closed; |
1110 | 30 | |
1111 | 30 | // Lambda to add all scalar reads to the work list. |
1112 | 64 | auto ProcessAllIncoming = [&](ScopStmt *Stmt) { |
1113 | 134 | for (auto *MA : *Stmt) { |
1114 | 134 | if (!MA->isLatestScalarKind()) |
1115 | 87 | continue; |
1116 | 47 | if (47 !MA->isRead()47 ) |
1117 | 11 | continue; |
1118 | 36 | |
1119 | 36 | Worklist.push_back(MA); |
1120 | 36 | } |
1121 | 64 | }; |
1122 | 30 | |
1123 | 30 | auto *WrittenVal = TargetStoreMA->getAccessInstruction()->getOperand(0); |
1124 | 30 | if (auto *WrittenValInputMA = TargetStmt->lookupInputAccessOf(WrittenVal)) |
1125 | 22 | Worklist.push_back(WrittenValInputMA); |
1126 | 30 | else |
1127 | 8 | ProcessAllIncoming(TargetStmt); |
1128 | 30 | |
1129 | 30 | auto AnyMapped = false; |
1130 | 30 | auto &DL = S->getRegion().getEntry()->getModule()->getDataLayout(); |
1131 | 30 | auto StoreSize = |
1132 | 30 | DL.getTypeAllocSize(TargetStoreMA->getAccessValue()->getType()); |
1133 | 30 | |
1134 | 107 | while (!Worklist.empty()107 ) { |
1135 | 77 | auto *MA = Worklist.pop_back_val(); |
1136 | 77 | |
1137 | 77 | auto *SAI = MA->getScopArrayInfo(); |
1138 | 77 | if (Closed.count(SAI)) |
1139 | 10 | continue; |
1140 | 67 | Closed.insert(SAI); |
1141 | 67 | DEBUG(dbgs() << "\n Trying to map " << MA << " (SAI: " << SAI |
1142 | 67 | << ")\n"); |
1143 | 67 | |
1144 | 67 | // Skip non-mappable scalars. |
1145 | 67 | if (!isMappable(SAI)) |
1146 | 3 | continue; |
1147 | 64 | |
1148 | 64 | auto MASize = DL.getTypeAllocSize(MA->getAccessValue()->getType()); |
1149 | 64 | if (MASize > StoreSize64 ) { |
1150 | 1 | DEBUG(dbgs() << " Reject because storage size is insufficient\n"); |
1151 | 1 | continue; |
1152 | 1 | } |
1153 | 63 | |
1154 | 63 | // Try to map MemoryKind::Value scalars. |
1155 | 63 | if (63 SAI->isValueKind()63 ) { |
1156 | 39 | if (!tryMapValue(SAI, EltTarget)) |
1157 | 6 | continue; |
1158 | 33 | |
1159 | 33 | auto *DefAcc = S->getValueDef(SAI); |
1160 | 33 | ProcessAllIncoming(DefAcc->getStatement()); |
1161 | 33 | |
1162 | 33 | AnyMapped = true; |
1163 | 33 | continue; |
1164 | 33 | } |
1165 | 24 | |
1166 | 24 | // Try to map MemoryKind::PHI scalars. |
1167 | 24 | if (24 SAI->isPHIKind()24 ) { |
1168 | 24 | if (!tryMapPHI(SAI, EltTarget)) |
1169 | 3 | continue; |
1170 | 21 | // Add inputs of all incoming statements to the worklist. Prefer the |
1171 | 21 | // input accesses of the incoming blocks. |
1172 | 21 | for (auto *PHIWrite : S->getPHIIncomings(SAI)) 21 { |
1173 | 42 | auto *PHIWriteStmt = PHIWrite->getStatement(); |
1174 | 42 | bool FoundAny = false; |
1175 | 42 | for (auto Incoming : PHIWrite->getIncoming()) { |
1176 | 42 | auto *IncomingInputMA = |
1177 | 42 | PHIWriteStmt->lookupInputAccessOf(Incoming.second); |
1178 | 42 | if (!IncomingInputMA) |
1179 | 23 | continue; |
1180 | 19 | |
1181 | 19 | Worklist.push_back(IncomingInputMA); |
1182 | 19 | FoundAny = true; |
1183 | 19 | } |
1184 | 42 | |
1185 | 42 | if (!FoundAny) |
1186 | 23 | ProcessAllIncoming(PHIWrite->getStatement()); |
1187 | 42 | } |
1188 | 24 | |
1189 | 24 | AnyMapped = true; |
1190 | 24 | continue; |
1191 | 24 | } |
1192 | 77 | } |
1193 | 30 | |
1194 | 30 | if (AnyMapped30 ) { |
1195 | 19 | TargetsMapped++; |
1196 | 19 | NumberOfTargetsMapped++; |
1197 | 19 | } |
1198 | 30 | return AnyMapped; |
1199 | 30 | } |
1200 | | |
1201 | | /// Compute when an array element is unused. |
1202 | | /// |
1203 | | /// @return { [Element[] -> Zone[]] } |
1204 | 36 | isl::union_set computeLifetime() const { |
1205 | 36 | // { Element[] -> Zone[] } |
1206 | 36 | auto ArrayUnused = computeArrayUnused(Schedule, AllMustWrites, AllReads, |
1207 | 36 | false, false, true); |
1208 | 36 | |
1209 | 36 | auto Result = give(isl_union_map_wrap(ArrayUnused.copy())); |
1210 | 36 | |
1211 | 36 | simplify(Result); |
1212 | 36 | return Result; |
1213 | 36 | } |
1214 | | |
1215 | | /// Determine when an array element is written to, and which value instance is |
1216 | | /// written. |
1217 | | /// |
1218 | | /// @return { [Element[] -> Scatter[]] -> ValInst[] } |
1219 | 36 | isl::union_map computeWritten() const { |
1220 | 36 | // { [Element[] -> Scatter[]] -> ValInst[] } |
1221 | 36 | auto EltWritten = applyDomainRange(AllWriteValInst, Schedule); |
1222 | 36 | |
1223 | 36 | simplify(EltWritten); |
1224 | 36 | return EltWritten; |
1225 | 36 | } |
1226 | | |
1227 | | /// Determine whether an access touches at most one element. |
1228 | | /// |
1229 | | /// The accessed element could be a scalar or accessing an array with constant |
1230 | | /// subscript, such that all instances access only that element. |
1231 | | /// |
1232 | | /// @param MA The access to test. |
1233 | | /// |
1234 | | /// @return True, if zero or one elements are accessed; False if at least two |
1235 | | /// different elements are accessed. |
1236 | 43 | bool isScalarAccess(MemoryAccess *MA) { |
1237 | 43 | auto Map = getAccessRelationFor(MA); |
1238 | 43 | auto Set = give(isl_map_range(Map.take())); |
1239 | 43 | return isl_set_is_singleton(Set.keep()) == isl_bool_true; |
1240 | 43 | } |
1241 | | |
1242 | | /// Print mapping statistics to @p OS. |
1243 | 34 | void printStatistics(llvm::raw_ostream &OS, int Indent = 0) const { |
1244 | 34 | OS.indent(Indent) << "Statistics {\n"; |
1245 | 34 | OS.indent(Indent + 4) << "Compatible overwrites: " |
1246 | 34 | << NumberOfCompatibleTargets << "\n"; |
1247 | 34 | OS.indent(Indent + 4) << "Overwrites mapped to: " << NumberOfTargetsMapped |
1248 | 34 | << '\n'; |
1249 | 34 | OS.indent(Indent + 4) << "Value scalars mapped: " |
1250 | 34 | << NumberOfMappedValueScalars << '\n'; |
1251 | 34 | OS.indent(Indent + 4) << "PHI scalars mapped: " |
1252 | 34 | << NumberOfMappedPHIScalars << '\n'; |
1253 | 34 | OS.indent(Indent) << "}\n"; |
1254 | 34 | } |
1255 | | |
1256 | | /// Return whether at least one transformation been applied. |
1257 | 34 | bool isModified() const { return NumberOfTargetsMapped > 0; } |
1258 | | |
1259 | | public: |
1260 | 36 | DeLICMImpl(Scop *S, LoopInfo *LI) : ZoneAlgorithm("polly-delicm", S, LI) {} |
1261 | | |
1262 | | /// Calculate the lifetime (definition to last use) of every array element. |
1263 | | /// |
1264 | | /// @return True if the computed lifetimes (#Zone) is usable. |
1265 | 36 | bool computeZone() { |
1266 | 36 | // Check that nothing strange occurs. |
1267 | 36 | collectCompatibleElts(); |
1268 | 36 | |
1269 | 36 | isl::union_set EltUnused; |
1270 | 36 | isl::union_map EltKnown, EltWritten; |
1271 | 36 | |
1272 | 36 | { |
1273 | 36 | IslMaxOperationsGuard MaxOpGuard(IslCtx.get(), DelicmMaxOps); |
1274 | 36 | |
1275 | 36 | computeCommon(); |
1276 | 36 | |
1277 | 36 | EltUnused = computeLifetime(); |
1278 | 36 | EltKnown = computeKnown(true, false); |
1279 | 36 | EltWritten = computeWritten(); |
1280 | 36 | } |
1281 | 36 | DeLICMAnalyzed++; |
1282 | 36 | |
1283 | 36 | if (!EltUnused || 36 !EltKnown35 || !EltWritten35 ) { |
1284 | 1 | assert(isl_ctx_last_error(IslCtx.get()) == isl_error_quota && |
1285 | 1 | "The only reason that these things have not been computed should " |
1286 | 1 | "be if the max-operations limit hit"); |
1287 | 1 | DeLICMOutOfQuota++; |
1288 | 1 | DEBUG(dbgs() << "DeLICM analysis exceeded max_operations\n"); |
1289 | 1 | DebugLoc Begin, End; |
1290 | 1 | getDebugLocations(getBBPairForRegion(&S->getRegion()), Begin, End); |
1291 | 1 | OptimizationRemarkAnalysis R(DEBUG_TYPE, "OutOfQuota", Begin, |
1292 | 1 | S->getEntry()); |
1293 | 1 | R << "maximal number of operations exceeded during zone analysis"; |
1294 | 1 | S->getFunction().getContext().diagnose(R); |
1295 | 1 | return false; |
1296 | 1 | } |
1297 | 35 | |
1298 | 35 | Zone = OriginalZone = Knowledge(nullptr, EltUnused, EltKnown, EltWritten); |
1299 | 35 | DEBUG(dbgs() << "Computed Zone:\n"; OriginalZone.print(dbgs(), 4)); |
1300 | 36 | |
1301 | 36 | assert(Zone.isUsable() && OriginalZone.isUsable()); |
1302 | 36 | return true; |
1303 | 36 | } |
1304 | | |
1305 | | /// Try to map as many scalars to unused array elements as possible. |
1306 | | /// |
1307 | | /// Multiple scalars might be mappable to intersecting unused array element |
1308 | | /// zones, but we can only chose one. This is a greedy algorithm, therefore |
1309 | | /// the first processed element claims it. |
1310 | 35 | void greedyCollapse() { |
1311 | 35 | bool Modified = false; |
1312 | 35 | |
1313 | 162 | for (auto &Stmt : *S) { |
1314 | 325 | for (auto *MA : Stmt) { |
1315 | 325 | if (!MA->isLatestArrayKind()) |
1316 | 252 | continue; |
1317 | 73 | if (73 !MA->isWrite()73 ) |
1318 | 25 | continue; |
1319 | 48 | |
1320 | 48 | if (48 MA->isMayWrite()48 ) { |
1321 | 4 | DEBUG(dbgs() << "Access " << MA |
1322 | 4 | << " pruned because it is a MAY_WRITE\n"); |
1323 | 4 | OptimizationRemarkMissed R(DEBUG_TYPE, "TargetMayWrite", |
1324 | 4 | MA->getAccessInstruction()); |
1325 | 4 | R << "Skipped possible mapping target because it is not an " |
1326 | 4 | "unconditional overwrite"; |
1327 | 4 | S->getFunction().getContext().diagnose(R); |
1328 | 4 | continue; |
1329 | 4 | } |
1330 | 44 | |
1331 | 44 | if (44 Stmt.getNumIterators() == 044 ) { |
1332 | 1 | DEBUG(dbgs() << "Access " << MA |
1333 | 1 | << " pruned because it is not in a loop\n"); |
1334 | 1 | OptimizationRemarkMissed R(DEBUG_TYPE, "WriteNotInLoop", |
1335 | 1 | MA->getAccessInstruction()); |
1336 | 1 | R << "skipped possible mapping target because it is not in a loop"; |
1337 | 1 | S->getFunction().getContext().diagnose(R); |
1338 | 1 | continue; |
1339 | 1 | } |
1340 | 43 | |
1341 | 43 | if (43 isScalarAccess(MA)43 ) { |
1342 | 6 | DEBUG(dbgs() << "Access " << MA |
1343 | 6 | << " pruned because it writes only a single element\n"); |
1344 | 6 | OptimizationRemarkMissed R(DEBUG_TYPE, "ScalarWrite", |
1345 | 6 | MA->getAccessInstruction()); |
1346 | 6 | R << "skipped possible mapping target because the memory location " |
1347 | 6 | "written to does not depend on its outer loop"; |
1348 | 6 | S->getFunction().getContext().diagnose(R); |
1349 | 6 | continue; |
1350 | 6 | } |
1351 | 37 | |
1352 | 37 | if (37 !isa<StoreInst>(MA->getAccessInstruction())37 ) { |
1353 | 3 | DEBUG(dbgs() << "Access " << MA |
1354 | 3 | << " pruned because it is not a StoreInst\n"); |
1355 | 3 | OptimizationRemarkMissed R(DEBUG_TYPE, "NotAStore", |
1356 | 3 | MA->getAccessInstruction()); |
1357 | 3 | R << "skipped possible mapping target because non-store instructions " |
1358 | 3 | "are not supported"; |
1359 | 3 | S->getFunction().getContext().diagnose(R); |
1360 | 3 | continue; |
1361 | 3 | } |
1362 | 34 | |
1363 | 34 | isl::union_set TouchedElts = MA->getLatestAccessRelation().range(); |
1364 | 34 | if (!TouchedElts.is_subset(CompatibleElts)34 ) { |
1365 | 4 | DEBUG( |
1366 | 4 | dbgs() |
1367 | 4 | << "Access " << MA |
1368 | 4 | << " is incompatible because it touches incompatible elements\n"); |
1369 | 4 | OptimizationRemarkMissed R(DEBUG_TYPE, "IncompatibleElts", |
1370 | 4 | MA->getAccessInstruction()); |
1371 | 4 | R << "skipped possible mapping target because a target location " |
1372 | 4 | "cannot be reliably analyzed"; |
1373 | 4 | S->getFunction().getContext().diagnose(R); |
1374 | 4 | continue; |
1375 | 4 | } |
1376 | 30 | |
1377 | 34 | assert(isCompatibleAccess(MA)); |
1378 | 30 | NumberOfCompatibleTargets++; |
1379 | 30 | DEBUG(dbgs() << "Analyzing target access " << MA << "\n"); |
1380 | 30 | if (collapseScalarsToStore(MA)) |
1381 | 19 | Modified = true; |
1382 | 325 | } |
1383 | 162 | } |
1384 | 35 | |
1385 | 35 | if (Modified) |
1386 | 19 | DeLICMScopsModified++; |
1387 | 35 | } |
1388 | | |
1389 | | /// Dump the internal information about a performed DeLICM to @p OS. |
1390 | 35 | void print(llvm::raw_ostream &OS, int Indent = 0) { |
1391 | 35 | if (!Zone.isUsable()35 ) { |
1392 | 1 | OS.indent(Indent) << "Zone not computed\n"; |
1393 | 1 | return; |
1394 | 1 | } |
1395 | 34 | |
1396 | 34 | printStatistics(OS, Indent); |
1397 | 34 | if (!isModified()34 ) { |
1398 | 16 | OS.indent(Indent) << "No modification has been made\n"; |
1399 | 16 | return; |
1400 | 16 | } |
1401 | 18 | printAccesses(OS, Indent); |
1402 | 18 | } |
1403 | | }; |
1404 | | |
1405 | | class DeLICM : public ScopPass { |
1406 | | private: |
1407 | | DeLICM(const DeLICM &) = delete; |
1408 | | const DeLICM &operator=(const DeLICM &) = delete; |
1409 | | |
1410 | | /// The pass implementation, also holding per-scop data. |
1411 | | std::unique_ptr<DeLICMImpl> Impl; |
1412 | | |
1413 | 36 | void collapseToUnused(Scop &S) { |
1414 | 36 | auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); |
1415 | 36 | Impl = make_unique<DeLICMImpl>(&S, &LI); |
1416 | 36 | |
1417 | 36 | if (!Impl->computeZone()36 ) { |
1418 | 1 | DEBUG(dbgs() << "Abort because cannot reliably compute lifetimes\n"); |
1419 | 1 | return; |
1420 | 1 | } |
1421 | 35 | |
1422 | 35 | DEBUG35 (dbgs() << "Collapsing scalars to unused array elements...\n"); |
1423 | 35 | Impl->greedyCollapse(); |
1424 | 35 | |
1425 | 35 | DEBUG(dbgs() << "\nFinal Scop:\n"); |
1426 | 35 | DEBUG(dbgs() << S); |
1427 | 36 | } |
1428 | | |
1429 | | public: |
1430 | | static char ID; |
1431 | 36 | explicit DeLICM() : ScopPass(ID) {} |
1432 | | |
1433 | 36 | virtual void getAnalysisUsage(AnalysisUsage &AU) const override { |
1434 | 36 | AU.addRequiredTransitive<ScopInfoRegionPass>(); |
1435 | 36 | AU.addRequired<LoopInfoWrapperPass>(); |
1436 | 36 | AU.setPreservesAll(); |
1437 | 36 | } |
1438 | | |
1439 | 36 | virtual bool runOnScop(Scop &S) override { |
1440 | 36 | // Free resources for previous scop's computation, if not yet done. |
1441 | 36 | releaseMemory(); |
1442 | 36 | |
1443 | 36 | collapseToUnused(S); |
1444 | 36 | |
1445 | 36 | auto ScopStats = S.getStatistics(); |
1446 | 36 | NumValueWrites += ScopStats.NumValueWrites; |
1447 | 36 | NumValueWritesInLoops += ScopStats.NumValueWritesInLoops; |
1448 | 36 | NumPHIWrites += ScopStats.NumPHIWrites; |
1449 | 36 | NumPHIWritesInLoops += ScopStats.NumPHIWritesInLoops; |
1450 | 36 | NumSingletonWrites += ScopStats.NumSingletonWrites; |
1451 | 36 | NumSingletonWritesInLoops += ScopStats.NumSingletonWritesInLoops; |
1452 | 36 | |
1453 | 36 | return false; |
1454 | 36 | } |
1455 | | |
1456 | 35 | virtual void printScop(raw_ostream &OS, Scop &S) const override { |
1457 | 35 | if (!Impl) |
1458 | 0 | return; |
1459 | 35 | assert(Impl->getScop() == &S); |
1460 | 35 | |
1461 | 35 | OS << "DeLICM result:\n"; |
1462 | 35 | Impl->print(OS); |
1463 | 35 | } |
1464 | | |
1465 | 191 | virtual void releaseMemory() override { Impl.reset(); } |
1466 | | }; |
1467 | | |
1468 | | char DeLICM::ID; |
1469 | | } // anonymous namespace |
1470 | | |
1471 | 0 | Pass *polly::createDeLICMPass() { return new DeLICM(); } |
1472 | | |
1473 | 41.7k | INITIALIZE_PASS_BEGIN41.7k (DeLICM, "polly-delicm", "Polly - DeLICM/DePRE", false,
|
1474 | 41.7k | false) |
1475 | 41.7k | INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass) |
1476 | 41.7k | INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) |
1477 | 41.7k | INITIALIZE_PASS_END(DeLICM, "polly-delicm", "Polly - DeLICM/DePRE", false, |
1478 | | false) |
1479 | | |
1480 | | bool polly::isConflicting( |
1481 | | isl::union_set ExistingOccupied, isl::union_set ExistingUnused, |
1482 | | isl::union_map ExistingKnown, isl::union_map ExistingWrites, |
1483 | | isl::union_set ProposedOccupied, isl::union_set ProposedUnused, |
1484 | | isl::union_map ProposedKnown, isl::union_map ProposedWrites, |
1485 | 232 | llvm::raw_ostream *OS, unsigned Indent) { |
1486 | 232 | Knowledge Existing(std::move(ExistingOccupied), std::move(ExistingUnused), |
1487 | 232 | std::move(ExistingKnown), std::move(ExistingWrites)); |
1488 | 232 | Knowledge Proposed(std::move(ProposedOccupied), std::move(ProposedUnused), |
1489 | 232 | std::move(ProposedKnown), std::move(ProposedWrites)); |
1490 | 232 | |
1491 | 232 | return Knowledge::isConflicting(Existing, Proposed, OS, Indent); |
1492 | 232 | } |