[X86] PR32755 : Improvement in CodeGen instruction selection for LEAs.

Summary:
   1/  Operand folding during complex pattern matching for LEAs has been
       extended, such that it promotes Scale to accommodate similar operand
       appearing in the DAG.
       e.g.
          T1 = A + B
          T2 = T1 + 10
          T3 = T2 + A
       For above DAG rooted at T3, X86AddressMode will no look like
          Base = B , Index = A , Scale = 2 , Disp = 10

   2/  During OptimizeLEAPass down the pipeline factorization is now performed over LEAs
       so that if there is an opportunity then complex LEAs (having 3 operands)
       could be factored out.
       e.g.
          leal 1(%rax,%rcx,1), %rdx
          leal 1(%rax,%rcx,2), %rcx
       will be factored as following
          leal 1(%rax,%rcx,1), %rdx
          leal (%rdx,%rcx)   , %edx

   3/ Aggressive operand folding for AM based selection for LEAs is sensitive to loops,
      thus avoiding creation of any complex LEAs within a loop.

Reviewers: lsaba, RKSimon, craig.topper, qcolombet

Reviewed By: lsaba

Subscribers: spatel, igorb, llvm-commits

Differential Revision: https://reviews.llvm.org/D35014

llvm-svn: 313343

1 files changed, 79 insertions, 6 deletions

diff --git a/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp b/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp
index a0d7cb35467..a5e1fea3bf4 100644
--- a/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp
+++ b/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp
@@ -88,6 +88,11 @@ namespace {
              IndexReg.getNode() != nullptr || Base_Reg.getNode() != nullptr;
     }
 
