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