3 ms·

>I'm certainly not convinced by the argument that optimal egraph is equivalent to the minimum set cover problem and thus in NP. I can believe that egraph extrac

>I'm certainly not convinced by the argument that optimal egraph is equivalent to the minimum set cover problem and thus in NP. I can believe that egraph extraction can be modelled as minimum set cover Are you like actually misunderstanding or are you trying to say something else - egraph is in np because it's equivalent to ilp and it's complete because you can reduce set cover to it not the other way around (the reduction always goes to the problem not from the problem in a completeness proof). >Despite that, register allocation on a chordal graph can be done in linear time, and SSA form gives you a chordal graph. This isn't saying much since SSA construction (phi elimination) isn't linear.

JonChesterfield 3y ago
I'm least one of misunderstanding and disagreeing. Start with a set cover problem, NP. OK. Translate it mechanically to an e-graph in polynomial time, sure, that instance of the e-graph is still unsolvable in polynomial time. It doesn't follow that all instances of e-graphs are unsolvable in polynomial time, only that some aren't. Your e-graph is really heavily constrained by the ISA and optionally by the ABI. It's also constrained by the code it was created from which will tend to have its own constraints. Constraints can lead to faster solutions. SSA construction is putting phi's in, if you're using them instead of block arguments. Destruction is taking phis out. Whether that's linear time or polynomial or non-polynomial depends on how optimal a job of eliding copies you choose to do.
- mathisfun123 3y ago
  It's like your willfully misconstruing to make what points here? >It doesn't follow that all instances of e-graphs are unsolvable in polynomial time, only that some aren't. Yes and hardness results are about proving lower bounds on worst case complexity not best case or sometimes case or whatever-you-chose-as-meaningful case.
  - JonChesterfield 3y ago
    Let's not rule out that I may just be wrong. However e-graphs are not really a general purpose thing, they're a bespoke creation for partially solving phase ordering in compilers, intermixed with the DAG tiling problem from instruction selection. Specifically, e-graphs are used with respect to an ISA from which the cost model is derived. My intuition is that this constrains the structure sufficiently that polynomial solutions can be found. Probably involving a partial order calculated ahead of time. For me, whether the result in the opening post is applicable to uses of e-graphs in compilers has a strong influence over whether I need to worry about it or not. I'm on the fence about e-graphs as a model. If rolling one into production means I'll occasionally hit exponential increases in running time as heuristics fall over, that's an argument against. If those cliffs are unreachable for a given ISA, they don't matter.
    - mathisfun123 3y ago
      >if those cliffs are unreachable for a given ISA, they don't matter By rice's theorem, for any ISA that has a jmp or mov, there is no way to know/prove/predict this. So you're still not saying anything useful.
- nextaccountic 3y ago
  Plenty of NP-complete problems have easy instances. Indeed for a lot of problems there's an assumption that most instances that naturally arise are easier and well solved by heuristics but there are some pathological instances that aren't but don't appear in practice Also: if you are okay with heuristics that aren't guaranteed to output the optimal answer the whole point is moot

JonChesterfield 3y ago

I'm least one of misunderstanding and disagreeing. Start with a set cover problem, NP. OK. Translate it mechanically to an e-graph in polynomial time, sure, that instance of the e-graph is still unsolvable in polynomial time. It doesn't follow that all instances of e-graphs are unsolvable in polynomial time, only that some aren't. Your e-graph is really heavily constrained by the ISA and optionally by the ABI. It's also constrained by the code it was created from which will tend to have its own constraints. Constraints can lead to faster solutions. SSA construction is putting phi's in, if you're using them instead of block arguments. Destruction is taking phis out. Whether that's linear time or polynomial or non-polynomial depends on how optimal a job of eliding copies you choose to do.

mathisfun123 3y ago
It's like your willfully misconstruing to make what points here? >It doesn't follow that all instances of e-graphs are unsolvable in polynomial time, only that some aren't. Yes and hardness results are about proving lower bounds on worst case complexity not best case or sometimes case or whatever-you-chose-as-meaningful case.
- JonChesterfield 3y ago
  Let's not rule out that I may just be wrong. However e-graphs are not really a general purpose thing, they're a bespoke creation for partially solving phase ordering in compilers, intermixed with the DAG tiling problem from instruction selection. Specifically, e-graphs are used with respect to an ISA from which the cost model is derived. My intuition is that this constrains the structure sufficiently that polynomial solutions can be found. Probably involving a partial order calculated ahead of time. For me, whether the result in the opening post is applicable to uses of e-graphs in compilers has a strong influence over whether I need to worry about it or not. I'm on the fence about e-graphs as a model. If rolling one into production means I'll occasionally hit exponential increases in running time as heuristics fall over, that's an argument against. If those cliffs are unreachable for a given ISA, they don't matter.
  - mathisfun123 3y ago
    >if those cliffs are unreachable for a given ISA, they don't matter By rice's theorem, for any ISA that has a jmp or mov, there is no way to know/prove/predict this. So you're still not saying anything useful.
nextaccountic 3y ago
Plenty of NP-complete problems have easy instances. Indeed for a lot of problems there's an assumption that most instances that naturally arise are easier and well solved by heuristics but there are some pathological instances that aren't but don't appear in practice Also: if you are okay with heuristics that aren't guaranteed to output the optimal answer the whole point is moot