[GlobalISel] Add a new IR canonicalization pass

[aemerson]

Summary

This pass is intended to contain IR transformations to make GlobalISel more effective, even running at -O0.

Motivated by discussions on D51362

The only canonicalization done in this initial version is swapping of icmp operands to ensure constants are on the RHS.

[qcolombet]

Hi Amara,

Thanks for putting this up.

I like the general approach.

Couple of open questions:

• Given this is canonicalization as opposed to optimization, shouldn't this be mandatory? I.e., if GISel runs, this runs. Alternatively, should we use another name not to imply this is mandatory (like beautification, I know this is ugly :P).
• Given this runs on IR, I assume we won't need something similar at the MIR level, is that correct?
• Given this runs on IR, I am guessing there are/will be some redundant code with InstCombine. Could/should we move the core of the logic in a separate library/file that could be called directly by this pass and InstCombine.
• This kind of canonicalization could be useful to other ISels, should we make this a mandatory pass period? I.e., not tie to GISel at all.

Cheers,
-Quentin

[aemerson]

Hi Quentin,

Thanks for taking a look.

• Given this is canonicalization as opposed to optimization, shouldn't this be mandatory? I.e., if GISel runs, this runs. Alternatively, should we use another name not to imply this is mandatory (like beautification, I know this is ugly :P).

Are you referring to the enable-gisel-canonicalize option? I can remove that to force it to always run when GISel does, it's just an old habit of mine to add toggle flags for new passes.

• Given this runs on IR, I assume we won't need something similar at the MIR level, is that correct?

Not that I can see. There may be cases where we need to re-do canonicalization if legalizer breaks it, but as we discussed we should try to fix that in the offending passes if possible.

• Given this runs on IR, I am guessing there are/will be some redundant code with InstCombine. Could/should we move the core of the logic in a separate library/file that could be called directly by this pass and InstCombine.

Perhaps, for this particular case it's less code to just do it manually since it's almost trivial. I think if we wanted to share the code in future then we'd need to create a new library, to prevent LLVMCodeGen having to depend on LLVMInstCombine which would be weird.

• This kind of canonicalization could be useful to other ISels, should we make this a mandatory pass period? I.e., not tie to GISel at all.

Maybe, but we don't have a real motivating use case right now. SelectionDAG already handles the compare immediate case already at -O0. -O0 canonicalizations is where I see this being most useful in order to be on par with the other ISels, and at higher opt levels we can rely on instcombine to do most of it.

Cheers,
-Quentin

[qcolombet]

Hi Amara,

Are you referring to the enable-gisel-canonicalize option? I can remove that to force it to always run when GISel does, it's just an old habit of mine to add toggle flags for new passes.

Yes, I was referring to this.
I think it depends what's the intent: is this required for correctness (always run) or simply yield better code.
If this is for correctness (say for instance because we conservatively declare that we don't want to handle weird cases), then we should have a way to enforce (verifier) it.

There may be cases where we need to re-do canonicalization if legalizer breaks it, but as we discussed we should try to fix that in the offending passes if possible.

Sounds good to me.

I think if we wanted to share the code in future then we'd need to create a new library, to prevent LLVMCodeGen having to depend on LLVMInstCombine which would be weird.

Agree.

Maybe, but we don't have a real motivating use case right now. SelectionDAG already handles the compare immediate case already at -O0. -O0 canonicalizations is where I see this being most useful in order to be on par with the other ISels, and at higher opt levels we can rely on instcombine to do most of it.

FastISel may benefit from it as well, but I agree this is not strictly require plus we are killing fastisel, so not changing its inputs mean no need to do more validations :).

