Also, please let me know if you think it'll make sense to commit the two patches at once (once they are approved).

Addressed comments from @Meinersbur.

In D63304#1544199, @Meinersbur wrote:

In D63304#1543859, @sabuasal wrote:

You can detect this simple loop domain directly by using quering "is_singleton" but with nested loops you'll need to project out to find singletons in one dimension out of all the loop nest dimensions.

What I meant is NOT using isl at all for detecting the situation, but deriving it from the control flow graph (such as 'conditional branch found at the end of the loop instead of before'). Keep in mind this is only a [suggestion], not a requirement for me to accept this patch.

Oh I see, I only thought about this in terms of modeling in ISL instead of hacking something in ScopDetection\Info. Thanks for the suggestion.

In D63304#1543859, @sabuasal wrote:

In D63304#1542864, @Meinersbur wrote:

Thanks for the patch. Do you happen to have performance, code size numbers?

[suggestion] The algorithm for detecting non-looping basic sets is quite ISL-heavy. If the goal is to better handle loops such as

i = 0;
do {
  Stmt(i)
} while (++i <n)

did you think about recognizing them directly?
Another possibility would be to merge the singleton with the main loop. E.g. the loop above could be converted into

for (int i = 0; i < max(1,n); i+=1) 
  Stmt(i);

You can detect this simple loop domain directly by using "is_singleton" but with nested loops you'll need to project out to find singletons in one dimension out of all the loop nest dimensions.

In D63304#1543859, @sabuasal wrote:

In D63304#1542864, @Meinersbur wrote:

Thanks for the patch. Do you happen to have performance, code size numbers?

[suggestion] The algorithm for detecting non-looping basic sets is quite ISL-heavy. If the goal is to better handle loops such as

i = 0;
do {
  Stmt(i)
} while (++i <n)

did you think about recognizing them directly?
Another possibility would be to merge the singleton with the main loop. E.g. the loop above could be converted into

for (int i = 0; i < max(1,n); i+=1) 
  Stmt(i);

You can detect this simple loop domain directly by using "is_singleton" but with nested loops you'll need to project out to find singletons in one dimension out of all the loop nest dimensions.

In D63304#1542864, @Meinersbur wrote:

Thanks for the patch. Do you happen to have performance, code size numbers?

[suggestion] The algorithm for detecting non-looping basic sets is quite ISL-heavy. If the goal is to better handle loops such as

i = 0;
do {
  Stmt(i)
} while (++i <n)

did you think about recognizing them directly?
Another possibility would be to merge the singleton with the main loop. E.g. the loop above could be converted into

for (int i = 0; i < max(1,n); i+=1) 
  Stmt(i);

You can detect this simple loop domain directly by using quering "is_singleton" but with nested loops you'll need to project out to find singletons in one dimension out of all the loop nest dimensions.

Apologies for the late response

Thank you for updating this.

LGTM!

In D52961#1265204, @asb wrote:

In D52961#1261196, @sabuasal wrote:

In D52961#1258464, @asb wrote:

No real reason to prefer one or the other when they're semantically identical. It's mostly to be closer to gas/gcc which uses addi at least for the isInt<12> case.

I see. makes sense. I just checked gcc and it seems to be favoring addi for that case.

Does this look good to you then?

Do you need to update test/CodeGen/RISCV/compress.ll to add an 64 bit run line?

In D52961#1258464, @asb wrote:

In D52961#1258446, @sabuasal wrote:

The helper makes it clear to follow. Thanks!

I am just not sure why you did the change to prefer add to addiw when for 64bit? is addi faster than addiw?

No real reason to prefer one or the other when they're semantically identical. It's mostly to be closer to gas/gcc which uses addi at least for the isInt<12> case.

I see. makes sense. I just checked gcc and it seems to be favoring addi for that case.

The helper makes it clear to follow. Thanks!

comments addressed in committed version rL342675.

• Simplified the test case.
• Added it to inline-varargs instead of having it in a separate file.

In rL335786#257591, @brucehoult wrote:

Can something similar to this be done where the user is a load or store?

You quite often get things like...

lui r1, #nnnnn
addi r1,#nnn
lw r2 nnn(r1)

... for example to access a field in a global. The addi can be merged into the lw offset and the lui adjusted appropriately.

Updated comments by @asb .

Perhaps we should update the test to not rely on label names on the first place.

commits: https://reviews.llvm.org/D45748

committed in: https://reviews.llvm.org/rL333455

• Added comment to the peephole to mention that it might be better as a machine function pass.
• Added one extra test case to test.

• Added a test case that shows this patch inability to deal with global address nodes spanning multiple blocks.

In D45748#1111477, @asb wrote:

In D45748#1110695, @sabuasal wrote:

In D45748#1110644, @asb wrote:

I'm happy to land this patch as-is. It generates good code in a wide variety of cases (more so than many other backends). But please add the above example to your test file with a note about the missed optimisation opportunity.

The example is actually already added to the test (define dso_local i32 @load_half() nounwind).

Sorry, I was focusing on the diff and had forgotten you already added this in the previous patch. Thanks!

On the other hand, after some chat with @efriedma I am starting to think that this whole thing could be better handled with a machine function Pass that runs after MachineCSE. Your point in your original longer example (and the example I have in the test case called control_flow) shows that we are getting different notes for the lowered global address (just run llc with --stop-before=machine--cse), hasUseOnce always considers the uses within the basic block you are on, not the whole function (which makes sense). The reason these two examples worked (and by worked I mean NOT having the offset merged back into the global address lowering) is because the ADDI generated for the offset was folded into the Load\STore and my peephole found no Tail to kick in. If we add a MachineFunctionPasss we we will have:

I agree with your analysis. It's conceivable you could have an IR pass that tries to improve codegen, but it would have to operate based on assumption about how global lowering would work. I think as you suggest, a machine function pass is promising.

So would the plan be to always generate offset separate from the global (as is current upstream behaviour after your recent patch), and to opportunistically merge the offset in the case the the global base only has a single reference, or (optionally, probably less common) every reference using that base has the same offset.

In D45748#1110644, @asb wrote:

The point I was trying to make is that even with these peepholes, there are trivial cases that aren't caught, such as the example I shared:

@foo = global [6 x i16] [i16 1, i16 2, i16 3, i16 4, i16 5, i16 0], align 2                                     
                                                                                                                
define i32 @main() nounwind {                                                                                   
entry:                                                                                                          
  %0 = load i16, i16* getelementptr inbounds ([6 x i16], [6 x i16]* @foo, i32 0, i32 4), align 2                
  %cmp = icmp eq i16 %0, 140                                                                                    
  br i1 %cmp, label %if.end, label %if.then                                                                     
                                                                                                                
if.then:                                                                                                        
  tail call void @abort()                                                                                       
  unreachable                                                                                                   
                                                                                                                
if.end:                                                                                                         
  ret i32 0                                                                                                     
}                                                                                                               
                                                                                                                
declare void @abort()

This generates 3 instructions for the global access when you'd obviously prefer to use two:

lui     a0, %hi(foo)
addi    a0, a0, %lo(foo)
lhu     a0, 8(a0)

I proposed one way of adding a peephole, but don't see a way of differentiating between the case above and more complex cases where the peephole is counter-productive (such as in the longer IR sample I shared). Possible the solution would be to have an IR pass perform common subexpression elimination on the getelementptr calculations - possibly such a pass already exists.

Hi alex,

Updated the comment.

Ping?

Ping?
is this good to merge?

Hi Shiva,

Added descriptive comments for rationale behind setting the CostPerUse property.

Updated the patch to only show the peephole optimizations.

In D45748#1100940, @asb wrote:

I think we've all spent enough time looking at this to see that separating the base from offset in lowerGlobalAddress is a better starting point, even though there are a range of examples where it results in more instructions. I think we'll soon arrive at a solution that fixes the most common of those cases, but it's obviously not quite as straight-forward as originally hoped. If you'd like to land the change to lowerGlobalAddress quickly, I'd happily now review that as a standalone change. If you like, you could create a new review thread that includes that change as well as test cases that demonstrates where it helps, and cases where it's worse marked with TODO.

In D45748#1100874, @asb wrote:

I've started a discussion on GlobalAddress lowering strategy on llvm-dev here: http://lists.llvm.org/pipermail/llvm-dev/2018-May/123359.html

Your peephole code seems well written and really solid, but I'd like to discuss the dagcombiner approach some more. The sort of approach taken in rL330630 seems to catch the cases discussed in this thread and has a simpler implementation.

In D45748#1100079, @asb wrote:

I looked at this in some more detail. I have a few very rough statistics on the effect of the various peepholes on the GCC torture suite. I don't claim this is representative of real code, but of course global accesses are highly codebase dependent anyway. Stats are just on the total static instruction count, i.e. it doesn't take into account if instructions are moved from hot to cold basic blocks or vice versa.

Improvement of your proposed peephole over your patch with the peephole disabled:

• 26 files have reduced number of instructions
• 10 have an increased number of instructions
• 6 have changed output but the same static instruction count

If you then add my proposed peephole on top of that, then you see the following changes (baseline = this patch including your peephole)

