Subzero. ARM32. Implements bool folding.

src/IceTargetLoweringARM32.h

 //===- subzero/src/IceTargetLoweringARM32.h - ARM32 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 40 matching lines @@
 // The target lowering logic for ARM32.
 class TargetARM32 : public TargetLowering {
   TargetARM32() = delete;
   TargetARM32(const TargetARM32 &) = delete;
   TargetARM32 &operator=(const TargetARM32 &) = delete;
 
 public:
   // TODO(jvoung): return a unique_ptr.
   static TargetARM32 *create(Cfg *Func) { return new TargetARM32(Func); }
 
+  void initNodeForLowering(CfgNode *Node) override {
+    BoolComputations.forgetProducers();
+    BoolComputations.recordProducers(Node);
+    BoolComputations.dump(Func);
+  }
+
   void translateOm1() override;
   void translateO2() override;
   bool doBranchOpt(Inst *I, const CfgNode *NextNode) override;
 
   SizeT getNumRegisters() const override { return RegARM32::Reg_NUM; }
   Variable *getPhysicalRegister(SizeT RegNum, Type Ty = IceType_void) override;
   IceString getRegName(SizeT RegNum, Type Ty) const override;
   llvm::SmallBitVector getRegisterSet(RegSetMask Include,
                                       RegSetMask Exclude) const override;
   const llvm::SmallBitVector &getRegisterSetForType(Type Ty) const override {
@@ skipping 52 matching lines @@
 
   void postLower() override;
 
   void lowerAlloca(const InstAlloca *Inst) override;
   void lowerArithmetic(const InstArithmetic *Inst) override;
   void lowerAssign(const InstAssign *Inst) override;
   void lowerBr(const InstBr *Inst) override;
   void lowerCall(const InstCall *Inst) override;
   void lowerCast(const InstCast *Inst) override;
   void lowerExtractElement(const InstExtractElement *Inst) override;
-  void lowerFcmp(const InstFcmp *Inst) override;
-  void lowerIcmp(const InstIcmp *Inst) override;
+  void lowerFcmpCond(const InstFcmp *Instr, CondARM32::Cond *CondIfTrue0,
+                     CondARM32::Cond *CondIfTrue1,
+                     CondARM32::Cond *CondIfFalse);
+  void lowerFcmp(const InstFcmp *Instr) override;
+  void lowerIcmpCond(const InstIcmp *Instr, CondARM32::Cond *CondIfTrue,
+                     CondARM32::Cond *CondIfFalse);
+  void lowerIcmp(const InstIcmp *Instr) override;
   void lowerAtomicRMW(Variable *Dest, uint32_t Operation, Operand *Ptr,
                       Operand *Val);
   void lowerIntrinsicCall(const InstIntrinsicCall *Inst) override;
   void lowerInsertElement(const InstInsertElement *Inst) override;
   void lowerLoad(const InstLoad *Inst) override;
   void lowerPhi(const InstPhi *Inst) override;
   void lowerRet(const InstRet *Inst) override;
   void lowerSelect(const InstSelect *Inst) override;
   void lowerStore(const InstStore *Inst) override;
   void lowerSwitch(const InstSwitch *Inst) override;
@@ skipping 164 matching lines @@
     auto *Instr = InstARM32Mov::create(Func, Dest, Src0, Pred);
     Instr->setDestRedefined();
     Context.insert(Instr);
     if (Instr->isMultiDest()) {
       // If Instr is multi-dest, then Dest must be a Variable64On32. We add a
       // fake-def for Instr.DestHi here.
       assert(llvm::isa<Variable64On32>(Dest));
       Context.insert(InstFakeDef::create(Func, Instr->getDestHi()));
     }
   }
+
+  // _mov_i1_to_flags is used for bool folding. If "Boolean" is folded, this
+  // method returns true, and sets "CondIfTrue0" and "CondIfTrue1" to the
+  // appropriate ARM condition codes. If "Boolean" is not to be folded, then this
+  // method returns false.
+  bool _mov_i1_to_flags(Operand *Boolean, CondARM32::Cond *CondIfTrue0,
+                        CondARM32::Cond *CondIfTrue1,
+                        CondARM32::Cond *CondIfFalse);
+
+  // _cmov is a pseudo instruction that is used for boolean folding. It emits
+  // code that moves "SrcIfTrue" to dest if either "CondIfTrue0" or
+  // "CondIfTrue1" holds, and "SrcIfFalse", if "CondIfFalse" holds. It requires
+  // "Dest" to be an infinite-weight temporary.
+  void _cmov(Variable *Dest, Operand *SrcIfTrue, CondARM32::Cond CondIfTrue0,
+             CondARM32::Cond CondIfTrue1, Operand *SrcIfFalse,
+             CondARM32::Cond CondIfFalse) {
+    assert(Dest->mustHaveReg());
+
+    if (CondIfFalse == CondARM32::kNone) {
+      assert(CondIfTrue0 == CondARM32::AL);
+      assert(CondIfTrue1 == CondARM32::kNone);
+    }
+
+    if (CondIfTrue0 == CondARM32::kNone) {
+      assert(CondIfFalse == CondARM32::AL);
+      assert(CondIfTrue1 == CondARM32::kNone);
+    }
+
+    if (CondIfTrue1 != CondARM32::kNone) {
+      assert(CondIfFalse == CondARM32::AL);
+      assert(CondIfTrue1 != CondARM32::kNone);
+    }
+
+    bool RedefineT = false;
+    if (CondIfFalse != CondARM32::kNone) {
+      _mov(Dest, SrcIfFalse, CondIfFalse);
+      RedefineT = true;
+    }
+
+    if (CondIfTrue0 != CondARM32::kNone) {
+      if (RedefineT) {
+        _mov_redefined(Dest, SrcIfTrue, CondIfTrue0);
+      } else {
+        _mov(Dest, SrcIfTrue, CondIfTrue0);
+      }
+      RedefineT = true;
+    }
+
+    if (CondIfTrue1 != CondARM32::kNone) {
+      assert(RedefineT);
+      _mov_redefined(Dest, SrcIfTrue, CondIfTrue1);
+    }
+  }
+
   /// The Operand can only be a 16-bit immediate or a ConstantRelocatable (with
   /// an upper16 relocation).
   void _movt(Variable *Dest, Operand *Src0,
              CondARM32::Cond Pred = CondARM32::AL) {
     Context.insert(InstARM32Movt::create(Func, Dest, Src0, Pred));
   }
   void _movw(Variable *Dest, Operand *Src0,
              CondARM32::Cond Pred = CondARM32::AL) {
     Context.insert(InstARM32Movw::create(Func, Dest, Src0, Pred));
   }
@@ skipping 206 matching lines @@
 
   private:
     uint32_t NumGPRRegsUsed = 0;
     llvm::SmallBitVector VFPRegsFree;
     llvm::SmallBitVector ValidF64Regs;
     llvm::SmallBitVector ValidV128Regs;
   };
 
 private:
   ~TargetARM32() override = default;
