LLVM  9.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  return true;
56  }
57  return false;
58 }
59 
61  return Opc == TargetOpcode::G_CONSTANT;
62 }
63 
64 std::unique_ptr<CSEConfigBase>
66  std::unique_ptr<CSEConfigBase> Config;
67  if (Level == CodeGenOpt::None)
68  Config = make_unique<CSEConfigConstantOnly>();
69  else
70  Config = make_unique<CSEConfigFull>();
71  return Config;
72 }
73 
74 /// -----------------------------------------
75 
76 /// -------- GISelCSEInfo -------------//
78  this->MF = &MF;
79  this->MRI = &MF.getRegInfo();
80 }
81 
83 
84 bool GISelCSEInfo::isUniqueMachineInstValid(
85  const UniqueMachineInstr &UMI) const {
86  // Should we check here and assert that the instruction has been fully
87  // constructed?
88  // FIXME: Any other checks required to be done here? Remove this method if
89  // none.
90  return true;
91 }
92 
93 void GISelCSEInfo::invalidateUniqueMachineInstr(UniqueMachineInstr *UMI) {
94  bool Removed = CSEMap.RemoveNode(UMI);
95  (void)Removed;
96  assert(Removed && "Invalidation called on invalid UMI");
97  // FIXME: Should UMI be deallocated/destroyed?
98 }
99 
100 UniqueMachineInstr *GISelCSEInfo::getNodeIfExists(FoldingSetNodeID &ID,
101  MachineBasicBlock *MBB,
102  void *&InsertPos) {
103  auto *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
104  if (Node) {
105  if (!isUniqueMachineInstValid(*Node)) {
106  invalidateUniqueMachineInstr(Node);
107  return nullptr;
108  }
109 
110  if (Node->MI->getParent() != MBB)
111  return nullptr;
112  }
113  return Node;
114 }
115 
116 void GISelCSEInfo::insertNode(UniqueMachineInstr *UMI, void *InsertPos) {
117  handleRecordedInsts();
118  assert(UMI);
119  UniqueMachineInstr *MaybeNewNode = UMI;
120  if (InsertPos)
121  CSEMap.InsertNode(UMI, InsertPos);
122  else
123  MaybeNewNode = CSEMap.GetOrInsertNode(UMI);
124  if (MaybeNewNode != UMI) {
125  // A similar node exists in the folding set. Let's ignore this one.
126  return;
127  }
128  assert(InstrMapping.count(UMI->MI) == 0 &&
129  "This instruction should not be in the map");
130  InstrMapping[UMI->MI] = MaybeNewNode;
131 }
132 
133 UniqueMachineInstr *GISelCSEInfo::getUniqueInstrForMI(const MachineInstr *MI) {
134  assert(shouldCSE(MI->getOpcode()) && "Trying to CSE an unsupported Node");
135  auto *Node = new (UniqueInstrAllocator) UniqueMachineInstr(MI);
136  return Node;
137 }
138 
139 void GISelCSEInfo::insertInstr(MachineInstr *MI, void *InsertPos) {
140  assert(MI);
141  // If it exists in temporary insts, remove it.
142  TemporaryInsts.remove(MI);
143  auto *Node = getUniqueInstrForMI(MI);
144  insertNode(Node, InsertPos);
145 }
146 
147 MachineInstr *GISelCSEInfo::getMachineInstrIfExists(FoldingSetNodeID &ID,
148  MachineBasicBlock *MBB,
149  void *&InsertPos) {
150  handleRecordedInsts();
151  if (auto *Inst = getNodeIfExists(ID, MBB, InsertPos)) {
152  LLVM_DEBUG(dbgs() << "CSEInfo::Found Instr " << *Inst->MI;);
153  return const_cast<MachineInstr *>(Inst->MI);
154  }
155  return nullptr;
156 }
157 
158 void GISelCSEInfo::countOpcodeHit(unsigned Opc) {
159 #ifndef NDEBUG
160  if (OpcodeHitTable.count(Opc))
161  OpcodeHitTable[Opc] += 1;
162  else
163  OpcodeHitTable[Opc] = 1;
164 #endif
165  // Else do nothing.
166 }
167 
169  if (shouldCSE(MI->getOpcode())) {
170  TemporaryInsts.insert(MI);
171  LLVM_DEBUG(dbgs() << "CSEInfo::Recording new MI " << *MI);
172  }
173 }
174 
176  assert(shouldCSE(MI->getOpcode()) && "Invalid instruction for CSE");
177  auto *UMI = InstrMapping.lookup(MI);
178  LLVM_DEBUG(dbgs() << "CSEInfo::Handling recorded MI " << *MI);
179  if (UMI) {
180  // Invalidate this MI.
181  invalidateUniqueMachineInstr(UMI);
182  InstrMapping.erase(MI);
183  }
184  /// Now insert the new instruction.
185  if (UMI) {
186  /// We'll reuse the same UniqueMachineInstr to avoid the new
187  /// allocation.
188  *UMI = UniqueMachineInstr(MI);
189  insertNode(UMI, nullptr);
190  } else {
191  /// This is a new instruction. Allocate a new UniqueMachineInstr and
192  /// Insert.
193  insertInstr(MI);
194  }
195 }
196 
198  if (auto *UMI = InstrMapping.lookup(MI)) {
199  invalidateUniqueMachineInstr(UMI);
200  InstrMapping.erase(MI);
201  }
202  TemporaryInsts.remove(MI);
203 }
204 
206  while (!TemporaryInsts.empty()) {
207  auto *MI = TemporaryInsts.pop_back_val();
208  handleRecordedInst(MI);
209  }
210 }
211 
212 bool GISelCSEInfo::shouldCSE(unsigned Opc) const {
213  // Only GISel opcodes are CSEable
214  if (!isPreISelGenericOpcode(Opc))
215  return false;
216  assert(CSEOpt.get() && "CSEConfig not set");
217  return CSEOpt->shouldCSEOpc(Opc);
218 }
219 
220 void GISelCSEInfo::erasingInstr(MachineInstr &MI) { handleRemoveInst(&MI); }
221 void GISelCSEInfo::createdInstr(MachineInstr &MI) { recordNewInstruction(&MI); }
223  // For now, perform erase, followed by insert.
224  erasingInstr(MI);
225  createdInstr(MI);
226 }
227 void GISelCSEInfo::changedInstr(MachineInstr &MI) { changingInstr(MI); }
228 
230  setMF(MF);
231  for (auto &MBB : MF) {
232  if (MBB.empty())
233  continue;
234  for (MachineInstr &MI : MBB) {
235  if (!shouldCSE(MI.getOpcode()))
236  continue;
237  LLVM_DEBUG(dbgs() << "CSEInfo::Add MI: " << MI);
238  insertInstr(&MI);
239  }
240  }
241 }
242 
244  print();
245  CSEMap.clear();
246  InstrMapping.clear();
247  UniqueInstrAllocator.Reset();
248  TemporaryInsts.clear();
249  CSEOpt.reset();
250  MRI = nullptr;
251  MF = nullptr;
252 #ifndef NDEBUG
253  OpcodeHitTable.clear();
254 #endif
255 }
256 
258  LLVM_DEBUG(for (auto &It
259  : OpcodeHitTable) {
260  dbgs() << "CSEInfo::CSE Hit for Opc " << It.first << " : " << It.second
261  << "\n";
262  };);
263 }
264 /// -----------------------------------------
265 // ---- Profiling methods for FoldingSetNode --- //
268  addNodeIDMBB(MI->getParent());
269  addNodeIDOpcode(MI->getOpcode());
270  for (auto &Op : MI->operands())
271  addNodeIDMachineOperand(Op);
272  addNodeIDFlag(MI->getFlags());
273  return *this;
274 }
275 
278  ID.AddInteger(Opc);
279  return *this;
280 }
281 
284  uint64_t Val = Ty.getUniqueRAWLLTData();
285  ID.AddInteger(Val);
286  return *this;
287 }
288 
291  ID.AddPointer(RC);
292  return *this;
293 }
294 
297  ID.AddPointer(RB);
298  return *this;
299 }
300 
303  ID.AddInteger(Imm);
304  return *this;
305 }
306 
309  ID.AddInteger(Reg);
310  return *this;
311 }
312 
315  addNodeIDMachineOperand(MachineOperand::CreateReg(Reg, false));
316  return *this;
317 }
318 
321  ID.AddPointer(MBB);
322  return *this;
323 }
324 
327  if (Flag)
328  ID.AddInteger(Flag);
329  return *this;
330 }
331 
333  const MachineOperand &MO) const {
334  if (MO.isReg()) {
335  unsigned Reg = MO.getReg();
336  if (!MO.isDef())
337  addNodeIDRegNum(Reg);
338  LLT Ty = MRI.getType(Reg);
339  if (Ty.isValid())
340  addNodeIDRegType(Ty);
341  auto *RB = MRI.getRegBankOrNull(Reg);
342  if (RB)
343  addNodeIDRegType(RB);
344  auto *RC = MRI.getRegClassOrNull(Reg);
345  if (RC)
346  addNodeIDRegType(RC);
347  assert(!MO.isImplicit() && "Unhandled case");
348  } else if (MO.isImm())
349  ID.AddInteger(MO.getImm());
350  else if (MO.isCImm())
351  ID.AddPointer(MO.getCImm());
352  else if (MO.isFPImm())
353  ID.AddPointer(MO.getFPImm());
354  else if (MO.isPredicate())
355  ID.AddInteger(MO.getPredicate());
356  else
357  llvm_unreachable("Unhandled operand type");
358  // Handle other types
359  return *this;
360 }
361 
362 GISelCSEInfo &
363 GISelCSEAnalysisWrapper::get(std::unique_ptr<CSEConfigBase> CSEOpt,
364  bool Recompute) {
365  if (!AlreadyComputed || Recompute) {
366  Info.setCSEConfig(std::move(CSEOpt));
367  Info.analyze(*MF);
368  AlreadyComputed = true;
369  }
370  return Info;
371 }
373  AU.setPreservesAll();
375 }
376 
378  releaseMemory();
379  Wrapper.setMF(MF);
380  return false;
381 }
void changedInstr(MachineInstr &MI) override
This instruction was mutated in some way.
Definition: CSEInfo.cpp:227
virtual ~GISelCSEInfo()
Definition: CSEInfo.cpp:82
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:377
unsigned getReg() const
getReg - Returns the register number.
unsigned Reg
const GISelInstProfileBuilder & addNodeIDImmediate(int64_t Imm) const
Definition: CSEInfo.cpp:302
The actual analysis pass wrapper.
Definition: CSEInfo.h:218
block Block Frequency true
void setMF(MachineFunction &MF)
Definition: CSEInfo.cpp:77
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:460
const GISelInstProfileBuilder & addNodeIDRegNum(unsigned Reg) const
Definition: CSEInfo.cpp:308
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
static MachineOperand CreateReg(unsigned 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)
const GISelInstProfileBuilder & addNodeIDFlag(unsigned Flag) const
Definition: CSEInfo.cpp:326
void changingInstr(MachineInstr &MI) override
This instruction is about to be mutated in some way.
Definition: CSEInfo.cpp:222
amdgpu aa AMDGPU Address space based Alias Analysis Wrapper
const GISelInstProfileBuilder & addNodeIDOpcode(unsigned Opc) const
Definition: CSEInfo.cpp:277
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: CSEInfo.cpp:372
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:60
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:410
const GISelInstProfileBuilder & addNodeIDRegType(const LLT &Ty) const
Definition: CSEInfo.cpp:283
void erasingInstr(MachineInstr &MI) override
An instruction is about to be erased.
Definition: CSEInfo.cpp:220
bool isFPImm() const
isFPImm - Tests if this is a MO_FPImmediate operand.
bool isPredicate() const
void releaseMemory()
Definition: CSEInfo.cpp:243
bool shouldCSE(unsigned Opc) const
Definition: CSEInfo.cpp:212
void handleRemoveInst(MachineInstr *MI)
Remove this inst from the CSE map.
Definition: CSEInfo.cpp:197
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:117
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:65
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:267
Represent the analysis usage information of a pass.
void countOpcodeHit(unsigned Opc)
Definition: CSEInfo.cpp:158
GISelCSEInfo & get(std::unique_ptr< CSEConfigBase > CSEOpt, bool ReCompute=false)
Takes a CSEConfigBase object that defines what opcodes get CSEd.
Definition: CSEInfo.cpp:363
bool isValid() const
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
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:175
void recordNewInstruction(MachineInstr *MI)
Records a newly created inst in a list and lazily insert it to the CSEMap.
Definition: CSEInfo.cpp:168
MachineOperand class - Representation of each machine instruction operand.
void analyze(MachineFunction &MF)
Definition: CSEInfo.cpp:229
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:255
Representation of each machine instruction.
Definition: MachineInstr.h:63
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
const GISelInstProfileBuilder & addNodeIDMBB(const MachineBasicBlock *MBB) const
Definition: CSEInfo.cpp:320
bool isReg() const
isReg - Tests if this is a MO_Register operand.
uint16_t getFlags() const
Return the MI flags bitvector.
Definition: MachineInstr.h:291
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:332
void createdInstr(MachineInstr &MI) override
An instruction has been created and inserted into the function.
Definition: CSEInfo.cpp:221
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
#define LLVM_DEBUG(X)
Definition: Debug.h:122
void handleRecordedInsts()
Use this callback to insert all the recorded instructions.
Definition: CSEInfo.cpp:205
const ConstantInt * getCImm() const
bool isImplicit() const
unsigned getPredicate() const