[Speculation] Automatic Finder for Speculative Units Placement

[asleix]

Description

A new feature for Speculation is added. Finder methods are implemented to allow for automatic placement of the speculative units, without the need of manually specifying al positions in the JSON file.

The pass can now be called with --handshake-speculation="json-path=myjson.json automatic=true" to automatically find the placements. Notice that automatic=true by default, so to manually specify the units, automatic=false is needed.

The feature is implemented in the class PlacementFinder, whose constructor and the method findPlacements are exposed. Many private methods are implemented to find the positions of all units, including saves, commits and save-commits.

New tests are added to support this feature.

As this PR is a bit large, some discussions will be needed.

Control-flow-graph calculations

A helper struct to hold a BB's predecessor arcs is created:

struct BlockPredecessor {
  unsigned srcBB;
  unsigned dstBB;
  std::vector<OpPlacement> arcs;
};

Its purpose is to be able to map a BB with the arcs that lead to its predecessors using a std::map<unsigned, std::vector<BlockPredecessor>>. The function getBlockPredecessors is implemented to achieve this purpose.

If this feature can be useful for CFG.h, it can be refactored in the future.

[asleix]

As per @murphe67 suggestions, I renamed and changed some of SpeculationPlacements methods to work better with edges.

• Added overloaded methods to SpeculationPlacements such that it works both with the two arguments srcOpResult, *dstOp and the struct {srcOpResult, *dstOp}.
• Renamed OpPlacement to CFGEdge in the section where the edges are used. However, I think that in other sections (such as in SpeculationPlacement.cpp) the name OpPlacement is still preferred. To achieve this, using CFGEdge = OpPlacement; is used, which achieves the best of both worlds.
• Improved overall comments when using these edges.

[asleix]

Thanks @lucas-rami for the nice comments! I have addressed all of them.

The major structural change is the removal of OpPlacement and the use of mlir::OpOperand instead. The sets and maps now use OpOperand *, and the behavior is unchanged.

Some of the syntax may have become a bit more verbose. To traverse the IR in a DFS manner, now I use

for (Operation *succOp : currOp->getUsers()) {
    for (OpOperand &dstOpOperand : succOp->getOpOperands()) {
      // Iterate the operands of succOp that are results of currOp
      if (dstOpOperand.get().getDefiningOp() == currOp) {
         // do stuff with dstOpOperand
    }
  }
}

I wanted to share a concern regarding memory safety. When the IR is modified, e. g., once the speculator is placed, what happens with the OpOperand * that pointed to the operand edge where we now have the speculator? Is that part of memory still pointing to the same OpOperand?

But I did some tests and didn't get any segmentation faults, so it is likely to be memory safe.

Finally, regarding moving the CFG code to CFG.h/cpp, my suggestion is to create a PR moving the code after merging this PR. :)

[lucas-rami]

Thanks @asleix for addressing everything quickly :)

(tip: For minor PR comments, you can just do "Resolve conversation" instead of reacting with a +1 to my message. I trust that in those cases you have addressed the requested change and I will not check. Only leave the conversation open if you want me to argue/discuss the change or simply replied to my comment. This allows me to go a bit faster over your updates ;))

Some of the syntax may have become a bit more verbose. To traverse the IR in a DFS manner, now I use...

You can be shorter and more efficient with

for (OpResult res : currOp->getResults()) {
  for (OpOperand &dstOpOperand : res.getUses()) {
    // do stuff with dstOpOperand
  }
}

I wanted to share a concern regarding memory safety. When the IR is modified, e. g., once the speculator is placed, what happens with the OpOperand * that pointed to the operand edge where we now have the speculator? Is that part of memory still pointing to the same OpOperand?

That's a good question, and a scenario where I'm not completely sure of what happens under the hood. I think it is safe to assume that, as long as the operands of an operation do not change, then they will maintain their location in memory (i.e., your OpOperand*'s will remain valid). However the story is probably different as soon as you modify them. I would not assume that pointers remain valid after modifications to the operands of an operation i.e., if p of type OpOperand* holds a pointer to operand i of some operation op, then after you replace the i'th operand of op with the result of a new operation, p should be assumed to be garbage and never used again. As long as you don't modify any given operand more than once this means you should probably be fine (unless you are for some reason re-using the pointer to some previously replaced operand at any point).

Finally, regarding moving the CFG code to CFG.h/cpp, my suggestion is to create a PR moving the code after merging this PR. :)

Perfect :)

I let you address the DFS traversal thing and then we can merge!

[asleix]

Thanks @lucas-rami! I have improved the syntax for the DFS traversal with your suggestion. And thanks a lot for the thoughts and insights regarding the OpOperand pointers. Also, in the future, I'll mark as resolved directly for minor comments.

I have merged with main and run the tests to verify correct behavior. I'll soon open PRs, one for moving code to CFG.h and the other for some additions to DOTPrinter.h to support speculation.