LLVM  6.0.0svn
ExecutionDepsFix.h
Go to the documentation of this file.
1 //==- llvm/CodeGen/ExecutionDepsFix.h - Execution Dependency 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 Dependency 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_EXECUTIONDEPSFIX_H
24 #define LLVM_CODEGEN_EXECUTIONDEPSFIX_H
25 
26 #include "llvm/ADT/DenseMap.h"
28 #include "llvm/ADT/SmallVector.h"
33 #include "llvm/Pass.h"
34 #include "llvm/Support/Allocator.h"
36 #include <cassert>
37 #include <limits>
38 #include <utility>
39 #include <vector>
40 
41 namespace llvm {
42 
43 class MachineBasicBlock;
44 class MachineInstr;
45 class TargetInstrInfo;
46 
47 /// A DomainValue is a bit like LiveIntervals' ValNo, but it also keeps track
48 /// of execution domains.
49 ///
50 /// An open DomainValue represents a set of instructions that can still switch
51 /// execution domain. Multiple registers may refer to the same open
52 /// DomainValue - they will eventually be collapsed to the same execution
53 /// domain.
54 ///
55 /// A collapsed DomainValue represents a single register that has been forced
56 /// into one of more execution domains. There is a separate collapsed
57 /// DomainValue for each register, but it may contain multiple execution
58 /// domains. A register value is initially created in a single execution
59 /// domain, but if we were forced to pay the penalty of a domain crossing, we
60 /// keep track of the fact that the register is now available in multiple
61 /// domains.
62 struct DomainValue {
63  // Basic reference counting.
64  unsigned Refs = 0;
65 
66  // Bitmask of available domains. For an open DomainValue, it is the still
67  // possible domains for collapsing. For a collapsed DomainValue it is the
68  // domains where the register is available for free.
69  unsigned AvailableDomains;
70 
71  // Pointer to the next DomainValue in a chain. When two DomainValues are
72  // merged, Victim.Next is set to point to Victor, so old DomainValue
73  // references can be updated by following the chain.
75 
76  // Twiddleable instructions using or defining these registers.
78 
79  DomainValue() { clear(); }
80 
81  // A collapsed DomainValue has no instructions to twiddle - it simply keeps
82  // track of the domains where the registers are already available.
83  bool isCollapsed() const { return Instrs.empty(); }
84 
85  // Is domain available?
86  bool hasDomain(unsigned domain) const {
87  assert(domain <
88  static_cast<unsigned>(std::numeric_limits<unsigned>::digits) &&
89  "undefined behavior");
90  return AvailableDomains & (1u << domain);
91  }
92 
93  // Mark domain as available.
94  void addDomain(unsigned domain) {
95  AvailableDomains |= 1u << domain;
96  }
97 
98  // Restrict to a single domain available.
99  void setSingleDomain(unsigned domain) {
100  AvailableDomains = 1u << domain;
101  }
102 
103  // Return bitmask of domains that are available and in mask.
104  unsigned getCommonDomains(unsigned mask) const {
105  return AvailableDomains & mask;
106  }
107 
108  // First domain available.
109  unsigned getFirstDomain() const {
110  return countTrailingZeros(AvailableDomains);
111  }
112 
113  // Clear this DomainValue and point to next which has all its data.
114  void clear() {
115  AvailableDomains = 0;
116  Next = nullptr;
117  Instrs.clear();
118  }
119 };
120 
121 /// Information about a live register.
122 struct LiveReg {
123  /// Value currently in this register, or NULL when no value is being tracked.
124  /// This counts as a DomainValue reference.
126 
127  /// Instruction that defined this register, relative to the beginning of the
128  /// current basic block. When a LiveReg is used to represent a live-out
129  /// register, this value is relative to the end of the basic block, so it
130  /// will be a negative number.
131  int Def;
132 };
133 
137 
138  const TargetRegisterClass *const RC;
139  MachineFunction *MF;
140  const TargetInstrInfo *TII;
141  const TargetRegisterInfo *TRI;
142  RegisterClassInfo RegClassInfo;
143  std::vector<SmallVector<int, 1>> AliasMap;
144  const unsigned NumRegs;
145  LiveReg *LiveRegs;
146  struct MBBInfo {
147  // Keeps clearance and domain information for all registers. Note that this
148  // is different from the usual definition notion of liveness. The CPU
149  // doesn't care whether or not we consider a register killed.
150  LiveReg *OutRegs = nullptr;
151 
152  // Whether we have gotten to this block in primary processing yet.
153  bool PrimaryCompleted = false;
154 
155  // The number of predecessors for which primary processing has completed
156  unsigned IncomingProcessed = 0;
157 
158  // The value of `IncomingProcessed` at the start of primary processing
159  unsigned PrimaryIncoming = 0;
160 
161  // The number of predecessors for which all processing steps are done.
162  unsigned IncomingCompleted = 0;
163 
164  MBBInfo() = default;
165  };
167  MBBInfoMap MBBInfos;
168 
169  /// List of undefined register reads in this block in forward order.
170  std::vector<std::pair<MachineInstr *, unsigned>> UndefReads;
171 
172  /// Storage for register unit liveness.
174 
175  /// Current instruction number.
176  /// The first instruction in each basic block is 0.
177  int CurInstr;
178 
179 public:
180  ExecutionDepsFix(char &PassID, const TargetRegisterClass &RC)
181  : MachineFunctionPass(PassID), RC(&RC), NumRegs(RC.getNumRegs()) {}
182 
183  void getAnalysisUsage(AnalysisUsage &AU) const override {
184  AU.setPreservesAll();
186  }
187 
188  bool runOnMachineFunction(MachineFunction &MF) override;
189 
193  }
194 
195 private:
197  regIndices(unsigned Reg) const;
198  // DomainValue allocation.
199  DomainValue *alloc(int domain = -1);
200  DomainValue *retain(DomainValue *DV) {
201  if (DV) ++DV->Refs;
202  return DV;
203  }
204  void release(DomainValue*);
205  DomainValue *resolve(DomainValue*&);
206 
207  // LiveRegs manipulations.
208  void setLiveReg(int rx, DomainValue *DV);
209  void kill(int rx);
210  void force(int rx, unsigned domain);
211  void collapse(DomainValue *dv, unsigned domain);
212  bool merge(DomainValue *A, DomainValue *B);
213 
214  void enterBasicBlock(MachineBasicBlock*);
215  void leaveBasicBlock(MachineBasicBlock*);
216  bool isBlockDone(MachineBasicBlock *);
217  void processBasicBlock(MachineBasicBlock *MBB, bool PrimaryPass);
218  bool visitInstr(MachineInstr *);
219  void processDefs(MachineInstr *, bool breakDependency, bool Kill);
220  void visitSoftInstr(MachineInstr*, unsigned mask);
221  void visitHardInstr(MachineInstr*, unsigned domain);
222  bool pickBestRegisterForUndef(MachineInstr *MI, unsigned OpIdx,
223  unsigned Pref);
224  bool shouldBreakDependence(MachineInstr*, unsigned OpIdx, unsigned Pref);
225  void processUndefReads(MachineBasicBlock*);
226 };
227 
228 } // end namepsace llvm
229 
230 #endif // LLVM_CODEGEN_EXECUTIONDEPSFIX_H
unsigned getCommonDomains(unsigned mask) const
void addDomain(unsigned domain)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
unsigned getFirstDomain() const
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
Reg
All possible values of the reg field in the ModR/M byte.
DomainValue * Value
Value currently in this register, or NULL when no value is being tracked.
DomainValue * Next
ExecutionDepsFix(char &PassID, const TargetRegisterClass &RC)
TargetInstrInfo - Interface to description of machine instruction set.
bool hasDomain(unsigned domain) const
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
int Def
Instruction that defined this register, relative to the beginning of the current basic block...
std::size_t countTrailingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0&#39;s from the least significant bit to the most stopping at the first 1...
Definition: MathExtras.h:112
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Represent the analysis usage information of a pass.
SmallVector< MachineInstr *, 8 > Instrs
A set of live virtual registers and physical register units.
Information about a live register.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
Basic Register Allocator
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
void setSingleDomain(unsigned domain)
A BumpPtrAllocator that allows only elements of a specific type to be allocated.
Definition: Allocator.h:385
A range adaptor for a pair of iterators.
void setPreservesAll()
Set by analyses that do not transform their input at all.
A DomainValue is a bit like LiveIntervals&#39; ValNo, but it also keeps track of execution domains...
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:59
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:49
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
IRTranslator LLVM IR MI
bool isCollapsed() const
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties getRequiredProperties() const override