Index: lib/CodeGen/SelectionDAG/DAGCombiner.cpp =================================================================== --- lib/CodeGen/SelectionDAG/DAGCombiner.cpp +++ lib/CodeGen/SelectionDAG/DAGCombiner.cpp @@ -402,6 +402,14 @@ unsigned SequenceNum; }; + /// This is a helper function for visitMUL to check the profitability + /// of folding (mul (add x, c1), c2) -> (add (mul x, c2), c1*c2). + /// MulNode is the original multiply, AddNode is (add x, c1), + /// and ConstNode is c2. + bool isMulAddWithConstProfitable(SDNode *MulNode, + SDValue &AddNode, + SDValue &ConstNode); + /// This is a helper function for MergeStoresOfConstantsOrVecElts. Returns a /// constant build_vector of the stored constant values in Stores. SDValue getMergedConstantVectorStore(SelectionDAG &DAG, @@ -2145,14 +2153,15 @@ } // fold (mul (add x, c1), c2) -> (add (mul x, c2), c1*c2) - if (N1IsConst && N0.getOpcode() == ISD::ADD && N0.getNode()->hasOneUse() && + if (N1IsConst && N0.getOpcode() == ISD::ADD && (isConstantSplatVector(N0.getOperand(1).getNode(), Val) || - isa(N0.getOperand(1)))) - return DAG.getNode(ISD::ADD, SDLoc(N), VT, - DAG.getNode(ISD::MUL, SDLoc(N0), VT, - N0.getOperand(0), N1), - DAG.getNode(ISD::MUL, SDLoc(N1), VT, - N0.getOperand(1), N1)); + isa(N0.getOperand(1))) && + isMulAddWithConstProfitable(N, N0, N1)) + return DAG.getNode(ISD::ADD, SDLoc(N), VT, + DAG.getNode(ISD::MUL, SDLoc(N0), VT, + N0.getOperand(0), N1), + DAG.getNode(ISD::MUL, SDLoc(N1), VT, + N0.getOperand(1), N1)); // reassociate mul if (SDValue RMUL = ReassociateOps(ISD::MUL, SDLoc(N), N0, N1)) @@ -10796,6 +10805,82 @@ }; } // namespace +// This is a helper function for visitMUL to check the profitability +// of folding (mul (add x, c1), c2) -> (add (mul x, c2), c1*c2). +// MulNode is the original multiply, AddNode is (add x, c1), +// and ConstNode is c2. +// +// If the (add x, c1) has multiple uses, we could increase +// the number of adds if we make this transformation. +// It would only be worth doing this if we can remove a +// multiply in the process. Check for that here. +// To illustrate: +// (A + c1) * c3 +// (A + c2) * c3 +// We're checking for cases where we have common "c3 * A" expressions. +bool DAGCombiner::isMulAddWithConstProfitable(SDNode *MulNode, + SDValue &AddNode, + SDValue &ConstNode) { + APInt Val; + + // If the add only has one use, this would be OK to do. + if (AddNode.getNode()->hasOneUse()) + return true; + + // Walk all the users of the constant with which we're multiplying. + for (SDNode *Use : ConstNode->uses()) { + + if (Use == MulNode) // This use is the one we're on right now. Skip it. + continue; + + if (Use->getOpcode() == ISD::MUL) { // We have another multiply use. + SDNode *OtherOp; + SDNode *MulVar = AddNode.getOperand(0).getNode(); + + // OtherOp is what we're multiplying against the constant. + if (Use->getOperand(0) == ConstNode) + OtherOp = Use->getOperand(1).getNode(); + else + OtherOp = Use->getOperand(0).getNode(); + + // Check to see if multiply is with the same operand of our "add". + // + // ConstNode = CONST + // Use = ConstNode * A <-- visiting Use. OtherOp is A. + // ... + // AddNode = (A + c1) <-- MulVar is A. + // = AddNode * ConstNode <-- current visiting instruction. + // + // If we make this transformation, we will have a common + // multiply (ConstNode * A) that we can save. + if (OtherOp == MulVar) + return true; + + // Now check to see if a future expansion will give us a common + // multiply. + // + // ConstNode = CONST + // AddNode = (A + c1) + // ... = AddNode * ConstNode <-- current visiting instruction. + // ... + // OtherOp = (A + c2) + // Use = OtherOp * ConstNode <-- visiting Use. + // + // If we make this transformation, we will have a common + // multiply (CONST * A) after we also do the same transformation + // to the "t2" instruction. + if (OtherOp->getOpcode() == ISD::ADD && + (isConstantSplatVector(OtherOp->getOperand(1).getNode(), Val) || + isa(OtherOp->getOperand(1).getNode())) && + OtherOp->getOperand(0).getNode() == MulVar) + return true; + } + } + + // Didn't find a case where this would be profitable. + return false; +} + SDValue DAGCombiner::getMergedConstantVectorStore(SelectionDAG &DAG, SDLoc SL, ArrayRef Stores, Index: test/CodeGen/X86/combine-multiplies.ll =================================================================== --- test/CodeGen/X86/combine-multiplies.ll +++ test/CodeGen/X86/combine-multiplies.ll @@ -0,0 +1,55 @@ +; RUN: llc < %s -mtriple=i386-unknown-linux-gnu | FileCheck %s + +; Source file looks something like this: +; +; typedef int AAA[100][100]; +; +; void foo(AAA a,int lll) +; { +; int LOC = lll + 5; +; +; a[LOC][LOC] = 11; +; +; a[LOC][20] = 22; +; a[LOC+20][20] = 33; +; } +; +; We want to make sure we don't generate 2 multiply instructions, +; one for a[LOC][] and one for a[LOC+20]. visitMUL in DAGCombiner.cpp +; should combine the instructions in such a way to avoid the extra +; multiply. +; +; Output looks roughly like this: +; +; movl 8(%esp), %eax +; movl 12(%esp), %ecx +; imull $400, %ecx, %edx # imm = 0x190 +; leal (%edx,%eax), %esi +; movl $11, 2020(%esi,%ecx,4) +; movl $22, 2080(%edx,%eax) +; movl $33, 10080(%edx,%eax) +; +; CHECK-LABEL: foo +; CHECK: imull $400, [[ARG1:%[a-z]+]], [[MUL:%[a-z]+]] # imm = 0x190 +; CHECK-NEXT: leal ([[MUL]],[[ARG2:%[a-z]+]]), [[LEA:%[a-z]+]] +; CHECK-NEXT: movl $11, {{[0-9]+}}([[LEA]],[[ARG1]],4) +; CHECK-NEXT: movl $22, {{[0-9]+}}([[MUL]],[[ARG2]]) +; CHECK-NEXT: movl $33, {{[0-9]+}}([[MUL]],[[ARG2]]) +; CHECK: retl +; + +; Function Attrs: nounwind +define void @foo([100 x i32]* nocapture %a, i32 %lll) { +entry: + %add = add nsw i32 %lll, 5 + %arrayidx1 = getelementptr inbounds [100 x i32], [100 x i32]* %a, i32 %add, i32 %add + store i32 11, i32* %arrayidx1, align 4 + %arrayidx3 = getelementptr inbounds [100 x i32], [100 x i32]* %a, i32 %add, i32 20 + store i32 22, i32* %arrayidx3, align 4 + %add4 = add nsw i32 %lll, 25 + %arrayidx6 = getelementptr inbounds [100 x i32], [100 x i32]* %a, i32 %add4, i32 20 + store i32 33, i32* %arrayidx6, align 4 + ret void +} + +