Short Circuit Evaluation

src/IceCfgNode.cpp

Index: src/IceCfgNode.cpp
diff --git a/src/IceCfgNode.cpp b/src/IceCfgNode.cpp
index 78e3d18f414a94f1baa6f68923eb977604f30f42..7c59827f801945e4796e137ba39ec1358ea63a5b 100644
--- a/src/IceCfgNode.cpp
+++ b/src/IceCfgNode.cpp
@@ -51,6 +51,22 @@ void CfgNode::appendInst(Inst *Instr) {
   }
 }
 
+void CfgNode::replaceInEdge(CfgNode *Old, CfgNode *New) {
+  for (SizeT i = 0; i < InEdges.size(); ++i) {
+    if (InEdges[i] == Old) {
+      InEdges[i] = New;
+    }
+  }
+  for (auto &Inst : getPhis()) {
+    InstPhi &Phi = llvm::cast<InstPhi>(Inst);
+    for (SizeT i = 0; i < Phi.getSrcSize(); ++i) {
+      if (Phi.getLabel(i) == Old) {
+        Phi.setLabel(i, New);
+      }
+    }
+  }
+}
+
 namespace {
 template <typename List> void removeDeletedAndRenumber(List *L, Cfg *Func) {
   const bool DoDelete =
@@ -1471,5 +1487,156 @@ void CfgNode::profileExecutionCount(VariableDeclaration *Var) {
   Instr->addArg(OrderAcquireRelease);
   Insts.push_front(Instr);
 }
+void CfgNode::removeInEdge(CfgNode *In) {

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

add empty line before function definition?

[manasijm, 2016/06/20 20:45:36]

Done.

+  InEdges.erase(std::find(InEdges.begin(), InEdges.end(), In));
+}
+CfgNode *CfgNode::shortCircuit() {

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

add empty line before function definition?

[manasijm, 2016/06/20 20:45:36]

Done.

+  auto *Func = getCfg();
+  auto *Last = &getInsts().back();
+  Variable *Goal = nullptr;

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

How about renaming this variable (Goal) to Condition...

[manasijm, 2016/06/20 20:45:36]

Done.

+  InstBr *Br = nullptr;
+  if ((Br = llvm::dyn_cast<InstBr>(Last))) {
+    if (!Br->isUnconditional()) {
+      Goal = llvm::dyn_cast<Variable>(Br->getCondition());
+    }
+  }
+  if (Goal == nullptr)
+    return nullptr;
+
+  auto *JumpOnTrue = Br->getTargetTrue();
+  auto *JumpOnFalse = Br->getTargetFalse();
+
+  bool FoundOr = false;
+  bool FoundAnd = false;
+
+  CfgUnorderedSet<Variable *> Operands;

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

Instead of creating the unordered set, save a pointer to the instruction.
Remember, these Cfg* data structures allocate data in the CFG local allocator,
and that data will live on until subzero's done lowering the CFG.

[manasijm, 2016/06/20 20:45:36]

Done.

+  InstArithmetic *TopLevelBoolOp = nullptr;
+
+  for (auto &Inst : reverse_range(getInsts())) {
+    if (Inst.isDeleted())
+      continue;
+    if (Inst.getDest() == Goal) {
+      if (auto *Arith = llvm::dyn_cast<InstArithmetic>(&Inst)) {
+
+        FoundOr = (Arith->getOp() == InstArithmetic::OpKind::Or);
+        FoundAnd = (Arith->getOp() == InstArithmetic::OpKind::And);
+
+        if (FoundOr || FoundAnd) {
+          for (SizeT i = 0; i < Arith->getSrcSize(); ++i) {
+            if (auto *Var = llvm::dyn_cast<Variable>(Arith->getSrc(i))) {
+              Operands.insert(Var);
+            }
+          }
+          TopLevelBoolOp = Arith;
+          break;
+        }
+      }
+    }
+  }
+
+  Inst *FirstOperandDef = nullptr;
+  if ((FoundAnd || FoundOr) && Operands.size() > 1) {

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

This seems to be optimizing the

a = or i32 x, x

and

a = and i32 x, x

You can still do something sensible here. Just delete the instruction and add a
mov a = x.

+    for (auto &Inst : getInsts()) {
+      if (Operands.find(Inst.getDest()) != Operands.end()) {
+        FirstOperandDef = &Inst;
+        break;
+      }
+    }
+  } else {
+    return nullptr;
+  }
+  if (FirstOperandDef == nullptr) {

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

this should never happens, by contruction, right? If so, add an

assert(false);

[manasijm, 2016/06/20 20:45:36]

It could happen for valid code, if the condition of the br instruction was
defined in another basic block.

+    return nullptr;
+  }
+
+  // Check for side effects, might be too conservative. Checking for last use
+  // instead of isSingleBlock might introduce more opportunities.

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

actually, there are good reasons for this.

1) you need some sort of liveness analysis for last use -- which might not be
available when this is running.

2) it's better to avoid adding multi-block variables to avoid increasing the
site of the liveness bit vectors.

[manasijm, 2016/06/20 20:45:36]

Acknowledged.

+  auto It = Ice::instToIterator(FirstOperandDef);
+  bool hasSideEffects = false;
+  while (It != getInsts().end()) {
+    if (It->isDeleted()) {
+      It++;
+      continue;
+    }
+    if (llvm::isa<InstBr>(It) || llvm::isa<InstRet>(It)) {
+      break;
+    }
+    auto Dest = It->getDest();

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

auto*

+    if (It->getDest() == nullptr || It->hasSideEffects() ||
+        !Func->getVMetadata()->isSingleBlock(Dest)) {
+      // Relying on short cicuit eval here.
+      // getVMetadata()->isSingleBlock(Dest)
+      // will segfault if It->getDest() == nullptr
+      hasSideEffects = true;

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

just return nullptr here?

[manasijm, 2016/06/20 20:45:36]

Done.

+    }
+    if (hasSideEffects) {
+      break;
+    }
+    It++;
+  }
+
+  if (hasSideEffects) {
+    return nullptr;
+  }
+
+  auto *NewNode = Func->makeNode();
+  NewNode->setLoopNestDepth(getLoopNestDepth());
+  It = Ice::instToIterator(FirstOperandDef);
+  It++; // Have to split after the def
+
+  NewNode->getInsts().splice(NewNode->getInsts().begin(), getInsts(), It,
+                             getInsts().end());
+
+  NewNode->setName(getName().append("_ext_"));
+
+  // Point edges properly
+  NewNode->addInEdge(this);
+  for (auto *Out : getOutEdges()) {
+    NewNode->addOutEdge(Out);
+    Out->addInEdge(NewNode);
+  }
+  removeAllOutEdges();
+  addOutEdge(NewNode);
+
+  //Manage Phi instructions of successors
+  for (auto *Succ : NewNode->getOutEdges()) {
+    for (auto &Inst : Succ->getPhis()) {
+      auto *Phi = llvm::dyn_cast<InstPhi>(&Inst);
+      for (SizeT i = 0; i < Phi->getSrcSize(); ++i) {
+        if (Phi->getLabel(i) == this) {
+          Phi->addArgument(Phi->getSrc(i), NewNode);
+        }
+      }
+    }
+  }
+
+  //Create new Br instruction
+  InstBr *NewInst = nullptr;
+  if (FoundOr) {
+    addOutEdge(JumpOnTrue);
+    JumpOnFalse->removeInEdge(this);
+    NewInst =
+        InstBr::create(Func, FirstOperandDef->getDest(), JumpOnTrue, NewNode);
+  } else if (FoundAnd) {
+    addOutEdge(JumpOnFalse);
+    JumpOnTrue->removeInEdge(this);
+    NewInst =
+        InstBr::create(Func, FirstOperandDef->getDest(), NewNode, JumpOnFalse);
+  }
+  appendInst(NewInst);
+
+  Operand *UnusedOperand = nullptr;
+  assert(TopLevelBoolOp->getSrcSize() == 2);
+  if (TopLevelBoolOp->getSrc(0) == FirstOperandDef->getDest())
+    UnusedOperand = TopLevelBoolOp->getSrc(1);
+  else if (TopLevelBoolOp->getSrc(1) == FirstOperandDef->getDest())
+    UnusedOperand = TopLevelBoolOp->getSrc(0);
+  assert(UnusedOperand);
+
+  Br->replaceSource(0, UnusedOperand); // Index 0 has the condition of the Br
+
+  TopLevelBoolOp->setDeleted();
+  return NewNode;
+}
 
 } // end of namespace Ice