Page MenuHomePhabricator

[Polly][ForwardOpTree] Use less computationally expensive method to compute def-to-target map. NFCI.

Authored by Meinersbur on May 25 2018, 12:20 PM.



When forwarding a LoadInst to another statement, a map that translates their domain is needed. Before this patch, is was computed by appending the def-to-use map to the def-to-target of the operand tree's target. This patch lets the new method getDefToTarget to is. This is computationally less expensive due to:

  • Caching of the result such that it can be used for multiple operands tree to the same target.
  • The map is only computed when there is a LoadInst that needs it.
  • It is only computed for the statement requiring the translator map, instead of having an intermediate result for every edge in the operand tree.

The downside is that this scheme cannot handle forwarding from a previous loop iteration (which would require the entire path from statement to target). Since ForwardOpTree currently does not support forwarding across loop iterations, this was not needed anyway.

This was written in reaction to the compilation timeout in GrTestUtils.cpp by the aosp-O3-polly-before-vectorizer-unprofitable buildbot. This patch may not solve the timeout itself, but would enable other mitigations such as reducing the max-computations limit for ForwardOptree or drastically simplifying the computations needed for the translator map if the schedule is still the original from ScopInfo.

Diff Detail


Event Timeline

Meinersbur created this revision.May 25 2018, 12:20 PM

This is a very good idea. I am out of office, but will review this Sunday night.


Hi Michael,

this looks very good. I am especially interested in further optimizations for cases where the original schedule has not been changed. (What is the case currently in Polly). Just some minor nits:

"to this" -> "do this"

409 ↗(On Diff #148646)


410 ↗(On Diff #148646)


This revision is now accepted and ready to land.May 27 2018, 11:22 PM
This revision was automatically updated to reflect the committed changes.
Meinersbur marked 2 inline comments as done.