summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/MachinePipeliner.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [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
* [Pipeliner] Drop memrefs instead of creating ones with size UINT64_MAXKrzysztof Parzyszek2018-02-271-2/+4
| | | | | | | | | Absence of memory operands is treated as "aliasing everything", so dropping them is sufficient. Recommit r326256 with a fixed testcase. llvm-svn: 326262
* Revert "[Pipeliner] Drop memrefs instead of creating ones with size UINT64_MAX"Krzysztof Parzyszek2018-02-271-4/+2
| | | | | | This reverts r326256. One testcase needs to be updated. llvm-svn: 326259
* [Pipeliner] Drop memrefs instead of creating ones with size UINT64_MAXKrzysztof Parzyszek2018-02-271-2/+4
| | | | | | | Absence of memory operands is treated as "aliasing everything", so dropping them is sufficient. llvm-svn: 326256
* [NFC] fix trivial typos in commentsHiroshi Inoue2018-01-171-3/+3
| | | | | | "the the" -> "the" llvm-svn: 322636
* support phi ranges for machine-level IRBob Wilson2018-01-041-16/+10
| | | | | | | | | | | | Add iterator ranges for machine instruction phis, similar to the IR-level phi ranges added in r303964. I updated a few places to use this. Besides general code simplification, this change will allow removing a non-upstream change from Swift's copy of LLVM (in a better way than my previous attempt in http://reviews.llvm.org/D19080). https://reviews.llvm.org/D41672 llvm-svn: 321783
* MachineFunction: Return reference from getFunction(); NFCMatthias Braun2017-12-151-2/+2
| | | | | | The Function can never be nullptr so we can return a reference. llvm-svn: 320884
* Rename LiveIntervalAnalysis.h to LiveIntervals.hMatthias Braun2017-12-131-1/+1
| | | | | | | | | | Headers/Implementation files should be named after the class they declare/define. Also eliminated an `#include "llvm/CodeGen/LiveIntervalAnalysis.h"` in favor of `class LiveIntarvals;` llvm-svn: 320546
* Fix a bunch more layering of CodeGen headers that are in TargetDavid Blaikie2017-11-171-3/+3
| | | | | | | | All these headers already depend on CodeGen headers so moving them into CodeGen fixes the layering (since CodeGen depends on Target, not the other way around). llvm-svn: 318490
* Target/TargetInstrInfo.h -> CodeGen/TargetInstrInfo.h to match layeringDavid Blaikie2017-11-081-1/+1
| | | | | | | | This header includes CodeGen headers, and is not, itself, included by any Target headers, so move it into CodeGen to match the layering of its implementation. llvm-svn: 317647
* Reverting r315590; it did not include changes for llvm-tblgen, which is ↵Aaron Ballman2017-10-151-2/+2
| | | | | | | | causing link errors for several people. Error LNK2019 unresolved external symbol "public: void __cdecl `anonymous namespace'::MatchableInfo::dump(void)const " (?dump@MatchableInfo@?A0xf4f1c304@@QEBAXXZ) referenced in function "public: void __cdecl `anonymous namespace'::AsmMatcherEmitter::run(class llvm::raw_ostream &)" (?run@AsmMatcherEmitter@?A0xf4f1c304@@QEAAXAEAVraw_ostream@llvm@@@Z) llvm-tblgen D:\llvm\2017\utils\TableGen\AsmMatcherEmitter.obj 1 llvm-svn: 315854
* [dump] Remove NDEBUG from test to enable dump methods [NFC]Don Hinton2017-10-121-2/+2
| | | | | | | | | | | | | | | Summary: Add LLVM_FORCE_ENABLE_DUMP cmake option, and use it along with LLVM_ENABLE_ASSERTIONS to set LLVM_ENABLE_DUMP. Remove NDEBUG and only use LLVM_ENABLE_DUMP to enable dump methods. Move definition of LLVM_ENABLE_DUMP from config.h to llvm-config.h so it'll be picked up by public headers. Differential Revision: https://reviews.llvm.org/D38406 llvm-svn: 315590
* [Pipeliner] Fix offset value for instrs dependent on post-inc load/storesKrzysztof Parzyszek2017-10-111-3/+8
| | | | | | | | | | | | The software pipeliner and the packetizer try to break dependence between the post-increment instruction and the dependent memory instructions by changing the base register and the offset value. However, in some cases, the existing logic didn't work properly and created incorrect offset value. Patch by Jyotsna Verma. llvm-svn: 315468
* [Pipeliner] Improve serialization order for post-incrementsKrzysztof Parzyszek2017-10-111-13/+57
| | | | | | | | | | | | | | | | | | | The pipeliner is generating a serial sequence that causes poor register allocation when a post-increment instruction appears prior to the use of the post-increment register. This occurs when there is a circular set of dependences involved with a sequence of instructions in the same cycle. In this case, there is no serialization of the parallel semantics that will not cause an additional register to be allocated. This patch fixes the problem by changing the instructions so that the post-increment instruction is used by the subsequent instruction, which enables the register allocator to make a better decision and not require another register. Patch by Brendon Cahoon. llvm-svn: 315466
* CodeGen: Minor cleanups to use MachineInstr::getMF. NFCJustin Bogner2017-10-101-1/+1
| | | | | | | Since r315388 we have a shorter way to say this, so we'll replace MI->getParent()->getParent() with MI->getMF() in a few places. llvm-svn: 315390
* [CodeGen] Fix some Clang-tidy modernize-use-using and Include What You Use ↵Eugene Zelenko2017-09-111-49/+50
| | | | | | warnings; other minor fixes (NFC). llvm-svn: 312971
* Guard print() functions only used by dump() functions.Florian Hahn2017-07-311-1/+1
| | | | | | | | | | | | | | | | | | | Summary: Since r293359, most dump() function are only defined when `!defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)` holds. print() functions only used by dump() functions are now unused in release builds, generating lots of warnings. This patch only defines some print() functions if they are used. Reviewers: MatzeB Reviewed By: MatzeB Subscribers: arsenm, mzolotukhin, nhaehnle, llvm-commits Differential Revision: https://reviews.llvm.org/D35949 llvm-svn: 309553
* Sort the remaining #include lines in include/... and lib/....Chandler Carruth2017-06-061-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | I did this a long time ago with a janky python script, but now clang-format has built-in support for this. I fed clang-format every line with a #include and let it re-sort things according to the precise LLVM rules for include ordering baked into clang-format these days. I've reverted a number of files where the results of sorting includes isn't healthy. Either places where we have legacy code relying on particular include ordering (where possible, I'll fix these separately) or where we have particular formatting around #include lines that I didn't want to disturb in this patch. This patch is *entirely* mechanical. If you get merge conflicts or anything, just ignore the changes in this patch and run clang-format over your #include lines in the files. Sorry for any noise here, but it is important to keep these things stable. I was seeing an increasing number of patches with irrelevant re-ordering of #include lines because clang-format was used. This patch at least isolates that churn, makes it easy to skip when resolving conflicts, and gets us to a clean baseline (again). llvm-svn: 304787
* CodeGen: Rename DEBUG_TYPE to match passnamesMatthias Braun2017-05-251-2/+2
| | | | | | | | Rename the DEBUG_TYPE to match the names of corresponding passes where it makes sense. Also establish the pattern of simply referencing DEBUG_TYPE instead of repeating the passname where possible. llvm-svn: 303921
* Spelling mistakes in comments. NFCI.Simon Pilgrim2017-03-311-1/+1
| | | | llvm-svn: 299197
* Rename AttributeSet to AttributeListReid Kleckner2017-03-211-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | Summary: This class is a list of AttributeSetNodes corresponding the function prototype of a call or function declaration. This class used to be called ParamAttrListPtr, then AttrListPtr, then AttributeSet. It is typically accessed by parameter and return value index, so "AttributeList" seems like a more intuitive name. Rename AttributeSetImpl to AttributeListImpl to follow suit. It's useful to rename this class so that we can rename AttributeSetNode to AttributeSet later. AttributeSet is the set of attributes that apply to a single function, argument, or return value. Reviewers: sanjoy, javed.absar, chandlerc, pete Reviewed By: pete Subscribers: pete, jholewinski, arsenm, dschuff, mehdi_amini, jfb, nhaehnle, sbc100, void, llvm-commits Differential Revision: https://reviews.llvm.org/D31102 llvm-svn: 298393
* Remove redundant conditions (PR31753). NFCI.Simon Pilgrim2017-03-161-2/+2
| | | | llvm-svn: 297976
* [MachinePipeliner] Remove redundant destructor. NFC.Benjamin Kramer2017-02-161-8/+1
| | | | llvm-svn: 295372
* Cleanup dump() functions.Matthias Braun2017-01-281-2/+6
| | | | | | | | | | | | | | | | | | We had various variants of defining dump() functions in LLVM. Normalize them (this should just consistently implement the things discussed in http://lists.llvm.org/pipermail/cfe-dev/2014-January/034323.html For reference: - Public headers should just declare the dump() method but not use LLVM_DUMP_METHOD or #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) - The definition of a dump method should look like this: #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) LLVM_DUMP_METHOD void MyClass::dump() { // print stuff to dbgs()... } #endif llvm-svn: 293359
* Add the DAG mutation interface to the software pipelinerKrzysztof Parzyszek2016-12-221-1/+18
| | | | llvm-svn: 290360
* Fix two bugs in the pipeliner in renaming phis in the prolog and epilogKrzysztof Parzyszek2016-12-221-2/+2
| | | | | | | | | | | | | | | When the pipeliner is renaming phi values, it may need to iterate through the phi operands to check for other phis. However, the pipeliner should stop once it reaches a phi that is outside the pipelined loop. Also, when the generateExistingPhis code is unable to reuse an existing phi, the default code that computes the PhiOp2 is only to be used when the pipeliner is generating the kernel. Otherwise, the phi may be a value computed earlier in the same epilog. Patch by Brendon Cahoon. llvm-svn: 290355
* Extract LaneBitmask into a separate typeKrzysztof Parzyszek2016-12-151-2/+4
| | | | | | | | | | | | Specifically avoid implicit conversions from/to integral types to avoid potential errors when changing the underlying type. For example, a typical initialization of a "full" mask was "LaneMask = ~0u", which would result in a value of 0x00000000FFFFFFFF if the type was extended to uint64_t. Differential Revision: https://reviews.llvm.org/D27454 llvm-svn: 289820
* Remove redundant condition (PR28800) NFCI.Simon Pilgrim2016-11-141-2/+1
| | | | | | | | | | 'A || (!A && B)' is equivalent to 'A || B': (LoopCycle > DefCycle) || (LoopCycle <= DefCycle && LoopStage <= DefStage) --> (LoopCycle > DefCycle) || (LoopStage <= DefStage) llvm-svn: 286811
* Use MachineInstr::mop_iterator instead of MIOperands; NFCMatthias Braun2016-10-241-6/+6
| | | | | | | | (Const)?MIOperands is equivalent to the C++ style MachineInstr::mop_iterator. Use the latter for consistency except for a few callers of MIOperands::analyzePhysReg(). llvm-svn: 285029
* Finish renaming remaining analyzeBranch functionsMatt Arsenault2016-09-141-2/+2
| | | | llvm-svn: 281535
* Make analyzeBranch family of instruction names consistentMatt Arsenault2016-09-141-6/+6
| | | | | | | analyzeBranch was renamed to use lowercase first, rename the related set to match. llvm-svn: 281506
* [CodeGen] Split out the notions of MI invariance and MI dereferenceability.Justin Lebar2016-09-111-1/+2
| | | | | | | | | | | | | | | | | | | Summary: An IR load can be invariant, dereferenceable, neither, or both. But currently, MI's notion of invariance is IR-invariant && IR-dereferenceable. This patch splits up the notions of invariance and dereferenceability at the MI level. It's NFC, so adds some probably-unnecessary "is-dereferenceable" checks, which we can remove later if desired. Reviewers: chandlerc, tstellarAMD Subscribers: jholewinski, arsenm, nemanjai, llvm-commits Differential Revision: https://reviews.llvm.org/D23371 llvm-svn: 281151
* [CodeGen] Rename MachineInstr::isInvariantLoad to ↵Justin Lebar2016-09-101-1/+1
| | | | | | | | | | | | | | | | | | | | isDereferenceableInvariantLoad. NFC Summary: I want to separate out the notions of invariance and dereferenceability at the MI level, so that they correspond to the equivalent concepts at the IR level. (Currently an MI load is MI-invariant iff it's IR-invariant and IR-dereferenceable.) First step is renaming this function. Reviewers: chandlerc Subscribers: MatzeB, jfb, llvm-commits Differential Revision: https://reviews.llvm.org/D23370 llvm-svn: 281125
* ADT: Give ilist<T>::reverse_iterator a handle to the current nodeDuncan P. N. Exon Smith2016-08-301-2/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Reverse iterators to doubly-linked lists can be simpler (and cheaper) than std::reverse_iterator. Make it so. In particular, change ilist<T>::reverse_iterator so that it is *never* invalidated unless the node it references is deleted. This matches the guarantees of ilist<T>::iterator. (Note: MachineBasicBlock::iterator is *not* an ilist iterator, but a MachineInstrBundleIterator<MachineInstr>. This commit does not change MachineBasicBlock::reverse_iterator, but it does update MachineBasicBlock::reverse_instr_iterator. See note at end of commit message for details on bundle iterators.) Given the list (with the Sentinel showing twice for simplicity): [Sentinel] <-> A <-> B <-> [Sentinel] the following is now true: 1. begin() represents A. 2. begin() holds the pointer for A. 3. end() represents [Sentinel]. 4. end() holds the poitner for [Sentinel]. 5. rbegin() represents B. 6. rbegin() holds the pointer for B. 7. rend() represents [Sentinel]. 8. rend() holds the pointer for [Sentinel]. The changes are #6 and #8. Here are some properties from the old scheme (which used std::reverse_iterator): - rbegin() held the pointer for [Sentinel] and rend() held the pointer for A; - operator*() cost two dereferences instead of one; - converting from a valid iterator to its valid reverse_iterator involved a confusing increment; and - "RI++->erase()" left RI invalid. The unintuitive replacement was "RI->erase(), RE = end()". With vector-like data structures these properties are hard to avoid (since past-the-beginning is not a valid pointer), and don't impose a real cost (since there's still only one dereference, and all iterators are invalidated on erase). But with lists, this was a poor design. Specifically, the following code (which obviously works with normal iterators) now works with ilist::reverse_iterator as well: for (auto RI = L.rbegin(), RE = L.rend(); RI != RE;) fooThatMightRemoveArgFromList(*RI++); Converting between iterator and reverse_iterator for the same node uses the getReverse() function. reverse_iterator iterator::getReverse(); iterator reverse_iterator::getReverse(); Why doesn't iterator <=> reverse_iterator conversion use constructors? In order to catch and update old code, reverse_iterator does not even have an explicit conversion from iterator. It wouldn't be safe because there would be no reasonable way to catch all the bugs from the changed semantic (see the changes at call sites that are part of this patch). Old code used this API: std::reverse_iterator::reverse_iterator(iterator); iterator std::reverse_iterator::base(); Here's how to update from old code to new (that incorporates the semantic change), assuming I is an ilist<>::iterator and RI is an ilist<>::reverse_iterator: [Old] ==> [New] reverse_iterator(I) (--I).getReverse() reverse_iterator(I) ++I.getReverse() --reverse_iterator(I) I.getReverse() reverse_iterator(++I) I.getReverse() RI.base() (--RI).getReverse() RI.base() ++RI.getReverse() --RI.base() RI.getReverse() (++RI).base() RI.getReverse() delete &*RI, RE = end() delete &*RI++ RI->erase(), RE = end() RI++->erase() ======================================= Note: bundle iterators are out of scope ======================================= MachineBasicBlock::iterator, also known as MachineInstrBundleIterator<MachineInstr>, is a wrapper to represent MachineInstr bundles. The idea is that each operator++ takes you to the beginning of the next bundle. Implementing a sane reverse iterator for this is harder than ilist. Here are the options: - Use std::reverse_iterator<MBB::i>. Store a handle to the beginning of the next bundle. A call to operator*() runs a loop (usually operator--() will be called 1 time, for unbundled instructions). Increment/decrement just works. This is the status quo. - Store a handle to the final node in the bundle. A call to operator*() still runs a loop, but it iterates one time fewer (usually operator--() will be called 0 times, for unbundled instructions). Increment/decrement just works. - Make the ilist_sentinel<MachineInstr> *always* store that it's the sentinel (instead of just in asserts mode). Then the bundle iterator can sniff the sentinel bit in operator++(). I initially tried implementing the end() option as part of this commit, but updating iterator/reverse_iterator conversion call sites was error-prone. I have a WIP series of patches that implements the final option. llvm-svn: 280032
* [CodeGen] Convert a loop to a for-each loop. NFCJustin Lebar2016-08-231-7/+5
| | | | llvm-svn: 279536
* [Pipeliner] Fix an asssert due to invalid Phi in the epilogBrendon Cahoon2016-08-161-2/+1
| | | | | | | | | | | | The pipeliner was generating an invalid Phi name for an operand in the epilog block, which caused an assert in the live variable analysis pass. The fix is to the code that generates new Phis in the epilog block. In this case, there is an existing Phi that needs to be reused rather than creating a new Phi instruction. Differential Revision: https://reviews.llvm.org/D23513 llvm-svn: 278805
* Minor comment fix ("generate" --> "generates").Justin Lebar2016-08-121-1/+1
| | | | llvm-svn: 278578
OpenPOWER on IntegriCloud