Addressing @wmi's concern by limiting the targets to the recurrence cycles that only the last instruction of the recurrence (that feeds the PHI instruction) can have uses outside of the recurrence. This is not an ideal solution yet, and more fundamental solution (such as having recurrence optimization as a separate pass and/or using live range analysis for it) should follow. But still I think it is worth to have it here.

In D34373#785642, @hfinkel wrote:

In D34373#785485, @twoh wrote:

In D34373#785367, @hfinkel wrote:

In D34373#784975, @twoh wrote:

I think this is a right approach, but concerned that the experimental results I shared on D32451 show that it is generally better to not to vectorize the low trip count loops. @Ayal, I wonder if you have any results that this patch actually improves the performance. Thanks!

I know that we're currently missing opportunities for large vectorizable loops with low (static) trip counts. Smaller inner loops are also good candidates for unpredicated vectorization, but we may need to be a bit careful because of modeling inaccuracies and phase-ordering effects (e.g. if we don't vectorize a loop, then we'll end up unrolling it when the unroller runs).

Got it. My concern was for small single-level loops with low trip counts, as I observe them pretty frequently. I have no objection accepting this patch and improve the cost estimator separately.

Do you mean that you see such loops frequently with dynamically-small trip counts, or with static trip counts? I assume the small loops with (small) static trip counts will generally be unrolled.

In D34373#785367, @hfinkel wrote:

In D34373#784975, @twoh wrote:

I think this is a right approach, but concerned that the experimental results I shared on D32451 show that it is generally better to not to vectorize the low trip count loops. @Ayal, I wonder if you have any results that this patch actually improves the performance. Thanks!

I know that we're currently missing opportunities for large vectorizable loops with low (static) trip counts. Smaller inner loops are also good candidates for unpredicated vectorization, but we may need to be a bit careful because of modeling inaccuracies and phase-ordering effects (e.g. if we don't vectorize a loop, then we'll end up unrolling it when the unroller runs).

I think this is a right approach, but concerned that the experimental results I shared on D32451 show that it is generally better to not to vectorize the low trip count loops. @Ayal, I wonder if you have any results that this patch actually improves the performance. Thanks!

Addressing comments from @tejohnson. Thanks!

@tejohnson Sorry for the late reply. I was out of internet for days. I have no objection to set the default value to true, but prefer to have it as a separate patch so that we can track the impact on performance of each chance more easily.

Ping. Thanks!

@wmi Not at all! Thanks for your comments.

ping. thanks!

FYI, below is the compile difference in percentage for spec2006:

Add missing reference.

Reimplement the feature in peephole optimizer. This patch makes the values in the recurrence cycle to be tied to each other if possible.

Ping. Thanks!

Comparing the existing implementation and this patch, I don't observe noticeable compile time different with Video-SIMDBench. I compiled the benchmark suite 3 times each and the median was 27.12 sec vs 27.55 sec, while the average was 27.96sec vs 27.89 sec. There were some code size differences, but it is simply more vectorization results bigger code size. There's no difference between OptForSize and non-vectorized.

Addressing Ayal's comments.

@wmi Thank you for your reply. I agree on you that we should consider tied operand group, and as @qcolombet mentioned in the previous comment, if tie operand information is already available before this pass, I'd like to discuss where would be the best place to implement this.

@qcolombet Actually you're right. Having tied operands, this can be done within SSA. Do you have a suggestion for a better place to implement this? I thought what isRevCopyChain does is most close to what this patch does.

@MatzeB Thank you for your comments. I'm collection compile time numbers now with spec2006. For our internal benchmark, which takes about ~40min to compile, the compile time difference was negligible.

Addressing comments from @MatzeB.

@Ayal Thanks for the pointer.

Ping. Can someone please let me know what would be the best way to have this patch reviewed? Thanks!

I don't have a strong opinion about treating static trip count and profile-based trip count or not. I treated them separately because existing implementation sets OptForSize to true instead of returning false when it makes a profile-based decision. It would be great if someone can explain the reason behind that.

Thanks @Ayal for your comments! If the profile-based trip count checking is moved above the line

Addresing comments from Ayal.

