summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/MachinePipeliner.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [CodeGen] Be as conservative about atomic accesses as for volatilePhilip Reames2019-02-011-1/+3
| | | | | | | | | | | | | | Background: At the moment, we record the AtomicOrdering of an access in the MMO, but also mark any atomic access as volatile in SelectionDAG. I'm working towards separating that. See https://reviews.llvm.org/D57601 for context. Update all usages of isVolatile in lib/CodeGen to preserve behaviour once atomic MMOs stop being also volatile. This is NFC in it's current form, but is essential for correctness once we make that final change. It useful to keep in mind that AtomicSDNode is not a parent of LoadSDNode, StoreSDNode, or LSBaseSDNode. As a result, any call to isVolatile on one of those static types doesn't need a companion isAtomic check. We should probably adjust that class hierarchy long term, but for now, that seperation is useful. I'm deliberately being conservative about handling. I want the change to stop adding volatile to be NFC itself, and then will work through places where we can be less conservative for atomics one by one in separate changes w/tests. Differential Revision: https://reviews.llvm.org/D57596 llvm-svn: 352937
* [NFC] Test commit : fix typo.Alexey Lapshin2019-01-251-1/+1
| | | | llvm-svn: 352248
* [Pipeliner] Add two pragmas to control software pipelining optimizationBrendon Cahoon2019-01-231-7/+76
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | #pragma clang loop pipeline(disable) Disable SWP optimization for the next loop. “disable” is the only possible value. #pragma clang loop pipeline_initiation_interval(number) Set value of initiation interval for SWP optimization to specified number value for the next loop. Number is the positive value greater than 0. These pragmas could be used for debugging or reducing compile time purposes. It is possible to disable SWP for concrete loops to save compilation time or to find bugs by not doing SWP to certain loops. It is possible to set value of initiation interval to concrete number to save compilation time by not doing extra pipeliner passes or to check created schedule for specific initiation interval. That is llvm part of the fix Clang part of fix: https://reviews.llvm.org/D55710 Patch by Alexey Lapshin! Differential Revision: https://reviews.llvm.org/D56403 llvm-svn: 351923
* Update the file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-191-4/+3
| | | | | | | | | | | | | | | | | to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351636
* Reapply r345008 "Split MachinePipeliner code into header and cpp files"Adrian Prantl2019-01-141-595/+18
| | | | | | | | | | | | | | Split MachinePipeliner code into header and cpp files to allow inheritance from SwingSchedulerDAG. This reapplies https://reviews.llvm.org/D56084 after moving the implementation of the dump functions into the .cpp files. This fixes a linker error when building with Clang modules enables and local submodule visibility disabled. Original patch by Lama Saba <lama.saba@intel.com>! llvm-svn: 351077
* [NFC] fix trivial typos in commentsHiroshi Inoue2019-01-091-2/+2
| | | | llvm-svn: 350690
* Revert "Revert "Revert "Resubmit rL345008 "Split MachinePipeliner code into ↵Adrian Prantl2019-01-081-5/+595
| | | | | | | | header and cpp files"""" This reverts commit D56084. llvm-svn: 350654
* Revert "Revert "Resubmit rL345008 "Split MachinePipeliner code into header ↵Lama Saba2019-01-081-595/+5
| | | | | | | | | | and cpp files""" This reverts commit rL350497 reported remaining issues seem to be unrelated to modules or this change. more info: https://reviews.llvm.org/D56084 llvm-svn: 350621
* Revert "Resubmit rL345008 "Split MachinePipeliner code into header and cpp ↵Lama Saba2019-01-061-5/+595
| | | | | | | | | files"" This reverts commit rL350493 issues related to modules still appear in http://green.lab.llvm.org/green/job/lldb-cmake llvm-svn: 350497
* Resubmit rL345008 "Split MachinePipeliner code into header and cpp files"Lama Saba2019-01-061-595/+5
| | | | | | | | | Resubmitted in rL345290 and reverted in rL350345 due to failures in http://green.lab.llvm.org/green/job/lldb-cmake/ Resubmitting after a workaround to lldb-cmake failure was committed in rL350346, more info in https://reviews.llvm.org/D56084 llvm-svn: 350493
* Revert "Resubmit rL345008 "Split MachinePipeliner code into header and cpp ↵Stefan Granitz2019-01-031-5/+595
| | | | | | | | files"" This reverts commit r350290. llvm-svn: 350345
* Resubmit rL345008 "Split MachinePipeliner code into header and cpp files"Lama Saba2019-01-031-595/+5
| | | | | | | | | The commit caused unclear failures in http://green.lab.llvm.org/green//job/lldb-cmake/ will revert if the error reappears Differential Revision: https://reviews.llvm.org/D56084 llvm-svn: 350290
* [CodeGen][NFC] Make `TII::getMemOpBaseImmOfs` return a base operandFrancis Visoiu Mistrih2018-11-281-11/+17
| | | | | | | | | | | | | | | | | | Currently, instructions doing memory accesses through a base operand that is not a register can not be analyzed using `TII::getMemOpBaseRegImmOfs`. This means that functions such as `TII::shouldClusterMemOps` will bail out on instructions using an FI as a base instead of a register. The goal of this patch is to refactor all this to return a base operand instead of a base register. Then in a separate patch, I will add FI support to the mem op clustering in the MachineScheduler. Differential Revision: https://reviews.llvm.org/D54846 llvm-svn: 347746
* [Pipeliner] Ignore Artificial dependences while computing recurrences.Sumanth Gundapaneni2018-10-251-3/+3
| | | | | | | | | | The artificial dependencies are not real dependencies. In some cases, they form circuits with bigger MII. However, they are used to schedule instructions better. Differential Revision: https://reviews.llvm.org/D53450 llvm-svn: 345319
* [Pipeliner] Remove the unneeded include header(NFC).Sumanth Gundapaneni2018-10-251-1/+0
| | | | | | Differential Revision: https://reviews.llvm.org/D53451 llvm-svn: 345318
* Revert "[MachinePipeliner] Split MachinePipeliner code into header and cpp ↵Aleksandr Urakov2018-10-231-7/+598
| | | | | | | | | files" This reverts commit 40760b733d9eef841c897338af5e9d81b12551bf. It seems that the commit is a cuse of the build failure. llvm-svn: 345032
* [MachinePipeliner] Split MachinePipeliner code into header and cpp filesLama Saba2018-10-231-598/+7
| | | | | | | | Split MachinePipeliner code into header and cpp files to allow inheritance from SwingSchedulerDAG Differential Revision: https://reviews.llvm.org/D53477 llvm-svn: 345008
* [Pipeliner] copyToPhi DAG Mutation to improve scheduling.Sumanth Gundapaneni2018-10-181-1/+95
| | | | | | | | | | | | | | | | | | | | | | | | | | In a loop, create artificial dependences between the source of a COPY/REG_SEQUENCE to the use in next iteration. Eg: SRC ----Data Dep--> COPY COPY ---Anti Dep--> PHI (implies, to be used in next iteration) PHI ----Data Dep--> USE This patches creates USE ----Artificial Dep---> SRC This will effectively schedule the COPY late to eliminate additional copies. Before this patch, the schedule can be SRC, COPY, USE : The COPY is used in next iteration and it needs to be preserved. After this patch, the schedule can be USE, SRC, COPY : The COPY is used in next iteration and the live interval is reduced. Differential Revision: https://reviews.llvm.org/D53303 llvm-svn: 344748
* [Pipeliner] Use the Index from Topo instead of relying on NodeNum. (NFC)Sumanth Gundapaneni2018-10-111-4/+14
| | | | | | | | | | In future, if we may add any new DAG mutations other than artificial dependencies, the NodeNum may not be valid. Instead the index from topological schedule DAG can be used as long as we update it with the DAG change. Differential Revision: https://reviews.llvm.org/D53104 llvm-svn: 344283
* [Pipeliner] Fix the Schedule DAG topoligical order.Sumanth Gundapaneni2018-10-111-0/+1
| | | | | | | | | This patch updates the DAG change to reflect in the topological ordering of the nodes. Differential Revision: https://reviews.llvm.org/D53105 llvm-svn: 344282
* Replace most users of UnknownSize with LocationSize::unknown(); NFCGeorge Burgess IV2018-10-101-2/+2
| | | | | | | | | | | | Moving away from UnknownSize is part of the effort to migrate us to LocationSizes (e.g. the cleanup promised in D44748). This doesn't entirely remove all of the uses of UnknownSize; some uses require tweaks to assume that UnknownSize isn't just some kind of int. This patch is intended to just be a trivial replacement for all places where LocationSize::unknown() will Just Work. llvm-svn: 344186
* llvm::sort(C.begin(), C.end(), ...) -> llvm::sort(C, ...)Fangrui Song2018-09-271-3/+2
| | | | | | | | | | | | Summary: The convenience wrapper in STLExtras is available since rL342102. Reviewers: dblaikie, javed.absar, JDevlieghere, andreadb Subscribers: MatzeB, sanjoy, arsenm, dschuff, mehdi_amini, sdardis, nemanjai, jvesely, nhaehnle, sbc100, jgravelle-google, eraman, aheejin, kbarton, JDevlieghere, javed.absar, gbedwell, jrtc27, mgrang, atanasyan, steven_wu, george.burgess.iv, dexonsmith, kristina, jsji, llvm-commits Differential Revision: https://reviews.llvm.org/D52573 llvm-svn: 343163
* ScheduleDAG: Cleanup dumping code; NFCMatthias Braun2018-09-191-6/+3
| | | | | | | | | | | | - Instead of having both `SUnit::dump(ScheduleDAG*)` and `ScheduleDAG::dumpNode(ScheduleDAG*)`, just keep the latter around. - Add `ScheduleDAG::dump()` and avoid code duplication in several places. Implement it for different ScheduleDAG variants. - Add `ScheduleDAG::dumpNodeName()` in favor of the `SUnit::print()` functions. They were only ever used for debug dumping and putting the function into ScheduleDAG is consistent with the `dumpNode()` change. llvm-svn: 342520
* [Pipeliner] Fix incorrect phi values in the epilog and kernelBrendon Cahoon2018-08-271-29/+32
| | | | | | | | | | | | | | | | | | | The code that generates the loop definition operand for phis in the epilog and kernel is incorrect in some cases. In the kernel, when a phi refers to another phi, the code that updates PhiOp2 needs to include the stage difference between the two phis. In the epilog, the check for using the loop definition instead of the phi definition uses the StageDiffAdj value (the difference between the phi stage and the loop definition stage), but the adjustment is not needed to determine if the current stage contains an iteration with the loop definition. Differential Revision: https://reviews.llvm.org/D51167 llvm-svn: 340782
* Consistently use MemoryLocation::UnknownSize to indicate unknown access sizeKrzysztof Parzyszek2018-08-201-2/+2
| | | | | | | | | | | | 1. Change the software pipeliner to use unknown size instead of dropping memory operands. It used to do it before, but MachineInstr::mayAlias did not handle it correctly. 2. Recognize UnknownSize in MachineInstr::mayAlias. 3. Print and parse UnknownSize in MIR. Differential Revision: https://reviews.llvm.org/D50339 llvm-svn: 340208
* [MI] Change the array of `MachineMemOperand` pointers to beChandler Carruth2018-08-161-9/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | a generically extensible collection of extra info attached to a `MachineInstr`. The primary change here is cleaning up the APIs used for setting and manipulating the `MachineMemOperand` pointer arrays so chat we can change how they are allocated. Then we introduce an extra info object that using the trailing object pattern to attach some number of MMOs but also other extra info. The design of this is specifically so that this extra info has a fixed necessary cost (the header tracking what extra info is included) and everything else can be tail allocated. This pattern works especially well with a `BumpPtrAllocator` which we use here. I've also added the basic scaffolding for putting interesting pointers into this, namely pre- and post-instruction symbols. These aren't used anywhere yet, they're just there to ensure I've actually gotten the data structure types correct. I'll flesh out support for these in a subsequent patch (MIR dumping, parsing, the works). Finally, I've included an optimization where we store any single pointer inline in the `MachineInstr` to avoid the allocation overhead. This is expected to be the overwhelmingly most common case and so should avoid any memory usage growth due to slightly less clever / dense allocation when dealing with >1 MMO. This did require several ergonomic improvements to the `PointerSumType` to reasonably support the various usage models. This also has a side effect of freeing up 8 bits within the `MachineInstr` which could be repurposed for something else. The suggested direction here came largely from Hal Finkel. I hope it was worth it. ;] It does hopefully clear a path for subsequent extensions w/o nearly as much leg work. Lots of thanks to Reid and Justin for careful reviews and ideas about how to do all of this. Differential Revision: https://reviews.llvm.org/D50701 llvm-svn: 339940
* [CodeGen] Fix inconsistent declaration parameter nameFangrui Song2018-07-161-2/+2
| | | | llvm-svn: 337200
* [NFC] fix trivial typos in commentsHiroshi Inoue2018-06-201-8/+8
| | | | llvm-svn: 335096
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-39/+41
| | | | | | | | | | | | | | | | 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
* IWYU for llvm-config.h in llvm, additions.Nico Weber2018-04-301-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | See r331124 for how I made a list of files missing the include. I then ran this Python script: for f in open('filelist.txt'): f = f.strip() fl = open(f).readlines() found = False for i in xrange(len(fl)): p = '#include "llvm/' if not fl[i].startswith(p): continue if fl[i][len(p):] > 'Config': fl.insert(i, '#include "llvm/Config/llvm-config.h"\n') found = True break if not found: print 'not found', f else: open(f, 'w').write(''.join(fl)) and then looked through everything with `svn diff | diffstat -l | xargs -n 1000 gvim -p` and tried to fix include ordering and whatnot. No intended behavior change. llvm-svn: 331184
* [NFC] fix trivial typos in commentsHiroshi Inoue2018-04-131-1/+1
| | | | | | "the the" -> "the", "we we" -> "we", etc llvm-svn: 330006
* [Pipeliner] Use std::stable_sort when ordering NodeSetsKrzysztof Parzyszek2018-04-121-1/+1
| | | | | | | | | | | There are cases when individual NodeSets can be equal with respect to the ordering criteria. Since they are stored in an ordered container, use stable_sort to preserve the relative order of equal NodeSets. This should remove non-determinism discovered by shuffling done in llvm::sort with expensive checks enabled. llvm-svn: 329915
* [CodeGen] Change std::sort to llvm::sort in response to r327219Mandeep Singh Grang2018-04-061-3/+4
| | | | | | | | | | | | | | | | | | | | | | Summary: r327219 added wrappers to std::sort which randomly shuffle the container before sorting. This will help in uncovering non-determinism caused due to undefined sorting order of objects having the same key. To make use of that infrastructure we need to invoke llvm::sort instead of std::sort. Note: This patch is one of a series of patches to replace *all* std::sort to llvm::sort. Refer the comments section in D44363 for a list of all the required patches. Reviewers: bogner, rnk, MatzeB, RKSimon Reviewed By: rnk Subscribers: JDevlieghere, javed.absar, llvm-commits Differential Revision: https://reviews.llvm.org/D45133 llvm-svn: 329435
* [Pipeliner] Several node-ordering fixesKrzysztof Parzyszek2018-03-261-18/+16
| | | | | | | | | | | | | | | | | | | | | | First, we change the heuristic that is used to ignore the recurrent node-sets in the node ordering. In certain cases it's not important to focus on the recurrent node-sets. Instead, the algorithm begins by considering all the instructions in the node ordering step. Second, a minor change to the bottom up traversal, which needs to consider loop carried dependences (modeled as anti dependences). Previously, these instructions were skipped, which caused problems because the instruction ends up having both predecessors and sucessors in the schedule. Third, consider anti-dependences as a tie breaker when choosing between instructions in the node ordering. We want to make sure that the source of the anti-dependence does not end up with both predecesssors and sucessors in the final node ordering. Patch by Brendon Cahoon. llvm-svn: 328554
* [Pipeliner] Check for affine expression in isLoopCarriedOrderKrzysztof Parzyszek2018-03-261-1/+13
| | | | | | | | | | | | | | | | | The pipeliner must add a loop carried dependence between two memory operations if the base register is not an affine (linear) exression. The current implementation doesn't check how the base register is defined, which allows non-affine expressions, and then the pipeliner does not add a loop carried dependence when one is needed. This patch adds code to isLoopCarriedOrder that checks if the base register of the memory operations is defined by a phi, and the loop definition for the phi is a constant increment value. This is a very simple check for a linear expression. Patch by Brendon Cahoon. llvm-svn: 328550
* [Pipeliner] Add missing loop carried dependencesKrzysztof Parzyszek2018-03-261-14/+23
| | | | | | | | | | | | | | | | | | | | | | The pipeliner is not adding a dependence edge for a loop carried dependence, and ends up scheduling a load from iteration n prior to an aliased store in iteration n-1. The code that adds the loop carried dependences in the pipeliner doesn't check if the memory objects for loads and stores are "identified" (i.e., distinct) objects. If they are not, then the code that adds the dependences needs to be conservative. The objects can be used to check dependences only when they are distinct objects. The code that checks for loop carried dependences has been updated to classify loads and stores that are not identified as "unknown" values. A store with an "unknown" value can potentially create a loop carried dependence with any pending load. Patch by Brendon Cahoon. llvm-svn: 328547
* [Pipeliner] Fix renaming in pipeliner when eliminating phisKrzysztof Parzyszek2018-03-261-1/+1
| | | | | | | | | | | | | | | The phi renaming code in the pipeliner uses the wrong value when rewriting phi uses, which results in an undefined value. In this case, the original phi is no longer needed due to the order of instruction in the pipelined loop. The pipeliner was assuming, in this case, the the phi loop definition should be used to rewrite the uses. However, the pipeliner needs to check to make sure that the loop definition has already been scheduled. If not, then the phi initial value needs to be used instead. Patch by Brendon Cahoon. llvm-svn: 328545
* [Pipeliner] Fix number of phis to generate in the epilogKrzysztof Parzyszek2018-03-261-10/+7
| | | | | | | | | | | | | | | | | | | | The pipeliner was generating too many phis in the epilog blocks, which caused incorrect code generation when rewriting an instruction that uses the phi. In this case, there 3 prolog and epilog stages. An existing phi was scheduled at stage 1. When generating the code for the 2nd epilog an extra new phi was generated. To fix this, we need to update the code that calculates the maximum number of phis that can be generated, which is based upon the current prolog stage and the stage of the original phi. In this case, when the prolog stage is 1 and the original phi stage is 1, the maximum number of phis to generate is 2. Patch by Brendon Cahoon. llvm-svn: 328543
* [Pipeliner] Use latency to compute RecMIIKrzysztof Parzyszek2018-03-261-4/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The patch contains severals changes needed to pipeline an example that was transformed so that a Phi with a subreg is converted to copies. The pipeliner wasn't working for a couple of reasons. - The RecMII was 3 instead of 2 due to the extra copies. - Copy instructions contained a latency of 1. - The node order algorithm was not choosing the best "bottom" node, which caused an instruction to be scheduled that had a predecessor and successor already scheduled. - Updated the Hexagon Machine Scheduler to check if the node is latency bound when adding the cost for a 0-latency dependence. The RecMII was 3 because the computation looks at the number of nodes in the recurrence. The extra copy is an extra node but it shouldn't increase the latency. The new RecMII computation looks at the latency of the instructions in the recurrence. We changed the latency of the dependence of a copy to 0. The latency computation for the copy also checks the use of the copy (similar to a reg_sequence). The node order algorithm was not choosing the last instruction in the recurrence for a bottom up traversal. This was when the last instruction is a copy. A check was added when choosing the instruction to check for NodeNum if the maxASAP is the same. This means that the scheduler will not end up with another node in the recurrence that has both a predecessor and successor already scheduled. The cost computation in Hexagon Machine Scheduler adds cost when an instruction can be packetized with a zero-latency instruction. We should only do this if the schedule is latency bound. Patch by Brendon Cahoon. llvm-svn: 328542
* [Pipeliner] Fix assert caused by pipeliner serializationKrzysztof Parzyszek2018-03-261-28/+23
| | | | | | | | | | | | | | | | | | | | | | | | | | | | The pipeliner is asserting because the serialization step that occurs at the end is deleting an instruction. The assert occurs later on because there is a use without a definition. The problem occurs when an instruction defines a value used by a REQ_SEQUENCE and that value is used by a COPY instruction. The latencies between these instructions are zero, so they are put in to the same packet. The serialization code is unable to handle this correctly, and ends up putting the REG_SEQUENCE before its definition. There is special code in the serialization step that attempts to handle zero-cost instructions (phis, copy, reg_sequence) differently than regular instructions. Unfortunately, this means the order does not come out correct. This patch simplifies the code by changing the seperate steps for handling zero-cost and regular instructions. Only phis are handled separate now, since they should occurs first. Then, this patch adds checks to make use the MoveUse is set to the smallest value if there are multiple uses in a cycle. Patch by Brendon Cahoon. llvm-svn: 328540
* [Pipeliner] Enable more base+offset dependence changes in pipelinerKrzysztof Parzyszek2018-03-261-2/+7
| | | | | | | | | | | | | | | | | | | | The pipeliner changes dependences between base+offset instructions (loads and stores) so that the instructions have more flexibility to be scheduled with respect to each other. This occurs when the pipeliner is able to compute that the instructions will not alias if their order is changed. The prevous code enforced the alias property by checking if the base register is the same, and that the offset values are either both positive or negative. This patch improves the alias check by using the API areMemAccessesTriviallyDisjoint instead. This enables more cases, especially if the offset is a negative value. The pipeliner uses the function by creating a new instruction with the offset used in the next iteration. Patch by Brendon Cahoon. llvm-svn: 328538
* [Pipeliner] Fix calculation when reusing phisKrzysztof Parzyszek2018-03-261-3/+3
| | | | | | | | | | | | | | | | | A schedule may require that a phi from the original loop is used in multiple iterations in the scheduled loop. When this occurs, we generate multiple phis in the pipelined loop to save the value across iterations. When we generate the new phis and update the register names in the pipelined loop, the pipeliner attempts to reuse a previously generated phi, when possible. The calculation for the name of the new phi needs to account for the version/iteration of the original phi. Also, in the epilog, the code only needs to check backwards for a previous iteration until reaching the first prolog block. Patch by Brendon Cahoon. llvm-svn: 328537
* [Pipeliner] Fix check for order dependences when finalizing instructionsKrzysztof Parzyszek2018-03-261-51/+49
| | | | | | | | | | | | | | | | | The code in orderDepdences that looks at the order dependences between instructions was processing all the successor and predecessor order dependences. However, we really only want to check for an order dependence for instructions scheduled in the same cycle. Also, fixed how the pipeliner handles output dependences. An output dependence is also a potential loop carried dependence. The pipeliner didn't handle this case properly so an invalid schedule could be created that allowed an output dependence to be scheduled in the next iteration at the same cycle. Patch by Brendon Cahoon. llvm-svn: 328516
* [Pipeliner] Fix in the pipeliner phi reuse codeKrzysztof Parzyszek2018-03-261-1/+2
| | | | | | | | | | | When the definition of a phi is used by a phi in the next iteration, the pipeliner was assuming that the definition is processed first. Because of the assumption, an incorrect phi name was used. This patch has a check to see if the phi definition has been processed already. Patch by Brendon Cahoon. llvm-svn: 328510
* [Pipeliner] Pipeliner should mark physical registers as usedKrzysztof Parzyszek2018-03-261-1/+8
| | | | | | | | | | | | | The software pipeliner attempts to delete dead instructions after generating the pipelined loop. The code looks for uses of each instruction. Physical registers should be treated differently because the use chains do not exist. The code that checks for dead instructions should assume that definitions of physical registers are used if the operand doesn't contain the dead flag. Patch by Brendon Cahoon. llvm-svn: 328509
* [Pipeliner] Correctly update memoperands in the epilogKrzysztof Parzyszek2018-03-261-2/+4
| | | | | | | | | | | | | | | | The pipeliner needs to be conservative when updating the memoperands of instructions in the epilog. Previously, the pipeliner was changing the offset of the memoperand based upon the scheduling stage. However, that is incorrect when control flow branches around the kernel code. The bug enabled a load and store to the same stack offset to be swapped. This patch fixes the bug by updating the size of the memoperands to be UINT_MAX. This conservative value means that dependences will be created between other loads and stores. Patch by Brendon Cahoon. llvm-svn: 328508
* [Hexagon] Eliminate subregisters from PHI nodes before pipeliningKrzysztof Parzyszek2018-03-211-39/+74
| | | | | | | | | | | | | | | | The pipeliner needs to remove instructions from the SlotIndexes structure when they are deleted. Otherwise, the SlotIndexes map has stale data, and an assert will occur when adding new instructions. This patch also changes the pipeliner to make the back-edge of a loop carried dependence 1 cycle. The 1 cycle latency is added to the anti-dependence that represents the back-edge. This changes eliminates a couple of hacks added to the pipeliner to handle the latency of the back-edge. It is needed to correctly pipeline the test case for the sub-register elimination pass. llvm-svn: 328113
* Quiet unused variable warnings. NFC.David L Kreitzer2018-03-161-0/+3
| | | | | | Differential revision: https://reviews.llvm.org/D44583 llvm-svn: 327745
* [Pipeliner] Fixed node order issue related to zero latency edgesRoorda, Jan-Willem2018-03-071-22/+139
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: A desired property of the node order in Swing Modulo Scheduling is that for nodes outside circuits the following holds: none of them is scheduled after both a successor and a predecessor. We call node orders that meet this property valid. Although invalid node orders do not lead to the generation of incorrect code, they can cause the pipeliner not being able to find a pipelined schedule for arbitrary II. The reason is that after scheduling the successor and the predecessor of a node, no room may be left to schedule the node itself. For data flow graphs with 0-latency edges, the node ordering algorithm of Swing Modulo Scheduling can generate such undesired invalid node orders. This patch fixes that. In the remainder of this commit message, I will give an example demonstrating the issue, explain the fix, and explain how the the fix is tested. Consider, as an example, the following data flow graph with all edge latencies 0 and all edges pointing downward. ``` n0 / \ n1 n3 \ / n2 | n4 ``` Consider the implemented node order algorithm in top-down mode. In that mode, the algorithm orders the nodes based on greatest Height and in case of equal Height on lowest Movability. Finally, in case of equal Height and Movability, given two nodes with an edge between them, the algorithm prefers the source-node. In the graph, for every node, the Height and Movability are equal to 0. As will be explained below, the algorithm can generate the order n0, n1, n2, n3, n4. So, node n3 is scheduled after its predecessor n0 and after its successor n2. The reason that the algorithm can put node n2 in the order before node n3, even though they have an edge between them in which node n3 is the source, is the following: Suppose the algorithm has constructed the partial node order n0, n1. Then, the nodes left to be ordered are nodes n2, n3, and n4. Suppose that the while-loop in the implemented algorithm considers the nodes in the order n4, n3, n2. The algorithm will start with node n4, and look for more preferable nodes. First, node n4 will be compared with node n3. As the nodes have equal Height and Movability and have no edge between them, the algorithm will stick with node n4. Then node n4 is compared with node n2. Again the Height and Movability are equal. But, this time, there is an edge between the two nodes, and the algorithm will prefer the source node n2. As there are no nodes left to compare, the algorithm will add node n2 to the node order, yielding the partial node order n0, n1, n2. In this way node n2 arrives in the node-order before node n3. To solve this, this patch introduces the ZeroLatencyHeight (ZLH) property for nodes. It is defined as the maximum unweighted length of a path from the given node to an arbitrary node in which each edge has latency 0. So, ZLH(n0)=3, ZLH(n1)=ZLH(n3)=2, ZLH(n2)=1, and ZLH(n4)=0 In this patch, the preference for a greater ZeroLatencyHeight is added in the top-down mode of the node ordering algorithm, after the preference for a greater Height, and before the preference for a lower Movability. Therefore, the two allowed node-orders are n0, n1, n3, n2, n4 and n0, n3, n1, n2, n4. Both of them are valid node orders. In the same way, the bottom-up mode of the node ordering algorithm is adapted by introducing the ZeroLatencyDepth property for nodes. The patch is tested by adding extra checks to the following existing lit-tests: test/CodeGen/Hexagon/SUnit-boundary-prob.ll test/CodeGen/Hexagon/frame-offset-overflow.ll test/CodeGen/Hexagon/vect/vect-shuffle.ll Before this patch, the pipeliner failed to pipeline the loops in these tests due to invalid node-orders. After the patch, the pipeliner successfully pipelines all these loops. Reviewers: bcahoon Reviewed By: bcahoon Subscribers: Ayal, mgrang, llvm-commits Differential Revision: https://reviews.llvm.org/D43620 llvm-svn: 326925
* [Pipeliner] Test commit: fixed spelling mistake in commentsRoorda, Jan-Willem2018-03-061-1/+1
| | | | | | | | | | Reviewers: bcahoon Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D44152 llvm-svn: 326808
OpenPOWER on IntegriCloud