LGTM (one thing to think about is what we discuss regarding correctness vs. beautification, but that shouldn't hold this PR)

Cheers,
-Quentin

[qcolombet]

lib/CodeGen/TargetPassConfig.cpp

737

That additional line shouldn't be here I believe.

[qcolombet]

FWIW, I am still not convince this is a good thing to match SDISel behavior at O0, but this is the least bad solution of doing that IMHO.

[aemerson]

This isn't really ideal because of how trivial it is currently. The issue is that if we added the capability to InstSimplify (which is where it would fit most naturally), we'd still end up with the problem of running the whole of InstSimplify in the GlobalISel pipeline. It's reasonable for now I think so I'll commit with the changes requested.

[aditya_nandakumar]

Hi Amara - would it be possible to add this as part of AArch64 pass pipeline? Adding this to all targets would result in needless burning of compile time for targets that don't need this.

[aemerson]

In D51953#1237061, @aditya_nandakumar wrote:

Hi Amara - would it be possible to add this as part of AArch64 pass pipeline? Adding this to all targets would result in needless burning of compile time for targets that don't need this.

I expect other targets to also want to do this at some point, more often than not. I can introduce a target hook to let targets opt out, rather than opt-in, then we can assume for most target's GISel implementation that the IR's been canonicalized?

[aditya_nandakumar]

In D51953#1237504, @aemerson wrote:

In D51953#1237061, @aditya_nandakumar wrote:

Hi Amara - would it be possible to add this as part of AArch64 pass pipeline? Adding this to all targets would result in needless burning of compile time for targets that don't need this.

I expect other targets to also want to do this at some point, more often than not. I can introduce a target hook to let targets opt out, rather than opt-in, then we can assume for most target's GISel implementation that the IR's been canonicalized?

That sounds reasonable. Thanks

[aemerson]

@aditya_nandakumar I've added a target hook that defaults to enabling this.

include/llvm/CodeGen/GlobalISel/Canonicalize.h

+//===--- GISelCanonicalize.h - Canonicalize IR before GlobalISel codegen---===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_GLOBALISEL_CANONICALIZE_H
+#define LLVM_CODEGEN_GLOBALISEL_CANONICALIZE_H
+
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+class GISelCanonicalizePass
+    : public PassInfoMixin<GISelCanonicalizePass> {
+public:
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+};
+} // end namespace llvm
+
+#endif // LLVM_CODEGEN_GLOBALISEL_CANONICALIZE_H

include/llvm/CodeGen/Passes.h

/// MachineDominanaceFrontier - This pass is a machine dominators analysis pass.
   FunctionPass *createBreakFalseDeps();
 
   // This pass expands indirectbr instructions.
   FunctionPass *createIndirectBrExpandPass();
 
   /// Creates CFI Instruction Inserter pass. \see CFIInstrInserter.cpp
   FunctionPass *createCFIInstrInserter();
 
+  // Do some IR canonicalization for the GlobalISel pipeline.
+  FunctionPass *createGISelCanonicalizePass();
+
 } // End llvm namespace
 
 #endif

include/llvm/InitializePasses.h

 void initializeFloat2IntLegacyPassPass(PassRegistry&);
 void initializeForceFunctionAttrsLegacyPassPass(PassRegistry&);
 void initializeForwardControlFlowIntegrityPass(PassRegistry&);
 void initializeFuncletLayoutPass(PassRegistry&);
 void initializeFunctionImportLegacyPassPass(PassRegistry&);
 void initializeGCMachineCodeAnalysisPass(PassRegistry&);
 void initializeGCModuleInfoPass(PassRegistry&);
 void initializeGCOVProfilerLegacyPassPass(PassRegistry&);
+void initializeGISelCanonicalizePass(PassRegistry &);
 void initializeGVNHoistLegacyPassPass(PassRegistry&);
 void initializeGVNLegacyPassPass(PassRegistry&);
 void initializeGVNSinkLegacyPassPass(PassRegistry&);
 void initializeGlobalDCELegacyPassPass(PassRegistry&);
 void initializeGlobalMergePass(PassRegistry&);
 void initializeGlobalOptLegacyPassPass(PassRegistry&);
 void initializeGlobalSplitPass(PassRegistry&);
 void initializeGlobalsAAWrapperPassPass(PassRegistry&);

include/llvm/Target/TargetMachine.h

public:
 
   /// Overrides the optimization level.
   void setOptLevel(CodeGenOpt::Level Level);
 
   void setFastISel(bool Enable) { Options.EnableFastISel = Enable; }
   bool getO0WantsFastISel() { return O0WantsFastISel; }
   void setO0WantsFastISel(bool Enable) { O0WantsFastISel = Enable; }
   void setGlobalISel(bool Enable) { Options.EnableGlobalISel = Enable; }
+
+  // Return true if the IR canonicalization should be run when using GISel.
+  virtual bool shouldCanonicalizeGISel() const { return true; }
+
   void setMachineOutliner(bool Enable) {
     Options.EnableMachineOutliner = Enable;
   }
   void setSupportsDefaultOutlining(bool Enable) {
     Options.SupportsDefaultOutlining = Enable;
   }
 
   bool shouldPrintMachineCode() const { return Options.PrintMachineCode; }

