Skip to content

Commit bece442

Browse files
author
Quentin Colombet
committedMay 27, 2017
[GlobalISel] Add a localizer pass for target to use
This reverts commit r299287 plus clean-ups. The localizer pass is a helper pass that could be run at O0 in the GISel pipeline to work around the deficiency of the fast register allocator. It basically shortens the live-ranges of the constants so that the allocator does not spill all over the place. Long term fix would be to make the greedy allocator fast. llvm-svn: 304051
·
llvmorg-21-initllvmorg-5.0.0-rc1
1 parent 5bbb5aa commit bece442

File tree

7 files changed

+523
-0
lines changed

7 files changed

+523
-0
lines changed
 

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

+78
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
//== llvm/CodeGen/GlobalISel/Localizer.h - Localizer -------------*- 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 This file describes the interface of the Localizer pass.
11+
/// This pass moves/duplicates constant-like instructions close to their uses.
12+
/// Its primarily goal is to workaround the deficiencies of the fast register
13+
/// allocator.
14+
/// With GlobalISel constants are all materialized in the entry block of
15+
/// a function. However, the fast allocator cannot rematerialize constants and
16+
/// has a lot more live-ranges to deal with and will most likely end up
17+
/// spilling a lot.
18+
/// By pushing the constants close to their use, we only create small
19+
/// live-ranges.
20+
//===----------------------------------------------------------------------===//
21+
22+
#ifndef LLVM_CODEGEN_GLOBALISEL_LOCALIZER_H
23+
#define LLVM_CODEGEN_GLOBALISEL_LOCALIZER_H
24+
25+
#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
26+
#include "llvm/CodeGen/MachineFunctionPass.h"
27+
28+
namespace llvm {
29+
// Forward declarations.
30+
class MachineRegisterInfo;
31+
32+
/// This pass implements the localization mechanism described at the
33+
/// top of this file. One specificity of the implementation is that
34+
/// it will materialize one and only one instance of a constant per
35+
/// basic block, thus enabling reuse of that constant within that block.
36+
/// Moreover, it only materializes constants in blocks where they
37+
/// are used. PHI uses are considered happening at the end of the
38+
/// related predecessor.
39+
class Localizer : public MachineFunctionPass {
40+
public:
41+
static char ID;
42+
43+
private:
44+
/// MRI contains all the register class/bank information that this
45+
/// pass uses and updates.
46+
MachineRegisterInfo *MRI;
47+
48+
/// Check whether or not \p MI needs to be moved close to its uses.
49+
static bool shouldLocalize(const MachineInstr &MI);
50+
51+
/// Check if \p MOUse is used in the same basic block as \p Def.
52+
/// If the use is in the same block, we say it is local.
53+
/// When the use is not local, \p InsertMBB will contain the basic
54+
/// block when to insert \p Def to have a local use.
55+
static bool isLocalUse(MachineOperand &MOUse, const MachineInstr &Def,
56+
MachineBasicBlock *&InsertMBB);
57+
58+
/// Initialize the field members using \p MF.
59+
void init(MachineFunction &MF);
60+
61+
public:
62+
Localizer();
63+
64+
StringRef getPassName() const override { return "Localizer"; }
65+
66+
MachineFunctionProperties getRequiredProperties() const override {
67+
return MachineFunctionProperties()
68+
.set(MachineFunctionProperties::Property::IsSSA)
69+
.set(MachineFunctionProperties::Property::Legalized)
70+
.set(MachineFunctionProperties::Property::RegBankSelected);
71+
}
72+
73+
bool runOnMachineFunction(MachineFunction &MF) override;
74+
};
75+
76+
} // End namespace llvm.
77+
78+
#endif

‎llvm/include/llvm/CodeGen/MachineRegisterInfo.h