Ping.

Ping. Thanks!

Ping. If you're too busy to review this patch, could you please recommend someone else? Thanks!

So I evaluated loop vectorizer with https://github.com/malvanos/Video-SIMDBench, which is introduced in this paper: http://ieeexplore.ieee.org/document/7723550/. I first built it without profile data and ran linux perf with a command of

Use profile-based trip count estimation only when trip count cannot be computed.

@mkuper I can do that, but the issue is that the vectorized part doesn't dominated the execution time of the benchmark (profile is pretty flat across multiple functions), so it may not be suitable to tell the impact of vectorization change. Let me think about a good way to measure the it. Thanks!

@mkuper This helps with our internal benchmarks, but I don't have numbers with public benchmarks. What would be the good benchmarks to evaluate the vectorization? Thanks!

@MatzeB I was considering other passes as well for the sake of simplicity, but I concluded two-address instruction is the right place to do. The problem doesn't appear while we're in SSA, but becomes an issue when we make an decision about which operand register should be the destination register. I think this is why isProfitableToCommute function is in two-address instruction pass.

Ping. Thanks!

Friendly ping. Thanks!

With numbers, it doesn't seem worth to turn it on by default. @dberlin, just curious, do you have any rough estimation about how much compilation time can be saved by implementing rank-order based iteration optimization?

Below are the numbers with spec2006 (The numbers in the last row are overall for SPEC score and total for compile time and binary size):

@dberlin Thank you for your comments. I agree on you that it is not easy to invent a good heuristics around this knob, but still I find this useful for some cases that actually matters. Assuming that this doesn't make the implementation much complex, wouldn't it be better for compiler users to have more options?

No perf numbers with public benchmarks yet, but with our internal benchmark I confirmed that aggressive load PRE removes redundant instructions in a hot loop. I'll report spec2006 numbers later. This patch is for quick unlocking of the feature before making more fundamental improvement.

small changes to the test.

@aprantl Could you please give your opinion on the inlined questions? Thanks!

@aprantl Thanks for the review! I added inline questions asking for your opinion about consistency vs guideline.

addressing comments from @inglorion

@inglorion That makes a lot of sense. Maybe we don't even need -g, because -S -emit-llvm shows source_filename. I'll run some more experiments with relpath/abspath and debug locations, and submit a revised patch. Thanks for the comment!

Friendly Ping. Thanks!

Rebase. Fix test/CodeGen/X86/and-sink.ll that added 9days ago.

Ping. thanks!

Yes I observed the case from refresh_potential function in spec2006 429.mcf. The original C code snippet is below:

@aprantl I like the idea of having a convenience function. I'm afraid I still don't understand @dblaikie on getMergedLocation is better than the proposed convenience function in preventing buggy profile.

Friendly Ping. Thanks!

In D29833#682865, @probinson wrote:

In D29833#682595, @twoh wrote:

I don't have strong opinion about scope, because anyway we won't be able to have precise scope. Taking DISubprogram of the destination instruction might be a conservative option.

Mmmm... Does scope imply source file? LTO can inline across CUs, then merging an instruction from CU#1 into a scope from CU#2 would make the line number meaningless.

Addressing @aprantl's comments. Thanks!

@eric_niebler Do you want any more experiments with this patch? I think Windows machines not printing warnings/fixits for absolute path is a separate issue with this.

Personally I prefer the existing API, because it doesn't allow the transient state before merging. For example, in lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp in this patch, DebugLoc of NewSI is not actually valid after line 1430. Existing API doesn't have this problem.

Now avx512-fsel.ll is auto-generated from the script.

Some tests need to be updated as new DebugLoc changes instruction ordering.

Ping. Thanks!

@eric_niebler I just tried it on Windows machine, and it just succeeded with no warnings/fix-it. Is that expected?

nit: auto

Use MachineBasicBlock::findBranchDebugLoc instead of getBranchDebugLoc

Make it explicit that the test doesn't support windows. @eric_niebler, my original intention was avoiding use of platform-dependent path separator, but now made it explicit that the test is not for windows, it should be okay to use '/'. Thanks for the comments!

Thanks for the review!