[IPRA] Interprocedural Register Allocation - Transformation Pass

[vivekvpandya]

Summary

This commit adds required transformation pass for IPRA and a simple testcase to verify it.

  1) lib/Target/X86/X86RegUsageInfoPropagate.cpp (Target Specific MachineFunction Pass) to update RegMasks of call instr in caller function based on the RegMask returned by immutable pass, scheduled at Pre-RegAlloc.

[mcrosier]

Two very basic questions:
1.) Do we plan on supporting IPRA on other targets? My assumption is yes (please).
2.) Can the RegUsageInfoPropagate pass be written in a target-independent way and add target specific hooks as necessary?

[mehdi_amini]

I don't know why the pass is still X86 specific, I thought our conclusion before splitting the patch was that it is not and should be a generic pass?

The only reason it is X86 was that we thought we would have to handle calls in a target specific way, but it turned out we should be able to get away with that.

[vivekvpandya]

This commit makes IPRA transformation a target independent pass.

[mehdi_amini]

test/CodeGen/Generic/ipra-transform.ll

15

trailing whitespace

[mehdi_amini]

lib/CodeGen/RegUsageInfoPropagate.cpp

110

Take a Function * as argument here, and adapt call sites.

123

no braces

test/CodeGen/Generic/ipra-transform.ll

12

Add some comment in the test describing what you're checking in both cases.

[vivekvpandya]

Simple comment added in test case.

[mcrosier]

lib/CodeGen/RegUsageInfoPropagate.cpp

2

This doesn't appear to be 80-column.

14

MachineInstrs in a given

15

RegisterUsageInfo.cpp -> RegisterUsageInfo

16

of the callee

Perhaps something like:
if the RegMask information is available then this pass will update the RegMask of the call instruction.

18

used by the register allocator while allocating the current MachineFunction.

43

I've seen this style in the past:

#define RUIP_NAME "Register Usage Information Propagation"

and then replace the strings with the #define.

54

return  RUIP_NAME;

76

"Register Usage Information Propagation" -> RUIP_NAME

79

"Register Usage Information Propagation" -> RUIP_NAME

103

I'm not sure this comment is necessary, but I don't have any strong feelings for or against it. However, if you do decide to keep it, please write all comments using proper English prose (capitalization, puncuation, etc.).

http://llvm.org/docs/CodingStandards.html#commenting

104

You can reduce the indent by changing this check to:

if (!MI.isCall())
  continue;

I tend to think it also improves readability.

[mcrosier]

lib/CodeGen/RegUsageInfoPropagate.cpp

75

The second argument to INITIALIZE_PASS_BEGIN/END is used to specify the name of the command-line option passed to llc/opt to enable this pass. Generally, this is all lower case with dashes are used for spacing (e.g., "peephole-opt", "machine-sink", "if-converter"). We should decide upon a name that uses this convention (e.g., "reg-usage-propagation").

[vivekvpandya]

changes as suggested by @mcrosier.

[mehdi_amini]

lib/CodeGen/RegUsageInfoPropagate.cpp

119

No: Operand.getGlobal() already returns the Function *....
(you'll need a cast)

[mehdi_amini]

lib/CodeGen/RegUsageInfoPropagate.cpp

110

if (!RegMask)
  return;

119

No unsafe C-like cast, use the llvm style of casting please: cast<Function>

[mehdi_amini]

LGTM.

include/llvm/CodeGen/Passes.h

/// MachineDominanaceFrontier - This pass is a machine dominators analysis pass.
   /// This pass detects subregister lanes in a virtual register that are used
   /// independently of other lanes and splits them into separate virtual
   /// registers.
   extern char &RenameIndependentSubregsID;
 
   /// This pass is executed POST-RA to collect which physical registers are
   /// preserved by given machine function.
   FunctionPass *createRegUsageInfoCollector();
+
+  /// Return a MachineFunction pass that identifies call sites
+  /// and propagates register usage information of callee to caller
+  /// if available with PysicalRegisterUsageInfo pass.
+  FunctionPass *createRegUsageInfoPropPass();
 } // End llvm namespace
 
 /// Target machine pass initializer for passes with dependencies. Use with
 /// INITIALIZE_TM_PASS_END.
 #define INITIALIZE_TM_PASS_BEGIN INITIALIZE_PASS_BEGIN
 
 /// Target machine pass initializer for passes with dependencies. Use with
 /// INITIALIZE_TM_PASS_BEGIN.

