Skip to content

util: Add a generic worklist implementation

Alyssa Rosenzweig requested to merge alyssa/mesa:u_worklist_2 into main

Models a double-ended queue of elements from an a list. Based on NIR's worklist data structure. This is useful in most backend compilers for data flow analysis.

Using this data structure has several advantages for backends:

  • Simplicity, avoids open-coding a worklist data structure.
  • Performance, the data structure is lighter weight than e.g sets
  • Correctness, e.g. sets are nondeterministic and can cause random bugs.

Using a worklist approach at all is good for performance of liveness analysis to avoid performing excess walks over the IR.

Edited by Alyssa Rosenzweig

Merge request reports