[MIPS GlobalISel] RegBankSelect for chains of ambiguous instructions

When one of the uses/defs of ambiguous instruction is also ambiguous
visit it recursively and search its uses/defs for instruction with
only one mapping available.
When all instruction in a chain are ambiguous arbitrary mapping can
be selected. For s64 operands in ambiguous chain fprb is selected since
it results in less instructions then having to narrow scalar s64 to s32.
For s32 both gprb and fprb result in same number of instructions and
gprb is selected like a general purpose option.

At the moment we always avoid cross register bank copies.
TODO: Implement a model for costs calculations of different mappings
on same instruction and cross bank copies. Allow cross bank copies
when appropriate according to cost model.

Differential Revision: https://reviews.llvm.org/D64485

llvm-svn: 365743

2 files changed, 77 insertions, 14 deletions

diff --git a/llvm/lib/Target/Mips/MipsRegisterBankInfo.cpp b/llvm/lib/Target/Mips/MipsRegisterBankInfo.cpp
index 7f570207f59..63cb66416f3 100644
--- a/llvm/lib/Target/Mips/MipsRegisterBankInfo.cpp
+++ b/llvm/lib/Target/Mips/MipsRegisterBankInfo.cpp
@@ -210,8 +210,11 @@ MipsRegisterBankInfo::AmbiguousRegDefUseContainer::AmbiguousRegDefUseContainer(
   }
 }
 
-bool MipsRegisterBankInfo::TypeInfoForMF::visit(const MachineInstr *MI) {
+bool MipsRegisterBankInfo::TypeInfoForMF::visit(
+    const MachineInstr *MI, const MachineInstr *WaitingForTypeOfMI) {
   assert(isAmbiguous(MI->getOpcode()) && "Visiting non-Ambiguous opcode.\n");
+  if (wasVisited(MI))
+    return true; // InstType has already been determined for MI.
 
   startVisit(MI);
   AmbiguousRegDefUseContainer DefUseContainer(MI);
@@ -224,6 +227,21 @@ bool MipsRegisterBankInfo::TypeInfoForMF::visit(const MachineInstr *MI) {
   if (visitAdjacentInstrs(MI, DefUseContainer.getUseDefs(), false))
     return true;
 
+  // All MI's adjacent instructions, are ambiguous.
+  if (!WaitingForTypeOfMI) {
+    // This is chain of ambiguous instructions.
+    setTypes(MI, InstType::Ambiguous);
+    return true;
+  }
+  // Excluding WaitingForTypeOfMI, MI is either connected to chains of ambiguous
+  // instructions or has no other adjacent instructions. Anyway InstType could
+  // not be determined. There could be unexplored path from some of
+  // WaitingForTypeOfMI's adjacent instructions to an instruction with only one
+  // mapping available.
+  // We are done with this branch, add MI to WaitingForTypeOfMI's WaitingQueue,
+  // this way when WaitingForTypeOfMI figures out its InstType same InstType
+  // will be assigned to all instructions in this branch.
+  addToWaitingQueue(WaitingForTypeOfMI, MI);
   return false;
 }
 
@@ -246,15 +264,23 @@ bool MipsRegisterBankInfo::TypeInfoForMF::visitAdjacentInstrs(
       return true;
     }
 
-    if (isAmbiguous(AdjMI->getOpcode())) {
-      // Chains of ambiguous instructions are not supported.
-      return false;
-    }
-
     // Defaults to integer instruction. Includes G_MERGE_VALUES and
     // G_UNMERGE_VALUES.
-    setTypes(MI, InstType::Integer);
-    return true;
+    if (!isAmbiguous(AdjMI->getOpcode())) {
+      setTypes(MI, InstType::Integer);
+      return true;
+    }
+
+    // When AdjMI was visited first, MI has to continue to explore remaining
+    // adjacent instructions and determine InstType without visiting AdjMI.
+    if (!wasVisited(AdjMI) ||
+        getRecordedTypeForInstr(AdjMI) != InstType::NotDetermined) {
+      if (visit(AdjMI, MI)) {
+        // InstType is successfully determined and is same as for AdjMI.
+        setTypes(MI, getRecordedTypeForInstr(AdjMI));
+        return true;
+      }
+    }
   }
   return false;
 }
