Skip to content

Commit f0dc9fa

Browse files
ramntryramntry
committedMay 21, 2018
[GlobalISel] Improving InstructionSelect's performance by reducing MatchTable, mostly NFC, perf patch 1
This patch starts a series of patches that decrease time spent by GlobalISel in its InstructionSelect pass by roughly 60% for -O0 builds for large inputs as measured on sqlite3-amalgamation (http://sqlite.org/download.html) targeting AArch64. The performance improvements are achieved solely by reducing the number of matching GIM_* opcodes executed by the MatchTable's interpreter during the selection by approx. a factor of 30, which also brings contribution of this particular part of the selection process to the overall runtime of InstructionSelect pass down from approx. 60-70% to 5-7%, thus making further improvements in this particular direction not very profitable. The improvements described above are expected for any target that doesn't have many complex patterns. The targets that do should strictly benefit from the changes, but by how much exactly is hard to estimate beforehand. It's also likely that such target WILL benefit from further improvements to MatchTable, most likely the ones that bring it closer to a perfect decision tree. This commit specifically is rather large mostly NFC commit that does necessary preparation work and refactoring, there will be a following series of small patches introducing a specific optimization each shortly after. This commit specifically is expected to cause a small compile time regression (around 2.5% of InstructionSelect pass time), which should be fixed by the next commit of the series. Every commit planned shares the same Phabricator Review. Reviewers: qcolombet, dsanders, bogner, aemerson, javed.absar Reviewed By: qcolombet Subscribers: rovka, llvm-commits, kristof.beyls Differential Revision: https://reviews.llvm.org/D44700 llvm-svn: 332907
1 parent 0322e3c commit f0dc9fa

File tree

4 files changed

+1251
-1049
lines changed

4 files changed

+1251
-1049
lines changed
 

‎llvm/include/llvm/CodeGen/GlobalISel/InstructionSelector.h

Lines changed: 24 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,7 @@
2020
#include "llvm/ADT/Optional.h"
2121
#include "llvm/ADT/SmallVector.h"
2222
#include "llvm/Support/CodeGenCoverage.h"
23+
#include "llvm/Support/LowLevelTypeImpl.h"
2324
#include <bitset>
2425
#include <cstddef>
2526
#include <cstdint>
@@ -31,7 +32,6 @@ namespace llvm {
3132

3233
class APInt;
3334
class APFloat;
34-
class LLT;
3535
class MachineInstr;
3636
class MachineInstrBuilder;
3737
class MachineFunction;
@@ -146,12 +146,14 @@ enum {
146146
/// - OpIdx - Operand index
147147
/// - Expected register bank (specified as a register class)
148148
GIM_CheckRegBankForClass,
149+
149150
/// Check the operand matches a complex predicate
150151
/// - InsnID - Instruction ID
151152
/// - OpIdx - Operand index
152153
/// - RendererID - The renderer to hold the result
153154
/// - Complex predicate ID
154155
GIM_CheckComplexPattern,
156+
155157
/// Check the operand is a specific integer
156158
/// - InsnID - Instruction ID
157159
/// - OpIdx - Operand index
@@ -168,6 +170,7 @@ enum {
168170
/// - OpIdx - Operand index
169171
/// - Expected Intrinsic ID
170172
GIM_CheckIntrinsicID,
173+
171174
/// Check the specified operand is an MBB
172175
/// - InsnID - Instruction ID
173176
/// - OpIdx - Operand index
@@ -196,6 +199,7 @@ enum {
196199
/// - OldInsnID - Instruction ID to mutate
197200
/// - NewOpcode - The new opcode to use
198201
GIR_MutateOpcode,
202+
199203
/// Build a new instruction
200204
/// - InsnID - Instruction ID to define
201205
/// - Opcode - The new opcode to use
@@ -206,6 +210,7 @@ enum {
206210
/// - OldInsnID - Instruction ID to copy from
207211
/// - OpIdx - The operand to copy
208212
GIR_Copy,
213+
209214
/// Copy an operand to the specified instruction or add a zero register if the
210215
/// operand is a zero immediate.
211216
/// - NewInsnID - Instruction ID to modify
@@ -219,6 +224,7 @@ enum {
219224
/// - OpIdx - The operand to copy
220225
/// - SubRegIdx - The subregister to copy
221226
GIR_CopySubReg,
227+
222228
/// Add an implicit register def to the specified instruction
223229
/// - InsnID - Instruction ID to modify
224230
/// - RegNum - The register to add
@@ -231,11 +237,13 @@ enum {
231237
/// - InsnID - Instruction ID to modify
232238
/// - RegNum - The register to add
233239
GIR_AddRegister,
240+
234241
/// Add a temporary register to the specified instruction
235242
/// - InsnID - Instruction ID to modify
236243
/// - TempRegID - The temporary register ID to add
237244
/// - TempRegFlags - The register flags to set
238245
GIR_AddTempRegister,
246+
239247
/// Add an immediate to the specified instruction
240248
/// - InsnID - Instruction ID to modify
241249
/// - Imm - The immediate to add
@@ -244,6 +252,7 @@ enum {
244252
/// - InsnID - Instruction ID to modify
245253
/// - RendererID - The renderer to call
246254
GIR_ComplexRenderer,
255+
247256
/// Render sub-operands of complex operands to the specified instruction
248257
/// - InsnID - Instruction ID to modify
249258
/// - RendererID - The renderer to call
@@ -272,19 +281,23 @@ enum {
272281
/// - OpIdx - Operand index
273282
/// - RCEnum - Register class enumeration value
274283
GIR_ConstrainOperandRC,
284+
275285
/// Constrain an instructions operands according to the instruction
276286
/// description.
277287
/// - InsnID - Instruction ID to modify
278288
GIR_ConstrainSelectedInstOperands,
289+
279290
/// Merge all memory operands into instruction.
280291
/// - InsnID - Instruction ID to modify
281292
/// - MergeInsnID... - One or more Instruction ID to merge into the result.
282293
/// - GIU_MergeMemOperands_EndOfList - Terminates the list of instructions to
283294
/// merge.
284295
GIR_MergeMemOperands,
296+
285297
/// Erase from parent.
286298
/// - InsnID - Instruction ID to erase
287299
GIR_EraseFromParent,
300+
288301
/// Create a new temporary register that's not constrained.
289302
/// - TempRegID - The temporary register ID to initialize.
290303
/// - Expected type
@@ -297,6 +310,7 @@ enum {
297310
/// - RuleID - The ID of the rule that was covered.
298311
GIR_Coverage,
299312

313+
/// Keeping track of the number of the GI opcodes. Must be the last entry.
300314
GIU_NumOpcodes,
301315
};
302316

@@ -341,6 +355,15 @@ class InstructionSelector {
341355
template <class PredicateBitset, class ComplexMatcherMemFn,
342356
class CustomRendererFn>
343357
struct ISelInfoTy {
358+
ISelInfoTy(const LLT *TypeObjects, size_t NumTypeObjects,
359+
const PredicateBitset *FeatureBitsets,
360+
const ComplexMatcherMemFn *ComplexPredicates,
361+
const CustomRendererFn *CustomRenderers)
362+
: TypeObjects(TypeObjects),
363+
FeatureBitsets(FeatureBitsets),
364+
ComplexPredicates(ComplexPredicates),
365+
CustomRenderers(CustomRenderers) {
366+
}
344367
const LLT *TypeObjects;
345368
const PredicateBitset *FeatureBitsets;
346369
const ComplexMatcherMemFn *ComplexPredicates;

‎llvm/include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

Lines changed: 9 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -53,17 +53,17 @@ bool InstructionSelector::executeMatchTable(
5353
MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI,
5454
const RegisterBankInfo &RBI, const PredicateBitset &AvailableFeatures,
5555
CodeGenCoverage &CoverageInfo) const {
56+
5657
uint64_t CurrentIdx = 0;
57-
SmallVector<uint64_t, 8> OnFailResumeAt;
58+
SmallVector<uint64_t, 4> OnFailResumeAt;
5859

5960
enum RejectAction { RejectAndGiveUp, RejectAndResume };
6061
auto handleReject = [&]() -> RejectAction {
6162
DEBUG_WITH_TYPE(TgtInstructionSelector::getName(),
6263
dbgs() << CurrentIdx << ": Rejected\n");
6364
if (OnFailResumeAt.empty())
6465
return RejectAndGiveUp;
65-
CurrentIdx = OnFailResumeAt.back();
66-
OnFailResumeAt.pop_back();
66+
CurrentIdx = OnFailResumeAt.pop_back_val();
6767
DEBUG_WITH_TYPE(TgtInstructionSelector::getName(),
6868
dbgs() << CurrentIdx << ": Resume at " << CurrentIdx << " ("
6969
<< OnFailResumeAt.size() << " try-blocks remain)\n");
@@ -139,12 +139,13 @@ bool InstructionSelector::executeMatchTable(
139139
int64_t InsnID = MatchTable[CurrentIdx++];
140140
int64_t Expected = MatchTable[CurrentIdx++];
141141

142+
assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
142143
unsigned Opcode = State.MIs[InsnID]->getOpcode();
144+
143145
DEBUG_WITH_TYPE(TgtInstructionSelector::getName(),
144146
dbgs() << CurrentIdx << ": GIM_CheckOpcode(MIs[" << InsnID
145147
<< "], ExpectedOpcode=" << Expected
146148
<< ") // Got=" << Opcode << "\n");
147-
assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
148149
if (Opcode != Expected) {
149150
if (handleReject() == RejectAndGiveUp)
150151
return false;
@@ -197,7 +198,8 @@ bool InstructionSelector::executeMatchTable(
197198
<< CurrentIdx << ": GIM_CheckAPIntImmPredicate(MIs["
198199
<< InsnID << "], Predicate=" << Predicate << ")\n");
199200
assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
200-
assert(State.MIs[InsnID]->getOpcode() && "Expected G_CONSTANT");
201+
assert(State.MIs[InsnID]->getOpcode() == TargetOpcode::G_CONSTANT &&
202+
"Expected G_CONSTANT");
201203
assert(Predicate > GIPFP_APInt_Invalid && "Expected a valid predicate");
202204
APInt Value;
203205
if (State.MIs[InsnID]->getOperand(1).isCImm())
@@ -236,7 +238,6 @@ bool InstructionSelector::executeMatchTable(
236238
dbgs() << CurrentIdx << ": GIM_CheckAtomicOrdering(MIs["
237239
<< InsnID << "], " << (uint64_t)Ordering << ")\n");
238240
assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
239-
240241
if (!State.MIs[InsnID]->hasOneMemOperand())
241242
if (handleReject() == RejectAndGiveUp)
242243
return false;
@@ -255,7 +256,6 @@ bool InstructionSelector::executeMatchTable(
255256
<< ": GIM_CheckAtomicOrderingOrStrongerThan(MIs["
256257
<< InsnID << "], " << (uint64_t)Ordering << ")\n");
257258
assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
258-
259259
if (!State.MIs[InsnID]->hasOneMemOperand())
260260
if (handleReject() == RejectAndGiveUp)
261261
return false;
@@ -274,7 +274,6 @@ bool InstructionSelector::executeMatchTable(
274274
<< ": GIM_CheckAtomicOrderingWeakerThan(MIs["
275275
<< InsnID << "], " << (uint64_t)Ordering << ")\n");
276276
assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
277-
278277
if (!State.MIs[InsnID]->hasOneMemOperand())
279278
if (handleReject() == RejectAndGiveUp)
280279
return false;
@@ -375,7 +374,6 @@ bool InstructionSelector::executeMatchTable(
375374
<< "]->getOperand(" << OpIdx
376375
<< "), TypeID=" << TypeID << ")\n");
377376
assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
378-
379377
MachineOperand &MO = State.MIs[InsnID]->getOperand(OpIdx);
380378
if (!MO.isReg() ||
381379
MRI.getType(MO.getReg()) != ISelInfo.TypeObjects[TypeID]) {
@@ -394,7 +392,6 @@ bool InstructionSelector::executeMatchTable(
394392
<< InsnID << "]->getOperand(" << OpIdx
395393
<< "), SizeInBits=" << SizeInBits << ")\n");
396394
assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
397-
398395
// iPTR must be looked up in the target.
399396
if (SizeInBits == 0) {
400397
MachineFunction *MF = State.MIs[InsnID]->getParent()->getParent();
@@ -466,7 +463,6 @@ bool InstructionSelector::executeMatchTable(
466463
<< InsnID << "]->getOperand(" << OpIdx
467464
<< "), Value=" << Value << ")\n");
468465
assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
469-
470466
MachineOperand &MO = State.MIs[InsnID]->getOperand(OpIdx);
471467
if (MO.isReg()) {
472468
// isOperandImmEqual() will sign-extend to 64-bits, so should we.
@@ -562,7 +558,7 @@ bool InstructionSelector::executeMatchTable(
562558
}
563559
case GIM_Reject:
564560
DEBUG_WITH_TYPE(TgtInstructionSelector::getName(),
565-
dbgs() << CurrentIdx << ": GIM_Reject");
561+
dbgs() << CurrentIdx << ": GIM_Reject\n");
566562
if (handleReject() == RejectAndGiveUp)
567563
return false;
568564
break;
@@ -854,7 +850,7 @@ bool InstructionSelector::executeMatchTable(
854850

855851
case GIR_Done:
856852
DEBUG_WITH_TYPE(TgtInstructionSelector::getName(),
857-
dbgs() << CurrentIdx << ": GIR_Done");
853+
dbgs() << CurrentIdx << ": GIR_Done\n");
858854
return true;
859855

860856
default:

‎llvm/test/TableGen/GlobalISelEmitter.td

Lines changed: 658 additions & 730 deletions
Large diffs are not rendered by default.

‎llvm/utils/TableGen/GlobalISelEmitter.cpp

Lines changed: 560 additions & 305 deletions
Large diffs are not rendered by default.

0 commit comments

Comments
 (0)
Please sign in to comment.