[GlobalISel] Add bailout thresholds to CSEMIRBuilder::dominates() and the localizer.

[aemerson]

Summary

dominates(A, B) tries to determine dominance by walking an iterator from the beginning of the block potentially until the end. In extremely large BBs this can result in very long compile times, since this is called often from the artifact combiner.

The localizer's intra-block localization phase does a similar thing and walks through each instruction in the block top-down, checking if next instruction is the user set of the localizing instruction. Add a bailout threshold here too.

Longer term we may want to explore algorithmic changes to the code to alleviate these issues, perhaps by using lazy instruction numbering within blocks.

I arrived at these thresholds by building the test suite including SPEC2006, and choosing thresholds that were high enough that they wouldn't fire, going one order of magnitude higher.

[aditya_nandakumar]

llvm/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp

38

This change looks concerning.
If this method returns false, it implies that A does not dominate B, and getDominatingInstrForID ends up moving the instruction to the current position. Is this what you're trying to do? (I suspect not).

[aemerson]

llvm/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp

38

Right, I'd forgotten that getDominatingInstrForID() assumes that A and B are in the same block before its calls dominates(). I'll try passing in a return parameter to signal back when the search was aborted early?

[aditya_nandakumar]

llvm/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp

38

That would work. Though I'm not sure if this is the best way to go about - what we'll end up with is a MachineFunction that may or may not have CSE'd instructions (even though it could be). If CSE is being relied upon for canonicalization, this may not be the right approach (where depending on where an instruction is, it may or may not be CSEd).
Alternatively we can make this a part of the CSEConfig which allows targets to opt out of this behavior?

[arsenm]

llvm/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp

38

I don't think CSE should be a guaranteed property. I don't think we need a knob for this

[qcolombet]

Hi Amara,

dominates(A, B) tries to determine dominance by walking an iterator from the beginning of the block potentially until the end. In extremely large BBs this can result in very long compile times, since this is called often from the artifact combiner.

