PRE Improvements
- The tree based PRE implementation currently has a few limitations and maintenance issue. There are a very small number of algorithm unoptimalities causing things like PR 27755, and compile time issues like 28071. Besides these, it also lacks the ability to eliminate a certain class of redundancies. This work fixes all of these problems.
Personnel
- Daniel Berlin
Delivery Date
- These improvements are ready now.
Benefits
- PRE will generate better code, faster, and use less memory.
Dependencies
- None
Modifications Required
- The two set representations in PRE are changed so that there are only bitmap sets. The algorithmic issue is fixed, and the ability to detect and remove partial-partial redundancies is added. The algorithmic issue sometimes causes 50% performance slowdown in PRE on some cases (a small number), and thus will be limited to O3, along with the parital-partial redundancy elimination. This issue is simply one of optimality, and it not that commonly occurring. The set changes result in a massive memory reduction, and somewhere between a 10% and 100% speedup in PRE, depending on the case. On 28071, it reduces PRE time from 300 seconds to 4.