Short Circuit Evaluation

src/IceCfg.cpp

 //===- subzero/src/IceCfg.cpp - Control flow graph implementation ---------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 622 matching lines @@
             if (auto *Var = llvm::dyn_cast<Variable>(Opnd)) {
               Dependency[Var].push_back(&Instr);
             }
           }
         }
       }
     }
   }
 }
 
+void Cfg::shortCircuitJumps() {
+  // Split Nodes whenever an early jump is possible.
+  // __N :
+  //   a = <something>
+  //   Instruction 1 without side effect
+  //   ... b = <something> ...
+  //   Instruction N without side effect
+  //   t1 = or a b
+  //   br t1 __X __Y
+  //
+  // is transformed into:
+  // __N :
+  //   a = <something>
+  //   br a __X __N_ext
+  //
+  // __N_ext :
+  //   Instruction 1 without side effect
+  //   ... b = <something> ...
+  //   Instruction N without side effect
+  //   br b __X __Y
+  //(Similar logic for AND, jump to false instead of true target.)

[Jim Stichnoth, 2016/06/27 22:41:59]

Can you add a space after the "//"?  I thought "make format" would do that but I
guess not.

+
+  TimerMarker T(TimerStack::TT_shortCircuit, this);
+  getVMetadata()->init(VMK_Uses);
+  auto NodeStack = this->getNodes();
+  CfgUnorderedMap<SizeT, CfgVector<CfgNode *>> Splits;
+  while (!NodeStack.empty()) {
+    auto *Node = NodeStack.back();
+    NodeStack.pop_back();
+    auto NewNode = Node->shortCircuit();
+    if (NewNode) {
+      NodeStack.push_back(NewNode);
+      NodeStack.push_back(Node);
+      Splits[Node->getIndex()].push_back(NewNode);
+    }
+  }
+
+  // Insert nodes in the right place
+  NodeList NewList;
+  NewList.reserve(Nodes.size());
+  CfgUnorderedSet<SizeT> Inserted;
+  for (auto *Node : Nodes) {
+    if (Inserted.find(Node->getIndex()) != Inserted.end())
+      continue; // already inserted
+    NodeList Stack{Node};
+    while (!Stack.empty()) {
+      auto *Current = Stack.back();
+      Stack.pop_back();
+      Inserted.insert(Current->getIndex());
+      NewList.push_back(Current);
+      for (auto *Next : Splits[Current->getIndex()]) {
+        Stack.push_back(Next);
+      }
+    }
+  }
+
+  SizeT NodeIndex = 0;
+  for (auto *Node : NewList) {
+    Node->resetIndex(NodeIndex++);
+  }
+  Nodes = NewList;
+}
+
 void Cfg::doArgLowering() {
   TimerMarker T(TimerStack::TT_doArgLowering, this);
   getTarget()->lowerArguments();
 }
 
 void Cfg::sortAndCombineAllocas(CfgVector<Inst *> &Allocas,
                                 uint32_t CombinedAlignment, InstList &Insts,
                                 AllocaBaseVariableType BaseVariableType) {
   if (Allocas.empty())
     return;
@@ skipping 958 matching lines @@
     }
   }
   // Print each basic block
   for (CfgNode *Node : Nodes)
     Node->dump(this);
   if (isVerbose(IceV_Instructions))
     Str << "}\n";
 }
 
 } // end of namespace Ice