lib/CodeGen/MIRVRegNamerUtils.h

   1 //===------------ MIRVRegNamerUtils.h - MIR VReg Renaming Utilities -------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // The purpose of these utilities is to abstract out parts of the MIRCanon pass
  10 // that are responsible for renaming virtual registers with the purpose of
  11 // sharing code with a MIRVRegNamer pass that could be the analog of the
  12 // opt -instnamer pass.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/ADT/PostOrderIterator.h"
  17 #include "llvm/ADT/STLExtras.h"
  18 #include "llvm/CodeGen/MachineFunctionPass.h"
  19 #include "llvm/CodeGen/MachineInstrBuilder.h"
  20 #include "llvm/CodeGen/MachineRegisterInfo.h"
  21 #include "llvm/CodeGen/Passes.h"
  22 #include "llvm/Support/raw_ostream.h"
  23
  24 #include <queue>
  25
  26 using namespace llvm;
  27
  28 /// NamedVRegCursor - The cursor is an object that keeps track of what the next
  29 /// vreg name should be. It does book keeping to determine when to skip the
  30 /// index value and by how much, or if the next vreg name should be an increment
  31 /// from the previous.
  32 class NamedVRegCursor {
  33   MachineRegisterInfo &MRI;
  34
  35   /// virtualVRegNumber - Book keeping of the last vreg position.
  36   unsigned virtualVRegNumber;
  37
  38   /// SkipGapSize - Used to calculate a modulo amount to skip by after every
  39   /// sequence of instructions starting from a given side-effecting
  40   /// MachineInstruction for a given MachineBasicBlock. The general idea is that
  41   /// for a given program compiled with two different opt pipelines, there
  42   /// shouldn't be greater than SkipGapSize difference in how many vregs are in
  43   /// play between the two and for every def-use graph of vregs we rename we
  44   /// will round up to the next SkipGapSize'th number so that we have a high
  45   /// change of landing on the same name for two given matching side-effects
  46   /// for the two compilation outcomes.
  47   const unsigned SkipGapSize;
  48
  49   /// RenamedInOtherBB - VRegs that we already renamed: ie breadcrumbs.
  50   std::vector<Register> RenamedInOtherBB;
  51
  52 public:
  53   NamedVRegCursor() = delete;
  54   /// 1000 for the SkipGapSize was a good heuristic at the time of the writing
  55   /// of the MIRCanonicalizerPass. Adjust as needed.
  56   NamedVRegCursor(MachineRegisterInfo &MRI, unsigned SkipGapSize = 1000)
  57       : MRI(MRI), virtualVRegNumber(0), SkipGapSize(SkipGapSize) {}
  58
  59   /// SkipGapSize - Skips modulo a gap value of indices. Indices are used to
  60   /// produce the next vreg name.
  61   void skipVRegs();
  62
  63   unsigned getVirtualVReg() const { return virtualVRegNumber; }
  64
  65   /// incrementVirtualVReg - This increments an index value that us used to
  66   /// create a new vreg name. This is not a Register.
  67   unsigned incrementVirtualVReg(unsigned incr = 1) {
  68     virtualVRegNumber += incr;
  69     return virtualVRegNumber;
  70   }
  71
  72   /// createVirtualRegister - Given an existing vreg, create a named vreg to
  73   /// take its place.
  74   unsigned createVirtualRegister(unsigned VReg);
  75
  76   /// renameVRegs - For a given MachineBasicBlock, scan for side-effecting
  77   /// instructions, walk the def-use from each side-effecting root (in sorted
  78   /// root order) and rename the encountered vregs in the def-use graph in a
  79   /// canonical ordering. This method maintains book keeping for which vregs
  80   /// were already renamed in RenamedInOtherBB.
  81   // @return changed
  82   bool renameVRegs(MachineBasicBlock *MBB);
  83 };