Selectively invert ICMP operands for better address optimization

src/IceCfg.cpp

 //===- subzero/src/IceCfg.cpp - Control flow graph implementation ---------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 685 matching lines @@
     }
   }
 
   SizeT NodeIndex = 0;
   for (auto *Node : NewList) {
     Node->resetIndex(NodeIndex++);
   }
   Nodes = NewList;
 }
 
+void Cfg::invertICMP() {
+  for (auto *Node : getNodes()) {
+    for (auto &Inst : Node->getInsts()) {
+
+      if (auto *ICMP = llvm::dyn_cast<InstIcmp>(&Inst)) {

[John, 2016/07/07 21:20:56]

optional: Icmp instead of ICMP

[manasijm, 2016/07/07 22:43:35]

Done.

+        auto *Const0 = llvm::dyn_cast<Constant>(ICMP->getSrc(0));
+        auto *Const1 = llvm::dyn_cast<Constant>(ICMP->getSrc(1));
+        if (Const0 || Const1)

[Eric Holk, 2016/07/07 21:46:48]

Should this be (Const0 != nullptr || Const1 != nullptr), similarly to John's
comment on line 722?

[manasijm, 2016/07/07 22:43:35]

Acknowledged.

+          continue;
+        auto *Var0 = llvm::dyn_cast<Variable>(ICMP->getSrc(0));
+        auto *Var1 = llvm::dyn_cast<Variable>(ICMP->getSrc(1));
+        if (!Var0)

[Eric Holk, 2016/07/07 21:46:48]

Here too, Var0 == nullptr.

[manasijm, 2016/07/07 22:43:35]

Done.

+          continue;
+        if (!getVMetadata()->isTracked(Var0))
+          continue;
+        auto Op0Def = getVMetadata()->getFirstDefinitionSingleBlock(Var0);

[John, 2016/07/07 21:20:56]

are you missing a * here?

[manasijm, 2016/07/07 22:43:35]

Done.

+        if (!Op0Def || !llvm::isa<InstLoad>(Op0Def))

[John, 2016/07/07 21:20:55]

Op0Def == nullptr

[manasijm, 2016/07/07 22:43:35]

Done.

+          continue;
+        if (getVMetadata()->getLocalUseNode(Var0) != Node)
+          continue;
+

[John, 2016/07/07 21:20:55]

optional: define Var1 here, closer to where it is used...

[manasijm, 2016/07/07 22:43:35]

Done.

+        if (Var1 && getVMetadata()->isTracked(Var1)) {
+          auto Op1Def = getVMetadata()->getFirstDefinitionSingleBlock(Var1);

[John, 2016/07/07 21:20:55]

are you missing a * here?

[manasijm, 2016/07/07 22:43:35]

Done.

+          if (Op1Def && !getVMetadata()->isMultiBlock(Var1) &&
+              llvm::isa<InstLoad>(Op1Def)) {
+            continue; // Both are loads
+          }
+        }
+        auto Cond = ICMP->getCondition();
+        switch (Cond) {

[John, 2016/07/07 21:20:56]

I would either add a "swap" field to the ICEINSTICMP_TABLE:


#define ICEINSTICMP_TABLE                  \
  /* enum value, swap, printable string */ \
  X(Eq,          Eq,   "eq")               \
  X(Ne,          Ne,   "ne")               \
  X(Ugt,         Ult,  "ugt")              \
  X(Uge,         Uge,  "uge")              \

and then define a table, or I would have a helper function:

namespace {
Icmp::ICond swap(Icmp::ICond cond) {
  switch (cond) {
    case Eq: return Eq;
    case Ne: return Ne;
  }
}
} // end of anonymous namespace

[manasijm, 2016/07/07 22:43:35]

Added a function to InstIcmp

+        case InstIcmp::ICond::Eq:
+          break;
+        case InstIcmp::ICond::Ne:
+          break;
+        case InstIcmp::ICond::Sge:
+          Cond = InstIcmp::ICond::Sle;
+          break;
+        case InstIcmp::ICond::Sgt:
+          Cond = InstIcmp::ICond::Slt;
+          break;
+        case InstIcmp::ICond::Sle:
+          Cond = InstIcmp::ICond::Sge;
+          break;
+        case InstIcmp::ICond::Slt:
+          Cond = InstIcmp::ICond::Sgt;
+          break;
+        case InstIcmp::ICond::Uge:
+          Cond = InstIcmp::ICond::Ule;
+          break;
+        case InstIcmp::ICond::Ugt:
+          Cond = InstIcmp::ICond::Ult;
+          break;
+        case InstIcmp::ICond::Ule:
+          Cond = InstIcmp::ICond::Uge;
+          break;
+        case InstIcmp::ICond::Ult:
+          Cond = InstIcmp::ICond::Ugt;
+          break;
+        default:
+          continue;
+        }
+        ICMP->setCondition(Cond);
+        auto *TempOp = ICMP->getSrc(0);
+        ICMP->replaceSource(0, ICMP->getSrc(1));
+        ICMP->replaceSource(1, TempOp);
+      }
+    }
+  }
+}
+
 void Cfg::doArgLowering() {
   TimerMarker T(TimerStack::TT_doArgLowering, this);
   getTarget()->lowerArguments();
 }
 
 void Cfg::sortAndCombineAllocas(CfgVector<InstAlloca *> &Allocas,
                                 uint32_t CombinedAlignment, InstList &Insts,
                                 AllocaBaseVariableType BaseVariableType) {
   if (Allocas.empty())
     return;
@@ skipping 967 matching lines @@
     }
   }
   // Print each basic block
   for (CfgNode *Node : Nodes)
     Node->dump(this);
   if (isVerbose(IceV_Instructions))
     Str << "}\n";
 }
 
 } // end of namespace Ice