1 //===- subzero/src/IceCfgNode.cpp - Basic block (node) implementation -----===//
3 // The Subzero Code Generator
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the CfgNode class, including the complexities
11 // of instruction insertion and in-edge calculation.
13 //===----------------------------------------------------------------------===//
15 #include "assembler.h"
17 #include "IceCfgNode.h"
19 #include "IceLiveness.h"
20 #include "IceOperand.h"
21 #include "IceTargetLowering.h"
25 CfgNode::CfgNode(Cfg *Func, SizeT LabelNumber, IceString Name)
26 : Func(Func), Number(LabelNumber), Name(Name), HasReturn(false),
27 NeedsPlacement(false), InstCountEstimate(0) {}
29 // Returns the name the node was created with. If no name was given,
30 // it synthesizes a (hopefully) unique name.
31 IceString CfgNode::getName() const {
34 return "__" + std::to_string(getIndex());
37 // Adds an instruction to either the Phi list or the regular
38 // instruction list. Validates that all Phis are added before all
39 // regular instructions.
40 void CfgNode::appendInst(Inst *Inst) {
42 if (InstPhi *Phi = llvm::dyn_cast<InstPhi>(Inst)) {
44 Func->setError("Phi instruction added to the middle of a block");
49 Insts.push_back(Inst);
53 // Renumbers the non-deleted instructions in the node. This needs to
54 // be done in preparation for live range analysis. The instruction
55 // numbers in a block must be monotonically increasing. The range of
56 // instruction numbers in a block, from lowest to highest, must not
57 // overlap with the range of any other block.
58 void CfgNode::renumberInstructions() {
59 InstNumberT FirstNumber = Func->getNextInstNumber();
60 for (InstPhi *I : Phis)
64 InstCountEstimate = Func->getNextInstNumber() - FirstNumber;
67 // When a node is created, the OutEdges are immediately known, but the
68 // InEdges have to be built up incrementally. After the CFG has been
69 // constructed, the computePredecessors() pass finalizes it by
70 // creating the InEdges list.
71 void CfgNode::computePredecessors() {
72 OutEdges = (*Insts.rbegin())->getTerminatorEdges();
73 for (CfgNode *Succ : OutEdges)
74 Succ->InEdges.push_back(this);
77 // This does part 1 of Phi lowering, by creating a new dest variable
78 // for each Phi instruction, replacing the Phi instruction's dest with
79 // that variable, and adding an explicit assignment of the old dest to
80 // the new dest. For example,
83 // "a_phi=phi(...); a=a_phi".
85 // This is in preparation for part 2 which deletes the Phi
86 // instructions and appends assignment instructions to predecessor
87 // blocks. Note that this transformation preserves SSA form.
88 void CfgNode::placePhiLoads() {
89 for (InstPhi *I : Phis)
90 Insts.insert(Insts.begin(), I->lower(Func));
93 // This does part 2 of Phi lowering. For each Phi instruction at each
94 // out-edge, create a corresponding assignment instruction, and add
95 // all the assignments near the end of this block. They need to be
96 // added before any branch instruction, and also if the block ends
97 // with a compare instruction followed by a branch instruction that we
98 // may want to fuse, it's better to insert the new assignments before
99 // the compare instruction. The tryOptimizedCmpxchgCmpBr() method
100 // assumes this ordering of instructions.
102 // Note that this transformation takes the Phi dest variables out of
103 // SSA form, as there may be assignments to the dest variable in
106 // TODO: Defer this pass until after register allocation, then split
107 // critical edges, add the assignments, and lower them. This should
108 // reduce the amount of shuffling at the end of each block.
109 void CfgNode::placePhiStores() {
110 // Find the insertion point.
111 InstList::iterator InsertionPoint = Insts.end();
112 // Every block must end in a terminator instruction, and therefore
113 // must have at least one instruction, so it's valid to decrement
114 // InsertionPoint (but assert just in case).
115 assert(InsertionPoint != Insts.begin());
117 // Confirm that InsertionPoint is a terminator instruction. Calling
118 // getTerminatorEdges() on a non-terminator instruction will cause
119 // an llvm_unreachable().
120 (void)(*InsertionPoint)->getTerminatorEdges();
121 // SafeInsertionPoint is always immediately before the terminator
122 // instruction. If the block ends in a compare and conditional
123 // branch, it's better to place the Phi store before the compare so
124 // as not to interfere with compare/branch fusing. However, if the
125 // compare instruction's dest operand is the same as the new
126 // assignment statement's source operand, this can't be done due to
127 // data dependences, so we need to fall back to the
128 // SafeInsertionPoint. To illustrate:
130 // %97 = load i8* %96, align 1
131 // %98 = icmp ne i8 %97, 0
132 // br i1 %98, label %99, label %2132
134 // %100 = phi i8 [ %97, %95 ], [ %110, %108 ]
135 // %101 = phi i1 [ %98, %95 ], [ %111, %108 ]
136 // would be Phi-lowered as:
138 // %97 = load i8* %96, align 1
139 // %100_phi = %97 ; can be at InsertionPoint
140 // %98 = icmp ne i8 %97, 0
141 // %101_phi = %98 ; must be at SafeInsertionPoint
142 // br i1 %98, label %99, label %2132
147 // TODO(stichnot): It may be possible to bypass this whole
148 // SafeInsertionPoint mechanism. If a source basic block ends in a
149 // conditional branch:
152 // br i1 %foo, label %labelTrue, label %labelFalse
153 // and a branch target has a Phi involving the branch operand:
155 // %bar = phi i1 [ %foo, %labelSource ], ...
156 // then we actually know the constant i1 value of the Phi operand:
158 // %bar = phi i1 [ true, %labelSource ], ...
159 // It seems that this optimization should be done by clang or opt,
160 // but we could also do it here.
161 InstList::iterator SafeInsertionPoint = InsertionPoint;
162 // Keep track of the dest variable of a compare instruction, so that
163 // we insert the new instruction at the SafeInsertionPoint if the
164 // compare's dest matches the Phi-lowered assignment's source.
165 Variable *CmpInstDest = NULL;
166 // If the current insertion point is at a conditional branch
167 // instruction, and the previous instruction is a compare
168 // instruction, then we move the insertion point before the compare
169 // instruction so as not to interfere with compare/branch fusing.
170 if (InstBr *Branch = llvm::dyn_cast<InstBr>(*InsertionPoint)) {
171 if (!Branch->isUnconditional()) {
172 if (InsertionPoint != Insts.begin()) {
174 if (llvm::isa<InstIcmp>(*InsertionPoint) ||
175 llvm::isa<InstFcmp>(*InsertionPoint)) {
176 CmpInstDest = (*InsertionPoint)->getDest();
184 // Consider every out-edge.
185 for (CfgNode *Succ : OutEdges) {
186 // Consider every Phi instruction at the out-edge.
187 for (InstPhi *I : Succ->Phis) {
188 Operand *Operand = I->getOperandForTarget(this);
190 Variable *Dest = I->getDest();
192 InstAssign *NewInst = InstAssign::create(Func, Dest, Operand);
193 if (CmpInstDest == Operand)
194 Insts.insert(SafeInsertionPoint, NewInst);
196 Insts.insert(InsertionPoint, NewInst);
201 // Deletes the phi instructions after the loads and stores are placed.
202 void CfgNode::deletePhis() {
203 for (InstPhi *I : Phis)
207 // Splits the edge from Pred to this node by creating a new node and
208 // hooking up the in and out edges appropriately. (The EdgeIndex
209 // parameter is only used to make the new node's name unique when
210 // there are multiple edges between the same pair of nodes.) The new
211 // node's instruction list is initialized to the empty list, with no
212 // terminator instruction. If there are multiple edges from Pred to
213 // this node, only one edge is split, and the particular choice of
214 // edge is undefined. This could happen with a switch instruction, or
215 // a conditional branch that weirdly has both branches to the same
216 // place. TODO(stichnot,kschimpf): Figure out whether this is legal
217 // in the LLVM IR or the PNaCl bitcode, and if so, we need to
218 // establish a strong relationship among the ordering of Pred's
219 // out-edge list, this node's in-edge list, and the Phi instruction's
221 CfgNode *CfgNode::splitIncomingEdge(CfgNode *Pred, SizeT EdgeIndex) {
223 Func->makeNode("split_" + Pred->getName() + "_" + getName() + "_" +
224 std::to_string(EdgeIndex));
225 // The new node is added to the end of the node list, and will later
226 // need to be sorted into a reasonable topological order.
227 NewNode->setNeedsPlacement(true);
228 // Repoint Pred's out-edge.
230 for (auto I = Pred->OutEdges.begin(), E = Pred->OutEdges.end();
231 !Found && I != E; ++I) {
234 NewNode->InEdges.push_back(Pred);
239 // Repoint this node's in-edge.
241 for (auto I = InEdges.begin(), E = InEdges.end(); !Found && I != E; ++I) {
244 NewNode->OutEdges.push_back(this);
249 // Repoint a suitable branch instruction's target.
251 for (auto I = Pred->getInsts().rbegin(), E = Pred->getInsts().rend();
252 !Found && I != E; ++I) {
253 if (!(*I)->isDeleted()) {
254 Found = (*I)->repointEdge(this, NewNode);
263 // Helper function used by advancedPhiLowering().
264 bool sameVarOrReg(const Variable *Var, const Operand *Opnd) {
267 if (const auto Var2 = llvm::dyn_cast<Variable>(Opnd)) {
268 if (Var->hasReg() && Var->getRegNum() == Var2->getRegNum())
274 } // end of anonymous namespace
276 // This the "advanced" version of Phi lowering for a basic block, in
277 // contrast to the simple version that lowers through assignments
278 // involving temporaries.
280 // All Phi instructions in a basic block are conceptually executed in
281 // parallel. However, if we lower Phis early and commit to a
282 // sequential ordering, we may end up creating unnecessary
283 // interferences which lead to worse register allocation. Delaying
284 // Phi scheduling until after register allocation can help unless
285 // there are no free registers for shuffling registers or stack slots
286 // and spilling becomes necessary.
288 // The advanced Phi lowering starts by finding a topological sort of
289 // the Phi instructions, where "A=B" comes before "B=C" due to the
290 // anti-dependence on B. If a topological sort is not possible due to
291 // a cycle, the cycle is broken by introducing a non-parallel
292 // temporary. For example, a cycle arising from a permutation like
293 // "A=B;B=C;C=A" can become "T=A;A=B;B=C;C=T". All else being equal,
294 // prefer to schedule assignments with register-allocated Src operands
295 // earlier, in case that register becomes free afterwards, and prefer
296 // to schedule assignments with register-allocated Dest variables
297 // later, to keep that register free for longer.
299 // Once the ordering is determined, the Cfg edge is split and the
300 // assignment list is lowered by the target lowering layer. The
301 // specific placement of the new node within the Cfg node list is
302 // deferred until later, including after empty node contraction.
303 void CfgNode::advancedPhiLowering() {
304 if (getPhis().empty())
307 // Count the number of non-deleted Phi instructions.
313 size_t NumPred; // number of entries whose Src is this Dest
314 int32_t Weight; // preference for topological order
315 } Desc[getPhis().size()];
318 for (InstPhi *Inst : getPhis()) {
319 if (!Inst->isDeleted()) {
320 Desc[NumPhis].Phi = Inst;
321 Desc[NumPhis].Dest = Inst->getDest();
328 SizeT InEdgeIndex = 0;
329 for (CfgNode *Pred : InEdges) {
330 CfgNode *Split = splitIncomingEdge(Pred, InEdgeIndex++);
331 AssignList Assignments;
332 SizeT Remaining = NumPhis;
334 // First pass computes Src and initializes NumPred.
335 for (size_t I = 0; I < NumPhis; ++I) {
336 Variable *Dest = Desc[I].Dest;
337 Operand *Src = Desc[I].Phi->getOperandForTarget(Pred);
339 Desc[I].Processed = false;
341 // Cherry-pick any trivial assignments, so that they don't
342 // contribute to the running complexity of the topological sort.
343 if (sameVarOrReg(Dest, Src)) {
344 Desc[I].Processed = true;
347 // If Dest and Src are syntactically the same, don't bother
348 // adding the assignment, because in all respects it would
349 // be redundant, and if Dest/Src are on the stack, the
350 // target lowering may naively decide to lower it using a
351 // temporary register.
352 Assignments.push_back(InstAssign::create(Func, Dest, Src));
355 // Second pass computes NumPred by comparing every pair of Phi
357 for (size_t I = 0; I < NumPhis; ++I) {
358 if (Desc[I].Processed)
360 const Variable *Dest = Desc[I].Dest;
361 for (size_t J = 0; J < NumPhis; ++J) {
362 if (Desc[J].Processed)
365 // There shouldn't be two Phis with the same Dest variable
367 assert(!sameVarOrReg(Dest, Desc[J].Dest));
369 const Operand *Src = Desc[J].Src;
370 if (sameVarOrReg(Dest, Src))
375 // Another pass to compute initial Weight values.
377 // Always pick NumPred=0 over NumPred>0.
378 const int32_t WeightNoPreds = 4;
379 // Prefer Src as a register because the register might free up.
380 const int32_t WeightSrcIsReg = 2;
381 // Prefer Dest not as a register because the register stays free
383 const int32_t WeightDestNotReg = 1;
385 for (size_t I = 0; I < NumPhis; ++I) {
386 if (Desc[I].Processed)
389 if (Desc[I].NumPred == 0)
390 Weight += WeightNoPreds;
391 if (auto Var = llvm::dyn_cast<Variable>(Desc[I].Src))
393 Weight += WeightSrcIsReg;
394 if (!Desc[I].Dest->hasReg())
395 Weight += WeightDestNotReg;
396 Desc[I].Weight = Weight;
399 // Repeatedly choose and process the best candidate in the
400 // topological sort, until no candidates remain. This
401 // implementation is O(N^2) where N is the number of Phi
402 // instructions, but with a small constant factor compared to a
403 // likely implementation of O(N) topological sort.
404 for (; Remaining; --Remaining) {
405 size_t BestIndex = 0;
406 int32_t BestWeight = -1;
407 // Find the best candidate.
408 for (size_t I = 0; I < NumPhis; ++I) {
409 if (Desc[I].Processed)
412 Weight = Desc[I].Weight;
413 if (Weight > BestWeight) {
418 assert(BestWeight >= 0);
419 assert(Desc[BestIndex].NumPred <= 1);
420 Variable *Dest = Desc[BestIndex].Dest;
421 Operand *Src = Desc[BestIndex].Src;
422 assert(!sameVarOrReg(Dest, Src));
423 // Break a cycle by introducing a temporary.
424 if (Desc[BestIndex].NumPred) {
426 // If the target instruction "A=B" is part of a cycle, find
427 // the "X=A" assignment in the cycle because it will have to
428 // be rewritten as "X=tmp".
429 for (size_t J = 0; !Found && J < NumPhis; ++J) {
430 if (Desc[J].Processed)
432 Operand *OtherSrc = Desc[J].Src;
433 if (Desc[J].NumPred && sameVarOrReg(Dest, OtherSrc)) {
434 SizeT VarNum = Func->getNumVariables();
435 Variable *Tmp = Func->makeVariable(
436 OtherSrc->getType(), "__split_" + std::to_string(VarNum));
437 Tmp->setNeedsStackSlot();
438 Assignments.push_back(InstAssign::create(Func, Tmp, OtherSrc));
445 // Now that a cycle (if any) has been broken, create the actual
447 Assignments.push_back(InstAssign::create(Func, Dest, Src));
448 // Update NumPred for all Phi assignments using this Phi's Src
449 // as their Dest variable. Also update Weight if NumPred
450 // dropped from 1 to 0.
451 if (auto Var = llvm::dyn_cast<Variable>(Src)) {
452 for (size_t I = 0; I < NumPhis; ++I) {
453 if (Desc[I].Processed)
455 if (sameVarOrReg(Var, Desc[I].Dest)) {
456 if (--Desc[I].NumPred == 0)
457 Desc[I].Weight += WeightNoPreds;
461 Desc[BestIndex].Processed = true;
464 Func->getTarget()->lowerPhiAssignments(Split, Assignments);
466 // Renumber the instructions to be monotonically increasing so
467 // that addNode() doesn't assert when multi-definitions are added
469 Split->renumberInstructions();
470 Func->getVMetadata()->addNode(Split);
473 for (InstPhi *Inst : getPhis())
477 // Does address mode optimization. Pass each instruction to the
478 // TargetLowering object. If it returns a new instruction
479 // (representing the optimized address mode), then insert the new
480 // instruction and delete the old.
481 void CfgNode::doAddressOpt() {
482 TargetLowering *Target = Func->getTarget();
483 LoweringContext &Context = Target->getContext();
485 while (!Context.atEnd()) {
486 Target->doAddressOpt();
490 void CfgNode::doNopInsertion() {
491 TargetLowering *Target = Func->getTarget();
492 LoweringContext &Context = Target->getContext();
494 while (!Context.atEnd()) {
495 Target->doNopInsertion();
496 // Ensure Cur=Next, so that the nops are inserted before the current
497 // instruction rather than after.
498 Context.advanceNext();
499 Context.advanceCur();
501 // Insert before all instructions.
502 Context.setInsertPoint(getInsts().begin());
503 Context.advanceNext();
504 Context.advanceCur();
505 Target->doNopInsertion();
508 // Drives the target lowering. Passes the current instruction and the
509 // next non-deleted instruction for target lowering.
510 void CfgNode::genCode() {
511 TargetLowering *Target = Func->getTarget();
512 LoweringContext &Context = Target->getContext();
513 // Lower the regular instructions.
515 while (!Context.atEnd()) {
516 InstList::iterator Orig = Context.getCur();
517 if (llvm::isa<InstRet>(*Orig))
520 // Ensure target lowering actually moved the cursor.
521 assert(Context.getCur() != Orig);
523 // Do preliminary lowering of the Phi instructions.
524 Target->prelowerPhis();
527 void CfgNode::livenessLightweight() {
528 SizeT NumVars = Func->getNumVariables();
529 LivenessBV Live(NumVars);
530 // Process regular instructions in reverse order.
531 // TODO(stichnot): Use llvm::make_range with LLVM 3.5.
532 for (auto I = Insts.rbegin(), E = Insts.rend(); I != E; ++I) {
533 if ((*I)->isDeleted())
535 (*I)->livenessLightweight(Func, Live);
537 for (InstPhi *I : Phis) {
540 I->livenessLightweight(Func, Live);
544 // Performs liveness analysis on the block. Returns true if the
545 // incoming liveness changed from before, false if it stayed the same.
546 // (If it changes, the node's predecessors need to be processed
548 bool CfgNode::liveness(Liveness *Liveness) {
549 SizeT NumVars = Liveness->getNumVarsInNode(this);
550 LivenessBV Live(NumVars);
551 LiveBeginEndMap *LiveBegin = NULL;
552 LiveBeginEndMap *LiveEnd = NULL;
553 // Mark the beginning and ending of each variable's live range
554 // with the sentinel instruction number 0.
555 if (Liveness->getMode() == Liveness_Intervals) {
556 LiveBegin = Liveness->getLiveBegin(this);
557 LiveEnd = Liveness->getLiveEnd(this);
560 // Guess that the number of live ranges beginning is roughly the
561 // number of instructions, and same for live ranges ending.
562 LiveBegin->reserve(getInstCountEstimate());
563 LiveEnd->reserve(getInstCountEstimate());
565 // Initialize Live to be the union of all successors' LiveIn.
566 for (CfgNode *Succ : OutEdges) {
567 Live |= Liveness->getLiveIn(Succ);
568 // Mark corresponding argument of phis in successor as live.
569 for (InstPhi *I : Succ->Phis)
570 I->livenessPhiOperand(Live, this, Liveness);
572 Liveness->getLiveOut(this) = Live;
574 // Process regular instructions in reverse order.
575 for (auto I = Insts.rbegin(), E = Insts.rend(); I != E; ++I) {
576 if ((*I)->isDeleted())
578 (*I)->liveness((*I)->getNumber(), Live, Liveness, LiveBegin, LiveEnd);
580 // Process phis in forward order so that we can override the
581 // instruction number to be that of the earliest phi instruction in
583 SizeT NumNonDeadPhis = 0;
584 InstNumberT FirstPhiNumber = Inst::NumberSentinel;
585 for (InstPhi *I : Phis) {
588 if (FirstPhiNumber == Inst::NumberSentinel)
589 FirstPhiNumber = I->getNumber();
590 if (I->liveness(FirstPhiNumber, Live, Liveness, LiveBegin, LiveEnd))
594 // When using the sparse representation, after traversing the
595 // instructions in the block, the Live bitvector should only contain
596 // set bits for global variables upon block entry. We validate this
597 // by shrinking the Live vector and then testing it against the
598 // pre-shrunk version. (The shrinking is required, but the
599 // validation is not.)
600 LivenessBV LiveOrig = Live;
601 Live.resize(Liveness->getNumGlobalVars());
602 // Non-global arguments in the entry node are allowed to be live on
604 bool IsEntry = (Func->getEntryNode() == this);
605 if (!(IsEntry || Live == LiveOrig)) {
606 // This is a fatal liveness consistency error. Print some
607 // diagnostics and abort.
608 Ostream &Str = Func->getContext()->getStrDump();
609 Func->resetCurrentNode();
610 Str << "LiveOrig-Live =";
611 for (SizeT i = Live.size(); i < LiveOrig.size(); ++i) {
612 if (LiveOrig.test(i)) {
614 Liveness->getVariable(i, this)->dump(Func);
618 llvm_unreachable("Fatal inconsistency in liveness analysis");
621 bool Changed = false;
622 LivenessBV &LiveIn = Liveness->getLiveIn(this);
623 // Add in current LiveIn
625 // Check result, set LiveIn=Live
626 SizeT &PrevNumNonDeadPhis = Liveness->getNumNonDeadPhis(this);
627 bool LiveInChanged = (Live != LiveIn);
628 Changed = (NumNonDeadPhis != PrevNumNonDeadPhis || LiveInChanged);
631 PrevNumNonDeadPhis = NumNonDeadPhis;
635 // Now that basic liveness is complete, remove dead instructions that
636 // were tentatively marked as dead, and compute actual live ranges.
637 // It is assumed that within a single basic block, a live range begins
638 // at most once and ends at most once. This is certainly true for
639 // pure SSA form. It is also true once phis are lowered, since each
640 // assignment to the phi-based temporary is in a different basic
641 // block, and there is a single read that ends the live in the basic
642 // block that contained the actual phi instruction.
643 void CfgNode::livenessPostprocess(LivenessMode Mode, Liveness *Liveness) {
644 InstNumberT FirstInstNum = Inst::NumberSentinel;
645 InstNumberT LastInstNum = Inst::NumberSentinel;
646 // Process phis in any order. Process only Dest operands.
647 for (InstPhi *I : Phis) {
651 if (FirstInstNum == Inst::NumberSentinel)
652 FirstInstNum = I->getNumber();
653 assert(I->getNumber() > LastInstNum);
654 LastInstNum = I->getNumber();
656 // Process instructions
657 for (Inst *I : Insts) {
661 if (FirstInstNum == Inst::NumberSentinel)
662 FirstInstNum = I->getNumber();
663 assert(I->getNumber() > LastInstNum);
664 LastInstNum = I->getNumber();
665 // Create fake live ranges for a Kill instruction, but only if the
666 // linked instruction is still alive.
667 if (Mode == Liveness_Intervals) {
668 if (InstFakeKill *Kill = llvm::dyn_cast<InstFakeKill>(I)) {
669 if (!Kill->getLinked()->isDeleted()) {
670 SizeT NumSrcs = I->getSrcSize();
671 for (SizeT Src = 0; Src < NumSrcs; ++Src) {
672 Variable *Var = llvm::cast<Variable>(I->getSrc(Src));
673 InstNumberT InstNumber = I->getNumber();
674 Var->addLiveRange(InstNumber, InstNumber, 1);
680 if (Mode != Liveness_Intervals)
682 TimerMarker T1(TimerStack::TT_liveRangeCtor, Func);
684 SizeT NumVars = Liveness->getNumVarsInNode(this);
685 LivenessBV &LiveIn = Liveness->getLiveIn(this);
686 LivenessBV &LiveOut = Liveness->getLiveOut(this);
687 LiveBeginEndMap &MapBegin = *Liveness->getLiveBegin(this);
688 LiveBeginEndMap &MapEnd = *Liveness->getLiveEnd(this);
689 std::sort(MapBegin.begin(), MapBegin.end());
690 std::sort(MapEnd.begin(), MapEnd.end());
691 // Verify there are no duplicates.
693 bool operator()(const LiveBeginEndMapEntry &A,
694 const LiveBeginEndMapEntry &B) {
695 return A.first == B.first;
698 assert(std::adjacent_find(MapBegin.begin(), MapBegin.end(), ComparePair()) ==
700 assert(std::adjacent_find(MapEnd.begin(), MapEnd.end(), ComparePair()) ==
703 LivenessBV LiveInAndOut = LiveIn;
704 LiveInAndOut &= LiveOut;
706 // Iterate in parallel across the sorted MapBegin[] and MapEnd[].
707 auto IBB = MapBegin.begin(), IEB = MapEnd.begin();
708 auto IBE = MapBegin.end(), IEE = MapEnd.end();
709 while (IBB != IBE || IEB != IEE) {
710 SizeT i1 = IBB == IBE ? NumVars : IBB->first;
711 SizeT i2 = IEB == IEE ? NumVars : IEB->first;
712 SizeT i = std::min(i1, i2);
713 // i1 is the Variable number of the next MapBegin entry, and i2 is
714 // the Variable number of the next MapEnd entry. If i1==i2, then
715 // the Variable's live range begins and ends in this block. If
716 // i1<i2, then i1's live range begins at instruction IBB->second
717 // and extends through the end of the block. If i1>i2, then i2's
718 // live range begins at the first instruction of the block and
719 // ends at IEB->second. In any case, we choose the lesser of i1
720 // and i2 and proceed accordingly.
721 InstNumberT LB = i == i1 ? IBB->second : FirstInstNum;
722 InstNumberT LE = i == i2 ? IEB->second : LastInstNum + 1;
724 Variable *Var = Liveness->getVariable(i, this);
725 if (!Var->getIgnoreLiveness()) {
727 Var->addLiveRange(FirstInstNum, LE, 1);
728 Var->addLiveRange(LB, LastInstNum + 1, 1);
729 // Assert that Var is a global variable by checking that its
730 // liveness index is less than the number of globals. This
731 // ensures that the LiveInAndOut[] access is valid.
732 assert(i < Liveness->getNumGlobalVars());
733 LiveInAndOut[i] = false;
735 Var->addLiveRange(LB, LE, 1);
743 // Process the variables that are live across the entire block.
744 for (int i = LiveInAndOut.find_first(); i != -1;
745 i = LiveInAndOut.find_next(i)) {
746 Variable *Var = Liveness->getVariable(i, this);
747 Var->addLiveRange(FirstInstNum, LastInstNum + 1, 1);
751 // If this node contains only deleted instructions, and ends in an
752 // unconditional branch, contract the node by repointing all its
753 // in-edges to its successor.
754 void CfgNode::contractIfEmpty() {
755 if (InEdges.size() == 0)
758 for (Inst *I : Insts) {
759 if (!I->isDeleted() && !I->isUnconditionalBranch())
763 Branch->setDeleted();
764 assert(OutEdges.size() == 1);
765 // Repoint all this node's in-edges to this node's successor.
766 for (CfgNode *Pred : InEdges) {
767 for (auto I = Pred->OutEdges.begin(), E = Pred->OutEdges.end(); I != E;
771 OutEdges[0]->InEdges.push_back(Pred);
774 for (Inst *I : Pred->getInsts()) {
776 I->repointEdge(this, OutEdges[0]);
780 // Don't bother removing the single out-edge, which would also
781 // require finding the corresponding in-edge in the successor and
785 void CfgNode::doBranchOpt(const CfgNode *NextNode) {
786 TargetLowering *Target = Func->getTarget();
787 // Check every instruction for a branch optimization opportunity.
788 // It may be more efficient to iterate in reverse and stop after the
789 // first opportunity, unless there is some target lowering where we
790 // have the possibility of multiple such optimizations per block
791 // (currently not the case for x86 lowering).
792 for (Inst *I : Insts) {
793 if (!I->isDeleted()) {
794 Target->doBranchOpt(I, NextNode);
799 // ======================== Dump routines ======================== //
801 void CfgNode::emit(Cfg *Func) const {
802 Func->setCurrentNode(this);
803 Ostream &Str = Func->getContext()->getStrEmit();
804 if (Func->getEntryNode() == this) {
805 Str << Func->getContext()->mangleName(Func->getFunctionName()) << ":\n";
807 Str << getAsmName() << ":\n";
808 if (Func->useIntegratedAssembler()) {
809 Assembler *Asm = Func->getAssembler<Assembler>();
810 Asm->BindCfgNodeLabel(getIndex());
812 for (InstPhi *Phi : Phis) {
813 if (Phi->isDeleted())
815 // Emitting a Phi instruction should cause an error.
819 for (Inst *I : Insts) {
822 if (Func->useIntegratedAssembler()) {
828 // Update emitted instruction count, plus fill/spill count for
829 // Variable operands without a physical register.
830 if (uint32_t Count = I->getEmitInstCount()) {
831 Func->getContext()->statsUpdateEmitted(Count);
832 if (Variable *Dest = I->getDest()) {
834 Func->getContext()->statsUpdateFills();
836 for (SizeT S = 0; S < I->getSrcSize(); ++S) {
837 if (Variable *Src = llvm::dyn_cast<Variable>(I->getSrc(S))) {
839 Func->getContext()->statsUpdateSpills();
846 void CfgNode::dump(Cfg *Func) const {
847 Func->setCurrentNode(this);
848 Ostream &Str = Func->getContext()->getStrDump();
849 Liveness *Liveness = Func->getLiveness();
850 if (Func->getContext()->isVerbose(IceV_Instructions)) {
851 Str << getName() << ":\n";
853 // Dump list of predecessor nodes.
854 if (Func->getContext()->isVerbose(IceV_Preds) && !InEdges.empty()) {
855 Str << " // preds = ";
857 for (CfgNode *I : InEdges) {
861 Str << "%" << I->getName();
865 // Dump the live-in variables.
868 LiveIn = Liveness->getLiveIn(this);
869 if (Func->getContext()->isVerbose(IceV_Liveness) && !LiveIn.empty()) {
870 Str << " // LiveIn:";
871 for (SizeT i = 0; i < LiveIn.size(); ++i) {
873 Variable *Var = Liveness->getVariable(i, this);
874 Str << " %" << Var->getName();
875 if (Func->getContext()->isVerbose(IceV_RegOrigins) && Var->hasReg()) {
876 Str << ":" << Func->getTarget()->getRegName(Var->getRegNum(),
883 // Dump each instruction.
884 if (Func->getContext()->isVerbose(IceV_Instructions)) {
885 for (InstPhi *I : Phis)
886 I->dumpDecorated(Func);
887 for (Inst *I : Insts)
888 I->dumpDecorated(Func);
890 // Dump the live-out variables.
893 LiveOut = Liveness->getLiveOut(this);
894 if (Func->getContext()->isVerbose(IceV_Liveness) && !LiveOut.empty()) {
895 Str << " // LiveOut:";
896 for (SizeT i = 0; i < LiveOut.size(); ++i) {
898 Variable *Var = Liveness->getVariable(i, this);
899 Str << " %" << Var->getName();
900 if (Func->getContext()->isVerbose(IceV_RegOrigins) && Var->hasReg()) {
901 Str << ":" << Func->getTarget()->getRegName(Var->getRegNum(),
908 // Dump list of successor nodes.
909 if (Func->getContext()->isVerbose(IceV_Succs)) {
910 Str << " // succs = ";
912 for (CfgNode *I : OutEdges) {
916 Str << "%" << I->getName();
922 } // end of namespace Ice