Introduction of improved switch lowering.

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.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 195 matching lines @@
 void CfgNode::deletePhis() {
   for (Inst &I : Phis)
     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
-// edge is undefined.  This could happen with a switch instruction, or
-// a conditional branch that weirdly has both branches to the same
-// place.  TODO(stichnot,kschimpf): Figure out whether this is legal
-// in the LLVM IR or the PNaCl bitcode, and if so, we need to
-// establish a strong relationship among the ordering of Pred's
-// out-edge list, this node's in-edge list, and the Phi instruction's
-// operand list.
+// terminator instruction. There must not be multiple edges from Pred
+// to this node so all Inst::getTerminatorEdges implementations must
+// not contain duplicates.
 CfgNode *CfgNode::splitIncomingEdge(CfgNode *Pred, SizeT EdgeIndex) {
   CfgNode *NewNode = Func->makeNode();
   if (BuildDefs::dump())
     NewNode->setName("split_" + Pred->getName() + "_" + getName() + "_" +
                      std::to_string(EdgeIndex));
   // The new node is added to the end of the node list, and will later
   // need to be sorted into a reasonable topological order.
   NewNode->setNeedsPlacement(true);
   // Repoint Pred's out-edge.
   bool Found = false;
-  for (auto I = Pred->OutEdges.begin(), E = Pred->OutEdges.end();
-       !Found && I != E; ++I) {
-    if (*I == this) {
-      *I = NewNode;
+  for (CfgNode *&I : Pred->OutEdges) {
+    if (I == this) {
+      I = NewNode;
       NewNode->InEdges.push_back(Pred);
       Found = true;
+      break;
     }
   }
   assert(Found);
   // Repoint this node's in-edge.
   Found = false;
-  for (auto I = InEdges.begin(), E = InEdges.end(); !Found && I != E; ++I) {
-    if (*I == Pred) {
-      *I = NewNode;
+  for (CfgNode *&I : InEdges) {
+    if (I == Pred) {
+      I = NewNode;
       NewNode->OutEdges.push_back(this);
       Found = true;
+      break;
     }
   }
   assert(Found);
-  // Repoint a suitable branch instruction's target and return.
+  // Repoint all suitable branch instructions' target and return.
   Found = false;
-  for (Inst &I : reverse_range(Pred->getInsts())) {
-    if (!I.isDeleted() && I.repointEdge(this, NewNode))
-      return NewNode;
-  }
-  // This should be unreachable, so the assert will fail.
+  for (Inst &I : Pred->getInsts())
+    if (!I.isDeleted() && I.repointEdges(this, NewNode))
+      Found = true;
   assert(Found);
   return NewNode;
 }
 
 namespace {
 
 // Helper function used by advancedPhiLowering().
 bool sameVarOrReg(const Variable *Var, const Operand *Opnd) {
   if (Var == Opnd)
     return true;
@@ skipping 474 matching lines @@
     for (CfgNode *Pred : InEdges) {
       for (auto I = Pred->OutEdges.begin(), E = Pred->OutEdges.end(); I != E;
            ++I) {
         if (*I == this) {
           *I = OutEdges.front();
           OutEdges.front()->InEdges.push_back(Pred);
         }
       }
       for (Inst &I : Pred->getInsts()) {
         if (!I.isDeleted())
-          I.repointEdge(this, OutEdges.front());
+          I.repointEdges(this, OutEdges.front());
       }
     }
   }
   InEdges.clear();
   // Don't bother removing the single out-edge, which would also
   // require finding the corresponding in-edge in the successor and
   // removing it.
 }
 
 void CfgNode::doBranchOpt(const CfgNode *NextNode) {
@@ skipping 502 matching lines @@
   InstIntrinsicCall *Inst = InstIntrinsicCall::create(
       Func, 5, Func->makeVariable(IceType_i64), RMWI64Name, Info->Info);
   Inst->addArg(AtomicRMWOp);
   Inst->addArg(Counter);
   Inst->addArg(One);
   Inst->addArg(OrderAcquireRelease);
   Insts.push_front(Inst);
 }
 
 } // end of namespace Ice