+5
Original file line numberDiff line numberDiff line change
@@ -642,6 +642,11 @@ class MachineRegisterInfo {
642642
///
643643
void setRegBank(unsigned Reg, const RegisterBank &RegBank);
644644

645+
void setRegClassOrRegBank(unsigned Reg,
646+
const RegClassOrRegBank &RCOrRB){
647+
VRegInfo[Reg].first = RCOrRB;
648+
}
649+
645650
/// constrainRegClass - Constrain the register class of the specified virtual
646651
/// register to be a common subclass of RC and the current register class,
647652
/// but only if the new class has at least MinNumRegs registers. Return the

‎llvm/include/llvm/InitializePasses.h

+1
Original file line numberDiff line numberDiff line change
@@ -194,6 +194,7 @@ void initializeLiveVariablesPass(PassRegistry&);
194194
void initializeLoadCombinePass(PassRegistry&);
195195
void initializeLoadStoreVectorizerPass(PassRegistry&);
196196
void initializeLoaderPassPass(PassRegistry&);
197+
void initializeLocalizerPass(PassRegistry&);
197198
void initializeLocalStackSlotPassPass(PassRegistry&);
198199
void initializeLoopAccessLegacyAnalysisPass(PassRegistry&);
199200
void initializeLoopDataPrefetchLegacyPassPass(PassRegistry&);

‎llvm/lib/CodeGen/GlobalISel/CMakeLists.txt

+1
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@ set(GLOBAL_ISEL_FILES
88
LegalizerHelper.cpp
99
Legalizer.cpp
1010
LegalizerInfo.cpp
11+
Localizer.cpp
1112
RegBankSelect.cpp
1213
RegisterBank.cpp
1314
RegisterBankInfo.cpp

‎llvm/lib/CodeGen/GlobalISel/GlobalISel.cpp

+1
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,7 @@ void llvm::initializeGlobalISel(PassRegistry &Registry) {
2626
void llvm::initializeGlobalISel(PassRegistry &Registry) {
2727
initializeIRTranslatorPass(Registry);
2828
initializeLegalizerPass(Registry);
29+
initializeLocalizerPass(Registry);
2930
initializeRegBankSelectPass(Registry);
3031
initializeInstructionSelectPass(Registry);
3132
}

‎llvm/lib/CodeGen/GlobalISel/Localizer.cpp

+125
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,125 @@
1+
//===- Localizer.cpp ---------------------- Localize some instrs -*- 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+
/// \file
10+
/// This file implements the Localizer class.
11+
//===----------------------------------------------------------------------===//
12+
13+
#include "llvm/CodeGen/GlobalISel/Localizer.h"
14+
#include "llvm/ADT/DenseMap.h"
15+
#include "llvm/ADT/SmallPtrSet.h"
16+
#include "llvm/CodeGen/MachineRegisterInfo.h"
17+
#include "llvm/Support/Debug.h"
18+
19+
#define DEBUG_TYPE "localizer"
20+
21+
using namespace llvm;
22+
23+
char Localizer::ID = 0;
24+
INITIALIZE_PASS(Localizer, DEBUG_TYPE,
25+
"Move/duplicate certain instructions close to their use", false,
26+
false);
27+
28+
Localizer::Localizer() : MachineFunctionPass(ID) {
29+
initializeLocalizerPass(*PassRegistry::getPassRegistry());
30+
}
31+
32+
void Localizer::init(MachineFunction &MF) { MRI = &MF.getRegInfo(); }
33+
34+
bool Localizer::shouldLocalize(const MachineInstr &MI) {
35+
switch (MI.getOpcode()) {
36+
default:
37+
return false;
38+
// Constants-like instructions should be close to their users.
39+
// We don't want long live-ranges for them.
40+
case TargetOpcode::G_CONSTANT:
41+
case TargetOpcode::G_FCONSTANT:
42+
case TargetOpcode::G_FRAME_INDEX:
43+
return true;
44+
}
45+
}
46+
47+
bool Localizer::isLocalUse(MachineOperand &MOUse, const MachineInstr &Def,
48+
MachineBasicBlock *&InsertMBB) {
49+
MachineInstr &MIUse = *MOUse.getParent();
50+
InsertMBB = MIUse.getParent();
51+
if (MIUse.isPHI())
52+
InsertMBB = MIUse.getOperand(MIUse.getOperandNo(&MOUse) + 1).getMBB();
53+
return InsertMBB == Def.getParent();
54+
}
55+
56+
bool Localizer::runOnMachineFunction(MachineFunction &MF) {
57+
// If the ISel pipeline failed, do not bother running that pass.
58+
if (MF.getProperties().hasProperty(
59+
MachineFunctionProperties::Property::FailedISel))
60+
return false;
61+
62+
DEBUG(dbgs() << "Localize instructions for: " << MF.getName() << '\n');
63+
64+
init(MF);
65+
66+
bool Changed = false;
67+
// Keep track of the instructions we localized.
68+
// We won't need to process them if we see them later in the CFG.
69+
SmallPtrSet<MachineInstr *, 16> LocalizedInstrs;
70+
DenseMap<std::pair<MachineBasicBlock *, unsigned>, unsigned> MBBWithLocalDef;
71+
// TODO: Do bottom up traversal.
72+
for (MachineBasicBlock &MBB : MF) {
73+
for (MachineInstr &MI : MBB) {
74+
if (LocalizedInstrs.count(&MI) || !shouldLocalize(MI))
75+
continue;
76+
DEBUG(dbgs() << "Should localize: " << MI);
77+
assert(MI.getDesc().getNumDefs() == 1 &&
78+
"More than one definition not supported yet");
79+
unsigned Reg = MI.getOperand(0).getReg();
80+
// Check if all the users of MI are local.
81+
// We are going to invalidation the list of use operands, so we
82+
// can't use range iterator.
83+
for (auto MOIt = MRI->use_begin(Reg), MOItEnd = MRI->use_end();
84+
MOIt != MOItEnd;) {
85+
MachineOperand &MOUse = *MOIt++;
86+
// Check if the use is already local.
87+
MachineBasicBlock *InsertMBB;
88+
DEBUG(MachineInstr &MIUse = *MOUse.getParent();
89+
dbgs() << "Checking use: " << MIUse
90+
<< " #Opd: " << MIUse.getOperandNo(&MOUse) << '\n');
91+
if (isLocalUse(MOUse, MI, InsertMBB))
92+
continue;
93+
DEBUG(dbgs() << "Fixing non-local use\n");
94+
Changed = true;
95+
auto MBBAndReg = std::make_pair(InsertMBB, Reg);
96+
auto NewVRegIt = MBBWithLocalDef.find(MBBAndReg);
97+
if (NewVRegIt == MBBWithLocalDef.end()) {
98+
// Create the localized instruction.
99+
MachineInstr *LocalizedMI = MF.CloneMachineInstr(&MI);
100+
LocalizedInstrs.insert(LocalizedMI);
101+
// Move it at the right place.
102+
MachineInstr &MIUse = *MOUse.getParent();
103+
if (MIUse.getParent() == InsertMBB)
104+
InsertMBB->insert(MIUse, LocalizedMI);
105+
else
106+
InsertMBB->insert(InsertMBB->getFirstNonPHI(), LocalizedMI);
107+
108+
// Set a new register for the definition.
109+
unsigned NewReg =
110+
MRI->createGenericVirtualRegister(MRI->getType(Reg));
111+
MRI->setRegClassOrRegBank(NewReg, MRI->getRegClassOrRegBank(Reg));
112+
LocalizedMI->getOperand(0).setReg(NewReg);
113+
NewVRegIt =
114+
MBBWithLocalDef.insert(std::make_pair(MBBAndReg, NewReg)).first;
115+
DEBUG(dbgs() << "Inserted: " << *LocalizedMI);
116+
}
117+
DEBUG(dbgs() << "Update use with: " << PrintReg(NewVRegIt->second)
118+
<< '\n');
119+
// Update the user reg.
120+
MOUse.setReg(NewVRegIt->second);
121+
}
122+
}
123+
}
124+
return Changed;
125+
}

‎llvm/test/CodeGen/AArch64/GlobalISel/localizer.mir

+312
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,312 @@
1+
# RUN: llc -O0 -mtriple=aarch64-apple-ios -run-pass=localizer -verify-machineinstrs -global-isel %s -o - | FileCheck %s -check-prefix=CHECK
2+
3+
# Test the localizer.
4+
5+
--- |
6+
target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
7+
8+
define void @local_use() { ret void }
9+
define void @non_local_1use() { ret void }
10+
define void @non_local_2uses() { ret void }
11+
define void @non_local_phi_use() { ret void }
12+
define void @non_local_phi_use_followed_by_use() { ret void }
13+
define void @non_local_phi_use_followed_by_use_fi() { ret void }
14+
define void @float_non_local_phi_use_followed_by_use_fi() { ret void }
15+
...
16+
17+
---
18+
# CHECK-LABEL: name: local_use
19+
name: local_use
20+
legalized: true
21+
regBankSelected: true
22+
23+
# CHECK: registers:
24+
registers:
25+
- { id: 0, class: gpr }
26+
- { id: 1, class: gpr }
27+
- { id: 2, class: gpr }
28+
29+
# CHECK: body:
30+
# CHECK: %0(s32) = G_CONSTANT 1
31+
# CHECK-NEXT: %1(s32) = G_ADD %0, %0
32+
body: |
33+
bb.0:
34+
%0(s32) = G_CONSTANT 1
35+
%1(s32) = G_ADD %0, %0
36+
...
37+
38+
---
39+
# CHECK-LABEL: name: non_local_1use
40+
name: non_local_1use
41+
legalized: true
42+
regBankSelected: true
43+
44+
# CHECK: registers:
45+
# Existing registers should be left untouched
46+
# CHECK: - { id: 0, class: gpr }
47+
#CHECK-NEXT: - { id: 1, class: gpr }
48+
#CHECK-NEXT: - { id: 2, class: gpr }
49+
# The newly created reg should be on the same regbank/regclass as its origin.
50+
#CHECK-NEXT: - { id: 3, class: gpr }
51+
52+
registers:
53+
- { id: 0, class: gpr }
54+
- { id: 1, class: gpr }
55+
- { id: 2, class: gpr }
56+
57+
# CHECK: body:
58+
# CHECK: %0(s32) = G_CONSTANT 1
59+
# CHECK-NEXT: %1(s32) = G_ADD %0, %0
60+
61+
# CHECK: bb.1:
62+
# CHECK: %3(s32) = G_CONSTANT 1
63+
# CHECK-NEXT: %2(s32) = G_ADD %3, %1
64+
body: |
65+
bb.0:
66+
successors: %bb.1
67+
68+
%0(s32) = G_CONSTANT 1
69+
%1(s32) = G_ADD %0, %0
70+
71+
bb.1:
72+
%2(s32) = G_ADD %0, %1
73+
...
74+
75+
76+
---
77+
# CHECK-LABEL: name: non_local_2uses
78+
name: non_local_2uses
79+
legalized: true
80+
regBankSelected: true
81+
82+
# CHECK: registers:
83+
# Existing registers should be left untouched
84+
# CHECK: - { id: 0, class: gpr }
85+
#CHECK-NEXT: - { id: 1, class: gpr }
86+
#CHECK-NEXT: - { id: 2, class: gpr }
87+
# The newly created reg should be on the same regbank/regclass as its origin.
88+
#CHECK-NEXT: - { id: 3, class: gpr }
89+
90+
registers:
91+
- { id: 0, class: gpr }
92+
- { id: 1, class: gpr }
93+
- { id: 2, class: gpr }
94+
95+
# CHECK: body:
96+
# CHECK: %0(s32) = G_CONSTANT 1
97+
# CHECK-NEXT: %1(s32) = G_ADD %0, %0
98+
99+
# CHECK: bb.1:
100+
# CHECK: %3(s32) = G_CONSTANT 1
101+
# CHECK-NEXT: %2(s32) = G_ADD %3, %3
102+
body: |
103+
bb.0:
104+
successors: %bb.1
105+
106+
%0(s32) = G_CONSTANT 1
107+
%1(s32) = G_ADD %0, %0
108+
109+
bb.1:
110+
%2(s32) = G_ADD %0, %0
111+
...
112+
113+
---
114+
# CHECK-LABEL: name: non_local_phi_use
115+
name: non_local_phi_use
116+
legalized: true
117+
regBankSelected: true
118+
tracksRegLiveness: true
119+
120+
# CHECK: registers:
121+
# Existing registers should be left untouched
122+
# CHECK: - { id: 0, class: gpr }
123+
#CHECK-NEXT: - { id: 1, class: gpr }
124+
#CHECK-NEXT: - { id: 2, class: gpr }
125+
#CHECK-NEXT: - { id: 3, class: gpr }
126+
#CHECK-NEXT: - { id: 4, class: gpr }
127+
# The newly created reg should be on the same regbank/regclass as its origin.
128+
#CHECK-NEXT: - { id: 5, class: gpr }
129+
130+
registers:
131+
- { id: 0, class: gpr }
132+
- { id: 1, class: gpr }
133+
- { id: 2, class: gpr }
134+
- { id: 3, class: gpr }
135+
- { id: 4, class: gpr }
136+
137+
# CHECK: body:
138+
# CHECK: %0(s32) = G_CONSTANT 1
139+
# CHECK-NEXT: %1(s32) = G_ADD %0, %0
140+
141+
# CHECK: bb.1:
142+
# CHECK: %5(s32) = G_CONSTANT 1
143+
144+
# CHECK: bb.2:
145+
# CHECK: %3(s32) = PHI %5(s32), %bb.1
146+
body: |
147+
bb.0:
148+
successors: %bb.1
149+
150+
%0(s32) = G_CONSTANT 1
151+
%1(s32) = G_ADD %0, %0
152+
153+
bb.1:
154+
successors: %bb.2
155+
156+
bb.2:
157+
%3(s32) = PHI %0(s32), %bb.1
158+
%2(s32) = G_ADD %3, %3
159+
...
160+
161+
---
162+
# CHECK-LABEL: name: non_local_phi_use_followed_by_use
163+
name: non_local_phi_use_followed_by_use
164+
legalized: true
165+
regBankSelected: true
166+
tracksRegLiveness: true
167+
168+
# CHECK: registers:
169+
# Existing registers should be left untouched
170+
# CHECK: - { id: 0, class: gpr }
171+
#CHECK-NEXT: - { id: 1, class: gpr }
172+
#CHECK-NEXT: - { id: 2, class: gpr }
173+
#CHECK-NEXT: - { id: 3, class: gpr }
174+
#CHECK-NEXT: - { id: 4, class: gpr }
175+
# The newly created regs should be on the same regbank/regclass as its origin.
176+
#CHECK-NEXT: - { id: 5, class: gpr }
177+
#CHECK-NEXT: - { id: 6, class: gpr }
178+
179+
registers:
180+
- { id: 0, class: gpr }
181+
- { id: 1, class: gpr }
182+
- { id: 2, class: gpr }
183+
- { id: 3, class: gpr }
184+
- { id: 4, class: gpr }
185+
186+
# CHECK: body:
187+
# CHECK: %0(s32) = G_CONSTANT 1
188+
# CHECK-NEXT: %1(s32) = G_ADD %0, %0
189+
190+
# CHECK: bb.1:
191+
# CHECK: %5(s32) = G_CONSTANT 1
192+
193+
# CHECK: bb.2:
194+
# CHECK: %3(s32) = PHI %5(s32), %bb.1
195+
# CHECK-NEXT: %6(s32) = G_CONSTANT 1
196+
# CHECK-NEXT: %2(s32) = G_ADD %3, %6
197+
body: |
198+
bb.0:
199+
successors: %bb.1
200+
201+
%0(s32) = G_CONSTANT 1
202+
%1(s32) = G_ADD %0, %0
203+
204+
bb.1:
205+
successors: %bb.2
206+
207+
bb.2:
208+
%3(s32) = PHI %0(s32), %bb.1
209+
%2(s32) = G_ADD %3, %0
210+
...
211+
212+
---
213+
# CHECK-LABEL: name: non_local_phi_use_followed_by_use_fi
214+
name: non_local_phi_use_followed_by_use_fi
215+
legalized: true
216+
regBankSelected: true
217+
tracksRegLiveness: true
218+
219+
# CHECK: registers:
220+
# Existing registers should be left untouched
221+
# CHECK: - { id: 0, class: gpr }
222+
#CHECK-NEXT: - { id: 1, class: gpr }
223+
#CHECK-NEXT: - { id: 2, class: gpr }
224+
#CHECK-NEXT: - { id: 3, class: gpr }
225+
#CHECK-NEXT: - { id: 4, class: gpr }
226+
# The newly created reg should be on the same regbank/regclass as its origin.
227+
#CHECK-NEXT: - { id: 5, class: gpr }
228+
#CHECK-NEXT: - { id: 6, class: gpr }
229+
230+
registers:
231+
- { id: 0, class: gpr }
232+
- { id: 1, class: gpr }
233+
- { id: 2, class: gpr }
234+
- { id: 3, class: gpr }
235+
- { id: 4, class: gpr }
236+
237+
# CHECK: body:
238+
# CHECK: %0(s32) = G_FRAME_INDEX 1
239+
# CHECK-NEXT: %1(s32) = G_ADD %0, %0
240+
241+
# CHECK: bb.1:
242+
# CHECK: %5(s32) = G_FRAME_INDEX 1
243+
244+
# CHECK: bb.2:
245+
# CHECK: %3(s32) = PHI %5(s32), %bb.1
246+
# CHECK-NEXT: %6(s32) = G_FRAME_INDEX 1
247+
# CHECK-NEXT: %2(s32) = G_ADD %3, %6
248+
body: |
249+
bb.0:
250+
successors: %bb.1
251+
252+
%0(s32) = G_FRAME_INDEX 1
253+
%1(s32) = G_ADD %0, %0
254+
255+
bb.1:
256+
successors: %bb.2
257+
258+
bb.2:
259+
%3(s32) = PHI %0(s32), %bb.1
260+
%2(s32) = G_ADD %3, %0
261+
...
262+
263+
---
264+
# CHECK-LABEL: name: float_non_local_phi_use_followed_by_use_fi
265+
name: float_non_local_phi_use_followed_by_use_fi
266+
legalized: true
267+
regBankSelected: true
268+
tracksRegLiveness: true
269+
270+
# CHECK: registers:
271+
# Existing registers should be left untouched
272+
# CHECK: - { id: 0, class: fpr }
273+
#CHECK-NEXT: - { id: 1, class: fpr }
274+
#CHECK-NEXT: - { id: 2, class: fpr }
275+
#CHECK-NEXT: - { id: 3, class: fpr }
276+
#CHECK-NEXT: - { id: 4, class: fpr }
277+
# The newly created reg should be on the same regbank/regclass as its origin.
278+
#CHECK-NEXT: - { id: 5, class: fpr }
279+
#CHECK-NEXT: - { id: 6, class: fpr }
280+
281+
registers:
282+
- { id: 0, class: fpr }
283+
- { id: 1, class: fpr }
284+
- { id: 2, class: fpr }
285+
- { id: 3, class: fpr }
286+
- { id: 4, class: fpr }
287+
288+
# CHECK: body:
289+
# CHECK: %0(s32) = G_FCONSTANT float 1.0
290+
# CHECK-NEXT: %1(s32) = G_FADD %0, %0
291+
292+
# CHECK: bb.1:
293+
# CHECK: %5(s32) = G_FCONSTANT float 1.0
294+
295+
# CHECK: bb.2:
296+
# CHECK: %3(s32) = PHI %5(s32), %bb.1
297+
# CHECK-NEXT: %6(s32) = G_FCONSTANT float 1.0
298+
# CHECK-NEXT: %2(s32) = G_FADD %3, %6
299+
body: |
300+
bb.0:
301+
successors: %bb.1
302+
303+
%0(s32) = G_FCONSTANT float 1.0
304+
%1(s32) = G_FADD %0, %0
305+
306+
bb.1:
307+
successors: %bb.2
308+
309+
bb.2:
310+
%3(s32) = PHI %0(s32), %bb.1
311+
%2(s32) = G_FADD %3, %0
312+
...

0 commit comments

Comments
 (0)
Please sign in to comment.