+    bool hasComplexAddressingMode() const {
+      return Disp && IndexReg.getNode() != nullptr &&
+             Base_Reg.getNode() != nullptr;
+    }
+
     /// Return true if this addressing mode is already RIP-relative.
     bool isRIPRelative() const {
       if (BaseType != RegBase) return false;
@@ -97,6 +102,10 @@ namespace {
       return false;
     }
 
+    bool isLegalScale() {
+      return (Scale == 1 || Scale == 2 || Scale == 4 || Scale == 8);
+    }
+
     void setBaseReg(SDValue Reg) {
       BaseType = RegBase;
       Base_Reg = Reg;
@@ -162,10 +171,13 @@ namespace {
     /// If true, selector should try to optimize for minimum code size.
     bool OptForMinSize;
 
+    /// If true, selector should try to aggresively fold operands into AM.
+    bool OptForAggressingFolding;
+
   public:
     explicit X86DAGToDAGISel(X86TargetMachine &tm, CodeGenOpt::Level OptLevel)
         : SelectionDAGISel(tm, OptLevel), OptForSize(false),
-          OptForMinSize(false) {}
+          OptForMinSize(false), OptForAggressingFolding(false) {}
 
     StringRef getPassName() const override {
       return "X86 DAG->DAG Instruction Selection";
@@ -184,6 +196,12 @@ namespace {
 
     void PreprocessISelDAG() override;
 
+    void setAggressiveOperandFolding(bool val = false) {
+      OptForAggressingFolding = val;
+    }
+
+    bool getAggressiveOperandFolding() { return OptForAggressingFolding; }
+
 // Include the pieces autogenerated from the target description.
 #include "X86GenDAGISel.inc"
 
@@ -197,6 +215,7 @@ namespace {
     bool matchAdd(SDValue N, X86ISelAddressMode &AM, unsigned Depth);
     bool matchAddressRecursively(SDValue N, X86ISelAddressMode &AM,
                                  unsigned Depth);
+    bool matchAddressLEA(SDValue N, X86ISelAddressMode &AM);
     bool matchAddressBase(SDValue N, X86ISelAddressMode &AM);
     bool selectAddr(SDNode *Parent, SDValue N, SDValue &Base,
                     SDValue &Scale, SDValue &Index, SDValue &Disp,
@@ -425,6 +444,20 @@ namespace {
 
     bool matchBEXTRFromAnd(SDNode *Node);
   };
+
+  class X86AggressiveOperandFolding {
+  public:
+    explicit X86AggressiveOperandFolding(X86DAGToDAGISel &ISel, bool val)
+        : Selector(&ISel) {
+      Selector->setAggressiveOperandFolding(val);
+    }
+    ~X86AggressiveOperandFolding() {
+      Selector->setAggressiveOperandFolding(false);
+    }
+
+  private:
+    X86DAGToDAGISel *Selector;
+  };
 }
 
 
@@ -1138,7 +1171,7 @@ static bool foldMaskAndShiftToScale(SelectionDAG &DAG, SDValue N,
   AM.IndexReg = NewSRL;
   return false;
 }
-
+   
 bool X86DAGToDAGISel::matchAddressRecursively(SDValue N, X86ISelAddressMode &AM,
                                               unsigned Depth) {
   SDLoc dl(N);
@@ -1146,8 +1179,11 @@ bool X86DAGToDAGISel::matchAddressRecursively(SDValue N, X86ISelAddressMode &AM,
       dbgs() << "MatchAddress: ";
       AM.dump();
     });
-  // Limit recursion.
-  if (Depth > 5)
+
+  // Limit recursion. For aggressive operand folding recurse 
+  // till depth 8 which is the maximum legal scale value.
+  unsigned MaxDepth = getAggressiveOperandFolding() ? 8 : 5;
+  if (Depth > MaxDepth)
     return matchAddressBase(N, AM);
 
   // If this is already a %rip relative address, we can only merge immediates
@@ -1438,6 +1474,20 @@ bool X86DAGToDAGISel::matchAddressBase(SDValue N, X86ISelAddressMode &AM) {
       return false;
     }
 
+    if (OptLevel != CodeGenOpt::None && getAggressiveOperandFolding() &&
+        AM.BaseType == X86ISelAddressMode::RegBase) {
+      if (AM.Base_Reg == N) {
+        SDValue Base_Reg = AM.Base_Reg;
+        AM.Base_Reg = AM.IndexReg;
+        AM.IndexReg = Base_Reg;
+        AM.Scale++;
+        return false;
+      } else if (AM.IndexReg == N) {
+        AM.Scale++;
+        return false;
+      }
+    }
+
     // Otherwise, we cannot select it.
     return true;
   }
@@ -1668,7 +1718,7 @@ bool X86DAGToDAGISel::selectLEA64_32Addr(SDValue N, SDValue &Base,
                                          SDValue &Disp, SDValue &Segment) {
   // Save the debug loc before calling selectLEAAddr, in case it invalidates N.
   SDLoc DL(N);
-
+   
   if (!selectLEAAddr(N, Base, Scale, Index, Disp, Segment))
     return false;
 
@@ -1703,6 +1753,29 @@ bool X86DAGToDAGISel::selectLEA64_32Addr(SDValue N, SDValue &Base,
   return true;
 }
 
+bool X86DAGToDAGISel::matchAddressLEA(SDValue N, X86ISelAddressMode &AM) {
+  // Avoid enabling aggressive operand folding when node N is a part of loop.
+  X86AggressiveOperandFolding Enable(*this, !CurDAG->IsDAGPartOfLoop);
+
+  bool matchRes = matchAddress(N, AM);
+
+  // Check for legality of scale when recursion unwinds back to the top.
+  if (!matchRes) {
+    if (!AM.isLegalScale())
+      return true;
+
+    // Avoid creating costly complex LEAs having scale less than 2
+    // within loop.
+    if(CurDAG->IsDAGPartOfLoop && Subtarget->slow3OpsLEA() &&
+        AM.Scale <= 2 && AM.hasComplexAddressingMode() &&
+         (!AM.hasSymbolicDisplacement() && N.getOpcode() < ISD::BUILTIN_OP_END))
+     return true;
+  }
+
+  return matchRes;
+}
+
+
 /// Calls SelectAddr and determines if the maximal addressing
 /// mode it matches can be cost effectively emitted as an LEA instruction.
 bool X86DAGToDAGISel::selectLEAAddr(SDValue N,
@@ -1720,7 +1793,7 @@ bool X86DAGToDAGISel::selectLEAAddr(SDValue N,
   SDValue Copy = AM.Segment;
   SDValue T = CurDAG->getRegister(0, MVT::i32);
   AM.Segment = T;
-  if (matchAddress(N, AM))
+  if (matchAddressLEA(N, AM))
     return false;
   assert (T == AM.Segment);
   AM.Segment = Copy;