Instead of disabling the check, I think it would be best to fix the underlying compile time issue. The solution here would be to switch the list of MachineInstr to numbered instructions so that dominance checks become O(1).
I had meant to look at this for quite some time but didn't get a chance to do it.
Something similar has been done on LLVM IR (see https://reviews.llvm.org/D51664). I wish it was done in a way that could have benefited the Machine IR like I suggested in https://reviews.llvm.org/D51664#1389884, but this ship has sailed!

I understand this is a big under taking so I am fine with the threshold approach in the meantime.

I leave the final approval to Aditya and Matt.

Cheers,
-Quentin

[aemerson]

In D87297#2264152, @qcolombet wrote:

Hi Amara,

dominates(A, B) tries to determine dominance by walking an iterator from the beginning of the block potentially until the end. In extremely large BBs this can result in very long compile times, since this is called often from the artifact combiner.

Instead of disabling the check, I think it would be best to fix the underlying compile time issue. The solution here would be to switch the list of MachineInstr to numbered instructions so that dominance checks become O(1).
I had meant to look at this for quite some time but didn't get a chance to do it.
Something similar has been done on LLVM IR (see https://reviews.llvm.org/D51664). I wish it was done in a way that could have benefited the Machine IR like I suggested in https://reviews.llvm.org/D51664#1389884, but this ship has sailed!

I understand this is a big under taking so I am fine with the threshold approach in the meantime.

I leave the final approval to Aditya and Matt.

Cheers,
-Quentin

Yes I saw that thread, it's a shame we didn't have a shared solution for MBB too. There's probably more places where we have hidden super-linear compile time waiting to be triggered.

It's actually not quite as simple as I previously thought. The current logic in getDominatingInstrForID seems to be this:

MachineInstr *A = CSE_lookup_in_same_bb(B)
if (!dominates(A, B))
    move A before B such that dominates(A, B) is true
else
    return pointer to A

If we hit our threshold, what should getDominatingInstrForID() do? Perhaps clone the instruction A instead?

[aditya_nandakumar]

In D87297#2264223, @aemerson wrote:

In D87297#2264152, @qcolombet wrote:

Hi Amara,

dominates(A, B) tries to determine dominance by walking an iterator from the beginning of the block potentially until the end. In extremely large BBs this can result in very long compile times, since this is called often from the artifact combiner.

Instead of disabling the check, I think it would be best to fix the underlying compile time issue. The solution here would be to switch the list of MachineInstr to numbered instructions so that dominance checks become O(1).
I had meant to look at this for quite some time but didn't get a chance to do it.
Something similar has been done on LLVM IR (see https://reviews.llvm.org/D51664). I wish it was done in a way that could have benefited the Machine IR like I suggested in https://reviews.llvm.org/D51664#1389884, but this ship has sailed!

I understand this is a big under taking so I am fine with the threshold approach in the meantime.

I leave the final approval to Aditya and Matt.

Cheers,
-Quentin

Yes I saw that thread, it's a shame we didn't have a shared solution for MBB too. There's probably more places where we have hidden super-linear compile time waiting to be triggered.

It's actually not quite as simple as I previously thought. The current logic in getDominatingInstrForID seems to be this:

MachineInstr *A = CSE_lookup_in_same_bb(B)
if (!dominates(A, B))
    move A before B such that dominates(A, B) is true
else
    return pointer to A

If we hit our threshold, what should getDominatingInstrForID() do? Perhaps clone the instruction A instead?

I would expect something like

Returns None when it bailed.
HasValue && true -> Dominates
HasValue && false -> Not dominates but within threshold
Optional<bool> dominates(A, B);

MachineInstr *MI = getInstrIfExists();
if (MI) {
  if (auto Dom = dominates(MI, CurrPos)) {
    if (!*Dom)
       CurMBB->splice(CurrPos, CurMBB, MI);
    return MachineInstrBuilder(getMF(), MI);
  }
}
return MachineInstrBuilder();

[aditya_nandakumar]

llvm/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp

38

It's certainly a nice property to have. For eg, we can check if a new instruction we're building already exists and is being used just by trying building a new instruction and checking for uses of the def, which could be useful for combines (and we have at least one combine that does this in our backend). This could perhaps be enabled by other APIs but is currently unavailable.
I also think of CSE as a canonicalization and later passes can rematerialize as necessary.
Also @aemerson , does this trigger in those workloads you care about (and hence if this change is necessary at all) since you mentioned that you arrived at the limit by going one order of magnitude higher.

[arsenm]

This does touch on a bug I was looking into recently. There's a bug where if you attempt to insert an instruction, and it CSEs to the instruction at the insertion point, any new uses of the return value end up getting inserted before the instruction. I think this really needs to check for properly dominates, but it seemed a lot of cases were relying on the current behavior

llvm/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp

38

It may be a canonicalization, but I also don't think it's the MIRBuilder's job to ensure everything is canonical

[aditya_nandakumar]

llvm/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp

38

I'm not sure if you mean MIRBuilder here or the CSE mechanism. I was talking about the mechanism (the fact that we do it through builders is just implementation detail). My personal take on this is that ending up with a mechanism that doesn't guarantee CSE (assuming instructions can be CSEd) even if you enabled it fully by default, is not ideal.
Perhaps to address compile time for this issue (say O0 pipeline), we could try to observe which opcodes are responsible and selectively disable these with the CSEConfig. When I did measurements a while back among all opcodes CSEd, G_CONSTANT + FCONSTANT were responsible for about 75-80% of the hits in the test suites I looked at (out of tree), and these are usually right at the beginning and hence not a big problem for dominance queries taking too long. Obviously the longer term solution of O(1) dominance queries could be considered, but right now I don't have a better + cleaner suggestion.

[arsenm]

llvm/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp

38

I mean the MIRBuilder doing anything beyond directly inserting the instruction requested is a compile time hack. If having the MIRBuilder CSE in some situation adds compile time cost, it shouldn't need to do it

[aditya_nandakumar]

llvm/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp

38

I'm not sure I follow the argument. CSEMIRBuilder's only responsibility (and the way it's designed currently) is to do the CSE check and if not just fallback to MIRBuilder implementation. Are you suggesting CSEMIRBuilder should also not do CSE if it does more work (which it most certainly will)? That sounds like maybe the regular builder should be used (and not the CSEing).

[arsenm]

llvm/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp

38

I thought the argument for CSEMIRBuilder was that constructing an instruction is slow enough that it's cheaper to avoid creating it, and this happens often enough to give a net speedup vs. running MachineCSE later. I don't think it's particularly natural to have any kind of CSE or optimization in the builder, and it's only due to this practical compile time concern

[arsenm]

Is this still relevant?

[aemerson]

In D87297#2932894, @arsenm wrote:

Is this still relevant?

It'll be replaced by instruction numbering.

llvm/include/llvm/CodeGen/GlobalISel/CSEMIRBuilder.h

 /// 42); auto B = CB.buildConstant(s32, 42); assert(A == B); unsigned CReg =
 /// MRI.createGenericVirtualRegister(s32); auto C = CB.buildConstant(CReg, 42);
 /// assert(C->getOpcode() == TargetOpcode::COPY);
 /// Explicitly passing in a register would materialize a copy if possible.
 /// CSEMIRBuilder also does trivial constant folding for binary ops.
 class CSEMIRBuilder : public MachineIRBuilder {
 
   /// Returns true if A dominates B (within the same basic block).
-  /// Both iterators must be in the same basic block.
+  /// Both iterators must be in the same basic block. Note that if there are
+  /// more than a set threshold of instructions scanned during computation,
+  /// this will return false and exit early. Therefore, returning false does
+  /// not necessarily imply that A does *not* dominate B.
   //
   // TODO: Another approach for checking dominance is having two iterators and
   // making them go towards each other until they meet or reach begin/end. Which
   // approach is better? Should this even change dynamically? For G_CONSTANTS
   // most of which will be at the top of the BB, the top down approach would be
   // a better choice. Does IRTranslator placing constants at the beginning still
   // make sense? Should this change based on Opcode?
   bool dominates(MachineBasicBlock::const_iterator A,

llvm/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp

 //
 
 #include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 
 using namespace llvm;
 
+static cl::opt<unsigned>
+    DominatesSearchThreshold("csemib-dom-threshold",
+                             cl::desc("Max number of instructions to scan for "
+                                      "CSEMIRBuilder inst dominance checks"),
+                             cl::init(10000), cl::Hidden);
+
 bool CSEMIRBuilder::dominates(MachineBasicBlock::const_iterator A,
                               MachineBasicBlock::const_iterator B) const {
   auto MBBEnd = getMBB().end();
   if (B == MBBEnd)
     return true;
   assert(A->getParent() == B->getParent() &&
          "Iterators should be in same block");
   const MachineBasicBlock *BBA = A->getParent();
   MachineBasicBlock::const_iterator I = BBA->begin();
-  for (; &*I != A && &*I != B; ++I)
-    ;
+  for (unsigned Count = 0; &*I != A && &*I != B; ++I, ++Count) {
+    if (Count > DominatesSearchThreshold)
+      return false; // Conservatively return false.
+  }
+
   return &*I == A;
 }
 
 MachineInstrBuilder
 CSEMIRBuilder::getDominatingInstrForID(FoldingSetNodeID &ID,
                                        void *&NodeInsertPos) {
   GISelCSEInfo *CSEInfo = getCSEInfo();
   assert(CSEInfo && "Can't get here without setting CSEInfo");

llvm/lib/CodeGen/GlobalISel/Localizer.cpp

 //===- Localizer.cpp ---------------------- Localize some instrs -*- C++ -*-==//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 /// \file
 /// This file implements the Localizer class.
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/GlobalISel/Localizer.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetLowering.h"
+#include "llvm/IR/Constants.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/Debug.h"
 
 #define DEBUG_TYPE "localizer"
 
 using namespace llvm;
 
+static cl::opt<unsigned>
+    IntraBlockScanThreshold("localizer-intrablock-scan-threshold",
+                            cl::desc("Max number of unrelated insts to scan "
+                                     "over during intra-block localization."),
+                            cl::init(100000), cl::Hidden);
+
 char Localizer::ID = 0;
 INITIALIZE_PASS_BEGIN(Localizer, DEBUG_TYPE,
                       "Move/duplicate certain instructions close to their use",
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_PASS_END(Localizer, DEBUG_TYPE,
                     "Move/duplicate certain instructions close to their use",
                     false, false)
for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg)) {
         Users.insert(&UseMI);
     }
     // If all the users were PHIs then they're not going to be in our block,
     // don't try to move this instruction.
     if (Users.empty())
       continue;
 
     MachineBasicBlock::iterator II(MI);
+    // Once again don't try to scan over every instruction past a threshold.
+    // For some pathological cases with extremely large basic blocks, don't try
+    // to scan beyond a certain threshold, since this is potentially O(N^2).
+    unsigned Count = 0;
+    bool ExitedEarly = false;
     ++II;
-    while (II != MBB.end() && !Users.count(&*II))
+    Count = 0;
+    while (II != MBB.end() && !Users.count(&*II)) {
+      if (++Count > IntraBlockScanThreshold) {
+        ExitedEarly = true;
+        break;
+      }
       ++II;
+    }
+    if (ExitedEarly)
+      continue;
 
     LLVM_DEBUG(dbgs() << "Intra-block: moving " << *MI << " before " << *&*II
                       << "\n");
     assert(II != MBB.end() && "Didn't find the user in the MBB");
     MI->removeFromParent();
     MBB.insert(II, MI);
     Changed = true;
   }