Short Circuit Evaluation

src/IceCfg.cpp

Index: src/IceCfg.cpp
diff --git a/src/IceCfg.cpp b/src/IceCfg.cpp
index 8f6a2fffaca0ecbf8d040b895458c0b33bb69895..45a7f56c71bd7c205d55526f86b76ea88814f66f 100644
--- a/src/IceCfg.cpp
+++ b/src/IceCfg.cpp
@@ -633,6 +633,68 @@ void Cfg::localCSE() {
   }
 }
 
+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.)
+
+  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
+    CfgVector<CfgNode *> Stack{Node};

[Jim Stichnoth, 2016/06/27 19:44:40]

Can you use NodeList instead of CfgVector<CfgNode *> ?

[manasijm, 2016/06/27 22:00:40]

Done.

+    while(!Stack.empty()) {

[Jim Stichnoth, 2016/06/27 19:44:40]

Please run "make format"...

[manasijm, 2016/06/27 22:00:40]

Acknowledged.

+      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);
+      }
+    }
+  }
+  for (SizeT i = 0; i < NewList.size(); ++i) {

[Jim Stichnoth, 2016/06/27 19:44:41]

I think it would be better to use a range-based for loop.

SizeT NodeIndex = 0;
for (auto *Node : NewList) {
  Node->resetIndex(NodeIndex++);
}

[manasijm, 2016/06/27 22:00:40]

Done.

+    NewList[i]->resetIndex(i);
+  }
+  Nodes = NewList;
+}
+

[Jim Stichnoth, 2016/06/27 19:44:40]

just one blank line here

[manasijm, 2016/06/27 22:00:40]

Done.

+
 void Cfg::doArgLowering() {
   TimerMarker T(TimerStack::TT_doArgLowering, this);
   getTarget()->lowerArguments();