This is an archive of the discontinued LLVM Phabricator instance.

[llvm-mca] Introduce a pipeline Stage class and FetchStage.
ClosedPublic

Authored by mattd on May 10 2018, 9:56 PM.

Details

Summary
 This is just an idea, really two ideas.  I expect some push-back,
 but I realize that posting a diff is the most comprehensive way to express
 these concepts.

 This patch introduces a Stage class which represents the
 various stages of an instruction pipeline.  As a start, I have created a simple
 FetchStage that is based on existing logic for how MCA produces
 instructions, but now encapsulated in a Stage.  The idea should become more concrete
 once we introduce additional stages.  The idea being, that when a stage completes,
 the next stage in the pipeline will be executed.  Stages are chained together
 as a singly linked list to closely model a real pipeline. For now there is only one stage,
 so the stage-to-stage flow of instructions isn't immediately obvious.

 Eventually, Stage will also handle event notifications, but that functionality
 is not complete, and not destined for this patch.  Ideally, an interested party 
 can register for notifications from a particular stage.  Callbacks will be issued to
 these listeners at various points in the execution of the stage.  
 For now, eventing functionality remains similar to what it has been in mca::Backend. 
 We will be building-up the Stage class as we move on, such as adding debug output.

 This patch also removes the unique_ptr<Instruction> return value from
 InstrBuilder::createInstruction.  An Instruction pointer is still produced,
 but now it's up to the caller to decide how that item should be managed post-allocation
 (e.g., smart pointer).  This allows the Fetch stage to create instructions and
 manage the lifetime of those instructions as it wishes, and not have to be bound to any
 specific managed pointer type.  Other callers of createInstruction might have different 
 requirements, and thus can manage the pointer to fit their needs.  Another idea would be to push the
ownership to the RCU. 

 Currently, the FetchStage will wrap the Instruction
 pointer in a shared_ptr.  This allows us to remove the Instruction container in
 Backend, which was probably going to disappear, or move, at some point anyways.
 Note that I did run these changes through valgrind, to make sure we are not leaking
 memory.  While the shared_ptr comes with some additional overhead it relieves us
 from having to manage a list of generated instructions, and/or make lookup calls
 to remove the instructions. 

 I realize that both the Stage class and the Instruction pointer management
 (mentioned directly above) are separate but related ideas, and probably should
 land as separate patches; I am happy to do that if either idea is decent.
 The main reason these two ideas are together is that
 Stage::execute() can mutate an InstRef. For the fetch stage, the InstRef is populated
 as the primary action of that stage (execute()).  I didn't want to change the Stage interface
 to support the idea of generating an instruction.  Ideally, instructions are to
 be pushed through the pipeline.  I didn't want to draw too much of a
 specialization just for the fetch stage.  Excuse the word-salad.

Diff Detail

Repository
rL LLVM

Event Timeline

mattd created this revision.May 10 2018, 9:56 PM
mattd updated this revision to Diff 146353.May 11 2018, 10:31 AM

Store each stage in the pipeline as a unique_ptr. There should only be a single owner of a stage. The initial stage is owned by the backend, and all subsequent stages are owned by their predecessor stage.

andreadb requested changes to this revision.May 14 2018, 3:29 AM

Hi Matt,

Thanks for the patch! See my comments below.

-Andrea

