From 0ea26ca45b56b2b4cc1839cdbccc13a38b066969 Mon Sep 17 00:00:00 2001
From: Chris Lattner <sabre@nondot.org>
Date: Wed, 20 Sep 2006 03:38:48 +0000
Subject: [PATCH] Expand 64-bit shifts more optimally if we know that the high
 bit of the shift amount is one or zero.  For example, for:

long long foo1(long long X, int C) {
  return X << (C|32);
}

long long foo2(long long X, int C) {
  return X << (C&~32);
}

we get:

_foo1:
        movb $31, %cl
        movl 4(%esp), %edx
        andb 12(%esp), %cl
        shll %cl, %edx
        xorl %eax, %eax
        ret
_foo2:
        movb $223, %cl
        movl 4(%esp), %eax
        movl 8(%esp), %edx
        andb 12(%esp), %cl
        shldl %cl, %eax, %edx
        shll %cl, %eax
        ret

instead of:

_foo1:
        subl $4, %esp
        movl %ebx, (%esp)
        movb $32, %bl
        movl 8(%esp), %eax
        movl 12(%esp), %edx
        movb %bl, %cl
        orb 16(%esp), %cl
        shldl %cl, %eax, %edx
        shll %cl, %eax
        xorl %ecx, %ecx
        testb %bl, %bl
        cmovne %eax, %edx
        cmovne %ecx, %eax
        movl (%esp), %ebx
        addl $4, %esp
        ret
_foo2:
        subl $4, %esp
        movl %ebx, (%esp)
        movb $223, %cl
        movl 8(%esp), %eax
        movl 12(%esp), %edx
        andb 16(%esp), %cl
        shldl %cl, %eax, %edx
        shll %cl, %eax
        xorl %ecx, %ecx
        xorb %bl, %bl
        testb %bl, %bl
        cmovne %eax, %edx
        cmovne %ecx, %eax
        movl (%esp), %ebx
        addl $4, %esp
        ret


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@30506 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/CodeGen/SelectionDAG/LegalizeDAG.cpp | 66 ++++++++++++++++++++++++
 1 file changed, 66 insertions(+)

diff --git a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
index aa25fd82956..cb8588c0318 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
@@ -3781,6 +3781,72 @@ bool SelectionDAGLegalize::ExpandShift(unsigned Opc, SDOperand Op,SDOperand Amt,
       return true;
     }
   }
+  
+  // Okay, the shift amount isn't constant.  However, if we can tell that it is
+  // >= 32 or < 32, we can still simplify it, without knowing the actual value.
+  uint64_t Mask = NVTBits, KnownZero, KnownOne;
+  TLI.ComputeMaskedBits(Amt, Mask, KnownZero, KnownOne);
+  
+  // If we know that the high bit of the shift amount is one, then we can do
+  // this as a couple of simple shifts.
+  if (KnownOne & Mask) {
+    // Mask out the high bit, which we know is set.
+    Amt = DAG.getNode(ISD::AND, Amt.getValueType(), Amt,
+                      DAG.getConstant(NVTBits-1, Amt.getValueType()));
+    
+    // Expand the incoming operand to be shifted, so that we have its parts
+    SDOperand InL, InH;
+    ExpandOp(Op, InL, InH);
+    switch(Opc) {
+    case ISD::SHL:
+      Lo = DAG.getConstant(0, NVT);              // Low part is zero.
+      Hi = DAG.getNode(ISD::SHL, NVT, InL, Amt); // High part from Lo part.
+      return true;
+    case ISD::SRL:
+      Hi = DAG.getConstant(0, NVT);              // Hi part is zero.
+      Lo = DAG.getNode(ISD::SRL, NVT, InH, Amt); // Lo part from Hi part.
+      return true;
+    case ISD::SRA:
+      Hi = DAG.getNode(ISD::SRA, NVT, InH,       // Sign extend high part.
+                       DAG.getConstant(NVTBits-1, Amt.getValueType()));
+      Lo = DAG.getNode(ISD::SRA, NVT, InH, Amt); // Lo part from Hi part.
+      return true;
+    }
+  }
+  
+  // If we know that the high bit of the shift amount is zero, then we can do
+  // this as a couple of simple shifts.
+  if (KnownZero & Mask) {
+    // Compute 32-amt.
+    SDOperand Amt2 = DAG.getNode(ISD::SUB, Amt.getValueType(),
+                                 DAG.getConstant(NVTBits, Amt.getValueType()),
+                                 Amt);
+    
+    // Expand the incoming operand to be shifted, so that we have its parts
+    SDOperand InL, InH;
+    ExpandOp(Op, InL, InH);
+    switch(Opc) {
+    case ISD::SHL:
+      Lo = DAG.getNode(ISD::SHL, NVT, InL, Amt);
+      Hi = DAG.getNode(ISD::OR, NVT,
+                       DAG.getNode(ISD::SHL, NVT, InH, Amt),
+                       DAG.getNode(ISD::SRL, NVT, InL, Amt2));
+      return true;
+    case ISD::SRL:
+      Hi = DAG.getNode(ISD::SRL, NVT, InH, Amt);
+      Lo = DAG.getNode(ISD::OR, NVT,
+                       DAG.getNode(ISD::SRL, NVT, InL, Amt),
+                       DAG.getNode(ISD::SHL, NVT, InH, Amt2));
+      return true;
+    case ISD::SRA:
+      Hi = DAG.getNode(ISD::SRA, NVT, InH, Amt);
+      Lo = DAG.getNode(ISD::OR, NVT,
+                       DAG.getNode(ISD::SRL, NVT, InL, Amt),
+                       DAG.getNode(ISD::SHL, NVT, InH, Amt2));
+      return true;
+    }
+  }
+  
   return false;
 }
 
-- 
2.34.1