lib/CodeGen/GlobalISel/CMakeLists.txt

 add_llvm_library(LLVMGlobalISel
         CallLowering.cpp
         GlobalISel.cpp
         Combiner.cpp
         CombinerHelper.cpp
+        Canonicalize.cpp
         IRTranslator.cpp
         InstructionSelect.cpp
         InstructionSelector.cpp
         LegalityPredicates.cpp
         LegalizeMutations.cpp
         Legalizer.cpp
         LegalizerHelper.cpp
         LegalizerInfo.cpp

lib/CodeGen/GlobalISel/Canonicalize.cpp

+//===--- GISelCanonicalize.cpp - Canonicalize IR before GlobalISel codegen-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass does some canonicalization of the IR into standard forms to make
+// GlobalISel codegen more effective. This runs at all optimization levels,
+// although some canonicalization may be done already when optimizations are
+// enabled.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/GlobalISel/Canonicalize.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/Pass.h"
+
+#define DEBUG_TYPE "gisel-canonicalize"
+
+using namespace llvm;
+
+namespace {
+
+bool visitICmp(ICmpInst &I) {
+  if (isa<Constant>(I.getOperand(0)) && !isa<Constant>(I.getOperand(1))) {
+    LLVM_DEBUG(dbgs() << "GISelCanonicalize: swapping operands of " << I
+                      << "\n");
+    I.swapOperands();
+    return true;
+  }
+  return false;
+}
+
+bool canonicalizeFunction(Function &F) {
+  bool Changed = false;
+  for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
+    Instruction *I = &*II;
+    switch (I->getOpcode()) {
+    case Instruction::ICmp:
+      Changed |= visitICmp(*cast<ICmpInst>(I));
+      break;
+    default:
+      continue;
+    }
+  }
+  return Changed;
+}
+
+class GISelCanonicalize : public FunctionPass {
+public:
+  static char ID;
+  GISelCanonicalize() : FunctionPass(ID) {
+    initializeGISelCanonicalizePass(*PassRegistry::getPassRegistry());
+  }
+
+  bool runOnFunction(Function &F) override {
+    return canonicalizeFunction(F);
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesCFG();
+  }
+};
+}
+
+char GISelCanonicalize::ID;
+INITIALIZE_PASS_BEGIN(GISelCanonicalize, "gisel-canonicalize",
+                      "GISel canonicalization", false, false)
+INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
+INITIALIZE_PASS_END(GISelCanonicalize, "gisel-canonicalize",
+                    "GISel canonicalization", false, false)
+
+FunctionPass *llvm::createGISelCanonicalizePass() {
+  return new GISelCanonicalize();
+}
+
+PreservedAnalyses GISelCanonicalizePass::run(Function &F,
+                                             FunctionAnalysisManager &AM) {
+  if (!canonicalizeFunction(F))
+    return PreservedAnalyses::all();
+  PreservedAnalyses PA;
+  PA.preserveSet<CFGAnalyses>();
+  return PA;
+}

lib/CodeGen/TargetPassConfig.cpp

 /// Add pass to prepare the LLVM IR for code generation. This should be done
 /// before exception handling preparation passes.
 void TargetPassConfig::addCodeGenPrepare() {
   if (getOptLevel() != CodeGenOpt::None && !DisableCGP)
     addPass(createCodeGenPreparePass());
   addPass(createRewriteSymbolsPass());
 }
 
