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

src/IceTargetLoweringMIPS32.h

 //===- subzero/src/IceTargetLoweringMIPS32.h - MIPS32 lowering ---*- C++-*-===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 28 matching lines @@
     return false;
   }
   static std::unique_ptr<::Ice::TargetLowering> create(Cfg *Func) {
     return makeUnique<TargetMIPS32>(Func);
   }
 
   std::unique_ptr<::Ice::Assembler> createAssembler() const override {
     return makeUnique<MIPS32::AssemblerMIPS32>();
   }
 
+  void initNodeForLowering(CfgNode *Node) override {
+    Computations.forgetProducers();
+    Computations.recordProducers(Node);
+    Computations.dump(Func);
+  }
+
   void translateOm1() override;
   void translateO2() override;
   bool doBranchOpt(Inst *Instr, const CfgNode *NextNode) override;
 
   SizeT getNumRegisters() const override { return RegMIPS32::Reg_NUM; }
   Variable *getPhysicalRegister(RegNumT RegNum,
                                 Type Ty = IceType_void) override;
   const char *getRegName(RegNumT RegNum, Type Ty) const override;
   SmallBitVector getRegisterSet(RegSetMask Include,
                                 RegSetMask Exclude) const override;
@@ skipping 86 matching lines @@
   void _addu(Variable *Dest, Variable *Src0, Variable *Src1) {
     Context.insert<InstMIPS32Addu>(Dest, Src0, Src1);
   }
 
   void _and(Variable *Dest, Variable *Src0, Variable *Src1) {
     Context.insert<InstMIPS32And>(Dest, Src0, Src1);
   }
 
   void _br(CfgNode *Target) { Context.insert<InstMIPS32Br>(Target); }
 
+  void _br(CfgNode *TargetTrue, CfgNode *TargetFalse, Operand *Src0,
+           Operand *Src1, CondMIPS32::Cond Condition) {
+    Context.insert<InstMIPS32Br>(TargetTrue, TargetFalse, Src0, Src1,
+                                 Condition);
+  }
+
   void _ret(Variable *RA, Variable *Src0 = nullptr) {
     Context.insert<InstMIPS32Ret>(RA, Src0);
   }
 
   void _addiu(Variable *Dest, Variable *Src, uint32_t Imm) {
     Context.insert<InstMIPS32Addiu>(Dest, Src, Imm);
   }
 
   void _lui(Variable *Dest, uint32_t Imm) {
     Context.insert<InstMIPS32Lui>(Dest, Imm);
@@ skipping 177 matching lines @@
   bool UsesFramePointer = false;
   bool NeedsStackAlignment = false;
   static SmallBitVector TypeToRegisterSet[RCMIPS32_NUM];
   static SmallBitVector TypeToRegisterSetUnfiltered[RCMIPS32_NUM];
   static SmallBitVector RegisterAliases[RegMIPS32::Reg_NUM];
   SmallBitVector RegsUsed;
   VarList PhysicalRegisters[IceType_NUM];
 
 private:
   ENABLE_MAKE_UNIQUE;
+
+  class ComputationTracker {
+  public:
+    ComputationTracker() = default;
+    ~ComputationTracker() = default;
+
+    void forgetProducers() { KnownComputations.clear(); }
+    void recordProducers(CfgNode *Node);
+
+    const Inst *getProducerOf(const Operand *Opnd) const {
+      auto *Var = llvm::dyn_cast<Variable>(Opnd);
+      if (Var == nullptr) {
+        return nullptr;
+      }
+
+      auto Iter = KnownComputations.find(Var->getIndex());
+      if (Iter == KnownComputations.end()) {
+        return nullptr;
+      }
+
+      return Iter->second.Instr;
+    }
+
+    void dump(const Cfg *Func) const {
+      if (!BuildDefs::dump() || !Func->isVerbose(IceV_Folding))
+        return;
+      OstreamLocker L(Func->getContext());
+      Ostream &Str = Func->getContext()->getStrDump();
+      Str << "foldable producer:\n";
+      for (const auto &Computation : KnownComputations) {
+        Str << "    ";
+        Computation.second.Instr->dump(Func);
+        Str << "\n";
+      }
+      Str << "\n";
+    }
+
+  private:
+    class ComputationEntry {
+    public:
+      ComputationEntry(Inst *I, Type Ty) : Instr(I), ComputationType(Ty) {}
+      Inst *const Instr;
+      // Boolean folding is disabled for variables whose live range is multi
+      // block. We conservatively initialize IsLiveOut to true, and set it to
+      // false once we find the end of the live range for the variable defined
+      // by this instruction. If liveness analysis is not performed (e.g., in
+      // Om1 mode) IsLiveOut will never be set to false, and folding will be
+      // disabled.
+      bool IsLiveOut = true;
+      int32_t NumUses = 0;
+      Type ComputationType;
+    };
+
+    // ComputationMap maps a Variable number to a payload identifying which
+    // instruction defined it.
+    using ComputationMap = CfgUnorderedMap<SizeT, ComputationEntry>;
+    ComputationMap KnownComputations;
+  };
+
+  ComputationTracker Computations;
 };
 
 class TargetDataMIPS32 final : public TargetDataLowering {
   TargetDataMIPS32() = delete;
   TargetDataMIPS32(const TargetDataMIPS32 &) = delete;
   TargetDataMIPS32 &operator=(const TargetDataMIPS32 &) = delete;
 
 public:
   static std::unique_ptr<TargetDataLowering> create(GlobalContext *Ctx) {
     return std::unique_ptr<TargetDataLowering>(new TargetDataMIPS32(Ctx));
@@ skipping 28 matching lines @@
   explicit TargetHeaderMIPS32(GlobalContext *Ctx);
 
 private:
   ~TargetHeaderMIPS32() = default;
 };
 
 } // end of namespace MIPS32
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICETARGETLOWERINGMIPS32_H