Page MenuHomePhabricator

[Polly][ZoneAlgo/ForwardOpTree] Normalize PHIs to their known incoming values.

Authored by Meinersbur on Oct 26 2017, 8:19 AM.



Represent PHIs by their incoming values instead of an opaque value of themselves. This allows ForwardOpTree to "look through" the PHIs and forward the incoming values since forwardings PHIs is currently not supported.

This is particularly useful to cope with PHIs inserted by GVN LoadPRE. The incoming values all resolve to a load from a single array element which then can be forwarded.

It should in theory also reduce spurious conflicts in value mapping (DeLICM), but I have not yet found a profitable case yet.

To avoid transitive closure and potentially necessary overapproximations of those, PHIs that may reference themselves are excluded from normalization and keep their opaque self-representation.

The feature is disabled by default because it currently causes a significant compile time increase (when the max operations limit is disabled). Either we resolve this bottleneck (mostly in ZoneAlgorithm::computeKnownFromLoad()) or introduce support forwarding PHIs instead. In both cases, having the ability to remove any (non-recursive) PHI from the known content map is a good test to determine whether these cause a problem.

Diff Detail


Event Timeline

Meinersbur created this revision.Oct 26 2017, 8:19 AM

Add selfrefphi test case

grosser accepted this revision.Oct 26 2017, 11:30 PM

LGTM, otherwise.

103 ↗(On Diff #120429)

Do we need all these attributes?

This revision is now accepted and ready to land.Oct 26 2017, 11:30 PM
  • Introduce isNormalizable to resolve TODO
  • Remove unused function attributes in test-case
  • Add example to NormalizedPHI doxygen
bollu added inline comments.Oct 30 2017, 3:29 AM
118 ↗(On Diff #120786)

"We correctness" -> "We want correctness", perhaps?

326 ↗(On Diff #120786)

What does Normalized exactly refer to, here? I assume it refers to the PHI node normalization, but can we look for a better name? Normal is one of the most overloaded words there is :). Something like, isUnderstandablePHIRead? (I don't like that name either)

487 ↗(On Diff #120786)

consider const PHINode *PHI? From what I can see, no mutation is required of the PHI, and all methods used from the Phi node have const versions.

771 ↗(On Diff #120786)

Could you please document what Input and NormalizedPHIs are expected to look like?

773 ↗(On Diff #120786)

consider const DenseSet<PHINode *> &TranslatedPHIs? It's only used to count.

989 ↗(On Diff #120786)

Double negative: consider assert(PHIMap.is_single_valued().is_true())

Meinersbur marked 3 inline comments as done.
  • Address Siddharth's remarks
  • Fix one more TODO
Meinersbur added inline comments.Oct 30 2017, 7:33 AM
326 ↗(On Diff #120786)

@see #ZoneAlgorithm::NormalizeMap which explains what is going on.

I agree that there might be a better name than "normalize", however I am 80% satisfied with the name. Due to the existence of PHIs, there are multiple ValInsts representing the same value. "Normalization" is the process of keeping (ideally) one of these.

"Computable" as used in ComputedPHIs might be an alternative. However, PHINodes are also not the only source of normalization. For instance, a LoadInst might always read a previously stored ValInst. We could normalize the ValInst for the loaded value by the ValInst that was stored before.

isUnderstandablePHIRead kind of implies to me that other PHIs are not understandable, what would that mean?

487 ↗(On Diff #120786)

I did the change, but note that IMHO the const here is useless. The llvm::PHINode structure has not been designed around constness. E.g.


gets you a const-free object without any const-cast, the const gives a false sense that the object cannot be modified and adds clutter to declarations.

Generally, llvm::Value objects are identified by their address. That is, even after modifying it, we still means the same SSA value, so const does not accomplish anything,. This is different for e.g. SCEV, DenseSet.

In the past (eg. rL292480) we already had to remove const keywords that were added just because it could be added; it forced us to insert const_casts if we wanted to change code.

989 ↗(On Diff #120786)

is_single_valued() returns a tri-valued isl::boolean. The intended meaning is


Unfortunately is_true_or_error() did not make it into the isl API. Another alternative could be

assert(PHIMap.is_single_valued().is_error() || PHIMap.is_single_valued().is_true());

Unfortunately the quota limit could run out in the second call of is_single_valued(), such that the calls return different values.

This revision was automatically updated to reflect the committed changes.