1 | //===- CSKYConstantIslandPass.cpp - Emit PC Relative loads ----------------===// |
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 | // Loading constants inline is expensive on CSKY and it's in general better |
11 | // to place the constant nearby in code space and then it can be loaded with a |
12 | // simple 16/32 bit load instruction like lrw. |
13 | // |
14 | // The constants can be not just numbers but addresses of functions and labels. |
15 | // This can be particularly helpful in static relocation mode for embedded |
16 | // non-linux targets. |
17 | // |
18 | //===----------------------------------------------------------------------===// |
19 | |
20 | #include "CSKY.h" |
21 | #include "CSKYConstantPoolValue.h" |
22 | #include "CSKYMachineFunctionInfo.h" |
23 | #include "CSKYSubtarget.h" |
24 | #include "llvm/ADT/STLExtras.h" |
25 | #include "llvm/ADT/SmallSet.h" |
26 | #include "llvm/ADT/SmallVector.h" |
27 | #include "llvm/ADT/Statistic.h" |
28 | #include "llvm/ADT/StringRef.h" |
29 | #include "llvm/CodeGen/MachineBasicBlock.h" |
30 | #include "llvm/CodeGen/MachineConstantPool.h" |
31 | #include "llvm/CodeGen/MachineDominators.h" |
32 | #include "llvm/CodeGen/MachineFrameInfo.h" |
33 | #include "llvm/CodeGen/MachineFunction.h" |
34 | #include "llvm/CodeGen/MachineFunctionPass.h" |
35 | #include "llvm/CodeGen/MachineInstr.h" |
36 | #include "llvm/CodeGen/MachineInstrBuilder.h" |
37 | #include "llvm/CodeGen/MachineOperand.h" |
38 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
39 | #include "llvm/Config/llvm-config.h" |
40 | #include "llvm/IR/Constants.h" |
41 | #include "llvm/IR/DataLayout.h" |
42 | #include "llvm/IR/DebugLoc.h" |
43 | #include "llvm/IR/Function.h" |
44 | #include "llvm/IR/Type.h" |
45 | #include "llvm/Support/CommandLine.h" |
46 | #include "llvm/Support/Compiler.h" |
47 | #include "llvm/Support/Debug.h" |
48 | #include "llvm/Support/ErrorHandling.h" |
49 | #include "llvm/Support/Format.h" |
50 | #include "llvm/Support/MathExtras.h" |
51 | #include "llvm/Support/raw_ostream.h" |
52 | #include <algorithm> |
53 | #include <cassert> |
54 | #include <cstdint> |
55 | #include <iterator> |
56 | #include <vector> |
57 | |
58 | using namespace llvm; |
59 | |
60 | #define DEBUG_TYPE "CSKY-constant-islands" |
61 | |
62 | STATISTIC(NumCPEs, "Number of constpool entries" ); |
63 | STATISTIC(NumSplit, "Number of uncond branches inserted" ); |
64 | STATISTIC(NumCBrFixed, "Number of cond branches fixed" ); |
65 | STATISTIC(NumUBrFixed, "Number of uncond branches fixed" ); |
66 | |
67 | namespace { |
68 | |
69 | using Iter = MachineBasicBlock::iterator; |
70 | using ReverseIter = MachineBasicBlock::reverse_iterator; |
71 | |
72 | /// CSKYConstantIslands - Due to limited PC-relative displacements, CSKY |
73 | /// requires constant pool entries to be scattered among the instructions |
74 | /// inside a function. To do this, it completely ignores the normal LLVM |
75 | /// constant pool; instead, it places constants wherever it feels like with |
76 | /// special instructions. |
77 | /// |
78 | /// The terminology used in this pass includes: |
79 | /// Islands - Clumps of constants placed in the function. |
80 | /// Water - Potential places where an island could be formed. |
81 | /// CPE - A constant pool entry that has been placed somewhere, which |
82 | /// tracks a list of users. |
83 | |
84 | class CSKYConstantIslands : public MachineFunctionPass { |
85 | /// BasicBlockInfo - Information about the offset and size of a single |
86 | /// basic block. |
87 | struct BasicBlockInfo { |
88 | /// Offset - Distance from the beginning of the function to the beginning |
89 | /// of this basic block. |
90 | /// |
91 | /// Offsets are computed assuming worst case padding before an aligned |
92 | /// block. This means that subtracting basic block offsets always gives a |
93 | /// conservative estimate of the real distance which may be smaller. |
94 | /// |
95 | /// Because worst case padding is used, the computed offset of an aligned |
96 | /// block may not actually be aligned. |
97 | unsigned Offset = 0; |
98 | |
99 | /// Size - Size of the basic block in bytes. If the block contains |
100 | /// inline assembly, this is a worst case estimate. |
101 | /// |
102 | /// The size does not include any alignment padding whether from the |
103 | /// beginning of the block, or from an aligned jump table at the end. |
104 | unsigned Size = 0; |
105 | |
106 | BasicBlockInfo() = default; |
107 | |
108 | unsigned postOffset() const { return Offset + Size; } |
109 | }; |
110 | |
111 | std::vector<BasicBlockInfo> BBInfo; |
112 | |
113 | /// WaterList - A sorted list of basic blocks where islands could be placed |
114 | /// (i.e. blocks that don't fall through to the following block, due |
115 | /// to a return, unreachable, or unconditional branch). |
116 | std::vector<MachineBasicBlock *> WaterList; |
117 | |
118 | /// NewWaterList - The subset of WaterList that was created since the |
119 | /// previous iteration by inserting unconditional branches. |
120 | SmallSet<MachineBasicBlock *, 4> NewWaterList; |
121 | |
122 | using water_iterator = std::vector<MachineBasicBlock *>::iterator; |
123 | |
124 | /// CPUser - One user of a constant pool, keeping the machine instruction |
125 | /// pointer, the constant pool being referenced, and the max displacement |
126 | /// allowed from the instruction to the CP. The HighWaterMark records the |
127 | /// highest basic block where a new CPEntry can be placed. To ensure this |
128 | /// pass terminates, the CP entries are initially placed at the end of the |
129 | /// function and then move monotonically to lower addresses. The |
130 | /// exception to this rule is when the current CP entry for a particular |
131 | /// CPUser is out of range, but there is another CP entry for the same |
132 | /// constant value in range. We want to use the existing in-range CP |
133 | /// entry, but if it later moves out of range, the search for new water |
134 | /// should resume where it left off. The HighWaterMark is used to record |
135 | /// that point. |
136 | struct CPUser { |
137 | MachineInstr *MI; |
138 | MachineInstr *CPEMI; |
139 | MachineBasicBlock *HighWaterMark; |
140 | |
141 | private: |
142 | unsigned MaxDisp; |
143 | |
144 | public: |
145 | bool NegOk; |
146 | |
147 | CPUser(MachineInstr *Mi, MachineInstr *Cpemi, unsigned Maxdisp, bool Neg) |
148 | : MI(Mi), CPEMI(Cpemi), MaxDisp(Maxdisp), NegOk(Neg) { |
149 | HighWaterMark = CPEMI->getParent(); |
150 | } |
151 | |
152 | /// getMaxDisp - Returns the maximum displacement supported by MI. |
153 | unsigned getMaxDisp() const { return MaxDisp - 16; } |
154 | |
155 | void setMaxDisp(unsigned Val) { MaxDisp = Val; } |
156 | }; |
157 | |
158 | /// CPUsers - Keep track of all of the machine instructions that use various |
159 | /// constant pools and their max displacement. |
160 | std::vector<CPUser> CPUsers; |
161 | |
162 | /// CPEntry - One per constant pool entry, keeping the machine instruction |
163 | /// pointer, the constpool index, and the number of CPUser's which |
164 | /// reference this entry. |
165 | struct CPEntry { |
166 | MachineInstr *CPEMI; |
167 | unsigned CPI; |
168 | unsigned RefCount; |
169 | |
170 | CPEntry(MachineInstr *Cpemi, unsigned Cpi, unsigned Rc = 0) |
171 | : CPEMI(Cpemi), CPI(Cpi), RefCount(Rc) {} |
172 | }; |
173 | |
174 | /// CPEntries - Keep track of all of the constant pool entry machine |
175 | /// instructions. For each original constpool index (i.e. those that |
176 | /// existed upon entry to this pass), it keeps a vector of entries. |
177 | /// Original elements are cloned as we go along; the clones are |
178 | /// put in the vector of the original element, but have distinct CPIs. |
179 | std::vector<std::vector<CPEntry>> CPEntries; |
180 | |
181 | /// ImmBranch - One per immediate branch, keeping the machine instruction |
182 | /// pointer, conditional or unconditional, the max displacement, |
183 | /// and (if isCond is true) the corresponding unconditional branch |
184 | /// opcode. |
185 | struct ImmBranch { |
186 | MachineInstr *MI; |
187 | unsigned MaxDisp : 31; |
188 | bool IsCond : 1; |
189 | int UncondBr; |
190 | |
191 | ImmBranch(MachineInstr *Mi, unsigned Maxdisp, bool Cond, int Ubr) |
192 | : MI(Mi), MaxDisp(Maxdisp), IsCond(Cond), UncondBr(Ubr) {} |
193 | }; |
194 | |
195 | /// ImmBranches - Keep track of all the immediate branch instructions. |
196 | /// |
197 | std::vector<ImmBranch> ImmBranches; |
198 | |
199 | const CSKYSubtarget *STI = nullptr; |
200 | const CSKYInstrInfo *TII; |
201 | CSKYMachineFunctionInfo *MFI; |
202 | MachineFunction *MF = nullptr; |
203 | MachineConstantPool *MCP = nullptr; |
204 | |
205 | unsigned PICLabelUId; |
206 | |
207 | void initPICLabelUId(unsigned UId) { PICLabelUId = UId; } |
208 | |
209 | unsigned createPICLabelUId() { return PICLabelUId++; } |
210 | |
211 | public: |
212 | static char ID; |
213 | |
214 | CSKYConstantIslands() : MachineFunctionPass(ID) {} |
215 | |
216 | StringRef getPassName() const override { return "CSKY Constant Islands" ; } |
217 | |
218 | bool runOnMachineFunction(MachineFunction &F) override; |
219 | |
220 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
221 | AU.addRequired<MachineDominatorTree>(); |
222 | MachineFunctionPass::getAnalysisUsage(AU); |
223 | } |
224 | |
225 | MachineFunctionProperties getRequiredProperties() const override { |
226 | return MachineFunctionProperties().set( |
227 | MachineFunctionProperties::Property::NoVRegs); |
228 | } |
229 | |
230 | void doInitialPlacement(std::vector<MachineInstr *> &CPEMIs); |
231 | CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI); |
232 | Align getCPEAlign(const MachineInstr &CPEMI); |
233 | void initializeFunctionInfo(const std::vector<MachineInstr *> &CPEMIs); |
234 | unsigned getOffsetOf(MachineInstr *MI) const; |
235 | unsigned getUserOffset(CPUser &) const; |
236 | void dumpBBs(); |
237 | |
238 | bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset, unsigned Disp, |
239 | bool NegativeOK); |
240 | bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset, |
241 | const CPUser &U); |
242 | |
243 | void computeBlockSize(MachineBasicBlock *MBB); |
244 | MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI); |
245 | void updateForInsertedWaterBlock(MachineBasicBlock *NewBB); |
246 | void adjustBBOffsetsAfter(MachineBasicBlock *BB); |
247 | bool decrementCPEReferenceCount(unsigned CPI, MachineInstr *CPEMI); |
248 | int findInRangeCPEntry(CPUser &U, unsigned UserOffset); |
249 | bool findAvailableWater(CPUser &U, unsigned UserOffset, |
250 | water_iterator &WaterIter); |
251 | void createNewWater(unsigned CPUserIndex, unsigned UserOffset, |
252 | MachineBasicBlock *&NewMBB); |
253 | bool handleConstantPoolUser(unsigned CPUserIndex); |
254 | void removeDeadCPEMI(MachineInstr *CPEMI); |
255 | bool removeUnusedCPEntries(); |
256 | bool isCPEntryInRange(MachineInstr *MI, unsigned UserOffset, |
257 | MachineInstr *CPEMI, unsigned Disp, bool NegOk, |
258 | bool DoDump = false); |
259 | bool isWaterInRange(unsigned UserOffset, MachineBasicBlock *Water, CPUser &U, |
260 | unsigned &Growth); |
261 | bool isBBInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp); |
262 | bool fixupImmediateBr(ImmBranch &Br); |
263 | bool fixupConditionalBr(ImmBranch &Br); |
264 | bool fixupUnconditionalBr(ImmBranch &Br); |
265 | }; |
266 | } // end anonymous namespace |
267 | |
268 | char CSKYConstantIslands::ID = 0; |
269 | |
270 | bool CSKYConstantIslands::isOffsetInRange(unsigned UserOffset, |
271 | unsigned TrialOffset, |
272 | const CPUser &U) { |
273 | return isOffsetInRange(UserOffset, TrialOffset, Disp: U.getMaxDisp(), NegativeOK: U.NegOk); |
274 | } |
275 | |
276 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
277 | /// print block size and offset information - debugging |
278 | LLVM_DUMP_METHOD void CSKYConstantIslands::dumpBBs() { |
279 | for (unsigned J = 0, E = BBInfo.size(); J != E; ++J) { |
280 | const BasicBlockInfo &BBI = BBInfo[J]; |
281 | dbgs() << format(Fmt: "%08x %bb.%u\t" , Vals: BBI.Offset, Vals: J) |
282 | << format(Fmt: " size=%#x\n" , Vals: BBInfo[J].Size); |
283 | } |
284 | } |
285 | #endif |
286 | |
287 | bool CSKYConstantIslands::runOnMachineFunction(MachineFunction &Mf) { |
288 | MF = &Mf; |
289 | MCP = Mf.getConstantPool(); |
290 | STI = &Mf.getSubtarget<CSKYSubtarget>(); |
291 | |
292 | LLVM_DEBUG(dbgs() << "***** CSKYConstantIslands: " |
293 | << MCP->getConstants().size() << " CP entries, aligned to " |
294 | << MCP->getConstantPoolAlign().value() << " bytes *****\n" ); |
295 | |
296 | TII = STI->getInstrInfo(); |
297 | MFI = MF->getInfo<CSKYMachineFunctionInfo>(); |
298 | |
299 | // This pass invalidates liveness information when it splits basic blocks. |
300 | MF->getRegInfo().invalidateLiveness(); |
301 | |
302 | // Renumber all of the machine basic blocks in the function, guaranteeing that |
303 | // the numbers agree with the position of the block in the function. |
304 | MF->RenumberBlocks(); |
305 | |
306 | bool MadeChange = false; |
307 | |
308 | // Perform the initial placement of the constant pool entries. To start with, |
309 | // we put them all at the end of the function. |
310 | std::vector<MachineInstr *> CPEMIs; |
311 | if (!MCP->isEmpty()) |
312 | doInitialPlacement(CPEMIs); |
313 | |
314 | /// The next UID to take is the first unused one. |
315 | initPICLabelUId(UId: CPEMIs.size()); |
316 | |
317 | // Do the initial scan of the function, building up information about the |
318 | // sizes of each block, the location of all the water, and finding all of the |
319 | // constant pool users. |
320 | initializeFunctionInfo(CPEMIs); |
321 | CPEMIs.clear(); |
322 | LLVM_DEBUG(dumpBBs()); |
323 | |
324 | /// Remove dead constant pool entries. |
325 | MadeChange |= removeUnusedCPEntries(); |
326 | |
327 | // Iteratively place constant pool entries and fix up branches until there |
328 | // is no change. |
329 | unsigned NoCPIters = 0, NoBRIters = 0; |
330 | (void)NoBRIters; |
331 | while (true) { |
332 | LLVM_DEBUG(dbgs() << "Beginning CP iteration #" << NoCPIters << '\n'); |
333 | bool CPChange = false; |
334 | for (unsigned I = 0, E = CPUsers.size(); I != E; ++I) |
335 | CPChange |= handleConstantPoolUser(CPUserIndex: I); |
336 | if (CPChange && ++NoCPIters > 30) |
337 | report_fatal_error(reason: "Constant Island pass failed to converge!" ); |
338 | LLVM_DEBUG(dumpBBs()); |
339 | |
340 | // Clear NewWaterList now. If we split a block for branches, it should |
341 | // appear as "new water" for the next iteration of constant pool placement. |
342 | NewWaterList.clear(); |
343 | |
344 | LLVM_DEBUG(dbgs() << "Beginning BR iteration #" << NoBRIters << '\n'); |
345 | bool BRChange = false; |
346 | for (unsigned I = 0, E = ImmBranches.size(); I != E; ++I) |
347 | BRChange |= fixupImmediateBr(Br&: ImmBranches[I]); |
348 | if (BRChange && ++NoBRIters > 30) |
349 | report_fatal_error(reason: "Branch Fix Up pass failed to converge!" ); |
350 | LLVM_DEBUG(dumpBBs()); |
351 | if (!CPChange && !BRChange) |
352 | break; |
353 | MadeChange = true; |
354 | } |
355 | |
356 | LLVM_DEBUG(dbgs() << '\n'; dumpBBs()); |
357 | |
358 | BBInfo.clear(); |
359 | WaterList.clear(); |
360 | CPUsers.clear(); |
361 | CPEntries.clear(); |
362 | ImmBranches.clear(); |
363 | return MadeChange; |
364 | } |
365 | |
366 | /// doInitialPlacement - Perform the initial placement of the constant pool |
367 | /// entries. To start with, we put them all at the end of the function. |
368 | void CSKYConstantIslands::doInitialPlacement( |
369 | std::vector<MachineInstr *> &CPEMIs) { |
370 | // Create the basic block to hold the CPE's. |
371 | MachineBasicBlock *BB = MF->CreateMachineBasicBlock(); |
372 | MF->push_back(MBB: BB); |
373 | |
374 | // MachineConstantPool measures alignment in bytes. We measure in log2(bytes). |
375 | const Align MaxAlign = MCP->getConstantPoolAlign(); |
376 | |
377 | // Mark the basic block as required by the const-pool. |
378 | BB->setAlignment(Align(2)); |
379 | |
380 | // The function needs to be as aligned as the basic blocks. The linker may |
381 | // move functions around based on their alignment. |
382 | MF->ensureAlignment(A: BB->getAlignment()); |
383 | |
384 | // Order the entries in BB by descending alignment. That ensures correct |
385 | // alignment of all entries as long as BB is sufficiently aligned. Keep |
386 | // track of the insertion point for each alignment. We are going to bucket |
387 | // sort the entries as they are created. |
388 | SmallVector<MachineBasicBlock::iterator, 8> InsPoint(Log2(A: MaxAlign) + 1, |
389 | BB->end()); |
390 | |
391 | // Add all of the constants from the constant pool to the end block, use an |
392 | // identity mapping of CPI's to CPE's. |
393 | const std::vector<MachineConstantPoolEntry> &CPs = MCP->getConstants(); |
394 | |
395 | const DataLayout &TD = MF->getDataLayout(); |
396 | for (unsigned I = 0, E = CPs.size(); I != E; ++I) { |
397 | unsigned Size = CPs[I].getSizeInBytes(DL: TD); |
398 | assert(Size >= 4 && "Too small constant pool entry" ); |
399 | Align Alignment = CPs[I].getAlign(); |
400 | // Verify that all constant pool entries are a multiple of their alignment. |
401 | // If not, we would have to pad them out so that instructions stay aligned. |
402 | assert(isAligned(Alignment, Size) && "CP Entry not multiple of 4 bytes!" ); |
403 | |
404 | // Insert CONSTPOOL_ENTRY before entries with a smaller alignment. |
405 | unsigned LogAlign = Log2(A: Alignment); |
406 | MachineBasicBlock::iterator InsAt = InsPoint[LogAlign]; |
407 | |
408 | MachineInstr *CPEMI = |
409 | BuildMI(*BB, InsAt, DebugLoc(), TII->get(CSKY::CONSTPOOL_ENTRY)) |
410 | .addImm(I) |
411 | .addConstantPoolIndex(I) |
412 | .addImm(Size); |
413 | |
414 | CPEMIs.push_back(x: CPEMI); |
415 | |
416 | // Ensure that future entries with higher alignment get inserted before |
417 | // CPEMI. This is bucket sort with iterators. |
418 | for (unsigned A = LogAlign + 1; A <= Log2(A: MaxAlign); ++A) |
419 | if (InsPoint[A] == InsAt) |
420 | InsPoint[A] = CPEMI; |
421 | // Add a new CPEntry, but no corresponding CPUser yet. |
422 | CPEntries.emplace_back(args: 1, args: CPEntry(CPEMI, I)); |
423 | ++NumCPEs; |
424 | LLVM_DEBUG(dbgs() << "Moved CPI#" << I << " to end of function, size = " |
425 | << Size << ", align = " << Alignment.value() << '\n'); |
426 | } |
427 | LLVM_DEBUG(BB->dump()); |
428 | } |
429 | |
430 | /// BBHasFallthrough - Return true if the specified basic block can fallthrough |
431 | /// into the block immediately after it. |
432 | static bool bbHasFallthrough(MachineBasicBlock *MBB) { |
433 | // Get the next machine basic block in the function. |
434 | MachineFunction::iterator MBBI = MBB->getIterator(); |
435 | // Can't fall off end of function. |
436 | if (std::next(x: MBBI) == MBB->getParent()->end()) |
437 | return false; |
438 | |
439 | MachineBasicBlock *NextBB = &*std::next(x: MBBI); |
440 | for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(), |
441 | E = MBB->succ_end(); |
442 | I != E; ++I) |
443 | if (*I == NextBB) |
444 | return true; |
445 | |
446 | return false; |
447 | } |
448 | |
449 | /// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI, |
450 | /// look up the corresponding CPEntry. |
451 | CSKYConstantIslands::CPEntry * |
452 | CSKYConstantIslands::findConstPoolEntry(unsigned CPI, |
453 | const MachineInstr *CPEMI) { |
454 | std::vector<CPEntry> &CPEs = CPEntries[CPI]; |
455 | // Number of entries per constpool index should be small, just do a |
456 | // linear search. |
457 | for (unsigned I = 0, E = CPEs.size(); I != E; ++I) { |
458 | if (CPEs[I].CPEMI == CPEMI) |
459 | return &CPEs[I]; |
460 | } |
461 | return nullptr; |
462 | } |
463 | |
464 | /// getCPEAlign - Returns the required alignment of the constant pool entry |
465 | /// represented by CPEMI. Alignment is measured in log2(bytes) units. |
466 | Align CSKYConstantIslands::getCPEAlign(const MachineInstr &CPEMI) { |
467 | assert(CPEMI.getOpcode() == CSKY::CONSTPOOL_ENTRY); |
468 | |
469 | unsigned CPI = CPEMI.getOperand(i: 1).getIndex(); |
470 | assert(CPI < MCP->getConstants().size() && "Invalid constant pool index." ); |
471 | return MCP->getConstants()[CPI].getAlign(); |
472 | } |
473 | |
474 | /// initializeFunctionInfo - Do the initial scan of the function, building up |
475 | /// information about the sizes of each block, the location of all the water, |
476 | /// and finding all of the constant pool users. |
477 | void CSKYConstantIslands::initializeFunctionInfo( |
478 | const std::vector<MachineInstr *> &CPEMIs) { |
479 | BBInfo.clear(); |
480 | BBInfo.resize(new_size: MF->getNumBlockIDs()); |
481 | |
482 | // First thing, compute the size of all basic blocks, and see if the function |
483 | // has any inline assembly in it. If so, we have to be conservative about |
484 | // alignment assumptions, as we don't know for sure the size of any |
485 | // instructions in the inline assembly. |
486 | for (MachineFunction::iterator I = MF->begin(), E = MF->end(); I != E; ++I) |
487 | computeBlockSize(MBB: &*I); |
488 | |
489 | // Compute block offsets. |
490 | adjustBBOffsetsAfter(BB: &MF->front()); |
491 | |
492 | // Now go back through the instructions and build up our data structures. |
493 | for (MachineBasicBlock &MBB : *MF) { |
494 | // If this block doesn't fall through into the next MBB, then this is |
495 | // 'water' that a constant pool island could be placed. |
496 | if (!bbHasFallthrough(MBB: &MBB)) |
497 | WaterList.push_back(x: &MBB); |
498 | for (MachineInstr &MI : MBB) { |
499 | if (MI.isDebugInstr()) |
500 | continue; |
501 | |
502 | int Opc = MI.getOpcode(); |
503 | if (MI.isBranch() && !MI.isIndirectBranch()) { |
504 | bool IsCond = MI.isConditionalBranch(); |
505 | unsigned Bits = 0; |
506 | unsigned Scale = 1; |
507 | int UOpc = CSKY::BR32; |
508 | |
509 | switch (MI.getOpcode()) { |
510 | case CSKY::BR16: |
511 | case CSKY::BF16: |
512 | case CSKY::BT16: |
513 | Bits = 10; |
514 | Scale = 2; |
515 | break; |
516 | default: |
517 | Bits = 16; |
518 | Scale = 2; |
519 | break; |
520 | } |
521 | |
522 | // Record this immediate branch. |
523 | unsigned MaxOffs = ((1 << (Bits - 1)) - 1) * Scale; |
524 | ImmBranches.push_back(x: ImmBranch(&MI, MaxOffs, IsCond, UOpc)); |
525 | } |
526 | |
527 | if (Opc == CSKY::CONSTPOOL_ENTRY) |
528 | continue; |
529 | |
530 | // Scan the instructions for constant pool operands. |
531 | for (unsigned Op = 0, E = MI.getNumOperands(); Op != E; ++Op) |
532 | if (MI.getOperand(i: Op).isCPI()) { |
533 | // We found one. The addressing mode tells us the max displacement |
534 | // from the PC that this instruction permits. |
535 | |
536 | // Basic size info comes from the TSFlags field. |
537 | unsigned Bits = 0; |
538 | unsigned Scale = 1; |
539 | bool NegOk = false; |
540 | |
541 | switch (Opc) { |
542 | default: |
543 | llvm_unreachable("Unknown addressing mode for CP reference!" ); |
544 | case CSKY::MOVIH32: |
545 | case CSKY::ORI32: |
546 | continue; |
547 | case CSKY::PseudoTLSLA32: |
548 | case CSKY::JSRI32: |
549 | case CSKY::JMPI32: |
550 | case CSKY::LRW32: |
551 | case CSKY::LRW32_Gen: |
552 | Bits = 16; |
553 | Scale = 4; |
554 | break; |
555 | case CSKY::f2FLRW_S: |
556 | case CSKY::f2FLRW_D: |
557 | Bits = 8; |
558 | Scale = 4; |
559 | break; |
560 | case CSKY::GRS32: |
561 | Bits = 17; |
562 | Scale = 2; |
563 | NegOk = true; |
564 | break; |
565 | } |
566 | // Remember that this is a user of a CP entry. |
567 | unsigned CPI = MI.getOperand(i: Op).getIndex(); |
568 | MachineInstr *CPEMI = CPEMIs[CPI]; |
569 | unsigned MaxOffs = ((1 << Bits) - 1) * Scale; |
570 | CPUsers.push_back(x: CPUser(&MI, CPEMI, MaxOffs, NegOk)); |
571 | |
572 | // Increment corresponding CPEntry reference count. |
573 | CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); |
574 | assert(CPE && "Cannot find a corresponding CPEntry!" ); |
575 | CPE->RefCount++; |
576 | } |
577 | } |
578 | } |
579 | } |
580 | |
581 | /// computeBlockSize - Compute the size and some alignment information for MBB. |
582 | /// This function updates BBInfo directly. |
583 | void CSKYConstantIslands::computeBlockSize(MachineBasicBlock *MBB) { |
584 | BasicBlockInfo &BBI = BBInfo[MBB->getNumber()]; |
585 | BBI.Size = 0; |
586 | |
587 | for (const MachineInstr &MI : *MBB) |
588 | BBI.Size += TII->getInstSizeInBytes(MI); |
589 | } |
590 | |
591 | /// getOffsetOf - Return the current offset of the specified machine instruction |
592 | /// from the start of the function. This offset changes as stuff is moved |
593 | /// around inside the function. |
594 | unsigned CSKYConstantIslands::getOffsetOf(MachineInstr *MI) const { |
595 | MachineBasicBlock *MBB = MI->getParent(); |
596 | |
597 | // The offset is composed of two things: the sum of the sizes of all MBB's |
598 | // before this instruction's block, and the offset from the start of the block |
599 | // it is in. |
600 | unsigned Offset = BBInfo[MBB->getNumber()].Offset; |
601 | |
602 | // Sum instructions before MI in MBB. |
603 | for (MachineBasicBlock::iterator I = MBB->begin(); &*I != MI; ++I) { |
604 | assert(I != MBB->end() && "Didn't find MI in its own basic block?" ); |
605 | Offset += TII->getInstSizeInBytes(MI: *I); |
606 | } |
607 | return Offset; |
608 | } |
609 | |
610 | /// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB |
611 | /// ID. |
612 | static bool compareMbbNumbers(const MachineBasicBlock *LHS, |
613 | const MachineBasicBlock *RHS) { |
614 | return LHS->getNumber() < RHS->getNumber(); |
615 | } |
616 | |
617 | /// updateForInsertedWaterBlock - When a block is newly inserted into the |
618 | /// machine function, it upsets all of the block numbers. Renumber the blocks |
619 | /// and update the arrays that parallel this numbering. |
620 | void CSKYConstantIslands::updateForInsertedWaterBlock( |
621 | MachineBasicBlock *NewBB) { |
622 | // Renumber the MBB's to keep them consecutive. |
623 | NewBB->getParent()->RenumberBlocks(MBBFrom: NewBB); |
624 | |
625 | // Insert an entry into BBInfo to align it properly with the (newly |
626 | // renumbered) block numbers. |
627 | BBInfo.insert(position: BBInfo.begin() + NewBB->getNumber(), x: BasicBlockInfo()); |
628 | |
629 | // Next, update WaterList. Specifically, we need to add NewMBB as having |
630 | // available water after it. |
631 | water_iterator IP = llvm::lower_bound(Range&: WaterList, Value&: NewBB, C: compareMbbNumbers); |
632 | WaterList.insert(position: IP, x: NewBB); |
633 | } |
634 | |
635 | unsigned CSKYConstantIslands::getUserOffset(CPUser &U) const { |
636 | unsigned UserOffset = getOffsetOf(MI: U.MI); |
637 | |
638 | UserOffset &= ~3u; |
639 | |
640 | return UserOffset; |
641 | } |
642 | |
643 | /// Split the basic block containing MI into two blocks, which are joined by |
644 | /// an unconditional branch. Update data structures and renumber blocks to |
645 | /// account for this change and returns the newly created block. |
646 | MachineBasicBlock * |
647 | CSKYConstantIslands::splitBlockBeforeInstr(MachineInstr &MI) { |
648 | MachineBasicBlock *OrigBB = MI.getParent(); |
649 | |
650 | // Create a new MBB for the code after the OrigBB. |
651 | MachineBasicBlock *NewBB = |
652 | MF->CreateMachineBasicBlock(BB: OrigBB->getBasicBlock()); |
653 | MachineFunction::iterator MBBI = ++OrigBB->getIterator(); |
654 | MF->insert(MBBI, MBB: NewBB); |
655 | |
656 | // Splice the instructions starting with MI over to NewBB. |
657 | NewBB->splice(Where: NewBB->end(), Other: OrigBB, From: MI, To: OrigBB->end()); |
658 | |
659 | // Add an unconditional branch from OrigBB to NewBB. |
660 | // Note the new unconditional branch is not being recorded. |
661 | // There doesn't seem to be meaningful DebugInfo available; this doesn't |
662 | // correspond to anything in the source. |
663 | |
664 | // TODO: Add support for 16bit instr. |
665 | BuildMI(OrigBB, DebugLoc(), TII->get(CSKY::BR32)).addMBB(NewBB); |
666 | ++NumSplit; |
667 | |
668 | // Update the CFG. All succs of OrigBB are now succs of NewBB. |
669 | NewBB->transferSuccessors(FromMBB: OrigBB); |
670 | |
671 | // OrigBB branches to NewBB. |
672 | OrigBB->addSuccessor(Succ: NewBB); |
673 | |
674 | // Update internal data structures to account for the newly inserted MBB. |
675 | // This is almost the same as updateForInsertedWaterBlock, except that |
676 | // the Water goes after OrigBB, not NewBB. |
677 | MF->RenumberBlocks(MBBFrom: NewBB); |
678 | |
679 | // Insert an entry into BBInfo to align it properly with the (newly |
680 | // renumbered) block numbers. |
681 | BBInfo.insert(position: BBInfo.begin() + NewBB->getNumber(), x: BasicBlockInfo()); |
682 | |
683 | // Next, update WaterList. Specifically, we need to add OrigMBB as having |
684 | // available water after it (but not if it's already there, which happens |
685 | // when splitting before a conditional branch that is followed by an |
686 | // unconditional branch - in that case we want to insert NewBB). |
687 | water_iterator IP = llvm::lower_bound(Range&: WaterList, Value&: OrigBB, C: compareMbbNumbers); |
688 | MachineBasicBlock *WaterBB = *IP; |
689 | if (WaterBB == OrigBB) |
690 | WaterList.insert(position: std::next(x: IP), x: NewBB); |
691 | else |
692 | WaterList.insert(position: IP, x: OrigBB); |
693 | NewWaterList.insert(Ptr: OrigBB); |
694 | |
695 | // Figure out how large the OrigBB is. As the first half of the original |
696 | // block, it cannot contain a tablejump. The size includes |
697 | // the new jump we added. (It should be possible to do this without |
698 | // recounting everything, but it's very confusing, and this is rarely |
699 | // executed.) |
700 | computeBlockSize(MBB: OrigBB); |
701 | |
702 | // Figure out how large the NewMBB is. As the second half of the original |
703 | // block, it may contain a tablejump. |
704 | computeBlockSize(MBB: NewBB); |
705 | |
706 | // All BBOffsets following these blocks must be modified. |
707 | adjustBBOffsetsAfter(BB: OrigBB); |
708 | |
709 | return NewBB; |
710 | } |
711 | |
712 | /// isOffsetInRange - Checks whether UserOffset (the location of a constant pool |
713 | /// reference) is within MaxDisp of TrialOffset (a proposed location of a |
714 | /// constant pool entry). |
715 | bool CSKYConstantIslands::isOffsetInRange(unsigned UserOffset, |
716 | unsigned TrialOffset, |
717 | unsigned MaxDisp, bool NegativeOK) { |
718 | if (UserOffset <= TrialOffset) { |
719 | // User before the Trial. |
720 | if (TrialOffset - UserOffset <= MaxDisp) |
721 | return true; |
722 | } else if (NegativeOK) { |
723 | if (UserOffset - TrialOffset <= MaxDisp) |
724 | return true; |
725 | } |
726 | return false; |
727 | } |
728 | |
729 | /// isWaterInRange - Returns true if a CPE placed after the specified |
730 | /// Water (a basic block) will be in range for the specific MI. |
731 | /// |
732 | /// Compute how much the function will grow by inserting a CPE after Water. |
733 | bool CSKYConstantIslands::isWaterInRange(unsigned UserOffset, |
734 | MachineBasicBlock *Water, CPUser &U, |
735 | unsigned &Growth) { |
736 | unsigned CPEOffset = BBInfo[Water->getNumber()].postOffset(); |
737 | unsigned NextBlockOffset; |
738 | Align NextBlockAlignment; |
739 | MachineFunction::const_iterator NextBlock = ++Water->getIterator(); |
740 | if (NextBlock == MF->end()) { |
741 | NextBlockOffset = BBInfo[Water->getNumber()].postOffset(); |
742 | NextBlockAlignment = Align(4); |
743 | } else { |
744 | NextBlockOffset = BBInfo[NextBlock->getNumber()].Offset; |
745 | NextBlockAlignment = NextBlock->getAlignment(); |
746 | } |
747 | unsigned Size = U.CPEMI->getOperand(i: 2).getImm(); |
748 | unsigned CPEEnd = CPEOffset + Size; |
749 | |
750 | // The CPE may be able to hide in the alignment padding before the next |
751 | // block. It may also cause more padding to be required if it is more aligned |
752 | // that the next block. |
753 | if (CPEEnd > NextBlockOffset) { |
754 | Growth = CPEEnd - NextBlockOffset; |
755 | // Compute the padding that would go at the end of the CPE to align the next |
756 | // block. |
757 | Growth += offsetToAlignment(Value: CPEEnd, Alignment: NextBlockAlignment); |
758 | |
759 | // If the CPE is to be inserted before the instruction, that will raise |
760 | // the offset of the instruction. Also account for unknown alignment padding |
761 | // in blocks between CPE and the user. |
762 | if (CPEOffset < UserOffset) |
763 | UserOffset += Growth; |
764 | } else |
765 | // CPE fits in existing padding. |
766 | Growth = 0; |
767 | |
768 | return isOffsetInRange(UserOffset, TrialOffset: CPEOffset, U); |
769 | } |
770 | |
771 | /// isCPEntryInRange - Returns true if the distance between specific MI and |
772 | /// specific ConstPool entry instruction can fit in MI's displacement field. |
773 | bool CSKYConstantIslands::isCPEntryInRange(MachineInstr *MI, |
774 | unsigned UserOffset, |
775 | MachineInstr *CPEMI, |
776 | unsigned MaxDisp, bool NegOk, |
777 | bool DoDump) { |
778 | unsigned CPEOffset = getOffsetOf(MI: CPEMI); |
779 | |
780 | if (DoDump) { |
781 | LLVM_DEBUG({ |
782 | unsigned Block = MI->getParent()->getNumber(); |
783 | const BasicBlockInfo &BBI = BBInfo[Block]; |
784 | dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm() |
785 | << " max delta=" << MaxDisp |
786 | << format(" insn address=%#x" , UserOffset) << " in " |
787 | << printMBBReference(*MI->getParent()) << ": " |
788 | << format("%#x-%x\t" , BBI.Offset, BBI.postOffset()) << *MI |
789 | << format("CPE address=%#x offset=%+d: " , CPEOffset, |
790 | int(CPEOffset - UserOffset)); |
791 | }); |
792 | } |
793 | |
794 | return isOffsetInRange(UserOffset, TrialOffset: CPEOffset, MaxDisp, NegativeOK: NegOk); |
795 | } |
796 | |
797 | #ifndef NDEBUG |
798 | /// BBIsJumpedOver - Return true of the specified basic block's only predecessor |
799 | /// unconditionally branches to its only successor. |
800 | static bool bbIsJumpedOver(MachineBasicBlock *MBB) { |
801 | if (MBB->pred_size() != 1 || MBB->succ_size() != 1) |
802 | return false; |
803 | MachineBasicBlock *Succ = *MBB->succ_begin(); |
804 | MachineBasicBlock *Pred = *MBB->pred_begin(); |
805 | MachineInstr *PredMI = &Pred->back(); |
806 | if (PredMI->getOpcode() == CSKY::BR32 /*TODO: change to 16bit instr. */) |
807 | return PredMI->getOperand(i: 0).getMBB() == Succ; |
808 | return false; |
809 | } |
810 | #endif |
811 | |
812 | void CSKYConstantIslands::adjustBBOffsetsAfter(MachineBasicBlock *BB) { |
813 | unsigned BBNum = BB->getNumber(); |
814 | for (unsigned I = BBNum + 1, E = MF->getNumBlockIDs(); I < E; ++I) { |
815 | // Get the offset and known bits at the end of the layout predecessor. |
816 | // Include the alignment of the current block. |
817 | unsigned Offset = BBInfo[I - 1].Offset + BBInfo[I - 1].Size; |
818 | BBInfo[I].Offset = Offset; |
819 | } |
820 | } |
821 | |
822 | /// decrementCPEReferenceCount - find the constant pool entry with index CPI |
823 | /// and instruction CPEMI, and decrement its refcount. If the refcount |
824 | /// becomes 0 remove the entry and instruction. Returns true if we removed |
825 | /// the entry, false if we didn't. |
826 | bool CSKYConstantIslands::decrementCPEReferenceCount(unsigned CPI, |
827 | MachineInstr *CPEMI) { |
828 | // Find the old entry. Eliminate it if it is no longer used. |
829 | CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); |
830 | assert(CPE && "Unexpected!" ); |
831 | if (--CPE->RefCount == 0) { |
832 | removeDeadCPEMI(CPEMI); |
833 | CPE->CPEMI = nullptr; |
834 | --NumCPEs; |
835 | return true; |
836 | } |
837 | return false; |
838 | } |
839 | |
840 | /// LookForCPEntryInRange - see if the currently referenced CPE is in range; |
841 | /// if not, see if an in-range clone of the CPE is in range, and if so, |
842 | /// change the data structures so the user references the clone. Returns: |
843 | /// 0 = no existing entry found |
844 | /// 1 = entry found, and there were no code insertions or deletions |
845 | /// 2 = entry found, and there were code insertions or deletions |
846 | int CSKYConstantIslands::findInRangeCPEntry(CPUser &U, unsigned UserOffset) { |
847 | MachineInstr *UserMI = U.MI; |
848 | MachineInstr *CPEMI = U.CPEMI; |
849 | |
850 | // Check to see if the CPE is already in-range. |
851 | if (isCPEntryInRange(MI: UserMI, UserOffset, CPEMI, MaxDisp: U.getMaxDisp(), NegOk: U.NegOk, |
852 | DoDump: true)) { |
853 | LLVM_DEBUG(dbgs() << "In range\n" ); |
854 | return 1; |
855 | } |
856 | |
857 | // No. Look for previously created clones of the CPE that are in range. |
858 | unsigned CPI = CPEMI->getOperand(i: 1).getIndex(); |
859 | std::vector<CPEntry> &CPEs = CPEntries[CPI]; |
860 | for (unsigned I = 0, E = CPEs.size(); I != E; ++I) { |
861 | // We already tried this one |
862 | if (CPEs[I].CPEMI == CPEMI) |
863 | continue; |
864 | // Removing CPEs can leave empty entries, skip |
865 | if (CPEs[I].CPEMI == nullptr) |
866 | continue; |
867 | if (isCPEntryInRange(MI: UserMI, UserOffset, CPEMI: CPEs[I].CPEMI, MaxDisp: U.getMaxDisp(), |
868 | NegOk: U.NegOk)) { |
869 | LLVM_DEBUG(dbgs() << "Replacing CPE#" << CPI << " with CPE#" |
870 | << CPEs[I].CPI << "\n" ); |
871 | // Point the CPUser node to the replacement |
872 | U.CPEMI = CPEs[I].CPEMI; |
873 | // Change the CPI in the instruction operand to refer to the clone. |
874 | for (unsigned J = 0, E = UserMI->getNumOperands(); J != E; ++J) |
875 | if (UserMI->getOperand(i: J).isCPI()) { |
876 | UserMI->getOperand(i: J).setIndex(CPEs[I].CPI); |
877 | break; |
878 | } |
879 | // Adjust the refcount of the clone... |
880 | CPEs[I].RefCount++; |
881 | // ...and the original. If we didn't remove the old entry, none of the |
882 | // addresses changed, so we don't need another pass. |
883 | return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1; |
884 | } |
885 | } |
886 | return 0; |
887 | } |
888 | |
889 | /// getUnconditionalBrDisp - Returns the maximum displacement that can fit in |
890 | /// the specific unconditional branch instruction. |
891 | static inline unsigned getUnconditionalBrDisp(int Opc) { |
892 | unsigned Bits, Scale; |
893 | |
894 | switch (Opc) { |
895 | case CSKY::BR16: |
896 | Bits = 10; |
897 | Scale = 2; |
898 | break; |
899 | case CSKY::BR32: |
900 | Bits = 16; |
901 | Scale = 2; |
902 | break; |
903 | default: |
904 | llvm_unreachable("" ); |
905 | } |
906 | |
907 | unsigned MaxOffs = ((1 << (Bits - 1)) - 1) * Scale; |
908 | return MaxOffs; |
909 | } |
910 | |
911 | /// findAvailableWater - Look for an existing entry in the WaterList in which |
912 | /// we can place the CPE referenced from U so it's within range of U's MI. |
913 | /// Returns true if found, false if not. If it returns true, WaterIter |
914 | /// is set to the WaterList entry. |
915 | /// To ensure that this pass |
916 | /// terminates, the CPE location for a particular CPUser is only allowed to |
917 | /// move to a lower address, so search backward from the end of the list and |
918 | /// prefer the first water that is in range. |
919 | bool CSKYConstantIslands::findAvailableWater(CPUser &U, unsigned UserOffset, |
920 | water_iterator &WaterIter) { |
921 | if (WaterList.empty()) |
922 | return false; |
923 | |
924 | unsigned BestGrowth = ~0u; |
925 | for (water_iterator IP = std::prev(x: WaterList.end()), B = WaterList.begin();; |
926 | --IP) { |
927 | MachineBasicBlock *WaterBB = *IP; |
928 | // Check if water is in range and is either at a lower address than the |
929 | // current "high water mark" or a new water block that was created since |
930 | // the previous iteration by inserting an unconditional branch. In the |
931 | // latter case, we want to allow resetting the high water mark back to |
932 | // this new water since we haven't seen it before. Inserting branches |
933 | // should be relatively uncommon and when it does happen, we want to be |
934 | // sure to take advantage of it for all the CPEs near that block, so that |
935 | // we don't insert more branches than necessary. |
936 | unsigned Growth; |
937 | if (isWaterInRange(UserOffset, Water: WaterBB, U, Growth) && |
938 | (WaterBB->getNumber() < U.HighWaterMark->getNumber() || |
939 | NewWaterList.count(Ptr: WaterBB)) && |
940 | Growth < BestGrowth) { |
941 | // This is the least amount of required padding seen so far. |
942 | BestGrowth = Growth; |
943 | WaterIter = IP; |
944 | LLVM_DEBUG(dbgs() << "Found water after " << printMBBReference(*WaterBB) |
945 | << " Growth=" << Growth << '\n'); |
946 | |
947 | // Keep looking unless it is perfect. |
948 | if (BestGrowth == 0) |
949 | return true; |
950 | } |
951 | if (IP == B) |
952 | break; |
953 | } |
954 | return BestGrowth != ~0u; |
955 | } |
956 | |
957 | /// createNewWater - No existing WaterList entry will work for |
958 | /// CPUsers[CPUserIndex], so create a place to put the CPE. The end of the |
959 | /// block is used if in range, and the conditional branch munged so control |
960 | /// flow is correct. Otherwise the block is split to create a hole with an |
961 | /// unconditional branch around it. In either case NewMBB is set to a |
962 | /// block following which the new island can be inserted (the WaterList |
963 | /// is not adjusted). |
964 | void CSKYConstantIslands::createNewWater(unsigned CPUserIndex, |
965 | unsigned UserOffset, |
966 | MachineBasicBlock *&NewMBB) { |
967 | CPUser &U = CPUsers[CPUserIndex]; |
968 | MachineInstr *UserMI = U.MI; |
969 | MachineInstr *CPEMI = U.CPEMI; |
970 | MachineBasicBlock *UserMBB = UserMI->getParent(); |
971 | const BasicBlockInfo &UserBBI = BBInfo[UserMBB->getNumber()]; |
972 | |
973 | // If the block does not end in an unconditional branch already, and if the |
974 | // end of the block is within range, make new water there. |
975 | if (bbHasFallthrough(MBB: UserMBB)) { |
976 | // Size of branch to insert. |
977 | unsigned Delta = 4; |
978 | // Compute the offset where the CPE will begin. |
979 | unsigned CPEOffset = UserBBI.postOffset() + Delta; |
980 | |
981 | if (isOffsetInRange(UserOffset, TrialOffset: CPEOffset, U)) { |
982 | LLVM_DEBUG(dbgs() << "Split at end of " << printMBBReference(*UserMBB) |
983 | << format(", expected CPE offset %#x\n" , CPEOffset)); |
984 | NewMBB = &*++UserMBB->getIterator(); |
985 | // Add an unconditional branch from UserMBB to fallthrough block. Record |
986 | // it for branch lengthening; this new branch will not get out of range, |
987 | // but if the preceding conditional branch is out of range, the targets |
988 | // will be exchanged, and the altered branch may be out of range, so the |
989 | // machinery has to know about it. |
990 | |
991 | // TODO: Add support for 16bit instr. |
992 | int UncondBr = CSKY::BR32; |
993 | auto *NewMI = BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr)) |
994 | .addMBB(NewMBB) |
995 | .getInstr(); |
996 | unsigned MaxDisp = getUnconditionalBrDisp(Opc: UncondBr); |
997 | ImmBranches.push_back( |
998 | x: ImmBranch(&UserMBB->back(), MaxDisp, false, UncondBr)); |
999 | BBInfo[UserMBB->getNumber()].Size += TII->getInstSizeInBytes(MI: *NewMI); |
1000 | adjustBBOffsetsAfter(BB: UserMBB); |
1001 | return; |
1002 | } |
1003 | } |
1004 | |
1005 | // What a big block. Find a place within the block to split it. |
1006 | |
1007 | // Try to split the block so it's fully aligned. Compute the latest split |
1008 | // point where we can add a 4-byte branch instruction, and then align to |
1009 | // Align which is the largest possible alignment in the function. |
1010 | const Align Align = MF->getAlignment(); |
1011 | unsigned BaseInsertOffset = UserOffset + U.getMaxDisp(); |
1012 | LLVM_DEBUG(dbgs() << format("Split in middle of big block before %#x" , |
1013 | BaseInsertOffset)); |
1014 | |
1015 | // The 4 in the following is for the unconditional branch we'll be inserting |
1016 | // Alignment of the island is handled |
1017 | // inside isOffsetInRange. |
1018 | BaseInsertOffset -= 4; |
1019 | |
1020 | LLVM_DEBUG(dbgs() << format(", adjusted to %#x" , BaseInsertOffset) |
1021 | << " la=" << Log2(Align) << '\n'); |
1022 | |
1023 | // This could point off the end of the block if we've already got constant |
1024 | // pool entries following this block; only the last one is in the water list. |
1025 | // Back past any possible branches (allow for a conditional and a maximally |
1026 | // long unconditional). |
1027 | if (BaseInsertOffset + 8 >= UserBBI.postOffset()) { |
1028 | BaseInsertOffset = UserBBI.postOffset() - 8; |
1029 | LLVM_DEBUG(dbgs() << format("Move inside block: %#x\n" , BaseInsertOffset)); |
1030 | } |
1031 | unsigned EndInsertOffset = |
1032 | BaseInsertOffset + 4 + CPEMI->getOperand(i: 2).getImm(); |
1033 | MachineBasicBlock::iterator MI = UserMI; |
1034 | ++MI; |
1035 | unsigned CPUIndex = CPUserIndex + 1; |
1036 | unsigned NumCPUsers = CPUsers.size(); |
1037 | for (unsigned Offset = UserOffset + TII->getInstSizeInBytes(MI: *UserMI); |
1038 | Offset < BaseInsertOffset; |
1039 | Offset += TII->getInstSizeInBytes(MI: *MI), MI = std::next(x: MI)) { |
1040 | assert(MI != UserMBB->end() && "Fell off end of block" ); |
1041 | if (CPUIndex < NumCPUsers && CPUsers[CPUIndex].MI == MI) { |
1042 | CPUser &U = CPUsers[CPUIndex]; |
1043 | if (!isOffsetInRange(UserOffset: Offset, TrialOffset: EndInsertOffset, U)) { |
1044 | // Shift intertion point by one unit of alignment so it is within reach. |
1045 | BaseInsertOffset -= Align.value(); |
1046 | EndInsertOffset -= Align.value(); |
1047 | } |
1048 | // This is overly conservative, as we don't account for CPEMIs being |
1049 | // reused within the block, but it doesn't matter much. Also assume CPEs |
1050 | // are added in order with alignment padding. We may eventually be able |
1051 | // to pack the aligned CPEs better. |
1052 | EndInsertOffset += U.CPEMI->getOperand(i: 2).getImm(); |
1053 | CPUIndex++; |
1054 | } |
1055 | } |
1056 | |
1057 | NewMBB = splitBlockBeforeInstr(MI&: *--MI); |
1058 | } |
1059 | |
1060 | /// handleConstantPoolUser - Analyze the specified user, checking to see if it |
1061 | /// is out-of-range. If so, pick up the constant pool value and move it some |
1062 | /// place in-range. Return true if we changed any addresses (thus must run |
1063 | /// another pass of branch lengthening), false otherwise. |
1064 | bool CSKYConstantIslands::handleConstantPoolUser(unsigned CPUserIndex) { |
1065 | CPUser &U = CPUsers[CPUserIndex]; |
1066 | MachineInstr *UserMI = U.MI; |
1067 | MachineInstr *CPEMI = U.CPEMI; |
1068 | unsigned CPI = CPEMI->getOperand(i: 1).getIndex(); |
1069 | unsigned Size = CPEMI->getOperand(i: 2).getImm(); |
1070 | // Compute this only once, it's expensive. |
1071 | unsigned UserOffset = getUserOffset(U); |
1072 | |
1073 | // See if the current entry is within range, or there is a clone of it |
1074 | // in range. |
1075 | int result = findInRangeCPEntry(U, UserOffset); |
1076 | if (result == 1) |
1077 | return false; |
1078 | if (result == 2) |
1079 | return true; |
1080 | |
1081 | // Look for water where we can place this CPE. |
1082 | MachineBasicBlock *NewIsland = MF->CreateMachineBasicBlock(); |
1083 | MachineBasicBlock *NewMBB; |
1084 | water_iterator IP; |
1085 | if (findAvailableWater(U, UserOffset, WaterIter&: IP)) { |
1086 | LLVM_DEBUG(dbgs() << "Found water in range\n" ); |
1087 | MachineBasicBlock *WaterBB = *IP; |
1088 | |
1089 | // If the original WaterList entry was "new water" on this iteration, |
1090 | // propagate that to the new island. This is just keeping NewWaterList |
1091 | // updated to match the WaterList, which will be updated below. |
1092 | if (NewWaterList.erase(Ptr: WaterBB)) |
1093 | NewWaterList.insert(Ptr: NewIsland); |
1094 | |
1095 | // The new CPE goes before the following block (NewMBB). |
1096 | NewMBB = &*++WaterBB->getIterator(); |
1097 | } else { |
1098 | LLVM_DEBUG(dbgs() << "No water found\n" ); |
1099 | createNewWater(CPUserIndex, UserOffset, NewMBB); |
1100 | |
1101 | // splitBlockBeforeInstr adds to WaterList, which is important when it is |
1102 | // called while handling branches so that the water will be seen on the |
1103 | // next iteration for constant pools, but in this context, we don't want |
1104 | // it. Check for this so it will be removed from the WaterList. |
1105 | // Also remove any entry from NewWaterList. |
1106 | MachineBasicBlock *WaterBB = &*--NewMBB->getIterator(); |
1107 | IP = llvm::find(Range&: WaterList, Val: WaterBB); |
1108 | if (IP != WaterList.end()) |
1109 | NewWaterList.erase(Ptr: WaterBB); |
1110 | |
1111 | // We are adding new water. Update NewWaterList. |
1112 | NewWaterList.insert(Ptr: NewIsland); |
1113 | } |
1114 | |
1115 | // Remove the original WaterList entry; we want subsequent insertions in |
1116 | // this vicinity to go after the one we're about to insert. This |
1117 | // considerably reduces the number of times we have to move the same CPE |
1118 | // more than once and is also important to ensure the algorithm terminates. |
1119 | if (IP != WaterList.end()) |
1120 | WaterList.erase(position: IP); |
1121 | |
1122 | // Okay, we know we can put an island before NewMBB now, do it! |
1123 | MF->insert(MBBI: NewMBB->getIterator(), MBB: NewIsland); |
1124 | |
1125 | // Update internal data structures to account for the newly inserted MBB. |
1126 | updateForInsertedWaterBlock(NewBB: NewIsland); |
1127 | |
1128 | // Decrement the old entry, and remove it if refcount becomes 0. |
1129 | decrementCPEReferenceCount(CPI, CPEMI); |
1130 | |
1131 | // No existing clone of this CPE is within range. |
1132 | // We will be generating a new clone. Get a UID for it. |
1133 | unsigned ID = createPICLabelUId(); |
1134 | |
1135 | // Now that we have an island to add the CPE to, clone the original CPE and |
1136 | // add it to the island. |
1137 | U.HighWaterMark = NewIsland; |
1138 | U.CPEMI = BuildMI(NewIsland, DebugLoc(), TII->get(CSKY::CONSTPOOL_ENTRY)) |
1139 | .addImm(ID) |
1140 | .addConstantPoolIndex(CPI) |
1141 | .addImm(Size); |
1142 | CPEntries[CPI].push_back(x: CPEntry(U.CPEMI, ID, 1)); |
1143 | ++NumCPEs; |
1144 | |
1145 | // Mark the basic block as aligned as required by the const-pool entry. |
1146 | NewIsland->setAlignment(getCPEAlign(CPEMI: *U.CPEMI)); |
1147 | |
1148 | // Increase the size of the island block to account for the new entry. |
1149 | BBInfo[NewIsland->getNumber()].Size += Size; |
1150 | adjustBBOffsetsAfter(BB: &*--NewIsland->getIterator()); |
1151 | |
1152 | // Finally, change the CPI in the instruction operand to be ID. |
1153 | for (unsigned I = 0, E = UserMI->getNumOperands(); I != E; ++I) |
1154 | if (UserMI->getOperand(i: I).isCPI()) { |
1155 | UserMI->getOperand(i: I).setIndex(ID); |
1156 | break; |
1157 | } |
1158 | |
1159 | LLVM_DEBUG( |
1160 | dbgs() << " Moved CPE to #" << ID << " CPI=" << CPI |
1161 | << format(" offset=%#x\n" , BBInfo[NewIsland->getNumber()].Offset)); |
1162 | |
1163 | return true; |
1164 | } |
1165 | |
1166 | /// removeDeadCPEMI - Remove a dead constant pool entry instruction. Update |
1167 | /// sizes and offsets of impacted basic blocks. |
1168 | void CSKYConstantIslands::removeDeadCPEMI(MachineInstr *CPEMI) { |
1169 | MachineBasicBlock *CPEBB = CPEMI->getParent(); |
1170 | unsigned Size = CPEMI->getOperand(i: 2).getImm(); |
1171 | CPEMI->eraseFromParent(); |
1172 | BBInfo[CPEBB->getNumber()].Size -= Size; |
1173 | // All succeeding offsets have the current size value added in, fix this. |
1174 | if (CPEBB->empty()) { |
1175 | BBInfo[CPEBB->getNumber()].Size = 0; |
1176 | |
1177 | // This block no longer needs to be aligned. |
1178 | CPEBB->setAlignment(Align(4)); |
1179 | } else { |
1180 | // Entries are sorted by descending alignment, so realign from the front. |
1181 | CPEBB->setAlignment(getCPEAlign(CPEMI: *CPEBB->begin())); |
1182 | } |
1183 | |
1184 | adjustBBOffsetsAfter(BB: CPEBB); |
1185 | // An island has only one predecessor BB and one successor BB. Check if |
1186 | // this BB's predecessor jumps directly to this BB's successor. This |
1187 | // shouldn't happen currently. |
1188 | assert(!bbIsJumpedOver(CPEBB) && "How did this happen?" ); |
1189 | // FIXME: remove the empty blocks after all the work is done? |
1190 | } |
1191 | |
1192 | /// removeUnusedCPEntries - Remove constant pool entries whose refcounts |
1193 | /// are zero. |
1194 | bool CSKYConstantIslands::removeUnusedCPEntries() { |
1195 | unsigned MadeChange = false; |
1196 | for (unsigned I = 0, E = CPEntries.size(); I != E; ++I) { |
1197 | std::vector<CPEntry> &CPEs = CPEntries[I]; |
1198 | for (unsigned J = 0, Ee = CPEs.size(); J != Ee; ++J) { |
1199 | if (CPEs[J].RefCount == 0 && CPEs[J].CPEMI) { |
1200 | removeDeadCPEMI(CPEMI: CPEs[J].CPEMI); |
1201 | CPEs[J].CPEMI = nullptr; |
1202 | MadeChange = true; |
1203 | } |
1204 | } |
1205 | } |
1206 | return MadeChange; |
1207 | } |
1208 | |
1209 | /// isBBInRange - Returns true if the distance between specific MI and |
1210 | /// specific BB can fit in MI's displacement field. |
1211 | bool CSKYConstantIslands::isBBInRange(MachineInstr *MI, |
1212 | MachineBasicBlock *DestBB, |
1213 | unsigned MaxDisp) { |
1214 | unsigned BrOffset = getOffsetOf(MI); |
1215 | unsigned DestOffset = BBInfo[DestBB->getNumber()].Offset; |
1216 | |
1217 | LLVM_DEBUG(dbgs() << "Branch of destination " << printMBBReference(*DestBB) |
1218 | << " from " << printMBBReference(*MI->getParent()) |
1219 | << " max delta=" << MaxDisp << " from " << getOffsetOf(MI) |
1220 | << " to " << DestOffset << " offset " |
1221 | << int(DestOffset - BrOffset) << "\t" << *MI); |
1222 | |
1223 | if (BrOffset <= DestOffset) { |
1224 | // Branch before the Dest. |
1225 | if (DestOffset - BrOffset <= MaxDisp) |
1226 | return true; |
1227 | } else { |
1228 | if (BrOffset - DestOffset <= MaxDisp) |
1229 | return true; |
1230 | } |
1231 | return false; |
1232 | } |
1233 | |
1234 | /// fixupImmediateBr - Fix up an immediate branch whose destination is too far |
1235 | /// away to fit in its displacement field. |
1236 | bool CSKYConstantIslands::fixupImmediateBr(ImmBranch &Br) { |
1237 | MachineInstr *MI = Br.MI; |
1238 | MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI: *MI); |
1239 | |
1240 | // Check to see if the DestBB is already in-range. |
1241 | if (isBBInRange(MI, DestBB, MaxDisp: Br.MaxDisp)) |
1242 | return false; |
1243 | |
1244 | if (!Br.IsCond) |
1245 | return fixupUnconditionalBr(Br); |
1246 | return fixupConditionalBr(Br); |
1247 | } |
1248 | |
1249 | /// fixupUnconditionalBr - Fix up an unconditional branch whose destination is |
1250 | /// too far away to fit in its displacement field. If the LR register has been |
1251 | /// spilled in the epilogue, then we can use BSR to implement a far jump. |
1252 | /// Otherwise, add an intermediate branch instruction to a branch. |
1253 | bool CSKYConstantIslands::fixupUnconditionalBr(ImmBranch &Br) { |
1254 | MachineInstr *MI = Br.MI; |
1255 | MachineBasicBlock *MBB = MI->getParent(); |
1256 | |
1257 | if (!MFI->isLRSpilled()) |
1258 | report_fatal_error(reason: "underestimated function size" ); |
1259 | |
1260 | // Use BSR to implement far jump. |
1261 | Br.MaxDisp = ((1 << (26 - 1)) - 1) * 2; |
1262 | MI->setDesc(TII->get(CSKY::BSR32_BR)); |
1263 | BBInfo[MBB->getNumber()].Size += 4; |
1264 | adjustBBOffsetsAfter(BB: MBB); |
1265 | ++NumUBrFixed; |
1266 | |
1267 | LLVM_DEBUG(dbgs() << " Changed B to long jump " << *MI); |
1268 | |
1269 | return true; |
1270 | } |
1271 | |
1272 | /// fixupConditionalBr - Fix up a conditional branch whose destination is too |
1273 | /// far away to fit in its displacement field. It is converted to an inverse |
1274 | /// conditional branch + an unconditional branch to the destination. |
1275 | bool CSKYConstantIslands::fixupConditionalBr(ImmBranch &Br) { |
1276 | MachineInstr *MI = Br.MI; |
1277 | MachineBasicBlock *DestBB = TII->getBranchDestBlock(MI: *MI); |
1278 | |
1279 | SmallVector<MachineOperand, 4> Cond; |
1280 | Cond.push_back(Elt: MachineOperand::CreateImm(Val: MI->getOpcode())); |
1281 | Cond.push_back(Elt: MI->getOperand(i: 0)); |
1282 | TII->reverseBranchCondition(Cond); |
1283 | |
1284 | // Add an unconditional branch to the destination and invert the branch |
1285 | // condition to jump over it: |
1286 | // bteqz L1 |
1287 | // => |
1288 | // bnez L2 |
1289 | // b L1 |
1290 | // L2: |
1291 | |
1292 | // If the branch is at the end of its MBB and that has a fall-through block, |
1293 | // direct the updated conditional branch to the fall-through block. Otherwise, |
1294 | // split the MBB before the next instruction. |
1295 | MachineBasicBlock *MBB = MI->getParent(); |
1296 | MachineInstr *BMI = &MBB->back(); |
1297 | bool NeedSplit = (BMI != MI) || !bbHasFallthrough(MBB); |
1298 | |
1299 | ++NumCBrFixed; |
1300 | if (BMI != MI) { |
1301 | if (std::next(x: MachineBasicBlock::iterator(MI)) == std::prev(x: MBB->end()) && |
1302 | BMI->isUnconditionalBranch()) { |
1303 | // Last MI in the BB is an unconditional branch. Can we simply invert the |
1304 | // condition and swap destinations: |
1305 | // beqz L1 |
1306 | // b L2 |
1307 | // => |
1308 | // bnez L2 |
1309 | // b L1 |
1310 | MachineBasicBlock *NewDest = TII->getBranchDestBlock(MI: *BMI); |
1311 | if (isBBInRange(MI, DestBB: NewDest, MaxDisp: Br.MaxDisp)) { |
1312 | LLVM_DEBUG( |
1313 | dbgs() << " Invert Bcc condition and swap its destination with " |
1314 | << *BMI); |
1315 | BMI->getOperand(i: BMI->getNumExplicitOperands() - 1).setMBB(DestBB); |
1316 | MI->getOperand(i: MI->getNumExplicitOperands() - 1).setMBB(NewDest); |
1317 | |
1318 | MI->setDesc(TII->get(Cond[0].getImm())); |
1319 | return true; |
1320 | } |
1321 | } |
1322 | } |
1323 | |
1324 | if (NeedSplit) { |
1325 | splitBlockBeforeInstr(MI&: *MI); |
1326 | // No need for the branch to the next block. We're adding an unconditional |
1327 | // branch to the destination. |
1328 | int Delta = TII->getInstSizeInBytes(MI: MBB->back()); |
1329 | BBInfo[MBB->getNumber()].Size -= Delta; |
1330 | MBB->back().eraseFromParent(); |
1331 | // BBInfo[SplitBB].Offset is wrong temporarily, fixed below |
1332 | |
1333 | // The conditional successor will be swapped between the BBs after this, so |
1334 | // update CFG. |
1335 | MBB->addSuccessor(Succ: DestBB); |
1336 | std::next(x: MBB->getIterator())->removeSuccessor(Succ: DestBB); |
1337 | } |
1338 | MachineBasicBlock *NextBB = &*++MBB->getIterator(); |
1339 | |
1340 | LLVM_DEBUG(dbgs() << " Insert B to " << printMBBReference(*DestBB) |
1341 | << " also invert condition and change dest. to " |
1342 | << printMBBReference(*NextBB) << "\n" ); |
1343 | |
1344 | // Insert a new conditional branch and a new unconditional branch. |
1345 | // Also update the ImmBranch as well as adding a new entry for the new branch. |
1346 | |
1347 | BuildMI(MBB, DebugLoc(), TII->get(Cond[0].getImm())) |
1348 | .addReg(MI->getOperand(i: 0).getReg()) |
1349 | .addMBB(NextBB); |
1350 | |
1351 | Br.MI = &MBB->back(); |
1352 | BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MI: MBB->back()); |
1353 | BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr)).addMBB(DestBB); |
1354 | BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MI: MBB->back()); |
1355 | unsigned MaxDisp = getUnconditionalBrDisp(Opc: Br.UncondBr); |
1356 | ImmBranches.push_back(x: ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr)); |
1357 | |
1358 | // Remove the old conditional branch. It may or may not still be in MBB. |
1359 | BBInfo[MI->getParent()->getNumber()].Size -= TII->getInstSizeInBytes(MI: *MI); |
1360 | MI->eraseFromParent(); |
1361 | adjustBBOffsetsAfter(BB: MBB); |
1362 | return true; |
1363 | } |
1364 | |
1365 | /// Returns a pass that converts branches to long branches. |
1366 | FunctionPass *llvm::createCSKYConstantIslandPass() { |
1367 | return new CSKYConstantIslands(); |
1368 | } |
1369 | |
1370 | INITIALIZE_PASS(CSKYConstantIslands, DEBUG_TYPE, |
1371 | "CSKY constant island placement and branch shortening pass" , |
1372 | false, false) |
1373 | |