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 615 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.)
+
+  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();
 }
 
 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