[GISel]: Process new insts to legalize in the order they were created

[aditya_nandakumar]

Summary

Previously, we were legalizing new instructions in the order they were created (using the MIRBuilder). My previous patch to add a clean up combiner ended up chaining the order of how we process the instructions (in the worklist) from top down to bottom up.
While this shouldn't be an issue (legalization should only look at one instruction), there's some out of tree code that looks at other instructions as well, and this is breaking the legalization for that instruction.

This patch reverts the legalization processing order of newly created insts to how they were before the clean up combiner - but still cleans up artifacts.

[kristof.beyls]

While this shouldn't be an issue (legalization should only look at one instruction), there's some out of tree code that looks at other instructions as well, and this is breaking the legalization for that instruction.

I'm a bit confused by the above. Should we allow legalization to look at other instructions, or should we not?

lib/CodeGen/GlobalISel/Legalizer.cpp

55

I don't think I've seen the naming convention of ending type names with "Type" in the LLVM code base - but I also by far haven't looked at all the LLVM code.
Maybe "struct WorkList" would be better.

I find it unfortunate that we would need to create a custom container here for this single specific use case. Is there really not a pre-existing container that is good enough? My guess is that this WorkListType's advantage over a deque is only that it can check quickly if an element is present in the container. Is that really such a frequent operation that that must be fast, but removing that element if present doesn't have to be faster than deque.erase?

94

unordered_set could be used instead of set?

[qcolombet]

I'm a bit confused by the above. Should we allow legalization to look at other instructions, or should we not?

I believe we shouldn't allow to look at other instructions. I am guessing we need to do that to perform combines at legalization time and I think we shouldn't go in that direction. I would rather have the combines be a separate pass. I.e., we are not taking the same approach as SelectionDAG here.

Aditya, is this really needed to perform legalization?

[aemerson]

In D38200#893343, @qcolombet wrote:

I'm a bit confused by the above. Should we allow legalization to look at other instructions, or should we not?

I believe we shouldn't allow to look at other instructions. I am guessing we need to do that to perform combines at legalization time and I think we shouldn't go in that direction. I would rather have the combines be a separate pass. I.e., we are not taking the same approach as SelectionDAG here.

Aditya, is this really needed to perform legalization?

Agree, it seems strange for legalisation to need to do this, given that defs could be conceivably hoisted outside of the user's block.

If top-down processing is really necessary, i.e. legalisation really does need to inspect multiple instructions, then the current block iteration strategy will need changing anyway: we're currently doing a linear walk of the blocks when an RPO walk will be needed to ensure defs are processed first.

[aditya_nandakumar]

In D38200#893182, @kristof.beyls wrote:

While this shouldn't be an issue (legalization should only look at one instruction), there's some out of tree code that looks at other instructions as well, and this is breaking the legalization for that instruction.

I'm a bit confused by the above. Should we allow legalization to look at other instructions, or should we not?

I might have not framed that sentence correctly. I meant to say I realized about the dependency on legalization order when I added the LegalizationCombiner. I also think that shouldn't be happening here. I was only trying to revert to the original order in this patch, but I agree that it's a dangerous path to go down.

[aditya_nandakumar]

lib/CodeGen/GlobalISel/Legalizer.cpp

55

Thanks for the naming convention tip. "struct Worklist" does sound better.
I wanted a SetVector's equivalent which lets me do push_back and pop_front . As you said, the advantage over just the deque is quickly lookup if an element already exists. That said, I haven't measured how critical this is or how frequently this operation occurs.

[aditya_nandakumar]

Regarding looking at multiple instructions, One of the use cases I see is something like this.
t = G_ICMP <pred> a, b
s = G_SELECT t, c, d
On targets where selects are not legal, and we want something like the SELECT_CC, we'd need to generate something similar to
CUSTOM_SELECT_CC a, b, c, d, <pred>. This would require looking at the more than the select.
Of course, we can create a select_cc just locally (compare with 0) and let the combiner deal with it later, but that seems wasteful.

[volkan]

I think this is no longer required, rL318210 fixed this problem.

lib/CodeGen/GlobalISel/Legalizer.cpp

 void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<TargetPassConfig>();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 void Legalizer::init(MachineFunction &MF) {
 }
 