• 23 files have reduced number of instructions
• 11 have increased number of instructions
• 2 have changed output but the same static instruction count

So you are saying your addition hurts size, right?

If it were doable, the ideal starting point would be the following:

• If the global base has only a single reference across the whole function, or every reference has the same offset then combine the global with offset
• If the global base has multiple references with different offsets, then never combine the global with the offset

This is exactly what I am doing in my peephole:

• Catch a tail node (RISCV::ADDI or RISCV::ADD)
• Look at the operands of the node t detect a global address lowering sequence (LUI %hi followed by and ADDI %lo)
• Look at the other operands of the tail node to catch the and reconstruct the offset. (it can be just an operand if the tail is an ADDI, or you might have to reconstruct from an LUI + ADDI pair if the offset is big or just an LUI)
• Merge the offset back into the GlobalAddress if the global address only had one use. We can trust that at this point because ALL the blocks have RISCV target nodes.

I think the above two rules would be sensible regardless of whether you are linking statically or e.g. dynamic linking with PIC. Unfortunately we don't have access to that information at the point we'd like to make a decision about combining an offset. A particular lui+addi of a global may have only a single use, but that global may be referenced many times in the function. New TargetGlobalAddress nodes are introduced each time rather than reusing them. In these cases, MachineCSE can remove redundant instructions as long as different offsets aren't folded into the global. Unless we can force the reuse of identical TargetGlobalAddress nodes we can't easily write a peephole pass that respects the two rules proposed above. This input shows the problem well:

@a = internal unnamed_addr global [4 x i32] zeroinitializer, align 4

; Function Attrs: noreturn nounwind
define dso_local i32 @main() local_unnamed_addr #0 {
entry:
  %0 = load i32, i32* getelementptr inbounds ([4 x i32], [4 x i32]* @a, i32 0, i32 0), align 4
  %cmp = icmp eq i32 %0, 0
  br i1 %cmp, label %if.end, label %if.then

if.then:                                          ; preds = %entry
  tail call void @abort() #3
  unreachable

if.end:                                           ; preds = %entry
  %1 = load i32, i32* getelementptr inbounds ([4 x i32], [4 x i32]* @a, i32 0, i32 1), align 4
  %cmp1 = icmp eq i32 %1, 3
  br i1 %cmp1, label %if.end3, label %if.then2

if.then2:                                         ; preds = %if.end
  tail call void @abort() #3
  unreachable

if.end3:                                          ; preds = %if.end
  %2 = load i32, i32* getelementptr inbounds ([4 x i32], [4 x i32]* @a, i32 0, i32 2), align 4
  %cmp4 = icmp eq i32 %2, 2
  br i1 %cmp4, label %if.end6, label %if.then5

if.then5:                                         ; preds = %if.end3
  tail call void @abort() #3
  unreachable

if.end6:                                          ; preds = %if.end3
  %3 = load i32, i32* getelementptr inbounds ([4 x i32], [4 x i32]* @a, i32 0, i32 3), align 4
  %cmp7 = icmp eq i32 %3, 1
  br i1 %cmp7, label %if.end9, label %if.then8

if.then8:                                         ; preds = %if.end6
  tail call void @abort() #3
  unreachable

if.end9:                                          ; preds = %if.end6
  tail call void @exit(i32 0) #3
  unreachable
}

declare void @abort()

declare void @exit(i32)

Let me take a closer look at this test case. But I think SelectionDAG builder should be able
to merge the TargetNodes if they refer to the same address.

In D45748#1099689, @asb wrote:

Thanks for the update Sameer. I've been evaluating this patch today. I was curious about the decision to perform a peephole rather than a DAG combine. You mention that the DAG combiner doesn't work for uses spanning multiple basic blocks, but doesn't the SelectionDAG (and hence RISCVISelDAGToDAG) also work on a per-basic-block granularity?

Yes. Here is the problem with DAG combine:

• In our optimization we lower the Global address in a target global address and an ISD::ADD (a generic node, not target specific node)
• We create a DAG combine that does a call back for ISD::ADD.
• Right after the lowerGlobalAddress is done you hit the DAG combiner function. Now at this point other blocks are yet to be processed and the global address there is still not lowered into a TargetGlobalAddress, in other blocks (as listed in the the IR test I added called "control_flow") so the Target node we created only has one use only. Our combiner check will go back and put the offset back in the target lowering because it simply doesn't know.

• Updated tests and formatting.
• Added peepholes to handle corner cases, handling these cases with dag combiner doesn't work for uses spanning multiple basic blocks (dag combiner works on BB level),