Skip to content

Commit 8e8e85c

Browse files
author
Quentin Colombet
committedApr 5, 2016
[GlobalISel] Add the skeleton of the RegBankSelect pass.
This pass is reponsible for assigning the generic virtual registers to register banks. llvm-svn: 265440
1 parent e585b5c commit 8e8e85c

File tree

5 files changed

+146
-0
lines changed

5 files changed

+146
-0
lines changed
 

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

Lines changed: 111 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,111 @@
1+
//== llvm/CodeGen/GlobalISel/RegBankSelect.h - Reg Bank Selector -*- 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 MachineFunctionPass
11+
/// responsible for assigning the generic virtual registers to register bank.
12+
13+
/// By default, the reg bank selector relies on local decisions to
14+
/// assign the register bank. In other words, it looks at one instruction
15+
/// at a time to decide where the operand of that instruction should live.
16+
///
17+
/// At higher optimization level, we could imagine that the reg bank selector
18+
/// would use more global analysis and do crazier thing like duplicating
19+
/// instructions and so on. This is future work.
20+
///
21+
/// For now, the pass uses a greedy algorithm to decide where the operand
22+
/// of an instruction should live. It asks the target which banks may be
23+
/// used for each operand of the instruction and what is the cost. Then,
24+
/// it chooses the solution which minimize the cost of the instruction plus
25+
/// the cost of any move that may be needed to to the values into the right
26+
/// register bank.
27+
/// In other words, the cost for an instruction on a register bank RegBank
28+
/// is: Cost of I on RegBank plus the sum of the cost for bringing the
29+
/// input operands from their current register bank to RegBank.
30+
/// Thus, the following formula:
31+
/// cost(I, RegBank) = cost(I.Opcode, RegBank) +
32+
/// sum(for each arg in I.arguments: costCrossCopy(arg.RegBank, RegBank))
33+
///
34+
/// E.g., Let say we are assigning the register bank for the instruction
35+
/// defining v2.
36+
/// v0(A_REGBANK) = ...
37+
/// v1(A_REGBANK) = ...
38+
/// v2 = G_ADD i32 v0, v1 <-- MI
39+
///
40+
/// The target may say it can generate G_ADD i32 on register bank A and B
41+
/// with a cost of respectively 5 and 1.
42+
/// Then, let say the cost of a cross register bank copies from A to B is 1.
43+
/// The reg bank selector would compare the following two costs:
44+
/// cost(MI, A_REGBANK) = cost(G_ADD, A_REGBANK) + cost(v0.RegBank, A_REGBANK) +
45+
/// cost(v1.RegBank, A_REGBANK)
46+
/// = 5 + cost(A_REGBANK, A_REGBANK) + cost(A_REGBANK,
47+
/// A_REGBANK)
48+
/// = 5 + 0 + 0 = 5
49+
/// cost(MI, B_REGBANK) = cost(G_ADD, B_REGBANK) + cost(v0.RegBank, B_REGBANK) +
50+
/// cost(v1.RegBank, B_REGBANK)
51+
/// = 1 + cost(A_REGBANK, B_REGBANK) + cost(A_REGBANK,
52+
/// B_REGBANK)
53+
/// = 1 + 1 + 1 = 3
54+
/// Therefore, in this specific example, the reg bank selector would choose
55+
/// bank B for MI.
56+
/// v0(A_REGBANK) = ...
57+
/// v1(A_REGBANK) = ...
58+
/// tmp0(B_REGBANK) = COPY v0
59+
/// tmp1(B_REGBANK) = COPY v1
60+
/// v2(B_REGBANK) = G_ADD i32 tmp0, tmp1
61+
//
62+
//===----------------------------------------------------------------------===//
63+
64+
#ifndef LLVM_CODEGEN_GLOBALISEL_REGBANKSELECT_H
65+
#define LLVM_CODEGEN_GLOBALISEL_REGBANKSELECT_H
66+
67+
#include "llvm/CodeGen/MachineFunctionPass.h"
68+
69+
namespace llvm {
70+
// Forward declarations.
71+
class RegisterBankInfo;
72+
73+
/// This pass implements the reg bank selector pass used in the GlobalISel
74+
/// pipeline. At the end of this pass, all register operands have been assigned
75+
class RegBankSelect : public MachineFunctionPass {
76+
public:
77+
static char ID;
78+
79+
private:
80+
/// Interface to the target lowering info related
81+
/// to register banks.
82+
const RegisterBankInfo *RBI;
83+
84+
public:
85+
// Ctor, nothing fancy.
86+
RegBankSelect();
87+
88+
const char *getPassName() const override {
89+
return "RegBankSelect";
90+
}
91+
92+
// Simplified algo:
93+
// RBI = MF.subtarget.getRegBankInfo()
94+
// MIRBuilder.reset(MF)
95+
// for each bb in MF
96+
// for each inst in bb
97+
// MappingCosts = RBI.getMapping(inst);
98+
// Idx = findIdxOfMinCost(MappingCosts)
99+
// CurRegBank = MappingCosts[Idx].RegBank
100+
// MRI.setRegBank(inst.getOperand(0).getReg(), CurRegBank)
101+
// for each argument in inst
102+
// if (CurRegBank != argument.RegBank)
103+
// ArgReg = argument.getReg()
104+
// Tmp = MRI.createNewVirtual(MRI.getSize(ArgReg), CurRegBank)
105+
// MIRBuilder.buildInstr(COPY, Tmp, ArgReg)
106+
// inst.getOperand(argument.getOperandNo()).setReg(Tmp)
107+
bool runOnMachineFunction(MachineFunction &MF) override;
108+
};
109+
} // End namespace llvm.
110+
111+
#endif

