Mercurial > hg > CbC > CbC_llvm

comparison lib/Target/Lanai/LanaiMemAluCombiner.cpp @ 120:1172e4bd9c6f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update 4.0.0
author mir3636
date Fri, 25 Nov 2016 19:14:25 +0900
parents
children 3a76565eade5
comparison
equal deleted inserted replaced
101:34baf5011add 120:1172e4bd9c6f
1 //===-- LanaiMemAluCombiner.cpp - Pass to combine memory & ALU operations -===//
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 // Simple pass to combine memory and ALU operations
10 //
11 // The Lanai ISA supports instructions where a load/store modifies the base
12 // register used in the load/store operation. This pass finds suitable
13 // load/store and ALU instructions and combines them into one instruction.
14 //
15 // For example,
16 // ld [ %r6 -- ], %r12
17 // is a supported instruction that is not currently generated by the instruction
18 // selection pass of this backend. This pass generates these instructions by
19 // merging
20 // add %r6, -4, %r6
21 // followed by
22 // ld [ %r6 ], %r12
23 // in the same machine basic block into one machine instruction.
24 //===----------------------------------------------------------------------===//
25
26 #include "Lanai.h"
27 #include "LanaiTargetMachine.h"
28 #include "llvm/ADT/SmallSet.h"
29 #include "llvm/ADT/Statistic.h"
30 #include "llvm/CodeGen/MachineFunctionPass.h"
31 #include "llvm/CodeGen/MachineInstrBuilder.h"
32 #include "llvm/CodeGen/RegisterScavenging.h"
33 #include "llvm/Support/CommandLine.h"
34 #include "llvm/Target/TargetInstrInfo.h"
35 using namespace llvm;
36
37 #define GET_INSTRMAP_INFO
38 #include "LanaiGenInstrInfo.inc"
39
40 #define DEBUG_TYPE "lanai-mem-alu-combiner"
41
42 STATISTIC(NumLdStAluCombined, "Number of memory and ALU instructions combined");
43
44 static llvm::cl::opt<bool> DisableMemAluCombiner(
45 "disable-lanai-mem-alu-combiner", llvm::cl::init(false),
46 llvm::cl::desc("Do not combine ALU and memory operators"),
47 llvm::cl::Hidden);
48
49 namespace llvm {
50 void initializeLanaiMemAluCombinerPass(PassRegistry &);
51 } // namespace llvm
52
53 namespace {
54 typedef MachineBasicBlock::iterator MbbIterator;
55 typedef MachineFunction::iterator MfIterator;
56
57 class LanaiMemAluCombiner : public MachineFunctionPass {
58 public:
59 static char ID;
60 explicit LanaiMemAluCombiner() : MachineFunctionPass(ID) {
61 initializeLanaiMemAluCombinerPass(*PassRegistry::getPassRegistry());
62 }
63
64 StringRef getPassName() const override {
65 return "Lanai load / store optimization pass";
66 }
67
68 bool runOnMachineFunction(MachineFunction &F) override;
69
70 MachineFunctionProperties getRequiredProperties() const override {
71 return MachineFunctionProperties().set(
72 MachineFunctionProperties::Property::NoVRegs);
73 }
74
75 private:
76 MbbIterator findClosestSuitableAluInstr(MachineBasicBlock *BB,
77 const MbbIterator &MemInstr,
78 bool Decrement);
79 void insertMergedInstruction(MachineBasicBlock *BB,
80 const MbbIterator &MemInstr,
81 const MbbIterator &AluInstr, bool Before);
82 bool combineMemAluInBasicBlock(MachineBasicBlock *BB);
83
84 // Target machine description which we query for register names, data
85 // layout, etc.
86 const TargetInstrInfo *TII;
87 };
88 } // namespace
89
90 char LanaiMemAluCombiner::ID = 0;
91
92 INITIALIZE_PASS(LanaiMemAluCombiner, DEBUG_TYPE,
93 "Lanai memory ALU combiner pass", false, false)
94
95 namespace {
96 bool isSpls(uint16_t Opcode) { return Lanai::splsIdempotent(Opcode) == Opcode; }
97
98 // Determine the opcode for the merged instruction created by considering the
99 // old memory operation's opcode and whether the merged opcode will have an
100 // immediate offset.
101 unsigned mergedOpcode(unsigned OldOpcode, bool ImmediateOffset) {
102 switch (OldOpcode) {
103 case Lanai::LDW_RI:
104 case Lanai::LDW_RR:
105 if (ImmediateOffset)
106 return Lanai::LDW_RI;
107 return Lanai::LDW_RR;
108 case Lanai::LDHs_RI:
109 case Lanai::LDHs_RR:
110 if (ImmediateOffset)
111 return Lanai::LDHs_RI;
112 return Lanai::LDHs_RR;
113 case Lanai::LDHz_RI:
114 case Lanai::LDHz_RR:
115 if (ImmediateOffset)
116 return Lanai::LDHz_RI;
117 return Lanai::LDHz_RR;
118 case Lanai::LDBs_RI:
119 case Lanai::LDBs_RR:
120 if (ImmediateOffset)
121 return Lanai::LDBs_RI;
122 return Lanai::LDBs_RR;
123 case Lanai::LDBz_RI:
124 case Lanai::LDBz_RR:
125 if (ImmediateOffset)
126 return Lanai::LDBz_RI;
127 return Lanai::LDBz_RR;
128 case Lanai::SW_RI:
129 case Lanai::SW_RR:
130 if (ImmediateOffset)
131 return Lanai::SW_RI;
132 return Lanai::SW_RR;
133 case Lanai::STB_RI:
134 case Lanai::STB_RR:
135 if (ImmediateOffset)
136 return Lanai::STB_RI;
137 return Lanai::STB_RR;
138 case Lanai::STH_RI:
139 case Lanai::STH_RR:
140 if (ImmediateOffset)
141 return Lanai::STH_RI;
142 return Lanai::STH_RR;
143 default:
144 return 0;
145 }
146 }
147
148 // Check if the machine instruction has non-volatile memory operands of the type
149 // supported for combining with ALU instructions.
150 bool isNonVolatileMemoryOp(const MachineInstr &MI) {
151 if (!MI.hasOneMemOperand())
152 return false;
153
154 // Determine if the machine instruction is a supported memory operation by
155 // testing if the computed merge opcode is a valid memory operation opcode.
156 if (mergedOpcode(MI.getOpcode(), false) == 0)
157 return false;
158
159 const MachineMemOperand *MemOperand = *MI.memoperands_begin();
160
161 // Don't move volatile memory accesses
162 if (MemOperand->isVolatile())
163 return false;
164
165 return true;
166 }
167
168 // Test to see if two machine operands are of the same type. This test is less
169 // strict than the MachineOperand::isIdenticalTo function.
170 bool isSameOperand(const MachineOperand &Op1, const MachineOperand &Op2) {
171 if (Op1.getType() != Op2.getType())
172 return false;
173
174 switch (Op1.getType()) {
175 case MachineOperand::MO_Register:
176 return Op1.getReg() == Op2.getReg();
177 case MachineOperand::MO_Immediate:
178 return Op1.getImm() == Op2.getImm();
179 default:
180 return false;
181 }
182 }
183
184 bool isZeroOperand(const MachineOperand &Op) {
185 return ((Op.isReg() && Op.getReg() == Lanai::R0) ||
186 (Op.isImm() && Op.getImm() == 0));
187 }
188
189 // Determines whether a register is used by an instruction.
190 bool InstrUsesReg(const MbbIterator &Instr, const MachineOperand *Reg) {
191 for (MachineInstr::const_mop_iterator Mop = Instr->operands_begin();
192 Mop != Instr->operands_end(); ++Mop) {
193 if (isSameOperand(*Mop, *Reg))
194 return true;
195 }
196 return false;
197 }
198
199 // Converts between machine opcode and AluCode.
200 // Flag using/modifying ALU operations should not be considered for merging and
201 // are omitted from this list.
202 LPAC::AluCode mergedAluCode(unsigned AluOpcode) {
203 switch (AluOpcode) {
204 case Lanai::ADD_I_LO:
205 case Lanai::ADD_R:
206 return LPAC::ADD;
207 case Lanai::SUB_I_LO:
208 case Lanai::SUB_R:
209 return LPAC::SUB;
210 case Lanai::AND_I_LO:
211 case Lanai::AND_R:
212 return LPAC::AND;
213 case Lanai::OR_I_LO:
214 case Lanai::OR_R:
215 return LPAC::OR;
216 case Lanai::XOR_I_LO:
217 case Lanai::XOR_R:
218 return LPAC::XOR;
219 case Lanai::SHL_R:
220 return LPAC::SHL;
221 case Lanai::SRL_R:
222 return LPAC::SRL;
223 case Lanai::SRA_R:
224 return LPAC::SRA;
225 case Lanai::SA_I:
226 case Lanai::SL_I:
227 default:
228 return LPAC::UNKNOWN;
229 }
230 }
231
232 // Insert a new combined memory and ALU operation instruction.
233 //
234 // This function builds a new machine instruction using the MachineInstrBuilder
235 // class and inserts it before the memory instruction.
236 void LanaiMemAluCombiner::insertMergedInstruction(MachineBasicBlock *BB,
237 const MbbIterator &MemInstr,
238 const MbbIterator &AluInstr,
239 bool Before) {
240 // Insert new combined load/store + alu operation
241 MachineOperand Dest = MemInstr->getOperand(0);
242 MachineOperand Base = MemInstr->getOperand(1);
243 MachineOperand MemOffset = MemInstr->getOperand(2);
244 MachineOperand AluOffset = AluInstr->getOperand(2);
245
246 // Abort if ALU offset is not a register or immediate
247 assert((AluOffset.isReg() || AluOffset.isImm()) &&
248 "Unsupported operand type in merge");
249
250 // Determined merged instructions opcode and ALU code
251 LPAC::AluCode AluOpcode = mergedAluCode(AluInstr->getOpcode());
252 unsigned NewOpc = mergedOpcode(MemInstr->getOpcode(), AluOffset.isImm());
253
254 assert(AluOpcode != LPAC::UNKNOWN && "Unknown ALU code in merging");
255 assert(NewOpc != 0 && "Unknown merged node opcode");
256
257 // Build and insert new machine instruction
258 MachineInstrBuilder InstrBuilder =
259 BuildMI(*BB, MemInstr, MemInstr->getDebugLoc(), TII->get(NewOpc));
260 InstrBuilder.addReg(Dest.getReg(), getDefRegState(true));
261 InstrBuilder.addReg(Base.getReg(), getKillRegState(true));
262
263 // Add offset to machine instruction
264 if (AluOffset.isReg())
265 InstrBuilder.addReg(AluOffset.getReg());
266 else if (AluOffset.isImm())
267 InstrBuilder.addImm(AluOffset.getImm());
268 else
269 llvm_unreachable("Unsupported ld/st ALU merge.");
270
271 // Create a pre-op if the ALU operation preceded the memory operation or the
272 // MemOffset is non-zero (i.e. the memory value should be adjusted before
273 // accessing it), else create a post-op.
274 if (Before || !isZeroOperand(MemOffset))
275 InstrBuilder.addImm(LPAC::makePreOp(AluOpcode));
276 else
277 InstrBuilder.addImm(LPAC::makePostOp(AluOpcode));
278
279 // Transfer memory operands.
280 InstrBuilder->setMemRefs(MemInstr->memoperands_begin(),
281 MemInstr->memoperands_end());
282 }
283
284 // Function determines if ALU operation (in alu_iter) can be combined with
285 // a load/store with base and offset.
286 bool isSuitableAluInstr(bool IsSpls, const MbbIterator &AluIter,
287 const MachineOperand &Base,
288 const MachineOperand &Offset) {
289 // ALU operations have 3 operands
290 if (AluIter->getNumOperands() != 3)
291 return false;
292
293 MachineOperand &Dest = AluIter->getOperand(0);
294 MachineOperand &Op1 = AluIter->getOperand(1);
295 MachineOperand &Op2 = AluIter->getOperand(2);
296
297 // Only match instructions using the base register as destination and with the
298 // base and first operand equal
299 if (!isSameOperand(Dest, Base) || !isSameOperand(Dest, Op1))
300 return false;
301
302 if (Op2.isImm()) {
303 // It is not a match if the 2nd operand in the ALU operation is an
304 // immediate but the ALU operation is not an addition.
305 if (AluIter->getOpcode() != Lanai::ADD_I_LO)
306 return false;
307
308 if (Offset.isReg() && Offset.getReg() == Lanai::R0)
309 return true;
310
311 if (Offset.isImm() &&
312 ((Offset.getImm() == 0 &&
313 // Check that the Op2 would fit in the immediate field of the
314 // memory operation.
315 ((IsSpls && isInt<10>(Op2.getImm())) ||
316 (!IsSpls && isInt<16>(Op2.getImm())))) ||
317 Offset.getImm() == Op2.getImm()))
318 return true;
319 } else if (Op2.isReg()) {
320 // The Offset and 2nd operand are both registers and equal
321 if (Offset.isReg() && Op2.getReg() == Offset.getReg())
322 return true;
323 } else
324 // Only consider operations with register or immediate values
325 return false;
326
327 return false;
328 }
329
330 MbbIterator LanaiMemAluCombiner::findClosestSuitableAluInstr(
331 MachineBasicBlock *BB, const MbbIterator &MemInstr, const bool Decrement) {
332 MachineOperand *Base = &MemInstr->getOperand(1);
333 MachineOperand *Offset = &MemInstr->getOperand(2);
334 bool IsSpls = isSpls(MemInstr->getOpcode());
335
336 MbbIterator First = MemInstr;
337 MbbIterator Last = Decrement ? BB->begin() : BB->end();
338
339 while (First != Last) {
340 Decrement ? --First : ++First;
341
342 if (First == Last)
343 break;
344
345 // Skip over debug instructions
346 if (First->isDebugValue())
347 continue;
348
349 if (isSuitableAluInstr(IsSpls, First, *Base, *Offset)) {
350 return First;
351 }
352
353 // Usage of the base or offset register is not a form suitable for merging.
354 if (First != Last) {
355 if (InstrUsesReg(First, Base))
356 break;
357 if (Offset->isReg() && InstrUsesReg(First, Offset))
358 break;
359 }
360 }
361
362 return MemInstr;
363 }
364
365 bool LanaiMemAluCombiner::combineMemAluInBasicBlock(MachineBasicBlock *BB) {
366 bool Modified = false;
367
368 MbbIterator MBBIter = BB->begin(), End = BB->end();
369 while (MBBIter != End) {
370 bool IsMemOp = isNonVolatileMemoryOp(*MBBIter);
371
372 if (IsMemOp) {
373 MachineOperand AluOperand = MBBIter->getOperand(3);
374 unsigned int DestReg = MBBIter->getOperand(0).getReg(),
375 BaseReg = MBBIter->getOperand(1).getReg();
376 assert(AluOperand.isImm() && "Unexpected memory operator type");
377 LPAC::AluCode AluOpcode = static_cast<LPAC::AluCode>(AluOperand.getImm());
378
379 // Skip memory operations that already modify the base register or if
380 // the destination and base register are the same
381 if (!LPAC::modifiesOp(AluOpcode) && DestReg != BaseReg) {
382 for (int Inc = 0; Inc <= 1; ++Inc) {
383 MbbIterator AluIter =
384 findClosestSuitableAluInstr(BB, MBBIter, Inc == 0);
385 if (AluIter != MBBIter) {
386 insertMergedInstruction(BB, MBBIter, AluIter, Inc == 0);
387
388 ++NumLdStAluCombined;
389 Modified = true;
390
391 // Erase the matching ALU instruction
392 BB->erase(AluIter);
393 // Erase old load/store instruction
394 BB->erase(MBBIter++);
395 break;
396 }
397 }
398 }
399 }
400 if (MBBIter == End)
401 break;
402 ++MBBIter;
403 }
404
405 return Modified;
406 }
407
408 // Driver function that iterates over the machine basic building blocks of a
409 // machine function
410 bool LanaiMemAluCombiner::runOnMachineFunction(MachineFunction &MF) {
411 if (DisableMemAluCombiner)
412 return false;
413
414 TII = MF.getSubtarget<LanaiSubtarget>().getInstrInfo();
415 bool Modified = false;
416 for (MfIterator MFI = MF.begin(); MFI != MF.end(); ++MFI) {
417 Modified |= combineMemAluInBasicBlock(&*MFI);
418 }
419 return Modified;
420 }
421 } // namespace
422
423 FunctionPass *llvm::createLanaiMemAluCombinerPass() {
424 return new LanaiMemAluCombiner();
425 }