[GISel]: Rework legalization algorithm for better elimination of

artifacts along with DCE

Legalization Artifacts are all those insts that are there to make the
type system happy. Currently, the target needs to say all combinations
of extends and truncs are legal and there's no way of verifying that
post legalization, we only have *truly* legal instructions. This patch
changes roughly the legalization algorithm to process all illegal insts
at one go, and then process all truncs/extends that were added to
satisfy the type constraints separately trying to combine trivial cases
until they converge. This has the added benefit that, the target
legalizerinfo can only say which truncs and extends are okay and the
artifact combiner would combine away other exts and truncs.

Updated legalization algorithm to roughly the following pseudo code.

WorkList Insts, Artifacts;
collect_all_insts_and_artifacts(Insts, Artifacts);

do {
  for (Inst in Insts)
         legalizeInstrStep(Inst, Insts, Artifacts);
  for (Artifact in Artifacts)
         tryCombineArtifact(Artifact, Insts, Artifacts);
} while(!Insts.empty());

Also, wrote a simple wrapper equivalent to SetVector, except for
erasing, it avoids moving all elements over by one and instead just
nulls them out.

llvm-svn: 318210

1 files changed, 111 insertions, 101 deletions

diff --git a/llvm/lib/CodeGen/GlobalISel/Legalizer.cpp b/llvm/lib/CodeGen/GlobalISel/Legalizer.cpp
index 59f34d730d0..1d7a220b544 100644
--- a/llvm/lib/CodeGen/GlobalISel/Legalizer.cpp
+++ b/llvm/lib/CodeGen/GlobalISel/Legalizer.cpp
@@ -14,10 +14,12 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/GlobalISel/Legalizer.h"
+#include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SetVector.h"
-#include "llvm/CodeGen/GlobalISel/LegalizerCombiner.h"
+#include "llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
 #include "llvm/CodeGen/GlobalISel/Utils.h"
+#include "llvm/CodeGen/GlobalISel/GISelWorkList.h"
 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
