Page MenuHomePhabricator

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

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

Details

Summary

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.

Tobias

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"

lib/Transform/ForwardOpTree.cpp
409

statements.

410

across

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.