In D147368#4238148, @xen0n wrote:

Good catch, thanks!

IMO you could include as comments your explanations to existing cases where this optimization has not taken place (e.g. "This is not optimized into bstrpick + slli because the constant has multiple uses."), so future readers wouldn't have to do archaeology to see them. The code changes LGTM.

In D147305#4238054, @xen0n wrote:

In D147305#4237973, @benshi001 wrote:

In D147305#4237944, @SixWeining wrote:

Thanks for the improvements.
So this is only for the case 2 mentioned by @xen0n, right? Seems that the test for 81 is missing.

Will case 1 and case 3 be handled later?

Thanks for your comments.

1. The missing case 81 is added.
2. I will implement case 1 and case 3 later in another patch. BTW: Total amount of these two cases is small, and they even have redundant values with case 2, so how about implementing them without foreach, just standalone Pat one by one ?

As for point 2, fine by me. Case 1 would still have many remaining constants so a macro would go a long way (you could only go over the distinct Imm1 and Imm2 and auto-compute the source constant as you did for Case 2), and only 33 would be left for Case 3 so you may write the pattern straight-forward.

In D147305#4237944, @SixWeining wrote:

Thanks for the improvements.
So this is only for the case 2 mentioned by @xen0n, right? Seems that the test for 81 is missing.

Will case 1 and case 3 be handled later?

Here are how GNU-ld handles these two relocations

In D147305#4236071, @xen0n wrote:

This is good strength reduction overall, thanks for the insight!

Though maybe the exact patterns can be automatically generated with nested loops, for reduced mental burden to prove correctness? I've sketched something and it seems doable:

>>> alsl = lambda j, k, imm: (j << imm) + k
>>> a = [alsl(alsl(1, 1, i), alsl(1, 1, i), j) for j in range(1,5) for i in range(1,5)]
>>> a
[9, 15, 27, 51, 15, 25, 45, 85, 27, 45, 81, 153, 51, 85, 153, 289]
>>> list(sorted(set(a)))
[9, 15, 25, 27, 45, 51, 81, 85, 153, 289]
>>> b = [alsl(alsl(1, 1, i), 1, j) for j in range(1,5) for i in range(1,5)]
>>> b
[7, 11, 19, 35, 13, 21, 37, 69, 25, 41, 73, 137, 49, 81, 145, 273]
>>> ab = set(a).union(set(b))
>>> len(ab)
24
>>> list(sorted(set(a).intersection(set(b))))
[25, 81]

>>> c = [alsl(1, alsl(1, 1, i), j) for j in range(1,5) for i in range(1,5)]
>>> c
[5, 7, 11, 19, 7, 9, 13, 21, 11, 13, 17, 25, 19, 21, 25, 33]
>>> list(sorted(set(c)))
[5, 7, 9, 11, 13, 17, 19, 21, 25, 33]

>>> set(c).difference(ab)
{33, 5, 17}
>>> all = set(c).union(ab).difference({3, 5, 9, 17})
>>> len(all)
24
>>> list(sorted(all))
[7, 11, 13, 15, 19, 21, 25, 27, 33, 35, 37, 41, 45, 49, 51, 69, 73, 81, 85, 137, 145, 153, 273, 289]

So basically, we can strength-reduce a total of 24 different constant-multiplications with two alsl's:

• case 1: alsl T, X, X, i; alsl Y, T, T, j: 15, 25, 27, 45, 51, 81, 85, 153, 289
• case 2: alsl T, X, X, i; alsl Y, T, X, j: 7, 11, 13, 19, 21, 25, 35, 37, 41, 49, 69, 73, 81, 137, 145, 273
• case 3: alsl T, X, X, i; alsl Y, X, T, j: 7, 11, 13, 19, 21, 25, 33

Problem is that there are some overlaps between the 3 possible combinations, and some inside case 1 and 3. If we could somehow avoid producing conflicting rules then probably leveraging TableGen's loop and computation abilities would produce code that's easier to maintain. Otherwise, simplifying the code with some macros could also be beneficial.

Multiplication with some specific immediates can be simplified to a pair of ALSL.

In D147221#4233243, @xen0n wrote:

Nit: this is preparatory change adding baseline test cases for D147222, so the title may be tweaked a little bit, or you may add some commit message, to not suggest such tests were totally absent otherwise.

Otherwise LGTM, thanks.

These three relocations are handled in GNU-ld as following

Please refer to gun-ld,

ping ...

ping ...

Here is the cost of short jmp

In D146216#4225135, @MaskRay wrote:

Replacing an instruction to two likely makes the execution slower, so I think since we don't implement linker relaxation for AVR, we should not do the jmp/call rewriting as well.

ping ...

In D145646#4213975, @MaskRay wrote:

In D145646#4213547, @gulfem wrote:

We started seeing a test failure in avr-ld.c.

/b/s/w/ir/x/w/llvm-llvm-project/clang/test/Driver/avr-ld.c:48:11: error: 
// LINKP: {{".*ld.*"}} {{.*}} "--defsym=__DATA_REGION_ORIGIN__=0x800100" "-plugin" {{.*}} "-plugin-opt=mcpu=atmega328"
          ^
<stdin>:1:1: note: scanning from here
Fuchsia clang version 17.0.0 (https://llvm.googlesource.com/llvm-project 0d37efdbc599e61ce2a0418723a66d6b45aea8d7)
^
<stdin>:6:239: note: possible intended match here

https://luci-milo.appspot.com/ui/p/fuchsia/builders/toolchain.ci/clang-linux-x64/b8785950851645447937/overview

I am testing a change and will fix it in one minute.

ping ...

ping ...

In D146025#4197783, @reames wrote:

It's not really clear to me what value the new tests are adding. At a minimum, this should probably be a different test file. The file you're modifying was intended to focus on the load/store vectorization - the add was only there to provide some use chain between the load and stores.

If you wanted to add some wider examples, that might be useful though.