+
+  void lowerTruncToFlags(Operand *Src, CondARM32::Cond *CondIfTrue,
+                         CondARM32::Cond *CondIfFalse);
+  class BoolComputationTracker {
+  public:
+    BoolComputationTracker() = default;
+    ~BoolComputationTracker() = 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 BoolComputationEntry {
+    public:
+      explicit BoolComputationEntry(Inst *I) : Instr(I) {}
+      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;
+    };
+
+    using BoolComputationMap = std::unordered_map<SizeT, BoolComputationEntry>;
+    BoolComputationMap KnownComputations;
+  };
+
+  BoolComputationTracker BoolComputations;
 };
 
 class TargetDataARM32 final : public TargetDataLowering {
   TargetDataARM32() = delete;
   TargetDataARM32(const TargetDataARM32 &) = delete;
   TargetDataARM32 &operator=(const TargetDataARM32 &) = delete;
 
 public:
   static std::unique_ptr<TargetDataLowering> create(GlobalContext *Ctx) {
     return std::unique_ptr<TargetDataLowering>(new TargetDataARM32(Ctx));
@@ skipping 28 matching lines @@
 
 private:
   ~TargetHeaderARM32() = default;
 
   TargetARM32Features CPUFeatures;
 };
 
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICETARGETLOWERINGARM32_H