this does not feel like the right solution, but even if it is, this will hurt us; we *commonly* have shaders with single basic blocks exceeding 1000 instructions, and splitting them could sabotage scheduling quite badly. in the worst case, it could guarantee spilling, by splitting the block at a point that creates too many live values between the top and bottom.

This looks like it might fix the problem we've been having, but i'm still extremely nervous about the overall concept. this feels like a fantastically large amount of machinery for such a small optimization, including this dubiously defined "isRenamable" flag that applies to operand registers even though renamability seems to be more of a property of the instruction.

got the approval from puyan so i'm gonna push this later unless someone else has some other comments!

LGTM, though it'd be interesting to see if there's any other cases where (FOO (ROTATE pattern) [...]) gets torn apart besides FOO == truncate.

Updated patch and added comments.

In D40049#939097, @spatel wrote:

My understanding of 'reassociate' isn't good enough to approve this, but I'm curious about running the main loop multiple times (ReassociateStep) because I noticed an improvement in some other code by running the pass twice.

1. Can we split that part into a preliminary patch?
2. Is it too expensive in compile time to run that to a fixed-point (like instcombine)?

In D38313#937267, @zvi wrote:

In D38313#936422, @escha wrote:

Two comments on the trunc thing:

1. Thank you!!! As a GPU target maintainer, one of my main frustrations is how much LLVM *loves* to generate code that is needlessly too wide when smaller would do. We mostly have avoided this problem due to being float-heavy, but as integer code becomes more important, I absolutely love any chance I can get to reduce 32-bit to 16-bit and save register space accordingly.

Sometimes it's LLVM, and sometimes it's the frontend that is required to extend small typed values before performing operations.

2. I'm worried about this because the DAG *loves* to eliminate """redundant""" truncates and extensions, even if they're both marked as free. I've accidentally triggered infinite loops many times when trying to trick the DAG into emitting code that keeps intermediate variables small, an extreme example being something like this:

; pseudo-asm
; R1 = *b + (*a & 15);
; R2 = *c + (*a >> 16) & 15;
load.32 R0, [a]
load.32 R1, [b]
load.32 R2, [c]
shr.32 R0H, R0, 16
and.16 R0L, R0L, 15
and.16 R0H, R0H, 15
add.32 R1, R1, R0L
add.32 R2, R2, R0H

The DAG will usually try to turn this into this:

load.32 R0, [a]
load.32 R1, [b]
load.32 R2, [c]
shr.32 R3, R0, 16
and.32 R0, R0, 15
and.32 R3, R3, 15
add.32 R1, R1, R0
add.32 R2, R2, R3

this is just a hypothetical example but in general this makes me worry from past attempts at experimentation in this realm.

Not sure I fully understand the concern of this patch, but if the problem is root caused to Instruction Selection, shouldn't we fix it there? If DAGCombiner's elimination of free truncates/extensions is an issue, have you considered predicating the specific combines with TLI hooks?

Even if they're not redundant, it's something we still don't want.

Two comments on the trunc thing:

Regardless of semantics, this patch almost surely causes a major problem for us.

In D37989#936337, @scanon wrote:

IEEE 754 rules are that everything canonicalizes except bitwise operations (copy, abs, negate, copysign) and decimal re-encoding operations (which you don't care about).

turkey week is over pls glance at patch, thank

*gentle bump*

Closing to start a real patch review.

what is the purpose of this transform? why is the new form considered more canonical?

In D39340#913756, @fhahn wrote:

In D39340#910844, @escha wrote:

Hmm, reading through N-ary reassociate, it looks like it has similar goals but is not completely overlapping in action, for better or worse.

N-ary reassociate runs in dominator order and looks to see if any subexpressions of the current computation have already been computed.

But as far as I understand, it does not consider *reassociating expressions* to find those redundancies. In other words, it doesn't consider the N^2 possible sub-combinations of previous expressions; it only considers them in the order they were emitted. Its main goal seems to be optimizing addressing expressions. So for example, if you have (a+b) and a later expression computes (a+(b+2)), it can find that this is redundant. But if you have (a+(b+1)) and (a+(b+2)) but no (a+b), I don't think it handles that. It also only runs in dominator order, so it can't find arbitrary redundancies.

Similarly, my change doesn't handle GetElementPtr in the way N-ary reassociate does, since it wasn't targeted at addressing expressions.

So I agree they're redundant, and kind of share similar goals and purposes, but annoyingly I don't see any way to unify them and achieve the goals of both.

Thanks. I suppose it should be possible to to extend Reassociate to support GetElementPtr, and then we would get wha NaryReassociate provides with your patch? I am not saying this should be part of this patch, I am just trying to understand how we can build on this patch.

*poke*

Oh and of course because N-ary uses SCEV it cannot possibly handle floating point without a huge extension of SCEV, I think.

Hmm, reading through N-ary reassociate, it looks like it has similar goals but is not completely overlapping in action, for better or worse.

In D39340#909644, @dberlin wrote:

This seems very similar to what n-ary reassociate wants to do, I'd like to understand why we shouldn't do it there?
(where it seems to fit perfectly)

We use this function but we don't use the addrspace argument.

That really surprises me that it's faster! I would expect SFU functions like RCP/RSQRT to dwarf the cost of a multiply, especially for double.

Don't be too embarrassed; when we switched internally from an rcp(rsqrt(x)) expansion to x * rsqrt(x), we *also* completely missed this, and literally only found the bug when it showed up as internal test failures. The new expansion was even brought up and talked about at a team meeting and signed off by multiple people, and nobody thought to consider the number zero, myself included.

afaik, x * rsqrt(x) is wrong when x is zero (it gives NaN instead of 0). we use x * rsqrt(x) for our expansion, but we have to use an extra select_cc to handle the zero special case.

Confirmed this fixes the problem I was having.

Thanks for looking into this painful little bundle of nested semantic problems.

Might it be better to just bail if ShiftBits is zero? This seems like a classic case of "trying to optimize a node that itself is going to disappear when it gets combine()'d", so maybe we should just not do this "optimization" if the shift is no shift at all.

Sadly, the original version of this pass was *very* much not designed for the case of loading the same location multiple times in a single basic block... as you can probably tell.

Closing for now; it looks like this can interfere with address mode folding (e.g. on x86_64 where 32->64 zext is free), even though it makes logical sense.

This would work with 'sub' too, right?

Is this correct? I thought "nnan" on an instruction meant that we can optimize it assuming its inputs and outputs aren't NaN -- not that we can assume *for other instructions, that aren't fast-math* that *their inputs* aren't NaN.

As the author of some of that code, it is quite possible the code is just not well-written and can be done better ;-)

Make sure to check that the alias analyses are set up properly in the TM; this bit me when I implemented this out of tree (i.e. confirm that the AA queries are succeeding).

x = NaN

y = 0

fmin(x, fmax(x, y)) -> x ?
fmin(x, fmax(NaN, 0)) -> x ?
fmin(NaN, 0) -> x ?
fmin(NaN, 0) -> 0
0 != x

My intuition would be -- if loading using the texture cache doesn't change the result, but rather is just a performance thing, that would seem to be something you'd set with metadata on the instruction, right?

This is a nice solution -- instead of worrying too much about LLVM float semantic definitions, just let the target say how it implements things.

Some might be, as this code is fairly old. Here’s an extremely blind copy paste of our code:

LGTM. We actually do this out of tree in our backend for ADD, SUB, MUL, SHL (since we'd rather truncate inputs than do a larger op and truncate that), so it seems more than reasonable to me.

As far as I know -- "Custom" means something is not legal, but has a custom lowering. It has nothing to do with how it's implemented on the target; it just means that the target has a custom legalization hook (as opposed to Expand or such, which means it doesn't have any custom hook).

Our target has a legal FABS (it is in fact, free, as it's a modifier). But it's implemented as FADD DST, SRC.ABS, -0.0, which may modify bits other than the top bit.

LGTM

Poking this thread.

I am slightly afraid to silently modify the behavior of MaxCount to affect full unrolling (when it didn't before) because out of tree users may be using it.

Added commandline options and a test.

Ironically it looks like MaxCount itself doesn't even have a commandline option either... should I introduce one for both? :/ it feels wrong to bloat the commandline options like this, I guess

For your target there is a case when full unroll fails and then partial fails as well. And when patch applied partial unroll is successful. Right? So you can create target test.

Adding full context.

Yes, I understand that, but what I mean is, the bug won't trigger because we *will* get to the path that corrects Count because UnrolledSize > UP.PartialThreshold with Count = 9, and then it'll lower Count to 3. So we won't end up with a Count that isn't evenly dividing into 9.

I don't *think* it's possible for that problem to happen under normal circumstances without FullUnrollMaxCount being set. Normally, the only way we can fail to do full unrolling is if the full unroll cost is greater than Threshold. In this case, we'll go try partial unrolling, and we'll also be above the partial threshold (since a partial threshold higher than Threshold doesn't make sense), and it'll take the path that makes the count modulo-correct.

What sort of test case should I do for this (which behavior are you looking to test)? Should I make a commandline option so that this can easily be tested via 'opt'?

Going by the code, Count is emphatically not what I want:

That's what UP.Count is intended to do: let the target suggest an unroll count it deems reasonable.

Ugh, my mistake, I missed one hunk when uploading the diff; the hunk where the variable was used! My mistake.

FullUnrollMaxCount isn't used anywhere because it's a TTI option used by our out of tree target.

Thanks for catching this off-by-one.

Ah okay, I think now (looking at this a bit more) I understand why this cost keeps showing up in the profile. Like you said, it also happens during the main InstCombine run as well. Specifically, we have lots of loads and intrinsics with all constant operands that can't be folded (since they're runtime, not compile-time constants). So when running ConstantFoldInstruction, it's forced to call SimplifyConstantExpr on every operand, even though that ends up doing absolutely nothing. The results then get thrown away because you can't constant-fold a load to something whose value isn't known at compile time.

Yeah, I don't understand that part either!

Why not do the following:

1. Drop instructions that are dead.
2. Check to see if any ConstExpr operands are foldable, and update the instruction
3. If constant, fold the constant. [no longer needs to consider constexprs]
4. Add to the initial instcombine worklist.

To try to be more clear, this code appears to:

I believe this code is in the initial portion of instcombine that creates the initial worklist; it isn't run iteratively at all, at least if I remember right.

Updated diff with some context.

What git option do I use to get a diff with full context?

Added a test to make sure that resizing is enough to insert N elements without reallocation for a variety of sizes.

Use llvm::all_of.