lib/CodeGen/CMakeLists.txt

add_llvm_library(LLVMCodeGen
   RegAllocPBQP.cpp
   RegisterClassInfo.cpp
   RegisterCoalescer.cpp
   RegisterPressure.cpp
   RegisterScavenging.cpp
   RenameIndependentSubregs.cpp
   RegisterUsageInfo.cpp
   RegUsageInfoCollector.cpp
+  RegUsageInfoPropagate.cpp
   SafeStack.cpp
   ScheduleDAG.cpp
   ScheduleDAGInstrs.cpp
   ScheduleDAGPrinter.cpp
   ScoreboardHazardRecognizer.cpp
   ShadowStackGCLowering.cpp
   ShrinkWrap.cpp
   SjLjEHPrepare.cpp

lib/CodeGen/RegUsageInfoPropagate.cpp

+//=--- RegUsageInfoPropagate.cpp - Register Usage Informartion Propagation --=//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// This pass is required to take advantage of the interprocedural register
+/// allocation infrastructure.
+///
+/// This pass iterates through MachineInstrs in a given MachineFunction and at
+/// each callsite queries RegisterUsageInfo for RegMask (calculated based on
+/// actual register allocation) of the callee function, if the RegMask detail
+/// is available then this pass will update the RegMask of the call instruction.
+/// This updated RegMask will be used by the register allocator while allocating
+/// the current MachineFunction.
+///
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/RegisterUsageInfo.h"
+#include "llvm/IR/Module.h"
+#include "llvm/PassAnalysisSupport.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Target/TargetMachine.h"
+#include <map>
+#include <string>
+
+namespace llvm {
+void initializeRegUsageInfoPropagationPassPass(PassRegistry &);
+}
+
+using namespace llvm;
+
+#define DEBUG_TYPE "ip-regalloc"
+
+#define RUIP_NAME "Register Usage Information Propagation"
+
+namespace {
+class RegUsageInfoPropagationPass : public MachineFunctionPass {
+
+public:
+  RegUsageInfoPropagationPass() : MachineFunctionPass(ID) {
+    PassRegistry &Registry = *PassRegistry::getPassRegistry();
+    initializeRegUsageInfoPropagationPassPass(Registry);
+  }
+
+  const char *getPassName() const override { return RUIP_NAME; }
+
+  bool runOnMachineFunction(MachineFunction &MF) override;
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+
+  static char ID;
+
+private:
+  static void setRegMask(MachineInstr &MI, const uint32_t *RegMask) {
+    for (MachineOperand &MO : MI.operands()) {
+      if (MO.isRegMask())
+        MO.setRegMask(RegMask);
+    }
+  }
+};
+} // end of anonymous namespace
+char RegUsageInfoPropagationPass::ID = 0;
+
+INITIALIZE_PASS_BEGIN(RegUsageInfoPropagationPass, "reg-usage-propagation",
+                      RUIP_NAME, false, false)
+INITIALIZE_PASS_DEPENDENCY(PhysicalRegisterUsageInfo)
+INITIALIZE_PASS_END(RegUsageInfoPropagationPass, "reg-usage-propagation",
+                    RUIP_NAME, false, false)
+
+FunctionPass *llvm::createRegUsageInfoPropPass() {
+  return new RegUsageInfoPropagationPass();
+}
+
+void RegUsageInfoPropagationPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequired<PhysicalRegisterUsageInfo>();
+  AU.setPreservesAll();
+  MachineFunctionPass::getAnalysisUsage(AU);
+}
+
+bool RegUsageInfoPropagationPass::runOnMachineFunction(MachineFunction &MF) {
+  const Module *M = MF.getFunction()->getParent();
+  PhysicalRegisterUsageInfo *PRUI = &getAnalysis<PhysicalRegisterUsageInfo>();
+
+  DEBUG(dbgs() << " ++++++++++++++++++++ " << getPassName()
+               << " ++++++++++++++++++++  \n");
+  DEBUG(dbgs() << "MachineFunction : " << MF.getName() << "\n");
+
+  bool Changed = false;
+
+  for (MachineBasicBlock &MBB : MF) {
+    for (MachineInstr &MI : MBB) {
+      if (!MI.isCall())
+        continue;
+      DEBUG(dbgs()
+            << "Call Instruction Before Register Usage Info Propagation : \n");
+      DEBUG(dbgs() << MI << "\n");
+
+      auto UpdateRegMask = [&](Function *F) {
+        const auto *RegMask = PRUI->getRegUsageInfo(F);
+        if (RegMask) { // else skip optimization
+          setRegMask(MI, &(*RegMask)[0]);
+          Changed = true;
+        }
+      };
+
+      MachineOperand &Operand = MI.getOperand(0);
+      if (Operand.isGlobal())
+        UpdateRegMask((Function *)Operand.getGlobal());
+      else if (Operand.isSymbol())
+        UpdateRegMask(M->getFunction(Operand.getSymbolName()));
+
+      DEBUG(dbgs()
+            << "Call Instruction After Register Usage Info Propagation : \n");
+      DEBUG(dbgs() << MI << "\n");
+    }
+  }
+
+  DEBUG(dbgs() << " +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++"
+                  "++++++ \n");
+  return Changed;
+}

