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

src/IceTargetLoweringMIPS32.cpp

 //===- subzero/src/IceTargetLoweringMIPS32.cpp - MIPS32 lowering ----------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// \brief Implements the TargetLoweringMIPS32 class, which consists almost
 /// entirely of the lowering sequence for each high-level instruction.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "IceTargetLoweringMIPS32.h"
 
 #include "IceCfg.h"
 #include "IceCfgNode.h"
 #include "IceClFlags.h"
 #include "IceDefs.h"
 #include "IceELFObjectWriter.h"
 #include "IceGlobalInits.h"
 #include "IceInstMIPS32.h"
+#include "IceInstVarIter.h"
 #include "IceLiveness.h"
 #include "IceOperand.h"
 #include "IcePhiLoweringImpl.h"
 #include "IceRegistersMIPS32.h"
 #include "IceTargetLoweringMIPS32.def"
 #include "IceUtils.h"
 #include "llvm/Support/MathExtras.h"
 
 namespace MIPS32 {
 std::unique_ptr<::Ice::TargetLowering> createTargetLowering(::Ice::Cfg *Func) {
@@ skipping 771 matching lines @@
       _mov(Dest, SrcR);
     }
   }
 }
 
 void TargetMIPS32::lowerBr(const InstBr *Instr) {
   if (Instr->isUnconditional()) {
     _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) {
   // TODO(rkotler): assign arguments to registers and stack. Also reserve stack.
   if (Instr->getNumArgs()) {
     UnimplementedLoweringError(this, Instr);
     return;
   }
   // Generate the call instruction.  Assign its result to a temporary with high
   // register allocation weight.
@@ skipping 576 matching lines @@
     //   RegNum is required and Var->getRegNum() doesn't match.
     if ((!(Allowed & Legal_Mem) && !MustHaveRegister) ||
         (RegNum.hasValue() && RegNum != Var->getRegNum())) {
       From = copyToReg(From, RegNum);
     }
     return From;
   }
   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) {}
 
 void TargetHeaderMIPS32::lower() {
   OstreamLocker L(Ctx);
   Ostream &Str = Ctx->getStrEmit();
   Str << "\t.set\t"
       << "nomicromips\n";
   Str << "\t.set\t"
       << "nomips16\n";
 }
 
 SmallBitVector TargetMIPS32::TypeToRegisterSet[RCMIPS32_NUM];
 SmallBitVector TargetMIPS32::TypeToRegisterSetUnfiltered[RCMIPS32_NUM];
 SmallBitVector TargetMIPS32::RegisterAliases[RegMIPS32::Reg_NUM];
 
 } // end of namespace MIPS32
 } // end of namespace Ice