[LV] Relax Small Size Reduction Type Requirement

This patch enables small size reductions in which the source types are smaller
than the reduction type (e.g., computing an i16 sum from the values in an i8
array). The previous behavior was to only allow small size reductions if the
source types and reduction type were the same. The change accounts for the fact
that the existing sign- and zero-extend instructions in these cases should
still be included in the cost model.

Differential Revision: http://reviews.llvm.org/D12770

llvm-svn: 247337

1 files changed, 14 insertions, 6 deletions

diff --git a/llvm/lib/Transforms/Utils/LoopUtils.cpp b/llvm/lib/Transforms/Utils/LoopUtils.cpp
index 785e2d4917f..a8d20c65c15 100644
--- a/llvm/lib/Transforms/Utils/LoopUtils.cpp
+++ b/llvm/lib/Transforms/Utils/LoopUtils.cpp
@@ -98,6 +98,7 @@ bool RecurrenceDescriptor::getSourceExtensionKind(
 
   SmallVector<Instruction *, 8> Worklist;
   bool FoundOneOperand = false;
+  unsigned DstSize = RT->getPrimitiveSizeInBits();
   Worklist.push_back(Exit);
 
   // Traverse the instructions in the reduction expression, beginning with the
@@ -120,11 +121,16 @@ bool RecurrenceDescriptor::getSourceExtensionKind(
 
       // If the operand is not in Visited, it is not a reduction operation, but
       // it does feed into one. Make sure it is either a single-use sign- or
-      // zero-extend of the recurrence type.
+      // zero-extend instruction.
       CastInst *Cast = dyn_cast<CastInst>(J);
       bool IsSExtInst = isa<SExtInst>(J);
-      if (!Cast || !Cast->hasOneUse() || Cast->getSrcTy() != RT ||
-          !(isa<ZExtInst>(J) || IsSExtInst))
+      if (!Cast || !Cast->hasOneUse() || !(isa<ZExtInst>(J) || IsSExtInst))
+        return false;
+
+      // Ensure the source type of the extend is no larger than the reduction
+      // type. It is not necessary for the types to be identical.
+      unsigned SrcSize = Cast->getSrcTy()->getPrimitiveSizeInBits();
+      if (SrcSize > DstSize)
         return false;
 
       // Furthermore, ensure that all such extends are of the same kind.
@@ -136,9 +142,11 @@ bool RecurrenceDescriptor::getSourceExtensionKind(
         IsSigned = IsSExtInst;
       }
 
-      // Lastly, add the sign- or zero-extend to CI so that we can avoid
-      // accounting for it in the cost model.
-      CI.insert(Cast);
+      // Lastly, if the source type of the extend matches the reduction type,
+      // add the extend to CI so that we can avoid accounting for it in the
+      // cost model.
+      if (SrcSize == DstSize)
+        CI.insert(Cast);
     }
   }
   return true;