From 4878b8415fd524489b4bee5f90e969f6ccb253d4 Mon Sep 17 00:00:00 2001
From: Anton Korobeynikov <asl@math.spbu.ru>
Date: Sun, 16 May 2010 08:54:20 +0000
Subject: [PATCH] Generalize the ARM DAG combiner of mul with constants to all
 power-of-two cases.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103901 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Target/ARM/ARMISelLowering.cpp | 55 ++++++++++++------------------
 1 file changed, 21 insertions(+), 34 deletions(-)

diff --git a/lib/Target/ARM/ARMISelLowering.cpp b/lib/Target/ARM/ARMISelLowering.cpp
index 1e415d15f86..c284a7e0439 100644
--- a/lib/Target/ARM/ARMISelLowering.cpp
+++ b/lib/Target/ARM/ARMISelLowering.cpp
@@ -3613,44 +3613,31 @@ static SDValue PerformMULCombine(SDNode *N,
   ShiftAmt = ShiftAmt & (32 - 1);
   SDValue V = N->getOperand(0);
   DebugLoc DL = N->getDebugLoc();
-  SDValue NewAdd;
-
-  // FIXME: Handle arbitrary powers of 2.
-  switch (MulAmt >> ShiftAmt) {
-  case 3: // 2 + 1
-    NewAdd = DAG.getNode(ISD::ADD, DL, VT,
-                         V, DAG.getNode(ISD::SHL, DL, VT,
-                                        V, DAG.getConstant(1, MVT::i32)));
-   break;
-  case 5: // 4 + 1
-    NewAdd = DAG.getNode(ISD::ADD, DL, VT,
-                         V, DAG.getNode(ISD::SHL, DL, VT,
-                                        V, DAG.getConstant(2, MVT::i32)));
-    break;
-  case 7: // 8 - 1
-    NewAdd = DAG.getNode(ISD::SUB, DL, VT,
-                         DAG.getNode(ISD::SHL, DL, VT,
-                                     V, DAG.getConstant(3, MVT::i32)),
-                         V);
-    break;
-  case 9: // 8 + 1
-    NewAdd = DAG.getNode(ISD::ADD, DL, VT,
-                         V, DAG.getNode(ISD::SHL, DL, VT,
-                                        V, DAG.getConstant(3, MVT::i32)));
-    break;
-  default: return SDValue();
-  }
 
-  if (ShiftAmt != 0) {
-    SDValue NewShift = DAG.getNode(ISD::SHL, DL, VT, NewAdd,
-                                   DAG.getConstant(ShiftAmt, MVT::i32));
-    // Do not add new nodes to DAG combiner worklist.
-    DCI.CombineTo(N, NewShift, false);
+  SDValue Res;
+  MulAmt >>= ShiftAmt;
+  if (isPowerOf2_32(MulAmt - 1)) {
+    // (mul x, 2^N + 1) => (add (shl x, N), x)
+    Res = DAG.getNode(ISD::ADD, DL, VT,
+                      V, DAG.getNode(ISD::SHL, DL, VT,
+                                     V, DAG.getConstant(Log2_32(MulAmt-1),
+                                                        MVT::i32)));
+  } else if (isPowerOf2_32(MulAmt + 1)) {
+    // (mul x, 2^N - 1) => (sub (shl x, N), x)
+    Res = DAG.getNode(ISD::SUB, DL, VT,
+                      DAG.getNode(ISD::SHL, DL, VT,
+                                  V, DAG.getConstant(Log2_32(MulAmt+1),
+                                                     MVT::i32)),
+                                                     V);
+  } else
     return SDValue();
-  }
+
+  if (ShiftAmt != 0)
+    Res = DAG.getNode(ISD::SHL, DL, VT, Res,
+                      DAG.getConstant(ShiftAmt, MVT::i32));
 
   // Do not add new nodes to DAG combiner worklist.
-  DCI.CombineTo(N, NewAdd, false);
+  DCI.CombineTo(N, Res, false);
   return SDValue();
 }
 
-- 
2.34.1