[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

4241

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

4371

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

[skatkov]

lib/CodeGen/CodeGenPrepare.cpp

4371

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

for (unsigned i = 0, e = MemoryUses.size(); i != e; ++i) {
     MatchedAddrModeInsts.clear();
   }
 
   return true;
 }
 
 } // end anonymous namespace
 
-/// Return true if the specified values are defined in a
-/// different basic block than BB.
-static bool IsNonLocalValue(Value *V, BasicBlock *BB) {
-  if (Instruction *I = dyn_cast<Instruction>(V))
-    return I->getParent() != BB;
+/// Return true if the specified value is defined in a
+/// different basic block than I or is defined in the same BB but after BI.
+static bool IsNonLocalValueOrAfter(Value *V, Instruction *BI) {
+  BasicBlock *BB = BI->getParent();
+  if (Instruction *I = dyn_cast<Instruction>(V)) {
+    if (I->getParent() != BB)
+      return true;
+    for (Instruction &BBI : *BB) {
+      if (&BBI == I)
+        return false;
+      if (&BBI == BI)
+        return true;
+    }
+  }
   return false;
 }
 
 /// 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.
 ///
bool CodeGenPrepare::optimizeMemoryInst(Instruction *MemoryInst, Value *Addr,
   if (!Consensus) {
     TPT.rollback(LastKnownGood);
     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());
+        return IsNonLocalValueOrAfter(V, MemoryInst);
       })) {
     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
   // done this for some other load/store instr in this block.  If so, reuse the
   // computation.
   Value *&SunkAddr = SunkAddrs[Addr];
   if (SunkAddr) {
     DEBUG(dbgs() << "CGP: Reusing nonlocal addrmode: " << AddrMode << " for "
                  << *MemoryInst << "\n");
     if (SunkAddr->getType() != Addr->getType())
       SunkAddr = Builder.CreatePointerCast(SunkAddr, Addr->getType());
   } else if (AddrSinkUsingGEPs ||
              (!AddrSinkUsingGEPs.getNumOccurrences() && TM &&
               SubtargetInfo->useAA())) {
     // By default, we use the GEP-based method when AA is used later. This

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
+}