Page MenuHomePhabricator

Add a PhiValuesAnalysis pass to calculate the underlying values of phis
ClosedPublic

Authored by john.brawn on Jun 7 2018, 10:53 AM.

Details

Summary

This pass is being added in order to make the information available to BasicAA, which can't do caching of this information itself, but possibly this information may be useful for other passes.

Incorporates code based on Daniel Berlin's implementation of Tarjan's algorithm.

Diff Detail

Repository
rL LLVM

Event Timeline

john.brawn created this revision.Jun 7 2018, 10:53 AM
john.brawn planned changes to this revision.Jun 8 2018, 10:03 AM

This analysis (when enabled by D44564) is causing a bunch of assertion failures/segfaults in spec2000, so it looks like there's still more work for me to do here before this is ready.

john.brawn edited the summary of this revision. (Show Details)

After a lot of time spent trying to get it to work, I've decided that there's no way to get the analysis to handle all possible ways that the calculated values can be invalidated without ending up with something slower than if you jsut recalculate everything from scratch every time. The problems are:

  • Using ValueHandles doesn't work because plenty of passes modify a phi's operands directly and ValueHandle doesn't notice that.
  • Using pointers to the Use list of the phi can cope with that, but everything goes wrong if an operand is added to the phi as the use list gets reallocated.
  • Just caching the set of phis that a phi depends on and examining all of those to figure out if any have had operands changed works, but it's slower than just traversing the phi from scratch.

So I've ended up with going back to the original idea I had of having an interface to the analysis that lets you explicitly invalidate things, and using it from MemoryDependenceAnalysis where we already get notified about things being invalidated.

sebpop requested changes to this revision.Jun 22 2018, 1:10 PM
sebpop added inline comments.
lib/Analysis/PhiValues.cpp
45 ↗(On Diff #150360)

Why not using Danny's implementation of Tarjan's algorithm?
processPhi() would be findSCC()

https://reviews.llvm.org/D28934 has a version of the SCC finder you can
borrow if you want (TarjanSCC class)

// Tarjan's algorithm with Nuutila's improvements
// Wish we could use SCCIterator, but graph traits makes it *very* hard to
// create induced subgraphs because it
// 1. only works on pointers, so i can't just create an intermediate struct
// 2. the functions are static, so i can't just override them in a subclass of
// graphtraits, or otherwise store state in the struct.

struct TarjanSCC {
  unsigned int DFSNum = 1;
  SmallPtrSet<Value *, 8> InComponent;
  DenseMap<Value *, unsigned int> Root;
  SmallPtrSet<Value *, 8> PHISet;
  SmallVector<Value *, 8> Stack;
  // Store the components as vector of ptr sets, because we need the topo order
  // of SCC's, but not individual member order
  SmallVector<SmallPtrSet<PHINode *, 8>, 8> Components;
  TarjanSCC(const SmallVectorImpl<PHINode *> &Phis)
      : PHISet(Phis.begin(), Phis.end()) {
    for (auto Phi : Phis)
      if (Root.lookup(Phi) == 0)
        FindSCC(Phi);
  }
  void FindSCC(PHINode *Phi) {
    Root[Phi] = ++DFSNum;
    // Store the DFS Number we had before it possibly gets incremented.
    unsigned int OurDFS = DFSNum;
    InComponent.erase(Phi);
    for (auto &PhiOp : Phi->operands()) {
      // Only inducing the subgraph of phis we got passed
      if (!PHISet.count(PhiOp))
        continue;
      if (Root.lookup(PhiOp) == 0)
        FindSCC(cast<PHINode>(PhiOp));
      if (!InComponent.count(PhiOp))
        Root[Phi] = std::min(Root.lookup(Phi), Root.lookup(PhiOp));
    }
    // See if we really were the root, by seeing if we still have our DFSNumber,
    // or something lower
    if (Root.lookup(Phi) == OurDFS) {
      Components.resize(Components.size() + 1);
      auto &Component = Components.back();
      Component.insert(Phi);
      DEBUG(dbgs() << "Component root is " << *Phi << "\n");
      InComponent.insert(Phi);
      while (!Stack.empty() && Root.lookup(Stack.back()) >= OurDFS) {
        DEBUG(dbgs() << "Component member is " << *Stack.back() << "\n");
        Component.insert(cast<PHINode>(Stack.back()));
        InComponent.insert(Stack.back());
        Stack.pop_back();
      }
    } else {
      // Part of a component, push to stack
      Stack.push_back(Phi);
    }
  }
};
71 ↗(On Diff #150360)

This code is nested at loop depth 4.

75 ↗(On Diff #150360)

Same.

This revision now requires changes to proceed.Jun 22 2018, 1:10 PM
john.brawn added inline comments.Jun 25 2018, 7:26 AM
lib/Analysis/PhiValues.cpp
45 ↗(On Diff #150360)

Why not using Danny's implementation of Tarjan's algorithm?
processPhi() would be findSCC()

The two are doing two different things:

  • findSCC partitions the phi graph into a set of subgraphs where each subgraph is an SCC (each node has an edge to every other node)
  • processPhi (implicitly) partitions the phi graph into a set of subgraphs where the underlying values reachable in a subgraph is the same

Taking the long_phi_chain.ll test as an example, findSCC gives us the components:

  1. { phi1, phi2 }
  2. { phi3, phi4, phi5 }
  3. { phi6, phi7 }
  4. { phi8, phi9, phi10 }
  5. { phi11, phi12, phi13 }
  6. { phi14 }
  7. { phi15 }

which then form an SCC graph 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1.

processPhi however needs to find that all of these phis have the same set of underlying values, and I don't see a way to do this other than looking through the SCC graph in a way very similar to how processPhi looks through the phi graph (though the SCC graph will be simpler than the phi graph).

It may be possible though to do something similar to findSCC in order to explicitly construct a 'set of phis that have the same underlying values' partitioning, i.e. numbering nodes and building up stack then stacked nodes with the same number are in the same set, but I don't know if it will be simpler/faster than what I have here. I'll give it a try though.

john.brawn added inline comments.Jun 25 2018, 10:33 AM
lib/Analysis/PhiValues.cpp
45 ↗(On Diff #150360)

It may be possible though to do something similar to findSCC in order to explicitly construct a 'set of phis that have the same underlying values' partitioning, i.e. numbering nodes and building up stack then stacked nodes with the same number are in the same set, but I don't know if it will be simpler/faster than what I have here. I'll give it a try though.

Because Tarjan's algorithm completes SSCs in bottom-up order, and the SCC graph is guaranteed to have no cycles, this turns out to be fairly straighforward. I'll rework this to do that.

john.brawn edited the summary of this revision. (Show Details)
john.brawn set the repository for this revision to rL LLVM.

Use Tarjan's algorithm in processPhi.

sebpop accepted this revision.Jun 28 2018, 5:17 AM

Looks good to me. Thanks.

This revision is now accepted and ready to land.Jun 28 2018, 5:17 AM
This revision was automatically updated to reflect the committed changes.