@@ -52,6 +54,20 @@ void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const {
 void Legalizer::init(MachineFunction &MF) {
 }
 
+static bool isArtifact(const MachineInstr &MI) {
+  switch (MI.getOpcode()) {
+  default:
+    return false;
+  case TargetOpcode::G_TRUNC:
+  case TargetOpcode::G_ZEXT:
+  case TargetOpcode::G_ANYEXT:
+  case TargetOpcode::G_SEXT:
+  case TargetOpcode::G_MERGE_VALUES:
+  case TargetOpcode::G_UNMERGE_VALUES:
+    return true;
+  }
+}
+
 bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
   // If the ISel pipeline failed, do not bother running that pass.
   if (MF.getProperties().hasProperty(
@@ -63,114 +79,108 @@ bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
   LegalizerHelper Helper(MF);
 
-  // FIXME: an instruction may need more than one pass before it is legal. For
-  // example on most architectures <3 x i3> is doubly-illegal. It would
-  // typically proceed along a path like: <3 x i3> -> <3 x i8> -> <8 x i8>. We
-  // probably want a worklist of instructions rather than naive iterate until
-  // convergence for performance reasons.
-  bool Changed = false;
-  MachineBasicBlock::iterator NextMI;
-  using VecType = SmallSetVector<MachineInstr *, 8>;
-  VecType WorkList;
-  VecType CombineList;
-  for (auto &MBB : MF) {
-    for (auto MI = MBB.begin(); MI != MBB.end(); MI = NextMI) {
-      // Get the next Instruction before we try to legalize, because there's a
-      // good chance MI will be deleted.
-      NextMI = std::next(MI);
+  const size_t NumBlocks = MF.size();
+  MachineRegisterInfo &MRI = MF.getRegInfo();
 
+  // Populate Insts
+  GISelWorkList<256> InstList;
+  GISelWorkList<128> ArtifactList;
+  ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
+  // Perform legalization bottom up so we can DCE as we legalize.
+  // Traverse BB in RPOT and within each basic block, add insts top down,
+  // so when we pop_back_val in the legalization process, we traverse bottom-up.
+  for (auto *MBB : RPOT) {
+    if (MBB->empty())
+      continue;
+    for (MachineInstr &MI : *MBB) {
       // Only legalize pre-isel generic instructions: others don't have types
       // and are assumed to be legal.
-      if (!isPreISelGenericOpcode(MI->getOpcode()))
+      if (!isPreISelGenericOpcode(MI.getOpcode()))
         continue;
-      unsigned NumNewInsns = 0;
-      WorkList.clear();
-      CombineList.clear();
-      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(),
-                          Helper.getLegalizerInfo());
-      bool Changed = false;
-      LegalizerHelper::LegalizeResult Res;
-      do {
-        assert(!WorkList.empty() && "Expecting illegal ops");
-        while (!WorkList.empty()) {
-          NumNewInsns = 0;
-          MachineInstr *CurrInst = WorkList.pop_back_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);
-              return false;
-            }
-          }
-          Changed |= Res == LegalizerHelper::Legalized;
-          // If CurrInst was legalized, there's a good chance that it might have
-          // been erased. So remove it from the Combine List.
-          if (Res == LegalizerHelper::Legalized)
-            CombineList.remove(CurrInst);
-
-#ifndef NDEBUG
-          if (NumNewInsns)
-            for (unsigned I = WorkList.size() - NumNewInsns,
-                          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();
-          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();
-          }
-#ifndef NDEBUG
-          if (NumNewInsns)
-            for (unsigned I = CombineList.size() - NumNewInsns,
-                          E = CombineList.size();
-                 I != E; ++I)
-              DEBUG(dbgs() << ".. .. Combine New MI: " << *CombineList[I];);
-#endif
-        }
-      } while (!WorkList.empty());
-
-      Helper.MIRBuilder.stopRecordingInsertions();
+      if (isArtifact(MI))
+        ArtifactList.insert(&MI);
+      else
+        InstList.insert(&MI);
     }
   }
+  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())) {
+      if (isArtifact(*MI))
+        ArtifactList.insert(MI);
+      else
+        InstList.insert(MI);
+    }
+    DEBUG(dbgs() << ".. .. New MI: " << *MI;);
+  });
+  const LegalizerInfo &LInfo(Helper.getLegalizerInfo());
+  LegalizationArtifactCombiner ArtCombiner(Helper.MIRBuilder, MF.getRegInfo(), LInfo);
+  auto RemoveDeadInstFromLists = [&InstList,
+                                  &ArtifactList](MachineInstr *DeadMI) {
+    InstList.remove(DeadMI);
+    ArtifactList.remove(DeadMI);
+  };
+  bool Changed = false;
+  do {
+    while (!InstList.empty()) {
+      MachineInstr &MI = *InstList.pop_back_val();
+      assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
+      if (isTriviallyDead(MI, MRI)) {
+        DEBUG(dbgs() << MI << "Is dead; erasing.\n");
+        MI.eraseFromParentAndMarkDBGValuesForRemoval();
+        continue;
+      }
 
-  MachineRegisterInfo &MRI = MF.getRegInfo();
-  MachineIRBuilder MIRBuilder(MF);
-  LegalizerCombiner C(MIRBuilder, MRI, Helper.getLegalizerInfo());
-  for (auto &MBB : MF) {
-    for (auto MI = MBB.begin(); MI != MBB.end(); MI = NextMI) {
-      // Get the next Instruction before we try to legalize, because there's a
-      // good chance MI will be deleted.
-      // TOOD: Perhaps move this to a combiner pass later?.
-      NextMI = std::next(MI);
-      SmallVector<MachineInstr *, 4> DeadInsts;
-      Changed |= C.tryCombineMerges(*MI, DeadInsts);
-      for (auto *DeadMI : DeadInsts)
-        DeadMI->eraseFromParent();
+      // Do the legalization for this instruction.
+      auto Res = Helper.legalizeInstrStep(MI);
+      // 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();
+        reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
+                           "unable to legalize instruction", MI);
+        return false;
+      }
+      Changed |= Res == LegalizerHelper::Legalized;
+    }
+    while (!ArtifactList.empty()) {
+      MachineInstr &MI = *ArtifactList.pop_back_val();
+      assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
+      if (isTriviallyDead(MI, MRI)) {
+        DEBUG(dbgs() << MI << "Is dead; erasing.\n");
+        RemoveDeadInstFromLists(&MI);
+        MI.eraseFromParentAndMarkDBGValuesForRemoval();
+        continue;
+      }
+      SmallVector<MachineInstr *, 4> DeadInstructions;
+      if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions)) {
+        for (auto *DeadMI : DeadInstructions) {
+          DEBUG(dbgs() << ".. Erasing Dead Instruction " << *DeadMI);
+          RemoveDeadInstFromLists(DeadMI);
+          DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
+        }
+        Changed = true;
+        continue;
+      }
+      // If this was not an artifact (that could be combined away), this might
+      // need special handling. Add it to InstList, so when it's processed
+      // there, it has to be legal or specially handled.
+      else
+        InstList.insert(&MI);
     }
+  } while (!InstList.empty());
+
+  // For now don't support if new blocks are inserted - we would need to fix the
+  // outerloop for that.
+  if (MF.size() != NumBlocks) {
+    MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
+                                      MF.getFunction()->getSubprogram(),
+                                      /*MBB=*/nullptr);
+    R << "inserting blocks is not supported yet";
+    reportGISelFailure(MF, TPC, MORE, R);
+    return false;
   }
 
   return Changed;