Subzero: Auto-awesome iterators.

src/IceRegAlloc.cpp

 //===- subzero/src/IceRegAlloc.cpp - Linear-scan 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 LinearScan class, which performs the
@@ skipping 70 matching lines @@
   // balanced binary tree, so inserting live ranges for N variables is
   // O(N log N) complexity.  N may be proportional to the number of
   // instructions, thanks to temporary generation during lowering.  As
   // a result, it may be useful to design a better data structure for
   // storing Func->getVariables().
   const VarList &Vars = Func->getVariables();
   {
     static TimerIdT IDinitUnhandled =
         GlobalContext::getTimerID("initUnhandled");
     TimerMarker T(IDinitUnhandled, Func->getContext());
-    for (VarList::const_iterator I = Vars.begin(), E = Vars.end(); I != E;
-         ++I) {
-      Variable *Var = *I;
+    for (Variable *Var : Vars) {
       // Explicitly don't consider zero-weight variables, which are
       // meant to be spill slots.
       if (Var->getWeight() == RegWeight::Zero)
         continue;
       // Don't bother if the variable has a null live range, which means
       // it was never referenced.
       if (Var->getLiveRange().isEmpty())
         continue;
       Unhandled.insert(LiveRangeWrapper(Var));
       if (Var->hasReg()) {
@@ skipping 40 matching lines @@
         Cur.dump(Func);
         Str << "\n";
       }
       Active.push_back(Cur);
       assert(RegUses[RegNum] >= 0);
       ++RegUses[RegNum];
       continue;
     }
 
     // Check for active ranges that have expired or become inactive.
-    for (UnorderedRanges::iterator I = Active.begin(), E = Active.end(); I != E;
-         I = Next) {
+    for (auto I = Active.begin(), E = Active.end(); I != E; I = Next) {
       Next = I;
       ++Next;
       LiveRangeWrapper Item = *I;
       bool Moved = false;
       if (Item.endsBefore(Cur)) {
         // Move Item from Active to Handled list.
         if (Verbose) {
           Str << "Expiring     ";
           Item.dump(Func);
           Str << "\n";
@@ skipping 15 matching lines @@
       if (Moved) {
         // Decrement Item from RegUses[].
         assert(Item.Var->hasRegTmp());
         int32_t RegNum = Item.Var->getRegNumTmp();
         --RegUses[RegNum];
         assert(RegUses[RegNum] >= 0);
       }
     }
 
     // Check for inactive ranges that have expired or reactivated.
-    for (UnorderedRanges::iterator I = Inactive.begin(), E = Inactive.end();
-         I != E; I = Next) {
+    for (auto I = Inactive.begin(), E = Inactive.end(); I != E; I = Next) {
       Next = I;
       ++Next;
       LiveRangeWrapper Item = *I;
       if (Item.endsBefore(Cur)) {
         // Move Item from Inactive to Handled list.
         if (Verbose) {
           Str << "Expiring     ";
           Item.dump(Func);
           Str << "\n";
         }
@@ skipping 70 matching lines @@
     if (Verbose) {
       if (Prefer) {
         Str << "Initial Prefer=" << *Prefer << " R=" << PreferReg
             << " LIVE=" << Prefer->getLiveRange() << " Overlap=" << AllowOverlap
             << "\n";
       }
     }
 
     // Remove registers from the Free[] list where an Inactive range
     // overlaps with the current range.
-    for (UnorderedRanges::const_iterator I = Inactive.begin(),
-                                         E = Inactive.end();
-         I != E; ++I) {
-      LiveRangeWrapper Item = *I;
+    for (const LiveRangeWrapper &Item : Inactive) {
       if (Item.overlaps(Cur)) {
         int32_t RegNum = Item.Var->getRegNumTmp();
         // Don't assert(Free[RegNum]) because in theory (though
         // probably never in practice) there could be two inactive
         // variables that were marked with AllowOverlap.
         Free[RegNum] = false;
         // Disable AllowOverlap if an Inactive variable, which is not
         // Prefer, shares Prefer's register, and has a definition
         // within Cur's live range.
         if (AllowOverlap && Item.Var != Prefer && RegNum == PreferReg &&
             overlapsDefs(Func, Cur, Item.Var)) {
           AllowOverlap = false;
           dumpDisableOverlap(Func, Item.Var, "Inactive");
         }
       }
     }
 
     // Disable AllowOverlap if an Active variable, which is not
     // Prefer, shares Prefer's register, and has a definition within
     // Cur's live range.
-    for (UnorderedRanges::iterator I = Active.begin(), E = Active.end();
-         AllowOverlap && I != E; ++I) {
-      LiveRangeWrapper Item = *I;
+    for (const LiveRangeWrapper &Item : Active) {
       int32_t RegNum = Item.Var->getRegNumTmp();
       if (Item.Var != Prefer && RegNum == PreferReg &&
           overlapsDefs(Func, Cur, Item.Var)) {
         AllowOverlap = false;
         dumpDisableOverlap(Func, Item.Var, "Active");
       }
     }
 
     // Remove registers from the Free[] list where an Unhandled range
     // overlaps with the current range and is precolored.
-    // Cur.endsBefore(*I) is an early exit check that turns a
+    // Cur.endsBefore(Item) is an early exit check that turns a
     // guaranteed O(N^2) algorithm into expected linear complexity.
     llvm::SmallBitVector PrecoloredUnhandled(RegMask.size());
     // Note: PrecoloredUnhandled is only used for dumping.
-    for (OrderedRanges::const_iterator I = Unhandled.begin(),
-                                       E = Unhandled.end();
-         I != E && !Cur.endsBefore(*I); ++I) {
-      LiveRangeWrapper Item = *I;
+    for (const LiveRangeWrapper &Item : Unhandled) {
+      if (Cur.endsBefore(Item))
+        break;
       if (Item.Var->hasReg() && Item.overlaps(Cur)) {
         int32_t ItemReg = Item.Var->getRegNum(); // Note: not getRegNumTmp()
         Free[ItemReg] = false;
         PrecoloredUnhandled[ItemReg] = true;
         // Disable AllowOverlap if the preferred register is one of
         // these precolored unhandled overlapping ranges.
         if (AllowOverlap && ItemReg == PreferReg) {
           AllowOverlap = false;
           dumpDisableOverlap(Func, Item.Var, "PrecoloredUnhandled");
         }
@@ skipping 36 matching lines @@
         Str << "\n";
       }
       assert(RegUses[RegNum] >= 0);
       ++RegUses[RegNum];
       Active.push_back(Cur);
     } else {
       // Fallback: there are no free registers, so we look for the
       // lowest-weight register and see if Cur has higher weight.
       std::vector<RegWeight> Weights(RegMask.size());
       // Check Active ranges.
-      for (UnorderedRanges::const_iterator I = Active.begin(), E = Active.end();
-           I != E; ++I) {
-        LiveRangeWrapper Item = *I;
+      for (const LiveRangeWrapper &Item : Active) {
         assert(Item.overlaps(Cur));
         int32_t RegNum = Item.Var->getRegNumTmp();
         assert(Item.Var->hasRegTmp());
         Weights[RegNum].addWeight(Item.range().getWeight());
       }
       // Same as above, but check Inactive ranges instead of Active.
-      for (UnorderedRanges::const_iterator I = Inactive.begin(),
-                                           E = Inactive.end();
-           I != E; ++I) {
-        LiveRangeWrapper Item = *I;
+      for (const LiveRangeWrapper &Item : Inactive) {
         int32_t RegNum = Item.Var->getRegNumTmp();
         assert(Item.Var->hasRegTmp());
         if (Item.overlaps(Cur))
           Weights[RegNum].addWeight(Item.range().getWeight());
       }
       // Check Unhandled ranges that overlap Cur and are precolored.
       // Cur.endsBefore(*I) is an early exit check that turns a
       // guaranteed O(N^2) algorithm into expected linear complexity.
-      for (OrderedRanges::const_iterator I = Unhandled.begin(),
-                                         E = Unhandled.end();
-           I != E && !Cur.endsBefore(*I); ++I) {
-        LiveRangeWrapper Item = *I;
+      for (const LiveRangeWrapper &Item : Unhandled) {
+        if (Cur.endsBefore(Item))
+          break;
         int32_t RegNum = Item.Var->getRegNumTmp();
         if (RegNum < 0)
           continue;
         if (Item.overlaps(Cur))
           Weights[RegNum].setWeight(RegWeight::Inf);
       }
 
       // All the weights are now calculated.  Find the register with
       // smallest weight.
       int32_t MinWeightIndex = RegMask.find_first();
@@ skipping 10 matching lines @@
         // don't allocate any register to it, and move it to the
         // Handled state.
         Handled.push_back(Cur);
         if (Cur.range().getWeight().isInf()) {
           Func->setError("Unable to find a physical register for an "
                          "infinite-weight live range");
         }
       } else {
         // Evict all live ranges in Active that register number
         // MinWeightIndex is assigned to.
-        for (UnorderedRanges::iterator I = Active.begin(), E = Active.end();
-             I != E; I = Next) {
+        for (auto I = Active.begin(), E = Active.end(); I != E; I = Next) {
           Next = I;
           ++Next;
           LiveRangeWrapper Item = *I;
           if (Item.Var->getRegNumTmp() == MinWeightIndex) {
             if (Verbose) {
               Str << "Evicting     ";
               Item.dump(Func);
               Str << "\n";
             }
             --RegUses[MinWeightIndex];
             assert(RegUses[MinWeightIndex] >= 0);
             Item.Var->setRegNumTmp(Variable::NoRegister);
             Active.erase(I);
             Handled.push_back(Item);
           }
         }
         // Do the same for Inactive.
-        for (UnorderedRanges::iterator I = Inactive.begin(), E = Inactive.end();
-             I != E; I = Next) {
+        for (auto I = Inactive.begin(), E = Inactive.end(); I != E; I = Next) {
           Next = I;
           ++Next;
           LiveRangeWrapper Item = *I;
           // Note: The Item.overlaps(Cur) clause is not part of the
           // description of AssignMemLoc() in the original paper.  But
           // there doesn't seem to be any need to evict an inactive
           // live range that doesn't overlap with the live range
           // currently being considered.  It's especially bad if we
           // would end up evicting an infinite-weight but
           // currently-inactive live range.  The most common situation
@@ skipping 19 matching lines @@
         if (Verbose) {
           Str << "Allocating   ";
           Cur.dump(Func);
           Str << "\n";
         }
       }
     }
     dump(Func);
   }
   // Move anything Active or Inactive to Handled for easier handling.
-  for (UnorderedRanges::iterator I = Active.begin(), E = Active.end(); I != E;
-       I = Next) {
-    Next = I;
-    ++Next;
-    Handled.push_back(*I);
-    Active.erase(I);
-  }
-  for (UnorderedRanges::iterator I = Inactive.begin(), E = Inactive.end();
-       I != E; I = Next) {
-    Next = I;
-    ++Next;
-    Handled.push_back(*I);
-    Inactive.erase(I);
-  }
+  for (const LiveRangeWrapper &I : Active)
+    Handled.push_back(I);
+  Active.clear();
+  for (const LiveRangeWrapper &I : Inactive)
+    Handled.push_back(I);
+  Inactive.clear();
   dump(Func);
 
   // Finish up by assigning RegNumTmp->RegNum for each Variable.
-  for (UnorderedRanges::const_iterator I = Handled.begin(), E = Handled.end();
-       I != E; ++I) {
-    LiveRangeWrapper Item = *I;
+  for (const LiveRangeWrapper &Item : Handled) {
     int32_t RegNum = Item.Var->getRegNumTmp();
     if (Verbose) {
       if (!Item.Var->hasRegTmp()) {
         Str << "Not assigning ";
         Item.Var->dump(Func);
         Str << "\n";
       } else {
         Str << (RegNum == Item.Var->getRegNum() ? "Reassigning " : "Assigning ")
             << Func->getTarget()->getRegName(RegNum, IceType_i32) << "(r"
             << RegNum << ") to ";
@@ skipping 28 matching lines @@
   Str << "  Range=" << range();
 }
 
 void LinearScan::dump(Cfg *Func) const {
   Ostream &Str = Func->getContext()->getStrDump();
   if (!Func->getContext()->isVerbose(IceV_LinearScan))
     return;
   Func->resetCurrentNode();
   Str << "**** Current regalloc state:\n";
   Str << "++++++ Handled:\n";
-  for (UnorderedRanges::const_iterator I = Handled.begin(), E = Handled.end();
-       I != E; ++I) {
-    I->dump(Func);
+  for (const LiveRangeWrapper &Item : Handled) {
+    Item.dump(Func);
     Str << "\n";
   }
   Str << "++++++ Unhandled:\n";
-  for (OrderedRanges::const_iterator I = Unhandled.begin(), E = Unhandled.end();
-       I != E; ++I) {
-    I->dump(Func);
+  for (const LiveRangeWrapper &Item : Unhandled) {
+    Item.dump(Func);
     Str << "\n";
   }
   Str << "++++++ Active:\n";
-  for (UnorderedRanges::const_iterator I = Active.begin(), E = Active.end();
-       I != E; ++I) {
-    I->dump(Func);
+  for (const LiveRangeWrapper &Item : Active) {
+    Item.dump(Func);
     Str << "\n";
   }
   Str << "++++++ Inactive:\n";
-  for (UnorderedRanges::const_iterator I = Inactive.begin(), E = Inactive.end();
-       I != E; ++I) {
-    I->dump(Func);
+  for (const LiveRangeWrapper &Item : Inactive) {
+    Item.dump(Func);
     Str << "\n";
   }
 }
 
 } // end of namespace Ice