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 
DomainValueDomainValue70   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.
isCollapsedDomainValue74   bool isCollapsed() const { return Instrs.empty(); }
75 
76   /// Is domain available?
hasDomainDomainValue77   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.
addDomainDomainValue85   void addDomain(unsigned domain) { AvailableDomains |= 1u << domain; }
86 
87   // Restrict to a single domain available.
setSingleDomainDomainValue88   void setSingleDomain(unsigned domain) { AvailableDomains = 1u << domain; }
89 
90   /// Return bitmask of domains that are available and in mask.
getCommonDomainsDomainValue91   unsigned getCommonDomains(unsigned mask) const {
92     return AvailableDomains & mask;
93   }
94 
95   /// First domain available.
getFirstDomainDomainValue96   unsigned getFirstDomain() const {
97     return countTrailingZeros(AvailableDomains);
98   }
99 
100   /// Clear this DomainValue and point to next which has all its data.
clearDomainValue101   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:
ExecutionDomainFix(char & PassID,const TargetRegisterClass & RC)131   ExecutionDomainFix(char &PassID, const TargetRegisterClass &RC)
132       : MachineFunctionPass(PassID), RC(&RC), NumRegs(RC.getNumRegs()) {}
133 
getAnalysisUsage(AnalysisUsage & AU)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 
getRequiredProperties()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.
retain(DomainValue * 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
214