91 /// Compute the minimal bit width needed to represent a reduction whose exit
136 /// model, given a reduction exit value and the minimal type in which the
137 // reduction can be represented. Also search casts to the recurrence type
179 // Check if a given Phi node can be recognized as an ordered reduction for
194   // Ensure the exit instruction has only one user other than the reduction PHI  in checkOrderedReduction()
198   // The only pattern accepted is the one in which the reduction PHI  in checkOrderedReduction()
207   LLVM_DEBUG(dbgs() << "LV: Found an ordered reduction: Phi: " << *Phi  in checkOrderedReduction()
220   // Reduction variables are only found in the loop header block.  in AddReductionVar()
224   // Obtain the reduction start value from the value that comes from the loop  in AddReductionVar()
229   // We only allow for a single reduction value to be used outside the loop.  in AddReductionVar()
230   // This includes users of the reduction, variables (which form a cycle  in AddReductionVar()
236   // reduction value stored in invariant address.  in AddReductionVar()
239   // Indicates that we found a reduction operation in our scan.  in AddReductionVar()
243   // instruction. All users must be instructions that can be used as reduction  in AddReductionVar()
268   // to evaluate the reduction in the narrower width.  in AddReductionVar()
278     // Pointer min/max may exist, but it is not supported as a reduction op.  in AddReductionVar()
285   // Start with all flags set because we will intersect this with the reduction  in AddReductionVar()
286   // flags from all the reduction operations.  in AddReductionVar()
293   // A value in the reduction can be used:  in AddReductionVar()
294   //  - By the reduction:  in AddReductionVar()
295   //      - Reduction operation:  in AddReductionVar()
296   //        - One use of reduction value (safe).  in AddReductionVar()
297   //        - Multiple use of reduction value (not safe).  in AddReductionVar()
299   //        - All uses of the PHI must be the reduction (safe).  in AddReductionVar()
308   //  - By an instruction that is not part of the reduction (not safe).  in AddReductionVar()
310   //      * An instruction type other than PHI or the reduction operation.  in AddReductionVar()
315     // Store instructions are allowed iff it is the store of the reduction  in AddReductionVar()
331           LLVM_DEBUG(dbgs() << "Storing reduction value to different addresses "  in AddReductionVar()
341         LLVM_DEBUG(dbgs() << "Storing reduction value to non-uniform address "  in AddReductionVar()
354     // a reduction variable.  in AddReductionVar()
365     // LHS is the reduction variable.  in AddReductionVar()
371     // Any reduction instruction must be of one of the allowed kinds. We ignore  in AddReductionVar()
395       // Update this reduction kind if we matched a new instruction.  in AddReductionVar()
404     // A conditional reduction operation must only have 2 or less uses in  in AddReductionVar()
410     // A reduction operation must only have one use of the reduction value.  in AddReductionVar()
415     // All inputs to a PHI node must be a reduction value.  in AddReductionVar()
426     // Check  whether we found a reduction operator.  in AddReductionVar()
454         // the reduction operation if we vectorize.  in AddReductionVar()
459         // before we feed back to the reduction phi. Otherwise, we loose VF-1  in AddReductionVar()
468       // Process instructions only once (termination). Each reduction cycle  in AddReductionVar()
478             // Reduction variable chain can only be stored somewhere but it  in AddReductionVar()
513     // that the value stored in IntermediateStore is indeed the final reduction  in AddReductionVar()
516       LLVM_DEBUG(dbgs() << "Not a final reduction value stored: "  in AddReductionVar()
525       LLVM_DEBUG(dbgs() << "Last store Instruction of reduction value does not "  in AddReductionVar()
526                            "store last calculated value of the reduction: "  in AddReductionVar()
532     // reduction value after the loop will be the one used in the last store.  in AddReductionVar()
546     // arithmetic reduction to determine if it may have been type-promoted.  in AddReductionVar()
549     // reduction. If this is the same width that was indicated by the 'and', we  in AddReductionVar()
550     // can represent the reduction in the smaller type. The 'and' instruction  in AddReductionVar()
560     // exit value of the reduction to the width indicated by RecurrenceType and  in AddReductionVar()
565     // TODO: We should not rely on InstCombine to rewrite the reduction in the  in AddReductionVar()
583   //       instructions that are a part of the reduction. The vectorizer cost  in AddReductionVar()
591   // We found a reduction var if we have reached the original phi node and we  in AddReductionVar()
597   // Save the description of this reduction variable.  in AddReductionVar()
612 // where the reduction value (r) only has two states, in this example 0 or 3.
624 // across-vector reduction after the loop simply involves choosing the start
714 /// reduction pattern below. The select instruction argument is the last one
853     LLVM_DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");  in isReductionPHI()
858     LLVM_DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");  in isReductionPHI()
863     LLVM_DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");  in isReductionPHI()
868     LLVM_DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");  in isReductionPHI()
873     LLVM_DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");  in isReductionPHI()
878     LLVM_DEBUG(dbgs() << "Found a SMAX reduction PHI." << *Phi << "\n");  in isReductionPHI()
883     LLVM_DEBUG(dbgs() << "Found a SMIN reduction PHI." << *Phi << "\n");  in isReductionPHI()
888     LLVM_DEBUG(dbgs() << "Found a UMAX reduction PHI." << *Phi << "\n");  in isReductionPHI()
893     LLVM_DEBUG(dbgs() << "Found a UMIN reduction PHI." << *Phi << "\n");  in isReductionPHI()
898     LLVM_DEBUG(dbgs() << "Found an integer conditional select reduction PHI."  in isReductionPHI()
904     LLVM_DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");  in isReductionPHI()
909     LLVM_DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");  in isReductionPHI()
914     LLVM_DEBUG(dbgs() << "Found a float MAX reduction PHI." << *Phi << "\n");  in isReductionPHI()
919     LLVM_DEBUG(dbgs() << "Found a float MIN reduction PHI." << *Phi << "\n");  in isReductionPHI()
924     LLVM_DEBUG(dbgs() << "Found a float conditional select reduction PHI."  in isReductionPHI()
930     LLVM_DEBUG(dbgs() << "Found an FMulAdd reduction PHI." << *Phi << "\n");  in isReductionPHI()
935     LLVM_DEBUG(dbgs() << "Found a float MAXIMUM reduction PHI." << *Phi << "\n");  in isReductionPHI()
940     LLVM_DEBUG(dbgs() << "Found a float MINIMUM reduction PHI." << *Phi << "\n");  in isReductionPHI()
943   // Not a reduction of known type.  in isReductionPHI()
1077            "nnan, nsz is expected to be set for FP min reduction.");  in getRecurrenceIdentity()
1081            "nnan, nsz is expected to be set for FP max reduction.");  in getRecurrenceIdentity()
1136   // with a single user of the correct type for the reduction.  in getReductionOpChain()
1140   // sub, which would otherwise be treated as an add reduction. MinMax also need  in getReductionOpChain()
1145   // be part of the reduction chain, or attempt to looks through And's to find a  in getReductionOpChain()
1147   // treated as part of a add reduction) as they are expected to generally be  in getReductionOpChain()
1183   // Attempt to look through Phis which are part of the reduction chain  in getReductionOpChain()