@@ -262,6 +288,9 @@ bool MipsRegisterBankInfo::TypeInfoForMF::visitAdjacentInstrs(
 void MipsRegisterBankInfo::TypeInfoForMF::setTypes(const MachineInstr *MI,
                                                    InstType InstTy) {
   changeRecordedTypeForInstr(MI, InstTy);
+  for (const MachineInstr *WaitingInstr : getWaitingQueueFor(MI)) {
+    setTypes(WaitingInstr, InstTy);
+  }
 }
 
 void MipsRegisterBankInfo::TypeInfoForMF::setTypesAccordingToPhysicalRegister(
@@ -288,7 +317,7 @@ void MipsRegisterBankInfo::TypeInfoForMF::setTypesAccordingToPhysicalRegister(
 
 MipsRegisterBankInfo::InstType
 MipsRegisterBankInfo::TypeInfoForMF::determineInstType(const MachineInstr *MI) {
-  visit(MI);
+  visit(MI, nullptr);
   return getRecordedTypeForInstr(MI);
 }
 
@@ -296,6 +325,7 @@ void MipsRegisterBankInfo::TypeInfoForMF::cleanupIfNewFunction(
     llvm::StringRef FunctionName) {
   if (MFName != FunctionName) {
     MFName = FunctionName;
+    WaitingQueues.clear();
     Types.clear();
   }
 }
@@ -354,7 +384,8 @@ MipsRegisterBankInfo::getInstrMapping(const MachineInstr &MI) const {
       InstTy = TI.determineInstType(&MI);
     }
 
-    if (InstTy == InstType::FloatingPoint) { // fprb
+    if (InstTy == InstType::FloatingPoint ||
+        (Size == 64 && InstTy == InstType::Ambiguous)) { // fprb
       OperandsMapping =
           getOperandsMapping({Size == 32 ? &Mips::ValueMappings[Mips::SPRIdx]
                                          : &Mips::ValueMappings[Mips::DPRIdx],
@@ -378,7 +409,8 @@ MipsRegisterBankInfo::getInstrMapping(const MachineInstr &MI) const {
       InstTy = TI.determineInstType(&MI);
     }
 
-    if (InstTy == InstType::FloatingPoint) { // fprb
+    if (InstTy == InstType::FloatingPoint ||
+        (Size == 64 && InstTy == InstType::Ambiguous)) { // fprb
       OperandsMapping =
           getOperandsMapping({Size == 32 ? &Mips::ValueMappings[Mips::SPRIdx]
                                          : &Mips::ValueMappings[Mips::DPRIdx],
@@ -421,7 +453,8 @@ MipsRegisterBankInfo::getInstrMapping(const MachineInstr &MI) const {
       InstTy = TI.determineInstType(&MI);
     }
 
-    if (InstTy == InstType::FloatingPoint) { // fprb
+    if (InstTy == InstType::FloatingPoint ||
+        (Size == 64 && InstTy == InstType::Ambiguous)) { // fprb
       const RegisterBankInfo::ValueMapping *Bank =
           Size == 32 ? &Mips::ValueMappings[Mips::SPRIdx]
                      : &Mips::ValueMappings[Mips::DPRIdx];
diff --git a/llvm/lib/Target/Mips/MipsRegisterBankInfo.h b/llvm/lib/Target/Mips/MipsRegisterBankInfo.h
index 456797e1db0..704d40a6b10 100644
--- a/llvm/lib/Target/Mips/MipsRegisterBankInfo.h
+++ b/llvm/lib/Target/Mips/MipsRegisterBankInfo.h
@@ -45,13 +45,19 @@ private:
   /// We assign InstType to such instructions as it helps us to avoid cross bank
   /// copies. InstType deppends on context.
   enum InstType {
+    /// Temporary type, when visit(..., nullptr) finishes will convert to one of
+    /// the remaining types: Integer, FloatingPoint or Ambiguous.
     NotDetermined,
     /// Connected with instruction that interprets 'bags of bits' as integers.
     /// Select gprb to avoid cross bank copies.
     Integer,
     /// Connected with instruction that interprets 'bags of bits' as floating
     /// point numbers. Select fprb to avoid cross bank copies.
-    FloatingPoint
+    FloatingPoint,
+    /// Represents moving 'bags of bits' around. Select same bank for entire
+    /// chain to avoid cross bank copies. Currently we select fprb for s64 and
+    /// gprb for s32 Ambiguous operands.
+    Ambiguous
   };
 
   /// Some generic instructions have operands that can be mapped to either fprb
@@ -76,16 +82,23 @@ private:
   class TypeInfoForMF {
     /// MachineFunction name is used to recognise when MF changes.
     std::string MFName = "";
+    /// <key, value> : value is vector of all MachineInstrs that are waiting for
+    /// key to figure out type of some of its ambiguous operands.
+    DenseMap<const MachineInstr *, SmallVector<const MachineInstr *, 2>>
+        WaitingQueues;
     /// Recorded InstTypes for visited instructions.
     DenseMap<const MachineInstr *, InstType> Types;
 
-    bool visit(const MachineInstr *MI);
+    /// Recursively visit MI's adjacent instructions and find MI's InstType.
+    bool visit(const MachineInstr *MI, const MachineInstr *WaitingForTypeOfMI);
 
     /// Visit MI's adjacent UseDefs or DefUses.
     bool visitAdjacentInstrs(const MachineInstr *MI,
                              SmallVectorImpl<MachineInstr *> &AdjacentInstrs,
                              bool isDefUse);
 
+    /// Set type for MI, and recursively for all instructions that are
+    /// waiting for MI's type.
     void setTypes(const MachineInstr *MI, InstType ITy);
 
     /// InstType for MI is determined, set it to InstType that corresponds to
@@ -97,8 +110,11 @@ private:
     /// Set default values for MI in order to start visit.
     void startVisit(const MachineInstr *MI) {
       Types.try_emplace(MI, InstType::NotDetermined);
+      WaitingQueues.try_emplace(MI);
     }
 
+    /// Returns true if instruction was already visited. Type might not be
+    /// determined at this point but will be when visit(..., nullptr) finishes.
     bool wasVisited(const MachineInstr *MI) const { return Types.count(MI); };
 
     /// Returns recorded type for instruction.
@@ -113,6 +129,20 @@ private:
       Types.find(MI)->getSecond() = InstTy;
     };
 
+    /// Returns WaitingQueue for instruction.
+    const SmallVectorImpl<const MachineInstr *> &
+    getWaitingQueueFor(const MachineInstr *MI) const {
+      assert(WaitingQueues.count(MI) && "Instruction was not visited!");
+      return WaitingQueues.find(MI)->getSecond();
+    };
+
+    /// Add WaitingForMI to MI's WaitingQueue.
+    void addToWaitingQueue(const MachineInstr *MI,
+                           const MachineInstr *WaitingForMI) {
+      assert(WaitingQueues.count(MI) && "Instruction was not visited!");
+      WaitingQueues.find(MI)->getSecond().push_back(WaitingForMI);
+    };
+
   public:
     InstType determineInstType(const MachineInstr *MI);