+struct WorkListType {
+  WorkListType() = default;
+
+  void push_back(MachineInstr *MI) {
+    // Do not push back duplicates.
+    if (!S.count(MI)) {
+      Q.push_back(MI);
+      S.insert(MI);
+    }
+  }
+
+  void insert(MachineInstr *MI) { push_back(MI); }
+
+  MachineInstr *pop_front_val() {
+    MachineInstr *V = Q.front();
+    Q.pop_front();
+    S.erase(V);
+    return V;
+  }
+
+  bool remove(MachineInstr *MI) {
+    if (S.erase(MI)) {
+      auto It = find(Q.begin(), Q.end(), MI);
+      assert(It != Q.end() && "Invalid element in list");
+      Q.erase(It);
+      return true;
+    }
+    return false;
+  }
+
+  bool empty() const { return Q.empty(); }
+  unsigned size() const { return Q.size(); }
+  MachineInstr *operator[](uint64_t n) const {
+    assert(n < Q.size() && "Access out of range!");
+    return Q[n];
+  }
+
+private:
+  std::deque<MachineInstr *> Q;
+  std::set<MachineInstr *> S;
+};
+
 bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
   // If the ISel pipeline failed, do not bother running that pass.
   if (MF.getProperties().hasProperty(
           MachineFunctionProperties::Property::FailedISel))
     return false;
   DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
   init(MF);
   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
for (auto MI = MBB.begin(); MI != MBB.end(); MI = NextMI) {
       // good chance MI will be deleted.
       NextMI = std::next(MI);
 
       // Only legalize pre-isel generic instructions: others don't have types
       // and are assumed to be legal.
       if (!isPreISelGenericOpcode(MI->getOpcode()))
         continue;
       unsigned NumNewInsns = 0;
-      using VecType = SetVector<MachineInstr *, SmallVector<MachineInstr *, 8>>;
-      VecType WorkList;
-      VecType CombineList;
+      WorkListType WorkList;
+      WorkListType CombineList;
       Helper.MIRBuilder.recordInsertions([&](MachineInstr *MI) {
         // Only legalize pre-isel generic instructions.
         // Legalization process could generate Target specific pseudo
         // instructions with generic types. Don't record them
         if (isPreISelGenericOpcode(MI->getOpcode())) {
           ++NumNewInsns;
           WorkList.insert(MI);
           CombineList.insert(MI);
         }
       });
       WorkList.insert(&*MI);
       LegalizerCombiner C(Helper.MIRBuilder, MF.getRegInfo());
       bool Changed = false;
       LegalizerHelper::LegalizeResult Res;
       do {
         assert(!WorkList.empty() && "Expecting illegal ops");
         while (!WorkList.empty()) {
           NumNewInsns = 0;
-          MachineInstr *CurrInst = WorkList.pop_back_val();
+          MachineInstr *CurrInst = WorkList.pop_front_val();
           Res = Helper.legalizeInstrStep(*CurrInst);
           // Error out if we couldn't legalize this instruction. We may want to
           // fall back to DAG ISel instead in the future.
           if (Res == LegalizerHelper::UnableToLegalize) {
             Helper.MIRBuilder.stopRecordingInsertions();
             if (Res == LegalizerHelper::UnableToLegalize) {
               reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
                                  "unable to legalize instruction", *CurrInst);
#ifndef NDEBUG
                           E = WorkList.size();
                  I != E; ++I)
               DEBUG(dbgs() << ".. .. New MI: " << *WorkList[I];);
 #endif
         }
         // Do the combines.
         while (!CombineList.empty()) {
           NumNewInsns = 0;
-          MachineInstr *CurrInst = CombineList.pop_back_val();
+          MachineInstr *CurrInst = CombineList.pop_front_val();
           SmallVector<MachineInstr *, 4> DeadInstructions;
           Changed |= C.tryCombineInstruction(*CurrInst, DeadInstructions);
           for (auto *DeadMI : DeadInstructions) {
             DEBUG(dbgs() << ".. Erasing Dead Instruction " << *DeadMI);
             CombineList.remove(DeadMI);
             WorkList.remove(DeadMI);
             DeadMI->eraseFromParent();
           }