lib/CodeGen/TargetPassConfig.cpp

 /// tied to a common pass. But if it has subtle dependencies on multiple passes,
 /// the target should override the stage instead.
 ///
 /// TODO: We could use a single addPre/Post(ID) hook to allow pass injection
 /// before/after any target-independent pass. But it's currently overkill.
 void TargetPassConfig::addMachinePasses() {
   AddingMachinePasses = true;
 
+  if (UseIPRA)
+    addPass(createRegUsageInfoPropPass());
+
   // Insert a machine instr printer pass after the specified pass.
   if (!StringRef(PrintMachineInstrs.getValue()).equals("") &&
       !StringRef(PrintMachineInstrs.getValue()).equals("option-unspecified")) {
     const PassRegistry *PR = PassRegistry::getPassRegistry();
     const PassInfo *TPI = PR->getPassInfo(PrintMachineInstrs.getValue());
     const PassInfo *IPI = PR->getPassInfo(StringRef("machineinstr-printer"));
     assert (TPI && IPI && "Pass ID not registered!");
     const char *TID = (const char *)(TPI->getTypeInfo());

test/CodeGen/Generic/ipra-transform.ll

+
+; RUN: llc < %s | FileCheck %s -check-prefix=NOIPRA
+; RUN: llc -enable-ipra < %s | FileCheck %s
+
+
+target triple = "x86_64-unknown-unknown"
+define void @bar1() {
+  ret void
+}
+define preserve_allcc void @foo()#0 {
+; Due to preserve_allcc foo() will save some registers at start of foo()
+; prefix NOIPRA will verify that.
+; NOIPRA-LABEL: foo:
+; NOIPRA: pushq %r10
+; NOIPRA-NEXT: pushq %r9
+; NOIPRA-NEXT: pushq %r8
+; NOIPRA: callq bar1
+; When IPRA is present above registers will not be saved and that is verified
+; by prefix CHECK.
+; CHECK: foo:
+; CHECK-NOT: pushq %r10
+; CHECK-NOT: pushq %r9
+; CHECK-NOT: pushq %r8
+; CHECK: callq bar1
+  call void @bar1()
+  call void @bar2()
+  ret void
+}
+define void @bar2() {
+  ret void
+}
+attributes #0 = {nounwind}