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