[CGP] Relax a bit restriction for optimizeMemoryInst to extend scope

[skatkov]

Summary

CodeGenPrepare::optimizeMemoryInst contains a check that we do nothing
if all instructions combining the address for memory instruction is in the same
block as memory instruction itself.

However if any of these instruction are placed after memory instruction then
address calculation will not be folded to memory instruction.

The added test case shows an example.

[efriedma]

lib/CodeGen/CodeGenPrepare.cpp

4245

This is quadratic in the number of instruction in the BB.

[skatkov]

This should be better, please take a look.

[efriedma]

lib/CodeGen/CodeGenPrepare.cpp

4361

This is still essentially quadratic: optimizeMemoryInst itself is called in a loop which iterates over the basic block.

[skatkov]

lib/CodeGen/CodeGenPrepare.cpp

4361

Do you see a better way to detect that all instructions in AddrModeInsts is defined earlier than MemoryInst or you just propose to drop this improvement due to its complexity?

[skatkov]

ok, I will think whether it can be improved further...

[skatkov]

Any hints are appreciated :)

[efriedma]

Err, wait a sec... you don't need to check dominance at all.

The point of the check is to make sure we don't end up in an infinite loop: if we already sank the addressing mode, we don't want to sink it again.

If we didn't look through a PHI node to come up with an instruction in AddrModeInsts, it must dominate the memory instruction because the IR wouldn't be valid otherwise, so checking dominance is useless. If we did look through a PHI node to come up with an instruction in AddrModeInsts, it isn't really local anyway; we're using the PHI node, not the instruction itself, so the dominance relationship is irrelevant.

So I think the right solution here is to actually track how we came up with each instruction in AddrModeInsts, and skip the IsNonLocalValue check for the ones that came from PHI nodes.

[skatkov]

Good point. Meaning that if we traversed through Phi node it means that even it is in the same block, address computation is after memory instruction, otherwise it would not traverse Phi node. I will take a look into this deeper.

Side note, actually I think that the second reason for this check is to allow selection dag to use address folding. It traverses the instructions from the last one to the first one in basic block. So if addressing computation in the other basic block or after current memory instruction it will not be able to fold address computation to memory instruction...

[skatkov]

Thank you Eli for the idea.

Please take a look.

[efriedma]

LGTM

lib/CodeGen/CodeGenPrepare.cpp

 
 /// Sink addressing mode computation immediate before MemoryInst if doing so
 /// can be done without increasing register pressure.  The need for the
 /// register pressure constraint means this can end up being an all or nothing
 /// decision for all uses of the same addressing computation.
 ///
 /// Load and Store Instructions often have addressing modes that can do
 /// significant amounts of computation. As such, instruction selection will try
 /// to get the load or store to do as much computation as possible for the
 /// program. The problem is that isel can only see within a single block. As
 /// such, we sink as much legal addressing mode work into the block as possible.
 ///
 /// This method is used to optimize both load/store and inline asms with memory
 /// operands.  It's also used to sink addressing computations feeding into cold
 /// call sites into their (cold) basic block.
 ///
 /// The motivation for handling sinking into cold blocks is that doing so can
if (!Consensus) {
     return false;
   }
   TPT.commit();
 
   // If all the instructions matched are already in this BB, don't do anything.
   if (none_of(AddrModeInsts, [&](Value *V) {
         return IsNonLocalValue(V, MemoryInst->getParent());
       })) {
+    // All instructions are in the same basic block.
+    // Let's ensure that all of them earlier in basic block than memory
+    // instruction.
+    SmallPtrSet<Instruction *, 16> AddrModeInstsSet(AddrModeInsts.begin(),
+                                                    AddrModeInsts.end());
+    unsigned Count = AddrModeInstsSet.size();
+    for (Instruction &I : *(MemoryInst->getParent())) {
+      if (&I == MemoryInst)
+        break;
+      Count -= AddrModeInstsSet.count(&I);
+      if (!Count)
+        break;
+    }
+    if (!Count) {
       DEBUG(dbgs() << "CGP: Found      local addrmode: " << AddrMode << "\n");
       return false;
     }
+  }
 
   // Insert this computation right after this user.  Since our caller is
   // scanning from the top of the BB to the bottom, reuse of the expr are
   // guaranteed to happen later.
   IRBuilder<> Builder(MemoryInst);
 
   // Now that we determined the addressing expression we want to use and know
   // that we have to sink it into this block.  Check to see if we have already

test/CodeGen/X86/sink-gep-before-mem-inst.ll

+; RUN: opt < %s -S -codegenprepare -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
+
+define i64 @test.after(i8 addrspace(1)* readonly align 8) {
+; CHECK-LABEL: test.after
+; CHECK: sunkaddr
+entry:
+  %.0 = getelementptr inbounds i8, i8 addrspace(1)* %0, i64 8
+  %addr = bitcast i8 addrspace(1)* %.0 to i32 addrspace(1)*
+  br label %header
+
+header:
+  %addr.in.loop = phi i32 addrspace(1)* [ %addr, %entry ], [ %addr.after, %header ]
+  %local_2_ = phi i64 [ 0, %entry ], [ %.9, %header ]
+  %.7 = load i32, i32 addrspace(1)* %addr.in.loop, align 8
+  fence acquire
+  %.1 = getelementptr inbounds i8, i8 addrspace(1)* %0, i64 8
+  %addr.after = bitcast i8 addrspace(1)* %.1 to i32 addrspace(1)*
+  %.8 = sext i32 %.7 to i64
+  %.9 = add i64 %local_2_, %.8
+  %not. = icmp sgt i64 %.9, 999
+  br i1 %not., label %exit, label %header
+
+exit:
+  ret i64 %.9
+}