Subzero: Fold icmp into br/select lowering.

src/IceTargetLoweringX8632.h

Index: src/IceTargetLoweringX8632.h
diff --git a/src/IceTargetLoweringX8632.h b/src/IceTargetLoweringX8632.h
index f114dba2fbdb9abedd171557f7fe6184a043cb5e..55f2fb4e4fdb9b1c4bb9467d22aa9f6490dda86b 100644
--- a/src/IceTargetLoweringX8632.h
+++ b/src/IceTargetLoweringX8632.h
@@ -16,14 +16,80 @@
 #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;
@@ -63,6 +129,7 @@ public:
   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
@@ -507,6 +574,7 @@ protected:
 
 private:
   ~TargetX8632() override {}
+  BoolFolding FoldingInfo;
 };
 
 class TargetDataX8632 : public TargetDataLowering {