LLVM  10.0.0svn
CSEInfo.cpp
Go to the documentation of this file.
1 //===- CSEInfo.cpp ------------------------------===//
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 //
10 //===----------------------------------------------------------------------===//
13 
14 #define DEBUG_TYPE "cseinfo"
15 
16 using namespace llvm;
19  "Analysis containing CSE Info", false, true)
21  "Analysis containing CSE Info", false, true)
22 
23 /// -------- UniqueMachineInstr -------------//
24 
26  GISelInstProfileBuilder(ID, MI->getMF()->getRegInfo()).addNodeID(MI);
27 }
28 /// -----------------------------------------
29 
30 /// --------- CSEConfigFull ---------- ///
31 bool CSEConfigFull::shouldCSEOpc(unsigned Opc) {
32  switch (Opc) {
33  default:
34  break;
35  case TargetOpcode::G_ADD:
36  case TargetOpcode::G_AND:
37  case TargetOpcode::G_ASHR:
38  case TargetOpcode::G_LSHR:
39  case TargetOpcode::G_MUL:
40  case TargetOpcode::G_OR:
41  case TargetOpcode::G_SHL:
42  case TargetOpcode::G_SUB:
43  case TargetOpcode::G_XOR:
44  case TargetOpcode::G_UDIV:
45  case TargetOpcode::G_SDIV:
46  case TargetOpcode::G_UREM:
47  case TargetOpcode::G_SREM:
48  case TargetOpcode::G_CONSTANT:
49  case TargetOpcode::G_FCONSTANT:
50  case TargetOpcode::G_ZEXT:
51  case TargetOpcode::G_SEXT:
52  case TargetOpcode::G_ANYEXT:
53  case TargetOpcode::G_UNMERGE_VALUES:
54  case TargetOpcode::G_TRUNC:
55  case TargetOpcode::G_GEP:
56  return true;
57  }
58  return false;
59 }
60 
62  return Opc == TargetOpcode::G_CONSTANT;
63 }
64 
65 std::unique_ptr<CSEConfigBase>
67  std::unique_ptr<CSEConfigBase> Config;
68  if (Level == CodeGenOpt::None)
69  Config = std::make_unique<CSEConfigConstantOnly>();
70  else
71  Config = std::make_unique<CSEConfigFull>();
72  return Config;
73 }
74 
75 /// -----------------------------------------
76 
77 /// -------- GISelCSEInfo -------------//
79  this->MF = &MF;
80  this->MRI = &MF.getRegInfo();
81 }
82 
84 
85 bool GISelCSEInfo::isUniqueMachineInstValid(
86  const UniqueMachineInstr &UMI) const {
87  // Should we check here and assert that the instruction has been fully
88  // constructed?
89  // FIXME: Any other checks required to be done here? Remove this method if
90  // none.
91  return true;
92 }
93 
94 void GISelCSEInfo::invalidateUniqueMachineInstr(UniqueMachineInstr *UMI) {
95  bool Removed = CSEMap.RemoveNode(UMI);
96  (void)Removed;
97  assert(Removed && "Invalidation called on invalid UMI");
98  // FIXME: Should UMI be deallocated/destroyed?
99 }
100 
101 UniqueMachineInstr *GISelCSEInfo::getNodeIfExists(FoldingSetNodeID &ID,
102  MachineBasicBlock *MBB,
103  void *&InsertPos) {
104  auto *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
105  if (Node) {
106  if (!isUniqueMachineInstValid(*Node)) {
107  invalidateUniqueMachineInstr(Node);
108  return nullptr;
109  }
110 
111  if (Node->MI->getParent() != MBB)
112  return nullptr;
113  }
114  return Node;
115 }
116 
117 void GISelCSEInfo::insertNode(UniqueMachineInstr *UMI, void *InsertPos) {
118  handleRecordedInsts();
119  assert(UMI);
120  UniqueMachineInstr *MaybeNewNode = UMI;
121  if (InsertPos)
122  CSEMap.InsertNode(UMI, InsertPos);
123  else
124  MaybeNewNode = CSEMap.GetOrInsertNode(UMI);
125  if (MaybeNewNode != UMI) {
126  // A similar node exists in the folding set. Let's ignore this one.
127  return;
128  }
129  assert(InstrMapping.count(UMI->MI) == 0 &&
130  "This instruction should not be in the map");
131  InstrMapping[UMI->MI] = MaybeNewNode;
132 }
133 
134 UniqueMachineInstr *GISelCSEInfo::getUniqueInstrForMI(const MachineInstr *MI) {
135  assert(shouldCSE(MI->getOpcode()) && "Trying to CSE an unsupported Node");
136  auto *Node = new (UniqueInstrAllocator) UniqueMachineInstr(MI);
137  return Node;
138 }
139 
140 void GISelCSEInfo::insertInstr(MachineInstr *MI, void *InsertPos) {
141  assert(MI);
142  // If it exists in temporary insts, remove it.
143  TemporaryInsts.remove(MI);
144  auto *Node = getUniqueInstrForMI(MI);
145  insertNode(Node, InsertPos);
146 }
147 
148 MachineInstr *GISelCSEInfo::getMachineInstrIfExists(FoldingSetNodeID &ID,
149  MachineBasicBlock *MBB,
150  void *&InsertPos) {
151  handleRecordedInsts();
152  if (auto *Inst = getNodeIfExists(ID, MBB, InsertPos)) {
153  LLVM_DEBUG(dbgs() << "CSEInfo::Found Instr " << *Inst->MI;);
154  return const_cast<MachineInstr *>(Inst->MI);
155  }
156  return nullptr;
157 }
158 
159 void GISelCSEInfo::countOpcodeHit(unsigned Opc) {
160 #ifndef NDEBUG
161  if (OpcodeHitTable.count(Opc))
162  OpcodeHitTable[Opc] += 1;
163  else
164  OpcodeHitTable[Opc] = 1;
165 #endif
166  // Else do nothing.
167 }
168 
170  if (shouldCSE(MI->getOpcode())) {
171  TemporaryInsts.insert(MI);
172  LLVM_DEBUG(dbgs() << "CSEInfo::Recording new MI " << *MI);
173  }
174 }
175 
177  assert(shouldCSE(MI->getOpcode()) && "Invalid instruction for CSE");
178  auto *UMI = InstrMapping.lookup(MI);
179  LLVM_DEBUG(dbgs() << "CSEInfo::Handling recorded MI " << *MI);
180  if (UMI) {
181  // Invalidate this MI.
182  invalidateUniqueMachineInstr(UMI);
183  InstrMapping.erase(MI);
184  }
185  /// Now insert the new instruction.
186  if (UMI) {
187  /// We'll reuse the same UniqueMachineInstr to avoid the new
188  /// allocation.
189  *UMI = UniqueMachineInstr(MI);
190  insertNode(UMI, nullptr);
191  } else {
192  /// This is a new instruction. Allocate a new UniqueMachineInstr and
193  /// Insert.
194  insertInstr(MI);
195  }
196 }
197 
199  if (auto *UMI = InstrMapping.lookup(MI)) {
200  invalidateUniqueMachineInstr(UMI);
201  InstrMapping.erase(MI);
202  }
203  TemporaryInsts.remove(MI);
204 }
205 
207  while (!TemporaryInsts.empty()) {
208  auto *MI = TemporaryInsts.pop_back_val();
209  handleRecordedInst(MI);
210  }
211 }
212 
213 bool GISelCSEInfo::shouldCSE(unsigned Opc) const {
214  // Only GISel opcodes are CSEable
215  if (!isPreISelGenericOpcode(Opc))
216  return false;
217  assert(CSEOpt.get() && "CSEConfig not set");
218  return CSEOpt->shouldCSEOpc(Opc);
219 }
220 
221 void GISelCSEInfo::erasingInstr(MachineInstr &MI) { handleRemoveInst(&MI); }
222 void GISelCSEInfo::createdInstr(MachineInstr &MI) { recordNewInstruction(&MI); }
224  // For now, perform erase, followed by insert.
225  erasingInstr(MI);
226  createdInstr(MI);
227 }
228 void GISelCSEInfo::changedInstr(MachineInstr &MI) { changingInstr(MI); }
229 
231  setMF(MF);
232  for (auto &MBB : MF) {
233  if (MBB.empty())
234  continue;
235  for (MachineInstr &MI : MBB) {
236  if (!shouldCSE(MI.getOpcode()))
237  continue;
238  LLVM_DEBUG(dbgs() << "CSEInfo::Add MI: " << MI);
239  insertInstr(&MI);
240  }
241  }
242 }
243 
245  print();
246  CSEMap.clear();
247  InstrMapping.clear();
248  UniqueInstrAllocator.Reset();
249  TemporaryInsts.clear();
250  CSEOpt.reset();
251  MRI = nullptr;
252  MF = nullptr;
253 #ifndef NDEBUG
254  OpcodeHitTable.clear();
255 #endif
256 }
257 
259  LLVM_DEBUG(for (auto &It
260  : OpcodeHitTable) {
261  dbgs() << "CSEInfo::CSE Hit for Opc " << It.first << " : " << It.second
262  << "\n";
263  };);
264 }
265 /// -----------------------------------------
266 // ---- Profiling methods for FoldingSetNode --- //
269  addNodeIDMBB(MI->getParent());
270  addNodeIDOpcode(MI->getOpcode());
271  for (auto &Op : MI->operands())
272  addNodeIDMachineOperand(Op);
273  addNodeIDFlag(MI->getFlags());
274  return *this;
275 }
276 
279  ID.AddInteger(Opc);
280  return *this;
281 }
282 
285  uint64_t Val = Ty.getUniqueRAWLLTData();
286  ID.AddInteger(Val);
287  return *this;
288 }
289 
292  ID.AddPointer(RC);
293  return *this;
294 }
295 
298  ID.AddPointer(RB);
299  return *this;
300 }
301 
304  ID.AddInteger(Imm);
305  return *this;
306 }
307 
310  ID.AddInteger(Reg);
311  return *this;
312 }
313 
316  addNodeIDMachineOperand(MachineOperand::CreateReg(Reg, false));
317  return *this;
318 }
319 
322  ID.AddPointer(MBB);
323  return *this;
324 }
325 
328  if (Flag)
329  ID.AddInteger(Flag);
330  return *this;
331 }
332 
334  const MachineOperand &MO) const {
335  if (MO.isReg()) {
336  Register Reg = MO.getReg();
337  if (!MO.isDef())
338  addNodeIDRegNum(Reg);
339  LLT Ty = MRI.getType(Reg);
340  if (Ty.isValid())
341  addNodeIDRegType(Ty);
342  auto *RB = MRI.getRegBankOrNull(Reg);
343  if (RB)
344  addNodeIDRegType(RB);
345  auto *RC = MRI.getRegClassOrNull(Reg);
346  if (RC)
347  addNodeIDRegType(RC);
348  assert(!MO.isImplicit() && "Unhandled case");
349  } else if (MO.isImm())
350  ID.AddInteger(MO.getImm());
351  else if (MO.isCImm())
352  ID.AddPointer(MO.getCImm());
353  else if (MO.isFPImm())
354  ID.AddPointer(MO.getFPImm());
355  else if (MO.isPredicate())
356  ID.AddInteger(MO.getPredicate());
357  else
358  llvm_unreachable("Unhandled operand type");
359  // Handle other types
360  return *this;
361 }
362 
363 GISelCSEInfo &
364 GISelCSEAnalysisWrapper::get(std::unique_ptr<CSEConfigBase> CSEOpt,
365  bool Recompute) {
366  if (!AlreadyComputed || Recompute) {
367  Info.setCSEConfig(std::move(CSEOpt));
368  Info.analyze(*MF);
369  AlreadyComputed = true;
370  }
371  return Info;
372 }
374  AU.setPreservesAll();
376 }
377 
379  releaseMemory();
380  Wrapper.setMF(MF);
381  return false;
382 }
void changedInstr(MachineInstr &MI) override
This instruction was mutated in some way.
Definition: CSEInfo.cpp:228
virtual ~GISelCSEInfo()
Definition: CSEInfo.cpp:83
void AddPointer(const void *Ptr)
Add* - Add various data types to Bit data.
Definition: FoldingSet.cpp:51
The CSE Analysis object.
Definition: CSEInfo.h:71
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Definition: CSEInfo.cpp:378
unsigned Reg
const GISelInstProfileBuilder & addNodeIDImmediate(int64_t Imm) const
Definition: CSEInfo.cpp:303
The actual analysis pass wrapper.
Definition: CSEInfo.h:218
block Block Frequency true
void setMF(MachineFunction &MF)
Definition: CSEInfo.cpp:78
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:461
const GISelInstProfileBuilder & addNodeIDRegNum(unsigned Reg) const
Definition: CSEInfo.cpp:309
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
const GISelInstProfileBuilder & addNodeIDFlag(unsigned Flag) const
Definition: CSEInfo.cpp:327
void changingInstr(MachineInstr &MI) override
This instruction is about to be mutated in some way.
Definition: CSEInfo.cpp:223
amdgpu aa AMDGPU Address space based Alias Analysis Wrapper
const GISelInstProfileBuilder & addNodeIDOpcode(unsigned Opc) const
Definition: CSEInfo.cpp:278
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: CSEInfo.cpp:373
const ConstantFP * getFPImm() const
separate const offset from Split GEPs to a variadic base and a constant offset for better CSE
void AddInteger(signed I)
Definition: FoldingSet.cpp:60
virtual bool shouldCSEOpc(unsigned Opc) override
Definition: CSEInfo.cpp:61
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:411
const GISelInstProfileBuilder & addNodeIDRegType(const LLT &Ty) const
Definition: CSEInfo.cpp:284
void erasingInstr(MachineInstr &MI) override
An instruction is about to be erased.
Definition: CSEInfo.cpp:221
bool isFPImm() const
isFPImm - Tests if this is a MO_FPImmediate operand.
bool isPredicate() const
void releaseMemory()
Definition: CSEInfo.cpp:244
bool shouldCSE(unsigned Opc) const
Definition: CSEInfo.cpp:213
void handleRemoveInst(MachineInstr *MI)
Remove this inst from the CSE map.
Definition: CSEInfo.cpp:198
Analysis containing CSE Info
Definition: CSEInfo.cpp:20
virtual bool shouldCSEOpc(unsigned Opc) override
Definition: CSEInfo.cpp:31
Flag
These should be considered private to the implementation of the MCInstrDesc class.
Definition: MCInstrDesc.h:131
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:305
std::unique_ptr< CSEConfigBase > getStandardCSEConfigForOpt(CodeGenOpt::Level Level)
Definition: CSEInfo.cpp:66
INITIALIZE_PASS_BEGIN(GISelCSEAnalysisWrapperPass, DEBUG_TYPE, "Analysis containing CSE Info", false, true) INITIALIZE_PASS_END(GISelCSEAnalysisWrapperPass
unsigned const MachineRegisterInfo * MRI
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
bool isCImm() const
isCImm - Test if this is a MO_CImmediate operand.
const GISelInstProfileBuilder & addNodeID(const MachineInstr *MI) const
Definition: CSEInfo.cpp:268
Represent the analysis usage information of a pass.
void countOpcodeHit(unsigned Opc)
Definition: CSEInfo.cpp:159
GISelCSEInfo & get(std::unique_ptr< CSEConfigBase > CSEOpt, bool ReCompute=false)
Takes a CSEConfigBase object that defines what opcodes get CSEd.
Definition: CSEInfo.cpp:364
bool isValid() const
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
static MachineOperand CreateReg(Register Reg, bool isDef, bool isImp=false, bool isKill=false, bool isDead=false, bool isUndef=false, bool isEarlyClobber=false, unsigned SubReg=0, bool isDebug=false, bool isInternalRead=false, bool isRenamable=false)
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void handleRecordedInst(MachineInstr *MI)
Use this callback to inform CSE about a newly fully created instruction.
Definition: CSEInfo.cpp:176
void recordNewInstruction(MachineInstr *MI)
Records a newly created inst in a list and lazily insert it to the CSEMap.
Definition: CSEInfo.cpp:169
MachineOperand class - Representation of each machine instruction operand.
void analyze(MachineFunction &MF)
Definition: CSEInfo.cpp:230
This class implements the register bank concept.
Definition: RegisterBank.h:28
int64_t getImm() const
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void setPreservesAll()
Set by analyses that do not transform their input at all.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:256
Representation of each machine instruction.
Definition: MachineInstr.h:64
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
const GISelInstProfileBuilder & addNodeIDMBB(const MachineBasicBlock *MBB) const
Definition: CSEInfo.cpp:321
bool isReg() const
isReg - Tests if this is a MO_Register operand.
uint16_t getFlags() const
Return the MI flags bitvector.
Definition: MachineInstr.h:292
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isPreISelGenericOpcode(unsigned Opcode)
Check whether the given Opcode is a generic opcode that is not supposed to appear after ISel...
Definition: TargetOpcodes.h:30
const GISelInstProfileBuilder & addNodeIDMachineOperand(const MachineOperand &MO) const
Definition: CSEInfo.cpp:333
void createdInstr(MachineInstr &MI) override
An instruction has been created and inserted into the function.
Definition: CSEInfo.cpp:222
IRTranslator LLVM IR MI
#define DEBUG_TYPE
Definition: CSEInfo.cpp:14
A class that wraps MachineInstrs and derives from FoldingSetNode in order to be uniqued in a CSEMap...
Definition: CSEInfo.h:31
Register getReg() const
getReg - Returns the register number.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
void handleRecordedInsts()
Use this callback to insert all the recorded instructions.
Definition: CSEInfo.cpp:206
const ConstantInt * getCImm() const
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
bool isImplicit() const
unsigned getPredicate() const