tools/llvm-mca/Backend.cpp
42 ↗(On Diff #146353)

Remove this assert. By construction, you cannot have a null pointer from the SourceMgr.

tools/llvm-mca/Backend.h
58 ↗(On Diff #146353)

I would just call it FetchStage for now.

86 ↗(On Diff #146353)

I would remove this for now.
It is clear that this is never going to be null.

tools/llvm-mca/FetchStage.cpp
1 ↗(On Diff #146353)

It should be FetchStage.cpp.

tools/llvm-mca/InstrBuilder.cpp
430–433 ↗(On Diff #146353)

It should return a unique_ptr.

tools/llvm-mca/InstrBuilder.h
65 ↗(On Diff #146353)

I don't like the changes to InstrBuilder.h and InstrBuilder.cpp.

I don't think that there is a good reason why createInstruction should return a normal pointer instead of a unique_ptr.

tools/llvm-mca/Instruction.h
39 ↗(On Diff #146353)

I've been thinking about the instruction ownership problem.

My opinion is that there is no real advantage in passing the ownership of an instruction from stage to stage.
It complicates the logic for very little (if no) gain. It forces the instruction to be manipulated as a shared_ptr in the Scheduler.

I'd like to keep the code simple. I prefer a simpler (and more intuitive) approach where instructions are created and destroyed in the same place.

Any particular reason why the FetchStage cannot be the owner of all Instructions? At the end of each cycle, it looks for instructions that have reached the retired stage, and remove them. That approach would be much cleaner, and - more importantly - it would not require using shared_ptr everywhere.

tools/llvm-mca/Stage.h
28 ↗(On Diff #146353)

Create a Stage.cpp, and pin the vtable there.
Move the definition of registerNextStage and addListener to Stage.cpp.

29 ↗(On Diff #146353)

Please remove this field.

31 ↗(On Diff #146353)

A stage should not "own" the next stage. I think the Backend (i.e. our pipeline) should be the owner of all the stages. Please remove this unique_ptr.

36–37 ↗(On Diff #146353)

Make these two to private.

This revision now requires changes to proceed.May 14 2018, 3:29 AM
mattd added a comment.May 14 2018, 9:50 AM

Thanks a ton for your comments. I'll simplify per our offline discussion, and what was grazed upon in your comments above. Thanks.

tools/llvm-mca/InstrBuilder.h
65 ↗(On Diff #146353)

My reason was to allow the caller decide how to manage the pointer. The benefit was that we can treat the pointer as a shared, or unique, else where. But given comments below, I'm convinced we can leave it as is.

tools/llvm-mca/Instruction.h
39 ↗(On Diff #146353)

Those are all valid points. My goal was to remove the Instructions list and any callbacks, such as eraseInstruction, to that list. I was trying to remove the need for any Stage to have to callback-out to another stage or backend. However, after discussing off-line, I am convinced to keep this Stage introduction simple. While Instruction ownership did influence this patch, and I built Stage around that idea, I am convinced that we can just move the ownership to the FetchStage, at least for now.

tools/llvm-mca/Stage.h
31 ↗(On Diff #146353)

The idea was that once a stage finishes with an instruction, it would then push that instruction to the next stage in the pipeline, very reactive. However, for now, we can just manage the stages as a list in Backend.

mattd updated this revision to Diff 146671.May 14 2018, 1:41 PM
mattd marked 11 inline comments as done.
  • Cleaned up the code per items mentioned in the comments.
  • I added a single stage to Backend.h, in the future this will be a list of stages that represent the instruction pipeline. This patch is about introducing the Stage and FetchStage idea.
  • As suggested, the Instruction list is now owned by the Fetch stage, since that stage produces the instructions.
    • I wonder if it would be cleaner to have an InstructionManager class, that manages the list of Instructions?
      • When the Backend instantiates the stages of the pipeline, it would also pass a reference to the InstructionManager instance to the stages.
  • The callback to Backend::eraseInstruction is still there, however, that routine now invokes the Fetch stage to remove the specified Instruction instance. I don't like that indirection, but that would be a different patch. Specifically, once we add eventing to the Stages, then that functionality would be completely removed from the Backend.
    • If we take the InstructionManager idea, then that would eliminate the eraseInstruction definition from Backend and any Stage.

Thanks Matt,

the patch looks much better now. I like how you designed the Stage interface.
See my comments below.

  • The callback to Backend::eraseInstruction is still there, however, that routine now invokes the Fetch stage to remove the specified Instruction instance. I don't like that indirection, but that would be a different patch. Specifically, once we add eventing to the Stages, then that functionality would be completely removed from the Backend.
    • If we take the InstructionManager idea, then that would eliminate the eraseInstruction definition from Backend and any Stage.

There is no reason why you shouldn't be able to get rid of it now.
In FetchStage::postExecute(), you should be able to iterate over the set of instructions, and remove instructions that have reached the retire stage.

tools/llvm-mca/Backend.h
89–93 ↗(On Diff #146671)

I think that you can get rid of this, if you modify the FetchStage::postExecute() method.

tools/llvm-mca/Stage.cpp
27 ↗(On Diff #146671)

You can simply call llvm::llvm_unreachable("...").

mattd updated this revision to Diff 146876.May 15 2018, 10:34 AM
  • Removed eraseInstruction. Since we place ownership of all instructions in FetchStage, we can scan the list at the end of each Fetch cycle (postExecute) and clean up retired instructions at that time (thanks Andrea for that suggestion).
  • Added isRetired predicate to Instruction.h
andreadb accepted this revision.May 15 2018, 10:57 AM

LGTM. Thanks!

This revision is now accepted and ready to land.May 15 2018, 10:57 AM
This revision was automatically updated to reflect the committed changes.