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 fold, this

[Jim Stichnoth, 2015/11/03 20:04:28]

There are a few places in comments where I think "fold" might be more properly
"folded" - take a second look and verify?

[John, 2015/11/05 20:25:39]

Done.

+  // method returns true, and sets "CondIfTrue0" and "CondIfTrue1" to the
+  // appropriate ARM condition codes. If "Boolean" is not to be fold, 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 fol boolean folding. It emits

[Jim Stichnoth, 2015/11/03 20:04:28]

for

[John, 2015/11/05 20:25:39]

Done.

+  // 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:
+    struct BoolComputationEntry {

[Jim Stichnoth, 2015/11/03 20:04:28]

Make this class instead of struct?

I'm not sure what various style guides have to say on the matter, but in Subzero
we've generally used "class" whenever there are actual methods defined,
including ctor/dtor.  Most if not all of the exceptions are from following
"standard" STL documentation for defining functors, or allocators, or whatnot.

[John, 2015/11/05 20:25:39]

I tend to think of classes as "data with behavior," and structs and "glorified
PODs." I also think "how hard would it be to replace this type with an
std::tuple<>?" If it is trivial, than the type is a struct; otherwise is a
class. Done anyway.

+      explicit BoolComputationEntry(Inst *I) : Instr(I) {}
+      Inst *Instr;

[Jim Stichnoth, 2015/11/03 20:04:28]

How about
  Inst *const Instr;
?

[John, 2015/11/05 20:25:39]

Done.

+      // 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