Home | History | Annotate | Line # | Download | only in lib 
      1 //===-- RegisterAliasingTracker.h -------------------------------*- C++ -*-===//
      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 /// \file
     10 /// Defines classes to keep track of register aliasing.
     11 ///
     12 //===----------------------------------------------------------------------===//
     13 
     14 #ifndef LLVM_TOOLS_LLVM_EXEGESIS_ALIASINGTRACKER_H
     15 #define LLVM_TOOLS_LLVM_EXEGESIS_ALIASINGTRACKER_H
     16 
     17 #include <memory>
     18 #include <unordered_map>
     19 
     20 #include "llvm/ADT/BitVector.h"
     21 #include "llvm/ADT/PackedVector.h"
     22 #include "llvm/MC/MCRegisterInfo.h"
     23 
     24 namespace llvm {
     25 namespace exegesis {
     26 
     27 // Returns the registers that are aliased by the ones set in SourceBits.
     28 BitVector getAliasedBits(const MCRegisterInfo &RegInfo,
     29                          const BitVector &SourceBits);
     30 
     31 // Keeps track of a mapping from one register (or a register class) to its
     32 // aliased registers.
     33 //
     34 // e.g.
     35 // RegisterAliasingTracker Tracker(RegInfo, X86::EAX);
     36 // Tracker.sourceBits() == { X86::EAX }
     37 // Tracker.aliasedBits() == { X86::AL, X86::AH, X86::AX,
     38 //                            X86::EAX,X86::HAX, X86::RAX }
     39 // Tracker.getOrigin(X86::AL) == X86::EAX;
     40 // Tracker.getOrigin(X86::BX) == -1;
     41 struct RegisterAliasingTracker {
     42   // Construct a tracker from an MCRegisterClass.
     43   RegisterAliasingTracker(const MCRegisterInfo &RegInfo,
     44                           const BitVector &ReservedReg,
     45                           const MCRegisterClass &RegClass);
     46 
     47   // Construct a tracker from an MCPhysReg.
     48   RegisterAliasingTracker(const MCRegisterInfo &RegInfo,
     49                           const MCPhysReg Register);
     50 
     51   const BitVector &sourceBits() const { return SourceBits; }
     52 
     53   // Retrieves all the touched registers as a BitVector.
     54   const BitVector &aliasedBits() const { return AliasedBits; }
     55 
     56   // Returns the origin of this register or -1.
     57   int getOrigin(MCPhysReg Aliased) const {
     58     if (!AliasedBits[Aliased])
     59       return -1;
     60     return Origins[Aliased];
     61   }
     62 
     63 private:
     64   RegisterAliasingTracker(const MCRegisterInfo &RegInfo);
     65   RegisterAliasingTracker(const RegisterAliasingTracker &) = delete;
     66 
     67   void FillOriginAndAliasedBits(const MCRegisterInfo &RegInfo,
     68                                 const BitVector &OriginalBits);
     69 
     70   BitVector SourceBits;
     71   BitVector AliasedBits;
     72   PackedVector<size_t, 10> Origins; // Max 1024 physical registers.
     73 };
     74 
     75 // A cache of existing trackers.
     76 struct RegisterAliasingTrackerCache {
     77   // RegInfo must outlive the cache.
     78   RegisterAliasingTrackerCache(const MCRegisterInfo &RegInfo,
     79                                const BitVector &ReservedReg);
     80 
     81   // Convenient function to retrieve a BitVector of the right size.
     82   const BitVector &emptyRegisters() const { return EmptyRegisters; }
     83 
     84   // Convenient function to retrieve the registers the function body can't use.
     85   const BitVector &reservedRegisters() const { return ReservedReg; }
     86 
     87   // Convenient function to retrieve the underlying MCRegInfo.
     88   const MCRegisterInfo &regInfo() const { return RegInfo; }
     89 
     90   // Retrieves the RegisterAliasingTracker for this particular register.
     91   const RegisterAliasingTracker &getRegister(MCPhysReg Reg) const;
     92 
     93   // Retrieves the RegisterAliasingTracker for this particular register class.
     94   const RegisterAliasingTracker &getRegisterClass(unsigned RegClassIndex) const;
     95 
     96 private:
     97   const MCRegisterInfo &RegInfo;
     98   const BitVector ReservedReg;
     99   const BitVector EmptyRegisters;
    100   mutable std::unordered_map<unsigned, std::unique_ptr<RegisterAliasingTracker>>
    101       Registers;
    102   mutable std::unordered_map<unsigned, std::unique_ptr<RegisterAliasingTracker>>
    103       RegisterClasses;
    104 };
    105 
    106 // `a = a & ~b`, optimized for few bit sets in B and no allocation.
    107 inline void remove(BitVector &A, const BitVector &B) {
    108   assert(A.size() == B.size());
    109   for (auto I : B.set_bits())
    110     A.reset(I);
    111 }
    112 
    113 // Returns a debug string for the list of registers.
    114 std::string debugString(const MCRegisterInfo &RegInfo, const BitVector &Regs);
    115 
    116 } // namespace exegesis
    117 } // namespace llvm
    118 
    119 #endif // LLVM_TOOLS_LLVM_EXEGESIS_ALIASINGTRACKER_H
    120