Meta issue: SSA for variable

[sklam]

Feature request

Use SSA for variables.

• func_ir.get_definitions() problems
  • problem example:

    def doit(x):
        return x
    
    def bar(pred):
        if pred:
            foo = True
        else:
            foo = False
        # do something with foo
        return doit(foo)

  • because foo has one name in all basic-blocks. Analysis cannot easily tell what local foo definition must be. For instance, if bool(pred)==True, we know that foo == True in the "then" block.
  • Many issues are related to this (what are they?)

Work items:

• add dominance frontier
• add phi-node insertion in interpreter.py

[guilhermeleobas]

Hi, I can work on this

[sklam]

@stuartarchibald, i remember you started looking at this. Can you give us an update?

[guilhermeleobas]

@sklam, can you point me a direction on the source code? I saw that the dominator tree algorithm is implemented on numba/controlflow.py. I can start implementing the dominance frontier algorithm there.

[stuartarchibald]

@sklam IIRC I've got the dominance frontier and dominator tree and was working on the data flow equations for phi node insertion.

[guilhermeleobas]

Hi @stuartarchibald, the code for the dominance frontier is in the master branch? I could only find the code to compute the (post)Dominator Tree.

[stuartarchibald]

@guilhermeleobas its not, I just hacked it together locally in the simplest way (form up dominance tree and mask off each vertex in turn) so I could start working on where to put phi nodes. If you are familiar with these concepts and the algorithms involved please feel free to write an implementation, it would be interesting to compare notes/you may well get this finished ahead of me doing it! Thanks.

[guilhermeleobas]

Cool, I will start working on that as soon as I have some cycles to spare.

[stuartarchibald]

Implemented in #5351, closing.