commit | defe7b1906c8b07e23866b9eeea7730662508bf5 | [log] [tgz] |
---|---|---|

author | Karthika Devi C <quic_kartc@quicinc.com> | Tue Jul 30 22:13:24 2024 +0530 |

committer | Copybara-Service <copybara-worker@google.com> | Tue Jul 30 09:46:02 2024 -0700 |

tree | 50204b084f4894fac05a62158ba88770cc584319 | |

parent | ad14fcbd4423e8ec44cf82f07309b6f1a303852e [diff] |

[Polly] Data flow reduction detection to cover more cases (#84901) The base concept is same as existing reduction algorithm where we get the list of candidate pairs <store,load>. But the existing algorithm works only if there is single binary operation between the load and store. Example sum += a[i]; This algorithm extends to work with more than single binary operation as well. It is implemented using data flow reduction detection on basic block level. We propagate the loads, the number of times the load is used(flows into instruction) and binary operation performed until we reach a store. Example sum += a[i] + b[i]; ``` sum(Ld) a[i](Ld) \ + / tmp b[i](Ld) \ + / sum(St) ``` In the above case the candidate pairs are formed by associating sum with all of its load inputs which are sum, a[i] and b[i]. Then check functions are used to filter a valid reduction pair ie {sum,sum}. --------- Co-authored-by: Michael Kruse <github@meinersbur.de> GitOrigin-RevId: 1e5334bcdae462e47d8516464b2cca1674ea899d

- include/polly/ScopBuilder.h[diff]
- include/polly/ScopInfo.h[diff]
- lib/Analysis/ScopBuilder.cpp[diff]
- lib/Analysis/ScopInfo.cpp[diff]
- test/DependenceInfo/reduction_indirect_access.ll[Added - diff]
- test/ScopInfo/reduction_double.ll[Added - diff]
- test/ScopInfo/reduction_escaping_intermediate_3.ll[Added - diff]
- test/ScopInfo/reduction_if.ll[Added - diff]
- test/ScopInfo/reduction_indirect_access.ll[Added - diff]
- test/ScopInfo/reduction_indirect_access_2.ll[Added - diff]
- test/ScopInfo/reduction_long_reduction_chain.ll[Added - diff]
- test/ScopInfo/reduction_long_reduction_chain_double_use.ll[Added - diff]
- test/ScopInfo/reduction_multiple_different_operators.ll[Added - diff]

13 files changed

tree: 50204b084f4894fac05a62158ba88770cc584319