Short Circuit Evaluation

src/IceCfg.cpp

Index: src/IceCfg.cpp
diff --git a/src/IceCfg.cpp b/src/IceCfg.cpp
index 8f6a2fffaca0ecbf8d040b895458c0b33bb69895..74430f5969207878597e43d765b80989c74307ba 100644
--- a/src/IceCfg.cpp
+++ b/src/IceCfg.cpp
@@ -633,6 +633,40 @@ 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 Nodes = this->getNodes();

[Jim Stichnoth, 2016/06/20 18:41:41]

Cfg::getNodes() returns "const NodeList &".  So I'm guessing this use of "auto"
is returning a copy of the node list rather than a reference to the master list.
 Is that what you intended?

Also, I already commented privately, but I'll repeat it here for the record. 
When I tested this patch, I saw that new nodes are being added to the end of
node list, and not necessarily added at the proper topological position.  This
makes the result code more branchy, and also slows down convergence of liveness
analysis.  (Also, it might make live range representation more fragmented which
can slow down register allocation.)

+  while (!Nodes.empty()) {
+    auto Node = Nodes.back();

[John, 2016/06/16 13:41:10]

auto*

+    Nodes.pop_back();
+    auto NewNode = Node->shortCircuit();
+    if (NewNode)
+      Nodes.push_back(NewNode);

[John, 2016/06/16 13:41:10]

(I think) You are missing short circuiting opportunities here: the algorithm
only short circuits a single operand per block, not the whole control
expression. How about adding a Nodes.push_back(Node) here, and let the algorithm
work on Node again?

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