Page MenuHomePhabricator

[WIP] Fixpoint iteration system for IPO attribute deduction

Authored by jdoerfert on Mar 10 2019, 10:18 PM.


NOTE: This is a prototype that needs a lot of cleanup but shows how the overall system could look like! The actual code review will happen on smaller chunks of this code, adding one feature at a time, first without removing the existing code path.

In the end, this commit shows how we should replace the current
"inter-procedural function attribute deduction" with a fixpoint
iteration system. For some problems with the current implementation see
[1]. The new system allows to determine various properties, including
inter-procedural function attributes, through interlaced fixpoint
iterations. All "in-flight" attributes can query the optimistic and
known values of other attributes computed in the same fixpoint
iteration. This allows better interference if there is a mutual
dependence. Dedicated fixpoint propagations determine information
alternating through forward and backward deduction (wrt. the execution
flow) until neither yields new results (or we decide to give up).

This prototype implementation:

  • determines all attributes we did with the existing code
  • adds detection for multiple new attributes
  • shows how local information, e.g. dereferenceability due to a load, can be propagated by the system to callees of the function (if applicable) and users of the loaded pointer alike.
  • distinguishes six different kinds of attribute "positions", e.g., function attributes and return attributes (see the enum ManifestPosition), five of which can be manifested in IR.

To deduce new attributes, at a known position (see the enum
ManifestPosition), one only needs to inherit from the AbstractAttribute
class and implement all methods without a default implementation. All
but the "bool updateImpl(Attributor &A, Direction Dir)" method are often
one liners.

Comment and remarks welcome!


Diff Detail

Event Timeline

jdoerfert created this revision.Mar 10 2019, 10:18 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 10 2019, 10:18 PM
uenoku added a subscriber: uenoku.Mar 25 2019, 7:37 AM
jdoerfert abandoned this revision.Apr 22 2019, 12:53 PM

Cleaned up versions are online now