Subzero: Use llvm::ilist<> for PhiList and AssignList.

src/IceCfgNode.cpp

 //===- subzero/src/IceCfgNode.cpp - Basic block (node) implementation -----===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the CfgNode class, including the complexities
@@ skipping 39 matching lines @@
   }
 }
 
 // Renumbers the non-deleted instructions in the node.  This needs to
 // be done in preparation for live range analysis.  The instruction
 // numbers in a block must be monotonically increasing.  The range of
 // instruction numbers in a block, from lowest to highest, must not
 // overlap with the range of any other block.
 void CfgNode::renumberInstructions() {
   InstNumberT FirstNumber = Func->getNextInstNumber();
-  for (InstPhi *I : Phis)
+  for (auto I = Phis.begin(), E = Phis.end(); I != E; ++I)
     I->renumber(Func);
   for (auto I = Insts.begin(), E = Insts.end(); I != E; ++I)
     I->renumber(Func);
   InstCountEstimate = Func->getNextInstNumber() - FirstNumber;
 }
 
 // When a node is created, the OutEdges are immediately known, but the
 // InEdges have to be built up incrementally.  After the CFG has been
 // constructed, the computePredecessors() pass finalizes it by
 // creating the InEdges list.
 void CfgNode::computePredecessors() {
   OutEdges = Insts.rbegin()->getTerminatorEdges();
   for (CfgNode *Succ : OutEdges)
     Succ->InEdges.push_back(this);
 }
 
 // This does part 1 of Phi lowering, by creating a new dest variable
 // for each Phi instruction, replacing the Phi instruction's dest with
 // that variable, and adding an explicit assignment of the old dest to
 // the new dest.  For example,
 //   a=phi(...)
 // changes to
 //   "a_phi=phi(...); a=a_phi".
 //
 // This is in preparation for part 2 which deletes the Phi
 // instructions and appends assignment instructions to predecessor
 // blocks.  Note that this transformation preserves SSA form.
 void CfgNode::placePhiLoads() {
-  for (InstPhi *I : Phis)
-    Insts.insert(Insts.begin(), I->lower(Func));
+  for (auto I = Phis.begin(), E = Phis.end(); I != E; ++I) {
+    auto Phi = llvm::dyn_cast<InstPhi>(I);
+    Insts.insert(Insts.begin(), Phi->lower(Func));
+  }
 }
 
 // This does part 2 of Phi lowering.  For each Phi instruction at each
 // out-edge, create a corresponding assignment instruction, and add
 // all the assignments near the end of this block.  They need to be
 // added before any branch instruction, and also if the block ends
 // with a compare instruction followed by a branch instruction that we
 // may want to fuse, it's better to insert the new assignments before
 // the compare instruction. The tryOptimizedCmpxchgCmpBr() method
 // assumes this ordering of instructions.
@@ skipping 76 matching lines @@
         } else {
           ++InsertionPoint;
         }
       }
     }
   }
 
   // Consider every out-edge.
   for (CfgNode *Succ : OutEdges) {
     // Consider every Phi instruction at the out-edge.
-    for (InstPhi *I : Succ->Phis) {
-      Operand *Operand = I->getOperandForTarget(this);
+    for (auto I = Succ->Phis.begin(), E = Succ->Phis.end(); I != E; ++I) {
+      auto Phi = llvm::dyn_cast<InstPhi>(I);
+      Operand *Operand = Phi->getOperandForTarget(this);
       assert(Operand);
       Variable *Dest = I->getDest();
       assert(Dest);
       InstAssign *NewInst = InstAssign::create(Func, Dest, Operand);
       if (CmpInstDest == Operand)
         Insts.insert(SafeInsertionPoint, NewInst);
       else
         Insts.insert(InsertionPoint, NewInst);
     }
   }
 }
 
 // Deletes the phi instructions after the loads and stores are placed.
 void CfgNode::deletePhis() {
-  for (InstPhi *I : Phis)
+  for (auto I = Phis.begin(), E = Phis.end(); I != E; ++I)
     I->setDeleted();
 }
 
 // Splits the edge from Pred to this node by creating a new node and
 // hooking up the in and out edges appropriately.  (The EdgeIndex
 // parameter is only used to make the new node's name unique when
 // there are multiple edges between the same pair of nodes.)  The new
 // node's instruction list is initialized to the empty list, with no
 // terminator instruction.  If there are multiple edges from Pred to
 // this node, only one edge is split, and the particular choice of
@@ skipping 95 matching lines @@
   struct {
     InstPhi *Phi;
     Variable *Dest;
     Operand *Src;
     bool Processed;
     size_t NumPred; // number of entries whose Src is this Dest
     int32_t Weight; // preference for topological order
   } Desc[getPhis().size()];
 
   size_t NumPhis = 0;