+static bool shouldEnableGlobalISelPasses(TargetMachine *TM) {
+  return EnableGlobalISelOption == cl::BOU_TRUE ||
+         (EnableGlobalISelOption == cl::BOU_UNSET &&
+          TM->Options.EnableGlobalISel && EnableFastISelOption != cl::BOU_TRUE);
+}
+
 /// Add common passes that perform LLVM IR to IR transforms in preparation for
 /// instruction selection.
 void TargetPassConfig::addISelPrepare() {
   addPreISel();
 
   // Force codegen to run according to the callgraph.
   if (requiresCodeGenSCCOrder())
     addPass(new DummyCGSCCPass);
 
+  // Do some IR canonicalizations for GlobalISel at all opt levels.
+  if (shouldEnableGlobalISelPasses(TM) && TM->shouldCanonicalizeGISel())
+    addPass(createGISelCanonicalizePass());
+
   // Add both the safe stack and the stack protection passes: each of them will
   // only protect functions that have corresponding attributes.
   addPass(createSafeStackPass());
   addPass(createStackProtectorPass());
 
   if (PrintISelInput)
     addPass(createPrintFunctionPass(
         dbgs(), "\n\n*** Final LLVM Code input to ISel ***\n"));
bool TargetPassConfig::addCoreISelPasses() {
   TM->setO0WantsFastISel(EnableFastISelOption != cl::BOU_FALSE);
   if (EnableFastISelOption == cl::BOU_TRUE ||
       (TM->getOptLevel() == CodeGenOpt::None && TM->getO0WantsFastISel()))
     TM->setFastISel(true);
 
   // Ask the target for an instruction selector.
   // Explicitly enabling fast-isel should override implicitly enabled
   // global-isel.
-  if (EnableGlobalISelOption == cl::BOU_TRUE ||
-      (EnableGlobalISelOption == cl::BOU_UNSET &&
-       TM->Options.EnableGlobalISel && EnableFastISelOption != cl::BOU_TRUE)) {
+  if (shouldEnableGlobalISelPasses(TM)) {
     TM->setFastISel(false);
 
     if (addIRTranslator())
       return true;
 
     addPreLegalizeMachineIR();
 
     if (addLegalizeMachineIR())
       return true;
 
     // Before running the register bank selector, ask the target if it

test/CodeGen/AArch64/O0-pipeline.ll

 ; CHECK-NEXT:       Remove unreachable blocks from the CFG
 ; CHECK-NEXT:       Instrument function entry/exit with calls to e.g. mcount() (post inlining)
 ; CHECK-NEXT:       Scalarize Masked Memory Intrinsics
 ; CHECK-NEXT:       Expand reduction intrinsics
 ; CHECK-NEXT:     Rewrite Symbols
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Exception handling preparation
+; CHECK-NEXT:       GISel canonicalization
 ; CHECK-NEXT:       Safe Stack instrumentation pass
 ; CHECK-NEXT:       Insert stack protectors
 ; CHECK-NEXT:       Module Verifier
 ; CHECK-NEXT:       IRTranslator
 ; CHECK-NEXT:       Legalizer
 ; CHECK-NEXT:       RegBankSelect
 ; CHECK-NEXT:       Localizer
 ; CHECK-NEXT:       InstructionSelect

test/CodeGen/Generic/gisel-canonicalize.ll

+; RUN: opt %s -gisel-canonicalize -S | FileCheck %s
+
+; CHECK-PREFIX: icmp_test
+; CHECK: %c = icmp sgt i64 %a, 42
+; CHECK: ret
+define i1 @icmp_test(i64 %a) {
+  %c = icmp slt i64 42, %a
+  ret i1 %c
+}

tools/llc/llc.cpp

int main(int argc, char **argv) {
   initializeEntryExitInstrumenterPass(*Registry);
   initializePostInlineEntryExitInstrumenterPass(*Registry);
   initializeUnreachableBlockElimLegacyPassPass(*Registry);
   initializeConstantHoistingLegacyPassPass(*Registry);
   initializeScalarOpts(*Registry);
   initializeVectorization(*Registry);
   initializeScalarizeMaskedMemIntrinPass(*Registry);
   initializeExpandReductionsPass(*Registry);
+  initializeGISelCanonicalizePass(*Registry);
 
   // Initialize debugging passes.
   initializeScavengerTestPass(*Registry);
 
   // Register the target printer for --version.
   cl::AddExtraVersionPrinter(TargetRegistry::printRegisteredTargetsForVersion);
 
   cl::ParseCommandLineOptions(argc, argv, "llvm system compiler\n");

tools/opt/opt.cpp

int main(int argc, char **argv) {
   initializeIndirectBrExpandPassPass(Registry);
   initializeInterleavedAccessPass(Registry);
   initializeEntryExitInstrumenterPass(Registry);
   initializePostInlineEntryExitInstrumenterPass(Registry);
   initializeUnreachableBlockElimLegacyPassPass(Registry);
   initializeExpandReductionsPass(Registry);
   initializeWasmEHPreparePass(Registry);
   initializeWriteBitcodePassPass(Registry);
+  initializeGISelCanonicalizePass(Registry);
 
 #ifdef LINK_POLLY_INTO_TOOLS
   polly::initializePollyPasses(Registry);
 #endif
 
   cl::ParseCommandLineOptions(argc, argv,
     "llvm .bc -> .bc modular optimizer and analysis printer\n");