summaryrefslogtreecommitdiffstats
path: root/llvm/tools/llvm-mca/Scheduler.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [llvm-mca] Introduce the llvm-mca library and organize the directory ↵Matt Davis2018-08-271-244/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | accordingly. NFC. Summary: This patch introduces llvm-mca as a library. The driver (llvm-mca.cpp), views, and stats, are not part of the library. Those are separate components that are not required for the functioning of llvm-mca. The directory has been organized as follows: All library source files now reside in: - `lib/HardwareUnits/` - All subclasses of HardwareUnit (these represent the simulated hardware components of a backend). (LSUnit does not inherit from HardwareUnit, but Scheduler does which uses LSUnit). - `lib/Stages/` - All subclasses of the pipeline stages. - `lib/` - This is the root of the library and contains library code that does not fit into the Stages or HardwareUnit subdirs. All library header files now reside in the `include` directory and mimic the same layout as the `lib` directory mentioned above. In the (near) future we would like to move the library (include and lib) contents from tools and into the core of llvm somewhere. That change would allow various analysis and optimization passes to make use of MCA functionality for things like cost modeling. I left all of the non-library code just where it has always been, in the root of the llvm-mca directory. The include directives for the non-library source file have been updated to refer to the llvm-mca library headers. I updated the llvm-mca/CMakeLists.txt file to include the library headers, but I made the non-library code explicitly reference the library's 'include' directory. Once we eventually (hopefully) migrate the MCA library components into llvm the include directives used by the non-library source files will be updated to point to the proper location in llvm. Reviewers: andreadb, courbet, RKSimon Reviewed By: andreadb Subscribers: mgorny, javed.absar, tschuett, gbedwell, llvm-commits Differential Revision: https://reviews.llvm.org/D50929 llvm-svn: 340755
* [llvm-mca] Move ResourceManager from Scheduler into its own file. NFC.Matt Davis2018-08-241-284/+0
| | | | | | This time I should be preserving history of the ResourceManager changes. llvm-svn: 340668
* [llvm-mca] Revert r340659. NFC.Matt Davis2018-08-241-0/+284
| | | | | | | | Choosing to revert the change and do it again, hopefully preserving the history of the changes by using svn copy instead of simply creating a new file from the contents within Scheduler. llvm-svn: 340661
* [llvm-mca] Move the ResourceManger from the Scheduler into its own file. NFC.Matt Davis2018-08-241-284/+0
| | | | llvm-svn: 340659
* [llvm-mca] Fix parameter name. NFC.Walter Lee2018-08-231-2/+2
| | | | llvm-svn: 340570
* [llvm-mca] Set the Selection strategy to Default if nullptr is passed.Matt Davis2018-08-231-1/+6
| | | | | | * Set (not reset) the strategy in Scheduler::setCustomStrategyImpl() llvm-svn: 340566
* [llvm-mca] Fix wrong call to setCustomStrategy().Andrea Di Biagio2018-08-231-0/+1
| | | | | | | | | Thanks to @waltl for reporting this issue. I have also added an assert to check for invalid null strategy objects, and I have reworded a couple of code comments in Scheduler.h llvm-svn: 340545
* [llvm-mca] Allow the definition of custom strategies for selecting processor ↵Andrea Di Biagio2018-08-231-45/+73
| | | | | | | | | | | | | | | | | | | | | | | | | resource units. With this patch, users can now customize the pipeline selection strategy for scheduler resources. The resource selection strategy can be defined at processor resource granularity. This enables the definition of different strategies for different hardware schedulers. To override the strategy associated with a processor resource, users can call method ResourceManager::setCustomStrategy(), and pass a 'ResourceStrategy' object in input. Class ResourceStrategy is an abstract class which declares virtual method `ResourceStrategy::select()`. Method select() is meant to implement the actual strategy; it is responsible for picking the next best resource from a set of available pipeline resources. Custom strategy must simply override that method. By default, processor resources are associated with instances of 'DefaultResourceStrategy'. A 'DefaultResourceStrategy' internally implements a simple round-robin selector. For more details, please refer to the code comments in Scheduler.h. llvm-svn: 340536
* [llvm-mca] Improved code comments and moved some method definitions from ↵Andrea Di Biagio2018-08-221-2/+29
| | | | | | Scheduler.h to Scheduler.cpp. NFC llvm-svn: 340395
* [llvm-mca] Add the ability to customize the instruction selection strategy ↵Andrea Di Biagio2018-08-211-24/+11
| | | | | | | | | | | | | | | | | | | | | | in the Scheduler. The constructor of Scheduler now accepts a SchedulerStrategy object, which is used internally by method Scheduler::select() to drive the instruction selection process. The goal of this patch is to enable the definition of custom selection strategies while reusing the same algorithms implemented by class Scheduler. The motivation is that, on some targets, the default strategy may not well approximate the selection logic in the hardware schedulers. This patch also adds the ability to pass a ResourceManager object to the constructor of Scheduler. This gives a bit more flexibility to the design, and potentially it allows to expose processor resources to SchedulerStrategy objects. Differential Revision: https://reviews.llvm.org/D51051 llvm-svn: 340314
* [llvm-mca] Add method cycleEvent() to class Scheduler. NFCIAndrea Di Biagio2018-08-211-14/+27
| | | | | | | | | | | | | | | | | | | | The goal of this patch is to simplify the Scheduler's interface in preparation for D50929. Some methods in the Scheduler's interface should not be exposed to external users, since their presence makes it hard to both understand, and extend the Scheduler's interface. This patch removes the following two methods from the public Scheduler's API: - reclaimSimulatedResources() - updatePendingQueue() Their logic has been migrated to a new method named 'cycleEvent()'. Methods 'updateIssuedSet()' and 'promoteToReadySet()' still exist. However, they are now private members of class Scheduler. This simplifies the interaction with the Scheduler from the ExecuteStage. llvm-svn: 340273
* [llvm-mca] Make the LSUnit a HardwareUnit, and allow derived classes to ↵Andrea Di Biagio2018-08-201-36/+57
| | | | | | | | | | | | | implement a different memory consistency model. The LSUnit is now a HardwareUnit, and it is owned by the mca::Context. Derived classes can now implement a different consistency model by overriding method `LSUnit::isReady()`. This patch also slightly refactors the Scheduler interface in the attempt to simplifying the interaction between ExecuteStage and the underlying Scheduler. llvm-svn: 340176
* [llvm-mca] Reformat a few lines (fix spacing). NFC.Matt Davis2018-08-171-3/+3
| | | | llvm-svn: 340065
* [llvm-mca] Removed references to HWStallEvent in Scheduler.h. NFCIAndrea Di Biagio2018-08-171-16/+17
| | | | | | | | | | class Scheduler should not know anything of hardware event listeners and hardware stall events (HWStallEvent). HWStallEvent objects should only be constructed by pipeline stages to notify listeners of hardware events. No functional change intended. llvm-svn: 340036
* [llvm-mca] Fix PR38575: Avoid an invalid implicit truncation of a processor ↵Andrea Di Biagio2018-08-151-1/+1
| | | | | | | | | | | | | | | | | resource mask (an uint64_t value) to unsigned. This patch fixes a regression introduced at revision 338702. A processor resource mask was incorrectly implicitly truncated to an unsigned quantity. Later on, the truncated mask was used to initialize an element of a vector of processor resource descriptors. On targets with more than 32 processor resources, some elements of the vector are left uninitialized. As a consequence, this bug might have eventually caused a crash due to null dereference in the Scheduler. This patch fixes PR38575, and adds a test for it. llvm-svn: 339768
* [llvm-mca] Speed up the computation of the wait/ready/issued sets in the ↵Andrea Di Biagio2018-08-031-62/+77
| | | | | | | | | | | | | | Scheduler. This patch is a follow-up to r338702. We don't need to use a map to model the wait/ready/issued sets. It is much more efficient to use a vector instead. This patch gives us an average 7.5% speedup (on top of the ~12% speedup obtained after r338702). llvm-svn: 338883
* [llvm-mca] Use a vector to store ResourceState objects in the ResourceManager.Andrea Di Biagio2018-08-021-33/+58
| | | | | | | | | | | | | | | We don't need to use a map to store ResourceState objects. The number of processor resources is known statically from the scheduling model. We can therefore use a vector, and reserve a slot for each processor resource that we want to simulate. Every time the ResourceManager queries the ResourceState vector, the index to the vector of ResourceState objects can be easily computed from the processor resource mask. This drastically reduces the time complexity of method ResourceManager::use() and method ResourceManager::release(). This patch gives an average speedup of 12%. llvm-svn: 338702
* [llvm-mca] Correctly update the rank in `Scheduler::select()`.Andrea Di Biagio2018-08-011-1/+3
| | | | | | Found by inspection. llvm-svn: 338579
* [llvm-mca] Improve a few debug prints. NFCAndrea Di Biagio2018-07-131-3/+3
| | | | llvm-svn: 337003
* [llvm-mca] improve the instruction issue logic implemented by the Scheduler.Andrea Di Biagio2018-07-061-7/+22
| | | | | | | | | | | | | | | | | | | | | | | | | | This patch modifies the Scheduler heuristic used to select the next instruction to issue to the pipelines. The motivating example is test X86/BtVer2/add-sequence.s, for which llvm-mca wrongly reported an estimated IPC of 1.50. According to perf, the actual IPC for that test should have been ~2.00. It turns out that an IPC of 2.00 for test add-sequence.s cannot possibly be predicted by a Scheduler that only prioritizes instructions based on their "age". A similar issue also affected test X86/BtVer2/dependent-pmuld-paddd.s, for which llvm-mca wrongly estimated an IPC of 0.84 instead of an IPC of 1.00. Instructions in the ReadyQueue are now ranked based on two factors: - The "age" of an instruction. - The number of unique users of writes associated with an instruction. The new logic still prioritizes older instructions over younger instructions to minimize the pressure on the reorder buffer. However, the number of users of an instruction now also affects the overall rank. This potentially increases the ability of the Scheduler to extract instruction level parallelism. This patch fixes the problem with the wrong IPC reported for test add-sequence.s and test dependent-pmuld-paddd.s. llvm-svn: 336420
* [llvm-mca] Avoid calling method update() on instructions that are already in ↵Andrea Di Biagio2018-06-271-1/+2
| | | | | | | | | | the IS_READY state. NFCI When promoting instructions from the wait queue to the ready queue, we should check if an instruction has already reached the IS_READY state before calling method update(). llvm-svn: 335722
* [llvm-mca] Removed wrong NDEBUG guards introduced by my last commit.Andrea Di Biagio2018-06-261-2/+0
| | | | | | This partially reverts r335589. llvm-svn: 335592
* [llvm-mca] Remove unused header files and correctly guard some include ↵Andrea Di Biagio2018-06-261-2/+5
| | | | | | headers under NDEBUG. NFC llvm-svn: 335589
* [llvm-mca] Rename Backend to Pipeline. NFC.Matt Davis2018-06-251-1/+1
| | | | | | | | | | | | | | | | | | Summary: This change renames the Backend and BackendPrinter to Pipeline and PipelinePrinter respectively. Variables and comments have also been updated to reflect this change. The reason for this rename, is to be slightly more correct about what MCA is modeling. MCA models a Pipeline, which implies some logical sequence of stages. Reviewers: andreadb, courbet, RKSimon Reviewed By: andreadb, courbet Subscribers: mgorny, javed.absar, tschuett, gbedwell, llvm-commits Differential Revision: https://reviews.llvm.org/D48496 llvm-svn: 335496
* [llvm-mca] Introduce the ExecuteStage (was originally the Scheduler class).Matt Davis2018-06-141-150/+33
| | | | | | | | | | | | | | Summary: This patch transforms the Scheduler class into the ExecuteStage. Most of the logic remains. Reviewers: andreadb, RKSimon, courbet Reviewed By: andreadb Subscribers: mgorny, javed.absar, tschuett, gbedwell, llvm-commits Differential Revision: https://reviews.llvm.org/D47246 llvm-svn: 334679
* [llvm-mca] Fixed a problem caused by an invalid use of a processor resource ↵Andrea Di Biagio2018-05-311-9/+7
| | | | | | | | | | | | | mask in the Scheduler. The lambda functions used by method ResourceManager::mustIssueImmediately() was incorrectly truncating masks of buffered processor resources to 32-bit quantities. The invalid mask values were then used to access a map of processor resource descriptors. Fixes PR37643. llvm-svn: 333692
* [llvm-mca] Add the RetireStage. Matt Davis2018-05-251-1/+1
| | | | | | | | | | | | | | | | | Summary: This class maintains the same logic as the original RetireControlUnit. This is just an intermediate patch to make the RCU a Stage. Future patches will remove the dependency on the DispatchStage, and then more properly populate the pre/execute/post Stage interface. Reviewers: andreadb, RKSimon, courbet Reviewed By: andreadb, courbet Subscribers: javed.absar, mgorny, tschuett, gbedwell, llvm-commits Differential Revision: https://reviews.llvm.org/D47244 llvm-svn: 333292
* [llvm-mca] Make Dispatch a subclass of Stage.Matt Davis2018-05-171-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: The logic of dispatch remains the same, but now DispatchUnit is a Stage (DispatchStage). This change has the benefit of simplifying the backend runCycle() code. The same logic applies, but it belongs to different components now. This is just a start, eventually we will need to remove the call to the DispatchStage in Scheduler.cpp, but that will be a separate patch. This change is mostly a renaming and moving of existing logic. This change also encouraged me to remove the Subtarget (STI) member from the Backend class. That member was used to initialize the other members of Backend and to eventually call DispatchUnit::dispatch(). Now that we have Stages, we can eliminate this by instantiating the DispatchStage with everything it needs at the time of construction (e.g., Subtarget). That change allows us to call DispatchStage::execute(IR) as we expect to call execute() for all other stages. Once we add the Stage list (D46907) we can more cleanly call preExecute() on all of the stages, DispatchStage, will probably wrap cycleEvent() in that case. Made some formatting and minor cleanups to README.txt. Some of the text was re-flowed to stay within 80 cols. Reviewers: andreadb, courbet, RKSimon Reviewed By: andreadb, courbet Subscribers: mgorny, javed.absar, tschuett, gbedwell, llvm-commits Differential Revision: https://reviews.llvm.org/D46983 llvm-svn: 332652
* [llvm-mca] Improved support for dependency-breaking instructions.Andrea Di Biagio2018-05-141-2/+1
| | | | | | | | | The tool assumes that a zero-latency instruction that doesn't consume hardware resources is an optimizable dependency-breaking instruction. That means, it doesn't have to wait on register input operands, and it doesn't consume any physical register. The PRF knows how to optimize it at register renaming stage. llvm-svn: 332249
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-8/+11
| | | | | | | | | | | | | | | | The DEBUG() macro is very generic so it might clash with other projects. The renaming was done as follows: - git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g' - git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM - Manual change to APInt - Manually chage DOCS as regex doesn't match it. In the transition period the DEBUG() macro is still present and aliased to the LLVM_DEBUG() one. Differential Revision: https://reviews.llvm.org/D43624 llvm-svn: 332240
* [llvm-mca] Avoid exposing index values in the MCA interfaces.Matt Davis2018-05-071-66/+66
| | | | | | | | | | | | | | | | | | | | | | | Summary: This patch eliminates many places where we originally needed to pass index values to represent an instruction. The index is still used as a key, in various parts of MCA. I'm not comfortable eliminating the index just yet. By burying the index in the instruction, we can avoid exposing that value in many places. Eventually, we should consider removing the Instructions list in the Backend all together, it's only used to hold and reclaim the memory for the allocated Instruction instances. Instead we could pass around a smart pointer. But that's a separate discussion/patch. Reviewers: andreadb, courbet, RKSimon Reviewed By: andreadb Subscribers: javed.absar, tschuett, gbedwell, llvm-commits Differential Revision: https://reviews.llvm.org/D46367 llvm-svn: 331660
* [llvm-mca] Correctly handle zero-latency stores that consume pipeline resources.Andrea Di Biagio2018-04-301-1/+2
| | | | | | | | | | | | | | | | This fixes PR37293. We can have scheduling classes with no write latency entries, that still consume processor resources. We don't want to treat those instructions as zero-latency instructions; they still have to be issued to the underlying pipelines, so they still consume resource cycles. This is likely to be a regression which I have accidentally introduced at revision 330807. Now, if an instruction has a non-empty set of write processor resources, we conservatively treat it as a normal (i.e. non zero-latency) instruction. llvm-svn: 331193
* [MCA] [NFC] Remove unused Index formal from ResourceManager::issueInstructionMatt Davis2018-04-261-2/+2
| | | | | | | | | | | | | | Summary: The instruction index was never referenced in the body. Just a minor cleanup. Reviewers: andreadb Reviewed By: andreadb Subscribers: javed.absar, gbedwell, llvm-commits Differential Revision: https://reviews.llvm.org/D46142 llvm-svn: 331001
* [llvm-mca] Remove method Instruction::isZeroLatency(). NFCIAndrea Di Biagio2018-04-251-1/+1
| | | | llvm-svn: 330807
* [llvm-mca] Refactor the Scheduler interface in preparation for PR36663.Andrea Di Biagio2018-04-241-72/+83
| | | | | | | | | | | | | Zero latency instructions are now scheduled the same way as other instructions. Before this patch, there was a specialzed code path for those instructions. All scheduler events are now generated from method `scheduleInstruction()` and from method `cycleEvent()`. This will make easier to implement a "execution stage", and let that stage publish all the scheduler events. No functional change intended. llvm-svn: 330723
* [llvm-mca] Ensure that instructions with a schedule read-advance are always ↵Andrea Di Biagio2018-04-131-50/+41
| | | | | | | | | | | | | | issued in the right order. Normally, the Scheduler prioritizes older instructions over younger instructions during the instruction issue stage. In one particular case where a dependent instruction had a schedule read-advance associated to one of the input operands, this rule was not correctly applied. This patch fixes the issue and adds a test to verify that we don't regress that particular case. llvm-svn: 330032
* [llvm-mca] Removed unused argument from cycleEvent. NFCAndrea Di Biagio2018-04-121-1/+1
| | | | llvm-svn: 329895
* [llvm-mca] Let the Scheduler notify dispatch stall events caused by the lack ↵Andrea Di Biagio2018-04-111-16/+18
| | | | | | | | | | | | | | | | | | | of scheduling resources. This patch moves part of the logic that notifies dispatch stall events from the DispatchUnit to the Scheduler. The main goal of this patch is to remove (yet another) dependency between the DispatchUnit and the Scheduler. Before this patch, the DispatchUnit had to know about `Scheduler::Event` and how to classify stalls due to the lack of scheduling resources. This patch removes that knowledge and simplifies the logic in DispatchUnit::checkScheduler. This is another change done in preparation for the work to fix PR36663. No functional change intended. llvm-svn: 329835
* [llvm-mca] Correctly set the ReadAdvance information for register use operands.Andrea Di Biagio2018-03-291-22/+52
| | | | | | | | | | | | The tool was passing the wrong operand index to method MCSubtargetInfo::getReadAdvanceCycles(). That method requires a "UseIdx", and not the operand index. This was found when testing X86 code where instructions had a memory folded operand. This patch fixes the issue and adds test read-advance-1.s to ensure that the ReadAfterLd (a ReadAdvance of 3cy) information is correctly used. llvm-svn: 328790
* [llvm-mca] Make the resource cost a double.Andrea Di Biagio2018-03-231-5/+6
| | | | | | | | This is done in preparation for the fix for PR36874. The number of cycles consumed for each pipe is now a double quantity. This allows reuse of the resource pressure view to print out instruction tables. llvm-svn: 328335
* [llvm-mca] Minor refactoring. NFCIAndrea Di Biagio2018-03-221-10/+3
| | | | | | Also, removed a couple of unused methods from class Instruction. llvm-svn: 328198
* [llvm-mca] Simplify (and better standardize) the Instruction interface.Andrea Di Biagio2018-03-221-4/+3
| | | | llvm-svn: 328190
* [llvm-mca] Simplify code. NFCAndrea Di Biagio2018-03-221-5/+7
| | | | llvm-svn: 328187
* [llvm-mca] Remove const from a bunch of ArrayRef. NFCAndrea Di Biagio2018-03-201-4/+4
| | | | llvm-svn: 328018
* [llvm-mca] Move the logic that computes the scheduler's queue usage to the ↵Andrea Di Biagio2018-03-201-15/+39
| | | | | | | | | | | | | | | | | | | | | | BackendStatistics view. This patch introduces two new callbacks in the event listener interface to handle the "buffered resource reserved" event and the "buffered resource released" event. Every time a buffered resource is used, an event is generated. Before this patch, the Scheduler (with the help of the ResourceManager) was responsible for tracking the scheduler's queue usage. However, that design forced the Scheduler to 'publish' scheduler's queue pressure information through the Backend interface. The goal of this patch is to break the dependency between the BackendStatistics view, and the Backend. Now the Scheduler knows how to notify "buffer reserved/released" events. The scheduler's queue usage analysis has been moved to the BackendStatistics. Differential Revision: https://reviews.llvm.org/D44686 llvm-svn: 328011
* [llvm-mca] Move the routine that computes processor resource masks to its ↵Andrea Di Biagio2018-03-201-31/+8
| | | | | | | | | | | | | | | | | | own file. Function computeProcResourceMasks is used by the ResourceManager (owned by the Scheduler) to compute resource masks for processor resources. Before this refactoring, there was an implicit dependency between the Scheduler and the InstrBuilder. That is because InstrBuilder has to know about resource masks when computing the set of processor resources consumed by a new instruction. With this patch, the functionality that computes resource masks has been extracted from the ResourceManager, and moved to a separate file (Support.h). This helps removing the dependency between the Scheduler and the InstrBuilder. No functional change intended. llvm-svn: 327973
* [llvm-mca] Simplify code. NFCAndrea Di Biagio2018-03-191-26/+40
| | | | llvm-svn: 327886
* [llvm-mca] Remove the logic that computes the reciprocal throughput, and ↵Andrea Di Biagio2018-03-131-20/+0
| | | | | | | | | | | | | | | | | make the SummaryView independent from the Backend. NFCI Since r327420, the tool can query the MCSchedModel interface to obtain the reciprocal throughput information. As a consequence, method `ResourceManager::getRThroughput`, and method `Backend::getRThroughput` are no longer needed. This patch simplifies the code by removing the custom RThroughput computation. This patch also refactors class SummaryView by removing the dependency with the Backend object. No functional change intended. llvm-svn: 327425
* [llvm-mca] Use a const ArrayRef in a few places. NFCAndrea Di Biagio2018-03-131-8/+8
| | | | llvm-svn: 327396
* [llvm-mca] Refactor event listeners to make the backend agnostic to event types.Clement Courbet2018-03-131-3/+18
| | | | | | | | | | Summary: This is a first step towards making the pipeline configurable. Subscribers: llvm-commits, andreadb Differential Revision: https://reviews.llvm.org/D44309 llvm-svn: 327389
OpenPOWER on IntegriCloud