Introducing a new, advanced Visual C++ code optimizer

Re:Introducing a new, advanced Visual C++ code optimizer by rayiner on Thursday May 05, 2016 @05:06PM (#11639665)

Aren't SSA analyses generally only "kinda flow-sensitive" since values are only renamed where control flow merges, not where it splits? E.g.

  int x = ...
  if(x > 0) {
    use(x)
  else {
    use(x)
  }

In a DFA where you track information about each variable at each program point, you could push the constraint implied by the condition into each branch. If you do a sparse analysis on SSA form, that doesn't come naturally, right?

[ Parent | on HN ]

Re:Introducing a new, advanced Visual C++ code optimizer by nikic on Thursday May 05, 2016 @05:45PM (#11639876)

To handle this case some SSA implementations add a concept of "pi" nodes, which are used to artificially split variables on branches that establish some useful data flow property.

    x1 = ...
    if (x1 > 0) {
        x2 = pi(x1 & RANGE[1..])
        use(x2)
    } else {
        x3 = pi(x1 & RANGE[..0])
        use(x3)
    }
    x4 = phi(x2, x3) // if used

I have placed the pi nodes in the blocks, but semantically they are placed along the control edge.

Ref e.g. e-SSA in the ABCD value range inference algorithm.

[ Parent | on HN ]

Re:Introducing a new, advanced Visual C++ code optimizer by pcwalton on Thursday May 05, 2016 @05:26PM (#11639778)

That's correct; it doesn't come for free.

[ Parent | on HN ]