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