contrib/llvm/include/llvm/CodeGen/ExecutionDomainFix.h

   1 //==-- llvm/CodeGen/ExecutionDomainFix.h - Execution Domain Fix -*- C++ -*--==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 /// \file Execution Domain Fix pass.
  11 ///
  12 /// Some X86 SSE instructions like mov, and, or, xor are available in different
  13 /// variants for different operand types. These variant instructions are
  14 /// equivalent, but on Nehalem and newer cpus there is extra latency
  15 /// transferring data between integer and floating point domains.  ARM cores
  16 /// have similar issues when they are configured with both VFP and NEON
  17 /// pipelines.
  18 ///
  19 /// This pass changes the variant instructions to minimize domain crossings.
  20 //
  21 //===----------------------------------------------------------------------===//
  22
  23 #ifndef LLVM_CODEGEN_EXECUTIONDOMAINFIX_H
  24 #define LLVM_CODEGEN_EXECUTIONDOMAINFIX_H
  25
  26 #include "llvm/ADT/SmallVector.h"
  27 #include "llvm/CodeGen/LoopTraversal.h"
  28 #include "llvm/CodeGen/MachineFunctionPass.h"
  29 #include "llvm/CodeGen/ReachingDefAnalysis.h"
  30 #include "llvm/CodeGen/TargetRegisterInfo.h"
  31
  32 namespace llvm {
  33
  34 class MachineBasicBlock;
  35 class MachineInstr;
  36 class TargetInstrInfo;
  37
  38 /// A DomainValue is a bit like LiveIntervals' ValNo, but it also keeps track
  39 /// of execution domains.
  40 ///
  41 /// An open DomainValue represents a set of instructions that can still switch
  42 /// execution domain. Multiple registers may refer to the same open
  43 /// DomainValue - they will eventually be collapsed to the same execution
  44 /// domain.
  45 ///
  46 /// A collapsed DomainValue represents a single register that has been forced
  47 /// into one of more execution domains. There is a separate collapsed
  48 /// DomainValue for each register, but it may contain multiple execution
  49 /// domains. A register value is initially created in a single execution
  50 /// domain, but if we were forced to pay the penalty of a domain crossing, we
  51 /// keep track of the fact that the register is now available in multiple
  52 /// domains.
  53 struct DomainValue {
  54   /// Basic reference counting.
  55   unsigned Refs = 0;
  56
  57   /// Bitmask of available domains. For an open DomainValue, it is the still
  58   /// possible domains for collapsing. For a collapsed DomainValue it is the
  59   /// domains where the register is available for free.
  60   unsigned AvailableDomains;
  61
  62   /// Pointer to the next DomainValue in a chain.  When two DomainValues are
  63   /// merged, Victim.Next is set to point to Victor, so old DomainValue
  64   /// references can be updated by following the chain.
  65   DomainValue *Next;
  66
  67   /// Twiddleable instructions using or defining these registers.
  68   SmallVector<MachineInstr *, 8> Instrs;
  69
  70   DomainValue() { clear(); }
  71
  72   /// A collapsed DomainValue has no instructions to twiddle - it simply keeps
  73   /// track of the domains where the registers are already available.
  74   bool isCollapsed() const { return Instrs.empty(); }
  75
  76   /// Is domain available?
  77   bool hasDomain(unsigned domain) const {
  78     assert(domain <
  79                static_cast<unsigned>(std::numeric_limits<unsigned>::digits) &&
  80            "undefined behavior");
  81     return AvailableDomains & (1u << domain);
  82   }
  83
  84   /// Mark domain as available.
  85   void addDomain(unsigned domain) { AvailableDomains |= 1u << domain; }
  86
  87   // Restrict to a single domain available.
  88   void setSingleDomain(unsigned domain) { AvailableDomains = 1u << domain; }
  89
  90   /// Return bitmask of domains that are available and in mask.
  91   unsigned getCommonDomains(unsigned mask) const {
  92     return AvailableDomains & mask;
  93   }
  94
  95   /// First domain available.
  96   unsigned getFirstDomain() const {
  97     return countTrailingZeros(AvailableDomains);
  98   }
  99
 100   /// Clear this DomainValue and point to next which has all its data.
 101   void clear() {
 102     AvailableDomains = 0;
 103     Next = nullptr;
 104     Instrs.clear();
 105   }
 106 };
 107
 108 class ExecutionDomainFix : public MachineFunctionPass {
 109   SpecificBumpPtrAllocator<DomainValue> Allocator;
 110   SmallVector<DomainValue *, 16> Avail;
 111
 112   const TargetRegisterClass *const RC;
 113   MachineFunction *MF;
 114   const TargetInstrInfo *TII;
 115   const TargetRegisterInfo *TRI;
 116   std::vector<SmallVector<int, 1>> AliasMap;
 117   const unsigned NumRegs;
 118   /// Value currently in each register, or NULL when no value is being tracked.
 119   /// This counts as a DomainValue reference.
 120   using LiveRegsDVInfo = std::vector<DomainValue *>;
 121   LiveRegsDVInfo LiveRegs;
 122   /// Keeps domain information for all registers. Note that this
 123   /// is different from the usual definition notion of liveness. The CPU
 124   /// doesn't care whether or not we consider a register killed.
 125   using OutRegsInfoMap = SmallVector<LiveRegsDVInfo, 4>;
 126   OutRegsInfoMap MBBOutRegsInfos;
 127
 128   ReachingDefAnalysis *RDA;
 129
 130 public:
 131   ExecutionDomainFix(char &PassID, const TargetRegisterClass &RC)
 132       : MachineFunctionPass(PassID), RC(&RC), NumRegs(RC.getNumRegs()) {}
 133
 134   void getAnalysisUsage(AnalysisUsage &AU) const override {
 135     AU.setPreservesAll();
 136     AU.addRequired<ReachingDefAnalysis>();
 137     MachineFunctionPass::getAnalysisUsage(AU);
 138   }
 139
 140   bool runOnMachineFunction(MachineFunction &MF) override;
 141
 142   MachineFunctionProperties getRequiredProperties() const override {
 143     return MachineFunctionProperties().set(
 144         MachineFunctionProperties::Property::NoVRegs);
 145   }
 146
 147 private:
 148   /// Translate TRI register number to a list of indices into our smaller tables
 149   /// of interesting registers.
 150   iterator_range<SmallVectorImpl<int>::const_iterator>
 151   regIndices(unsigned Reg) const;
 152
 153   /// DomainValue allocation.
 154   DomainValue *alloc(int domain = -1);
 155
 156   /// Add reference to DV.
 157   DomainValue *retain(DomainValue *DV) {
 158     if (DV)
 159       ++DV->Refs;
 160     return DV;
 161   }
 162
 163   /// Release a reference to DV.  When the last reference is released,
 164   /// collapse if needed.
 165   void release(DomainValue *);
 166
 167   /// Follow the chain of dead DomainValues until a live DomainValue is reached.
 168   /// Update the referenced pointer when necessary.
 169   DomainValue *resolve(DomainValue *&);
 170
 171   /// Set LiveRegs[rx] = dv, updating reference counts.
 172   void setLiveReg(int rx, DomainValue *DV);
 173
 174   /// Kill register rx, recycle or collapse any DomainValue.
 175   void kill(int rx);
 176
 177   /// Force register rx into domain.
 178   void force(int rx, unsigned domain);
 179
 180   /// Collapse open DomainValue into given domain. If there are multiple
 181   /// registers using dv, they each get a unique collapsed DomainValue.
 182   void collapse(DomainValue *dv, unsigned domain);
 183
 184   /// All instructions and registers in B are moved to A, and B is released.
 185   bool merge(DomainValue *A, DomainValue *B);
 186
 187   /// Set up LiveRegs by merging predecessor live-out values.
 188   void enterBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
 189
 190   /// Update live-out values.
 191   void leaveBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
 192
 193   /// Process he given basic block.
 194   void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
 195
 196   /// Visit given insturcion.
 197   bool visitInstr(MachineInstr *);
 198
 199   /// Update def-ages for registers defined by MI.
 200   /// If Kill is set, also kill off DomainValues clobbered by the defs.
 201   void processDefs(MachineInstr *, bool Kill);
 202
 203   /// A soft instruction can be changed to work in other domains given by mask.
 204   void visitSoftInstr(MachineInstr *, unsigned mask);
 205
 206   /// A hard instruction only works in one domain. All input registers will be
 207   /// forced into that domain.
 208   void visitHardInstr(MachineInstr *, unsigned domain);
 209 };
 210
 211 } // namespace llvm
 212
 213 #endif // LLVM_CODEGEN_EXECUTIONDOMAINFIX_H