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