‎llvm/include/llvm/InitializePasses.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -249,6 +249,7 @@ void initializeProcessImplicitDefsPass(PassRegistry&);
249249
void initializePromotePassPass(PassRegistry&);
250250
void initializePruneEHPass(PassRegistry&);
251251
void initializeReassociatePass(PassRegistry&);
252+
void initializeRegBankSelectPass(PassRegistry &);
252253
void initializeRegToMemPass(PassRegistry&);
253254
void initializeRegionInfoPassPass(PassRegistry&);
254255
void initializeRegionOnlyPrinterPass(PassRegistry&);

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

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@
22
set(GLOBAL_ISEL_FILES
33
IRTranslator.cpp
44
MachineIRBuilder.cpp
5+
RegBankSelect.cpp
56
)
67

78
# Add GlobalISel files to the dependencies if the user wants to build it.

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

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -25,5 +25,6 @@ void llvm::initializeGlobalISel(PassRegistry &Registry) {
2525

2626
void llvm::initializeGlobalISel(PassRegistry &Registry) {
2727
initializeIRTranslatorPass(Registry);
28+
initializeRegBankSelectPass(Registry);
2829
}
2930
#endif // LLVM_BUILD_GLOBAL_ISEL

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

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
//===- llvm/CodeGen/GlobalISel/RegBankSelect.cpp - RegBankSelect -*- 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 RegBankSelect class.
11+
//===----------------------------------------------------------------------===//
12+
13+
#include "llvm/CodeGen/GlobalISel/RegBankSelect.h"
14+
15+
#define DEBUG_TYPE "regbankselect"
16+
17+
using namespace llvm;
18+
19+
char RegBankSelect::ID = 0;
20+
INITIALIZE_PASS(RegBankSelect, "regbankselect",
21+
"Assign register bank of generic virtual registers",
22+
false, false);
23+
24+
RegBankSelect::RegBankSelect() : MachineFunctionPass(ID), RBI(nullptr) {
25+
initializeRegBankSelectPass(*PassRegistry::getPassRegistry());
26+
}
27+
28+
bool RegBankSelect::runOnMachineFunction(MachineFunction &MF) {
29+
// Avoid unused field member warning.
30+
(void)RBI;
31+
return false;
32+
}

0 commit comments

Comments
 (0)
Please sign in to comment.