[Subzero][MIPS32] Addition of bool folding machinery and implementation of conditional branches

src/IceTargetLoweringMIPS32.cpp

Index: src/IceTargetLoweringMIPS32.cpp
diff --git a/src/IceTargetLoweringMIPS32.cpp b/src/IceTargetLoweringMIPS32.cpp
index cbfad693619260aa00cd2b05f75316550c1e97d7..46718f6fe0b57d0156d277c4aa79e7f1fcf35e71 100644
--- a/src/IceTargetLoweringMIPS32.cpp
+++ b/src/IceTargetLoweringMIPS32.cpp
@@ -22,6 +22,7 @@
 #include "IceELFObjectWriter.h"
 #include "IceGlobalInits.h"
 #include "IceInstMIPS32.h"
+#include "IceInstVarIter.h"
 #include "IceLiveness.h"
 #include "IceOperand.h"
 #include "IcePhiLoweringImpl.h"
@@ -813,7 +814,78 @@ void TargetMIPS32::lowerBr(const InstBr *Instr) {
     _br(Instr->getTargetUnconditional());
     return;
   }
-  UnimplementedLoweringError(this, Instr);
+  CfgNode *TargetTrue = Instr->getTargetTrue();
+  CfgNode *TargetFalse = Instr->getTargetFalse();
+  Operand *Boolean = Instr->getCondition();
+  const Inst *Producer = Computations.getProducerOf(Boolean);
+  assert(Producer != nullptr);
+  if (Producer->getKind() == Inst::Icmp) {
+    const InstIcmp *CompareInst = llvm::cast<InstIcmp>(Producer);
+    Operand *Src0 = CompareInst->getSrc(0);
+    Operand *Src1 = CompareInst->getSrc(1);
+    const Type Src0Ty = Src0->getType();
+    const Type Src1Ty = Src1->getType();
+    if (Src0Ty == IceType_i64 || Src1Ty == IceType_i64) {

[Jim Stichnoth, 2016/05/19 15:03:41]

Instead of testing both types against i64, I suggest something like:
  assert(Src0Ty == Src1Ty);
  if (Src0Ty == IceType_i64) {
    ...
  }

Actually, you'll get a compiler warning/error in a NOASSERT build because Src1Ty
is only used in the assert expression, so:
  assert(Src0Ty == CompareInst->getSrc(1));

[sagar.thakur, 2016/05/23 18:30:26]

Done.

+      UnimplementedLoweringError(this, Instr);
+      return;
+    }
+    auto *Src0R = legalizeToReg(Src0);
+    auto *Src1R = legalizeToReg(Src1);
+    auto *DestT = makeReg(Src0Ty);
+    switch (CompareInst->getCondition()) {
+    default:
+      break;
+    case InstIcmp::Eq: {
+      _br(TargetTrue, TargetFalse, Src0R, Src1R, CondMIPS32::Cond::NE);
+      break;
+    }
+    case InstIcmp::Ne: {
+      _br(TargetTrue, TargetFalse, Src0R, Src1R, CondMIPS32::Cond::EQ);
+      break;
+    }
+    case InstIcmp::Ugt: {
+      _sltu(DestT, Src1R, Src0R);
+      _br(TargetTrue, TargetFalse, DestT, NULL, CondMIPS32::Cond::EQZ);

[Jim Stichnoth, 2016/05/19 15:03:41]

All the NULL should be nullptr.

[sagar.thakur, 2016/05/23 18:30:26]

Done.

+      break;
+    }
+    case InstIcmp::Uge: {
+      _sltu(DestT, Src0R, Src1R);
+      _br(TargetTrue, TargetFalse, DestT, NULL, CondMIPS32::Cond::NEZ);
+      break;
+    }
+    case InstIcmp::Ult: {
+      _sltu(DestT, Src0R, Src1R);
+      _br(TargetTrue, TargetFalse, DestT, NULL, CondMIPS32::Cond::EQZ);
+      break;
+    }
+    case InstIcmp::Ule: {
+      _sltu(DestT, Src1R, Src0R);
+      _br(TargetTrue, TargetFalse, DestT, NULL, CondMIPS32::Cond::NEZ);
+      break;
+    }
+    case InstIcmp::Sgt: {
+      _slt(DestT, Src1R, Src0R);
+      _br(TargetTrue, TargetFalse, DestT, NULL, CondMIPS32::Cond::EQZ);
+      break;
+    }
+    case InstIcmp::Sge: {
+      _slt(DestT, Src0R, Src1R);
+      _br(TargetTrue, TargetFalse, DestT, NULL, CondMIPS32::Cond::NEZ);
+      break;
+    }
+    case InstIcmp::Slt: {
+      _slt(DestT, Src0R, Src1R);
+      _br(TargetTrue, TargetFalse, DestT, NULL, CondMIPS32::Cond::EQZ);
+      break;
+    }
+    case InstIcmp::Sle: {
+      _slt(DestT, Src1R, Src0R);
+      _br(TargetTrue, TargetFalse, DestT, NULL, CondMIPS32::Cond::NEZ);
+      break;
+    }
+    }
+  }
+  return;

