Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 1 | //===- subzero/src/IceCfgNode.cpp - Basic block (node) implementation -----===// |
| 2 | // |
| 3 | // The Subzero Code Generator |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 9 | /// |
| 10 | /// \file |
Jim Stichnoth | 92a6e5b | 2015-12-02 16:52:44 -0800 | [diff] [blame] | 11 | /// \brief Implements the CfgNode class, including the complexities of |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 12 | /// instruction insertion and in-edge calculation. |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 13 | /// |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 14 | //===----------------------------------------------------------------------===// |
| 15 | |
John Porto | 67f8de9 | 2015-06-25 10:14:17 -0700 | [diff] [blame] | 16 | #include "IceCfgNode.h" |
| 17 | |
John Porto | aff4ccf | 2015-06-10 16:35:06 -0700 | [diff] [blame] | 18 | #include "IceAssembler.h" |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 19 | #include "IceCfg.h" |
John Porto | f8b4cc8 | 2015-06-09 18:06:19 -0700 | [diff] [blame] | 20 | #include "IceGlobalInits.h" |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 21 | #include "IceInst.h" |
John Porto | ec3f565 | 2015-08-31 15:07:09 -0700 | [diff] [blame] | 22 | #include "IceInstVarIter.h" |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 23 | #include "IceLiveness.h" |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 24 | #include "IceOperand.h" |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 25 | #include "IceTargetLowering.h" |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 26 | |
| 27 | namespace Ice { |
| 28 | |
Jim Stichnoth | 668a7a3 | 2014-12-10 15:32:25 -0800 | [diff] [blame] | 29 | CfgNode::CfgNode(Cfg *Func, SizeT LabelNumber) |
Jim Stichnoth | e7dbc0b | 2015-09-15 10:09:24 -0700 | [diff] [blame] | 30 | : Func(Func), Number(LabelNumber), LabelNumber(LabelNumber) {} |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 31 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 32 | // Returns the name the node was created with. If no name was given, it |
| 33 | // synthesizes a (hopefully) unique name. |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 34 | IceString CfgNode::getName() const { |
Jim Stichnoth | 668a7a3 | 2014-12-10 15:32:25 -0800 | [diff] [blame] | 35 | if (NameIndex >= 0) |
Jim Stichnoth | 9a04c07 | 2014-12-11 15:51:42 -0800 | [diff] [blame] | 36 | return Func->getIdentifierName(NameIndex); |
Jim Stichnoth | e7dbc0b | 2015-09-15 10:09:24 -0700 | [diff] [blame] | 37 | return "__" + std::to_string(LabelNumber); |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 38 | } |
| 39 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 40 | // Adds an instruction to either the Phi list or the regular instruction list. |
| 41 | // Validates that all Phis are added before all regular instructions. |
Jim Stichnoth | 8cfeb69 | 2016-02-05 09:50:02 -0800 | [diff] [blame] | 42 | void CfgNode::appendInst(Inst *Instr) { |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 43 | ++InstCountEstimate; |
Jim Stichnoth | 8cfeb69 | 2016-02-05 09:50:02 -0800 | [diff] [blame] | 44 | if (auto *Phi = llvm::dyn_cast<InstPhi>(Instr)) { |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 45 | if (!Insts.empty()) { |
| 46 | Func->setError("Phi instruction added to the middle of a block"); |
| 47 | return; |
| 48 | } |
| 49 | Phis.push_back(Phi); |
| 50 | } else { |
Jim Stichnoth | 8cfeb69 | 2016-02-05 09:50:02 -0800 | [diff] [blame] | 51 | Insts.push_back(Instr); |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 52 | } |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 53 | } |
| 54 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 55 | // Renumbers the non-deleted instructions in the node. This needs to be done in |
| 56 | // preparation for live range analysis. The instruction numbers in a block must |
| 57 | // be monotonically increasing. The range of instruction numbers in a block, |
| 58 | // from lowest to highest, must not overlap with the range of any other block. |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 59 | void CfgNode::renumberInstructions() { |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 60 | InstNumberT FirstNumber = Func->getNextInstNumber(); |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 61 | for (Inst &I : Phis) |
| 62 | I.renumber(Func); |
| 63 | for (Inst &I : Insts) |
| 64 | I.renumber(Func); |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 65 | InstCountEstimate = Func->getNextInstNumber() - FirstNumber; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 66 | } |
| 67 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 68 | // When a node is created, the OutEdges are immediately known, but the InEdges |
| 69 | // have to be built up incrementally. After the CFG has been constructed, the |
| 70 | // computePredecessors() pass finalizes it by creating the InEdges list. |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 71 | void CfgNode::computePredecessors() { |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 72 | for (CfgNode *Succ : OutEdges) |
| 73 | Succ->InEdges.push_back(this); |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 74 | } |
| 75 | |
Jim Stichnoth | 69d3f9c | 2015-03-23 10:33:38 -0700 | [diff] [blame] | 76 | void CfgNode::computeSuccessors() { |
| 77 | OutEdges = Insts.rbegin()->getTerminatorEdges(); |
| 78 | } |
| 79 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 80 | // Validate each Phi instruction in the node with respect to control flow. For |
| 81 | // every phi argument, its label must appear in the predecessor list. For each |
| 82 | // predecessor, there must be a phi argument with that label. We don't check |
Jim Stichnoth | 1aca230 | 2015-09-16 11:25:22 -0700 | [diff] [blame] | 83 | // that phi arguments with the same label have the same value. |
| 84 | void CfgNode::validatePhis() { |
| 85 | for (Inst &Instr : Phis) { |
| 86 | auto *Phi = llvm::cast<InstPhi>(&Instr); |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 87 | // We do a simple O(N^2) algorithm to check for consistency. Even so, it |
| 88 | // shows up as only about 0.2% of the total translation time. But if |
| 89 | // necessary, we could improve the complexity by using a hash table to |
| 90 | // count how many times each node is referenced in the Phi instruction, and |
| 91 | // how many times each node is referenced in the incoming edge list, and |
| 92 | // compare the two for equality. |
Jim Stichnoth | 1aca230 | 2015-09-16 11:25:22 -0700 | [diff] [blame] | 93 | for (SizeT i = 0; i < Phi->getSrcSize(); ++i) { |
| 94 | CfgNode *Label = Phi->getLabel(i); |
| 95 | bool Found = false; |
| 96 | for (CfgNode *InNode : getInEdges()) { |
| 97 | if (InNode == Label) { |
| 98 | Found = true; |
| 99 | break; |
| 100 | } |
| 101 | } |
| 102 | if (!Found) |
| 103 | llvm::report_fatal_error("Phi error: label for bad incoming edge"); |
| 104 | } |
| 105 | for (CfgNode *InNode : getInEdges()) { |
| 106 | bool Found = false; |
| 107 | for (SizeT i = 0; i < Phi->getSrcSize(); ++i) { |
| 108 | CfgNode *Label = Phi->getLabel(i); |
| 109 | if (InNode == Label) { |
| 110 | Found = true; |
| 111 | break; |
| 112 | } |
| 113 | } |
| 114 | if (!Found) |
| 115 | llvm::report_fatal_error("Phi error: missing label for incoming edge"); |
| 116 | } |
| 117 | } |
| 118 | } |
| 119 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 120 | // This does part 1 of Phi lowering, by creating a new dest variable for each |
| 121 | // Phi instruction, replacing the Phi instruction's dest with that variable, |
| 122 | // and adding an explicit assignment of the old dest to the new dest. For |
| 123 | // example, |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 124 | // a=phi(...) |
| 125 | // changes to |
| 126 | // "a_phi=phi(...); a=a_phi". |
| 127 | // |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 128 | // This is in preparation for part 2 which deletes the Phi instructions and |
| 129 | // appends assignment instructions to predecessor blocks. Note that this |
| 130 | // transformation preserves SSA form. |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 131 | void CfgNode::placePhiLoads() { |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 132 | for (Inst &I : Phis) { |
Jim Stichnoth | 5bff61c | 2015-10-28 09:26:00 -0700 | [diff] [blame] | 133 | auto *Phi = llvm::dyn_cast<InstPhi>(&I); |
Jim Stichnoth | 1502e59 | 2014-12-11 09:22:45 -0800 | [diff] [blame] | 134 | Insts.insert(Insts.begin(), Phi->lower(Func)); |
| 135 | } |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 136 | } |
| 137 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 138 | // This does part 2 of Phi lowering. For each Phi instruction at each out-edge, |
| 139 | // create a corresponding assignment instruction, and add all the assignments |
| 140 | // near the end of this block. They need to be added before any branch |
| 141 | // instruction, and also if the block ends with a compare instruction followed |
| 142 | // by a branch instruction that we may want to fuse, it's better to insert the |
| 143 | // new assignments before the compare instruction. The |
| 144 | // tryOptimizedCmpxchgCmpBr() method assumes this ordering of instructions. |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 145 | // |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 146 | // Note that this transformation takes the Phi dest variables out of SSA form, |
| 147 | // as there may be assignments to the dest variable in multiple blocks. |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 148 | void CfgNode::placePhiStores() { |
Jim Stichnoth | e5a5be7 | 2014-09-10 11:51:38 -0700 | [diff] [blame] | 149 | // Find the insertion point. |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 150 | InstList::iterator InsertionPoint = Insts.end(); |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 151 | // Every block must end in a terminator instruction, and therefore must have |
| 152 | // at least one instruction, so it's valid to decrement InsertionPoint (but |
| 153 | // assert just in case). |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 154 | assert(InsertionPoint != Insts.begin()); |
| 155 | --InsertionPoint; |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 156 | // Confirm that InsertionPoint is a terminator instruction. Calling |
| 157 | // getTerminatorEdges() on a non-terminator instruction will cause an |
| 158 | // llvm_unreachable(). |
Jim Stichnoth | 607e9f0 | 2014-11-06 13:32:05 -0800 | [diff] [blame] | 159 | (void)InsertionPoint->getTerminatorEdges(); |
Jim Stichnoth | e5a5be7 | 2014-09-10 11:51:38 -0700 | [diff] [blame] | 160 | // SafeInsertionPoint is always immediately before the terminator |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 161 | // instruction. If the block ends in a compare and conditional branch, it's |
| 162 | // better to place the Phi store before the compare so as not to interfere |
| 163 | // with compare/branch fusing. However, if the compare instruction's dest |
| 164 | // operand is the same as the new assignment statement's source operand, this |
| 165 | // can't be done due to data dependences, so we need to fall back to the |
| 166 | // SafeInsertionPoint. To illustrate: |
Jim Stichnoth | e5a5be7 | 2014-09-10 11:51:38 -0700 | [diff] [blame] | 167 | // ; <label>:95 |
| 168 | // %97 = load i8* %96, align 1 |
| 169 | // %98 = icmp ne i8 %97, 0 |
| 170 | // br i1 %98, label %99, label %2132 |
| 171 | // ; <label>:99 |
| 172 | // %100 = phi i8 [ %97, %95 ], [ %110, %108 ] |
| 173 | // %101 = phi i1 [ %98, %95 ], [ %111, %108 ] |
| 174 | // would be Phi-lowered as: |
| 175 | // ; <label>:95 |
| 176 | // %97 = load i8* %96, align 1 |
| 177 | // %100_phi = %97 ; can be at InsertionPoint |
| 178 | // %98 = icmp ne i8 %97, 0 |
| 179 | // %101_phi = %98 ; must be at SafeInsertionPoint |
| 180 | // br i1 %98, label %99, label %2132 |
| 181 | // ; <label>:99 |
| 182 | // %100 = %100_phi |
| 183 | // %101 = %101_phi |
| 184 | // |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 185 | // TODO(stichnot): It may be possible to bypass this whole SafeInsertionPoint |
| 186 | // mechanism. If a source basic block ends in a conditional branch: |
Jim Stichnoth | e5a5be7 | 2014-09-10 11:51:38 -0700 | [diff] [blame] | 187 | // labelSource: |
| 188 | // ... |
| 189 | // br i1 %foo, label %labelTrue, label %labelFalse |
| 190 | // and a branch target has a Phi involving the branch operand: |
| 191 | // labelTrue: |
| 192 | // %bar = phi i1 [ %foo, %labelSource ], ... |
| 193 | // then we actually know the constant i1 value of the Phi operand: |
| 194 | // labelTrue: |
| 195 | // %bar = phi i1 [ true, %labelSource ], ... |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 196 | // It seems that this optimization should be done by clang or opt, but we |
| 197 | // could also do it here. |
Jim Stichnoth | e5a5be7 | 2014-09-10 11:51:38 -0700 | [diff] [blame] | 198 | InstList::iterator SafeInsertionPoint = InsertionPoint; |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 199 | // Keep track of the dest variable of a compare instruction, so that we |
| 200 | // insert the new instruction at the SafeInsertionPoint if the compare's dest |
| 201 | // matches the Phi-lowered assignment's source. |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 202 | Variable *CmpInstDest = nullptr; |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 203 | // If the current insertion point is at a conditional branch instruction, and |
| 204 | // the previous instruction is a compare instruction, then we move the |
| 205 | // insertion point before the compare instruction so as not to interfere with |
| 206 | // compare/branch fusing. |
Jim Stichnoth | 54f3d51 | 2015-12-11 09:53:00 -0800 | [diff] [blame] | 207 | if (auto *Branch = llvm::dyn_cast<InstBr>(InsertionPoint)) { |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 208 | if (!Branch->isUnconditional()) { |
| 209 | if (InsertionPoint != Insts.begin()) { |
| 210 | --InsertionPoint; |
Jim Stichnoth | 607e9f0 | 2014-11-06 13:32:05 -0800 | [diff] [blame] | 211 | if (llvm::isa<InstIcmp>(InsertionPoint) || |
| 212 | llvm::isa<InstFcmp>(InsertionPoint)) { |
| 213 | CmpInstDest = InsertionPoint->getDest(); |
Jim Stichnoth | e5a5be7 | 2014-09-10 11:51:38 -0700 | [diff] [blame] | 214 | } else { |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 215 | ++InsertionPoint; |
| 216 | } |
| 217 | } |
| 218 | } |
| 219 | } |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 220 | |
| 221 | // Consider every out-edge. |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 222 | for (CfgNode *Succ : OutEdges) { |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 223 | // Consider every Phi instruction at the out-edge. |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 224 | for (Inst &I : Succ->Phis) { |
Jim Stichnoth | 5bff61c | 2015-10-28 09:26:00 -0700 | [diff] [blame] | 225 | auto *Phi = llvm::dyn_cast<InstPhi>(&I); |
Jim Stichnoth | 1502e59 | 2014-12-11 09:22:45 -0800 | [diff] [blame] | 226 | Operand *Operand = Phi->getOperandForTarget(this); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 227 | assert(Operand); |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 228 | Variable *Dest = I.getDest(); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 229 | assert(Dest); |
Jim Stichnoth | 54f3d51 | 2015-12-11 09:53:00 -0800 | [diff] [blame] | 230 | auto *NewInst = InstAssign::create(Func, Dest, Operand); |
Jim Stichnoth | e5a5be7 | 2014-09-10 11:51:38 -0700 | [diff] [blame] | 231 | if (CmpInstDest == Operand) |
| 232 | Insts.insert(SafeInsertionPoint, NewInst); |
| 233 | else |
| 234 | Insts.insert(InsertionPoint, NewInst); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 235 | } |
| 236 | } |
| 237 | } |
| 238 | |
| 239 | // Deletes the phi instructions after the loads and stores are placed. |
| 240 | void CfgNode::deletePhis() { |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 241 | for (Inst &I : Phis) |
| 242 | I.setDeleted(); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 243 | } |
| 244 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 245 | // Splits the edge from Pred to this node by creating a new node and hooking up |
| 246 | // the in and out edges appropriately. (The EdgeIndex parameter is only used to |
| 247 | // make the new node's name unique when there are multiple edges between the |
| 248 | // same pair of nodes.) The new node's instruction list is initialized to the |
| 249 | // empty list, with no terminator instruction. There must not be multiple edges |
| 250 | // from Pred to this node so all Inst::getTerminatorEdges implementations must |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 251 | // not contain duplicates. |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 252 | CfgNode *CfgNode::splitIncomingEdge(CfgNode *Pred, SizeT EdgeIndex) { |
Jim Stichnoth | 668a7a3 | 2014-12-10 15:32:25 -0800 | [diff] [blame] | 253 | CfgNode *NewNode = Func->makeNode(); |
Andrew Scull | aa6c109 | 2015-09-03 17:50:30 -0700 | [diff] [blame] | 254 | // Depth is the minimum as it works if both are the same, but if one is |
| 255 | // outside the loop and the other is inside, the new node should be placed |
| 256 | // outside and not be executed multiple times within the loop. |
| 257 | NewNode->setLoopNestDepth( |
| 258 | std::min(getLoopNestDepth(), Pred->getLoopNestDepth())); |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 259 | if (BuildDefs::dump()) |
Jim Stichnoth | 668a7a3 | 2014-12-10 15:32:25 -0800 | [diff] [blame] | 260 | NewNode->setName("split_" + Pred->getName() + "_" + getName() + "_" + |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 261 | std::to_string(EdgeIndex)); |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 262 | // The new node is added to the end of the node list, and will later need to |
| 263 | // be sorted into a reasonable topological order. |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 264 | NewNode->setNeedsPlacement(true); |
| 265 | // Repoint Pred's out-edge. |
| 266 | bool Found = false; |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 267 | for (CfgNode *&I : Pred->OutEdges) { |
| 268 | if (I == this) { |
| 269 | I = NewNode; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 270 | NewNode->InEdges.push_back(Pred); |
| 271 | Found = true; |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 272 | break; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 273 | } |
| 274 | } |
| 275 | assert(Found); |
Jim Stichnoth | a8d4713 | 2015-09-08 14:43:38 -0700 | [diff] [blame] | 276 | (void)Found; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 277 | // Repoint this node's in-edge. |
| 278 | Found = false; |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 279 | for (CfgNode *&I : InEdges) { |
| 280 | if (I == Pred) { |
| 281 | I = NewNode; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 282 | NewNode->OutEdges.push_back(this); |
| 283 | Found = true; |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 284 | break; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 285 | } |
| 286 | } |
| 287 | assert(Found); |
Jim Stichnoth | a8d4713 | 2015-09-08 14:43:38 -0700 | [diff] [blame] | 288 | (void)Found; |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 289 | // Repoint all suitable branch instructions' target and return. |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 290 | Found = false; |
Andrew Scull | 87f80c1 | 2015-07-20 10:19:16 -0700 | [diff] [blame] | 291 | for (Inst &I : Pred->getInsts()) |
| 292 | if (!I.isDeleted() && I.repointEdges(this, NewNode)) |
| 293 | Found = true; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 294 | assert(Found); |
Jim Stichnoth | a8d4713 | 2015-09-08 14:43:38 -0700 | [diff] [blame] | 295 | (void)Found; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 296 | return NewNode; |
| 297 | } |
| 298 | |
| 299 | namespace { |
| 300 | |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 301 | // Helpers for advancedPhiLowering(). |
| 302 | |
| 303 | class PhiDesc { |
| 304 | PhiDesc() = delete; |
| 305 | PhiDesc(const PhiDesc &) = delete; |
| 306 | PhiDesc &operator=(const PhiDesc &) = delete; |
Jim Stichnoth | c59288b | 2015-11-09 11:38:40 -0800 | [diff] [blame] | 307 | |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 308 | public: |
| 309 | PhiDesc(InstPhi *Phi, Variable *Dest) : Phi(Phi), Dest(Dest) {} |
| 310 | PhiDesc(PhiDesc &&) = default; |
| 311 | InstPhi *Phi = nullptr; |
| 312 | Variable *Dest = nullptr; |
| 313 | Operand *Src = nullptr; |
| 314 | bool Processed = false; |
| 315 | size_t NumPred = 0; // number of entries whose Src is this Dest |
| 316 | int32_t Weight = 0; // preference for topological order |
| 317 | }; |
| 318 | using PhiDescList = llvm::SmallVector<PhiDesc, 32>; |
| 319 | |
| 320 | // Always pick NumPred=0 over NumPred>0. |
| 321 | constexpr int32_t WeightNoPreds = 4; |
| 322 | // Prefer Src as a register because the register might free up. |
| 323 | constexpr int32_t WeightSrcIsReg = 2; |
| 324 | // Prefer Dest not as a register because the register stays free longer. |
| 325 | constexpr int32_t WeightDestNotReg = 1; |
| 326 | |
Jim Stichnoth | 1fb030c | 2015-10-15 11:10:38 -0700 | [diff] [blame] | 327 | bool sameVarOrReg(TargetLowering *Target, const Variable *Var1, |
| 328 | const Operand *Opnd) { |
| 329 | if (Var1 == Opnd) |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 330 | return true; |
Jim Stichnoth | 5bff61c | 2015-10-28 09:26:00 -0700 | [diff] [blame] | 331 | const auto *Var2 = llvm::dyn_cast<Variable>(Opnd); |
Jim Stichnoth | 1fb030c | 2015-10-15 11:10:38 -0700 | [diff] [blame] | 332 | if (Var2 == nullptr) |
| 333 | return false; |
| 334 | |
| 335 | // If either operand lacks a register, they cannot be the same. |
| 336 | if (!Var1->hasReg()) |
| 337 | return false; |
| 338 | if (!Var2->hasReg()) |
| 339 | return false; |
| 340 | |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 341 | const auto RegNum1 = Var1->getRegNum(); |
| 342 | const auto RegNum2 = Var2->getRegNum(); |
Jim Stichnoth | 1fb030c | 2015-10-15 11:10:38 -0700 | [diff] [blame] | 343 | // Quick common-case check. |
| 344 | if (RegNum1 == RegNum2) |
| 345 | return true; |
| 346 | |
| 347 | assert(Target->getAliasesForRegister(RegNum1)[RegNum2] == |
| 348 | Target->getAliasesForRegister(RegNum2)[RegNum1]); |
| 349 | return Target->getAliasesForRegister(RegNum1)[RegNum2]; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 350 | } |
| 351 | |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 352 | // Update NumPred for all Phi assignments using Var as their Dest variable. |
| 353 | // Also update Weight if NumPred dropped from 1 to 0. |
| 354 | void updatePreds(PhiDescList &Desc, TargetLowering *Target, Variable *Var) { |
| 355 | for (PhiDesc &Item : Desc) { |
| 356 | if (!Item.Processed && sameVarOrReg(Target, Var, Item.Dest)) { |
| 357 | if (--Item.NumPred == 0) { |
| 358 | Item.Weight += WeightNoPreds; |
| 359 | } |
| 360 | } |
| 361 | } |
| 362 | } |
| 363 | |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 364 | } // end of anonymous namespace |
| 365 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 366 | // This the "advanced" version of Phi lowering for a basic block, in contrast |
| 367 | // to the simple version that lowers through assignments involving temporaries. |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 368 | // |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 369 | // All Phi instructions in a basic block are conceptually executed in parallel. |
| 370 | // However, if we lower Phis early and commit to a sequential ordering, we may |
| 371 | // end up creating unnecessary interferences which lead to worse register |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 372 | // allocation. Delaying Phi scheduling until after register allocation can help |
| 373 | // unless there are no free registers for shuffling registers or stack slots |
| 374 | // and spilling becomes necessary. |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 375 | // |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 376 | // The advanced Phi lowering starts by finding a topological sort of the Phi |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 377 | // instructions, where "A=B" comes before "B=C" due to the anti-dependence on |
| 378 | // B. Preexisting register assignments are considered in the topological sort. |
| 379 | // If a topological sort is not possible due to a cycle, the cycle is broken by |
| 380 | // introducing a non-parallel temporary. For example, a cycle arising from a |
| 381 | // permutation like "A=B;B=C;C=A" can become "T=A;A=B;B=C;C=T". All else being |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 382 | // equal, prefer to schedule assignments with register-allocated Src operands |
| 383 | // earlier, in case that register becomes free afterwards, and prefer to |
| 384 | // schedule assignments with register-allocated Dest variables later, to keep |
| 385 | // that register free for longer. |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 386 | // |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 387 | // Once the ordering is determined, the Cfg edge is split and the assignment |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 388 | // list is lowered by the target lowering layer. Since the assignment lowering |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 389 | // may create new infinite-weight temporaries, a follow-on register allocation |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 390 | // pass will be needed. To prepare for this, liveness (including live range |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 391 | // calculation) of the split nodes needs to be calculated, and liveness of the |
| 392 | // original node need to be updated to "undo" the effects of the phi |
| 393 | // assignments. |
| 394 | |
| 395 | // The specific placement of the new node within the Cfg node list is deferred |
| 396 | // until later, including after empty node contraction. |
| 397 | // |
| 398 | // After phi assignments are lowered across all blocks, another register |
| 399 | // allocation pass is run, focusing only on pre-colored and infinite-weight |
| 400 | // variables, similar to Om1 register allocation (except without the need to |
| 401 | // specially compute these variables' live ranges, since they have already been |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 402 | // precisely calculated). The register allocator in this mode needs the ability |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 403 | // to forcibly spill and reload registers in case none are naturally available. |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 404 | void CfgNode::advancedPhiLowering() { |
| 405 | if (getPhis().empty()) |
| 406 | return; |
| 407 | |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 408 | PhiDescList Desc; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 409 | |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 410 | for (Inst &I : Phis) { |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 411 | auto *Phi = llvm::dyn_cast<InstPhi>(&I); |
| 412 | if (!Phi->isDeleted()) { |
| 413 | Variable *Dest = Phi->getDest(); |
| 414 | Desc.emplace_back(Phi, Dest); |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 415 | // Undo the effect of the phi instruction on this node's live-in set by |
| 416 | // marking the phi dest variable as live on entry. |
| 417 | SizeT VarNum = Func->getLiveness()->getLiveIndex(Dest->getIndex()); |
| 418 | assert(!Func->getLiveness()->getLiveIn(this)[VarNum]); |
| 419 | Func->getLiveness()->getLiveIn(this)[VarNum] = true; |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 420 | Phi->setDeleted(); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 421 | } |
| 422 | } |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 423 | if (Desc.empty()) |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 424 | return; |
| 425 | |
Jim Stichnoth | 1fb030c | 2015-10-15 11:10:38 -0700 | [diff] [blame] | 426 | TargetLowering *Target = Func->getTarget(); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 427 | SizeT InEdgeIndex = 0; |
| 428 | for (CfgNode *Pred : InEdges) { |
| 429 | CfgNode *Split = splitIncomingEdge(Pred, InEdgeIndex++); |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 430 | SizeT Remaining = Desc.size(); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 431 | |
| 432 | // First pass computes Src and initializes NumPred. |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 433 | for (PhiDesc &Item : Desc) { |
| 434 | Variable *Dest = Item.Dest; |
| 435 | Operand *Src = Item.Phi->getOperandForTarget(Pred); |
| 436 | Item.Src = Src; |
| 437 | Item.Processed = false; |
| 438 | Item.NumPred = 0; |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 439 | // Cherry-pick any trivial assignments, so that they don't contribute to |
| 440 | // the running complexity of the topological sort. |
Jim Stichnoth | 1fb030c | 2015-10-15 11:10:38 -0700 | [diff] [blame] | 441 | if (sameVarOrReg(Target, Dest, Src)) { |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 442 | Item.Processed = true; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 443 | --Remaining; |
| 444 | if (Dest != Src) |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 445 | // If Dest and Src are syntactically the same, don't bother adding |
| 446 | // the assignment, because in all respects it would be redundant, and |
| 447 | // if Dest/Src are on the stack, the target lowering may naively |
| 448 | // decide to lower it using a temporary register. |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 449 | Split->appendInst(InstAssign::create(Func, Dest, Src)); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 450 | } |
| 451 | } |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 452 | // Second pass computes NumPred by comparing every pair of Phi instructions. |
| 453 | for (PhiDesc &Item : Desc) { |
| 454 | if (Item.Processed) |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 455 | continue; |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 456 | const Variable *Dest = Item.Dest; |
| 457 | for (PhiDesc &Item2 : Desc) { |
| 458 | if (Item2.Processed) |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 459 | continue; |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 460 | // There shouldn't be two different Phis with the same Dest variable or |
Jim Stichnoth | c59288b | 2015-11-09 11:38:40 -0800 | [diff] [blame] | 461 | // register. |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 462 | assert((&Item == &Item2) || !sameVarOrReg(Target, Dest, Item2.Dest)); |
| 463 | if (sameVarOrReg(Target, Dest, Item2.Src)) |
| 464 | ++Item.NumPred; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 465 | } |
| 466 | } |
| 467 | |
| 468 | // Another pass to compute initial Weight values. |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 469 | for (PhiDesc &Item : Desc) { |
| 470 | if (Item.Processed) |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 471 | continue; |
| 472 | int32_t Weight = 0; |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 473 | if (Item.NumPred == 0) |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 474 | Weight += WeightNoPreds; |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 475 | if (auto *Var = llvm::dyn_cast<Variable>(Item.Src)) |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 476 | if (Var->hasReg()) |
| 477 | Weight += WeightSrcIsReg; |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 478 | if (!Item.Dest->hasReg()) |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 479 | Weight += WeightDestNotReg; |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 480 | Item.Weight = Weight; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 481 | } |
| 482 | |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 483 | // Repeatedly choose and process the best candidate in the topological sort, |
| 484 | // until no candidates remain. This implementation is O(N^2) where N is the |
| 485 | // number of Phi instructions, but with a small constant factor compared to |
| 486 | // a likely implementation of O(N) topological sort. |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 487 | for (; Remaining; --Remaining) { |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 488 | int32_t BestWeight = -1; |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 489 | PhiDesc *BestItem = nullptr; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 490 | // Find the best candidate. |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 491 | for (PhiDesc &Item : Desc) { |
| 492 | if (Item.Processed) |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 493 | continue; |
| 494 | int32_t Weight = 0; |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 495 | Weight = Item.Weight; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 496 | if (Weight > BestWeight) { |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 497 | BestItem = &Item; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 498 | BestWeight = Weight; |
| 499 | } |
| 500 | } |
| 501 | assert(BestWeight >= 0); |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 502 | assert(BestItem->NumPred <= 1); |
| 503 | Variable *Dest = BestItem->Dest; |
| 504 | Operand *Src = BestItem->Src; |
Jim Stichnoth | 1fb030c | 2015-10-15 11:10:38 -0700 | [diff] [blame] | 505 | assert(!sameVarOrReg(Target, Dest, Src)); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 506 | // Break a cycle by introducing a temporary. |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 507 | if (BestItem->NumPred) { |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 508 | bool Found = false; |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 509 | // If the target instruction "A=B" is part of a cycle, find the "X=A" |
| 510 | // assignment in the cycle because it will have to be rewritten as |
| 511 | // "X=tmp". |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 512 | for (PhiDesc &Item : Desc) { |
| 513 | if (Item.Processed) |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 514 | continue; |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 515 | Operand *OtherSrc = Item.Src; |
| 516 | if (Item.NumPred && sameVarOrReg(Target, Dest, OtherSrc)) { |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 517 | SizeT VarNum = Func->getNumVariables(); |
Jim Stichnoth | 9a04c07 | 2014-12-11 15:51:42 -0800 | [diff] [blame] | 518 | Variable *Tmp = Func->makeVariable(OtherSrc->getType()); |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 519 | if (BuildDefs::dump()) |
Jim Stichnoth | 9a04c07 | 2014-12-11 15:51:42 -0800 | [diff] [blame] | 520 | Tmp->setName(Func, "__split_" + std::to_string(VarNum)); |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 521 | Split->appendInst(InstAssign::create(Func, Tmp, OtherSrc)); |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 522 | Item.Src = Tmp; |
| 523 | updatePreds(Desc, Target, llvm::cast<Variable>(OtherSrc)); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 524 | Found = true; |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 525 | break; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 526 | } |
| 527 | } |
| 528 | assert(Found); |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 529 | (void)Found; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 530 | } |
| 531 | // Now that a cycle (if any) has been broken, create the actual |
| 532 | // assignment. |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 533 | Split->appendInst(InstAssign::create(Func, Dest, Src)); |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 534 | if (auto *Var = llvm::dyn_cast<Variable>(Src)) |
| 535 | updatePreds(Desc, Target, Var); |
| 536 | BestItem->Processed = true; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 537 | } |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 538 | Split->appendInst(InstBr::create(Func, this)); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 539 | |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 540 | Split->genCode(); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 541 | Func->getVMetadata()->addNode(Split); |
Jim Stichnoth | ea15bbe | 2015-11-09 11:19:11 -0800 | [diff] [blame] | 542 | // Validate to be safe. All items should be marked as processed, and have |
| 543 | // no predecessors. |
| 544 | if (BuildDefs::asserts()) { |
| 545 | for (PhiDesc &Item : Desc) { |
| 546 | (void)Item; |
| 547 | assert(Item.Processed); |
| 548 | assert(Item.NumPred == 0); |
| 549 | } |
| 550 | } |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 551 | } |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 552 | } |
| 553 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 554 | // Does address mode optimization. Pass each instruction to the TargetLowering |
| 555 | // object. If it returns a new instruction (representing the optimized address |
| 556 | // mode), then insert the new instruction and delete the old. |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 557 | void CfgNode::doAddressOpt() { |
| 558 | TargetLowering *Target = Func->getTarget(); |
| 559 | LoweringContext &Context = Target->getContext(); |
| 560 | Context.init(this); |
| 561 | while (!Context.atEnd()) { |
| 562 | Target->doAddressOpt(); |
| 563 | } |
| 564 | } |
| 565 | |
Qining Lu | aee5fa8 | 2015-08-20 14:59:03 -0700 | [diff] [blame] | 566 | void CfgNode::doNopInsertion(RandomNumberGenerator &RNG) { |
Matt Wala | c330274 | 2014-08-15 16:21:56 -0700 | [diff] [blame] | 567 | TargetLowering *Target = Func->getTarget(); |
| 568 | LoweringContext &Context = Target->getContext(); |
| 569 | Context.init(this); |
Qining Lu | 969f6a3 | 2015-07-31 09:58:34 -0700 | [diff] [blame] | 570 | Context.setInsertPoint(Context.getCur()); |
| 571 | // Do not insert nop in bundle locked instructions. |
| 572 | bool PauseNopInsertion = false; |
Matt Wala | c330274 | 2014-08-15 16:21:56 -0700 | [diff] [blame] | 573 | while (!Context.atEnd()) { |
Qining Lu | 969f6a3 | 2015-07-31 09:58:34 -0700 | [diff] [blame] | 574 | if (llvm::isa<InstBundleLock>(Context.getCur())) { |
| 575 | PauseNopInsertion = true; |
| 576 | } else if (llvm::isa<InstBundleUnlock>(Context.getCur())) { |
| 577 | PauseNopInsertion = false; |
| 578 | } |
| 579 | if (!PauseNopInsertion) |
Qining Lu | aee5fa8 | 2015-08-20 14:59:03 -0700 | [diff] [blame] | 580 | Target->doNopInsertion(RNG); |
Matt Wala | c330274 | 2014-08-15 16:21:56 -0700 | [diff] [blame] | 581 | // Ensure Cur=Next, so that the nops are inserted before the current |
| 582 | // instruction rather than after. |
Matt Wala | c330274 | 2014-08-15 16:21:56 -0700 | [diff] [blame] | 583 | Context.advanceCur(); |
Qining Lu | 969f6a3 | 2015-07-31 09:58:34 -0700 | [diff] [blame] | 584 | Context.advanceNext(); |
Matt Wala | c330274 | 2014-08-15 16:21:56 -0700 | [diff] [blame] | 585 | } |
Matt Wala | c330274 | 2014-08-15 16:21:56 -0700 | [diff] [blame] | 586 | } |
| 587 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 588 | // Drives the target lowering. Passes the current instruction and the next |
| 589 | // non-deleted instruction for target lowering. |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 590 | void CfgNode::genCode() { |
| 591 | TargetLowering *Target = Func->getTarget(); |
| 592 | LoweringContext &Context = Target->getContext(); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 593 | // Lower the regular instructions. |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 594 | Context.init(this); |
Jim Stichnoth | a59ae6f | 2015-05-17 10:11:41 -0700 | [diff] [blame] | 595 | Target->initNodeForLowering(this); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 596 | while (!Context.atEnd()) { |
| 597 | InstList::iterator Orig = Context.getCur(); |
| 598 | if (llvm::isa<InstRet>(*Orig)) |
| 599 | setHasReturn(); |
| 600 | Target->lower(); |
| 601 | // Ensure target lowering actually moved the cursor. |
| 602 | assert(Context.getCur() != Orig); |
| 603 | } |
Jim Stichnoth | 318f4cd | 2015-10-01 21:02:37 -0700 | [diff] [blame] | 604 | Context.availabilityReset(); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 605 | // Do preliminary lowering of the Phi instructions. |
| 606 | Target->prelowerPhis(); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 607 | } |
| 608 | |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 609 | void CfgNode::livenessLightweight() { |
| 610 | SizeT NumVars = Func->getNumVariables(); |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 611 | LivenessBV Live(NumVars); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 612 | // Process regular instructions in reverse order. |
Jim Stichnoth | 7e57136 | 2015-01-09 11:43:26 -0800 | [diff] [blame] | 613 | for (Inst &I : reverse_range(Insts)) { |
| 614 | if (I.isDeleted()) |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 615 | continue; |
Jim Stichnoth | 7e57136 | 2015-01-09 11:43:26 -0800 | [diff] [blame] | 616 | I.livenessLightweight(Func, Live); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 617 | } |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 618 | for (Inst &I : Phis) { |
| 619 | if (I.isDeleted()) |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 620 | continue; |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 621 | I.livenessLightweight(Func, Live); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 622 | } |
| 623 | } |
| 624 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 625 | // Performs liveness analysis on the block. Returns true if the incoming |
| 626 | // liveness changed from before, false if it stayed the same. (If it changes, |
| 627 | // the node's predecessors need to be processed again.) |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 628 | bool CfgNode::liveness(Liveness *Liveness) { |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame^] | 629 | const SizeT NumVars = Liveness->getNumVarsInNode(this); |
| 630 | const SizeT NumGlobalVars = Liveness->getNumGlobalVars(); |
| 631 | LivenessBV &Live = Liveness->getScratchBV(); |
| 632 | Live.clear(); |
| 633 | |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 634 | LiveBeginEndMap *LiveBegin = nullptr; |
| 635 | LiveBeginEndMap *LiveEnd = nullptr; |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 636 | // Mark the beginning and ending of each variable's live range with the |
| 637 | // sentinel instruction number 0. |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 638 | if (Liveness->getMode() == Liveness_Intervals) { |
| 639 | LiveBegin = Liveness->getLiveBegin(this); |
| 640 | LiveEnd = Liveness->getLiveEnd(this); |
| 641 | LiveBegin->clear(); |
| 642 | LiveEnd->clear(); |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 643 | // Guess that the number of live ranges beginning is roughly the number of |
| 644 | // instructions, and same for live ranges ending. |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 645 | LiveBegin->reserve(getInstCountEstimate()); |
| 646 | LiveEnd->reserve(getInstCountEstimate()); |
| 647 | } |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame^] | 648 | |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 649 | // Initialize Live to be the union of all successors' LiveIn. |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 650 | for (CfgNode *Succ : OutEdges) { |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame^] | 651 | const LivenessBV &LiveIn = Liveness->getLiveIn(Succ); |
| 652 | assert(LiveIn.empty() || LiveIn.size() == NumGlobalVars); |
| 653 | Live |= LiveIn; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 654 | // Mark corresponding argument of phis in successor as live. |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 655 | for (Inst &I : Succ->Phis) { |
Jim Stichnoth | 552490c | 2015-08-05 16:21:42 -0700 | [diff] [blame] | 656 | if (I.isDeleted()) |
| 657 | continue; |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame^] | 658 | auto *Phi = llvm::cast<InstPhi>(&I); |
Jim Stichnoth | 1502e59 | 2014-12-11 09:22:45 -0800 | [diff] [blame] | 659 | Phi->livenessPhiOperand(Live, this, Liveness); |
| 660 | } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 661 | } |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame^] | 662 | assert(Live.empty() || Live.size() == NumGlobalVars); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 663 | Liveness->getLiveOut(this) = Live; |
| 664 | |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame^] | 665 | // Expand Live so it can hold locals in addition to globals. |
| 666 | Live.resize(NumVars); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 667 | // Process regular instructions in reverse order. |
Jim Stichnoth | 7e57136 | 2015-01-09 11:43:26 -0800 | [diff] [blame] | 668 | for (Inst &I : reverse_range(Insts)) { |
| 669 | if (I.isDeleted()) |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 670 | continue; |
Jim Stichnoth | 7e57136 | 2015-01-09 11:43:26 -0800 | [diff] [blame] | 671 | I.liveness(I.getNumber(), Live, Liveness, LiveBegin, LiveEnd); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 672 | } |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 673 | // Process phis in forward order so that we can override the instruction |
| 674 | // number to be that of the earliest phi instruction in the block. |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 675 | SizeT NumNonDeadPhis = 0; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 676 | InstNumberT FirstPhiNumber = Inst::NumberSentinel; |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 677 | for (Inst &I : Phis) { |
| 678 | if (I.isDeleted()) |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 679 | continue; |
| 680 | if (FirstPhiNumber == Inst::NumberSentinel) |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 681 | FirstPhiNumber = I.getNumber(); |
| 682 | if (I.liveness(FirstPhiNumber, Live, Liveness, LiveBegin, LiveEnd)) |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 683 | ++NumNonDeadPhis; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 684 | } |
| 685 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 686 | // When using the sparse representation, after traversing the instructions in |
| 687 | // the block, the Live bitvector should only contain set bits for global |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame^] | 688 | // variables upon block entry. We validate this by testing the upper bits of |
| 689 | // the Live bitvector. |
| 690 | if (Live.find_next(NumGlobalVars) != -1) { |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 691 | if (BuildDefs::dump()) { |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 692 | // This is a fatal liveness consistency error. Print some diagnostics and |
| 693 | // abort. |
Jim Stichnoth | 69d3f9c | 2015-03-23 10:33:38 -0700 | [diff] [blame] | 694 | Ostream &Str = Func->getContext()->getStrDump(); |
| 695 | Func->resetCurrentNode(); |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame^] | 696 | Str << "Invalid Live ="; |
| 697 | for (SizeT i = NumGlobalVars; i < Live.size(); ++i) { |
| 698 | if (Live.test(i)) { |
Jim Stichnoth | 69d3f9c | 2015-03-23 10:33:38 -0700 | [diff] [blame] | 699 | Str << " "; |
| 700 | Liveness->getVariable(i, this)->dump(Func); |
| 701 | } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 702 | } |
Jim Stichnoth | 69d3f9c | 2015-03-23 10:33:38 -0700 | [diff] [blame] | 703 | Str << "\n"; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 704 | } |
Jim Stichnoth | 69d3f9c | 2015-03-23 10:33:38 -0700 | [diff] [blame] | 705 | llvm::report_fatal_error("Fatal inconsistency in liveness analysis"); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 706 | } |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame^] | 707 | // Now truncate Live to prevent LiveIn from growing. |
| 708 | Live.resize(NumGlobalVars); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 709 | |
| 710 | bool Changed = false; |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 711 | LivenessBV &LiveIn = Liveness->getLiveIn(this); |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame^] | 712 | assert(LiveIn.empty() || LiveIn.size() == NumGlobalVars); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 713 | // Add in current LiveIn |
| 714 | Live |= LiveIn; |
| 715 | // Check result, set LiveIn=Live |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 716 | SizeT &PrevNumNonDeadPhis = Liveness->getNumNonDeadPhis(this); |
| 717 | bool LiveInChanged = (Live != LiveIn); |
| 718 | Changed = (NumNonDeadPhis != PrevNumNonDeadPhis || LiveInChanged); |
| 719 | if (LiveInChanged) |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 720 | LiveIn = Live; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 721 | PrevNumNonDeadPhis = NumNonDeadPhis; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 722 | return Changed; |
| 723 | } |
| 724 | |
Jim Stichnoth | 230d410 | 2015-09-25 17:40:32 -0700 | [diff] [blame] | 725 | // Validate the integrity of the live ranges in this block. If there are any |
| 726 | // errors, it prints details and returns false. On success, it returns true. |
Jim Stichnoth | 318f4cd | 2015-10-01 21:02:37 -0700 | [diff] [blame] | 727 | bool CfgNode::livenessValidateIntervals(Liveness *Liveness) const { |
Jim Stichnoth | 230d410 | 2015-09-25 17:40:32 -0700 | [diff] [blame] | 728 | if (!BuildDefs::asserts()) |
| 729 | return true; |
| 730 | |
| 731 | // Verify there are no duplicates. |
| 732 | auto ComparePair = |
| 733 | [](const LiveBeginEndMapEntry &A, const LiveBeginEndMapEntry &B) { |
| 734 | return A.first == B.first; |
| 735 | }; |
| 736 | LiveBeginEndMap &MapBegin = *Liveness->getLiveBegin(this); |
| 737 | LiveBeginEndMap &MapEnd = *Liveness->getLiveEnd(this); |
| 738 | if (std::adjacent_find(MapBegin.begin(), MapBegin.end(), ComparePair) == |
| 739 | MapBegin.end() && |
| 740 | std::adjacent_find(MapEnd.begin(), MapEnd.end(), ComparePair) == |
| 741 | MapEnd.end()) |
| 742 | return true; |
| 743 | |
| 744 | // There is definitely a liveness error. All paths from here return false. |
| 745 | if (!BuildDefs::dump()) |
| 746 | return false; |
| 747 | |
| 748 | // Print all the errors. |
| 749 | if (BuildDefs::dump()) { |
| 750 | GlobalContext *Ctx = Func->getContext(); |
| 751 | OstreamLocker L(Ctx); |
| 752 | Ostream &Str = Ctx->getStrDump(); |
| 753 | if (Func->isVerbose()) { |
| 754 | Str << "Live range errors in the following block:\n"; |
| 755 | dump(Func); |
| 756 | } |
| 757 | for (auto Start = MapBegin.begin(); |
| 758 | (Start = std::adjacent_find(Start, MapBegin.end(), ComparePair)) != |
| 759 | MapBegin.end(); |
| 760 | ++Start) { |
| 761 | auto Next = Start + 1; |
| 762 | Str << "Duplicate LR begin, block " << getName() << ", instructions " |
| 763 | << Start->second << " & " << Next->second << ", variable " |
| 764 | << Liveness->getVariable(Start->first, this)->getName(Func) << "\n"; |
| 765 | } |
| 766 | for (auto Start = MapEnd.begin(); |
| 767 | (Start = std::adjacent_find(Start, MapEnd.end(), ComparePair)) != |
| 768 | MapEnd.end(); |
| 769 | ++Start) { |
| 770 | auto Next = Start + 1; |
| 771 | Str << "Duplicate LR end, block " << getName() << ", instructions " |
| 772 | << Start->second << " & " << Next->second << ", variable " |
| 773 | << Liveness->getVariable(Start->first, this)->getName(Func) << "\n"; |
| 774 | } |
| 775 | } |
| 776 | |
| 777 | return false; |
| 778 | } |
| 779 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 780 | // Once basic liveness is complete, compute actual live ranges. It is assumed |
| 781 | // that within a single basic block, a live range begins at most once and ends |
| 782 | // at most once. This is certainly true for pure SSA form. It is also true once |
| 783 | // phis are lowered, since each assignment to the phi-based temporary is in a |
| 784 | // different basic block, and there is a single read that ends the live in the |
| 785 | // basic block that contained the actual phi instruction. |
Jim Stichnoth | e5b73e6 | 2014-12-15 09:58:51 -0800 | [diff] [blame] | 786 | void CfgNode::livenessAddIntervals(Liveness *Liveness, InstNumberT FirstInstNum, |
| 787 | InstNumberT LastInstNum) { |
| 788 | TimerMarker T1(TimerStack::TT_liveRange, Func); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 789 | |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame^] | 790 | const SizeT NumVars = Liveness->getNumVarsInNode(this); |
| 791 | const LivenessBV &LiveIn = Liveness->getLiveIn(this); |
| 792 | const LivenessBV &LiveOut = Liveness->getLiveOut(this); |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 793 | LiveBeginEndMap &MapBegin = *Liveness->getLiveBegin(this); |
| 794 | LiveBeginEndMap &MapEnd = *Liveness->getLiveEnd(this); |
| 795 | std::sort(MapBegin.begin(), MapBegin.end()); |
| 796 | std::sort(MapEnd.begin(), MapEnd.end()); |
Jim Stichnoth | 230d410 | 2015-09-25 17:40:32 -0700 | [diff] [blame] | 797 | |
| 798 | if (!livenessValidateIntervals(Liveness)) { |
| 799 | llvm::report_fatal_error("livenessAddIntervals: Liveness error"); |
| 800 | return; |
| 801 | } |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 802 | |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame^] | 803 | LivenessBV &LiveInAndOut = Liveness->getScratchBV(); |
| 804 | LiveInAndOut = LiveIn; |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 805 | LiveInAndOut &= LiveOut; |
| 806 | |
| 807 | // Iterate in parallel across the sorted MapBegin[] and MapEnd[]. |
| 808 | auto IBB = MapBegin.begin(), IEB = MapEnd.begin(); |
| 809 | auto IBE = MapBegin.end(), IEE = MapEnd.end(); |
| 810 | while (IBB != IBE || IEB != IEE) { |
| 811 | SizeT i1 = IBB == IBE ? NumVars : IBB->first; |
| 812 | SizeT i2 = IEB == IEE ? NumVars : IEB->first; |
| 813 | SizeT i = std::min(i1, i2); |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 814 | // i1 is the Variable number of the next MapBegin entry, and i2 is the |
| 815 | // Variable number of the next MapEnd entry. If i1==i2, then the Variable's |
| 816 | // live range begins and ends in this block. If i1<i2, then i1's live range |
| 817 | // begins at instruction IBB->second and extends through the end of the |
| 818 | // block. If i1>i2, then i2's live range begins at the first instruction of |
| 819 | // the block and ends at IEB->second. In any case, we choose the lesser of |
| 820 | // i1 and i2 and proceed accordingly. |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 821 | InstNumberT LB = i == i1 ? IBB->second : FirstInstNum; |
| 822 | InstNumberT LE = i == i2 ? IEB->second : LastInstNum + 1; |
| 823 | |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 824 | Variable *Var = Liveness->getVariable(i, this); |
Jim Stichnoth | f9df452 | 2015-08-06 17:50:14 -0700 | [diff] [blame] | 825 | if (LB > LE) { |
Andrew Scull | 11c9a32 | 2015-08-28 14:24:14 -0700 | [diff] [blame] | 826 | Var->addLiveRange(FirstInstNum, LE); |
| 827 | Var->addLiveRange(LB, LastInstNum + 1); |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 828 | // Assert that Var is a global variable by checking that its liveness |
| 829 | // index is less than the number of globals. This ensures that the |
| 830 | // LiveInAndOut[] access is valid. |
Jim Stichnoth | f9df452 | 2015-08-06 17:50:14 -0700 | [diff] [blame] | 831 | assert(i < Liveness->getNumGlobalVars()); |
| 832 | LiveInAndOut[i] = false; |
| 833 | } else { |
Andrew Scull | 11c9a32 | 2015-08-28 14:24:14 -0700 | [diff] [blame] | 834 | Var->addLiveRange(LB, LE); |
Jim Stichnoth | 4775255 | 2014-10-13 17:15:08 -0700 | [diff] [blame] | 835 | } |
| 836 | if (i == i1) |
| 837 | ++IBB; |
| 838 | if (i == i2) |
| 839 | ++IEB; |
| 840 | } |
| 841 | // Process the variables that are live across the entire block. |
| 842 | for (int i = LiveInAndOut.find_first(); i != -1; |
| 843 | i = LiveInAndOut.find_next(i)) { |
| 844 | Variable *Var = Liveness->getVariable(i, this); |
Jim Stichnoth | 552490c | 2015-08-05 16:21:42 -0700 | [diff] [blame] | 845 | if (Liveness->getRangeMask(Var->getIndex())) |
Andrew Scull | 11c9a32 | 2015-08-28 14:24:14 -0700 | [diff] [blame] | 846 | Var->addLiveRange(FirstInstNum, LastInstNum + 1); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 847 | } |
| 848 | } |
| 849 | |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 850 | // If this node contains only deleted instructions, and ends in an |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 851 | // unconditional branch, contract the node by repointing all its in-edges to |
| 852 | // its successor. |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 853 | void CfgNode::contractIfEmpty() { |
Jim Stichnoth | bfb410d | 2014-11-05 16:04:05 -0800 | [diff] [blame] | 854 | if (InEdges.empty()) |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 855 | return; |
Jim Stichnoth | ae95320 | 2014-12-20 06:17:49 -0800 | [diff] [blame] | 856 | Inst *Branch = nullptr; |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 857 | for (Inst &I : Insts) { |
| 858 | if (I.isDeleted()) |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 859 | continue; |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 860 | if (I.isUnconditionalBranch()) |
| 861 | Branch = &I; |
| 862 | else if (!I.isRedundantAssign()) |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 863 | return; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 864 | } |
Jim Stichnoth | 6f7ad6c | 2016-01-15 09:52:54 -0800 | [diff] [blame] | 865 | // Make sure there is actually a successor to repoint in-edges to. |
| 866 | if (OutEdges.empty()) |
| 867 | return; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 868 | assert(OutEdges.size() == 1); |
Jim Stichnoth | 1921fba | 2015-09-15 10:06:30 -0700 | [diff] [blame] | 869 | // Don't try to delete a self-loop. |
| 870 | if (OutEdges[0] == this) |
| 871 | return; |
Jim Stichnoth | 6f7ad6c | 2016-01-15 09:52:54 -0800 | [diff] [blame] | 872 | // Make sure the node actually contains (ends with) an unconditional branch. |
| 873 | if (Branch == nullptr) |
| 874 | return; |
Jim Stichnoth | 1921fba | 2015-09-15 10:06:30 -0700 | [diff] [blame] | 875 | |
| 876 | Branch->setDeleted(); |
Andrew Scull | 713278a | 2015-07-22 17:17:02 -0700 | [diff] [blame] | 877 | CfgNode *Successor = OutEdges.front(); |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 878 | // Repoint all this node's in-edges to this node's successor, unless this |
| 879 | // node's successor is actually itself (in which case the statement |
| 880 | // "OutEdges.front()->InEdges.push_back(Pred)" could invalidate the iterator |
| 881 | // over this->InEdges). |
Andrew Scull | 713278a | 2015-07-22 17:17:02 -0700 | [diff] [blame] | 882 | if (Successor != this) { |
Jim Stichnoth | bfb410d | 2014-11-05 16:04:05 -0800 | [diff] [blame] | 883 | for (CfgNode *Pred : InEdges) { |
Andrew Scull | 713278a | 2015-07-22 17:17:02 -0700 | [diff] [blame] | 884 | for (CfgNode *&I : Pred->OutEdges) { |
| 885 | if (I == this) { |
| 886 | I = Successor; |
| 887 | Successor->InEdges.push_back(Pred); |
Jim Stichnoth | bfb410d | 2014-11-05 16:04:05 -0800 | [diff] [blame] | 888 | } |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 889 | } |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 890 | for (Inst &I : Pred->getInsts()) { |
| 891 | if (!I.isDeleted()) |
Andrew Scull | 713278a | 2015-07-22 17:17:02 -0700 | [diff] [blame] | 892 | I.repointEdges(this, Successor); |
Jim Stichnoth | bfb410d | 2014-11-05 16:04:05 -0800 | [diff] [blame] | 893 | } |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 894 | } |
Andrew Scull | 713278a | 2015-07-22 17:17:02 -0700 | [diff] [blame] | 895 | |
| 896 | // Remove the in-edge to the successor to allow node reordering to make |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 897 | // better decisions. For example it's more helpful to place a node after a |
| 898 | // reachable predecessor than an unreachable one (like the one we just |
Andrew Scull | 713278a | 2015-07-22 17:17:02 -0700 | [diff] [blame] | 899 | // contracted). |
| 900 | Successor->InEdges.erase( |
| 901 | std::find(Successor->InEdges.begin(), Successor->InEdges.end(), this)); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 902 | } |
| 903 | InEdges.clear(); |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 904 | } |
| 905 | |
Jim Stichnoth | ff9c706 | 2014-09-18 04:50:49 -0700 | [diff] [blame] | 906 | void CfgNode::doBranchOpt(const CfgNode *NextNode) { |
| 907 | TargetLowering *Target = Func->getTarget(); |
Andrew Scull | 713278a | 2015-07-22 17:17:02 -0700 | [diff] [blame] | 908 | // Find the first opportunity for branch optimization (which will be the last |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 909 | // instruction in the block) and stop. This is sufficient unless there is |
| 910 | // some target lowering where we have the possibility of multiple |
| 911 | // optimizations per block. Take care with switch lowering as there are |
| 912 | // multiple unconditional branches and only the last can be deleted. |
Andrew Scull | 713278a | 2015-07-22 17:17:02 -0700 | [diff] [blame] | 913 | for (Inst &I : reverse_range(Insts)) { |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 914 | if (!I.isDeleted()) { |
| 915 | Target->doBranchOpt(&I, NextNode); |
Andrew Scull | 713278a | 2015-07-22 17:17:02 -0700 | [diff] [blame] | 916 | return; |
Jim Stichnoth | 336f6c4 | 2014-10-30 15:01:31 -0700 | [diff] [blame] | 917 | } |
| 918 | } |
Jim Stichnoth | ff9c706 | 2014-09-18 04:50:49 -0700 | [diff] [blame] | 919 | } |
| 920 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 921 | // ======================== Dump routines ======================== // |
| 922 | |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 923 | namespace { |
| 924 | |
| 925 | // Helper functions for emit(). |
| 926 | |
| 927 | void emitRegisterUsage(Ostream &Str, const Cfg *Func, const CfgNode *Node, |
Andrew Scull | 00741a0 | 2015-09-16 19:04:09 -0700 | [diff] [blame] | 928 | bool IsLiveIn, CfgVector<SizeT> &LiveRegCount) { |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 929 | if (!BuildDefs::dump()) |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 930 | return; |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 931 | Liveness *Liveness = Func->getLiveness(); |
| 932 | const LivenessBV *Live; |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 933 | const auto StackReg = Func->getTarget()->getStackReg(); |
| 934 | const auto FrameOrStackReg = Func->getTarget()->getFrameOrStackReg(); |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 935 | if (IsLiveIn) { |
| 936 | Live = &Liveness->getLiveIn(Node); |
Jim Stichnoth | 751e27e | 2015-12-16 12:40:31 -0800 | [diff] [blame] | 937 | Str << "\t\t\t\t/* LiveIn="; |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 938 | } else { |
| 939 | Live = &Liveness->getLiveOut(Node); |
Jim Stichnoth | 751e27e | 2015-12-16 12:40:31 -0800 | [diff] [blame] | 940 | Str << "\t\t\t\t/* LiveOut="; |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 941 | } |
| 942 | if (!Live->empty()) { |
Andrew Scull | 00741a0 | 2015-09-16 19:04:09 -0700 | [diff] [blame] | 943 | CfgVector<Variable *> LiveRegs; |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 944 | for (SizeT i = 0; i < Live->size(); ++i) { |
Jim Stichnoth | e741871 | 2015-10-09 06:54:02 -0700 | [diff] [blame] | 945 | if (!(*Live)[i]) |
| 946 | continue; |
| 947 | Variable *Var = Liveness->getVariable(i, Node); |
| 948 | if (!Var->hasReg()) |
| 949 | continue; |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 950 | const auto RegNum = Var->getRegNum(); |
Jim Stichnoth | e741871 | 2015-10-09 06:54:02 -0700 | [diff] [blame] | 951 | if (RegNum == StackReg || RegNum == FrameOrStackReg) |
| 952 | continue; |
| 953 | if (IsLiveIn) |
| 954 | ++LiveRegCount[RegNum]; |
| 955 | LiveRegs.push_back(Var); |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 956 | } |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 957 | // Sort the variables by regnum so they are always printed in a familiar |
| 958 | // order. |
Jim Stichnoth | 9a05aea | 2015-05-26 16:01:23 -0700 | [diff] [blame] | 959 | std::sort(LiveRegs.begin(), LiveRegs.end(), |
| 960 | [](const Variable *V1, const Variable *V2) { |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 961 | return unsigned(V1->getRegNum()) < unsigned(V2->getRegNum()); |
Jim Stichnoth | 8e6bf6e | 2015-06-03 15:58:12 -0700 | [diff] [blame] | 962 | }); |
Jim Stichnoth | 9a05aea | 2015-05-26 16:01:23 -0700 | [diff] [blame] | 963 | bool First = true; |
| 964 | for (Variable *Var : LiveRegs) { |
| 965 | if (!First) |
| 966 | Str << ","; |
| 967 | First = false; |
| 968 | Var->emit(Func); |
| 969 | } |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 970 | } |
Jim Stichnoth | 751e27e | 2015-12-16 12:40:31 -0800 | [diff] [blame] | 971 | Str << " */\n"; |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 972 | } |
| 973 | |
Jim Stichnoth | 3e859b7 | 2015-11-10 14:39:51 -0800 | [diff] [blame] | 974 | /// Returns true if some text was emitted - in which case the caller definitely |
| 975 | /// needs to emit a newline character. |
| 976 | bool emitLiveRangesEnded(Ostream &Str, const Cfg *Func, const Inst *Instr, |
Andrew Scull | 00741a0 | 2015-09-16 19:04:09 -0700 | [diff] [blame] | 977 | CfgVector<SizeT> &LiveRegCount) { |
Jim Stichnoth | 3e859b7 | 2015-11-10 14:39:51 -0800 | [diff] [blame] | 978 | bool Printed = false; |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 979 | if (!BuildDefs::dump()) |
Jim Stichnoth | 3e859b7 | 2015-11-10 14:39:51 -0800 | [diff] [blame] | 980 | return Printed; |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 981 | Variable *Dest = Instr->getDest(); |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 982 | // Normally we increment the live count for the dest register. But we |
Jim Stichnoth | 230d410 | 2015-09-25 17:40:32 -0700 | [diff] [blame] | 983 | // shouldn't if the instruction's IsDestRedefined flag is set, because this |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 984 | // means that the target lowering created this instruction as a non-SSA |
| 985 | // assignment; i.e., a different, previous instruction started the dest |
| 986 | // variable's live range. |
Jim Stichnoth | 230d410 | 2015-09-25 17:40:32 -0700 | [diff] [blame] | 987 | if (!Instr->isDestRedefined() && Dest && Dest->hasReg()) |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 988 | ++LiveRegCount[Dest->getRegNum()]; |
John Porto | ec3f565 | 2015-08-31 15:07:09 -0700 | [diff] [blame] | 989 | FOREACH_VAR_IN_INST(Var, *Instr) { |
| 990 | bool ShouldReport = Instr->isLastUse(Var); |
| 991 | if (ShouldReport && Var->hasReg()) { |
| 992 | // Don't report end of live range until the live count reaches 0. |
| 993 | SizeT NewCount = --LiveRegCount[Var->getRegNum()]; |
| 994 | if (NewCount) |
| 995 | ShouldReport = false; |
| 996 | } |
| 997 | if (ShouldReport) { |
Jim Stichnoth | 3e859b7 | 2015-11-10 14:39:51 -0800 | [diff] [blame] | 998 | if (Printed) |
John Porto | ec3f565 | 2015-08-31 15:07:09 -0700 | [diff] [blame] | 999 | Str << ","; |
Jim Stichnoth | 3e859b7 | 2015-11-10 14:39:51 -0800 | [diff] [blame] | 1000 | else |
Jim Stichnoth | 751e27e | 2015-12-16 12:40:31 -0800 | [diff] [blame] | 1001 | Str << " \t/* END="; |
John Porto | ec3f565 | 2015-08-31 15:07:09 -0700 | [diff] [blame] | 1002 | Var->emit(Func); |
Jim Stichnoth | 3e859b7 | 2015-11-10 14:39:51 -0800 | [diff] [blame] | 1003 | Printed = true; |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 1004 | } |
| 1005 | } |
Jim Stichnoth | 751e27e | 2015-12-16 12:40:31 -0800 | [diff] [blame] | 1006 | if (Printed) |
| 1007 | Str << " */"; |
Jim Stichnoth | 3e859b7 | 2015-11-10 14:39:51 -0800 | [diff] [blame] | 1008 | return Printed; |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 1009 | } |
| 1010 | |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 1011 | void updateStats(Cfg *Func, const Inst *I) { |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 1012 | if (!BuildDefs::dump()) |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1013 | return; |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1014 | // Update emitted instruction count, plus fill/spill count for Variable |
| 1015 | // operands without a physical register. |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 1016 | if (uint32_t Count = I->getEmitInstCount()) { |
| 1017 | Func->getContext()->statsUpdateEmitted(Count); |
| 1018 | if (Variable *Dest = I->getDest()) { |
| 1019 | if (!Dest->hasReg()) |
| 1020 | Func->getContext()->statsUpdateFills(); |
| 1021 | } |
| 1022 | for (SizeT S = 0; S < I->getSrcSize(); ++S) { |
Jim Stichnoth | 54f3d51 | 2015-12-11 09:53:00 -0800 | [diff] [blame] | 1023 | if (auto *Src = llvm::dyn_cast<Variable>(I->getSrc(S))) { |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 1024 | if (!Src->hasReg()) |
| 1025 | Func->getContext()->statsUpdateSpills(); |
| 1026 | } |
| 1027 | } |
| 1028 | } |
| 1029 | } |
| 1030 | |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 1031 | } // end of anonymous namespace |
| 1032 | |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 1033 | void CfgNode::emit(Cfg *Func) const { |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 1034 | if (!BuildDefs::dump()) |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 1035 | return; |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 1036 | Func->setCurrentNode(this); |
| 1037 | Ostream &Str = Func->getContext()->getStrEmit(); |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 1038 | Liveness *Liveness = Func->getLiveness(); |
Jim Stichnoth | 238b4c1 | 2015-10-01 07:46:38 -0700 | [diff] [blame] | 1039 | const bool DecorateAsm = |
Karl Schimpf | df80eb8 | 2015-02-09 14:20:22 -0800 | [diff] [blame] | 1040 | Liveness && Func->getContext()->getFlags().getDecorateAsm(); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 1041 | Str << getAsmName() << ":\n"; |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1042 | // LiveRegCount keeps track of the number of currently live variables that |
| 1043 | // each register is assigned to. Normally that would be only 0 or 1, but the |
| 1044 | // register allocator's AllowOverlap inference allows it to be greater than 1 |
| 1045 | // for short periods. |
Andrew Scull | 00741a0 | 2015-09-16 19:04:09 -0700 | [diff] [blame] | 1046 | CfgVector<SizeT> LiveRegCount(Func->getTarget()->getNumRegisters()); |
Jim Stichnoth | 4175b2a | 2015-04-30 12:26:22 -0700 | [diff] [blame] | 1047 | if (DecorateAsm) { |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 1048 | constexpr bool IsLiveIn = true; |
Jim Stichnoth | 4175b2a | 2015-04-30 12:26:22 -0700 | [diff] [blame] | 1049 | emitRegisterUsage(Str, Func, this, IsLiveIn, LiveRegCount); |
Jim Stichnoth | 238b4c1 | 2015-10-01 07:46:38 -0700 | [diff] [blame] | 1050 | if (getInEdges().size()) { |
Jim Stichnoth | 751e27e | 2015-12-16 12:40:31 -0800 | [diff] [blame] | 1051 | Str << "\t\t\t\t/* preds="; |
Jim Stichnoth | 238b4c1 | 2015-10-01 07:46:38 -0700 | [diff] [blame] | 1052 | bool First = true; |
| 1053 | for (CfgNode *I : getInEdges()) { |
| 1054 | if (!First) |
| 1055 | Str << ","; |
| 1056 | First = false; |
Jim Stichnoth | 9a63bab | 2015-10-05 11:13:59 -0700 | [diff] [blame] | 1057 | Str << "$" << I->getName(); |
Jim Stichnoth | 238b4c1 | 2015-10-01 07:46:38 -0700 | [diff] [blame] | 1058 | } |
Jim Stichnoth | 751e27e | 2015-12-16 12:40:31 -0800 | [diff] [blame] | 1059 | Str << " */\n"; |
Jim Stichnoth | 238b4c1 | 2015-10-01 07:46:38 -0700 | [diff] [blame] | 1060 | } |
| 1061 | if (getLoopNestDepth()) { |
Jim Stichnoth | 751e27e | 2015-12-16 12:40:31 -0800 | [diff] [blame] | 1062 | Str << "\t\t\t\t/* loop depth=" << getLoopNestDepth() << " */\n"; |
Jim Stichnoth | 238b4c1 | 2015-10-01 07:46:38 -0700 | [diff] [blame] | 1063 | } |
Jim Stichnoth | 4175b2a | 2015-04-30 12:26:22 -0700 | [diff] [blame] | 1064 | } |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 1065 | |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 1066 | for (const Inst &I : Phis) { |
| 1067 | if (I.isDeleted()) |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 1068 | continue; |
| 1069 | // Emitting a Phi instruction should cause an error. |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 1070 | I.emit(Func); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 1071 | } |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 1072 | for (const Inst &I : Insts) { |
| 1073 | if (I.isDeleted()) |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 1074 | continue; |
Jim Stichnoth | b82baf2 | 2015-05-27 10:41:07 -0700 | [diff] [blame] | 1075 | if (I.isRedundantAssign()) { |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1076 | // Usually, redundant assignments end the live range of the src variable |
| 1077 | // and begin the live range of the dest variable, with no net effect on |
| 1078 | // the liveness of their register. However, if the register allocator |
| 1079 | // infers the AllowOverlap condition, then this may be a redundant |
| 1080 | // assignment that does not end the src variable's live range, in which |
| 1081 | // case the active variable count for that register needs to be bumped. |
| 1082 | // That normally would have happened as part of emitLiveRangesEnded(), |
| 1083 | // but that isn't called for redundant assignments. |
Jim Stichnoth | b82baf2 | 2015-05-27 10:41:07 -0700 | [diff] [blame] | 1084 | Variable *Dest = I.getDest(); |
Jim Stichnoth | 1fb030c | 2015-10-15 11:10:38 -0700 | [diff] [blame] | 1085 | if (DecorateAsm && Dest->hasReg()) { |
Jim Stichnoth | b82baf2 | 2015-05-27 10:41:07 -0700 | [diff] [blame] | 1086 | ++LiveRegCount[Dest->getRegNum()]; |
Jim Stichnoth | 1fb030c | 2015-10-15 11:10:38 -0700 | [diff] [blame] | 1087 | if (I.isLastUse(I.getSrc(0))) |
| 1088 | --LiveRegCount[llvm::cast<Variable>(I.getSrc(0))->getRegNum()]; |
| 1089 | } |
Jim Stichnoth | 3d44fe8 | 2014-11-01 10:10:18 -0700 | [diff] [blame] | 1090 | continue; |
Jim Stichnoth | b82baf2 | 2015-05-27 10:41:07 -0700 | [diff] [blame] | 1091 | } |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 1092 | I.emit(Func); |
Jim Stichnoth | 3e859b7 | 2015-11-10 14:39:51 -0800 | [diff] [blame] | 1093 | bool Printed = false; |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 1094 | if (DecorateAsm) |
Jim Stichnoth | 3e859b7 | 2015-11-10 14:39:51 -0800 | [diff] [blame] | 1095 | Printed = emitLiveRangesEnded(Str, Func, &I, LiveRegCount); |
| 1096 | if (Printed || llvm::isa<InstTarget>(&I)) |
| 1097 | Str << "\n"; |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 1098 | updateStats(Func, &I); |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 1099 | } |
Jim Stichnoth | 4175b2a | 2015-04-30 12:26:22 -0700 | [diff] [blame] | 1100 | if (DecorateAsm) { |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 1101 | constexpr bool IsLiveIn = false; |
Jim Stichnoth | 4175b2a | 2015-04-30 12:26:22 -0700 | [diff] [blame] | 1102 | emitRegisterUsage(Str, Func, this, IsLiveIn, LiveRegCount); |
| 1103 | } |
Jim Stichnoth | 5bc2b1d | 2014-05-22 13:38:48 -0700 | [diff] [blame] | 1104 | } |
| 1105 | |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1106 | // Helper class for emitIAS(). |
| 1107 | namespace { |
| 1108 | class BundleEmitHelper { |
| 1109 | BundleEmitHelper() = delete; |
| 1110 | BundleEmitHelper(const BundleEmitHelper &) = delete; |
| 1111 | BundleEmitHelper &operator=(const BundleEmitHelper &) = delete; |
| 1112 | |
| 1113 | public: |
David Sehr | 26217e3 | 2015-11-26 13:03:50 -0800 | [diff] [blame] | 1114 | BundleEmitHelper(Assembler *Asm, const InstList &Insts) |
| 1115 | : Asm(Asm), End(Insts.end()), BundleLockStart(End), |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1116 | BundleSize(1 << Asm->getBundleAlignLog2Bytes()), |
Jim Stichnoth | eafb56c | 2015-06-22 10:35:22 -0700 | [diff] [blame] | 1117 | BundleMaskLo(BundleSize - 1), BundleMaskHi(~BundleMaskLo) {} |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1118 | // Check whether we're currently within a bundle_lock region. |
| 1119 | bool isInBundleLockRegion() const { return BundleLockStart != End; } |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1120 | // Check whether the current bundle_lock region has the align_to_end option. |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1121 | bool isAlignToEnd() const { |
| 1122 | assert(isInBundleLockRegion()); |
| 1123 | return llvm::cast<InstBundleLock>(getBundleLockStart())->getOption() == |
| 1124 | InstBundleLock::Opt_AlignToEnd; |
| 1125 | } |
John Porto | 56958cb | 2016-01-14 09:18:18 -0800 | [diff] [blame] | 1126 | bool isPadToEnd() const { |
| 1127 | assert(isInBundleLockRegion()); |
| 1128 | return llvm::cast<InstBundleLock>(getBundleLockStart())->getOption() == |
| 1129 | InstBundleLock::Opt_PadToEnd; |
| 1130 | } |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1131 | // Check whether the entire bundle_lock region falls within the same bundle. |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1132 | bool isSameBundle() const { |
| 1133 | assert(isInBundleLockRegion()); |
| 1134 | return SizeSnapshotPre == SizeSnapshotPost || |
| 1135 | (SizeSnapshotPre & BundleMaskHi) == |
| 1136 | ((SizeSnapshotPost - 1) & BundleMaskHi); |
| 1137 | } |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1138 | // Get the bundle alignment of the first instruction of the bundle_lock |
| 1139 | // region. |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1140 | intptr_t getPreAlignment() const { |
| 1141 | assert(isInBundleLockRegion()); |
| 1142 | return SizeSnapshotPre & BundleMaskLo; |
| 1143 | } |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1144 | // Get the bundle alignment of the first instruction past the bundle_lock |
| 1145 | // region. |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1146 | intptr_t getPostAlignment() const { |
| 1147 | assert(isInBundleLockRegion()); |
| 1148 | return SizeSnapshotPost & BundleMaskLo; |
| 1149 | } |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1150 | // Get the iterator pointing to the bundle_lock instruction, e.g. to roll |
| 1151 | // back the instruction iteration to that point. |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1152 | InstList::const_iterator getBundleLockStart() const { |
| 1153 | assert(isInBundleLockRegion()); |
| 1154 | return BundleLockStart; |
| 1155 | } |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1156 | // Set up bookkeeping when the bundle_lock instruction is first processed. |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1157 | void enterBundleLock(InstList::const_iterator I) { |
| 1158 | assert(!isInBundleLockRegion()); |
| 1159 | BundleLockStart = I; |
| 1160 | SizeSnapshotPre = Asm->getBufferSize(); |
| 1161 | Asm->setPreliminary(true); |
| 1162 | assert(isInBundleLockRegion()); |
| 1163 | } |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1164 | // Update bookkeeping when the bundle_unlock instruction is processed. |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1165 | void enterBundleUnlock() { |
| 1166 | assert(isInBundleLockRegion()); |
| 1167 | SizeSnapshotPost = Asm->getBufferSize(); |
| 1168 | } |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1169 | // Update bookkeeping when we are completely finished with the bundle_lock |
| 1170 | // region. |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1171 | void leaveBundleLockRegion() { BundleLockStart = End; } |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1172 | // Check whether the instruction sequence fits within the current bundle, and |
| 1173 | // if not, add nop padding to the end of the current bundle. |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1174 | void padToNextBundle() { |
| 1175 | assert(isInBundleLockRegion()); |
| 1176 | if (!isSameBundle()) { |
| 1177 | intptr_t PadToNextBundle = BundleSize - getPreAlignment(); |
| 1178 | Asm->padWithNop(PadToNextBundle); |
| 1179 | SizeSnapshotPre += PadToNextBundle; |
| 1180 | SizeSnapshotPost += PadToNextBundle; |
| 1181 | assert((Asm->getBufferSize() & BundleMaskLo) == 0); |
| 1182 | assert(Asm->getBufferSize() == SizeSnapshotPre); |
| 1183 | } |
| 1184 | } |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1185 | // If align_to_end is specified, add padding such that the instruction |
| 1186 | // sequences ends precisely at a bundle boundary. |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1187 | void padForAlignToEnd() { |
| 1188 | assert(isInBundleLockRegion()); |
| 1189 | if (isAlignToEnd()) { |
| 1190 | if (intptr_t Offset = getPostAlignment()) { |
| 1191 | Asm->padWithNop(BundleSize - Offset); |
| 1192 | SizeSnapshotPre = Asm->getBufferSize(); |
| 1193 | } |
| 1194 | } |
| 1195 | } |
John Porto | 56958cb | 2016-01-14 09:18:18 -0800 | [diff] [blame] | 1196 | // If pad_to_end is specified, add padding such that the first instruction |
| 1197 | // after the instruction sequence starts at a bundle boundary. |
| 1198 | void padForPadToEnd() { |
| 1199 | assert(isInBundleLockRegion()); |
| 1200 | if (isPadToEnd()) { |
| 1201 | if (intptr_t Offset = getPostAlignment()) { |
| 1202 | Asm->padWithNop(BundleSize - Offset); |
| 1203 | SizeSnapshotPre = Asm->getBufferSize(); |
| 1204 | } |
| 1205 | } |
| 1206 | } // Update bookkeeping when rolling back for the second pass. |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1207 | void rollback() { |
| 1208 | assert(isInBundleLockRegion()); |
| 1209 | Asm->setBufferSize(SizeSnapshotPre); |
| 1210 | Asm->setPreliminary(false); |
| 1211 | } |
| 1212 | |
| 1213 | private: |
| 1214 | Assembler *const Asm; |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1215 | // End is a sentinel value such that BundleLockStart==End implies that we are |
| 1216 | // not in a bundle_lock region. |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1217 | const InstList::const_iterator End; |
| 1218 | InstList::const_iterator BundleLockStart; |
| 1219 | const intptr_t BundleSize; |
| 1220 | // Masking with BundleMaskLo identifies an address's bundle offset. |
| 1221 | const intptr_t BundleMaskLo; |
| 1222 | // Masking with BundleMaskHi identifies an address's bundle. |
| 1223 | const intptr_t BundleMaskHi; |
Jim Stichnoth | eafb56c | 2015-06-22 10:35:22 -0700 | [diff] [blame] | 1224 | intptr_t SizeSnapshotPre = 0; |
| 1225 | intptr_t SizeSnapshotPost = 0; |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1226 | }; |
| 1227 | |
| 1228 | } // end of anonymous namespace |
| 1229 | |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 1230 | void CfgNode::emitIAS(Cfg *Func) const { |
| 1231 | Func->setCurrentNode(this); |
Jim Stichnoth | bbca754 | 2015-02-11 16:08:31 -0800 | [diff] [blame] | 1232 | Assembler *Asm = Func->getAssembler<>(); |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1233 | // TODO(stichnot): When sandboxing, defer binding the node label until just |
| 1234 | // before the first instruction is emitted, to reduce the chance that a |
| 1235 | // padding nop is a branch target. |
Karl Schimpf | 50a3331 | 2015-10-23 09:19:48 -0700 | [diff] [blame] | 1236 | Asm->bindCfgNodeLabel(this); |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 1237 | for (const Inst &I : Phis) { |
| 1238 | if (I.isDeleted()) |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 1239 | continue; |
| 1240 | // Emitting a Phi instruction should cause an error. |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 1241 | I.emitIAS(Func); |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 1242 | } |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1243 | |
| 1244 | // Do the simple emission if not sandboxed. |
| 1245 | if (!Func->getContext()->getFlags().getUseSandboxing()) { |
| 1246 | for (const Inst &I : Insts) { |
| 1247 | if (!I.isDeleted() && !I.isRedundantAssign()) { |
| 1248 | I.emitIAS(Func); |
| 1249 | updateStats(Func, &I); |
| 1250 | } |
| 1251 | } |
| 1252 | return; |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 1253 | } |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1254 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1255 | // The remainder of the function handles emission with sandboxing. There are |
| 1256 | // explicit bundle_lock regions delimited by bundle_lock and bundle_unlock |
| 1257 | // instructions. All other instructions are treated as an implicit |
| 1258 | // one-instruction bundle_lock region. Emission is done twice for each |
| 1259 | // bundle_lock region. The first pass is a preliminary pass, after which we |
| 1260 | // can figure out what nop padding is needed, then roll back, and make the |
| 1261 | // final pass. |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1262 | // |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1263 | // Ideally, the first pass would be speculative and the second pass would |
| 1264 | // only be done if nop padding were needed, but the structure of the |
| 1265 | // integrated assembler makes it hard to roll back the state of label |
| 1266 | // bindings, label links, and relocation fixups. Instead, the first pass just |
| 1267 | // disables all mutation of that state. |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1268 | |
David Sehr | 26217e3 | 2015-11-26 13:03:50 -0800 | [diff] [blame] | 1269 | BundleEmitHelper Helper(Asm, Insts); |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1270 | InstList::const_iterator End = Insts.end(); |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1271 | // Retrying indicates that we had to roll back to the bundle_lock instruction |
| 1272 | // to apply padding before the bundle_lock sequence. |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1273 | bool Retrying = false; |
| 1274 | for (InstList::const_iterator I = Insts.begin(); I != End; ++I) { |
| 1275 | if (I->isDeleted() || I->isRedundantAssign()) |
| 1276 | continue; |
| 1277 | |
| 1278 | if (llvm::isa<InstBundleLock>(I)) { |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1279 | // Set up the initial bundle_lock state. This should not happen while |
| 1280 | // retrying, because the retry rolls back to the instruction following |
| 1281 | // the bundle_lock instruction. |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1282 | assert(!Retrying); |
| 1283 | Helper.enterBundleLock(I); |
| 1284 | continue; |
| 1285 | } |
| 1286 | |
| 1287 | if (llvm::isa<InstBundleUnlock>(I)) { |
| 1288 | Helper.enterBundleUnlock(); |
| 1289 | if (Retrying) { |
| 1290 | // Make sure all instructions are in the same bundle. |
| 1291 | assert(Helper.isSameBundle()); |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1292 | // If align_to_end is specified, make sure the next instruction begins |
| 1293 | // the bundle. |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1294 | assert(!Helper.isAlignToEnd() || Helper.getPostAlignment() == 0); |
John Porto | 56958cb | 2016-01-14 09:18:18 -0800 | [diff] [blame] | 1295 | Helper.padForPadToEnd(); |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1296 | Helper.leaveBundleLockRegion(); |
| 1297 | Retrying = false; |
| 1298 | } else { |
| 1299 | // This is the first pass, so roll back for the retry pass. |
| 1300 | Helper.rollback(); |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1301 | // Pad to the next bundle if the instruction sequence crossed a bundle |
| 1302 | // boundary. |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1303 | Helper.padToNextBundle(); |
| 1304 | // Insert additional padding to make AlignToEnd work. |
| 1305 | Helper.padForAlignToEnd(); |
| 1306 | // Prepare for the retry pass after padding is done. |
| 1307 | Retrying = true; |
| 1308 | I = Helper.getBundleLockStart(); |
| 1309 | } |
| 1310 | continue; |
| 1311 | } |
| 1312 | |
| 1313 | // I points to a non bundle_lock/bundle_unlock instruction. |
| 1314 | if (Helper.isInBundleLockRegion()) { |
| 1315 | I->emitIAS(Func); |
| 1316 | // Only update stats during the final pass. |
| 1317 | if (Retrying) |
| 1318 | updateStats(Func, I); |
| 1319 | } else { |
| 1320 | // Treat it as though there were an implicit bundle_lock and |
| 1321 | // bundle_unlock wrapping the instruction. |
| 1322 | Helper.enterBundleLock(I); |
| 1323 | I->emitIAS(Func); |
| 1324 | Helper.enterBundleUnlock(); |
| 1325 | Helper.rollback(); |
| 1326 | Helper.padToNextBundle(); |
| 1327 | I->emitIAS(Func); |
| 1328 | updateStats(Func, I); |
| 1329 | Helper.leaveBundleLockRegion(); |
| 1330 | } |
| 1331 | } |
| 1332 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 1333 | // Don't allow bundle locking across basic blocks, to keep the backtracking |
| 1334 | // mechanism simple. |
Jim Stichnoth | 9f42d8c | 2015-02-20 09:20:14 -0800 | [diff] [blame] | 1335 | assert(!Helper.isInBundleLockRegion()); |
| 1336 | assert(!Retrying); |
Jan Voung | 0faec4c | 2014-11-05 17:29:56 -0800 | [diff] [blame] | 1337 | } |
| 1338 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 1339 | void CfgNode::dump(Cfg *Func) const { |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 1340 | if (!BuildDefs::dump()) |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 1341 | return; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 1342 | Func->setCurrentNode(this); |
| 1343 | Ostream &Str = Func->getContext()->getStrDump(); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 1344 | Liveness *Liveness = Func->getLiveness(); |
Andrew Scull | aa6c109 | 2015-09-03 17:50:30 -0700 | [diff] [blame] | 1345 | if (Func->isVerbose(IceV_Instructions) || Func->isVerbose(IceV_Loop)) |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 1346 | Str << getName() << ":\n"; |
Andrew Scull | aa6c109 | 2015-09-03 17:50:30 -0700 | [diff] [blame] | 1347 | // Dump the loop nest depth |
| 1348 | if (Func->isVerbose(IceV_Loop)) |
| 1349 | Str << " // LoopNestDepth = " << getLoopNestDepth() << "\n"; |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 1350 | // Dump list of predecessor nodes. |
Jim Stichnoth | fa4efea | 2015-01-27 05:06:03 -0800 | [diff] [blame] | 1351 | if (Func->isVerbose(IceV_Preds) && !InEdges.empty()) { |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 1352 | Str << " // preds = "; |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 1353 | bool First = true; |
| 1354 | for (CfgNode *I : InEdges) { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 1355 | if (!First) |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 1356 | Str << ", "; |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 1357 | First = false; |
| 1358 | Str << "%" << I->getName(); |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 1359 | } |
| 1360 | Str << "\n"; |
| 1361 | } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 1362 | // Dump the live-in variables. |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame^] | 1363 | if (Func->isVerbose(IceV_Liveness)) { |
| 1364 | if (Liveness != nullptr && !Liveness->getLiveIn(this).empty()) { |
| 1365 | const LivenessBV &LiveIn = Liveness->getLiveIn(this); |
| 1366 | Str << " // LiveIn:"; |
| 1367 | for (SizeT i = 0; i < LiveIn.size(); ++i) { |
| 1368 | if (LiveIn[i]) { |
| 1369 | Variable *Var = Liveness->getVariable(i, this); |
| 1370 | Str << " %" << Var->getName(Func); |
| 1371 | if (Func->isVerbose(IceV_RegOrigins) && Var->hasReg()) { |
| 1372 | Str << ":" |
| 1373 | << Func->getTarget()->getRegName(Var->getRegNum(), |
| 1374 | Var->getType()); |
| 1375 | } |
Jim Stichnoth | 088b2be | 2014-10-23 12:02:08 -0700 | [diff] [blame] | 1376 | } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 1377 | } |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame^] | 1378 | Str << "\n"; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 1379 | } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 1380 | } |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 1381 | // Dump each instruction. |
Jim Stichnoth | fa4efea | 2015-01-27 05:06:03 -0800 | [diff] [blame] | 1382 | if (Func->isVerbose(IceV_Instructions)) { |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 1383 | for (const Inst &I : Phis) |
| 1384 | I.dumpDecorated(Func); |
| 1385 | for (const Inst &I : Insts) |
| 1386 | I.dumpDecorated(Func); |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 1387 | } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 1388 | // Dump the live-out variables. |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame^] | 1389 | if (Func->isVerbose(IceV_Liveness)) { |
| 1390 | if (Liveness != nullptr && !Liveness->getLiveOut(this).empty()) { |
| 1391 | const LivenessBV &LiveOut = Liveness->getLiveOut(this); |
| 1392 | Str << " // LiveOut:"; |
| 1393 | for (SizeT i = 0; i < LiveOut.size(); ++i) { |
| 1394 | if (LiveOut[i]) { |
| 1395 | Variable *Var = Liveness->getVariable(i, this); |
| 1396 | Str << " %" << Var->getName(Func); |
| 1397 | if (Func->isVerbose(IceV_RegOrigins) && Var->hasReg()) { |
| 1398 | Str << ":" |
| 1399 | << Func->getTarget()->getRegName(Var->getRegNum(), |
| 1400 | Var->getType()); |
| 1401 | } |
Jim Stichnoth | 088b2be | 2014-10-23 12:02:08 -0700 | [diff] [blame] | 1402 | } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 1403 | } |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame^] | 1404 | Str << "\n"; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 1405 | } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 1406 | } |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 1407 | // Dump list of successor nodes. |
Jim Stichnoth | fa4efea | 2015-01-27 05:06:03 -0800 | [diff] [blame] | 1408 | if (Func->isVerbose(IceV_Succs)) { |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 1409 | Str << " // succs = "; |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 1410 | bool First = true; |
| 1411 | for (CfgNode *I : OutEdges) { |
Jim Stichnoth | 8363a06 | 2014-10-07 10:02:38 -0700 | [diff] [blame] | 1412 | if (!First) |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 1413 | Str << ", "; |
Jim Stichnoth | f44f371 | 2014-10-01 14:05:51 -0700 | [diff] [blame] | 1414 | First = false; |
| 1415 | Str << "%" << I->getName(); |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 1416 | } |
| 1417 | Str << "\n"; |
| 1418 | } |
| 1419 | } |
| 1420 | |
John Porto | f8b4cc8 | 2015-06-09 18:06:19 -0700 | [diff] [blame] | 1421 | void CfgNode::profileExecutionCount(VariableDeclaration *Var) { |
| 1422 | constexpr char RMW_I64[] = "llvm.nacl.atomic.rmw.i64"; |
| 1423 | |
| 1424 | GlobalContext *Context = Func->getContext(); |
| 1425 | |
| 1426 | bool BadIntrinsic = false; |
| 1427 | const Intrinsics::FullIntrinsicInfo *Info = |
| 1428 | Context->getIntrinsicsInfo().find(RMW_I64, BadIntrinsic); |
| 1429 | assert(!BadIntrinsic); |
| 1430 | assert(Info != nullptr); |
| 1431 | |
| 1432 | Operand *RMWI64Name = Context->getConstantExternSym(RMW_I64); |
John Porto | 8b1a705 | 2015-06-17 13:20:08 -0700 | [diff] [blame] | 1433 | constexpr RelocOffsetT Offset = 0; |
| 1434 | constexpr bool SuppressMangling = true; |
| 1435 | Constant *Counter = |
| 1436 | Context->getConstantSym(Offset, Var->getName(), SuppressMangling); |
John Porto | f8b4cc8 | 2015-06-09 18:06:19 -0700 | [diff] [blame] | 1437 | Constant *AtomicRMWOp = Context->getConstantInt32(Intrinsics::AtomicAdd); |
| 1438 | Constant *One = Context->getConstantInt64(1); |
| 1439 | Constant *OrderAcquireRelease = |
| 1440 | Context->getConstantInt32(Intrinsics::MemoryOrderAcquireRelease); |
| 1441 | |
Jim Stichnoth | 8cfeb69 | 2016-02-05 09:50:02 -0800 | [diff] [blame] | 1442 | auto *Instr = InstIntrinsicCall::create( |
John Porto | f8b4cc8 | 2015-06-09 18:06:19 -0700 | [diff] [blame] | 1443 | Func, 5, Func->makeVariable(IceType_i64), RMWI64Name, Info->Info); |
Jim Stichnoth | 8cfeb69 | 2016-02-05 09:50:02 -0800 | [diff] [blame] | 1444 | Instr->addArg(AtomicRMWOp); |
| 1445 | Instr->addArg(Counter); |
| 1446 | Instr->addArg(One); |
| 1447 | Instr->addArg(OrderAcquireRelease); |
| 1448 | Insts.push_front(Instr); |
John Porto | f8b4cc8 | 2015-06-09 18:06:19 -0700 | [diff] [blame] | 1449 | } |
| 1450 | |
Jim Stichnoth | f7c9a14 | 2014-04-29 10:52:43 -0700 | [diff] [blame] | 1451 | } // end of namespace Ice |