Subzero: Fold icmp into br/select lowering.

src/IceTargetLoweringX8632.h

 //===- subzero/src/IceTargetLoweringX8632.h - x86-32 lowering ---*- C++ -*-===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file declares the TargetLoweringX8632 class, which
 // implements the TargetLowering interface for the x86-32
 // architecture.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef SUBZERO_SRC_ICETARGETLOWERINGX8632_H
 #define SUBZERO_SRC_ICETARGETLOWERINGX8632_H
 
+#include <unordered_map>
+
 #include "assembler_ia32.h"
 #include "IceDefs.h"
+#include "IceInst.h"
 #include "IceInstX8632.h"
 #include "IceRegistersX8632.h"
 #include "IceTargetLowering.h"
 
 namespace Ice {
 
+enum BoolFoldingProducerKind {

[jvoung (off chromium), 2015/05/15 21:48:20]

Can these be scoped in the TargetX8632 vs Ice, or maybe they can later be more
target independent?

[Jim Stichnoth, 2015/05/16 17:32:50]

It should probably be reasonable to refactor later to be target-independent, but
for now, I moved them into the BoolFolding class.

+  PK_None,
+  PK_Icmp32,
+  PK_Icmp64,
+  PK_Fcmp,
+  PK_Trunc
+};
+
+// Currently the actual enum values are not used (other than CK_None), but we go
+// ahead and produce them anyway for symmetry with the BoolFoldingProducerKind.
+enum BoolFoldingConsumerKind { CK_None, CK_Br, CK_Select, CK_Sext, CK_Zext };
+
+class BoolFoldingEntry {
+  BoolFoldingEntry(const BoolFoldingEntry &) = delete;
+
+public:
+  BoolFoldingEntry()
+      : Var(nullptr), Instr(nullptr), IsComplex(false), IsLiveOut(true),
+        NumUses(0) {}
+  explicit BoolFoldingEntry(Inst *I);
+  BoolFoldingEntry &operator=(const BoolFoldingEntry &) = default;
+  // Var is the i1-type variable produced by the instruction.
+  const Variable *Var;

[jvoung (off chromium), 2015/05/15 21:48:20]

Is the Var field used? Could the user just get it from the Instr->getDest() ?

[Jim Stichnoth, 2015/05/16 17:32:50]

Good point, done.

+  // Instr is the instruction whose dest is Var.
+  Inst *Instr;
+  // IsComplex is the cached result of BoolFolding::hasComplexLowering(Instr).
+  bool IsComplex;
+  // IsLiveOut is initialized conservatively to true, and is set to false when
+  // we encounter an instruction that ends Var's live range.  We disable the
+  // folding optimization when Var is live beyond this basic block.  Note that
+  // if liveness analysis is not performed (e.g. in Om1 mode), IsLiveOut will
+  // always be true and the folding optimization will never be performed.
+  bool IsLiveOut;
+  // NumUses counts the number of times Var is used as a source operand in the
+  // basic block.  If IsComplex is true and there is more than one use of Var,
+  // then the folding optimization is disabled for Var.
+  uint32_t NumUses;
+};
+
+class BoolFolding {
+  BoolFolding(const BoolFolding &) = delete;
+  BoolFolding &operator=(const BoolFolding &) = delete;
+
+public:
+  BoolFolding() {}
+  static BoolFoldingProducerKind getProducerKind(const Inst *Instr);
+  static BoolFoldingConsumerKind getConsumerKind(const Inst *Instr);
+  static bool hasComplexLowering(const Inst *Instr);
+  void init(CfgNode *Node);
+  const Inst *getProducerFor(const Operand *Opnd) const;
+  void dump(const Cfg *Func) const;
+
+private:
+  // Returns true if Producers contains a valid entry for the given VarNum.
+  bool containsValid(SizeT VarNum) const {
+    return Producers.find(VarNum) != Producers.end() &&

[jvoung (off chromium), 2015/05/15 21:48:20]

Would a compiler optimize the two lookups find() followed by at() ?

[Jim Stichnoth, 2015/05/16 17:32:50]

Probably, but the hand-"optimized" version is probably clearer as well. 
Changed.

+           Producers.at(VarNum).Instr != nullptr;
+  }
+  void setInvalid(SizeT VarNum) { Producers[VarNum].Instr = nullptr; }
+  // Producers maps Variable::Number to a BoolFoldingEntry.
+  std::unordered_map<SizeT, BoolFoldingEntry> Producers;
+};
+
 class TargetX8632 : public TargetLowering {
   TargetX8632() = delete;
   TargetX8632(const TargetX8632 &) = delete;
   TargetX8632 &operator=(const TargetX8632 &) = delete;
 
 public:
   static TargetX8632 *create(Cfg *Func) { return new TargetX8632(Func); }
 
   void translateOm1() override;
   void translateO2() override;
@@ skipping 19 matching lines @@
   void emitVariable(const Variable *Var) const override;
 
   const char *getConstantPrefix() const final { return "$"; }
   void emit(const ConstantUndef *C) const final;
   void emit(const ConstantInteger32 *C) const final;
   void emit(const ConstantInteger64 *C) const final;
   void emit(const ConstantFloat *C) const final;
   void emit(const ConstantDouble *C) const final;
 
   void lowerArguments() override;
+  void initNodeForLowering(CfgNode *Node) override;
   void addProlog(CfgNode *Node) override;
   void addEpilog(CfgNode *Node) override;
   // Ensure that a 64-bit Variable has been split into 2 32-bit
   // Variables, creating them if necessary.  This is needed for all
   // I64 operations, and it is needed for pushing F64 arguments for
   // function calls using the 32-bit push instruction (though the
   // latter could be done by directly writing to the stack).
   void split64(Variable *Var);
   void finishArgumentLowering(Variable *Arg, Variable *FramePtr,
                               size_t BasicFrameOffset, size_t &InArgsSizeBytes);
@@ skipping 424 matching lines @@
   size_t FrameSizeLocals;
   size_t SpillAreaSizeBytes;
   llvm::SmallBitVector TypeToRegisterSet[IceType_NUM];
   llvm::SmallBitVector ScratchRegs;
   llvm::SmallBitVector RegsUsed;
   VarList PhysicalRegisters[IceType_NUM];
   static IceString RegNames[];
 
 private:
   ~TargetX8632() override {}
+  BoolFolding FoldingInfo;
 };
 
 class TargetDataX8632 : public TargetDataLowering {
   TargetDataX8632() = delete;
   TargetDataX8632(const TargetDataX8632 &) = delete;
   TargetDataX8632 &operator=(const TargetDataX8632 &) = delete;
 
 public:
   static TargetDataLowering *create(GlobalContext *Ctx) {
     return new TargetDataX8632(Ctx);
   }
 
   void lowerGlobals(std::unique_ptr<VariableDeclarationList> Vars) const final;
   void lowerConstants() const final;
 
 protected:
   explicit TargetDataX8632(GlobalContext *Ctx);
 
 private:
   void lowerGlobal(const VariableDeclaration &Var) const;
   ~TargetDataX8632() override {}
   template <typename T> static void emitConstantPool(GlobalContext *Ctx);
 };
 
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICETARGETLOWERINGX8632_H