[John, 2016/05/19 14:59:59]

no need to "return" here.

[sagar.thakur, 2016/05/23 18:30:26]

Done.

 }
 
 void TargetMIPS32::lowerCall(const InstCall *Instr) {
@@ -1410,6 +1482,71 @@ Operand *TargetMIPS32::legalize(Operand *From, LegalMask Allowed,
   return From;
 }
 
+namespace BoolFolding {
+// TODO(sagar.thakur): Add remaining instruction kinds to shouldTrackProducer()
+// and isValidConsumer()
+bool shouldTrackProducer(const Inst &Instr) {
+  return Instr.getKind() == Inst::Icmp;
+}
+
+bool isValidConsumer(const Inst &Instr) { return Instr.getKind() == Inst::Br; }
+} // end of namespace BoolFolding
+
+void TargetMIPS32::ComputationTracker::recordProducers(CfgNode *Node) {
+  for (Inst &Instr : Node->getInsts()) {
+    // Check whether Instr is a valid producer.
+    Variable *Dest = Instr.getDest();
+    if (!Instr.isDeleted() // only consider non-deleted instructions; and

[Jim Stichnoth, 2016/05/19 15:03:41]

The isDeleted() check should be stronger.  The whole "for" loop should start
like this:
  for (Inst &Instr : Node->getInsts()) {
    if (Instr.isDeleted())
      continue;
    ...
  }

I think the x86 BoolFolding<Traits>::init() was changed to follow this form, but
not before TargetARM32::ComputationTracker::recordProducers() cloned the
original form.

The consequence of the code here as written is that the FOREACH_VAR_IN_INST loop
runs on deleted instructions and may inappropriately modify the bookkeeping.

I'll fix the ARM code as a separate CL, because I'd like to carefully look at
whether it makes any actual changes to the output.

[sagar.thakur, 2016/05/23 18:30:26]

Done.

+        && Dest            // only instructions with an actual dest var; and
+        && Dest->getType() == IceType_i1 // only bool-type dest vars; and
+        && BoolFolding::shouldTrackProducer(Instr)) { // white-listed instr.
+      KnownComputations.emplace(Dest->getIndex(),
+                                ComputationEntry(&Instr, IceType_i1));
+    }
+    // Check each src variable against the map.
+    FOREACH_VAR_IN_INST(Var, Instr) {
+      SizeT VarNum = Var->getIndex();
+      auto ComputationIter = KnownComputations.find(VarNum);
+      if (ComputationIter == KnownComputations.end()) {
+        continue;
+      }
+
+      ++ComputationIter->second.NumUses;
+      switch (ComputationIter->second.ComputationType) {
+      default:
+        KnownComputations.erase(VarNum);
+        continue;
+      case IceType_i1:
+        if (!BoolFolding::isValidConsumer(Instr)) {
+          KnownComputations.erase(VarNum);
+          continue;
+        }
+        break;
+      }
+
+      if (Instr.isLastUse(Var)) {
+        ComputationIter->second.IsLiveOut = false;
+      }
+    }
+  }
+
+  for (auto Iter = KnownComputations.begin(), End = KnownComputations.end();
+       Iter != End;) {
+    // Disable the folding if its dest may be live beyond this block.
+    if (Iter->second.IsLiveOut || Iter->second.NumUses > 1) {
+      Iter = KnownComputations.erase(Iter);
+      continue;
+    }
+
+    // Mark as "dead" rather than outright deleting. This is so that other
+    // peephole style optimizations during or before lowering have access to
+    // this instruction in undeleted form. See for example
+    // tryOptimizedCmpxchgCmpBr().
+    Iter->second.Instr->setDead();
+    ++Iter;
+  }
+}
+
 TargetHeaderMIPS32::TargetHeaderMIPS32(GlobalContext *Ctx)
     : TargetHeaderLowering(Ctx) {}