-  for (InstPhi *Inst : getPhis()) {
+  for (auto I = Phis.begin(), E = Phis.end(); I != E; ++I) {
+    auto Inst = llvm::dyn_cast<InstPhi>(I);
     if (!Inst->isDeleted()) {
       Desc[NumPhis].Phi = Inst;
       Desc[NumPhis].Dest = Inst->getDest();
       ++NumPhis;
     }
   }
   if (NumPhis == 0)
     return;
 
   SizeT InEdgeIndex = 0;
@@ skipping 133 matching lines @@
 
     Func->getTarget()->lowerPhiAssignments(Split, Assignments);
 
     // Renumber the instructions to be monotonically increasing so
     // that addNode() doesn't assert when multi-definitions are added
     // out of order.
     Split->renumberInstructions();
     Func->getVMetadata()->addNode(Split);
   }
 
-  for (InstPhi *Inst : getPhis())
-    Inst->setDeleted();
+  for (auto I = Phis.begin(), E = Phis.end(); I != E; ++I)
+    I->setDeleted();
 }
 
 // Does address mode optimization.  Pass each instruction to the
 // TargetLowering object.  If it returns a new instruction
 // (representing the optimized address mode), then insert the new
 // instruction and delete the old.
 void CfgNode::doAddressOpt() {
   TargetLowering *Target = Func->getTarget();
   LoweringContext &Context = Target->getContext();
   Context.init(this);
@@ skipping 42 matching lines @@
 void CfgNode::livenessLightweight() {
   SizeT NumVars = Func->getNumVariables();
   LivenessBV Live(NumVars);
   // Process regular instructions in reverse order.
   // TODO(stichnot): Use llvm::make_range with LLVM 3.5.
   for (auto I = Insts.rbegin(), E = Insts.rend(); I != E; ++I) {
     if (I->isDeleted())
       continue;
     I->livenessLightweight(Func, Live);
   }
-  for (InstPhi *I : Phis) {
+  for (auto I = Phis.begin(), E = Phis.end(); I != E; ++I) {
     if (I->isDeleted())
       continue;
     I->livenessLightweight(Func, Live);
   }
 }
 
 // Performs liveness analysis on the block.  Returns true if the
 // incoming liveness changed from before, false if it stayed the same.
 // (If it changes, the node's predecessors need to be processed
 // again.)
@@ skipping 11 matching lines @@
     LiveEnd->clear();
     // Guess that the number of live ranges beginning is roughly the
     // number of instructions, and same for live ranges ending.
     LiveBegin->reserve(getInstCountEstimate());
     LiveEnd->reserve(getInstCountEstimate());
   }
   // Initialize Live to be the union of all successors' LiveIn.
   for (CfgNode *Succ : OutEdges) {
     Live |= Liveness->getLiveIn(Succ);
     // Mark corresponding argument of phis in successor as live.
-    for (InstPhi *I : Succ->Phis)
-      I->livenessPhiOperand(Live, this, Liveness);
+    for (auto I = Succ->Phis.begin(), E = Succ->Phis.end(); I != E; ++I) {
+      auto Phi = llvm::dyn_cast<InstPhi>(I);
+      Phi->livenessPhiOperand(Live, this, Liveness);
+    }
   }
   Liveness->getLiveOut(this) = Live;
 
   // Process regular instructions in reverse order.
   for (auto I = Insts.rbegin(), E = Insts.rend(); I != E; ++I) {
     if (I->isDeleted())
       continue;
     I->liveness(I->getNumber(), Live, Liveness, LiveBegin, LiveEnd);
   }
   // Process phis in forward order so that we can override the
   // instruction number to be that of the earliest phi instruction in
   // the block.
   SizeT NumNonDeadPhis = 0;
   InstNumberT FirstPhiNumber = Inst::NumberSentinel;
-  for (InstPhi *I : Phis) {
+  for (auto I = Phis.begin(), E = Phis.end(); I != E; ++I) {
     if (I->isDeleted())
       continue;
     if (FirstPhiNumber == Inst::NumberSentinel)
       FirstPhiNumber = I->getNumber();
     if (I->liveness(FirstPhiNumber, Live, Liveness, LiveBegin, LiveEnd))
       ++NumNonDeadPhis;
   }
 
   // When using the sparse representation, after traversing the
   // instructions in the block, the Live bitvector should only contain
@@ skipping 41 matching lines @@
 // It is assumed that within a single basic block, a live range begins
 // at most once and ends at most once.  This is certainly true for
 // pure SSA form.  It is also true once phis are lowered, since each
 // assignment to the phi-based temporary is in a different basic
 // block, and there is a single read that ends the live in the basic
 // block that contained the actual phi instruction.
 void CfgNode::livenessPostprocess(LivenessMode Mode, Liveness *Liveness) {
   InstNumberT FirstInstNum = Inst::NumberSentinel;
   InstNumberT LastInstNum = Inst::NumberSentinel;
   // Process phis in any order.  Process only Dest operands.
-  for (InstPhi *I : Phis) {
+  for (auto I = Phis.begin(), E = Phis.end(); I != E; ++I) {
     I->deleteIfDead();
     if (I->isDeleted())
       continue;
     if (FirstInstNum == Inst::NumberSentinel)
       FirstInstNum = I->getNumber();
     assert(I->getNumber() > LastInstNum);
     LastInstNum = I->getNumber();
   }
   // Process instructions
   for (auto I = Insts.begin(), E = Insts.end(); I != E; ++I) {
@@ skipping 224 matching lines @@
     return;
   Func->setCurrentNode(this);
   Ostream &Str = Func->getContext()->getStrEmit();
   Liveness *Liveness = Func->getLiveness();
   bool DecorateAsm = Liveness && Func->getContext()->getFlags().DecorateAsm;
   Str << getAsmName() << ":\n";
   std::vector<SizeT> LiveRegCount(Func->getTarget()->getNumRegisters());
   if (DecorateAsm)
     emitRegisterUsage(Str, Func, this, true, LiveRegCount);
 
-  for (InstPhi *Phi : Phis) {
-    if (Phi->isDeleted())
+  for (auto I = Phis.begin(), E = Phis.end(); I != E; ++I) {
+    if (I->isDeleted())
       continue;
     // Emitting a Phi instruction should cause an error.
-    Inst *Instr = Phi;
-    Instr->emit(Func);
+    I->emit(Func);
   }
   for (auto I = Insts.begin(), E = Insts.end(); I != E; ++I) {
     if (I->isDeleted())
       continue;
     if (I->isRedundantAssign()) {
       Variable *Dest = I->getDest();
       if (DecorateAsm && Dest->hasReg() && !I->isLastUse(I->getSrc(0)))
         ++LiveRegCount[Dest->getRegNum()];
       continue;
     }
     I->emit(Func);
     if (DecorateAsm)
       emitLiveRangesEnded(Str, Func, I, LiveRegCount);
     Str << "\n";
     updateStats(Func, I);
   }
   if (DecorateAsm)
     emitRegisterUsage(Str, Func, this, false, LiveRegCount);
 }
 
 void CfgNode::emitIAS(Cfg *Func) const {
   Func->setCurrentNode(this);
   Assembler *Asm = Func->getAssembler<Assembler>();
   Asm->BindCfgNodeLabel(getIndex());
-  for (InstPhi *Phi : Phis) {
-    if (Phi->isDeleted())
+  for (auto I = Phis.begin(), E = Phis.end(); I != E; ++I) {
+    if (I->isDeleted())
       continue;
     // Emitting a Phi instruction should cause an error.
-    Inst *Instr = Phi;
-    Instr->emitIAS(Func);
+    I->emitIAS(Func);
   }
   for (auto I = Insts.begin(), E = Insts.end(); I != E; ++I) {
     if (I->isDeleted())
       continue;
     if (I->isRedundantAssign())
       continue;
     I->emitIAS(Func);
     updateStats(Func, I);
   }
 }
@@ skipping 32 matching lines @@
         if (Func->getContext()->isVerbose(IceV_RegOrigins) && Var->hasReg()) {
           Str << ":" << Func->getTarget()->getRegName(Var->getRegNum(),
                                                       Var->getType());
         }
       }
     }
     Str << "\n";
   }
   // Dump each instruction.
   if (Func->getContext()->isVerbose(IceV_Instructions)) {
-    for (InstPhi *I : Phis)
+    for (auto I = Phis.begin(), E = Phis.end(); I != E; ++I)
       I->dumpDecorated(Func);
     for (auto I = Insts.begin(), E = Insts.end(); I != E; ++I)
       I->dumpDecorated(Func);
   }
   // Dump the live-out variables.
   LivenessBV LiveOut;
   if (Liveness)
     LiveOut = Liveness->getLiveOut(this);
   if (Func->getContext()->isVerbose(IceV_Liveness) && !LiveOut.empty()) {
     Str << "    // LiveOut:";
@@ skipping 17 matching lines @@
       if (!First)
         Str << ", ";
       First = false;
       Str << "%" << I->getName();
     }
     Str << "\n";
   }
 }
 
 } // end of namespace Ice