From 895c4ab564c145d16a585201ea49b91541d806b6 Mon Sep 17 00:00:00 2001
From: Chris Lattner <sabre@nondot.org>
Date: Tue, 17 Apr 2007 21:14:16 +0000
Subject: [PATCH] Fold (x << c1)>> c2 into a single shift if the bits shifted
 out aren't used.

This compiles:
int baz(long long a) { return (short)(((int)(a >>24)) >> 9); }

into:
_baz:
        srwi r2, r3, 1
        extsh r3, r2
        blr

on PPC, instead of:
_baz:
        slwi r2, r3, 8
        srwi r2, r2, 9
        extsh r3, r2
        blr

GCC produces:
_baz:
        srwi r10,r4,24
        insrwi r10,r3,24,0
        srawi r9,r3,24
        srawi r3,r10,9
        extsh r3,r3
        blr

This implements CodeGen/PowerPC/shl_elim.ll


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@36221 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/CodeGen/SelectionDAG/TargetLowering.cpp | 57 +++++++++++++++++++--
 1 file changed, 52 insertions(+), 5 deletions(-)

diff --git a/lib/CodeGen/SelectionDAG/TargetLowering.cpp b/lib/CodeGen/SelectionDAG/TargetLowering.cpp
index 7d300629951..3da06f99749 100644
--- a/lib/CodeGen/SelectionDAG/TargetLowering.cpp
+++ b/lib/CodeGen/SelectionDAG/TargetLowering.cpp
@@ -563,7 +563,32 @@ bool TargetLowering::SimplifyDemandedBits(SDOperand Op, uint64_t DemandedMask,
     break;
   case ISD::SHL:
     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
-      if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask >> SA->getValue(),
+      unsigned ShAmt = SA->getValue();
+      SDOperand InOp = Op.getOperand(0);
+
+      // If this is ((X >>u C1) << ShAmt), see if we can simplify this into a
+      // single shift.  We can do this if the bottom bits (which are shifted
+      // out) are never demanded.
+      if (InOp.getOpcode() == ISD::SRL &&
+          isa<ConstantSDNode>(InOp.getOperand(1))) {
+        if (ShAmt && (DemandedMask & ((1ULL << ShAmt)-1)) == 0) {
+          unsigned C1 = cast<ConstantSDNode>(InOp.getOperand(1))->getValue();
+          unsigned Opc = ISD::SHL;
+          int Diff = ShAmt-C1;
+          if (Diff < 0) {
+            Diff = -Diff;
+            Opc = ISD::SRL;
+          }          
+          
+          SDOperand NewSA = 
+            TLO.DAG.getConstant(ShAmt-C1, Op.getOperand(0).getValueType());
+          MVT::ValueType VT = Op.getValueType();
+          return TLO.CombineTo(Op, TLO.DAG.getNode(ISD::SRL, VT,
+                                                   InOp.getOperand(0), NewSA));
+        }
+      }      
+      
+      if (SimplifyDemandedBits(Op.getOperand(0), DemandedMask >> ShAmt,
                                KnownZero, KnownOne, TLO, Depth+1))
         return true;
       KnownZero <<= SA->getValue();
@@ -575,11 +600,33 @@ bool TargetLowering::SimplifyDemandedBits(SDOperand Op, uint64_t DemandedMask,
     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
       MVT::ValueType VT = Op.getValueType();
       unsigned ShAmt = SA->getValue();
+      uint64_t TypeMask = MVT::getIntVTBitMask(VT);
+      unsigned VTSize = MVT::getSizeInBits(VT);
+      SDOperand InOp = Op.getOperand(0);
+      
+      // If this is ((X << C1) >>u ShAmt), see if we can simplify this into a
+      // single shift.  We can do this if the top bits (which are shifted out)
+      // are never demanded.
+      if (InOp.getOpcode() == ISD::SHL &&
+          isa<ConstantSDNode>(InOp.getOperand(1))) {
+        if (ShAmt && (DemandedMask & (~0ULL << (VTSize-ShAmt))) == 0) {
+          unsigned C1 = cast<ConstantSDNode>(InOp.getOperand(1))->getValue();
+          unsigned Opc = ISD::SRL;
+          int Diff = ShAmt-C1;
+          if (Diff < 0) {
+            Diff = -Diff;
+            Opc = ISD::SHL;
+          }          
+          
+          SDOperand NewSA =
+            TLO.DAG.getConstant(Diff, Op.getOperand(0).getValueType());
+          return TLO.CombineTo(Op, TLO.DAG.getNode(Opc, VT,
+                                                   InOp.getOperand(0), NewSA));
+        }
+      }      
       
       // Compute the new bits that are at the top now.
-      uint64_t TypeMask = MVT::getIntVTBitMask(VT);
-      if (SimplifyDemandedBits(Op.getOperand(0), 
-                               (DemandedMask << ShAmt) & TypeMask,
+      if (SimplifyDemandedBits(InOp, (DemandedMask << ShAmt) & TypeMask,
                                KnownZero, KnownOne, TLO, Depth+1))
         return true;
       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
@@ -589,7 +636,7 @@ bool TargetLowering::SimplifyDemandedBits(SDOperand Op, uint64_t DemandedMask,
       KnownOne  >>= ShAmt;
 
       uint64_t HighBits = (1ULL << ShAmt)-1;
-      HighBits <<= MVT::getSizeInBits(VT) - ShAmt;
+      HighBits <<= VTSize - ShAmt;
       KnownZero |= HighBits;  // High bits known zero.
     }
     break;
-- 
2.34.1