1 //===-- ARMConstantIslandPass.cpp - ARM constant islands --------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file contains a pass that splits the constant pool up into 'islands'
11 // which are scattered through-out the function. This is required due to the
12 // limited pc-relative displacements that ARM has.
14 //===----------------------------------------------------------------------===//
16 #define DEBUG_TYPE "arm-cp-islands"
18 #include "ARMAddressingModes.h"
19 #include "ARMMachineFunctionInfo.h"
20 #include "ARMInstrInfo.h"
21 #include "llvm/CodeGen/MachineConstantPool.h"
22 #include "llvm/CodeGen/MachineFunctionPass.h"
23 #include "llvm/CodeGen/MachineInstrBuilder.h"
24 #include "llvm/CodeGen/MachineJumpTableInfo.h"
25 #include "llvm/Target/TargetData.h"
26 #include "llvm/Target/TargetMachine.h"
27 #include "llvm/Support/Debug.h"
28 #include "llvm/Support/ErrorHandling.h"
29 #include "llvm/Support/raw_ostream.h"
30 #include "llvm/ADT/SmallSet.h"
31 #include "llvm/ADT/SmallVector.h"
32 #include "llvm/ADT/STLExtras.h"
33 #include "llvm/ADT/Statistic.h"
37 STATISTIC(NumCPEs
, "Number of constpool entries");
38 STATISTIC(NumSplit
, "Number of uncond branches inserted");
39 STATISTIC(NumCBrFixed
, "Number of cond branches fixed");
40 STATISTIC(NumUBrFixed
, "Number of uncond branches fixed");
41 STATISTIC(NumTBs
, "Number of table branches generated");
42 STATISTIC(NumT2CPShrunk
, "Number of Thumb2 constantpool instructions shrunk");
43 STATISTIC(NumT2BrShrunk
, "Number of Thumb2 immediate branches shrunk");
46 /// ARMConstantIslands - Due to limited PC-relative displacements, ARM
47 /// requires constant pool entries to be scattered among the instructions
48 /// inside a function. To do this, it completely ignores the normal LLVM
49 /// constant pool; instead, it places constants wherever it feels like with
50 /// special instructions.
52 /// The terminology used in this pass includes:
53 /// Islands - Clumps of constants placed in the function.
54 /// Water - Potential places where an island could be formed.
55 /// CPE - A constant pool entry that has been placed somewhere, which
56 /// tracks a list of users.
57 class ARMConstantIslands
: public MachineFunctionPass
{
58 /// BBSizes - The size of each MachineBasicBlock in bytes of code, indexed
59 /// by MBB Number. The two-byte pads required for Thumb alignment are
60 /// counted as part of the following block (i.e., the offset and size for
61 /// a padded block will both be ==2 mod 4).
62 std::vector
<unsigned> BBSizes
;
64 /// BBOffsets - the offset of each MBB in bytes, starting from 0.
65 /// The two-byte pads required for Thumb alignment are counted as part of
66 /// the following block.
67 std::vector
<unsigned> BBOffsets
;
69 /// WaterList - A sorted list of basic blocks where islands could be placed
70 /// (i.e. blocks that don't fall through to the following block, due
71 /// to a return, unreachable, or unconditional branch).
72 std::vector
<MachineBasicBlock
*> WaterList
;
74 /// NewWaterList - The subset of WaterList that was created since the
75 /// previous iteration by inserting unconditional branches.
76 SmallSet
<MachineBasicBlock
*, 4> NewWaterList
;
78 typedef std::vector
<MachineBasicBlock
*>::iterator water_iterator
;
80 /// CPUser - One user of a constant pool, keeping the machine instruction
81 /// pointer, the constant pool being referenced, and the max displacement
82 /// allowed from the instruction to the CP. The HighWaterMark records the
83 /// highest basic block where a new CPEntry can be placed. To ensure this
84 /// pass terminates, the CP entries are initially placed at the end of the
85 /// function and then move monotonically to lower addresses. The
86 /// exception to this rule is when the current CP entry for a particular
87 /// CPUser is out of range, but there is another CP entry for the same
88 /// constant value in range. We want to use the existing in-range CP
89 /// entry, but if it later moves out of range, the search for new water
90 /// should resume where it left off. The HighWaterMark is used to record
95 MachineBasicBlock
*HighWaterMark
;
99 CPUser(MachineInstr
*mi
, MachineInstr
*cpemi
, unsigned maxdisp
,
100 bool neg
, bool soimm
)
101 : MI(mi
), CPEMI(cpemi
), MaxDisp(maxdisp
), NegOk(neg
), IsSoImm(soimm
) {
102 HighWaterMark
= CPEMI
->getParent();
106 /// CPUsers - Keep track of all of the machine instructions that use various
107 /// constant pools and their max displacement.
108 std::vector
<CPUser
> CPUsers
;
110 /// CPEntry - One per constant pool entry, keeping the machine instruction
111 /// pointer, the constpool index, and the number of CPUser's which
112 /// reference this entry.
117 CPEntry(MachineInstr
*cpemi
, unsigned cpi
, unsigned rc
= 0)
118 : CPEMI(cpemi
), CPI(cpi
), RefCount(rc
) {}
121 /// CPEntries - Keep track of all of the constant pool entry machine
122 /// instructions. For each original constpool index (i.e. those that
123 /// existed upon entry to this pass), it keeps a vector of entries.
124 /// Original elements are cloned as we go along; the clones are
125 /// put in the vector of the original element, but have distinct CPIs.
126 std::vector
<std::vector
<CPEntry
> > CPEntries
;
128 /// ImmBranch - One per immediate branch, keeping the machine instruction
129 /// pointer, conditional or unconditional, the max displacement,
130 /// and (if isCond is true) the corresponding unconditional branch
134 unsigned MaxDisp
: 31;
137 ImmBranch(MachineInstr
*mi
, unsigned maxdisp
, bool cond
, int ubr
)
138 : MI(mi
), MaxDisp(maxdisp
), isCond(cond
), UncondBr(ubr
) {}
141 /// ImmBranches - Keep track of all the immediate branch instructions.
143 std::vector
<ImmBranch
> ImmBranches
;
145 /// PushPopMIs - Keep track of all the Thumb push / pop instructions.
147 SmallVector
<MachineInstr
*, 4> PushPopMIs
;
149 /// T2JumpTables - Keep track of all the Thumb2 jumptable instructions.
150 SmallVector
<MachineInstr
*, 4> T2JumpTables
;
152 /// HasFarJump - True if any far jump instruction has been emitted during
153 /// the branch fix up pass.
156 const TargetInstrInfo
*TII
;
157 const ARMSubtarget
*STI
;
158 ARMFunctionInfo
*AFI
;
164 ARMConstantIslands() : MachineFunctionPass(&ID
) {}
166 virtual bool runOnMachineFunction(MachineFunction
&MF
);
168 virtual const char *getPassName() const {
169 return "ARM constant island placement and branch shortening pass";
173 void DoInitialPlacement(MachineFunction
&MF
,
174 std::vector
<MachineInstr
*> &CPEMIs
);
175 CPEntry
*findConstPoolEntry(unsigned CPI
, const MachineInstr
*CPEMI
);
176 void InitialFunctionScan(MachineFunction
&MF
,
177 const std::vector
<MachineInstr
*> &CPEMIs
);
178 MachineBasicBlock
*SplitBlockBeforeInstr(MachineInstr
*MI
);
179 void UpdateForInsertedWaterBlock(MachineBasicBlock
*NewBB
);
180 void AdjustBBOffsetsAfter(MachineBasicBlock
*BB
, int delta
);
181 bool DecrementOldEntry(unsigned CPI
, MachineInstr
* CPEMI
);
182 int LookForExistingCPEntry(CPUser
& U
, unsigned UserOffset
);
183 bool LookForWater(CPUser
&U
, unsigned UserOffset
, water_iterator
&WaterIter
);
184 void CreateNewWater(unsigned CPUserIndex
, unsigned UserOffset
,
185 MachineBasicBlock
*&NewMBB
);
186 bool HandleConstantPoolUser(MachineFunction
&MF
, unsigned CPUserIndex
);
187 void RemoveDeadCPEMI(MachineInstr
*CPEMI
);
188 bool RemoveUnusedCPEntries();
189 bool CPEIsInRange(MachineInstr
*MI
, unsigned UserOffset
,
190 MachineInstr
*CPEMI
, unsigned Disp
, bool NegOk
,
191 bool DoDump
= false);
192 bool WaterIsInRange(unsigned UserOffset
, MachineBasicBlock
*Water
,
194 bool OffsetIsInRange(unsigned UserOffset
, unsigned TrialOffset
,
195 unsigned Disp
, bool NegativeOK
, bool IsSoImm
= false);
196 bool BBIsInRange(MachineInstr
*MI
, MachineBasicBlock
*BB
, unsigned Disp
);
197 bool FixUpImmediateBr(MachineFunction
&MF
, ImmBranch
&Br
);
198 bool FixUpConditionalBr(MachineFunction
&MF
, ImmBranch
&Br
);
199 bool FixUpUnconditionalBr(MachineFunction
&MF
, ImmBranch
&Br
);
200 bool UndoLRSpillRestore();
201 bool OptimizeThumb2Instructions(MachineFunction
&MF
);
202 bool OptimizeThumb2Branches(MachineFunction
&MF
);
203 bool OptimizeThumb2JumpTables(MachineFunction
&MF
);
205 unsigned GetOffsetOf(MachineInstr
*MI
) const;
207 void verify(MachineFunction
&MF
);
209 char ARMConstantIslands::ID
= 0;
212 /// verify - check BBOffsets, BBSizes, alignment of islands
213 void ARMConstantIslands::verify(MachineFunction
&MF
) {
214 assert(BBOffsets
.size() == BBSizes
.size());
215 for (unsigned i
= 1, e
= BBOffsets
.size(); i
!= e
; ++i
)
216 assert(BBOffsets
[i
-1]+BBSizes
[i
-1] == BBOffsets
[i
]);
220 for (MachineFunction::iterator MBBI
= MF
.begin(), E
= MF
.end();
222 MachineBasicBlock
*MBB
= MBBI
;
224 MBB
->begin()->getOpcode() == ARM::CONSTPOOL_ENTRY
) {
225 unsigned MBBId
= MBB
->getNumber();
226 assert((BBOffsets
[MBBId
]%4 == 0 && BBSizes
[MBBId
]%4 == 0) ||
227 (BBOffsets
[MBBId
]%4 != 0 && BBSizes
[MBBId
]%4 != 0));
233 /// print block size and offset information - debugging
234 void ARMConstantIslands::dumpBBs() {
235 for (unsigned J
= 0, E
= BBOffsets
.size(); J
!=E
; ++J
) {
236 DEBUG(errs() << "block " << J
<< " offset " << BBOffsets
[J
]
237 << " size " << BBSizes
[J
] << "\n");
241 /// createARMConstantIslandPass - returns an instance of the constpool
243 FunctionPass
*llvm::createARMConstantIslandPass() {
244 return new ARMConstantIslands();
247 bool ARMConstantIslands::runOnMachineFunction(MachineFunction
&MF
) {
248 MachineConstantPool
&MCP
= *MF
.getConstantPool();
250 TII
= MF
.getTarget().getInstrInfo();
251 AFI
= MF
.getInfo
<ARMFunctionInfo
>();
252 STI
= &MF
.getTarget().getSubtarget
<ARMSubtarget
>();
254 isThumb
= AFI
->isThumbFunction();
255 isThumb1
= AFI
->isThumb1OnlyFunction();
256 isThumb2
= AFI
->isThumb2Function();
260 // Renumber all of the machine basic blocks in the function, guaranteeing that
261 // the numbers agree with the position of the block in the function.
264 // Thumb1 functions containing constant pools get 4-byte alignment.
265 // This is so we can keep exact track of where the alignment padding goes.
267 // Set default. Thumb1 function is 2-byte aligned, ARM and Thumb2 are 4-byte
269 AFI
->setAlign(isThumb1
? 1U : 2U);
271 // Perform the initial placement of the constant pool entries. To start with,
272 // we put them all at the end of the function.
273 std::vector
<MachineInstr
*> CPEMIs
;
274 if (!MCP
.isEmpty()) {
275 DoInitialPlacement(MF
, CPEMIs
);
280 /// The next UID to take is the first unused one.
281 AFI
->initConstPoolEntryUId(CPEMIs
.size());
283 // Do the initial scan of the function, building up information about the
284 // sizes of each block, the location of all the water, and finding all of the
285 // constant pool users.
286 InitialFunctionScan(MF
, CPEMIs
);
289 /// Remove dead constant pool entries.
290 RemoveUnusedCPEntries();
292 // Iteratively place constant pool entries and fix up branches until there
294 bool MadeChange
= false;
295 unsigned NoCPIters
= 0, NoBRIters
= 0;
297 bool CPChange
= false;
298 for (unsigned i
= 0, e
= CPUsers
.size(); i
!= e
; ++i
)
299 CPChange
|= HandleConstantPoolUser(MF
, i
);
300 if (CPChange
&& ++NoCPIters
> 30)
301 llvm_unreachable("Constant Island pass failed to converge!");
304 // Clear NewWaterList now. If we split a block for branches, it should
305 // appear as "new water" for the next iteration of constant pool placement.
306 NewWaterList
.clear();
308 bool BRChange
= false;
309 for (unsigned i
= 0, e
= ImmBranches
.size(); i
!= e
; ++i
)
310 BRChange
|= FixUpImmediateBr(MF
, ImmBranches
[i
]);
311 if (BRChange
&& ++NoBRIters
> 30)
312 llvm_unreachable("Branch Fix Up pass failed to converge!");
315 if (!CPChange
&& !BRChange
)
320 // Shrink 32-bit Thumb2 branch, load, and store instructions.
322 MadeChange
|= OptimizeThumb2Instructions(MF
);
324 // After a while, this might be made debug-only, but it is not expensive.
327 // If LR has been forced spilled and no far jumps (i.e. BL) has been issued.
328 // Undo the spill / restore of LR if possible.
329 if (isThumb
&& !HasFarJump
&& AFI
->isLRSpilledForFarJump())
330 MadeChange
|= UndoLRSpillRestore();
339 T2JumpTables
.clear();
344 /// DoInitialPlacement - Perform the initial placement of the constant pool
345 /// entries. To start with, we put them all at the end of the function.
346 void ARMConstantIslands::DoInitialPlacement(MachineFunction
&MF
,
347 std::vector
<MachineInstr
*> &CPEMIs
) {
348 // Create the basic block to hold the CPE's.
349 MachineBasicBlock
*BB
= MF
.CreateMachineBasicBlock();
352 // Add all of the constants from the constant pool to the end block, use an
353 // identity mapping of CPI's to CPE's.
354 const std::vector
<MachineConstantPoolEntry
> &CPs
=
355 MF
.getConstantPool()->getConstants();
357 const TargetData
&TD
= *MF
.getTarget().getTargetData();
358 for (unsigned i
= 0, e
= CPs
.size(); i
!= e
; ++i
) {
359 unsigned Size
= TD
.getTypeAllocSize(CPs
[i
].getType());
360 // Verify that all constant pool entries are a multiple of 4 bytes. If not,
361 // we would have to pad them out or something so that instructions stay
363 assert((Size
& 3) == 0 && "CP Entry not multiple of 4 bytes!");
364 MachineInstr
*CPEMI
=
365 BuildMI(BB
, DebugLoc::getUnknownLoc(), TII
->get(ARM::CONSTPOOL_ENTRY
))
366 .addImm(i
).addConstantPoolIndex(i
).addImm(Size
);
367 CPEMIs
.push_back(CPEMI
);
369 // Add a new CPEntry, but no corresponding CPUser yet.
370 std::vector
<CPEntry
> CPEs
;
371 CPEs
.push_back(CPEntry(CPEMI
, i
));
372 CPEntries
.push_back(CPEs
);
374 DEBUG(errs() << "Moved CPI#" << i
<< " to end of function as #" << i
379 /// BBHasFallthrough - Return true if the specified basic block can fallthrough
380 /// into the block immediately after it.
381 static bool BBHasFallthrough(MachineBasicBlock
*MBB
) {
382 // Get the next machine basic block in the function.
383 MachineFunction::iterator MBBI
= MBB
;
384 if (next(MBBI
) == MBB
->getParent()->end()) // Can't fall off end of function.
387 MachineBasicBlock
*NextBB
= next(MBBI
);
388 for (MachineBasicBlock::succ_iterator I
= MBB
->succ_begin(),
389 E
= MBB
->succ_end(); I
!= E
; ++I
)
396 /// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI,
397 /// look up the corresponding CPEntry.
398 ARMConstantIslands::CPEntry
399 *ARMConstantIslands::findConstPoolEntry(unsigned CPI
,
400 const MachineInstr
*CPEMI
) {
401 std::vector
<CPEntry
> &CPEs
= CPEntries
[CPI
];
402 // Number of entries per constpool index should be small, just do a
404 for (unsigned i
= 0, e
= CPEs
.size(); i
!= e
; ++i
) {
405 if (CPEs
[i
].CPEMI
== CPEMI
)
411 /// InitialFunctionScan - Do the initial scan of the function, building up
412 /// information about the sizes of each block, the location of all the water,
413 /// and finding all of the constant pool users.
414 void ARMConstantIslands::InitialFunctionScan(MachineFunction
&MF
,
415 const std::vector
<MachineInstr
*> &CPEMIs
) {
417 for (MachineFunction::iterator MBBI
= MF
.begin(), E
= MF
.end();
419 MachineBasicBlock
&MBB
= *MBBI
;
421 // If this block doesn't fall through into the next MBB, then this is
422 // 'water' that a constant pool island could be placed.
423 if (!BBHasFallthrough(&MBB
))
424 WaterList
.push_back(&MBB
);
426 unsigned MBBSize
= 0;
427 for (MachineBasicBlock::iterator I
= MBB
.begin(), E
= MBB
.end();
429 // Add instruction size to MBBSize.
430 MBBSize
+= TII
->GetInstSizeInBytes(I
);
432 int Opc
= I
->getOpcode();
433 if (I
->getDesc().isBranch()) {
440 continue; // Ignore other JT branches
442 // A Thumb1 table jump may involve padding; for the offsets to
443 // be right, functions containing these must be 4-byte aligned.
445 if ((Offset
+MBBSize
)%4 != 0)
446 // FIXME: Add a pseudo ALIGN instruction instead.
447 MBBSize
+= 2; // padding
448 continue; // Does not get an entry in ImmBranches
450 T2JumpTables
.push_back(I
);
451 continue; // Does not get an entry in ImmBranches
482 // Record this immediate branch.
483 unsigned MaxOffs
= ((1 << (Bits
-1))-1) * Scale
;
484 ImmBranches
.push_back(ImmBranch(I
, MaxOffs
, isCond
, UOpc
));
487 if (Opc
== ARM::tPUSH
|| Opc
== ARM::tPOP_RET
)
488 PushPopMIs
.push_back(I
);
490 if (Opc
== ARM::CONSTPOOL_ENTRY
)
493 // Scan the instructions for constant pool operands.
494 for (unsigned op
= 0, e
= I
->getNumOperands(); op
!= e
; ++op
)
495 if (I
->getOperand(op
).isCPI()) {
496 // We found one. The addressing mode tells us the max displacement
497 // from the PC that this instruction permits.
499 // Basic size info comes from the TSFlags field.
503 bool IsSoImm
= false;
507 llvm_unreachable("Unknown addressing mode for CP reference!");
510 // Taking the address of a CP entry.
512 // This takes a SoImm, which is 8 bit immediate rotated. We'll
513 // pretend the maximum offset is 255 * 4. Since each instruction
514 // 4 byte wide, this is always correct. We'llc heck for other
515 // displacements that fits in a SoImm as well.
521 case ARM::t2LEApcrel
:
533 Bits
= 12; // +-offset_12
540 Scale
= 4; // +(offset_8*4)
546 Scale
= 4; // +-(offset_8*4)
551 // Remember that this is a user of a CP entry.
552 unsigned CPI
= I
->getOperand(op
).getIndex();
553 MachineInstr
*CPEMI
= CPEMIs
[CPI
];
554 unsigned MaxOffs
= ((1 << Bits
)-1) * Scale
;
555 CPUsers
.push_back(CPUser(I
, CPEMI
, MaxOffs
, NegOk
, IsSoImm
));
557 // Increment corresponding CPEntry reference count.
558 CPEntry
*CPE
= findConstPoolEntry(CPI
, CPEMI
);
559 assert(CPE
&& "Cannot find a corresponding CPEntry!");
562 // Instructions can only use one CP entry, don't bother scanning the
563 // rest of the operands.
568 // In thumb mode, if this block is a constpool island, we may need padding
569 // so it's aligned on 4 byte boundary.
572 MBB
.begin()->getOpcode() == ARM::CONSTPOOL_ENTRY
&&
576 BBSizes
.push_back(MBBSize
);
577 BBOffsets
.push_back(Offset
);
582 /// GetOffsetOf - Return the current offset of the specified machine instruction
583 /// from the start of the function. This offset changes as stuff is moved
584 /// around inside the function.
585 unsigned ARMConstantIslands::GetOffsetOf(MachineInstr
*MI
) const {
586 MachineBasicBlock
*MBB
= MI
->getParent();
588 // The offset is composed of two things: the sum of the sizes of all MBB's
589 // before this instruction's block, and the offset from the start of the block
591 unsigned Offset
= BBOffsets
[MBB
->getNumber()];
593 // If we're looking for a CONSTPOOL_ENTRY in Thumb, see if this block has
594 // alignment padding, and compensate if so.
596 MI
->getOpcode() == ARM::CONSTPOOL_ENTRY
&&
600 // Sum instructions before MI in MBB.
601 for (MachineBasicBlock::iterator I
= MBB
->begin(); ; ++I
) {
602 assert(I
!= MBB
->end() && "Didn't find MI in its own basic block?");
603 if (&*I
== MI
) return Offset
;
604 Offset
+= TII
->GetInstSizeInBytes(I
);
608 /// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB
610 static bool CompareMBBNumbers(const MachineBasicBlock
*LHS
,
611 const MachineBasicBlock
*RHS
) {
612 return LHS
->getNumber() < RHS
->getNumber();
615 /// UpdateForInsertedWaterBlock - When a block is newly inserted into the
616 /// machine function, it upsets all of the block numbers. Renumber the blocks
617 /// and update the arrays that parallel this numbering.
618 void ARMConstantIslands::UpdateForInsertedWaterBlock(MachineBasicBlock
*NewBB
) {
619 // Renumber the MBB's to keep them consequtive.
620 NewBB
->getParent()->RenumberBlocks(NewBB
);
622 // Insert a size into BBSizes to align it properly with the (newly
623 // renumbered) block numbers.
624 BBSizes
.insert(BBSizes
.begin()+NewBB
->getNumber(), 0);
626 // Likewise for BBOffsets.
627 BBOffsets
.insert(BBOffsets
.begin()+NewBB
->getNumber(), 0);
629 // Next, update WaterList. Specifically, we need to add NewMBB as having
630 // available water after it.
632 std::lower_bound(WaterList
.begin(), WaterList
.end(), NewBB
,
634 WaterList
.insert(IP
, NewBB
);
638 /// Split the basic block containing MI into two blocks, which are joined by
639 /// an unconditional branch. Update data structures and renumber blocks to
640 /// account for this change and returns the newly created block.
641 MachineBasicBlock
*ARMConstantIslands::SplitBlockBeforeInstr(MachineInstr
*MI
) {
642 MachineBasicBlock
*OrigBB
= MI
->getParent();
643 MachineFunction
&MF
= *OrigBB
->getParent();
645 // Create a new MBB for the code after the OrigBB.
646 MachineBasicBlock
*NewBB
=
647 MF
.CreateMachineBasicBlock(OrigBB
->getBasicBlock());
648 MachineFunction::iterator MBBI
= OrigBB
; ++MBBI
;
649 MF
.insert(MBBI
, NewBB
);
651 // Splice the instructions starting with MI over to NewBB.
652 NewBB
->splice(NewBB
->end(), OrigBB
, MI
, OrigBB
->end());
654 // Add an unconditional branch from OrigBB to NewBB.
655 // Note the new unconditional branch is not being recorded.
656 // There doesn't seem to be meaningful DebugInfo available; this doesn't
657 // correspond to anything in the source.
658 unsigned Opc
= isThumb
? (isThumb2
? ARM::t2B
: ARM::tB
) : ARM::B
;
659 BuildMI(OrigBB
, DebugLoc::getUnknownLoc(), TII
->get(Opc
)).addMBB(NewBB
);
662 // Update the CFG. All succs of OrigBB are now succs of NewBB.
663 while (!OrigBB
->succ_empty()) {
664 MachineBasicBlock
*Succ
= *OrigBB
->succ_begin();
665 OrigBB
->removeSuccessor(Succ
);
666 NewBB
->addSuccessor(Succ
);
668 // This pass should be run after register allocation, so there should be no
669 // PHI nodes to update.
670 assert((Succ
->empty() || Succ
->begin()->getOpcode() != TargetInstrInfo::PHI
)
671 && "PHI nodes should be eliminated by now!");
674 // OrigBB branches to NewBB.
675 OrigBB
->addSuccessor(NewBB
);
677 // Update internal data structures to account for the newly inserted MBB.
678 // This is almost the same as UpdateForInsertedWaterBlock, except that
679 // the Water goes after OrigBB, not NewBB.
680 MF
.RenumberBlocks(NewBB
);
682 // Insert a size into BBSizes to align it properly with the (newly
683 // renumbered) block numbers.
684 BBSizes
.insert(BBSizes
.begin()+NewBB
->getNumber(), 0);
686 // Likewise for BBOffsets.
687 BBOffsets
.insert(BBOffsets
.begin()+NewBB
->getNumber(), 0);
689 // Next, update WaterList. Specifically, we need to add OrigMBB as having
690 // available water after it (but not if it's already there, which happens
691 // when splitting before a conditional branch that is followed by an
692 // unconditional branch - in that case we want to insert NewBB).
694 std::lower_bound(WaterList
.begin(), WaterList
.end(), OrigBB
,
696 MachineBasicBlock
* WaterBB
= *IP
;
697 if (WaterBB
== OrigBB
)
698 WaterList
.insert(next(IP
), NewBB
);
700 WaterList
.insert(IP
, OrigBB
);
701 NewWaterList
.insert(OrigBB
);
703 // Figure out how large the first NewMBB is. (It cannot
704 // contain a constpool_entry or tablejump.)
705 unsigned NewBBSize
= 0;
706 for (MachineBasicBlock::iterator I
= NewBB
->begin(), E
= NewBB
->end();
708 NewBBSize
+= TII
->GetInstSizeInBytes(I
);
710 unsigned OrigBBI
= OrigBB
->getNumber();
711 unsigned NewBBI
= NewBB
->getNumber();
712 // Set the size of NewBB in BBSizes.
713 BBSizes
[NewBBI
] = NewBBSize
;
715 // We removed instructions from UserMBB, subtract that off from its size.
716 // Add 2 or 4 to the block to count the unconditional branch we added to it.
717 int delta
= isThumb1
? 2 : 4;
718 BBSizes
[OrigBBI
] -= NewBBSize
- delta
;
720 // ...and adjust BBOffsets for NewBB accordingly.
721 BBOffsets
[NewBBI
] = BBOffsets
[OrigBBI
] + BBSizes
[OrigBBI
];
723 // All BBOffsets following these blocks must be modified.
724 AdjustBBOffsetsAfter(NewBB
, delta
);
729 /// OffsetIsInRange - Checks whether UserOffset (the location of a constant pool
730 /// reference) is within MaxDisp of TrialOffset (a proposed location of a
731 /// constant pool entry).
732 bool ARMConstantIslands::OffsetIsInRange(unsigned UserOffset
,
733 unsigned TrialOffset
, unsigned MaxDisp
,
734 bool NegativeOK
, bool IsSoImm
) {
735 // On Thumb offsets==2 mod 4 are rounded down by the hardware for
736 // purposes of the displacement computation; compensate for that here.
737 // Effectively, the valid range of displacements is 2 bytes smaller for such
739 unsigned TotalAdj
= 0;
740 if (isThumb
&& UserOffset
%4 !=0) {
744 // CPEs will be rounded up to a multiple of 4.
745 if (isThumb
&& TrialOffset
%4 != 0) {
750 // In Thumb2 mode, later branch adjustments can shift instructions up and
751 // cause alignment change. In the worst case scenario this can cause the
752 // user's effective address to be subtracted by 2 and the CPE's address to
754 if (isThumb2
&& TotalAdj
!= 4)
755 MaxDisp
-= (4 - TotalAdj
);
757 if (UserOffset
<= TrialOffset
) {
758 // User before the Trial.
759 if (TrialOffset
- UserOffset
<= MaxDisp
)
761 // FIXME: Make use full range of soimm values.
762 } else if (NegativeOK
) {
763 if (UserOffset
- TrialOffset
<= MaxDisp
)
765 // FIXME: Make use full range of soimm values.
770 /// WaterIsInRange - Returns true if a CPE placed after the specified
771 /// Water (a basic block) will be in range for the specific MI.
773 bool ARMConstantIslands::WaterIsInRange(unsigned UserOffset
,
774 MachineBasicBlock
* Water
, CPUser
&U
) {
775 unsigned MaxDisp
= U
.MaxDisp
;
776 unsigned CPEOffset
= BBOffsets
[Water
->getNumber()] +
777 BBSizes
[Water
->getNumber()];
779 // If the CPE is to be inserted before the instruction, that will raise
780 // the offset of the instruction.
781 if (CPEOffset
< UserOffset
)
782 UserOffset
+= U
.CPEMI
->getOperand(2).getImm();
784 return OffsetIsInRange(UserOffset
, CPEOffset
, MaxDisp
, U
.NegOk
, U
.IsSoImm
);
787 /// CPEIsInRange - Returns true if the distance between specific MI and
788 /// specific ConstPool entry instruction can fit in MI's displacement field.
789 bool ARMConstantIslands::CPEIsInRange(MachineInstr
*MI
, unsigned UserOffset
,
790 MachineInstr
*CPEMI
, unsigned MaxDisp
,
791 bool NegOk
, bool DoDump
) {
792 unsigned CPEOffset
= GetOffsetOf(CPEMI
);
793 assert(CPEOffset
%4 == 0 && "Misaligned CPE");
796 DEBUG(errs() << "User of CPE#" << CPEMI
->getOperand(0).getImm()
797 << " max delta=" << MaxDisp
798 << " insn address=" << UserOffset
799 << " CPE address=" << CPEOffset
800 << " offset=" << int(CPEOffset
-UserOffset
) << "\t" << *MI
);
803 return OffsetIsInRange(UserOffset
, CPEOffset
, MaxDisp
, NegOk
);
807 /// BBIsJumpedOver - Return true of the specified basic block's only predecessor
808 /// unconditionally branches to its only successor.
809 static bool BBIsJumpedOver(MachineBasicBlock
*MBB
) {
810 if (MBB
->pred_size() != 1 || MBB
->succ_size() != 1)
813 MachineBasicBlock
*Succ
= *MBB
->succ_begin();
814 MachineBasicBlock
*Pred
= *MBB
->pred_begin();
815 MachineInstr
*PredMI
= &Pred
->back();
816 if (PredMI
->getOpcode() == ARM::B
|| PredMI
->getOpcode() == ARM::tB
817 || PredMI
->getOpcode() == ARM::t2B
)
818 return PredMI
->getOperand(0).getMBB() == Succ
;
823 void ARMConstantIslands::AdjustBBOffsetsAfter(MachineBasicBlock
*BB
,
825 MachineFunction::iterator MBBI
= BB
; MBBI
= next(MBBI
);
826 for(unsigned i
= BB
->getNumber()+1, e
= BB
->getParent()->getNumBlockIDs();
828 BBOffsets
[i
] += delta
;
829 // If some existing blocks have padding, adjust the padding as needed, a
830 // bit tricky. delta can be negative so don't use % on that.
833 MachineBasicBlock
*MBB
= MBBI
;
835 // Constant pool entries require padding.
836 if (MBB
->begin()->getOpcode() == ARM::CONSTPOOL_ENTRY
) {
837 unsigned OldOffset
= BBOffsets
[i
] - delta
;
838 if ((OldOffset
%4) == 0 && (BBOffsets
[i
]%4) != 0) {
842 } else if ((OldOffset
%4) != 0 && (BBOffsets
[i
]%4) == 0) {
843 // remove existing padding
848 // Thumb1 jump tables require padding. They should be at the end;
849 // following unconditional branches are removed by AnalyzeBranch.
850 MachineInstr
*ThumbJTMI
= prior(MBB
->end());
851 if (ThumbJTMI
->getOpcode() == ARM::tBR_JTr
) {
852 unsigned NewMIOffset
= GetOffsetOf(ThumbJTMI
);
853 unsigned OldMIOffset
= NewMIOffset
- delta
;
854 if ((OldMIOffset
%4) == 0 && (NewMIOffset
%4) != 0) {
855 // remove existing padding
858 } else if ((OldMIOffset
%4) != 0 && (NewMIOffset
%4) == 0) {
871 /// DecrementOldEntry - find the constant pool entry with index CPI
872 /// and instruction CPEMI, and decrement its refcount. If the refcount
873 /// becomes 0 remove the entry and instruction. Returns true if we removed
874 /// the entry, false if we didn't.
876 bool ARMConstantIslands::DecrementOldEntry(unsigned CPI
, MachineInstr
*CPEMI
) {
877 // Find the old entry. Eliminate it if it is no longer used.
878 CPEntry
*CPE
= findConstPoolEntry(CPI
, CPEMI
);
879 assert(CPE
&& "Unexpected!");
880 if (--CPE
->RefCount
== 0) {
881 RemoveDeadCPEMI(CPEMI
);
889 /// LookForCPEntryInRange - see if the currently referenced CPE is in range;
890 /// if not, see if an in-range clone of the CPE is in range, and if so,
891 /// change the data structures so the user references the clone. Returns:
892 /// 0 = no existing entry found
893 /// 1 = entry found, and there were no code insertions or deletions
894 /// 2 = entry found, and there were code insertions or deletions
895 int ARMConstantIslands::LookForExistingCPEntry(CPUser
& U
, unsigned UserOffset
)
897 MachineInstr
*UserMI
= U
.MI
;
898 MachineInstr
*CPEMI
= U
.CPEMI
;
900 // Check to see if the CPE is already in-range.
901 if (CPEIsInRange(UserMI
, UserOffset
, CPEMI
, U
.MaxDisp
, U
.NegOk
, true)) {
902 DEBUG(errs() << "In range\n");
906 // No. Look for previously created clones of the CPE that are in range.
907 unsigned CPI
= CPEMI
->getOperand(1).getIndex();
908 std::vector
<CPEntry
> &CPEs
= CPEntries
[CPI
];
909 for (unsigned i
= 0, e
= CPEs
.size(); i
!= e
; ++i
) {
910 // We already tried this one
911 if (CPEs
[i
].CPEMI
== CPEMI
)
913 // Removing CPEs can leave empty entries, skip
914 if (CPEs
[i
].CPEMI
== NULL
)
916 if (CPEIsInRange(UserMI
, UserOffset
, CPEs
[i
].CPEMI
, U
.MaxDisp
, U
.NegOk
)) {
917 DEBUG(errs() << "Replacing CPE#" << CPI
<< " with CPE#"
918 << CPEs
[i
].CPI
<< "\n");
919 // Point the CPUser node to the replacement
920 U
.CPEMI
= CPEs
[i
].CPEMI
;
921 // Change the CPI in the instruction operand to refer to the clone.
922 for (unsigned j
= 0, e
= UserMI
->getNumOperands(); j
!= e
; ++j
)
923 if (UserMI
->getOperand(j
).isCPI()) {
924 UserMI
->getOperand(j
).setIndex(CPEs
[i
].CPI
);
927 // Adjust the refcount of the clone...
929 // ...and the original. If we didn't remove the old entry, none of the
930 // addresses changed, so we don't need another pass.
931 return DecrementOldEntry(CPI
, CPEMI
) ? 2 : 1;
937 /// getUnconditionalBrDisp - Returns the maximum displacement that can fit in
938 /// the specific unconditional branch instruction.
939 static inline unsigned getUnconditionalBrDisp(int Opc
) {
942 return ((1<<10)-1)*2;
944 return ((1<<23)-1)*2;
949 return ((1<<23)-1)*4;
952 /// LookForWater - Look for an existing entry in the WaterList in which
953 /// we can place the CPE referenced from U so it's within range of U's MI.
954 /// Returns true if found, false if not. If it returns true, WaterIter
955 /// is set to the WaterList entry. For Thumb, prefer water that will not
956 /// introduce padding to water that will. To ensure that this pass
957 /// terminates, the CPE location for a particular CPUser is only allowed to
958 /// move to a lower address, so search backward from the end of the list and
959 /// prefer the first water that is in range.
960 bool ARMConstantIslands::LookForWater(CPUser
&U
, unsigned UserOffset
,
961 water_iterator
&WaterIter
) {
962 if (WaterList
.empty())
965 bool FoundWaterThatWouldPad
= false;
966 water_iterator IPThatWouldPad
;
967 for (water_iterator IP
= prior(WaterList
.end()),
968 B
= WaterList
.begin();; --IP
) {
969 MachineBasicBlock
* WaterBB
= *IP
;
970 // Check if water is in range and is either at a lower address than the
971 // current "high water mark" or a new water block that was created since
972 // the previous iteration by inserting an unconditional branch. In the
973 // latter case, we want to allow resetting the high water mark back to
974 // this new water since we haven't seen it before. Inserting branches
975 // should be relatively uncommon and when it does happen, we want to be
976 // sure to take advantage of it for all the CPEs near that block, so that
977 // we don't insert more branches than necessary.
978 if (WaterIsInRange(UserOffset
, WaterBB
, U
) &&
979 (WaterBB
->getNumber() < U
.HighWaterMark
->getNumber() ||
980 NewWaterList
.count(WaterBB
))) {
981 unsigned WBBId
= WaterBB
->getNumber();
983 (BBOffsets
[WBBId
] + BBSizes
[WBBId
])%4 != 0) {
984 // This is valid Water, but would introduce padding. Remember
985 // it in case we don't find any Water that doesn't do this.
986 if (!FoundWaterThatWouldPad
) {
987 FoundWaterThatWouldPad
= true;
998 if (FoundWaterThatWouldPad
) {
999 WaterIter
= IPThatWouldPad
;
1005 /// CreateNewWater - No existing WaterList entry will work for
1006 /// CPUsers[CPUserIndex], so create a place to put the CPE. The end of the
1007 /// block is used if in range, and the conditional branch munged so control
1008 /// flow is correct. Otherwise the block is split to create a hole with an
1009 /// unconditional branch around it. In either case NewMBB is set to a
1010 /// block following which the new island can be inserted (the WaterList
1011 /// is not adjusted).
1012 void ARMConstantIslands::CreateNewWater(unsigned CPUserIndex
,
1013 unsigned UserOffset
,
1014 MachineBasicBlock
*&NewMBB
) {
1015 CPUser
&U
= CPUsers
[CPUserIndex
];
1016 MachineInstr
*UserMI
= U
.MI
;
1017 MachineInstr
*CPEMI
= U
.CPEMI
;
1018 MachineBasicBlock
*UserMBB
= UserMI
->getParent();
1019 unsigned OffsetOfNextBlock
= BBOffsets
[UserMBB
->getNumber()] +
1020 BBSizes
[UserMBB
->getNumber()];
1021 assert(OffsetOfNextBlock
== BBOffsets
[UserMBB
->getNumber()+1]);
1023 // If the block does not end in an unconditional branch already, and if the
1024 // end of the block is within range, make new water there. (The addition
1025 // below is for the unconditional branch we will be adding: 4 bytes on ARM +
1026 // Thumb2, 2 on Thumb1. Possible Thumb1 alignment padding is allowed for
1027 // inside OffsetIsInRange.
1028 if (BBHasFallthrough(UserMBB
) &&
1029 OffsetIsInRange(UserOffset
, OffsetOfNextBlock
+ (isThumb1
? 2: 4),
1030 U
.MaxDisp
, U
.NegOk
, U
.IsSoImm
)) {
1031 DEBUG(errs() << "Split at end of block\n");
1032 if (&UserMBB
->back() == UserMI
)
1033 assert(BBHasFallthrough(UserMBB
) && "Expected a fallthrough BB!");
1034 NewMBB
= next(MachineFunction::iterator(UserMBB
));
1035 // Add an unconditional branch from UserMBB to fallthrough block.
1036 // Record it for branch lengthening; this new branch will not get out of
1037 // range, but if the preceding conditional branch is out of range, the
1038 // targets will be exchanged, and the altered branch may be out of
1039 // range, so the machinery has to know about it.
1040 int UncondBr
= isThumb
? ((isThumb2
) ? ARM::t2B
: ARM::tB
) : ARM::B
;
1041 BuildMI(UserMBB
, DebugLoc::getUnknownLoc(),
1042 TII
->get(UncondBr
)).addMBB(NewMBB
);
1043 unsigned MaxDisp
= getUnconditionalBrDisp(UncondBr
);
1044 ImmBranches
.push_back(ImmBranch(&UserMBB
->back(),
1045 MaxDisp
, false, UncondBr
));
1046 int delta
= isThumb1
? 2 : 4;
1047 BBSizes
[UserMBB
->getNumber()] += delta
;
1048 AdjustBBOffsetsAfter(UserMBB
, delta
);
1050 // What a big block. Find a place within the block to split it.
1051 // This is a little tricky on Thumb1 since instructions are 2 bytes
1052 // and constant pool entries are 4 bytes: if instruction I references
1053 // island CPE, and instruction I+1 references CPE', it will
1054 // not work well to put CPE as far forward as possible, since then
1055 // CPE' cannot immediately follow it (that location is 2 bytes
1056 // farther away from I+1 than CPE was from I) and we'd need to create
1057 // a new island. So, we make a first guess, then walk through the
1058 // instructions between the one currently being looked at and the
1059 // possible insertion point, and make sure any other instructions
1060 // that reference CPEs will be able to use the same island area;
1061 // if not, we back up the insertion point.
1063 // The 4 in the following is for the unconditional branch we'll be
1064 // inserting (allows for long branch on Thumb1). Alignment of the
1065 // island is handled inside OffsetIsInRange.
1066 unsigned BaseInsertOffset
= UserOffset
+ U
.MaxDisp
-4;
1067 // This could point off the end of the block if we've already got
1068 // constant pool entries following this block; only the last one is
1069 // in the water list. Back past any possible branches (allow for a
1070 // conditional and a maximally long unconditional).
1071 if (BaseInsertOffset
>= BBOffsets
[UserMBB
->getNumber()+1])
1072 BaseInsertOffset
= BBOffsets
[UserMBB
->getNumber()+1] -
1074 unsigned EndInsertOffset
= BaseInsertOffset
+
1075 CPEMI
->getOperand(2).getImm();
1076 MachineBasicBlock::iterator MI
= UserMI
;
1078 unsigned CPUIndex
= CPUserIndex
+1;
1079 for (unsigned Offset
= UserOffset
+TII
->GetInstSizeInBytes(UserMI
);
1080 Offset
< BaseInsertOffset
;
1081 Offset
+= TII
->GetInstSizeInBytes(MI
),
1083 if (CPUIndex
< CPUsers
.size() && CPUsers
[CPUIndex
].MI
== MI
) {
1084 CPUser
&U
= CPUsers
[CPUIndex
];
1085 if (!OffsetIsInRange(Offset
, EndInsertOffset
,
1086 U
.MaxDisp
, U
.NegOk
, U
.IsSoImm
)) {
1087 BaseInsertOffset
-= (isThumb1
? 2 : 4);
1088 EndInsertOffset
-= (isThumb1
? 2 : 4);
1090 // This is overly conservative, as we don't account for CPEMIs
1091 // being reused within the block, but it doesn't matter much.
1092 EndInsertOffset
+= CPUsers
[CPUIndex
].CPEMI
->getOperand(2).getImm();
1096 DEBUG(errs() << "Split in middle of big block\n");
1097 NewMBB
= SplitBlockBeforeInstr(prior(MI
));
1101 /// HandleConstantPoolUser - Analyze the specified user, checking to see if it
1102 /// is out-of-range. If so, pick up the constant pool value and move it some
1103 /// place in-range. Return true if we changed any addresses (thus must run
1104 /// another pass of branch lengthening), false otherwise.
1105 bool ARMConstantIslands::HandleConstantPoolUser(MachineFunction
&MF
,
1106 unsigned CPUserIndex
) {
1107 CPUser
&U
= CPUsers
[CPUserIndex
];
1108 MachineInstr
*UserMI
= U
.MI
;
1109 MachineInstr
*CPEMI
= U
.CPEMI
;
1110 unsigned CPI
= CPEMI
->getOperand(1).getIndex();
1111 unsigned Size
= CPEMI
->getOperand(2).getImm();
1112 // Compute this only once, it's expensive. The 4 or 8 is the value the
1113 // hardware keeps in the PC.
1114 unsigned UserOffset
= GetOffsetOf(UserMI
) + (isThumb
? 4 : 8);
1116 // See if the current entry is within range, or there is a clone of it
1118 int result
= LookForExistingCPEntry(U
, UserOffset
);
1119 if (result
==1) return false;
1120 else if (result
==2) return true;
1122 // No existing clone of this CPE is within range.
1123 // We will be generating a new clone. Get a UID for it.
1124 unsigned ID
= AFI
->createConstPoolEntryUId();
1126 // Look for water where we can place this CPE.
1127 MachineBasicBlock
*NewIsland
= MF
.CreateMachineBasicBlock();
1128 MachineBasicBlock
*NewMBB
;
1130 if (LookForWater(U
, UserOffset
, IP
)) {
1131 DEBUG(errs() << "found water in range\n");
1132 MachineBasicBlock
*WaterBB
= *IP
;
1134 // If the original WaterList entry was "new water" on this iteration,
1135 // propagate that to the new island. This is just keeping NewWaterList
1136 // updated to match the WaterList, which will be updated below.
1137 if (NewWaterList
.count(WaterBB
)) {
1138 NewWaterList
.erase(WaterBB
);
1139 NewWaterList
.insert(NewIsland
);
1141 // The new CPE goes before the following block (NewMBB).
1142 NewMBB
= next(MachineFunction::iterator(WaterBB
));
1146 DEBUG(errs() << "No water found\n");
1147 CreateNewWater(CPUserIndex
, UserOffset
, NewMBB
);
1149 // SplitBlockBeforeInstr adds to WaterList, which is important when it is
1150 // called while handling branches so that the water will be seen on the
1151 // next iteration for constant pools, but in this context, we don't want
1152 // it. Check for this so it will be removed from the WaterList.
1153 // Also remove any entry from NewWaterList.
1154 MachineBasicBlock
*WaterBB
= prior(MachineFunction::iterator(NewMBB
));
1155 IP
= std::find(WaterList
.begin(), WaterList
.end(), WaterBB
);
1156 if (IP
!= WaterList
.end())
1157 NewWaterList
.erase(WaterBB
);
1159 // We are adding new water. Update NewWaterList.
1160 NewWaterList
.insert(NewIsland
);
1163 // Remove the original WaterList entry; we want subsequent insertions in
1164 // this vicinity to go after the one we're about to insert. This
1165 // considerably reduces the number of times we have to move the same CPE
1166 // more than once and is also important to ensure the algorithm terminates.
1167 if (IP
!= WaterList
.end())
1168 WaterList
.erase(IP
);
1170 // Okay, we know we can put an island before NewMBB now, do it!
1171 MF
.insert(NewMBB
, NewIsland
);
1173 // Update internal data structures to account for the newly inserted MBB.
1174 UpdateForInsertedWaterBlock(NewIsland
);
1176 // Decrement the old entry, and remove it if refcount becomes 0.
1177 DecrementOldEntry(CPI
, CPEMI
);
1179 // Now that we have an island to add the CPE to, clone the original CPE and
1180 // add it to the island.
1181 U
.HighWaterMark
= NewIsland
;
1182 U
.CPEMI
= BuildMI(NewIsland
, DebugLoc::getUnknownLoc(),
1183 TII
->get(ARM::CONSTPOOL_ENTRY
))
1184 .addImm(ID
).addConstantPoolIndex(CPI
).addImm(Size
);
1185 CPEntries
[CPI
].push_back(CPEntry(U
.CPEMI
, ID
, 1));
1188 BBOffsets
[NewIsland
->getNumber()] = BBOffsets
[NewMBB
->getNumber()];
1189 // Compensate for .align 2 in thumb mode.
1190 if (isThumb
&& BBOffsets
[NewIsland
->getNumber()]%4 != 0)
1192 // Increase the size of the island block to account for the new entry.
1193 BBSizes
[NewIsland
->getNumber()] += Size
;
1194 AdjustBBOffsetsAfter(NewIsland
, Size
);
1196 // Finally, change the CPI in the instruction operand to be ID.
1197 for (unsigned i
= 0, e
= UserMI
->getNumOperands(); i
!= e
; ++i
)
1198 if (UserMI
->getOperand(i
).isCPI()) {
1199 UserMI
->getOperand(i
).setIndex(ID
);
1203 DEBUG(errs() << " Moved CPE to #" << ID
<< " CPI=" << CPI
1204 << '\t' << *UserMI
);
1209 /// RemoveDeadCPEMI - Remove a dead constant pool entry instruction. Update
1210 /// sizes and offsets of impacted basic blocks.
1211 void ARMConstantIslands::RemoveDeadCPEMI(MachineInstr
*CPEMI
) {
1212 MachineBasicBlock
*CPEBB
= CPEMI
->getParent();
1213 unsigned Size
= CPEMI
->getOperand(2).getImm();
1214 CPEMI
->eraseFromParent();
1215 BBSizes
[CPEBB
->getNumber()] -= Size
;
1216 // All succeeding offsets have the current size value added in, fix this.
1217 if (CPEBB
->empty()) {
1218 // In thumb1 mode, the size of island may be padded by two to compensate for
1219 // the alignment requirement. Then it will now be 2 when the block is
1220 // empty, so fix this.
1221 // All succeeding offsets have the current size value added in, fix this.
1222 if (BBSizes
[CPEBB
->getNumber()] != 0) {
1223 Size
+= BBSizes
[CPEBB
->getNumber()];
1224 BBSizes
[CPEBB
->getNumber()] = 0;
1227 AdjustBBOffsetsAfter(CPEBB
, -Size
);
1228 // An island has only one predecessor BB and one successor BB. Check if
1229 // this BB's predecessor jumps directly to this BB's successor. This
1230 // shouldn't happen currently.
1231 assert(!BBIsJumpedOver(CPEBB
) && "How did this happen?");
1232 // FIXME: remove the empty blocks after all the work is done?
1235 /// RemoveUnusedCPEntries - Remove constant pool entries whose refcounts
1237 bool ARMConstantIslands::RemoveUnusedCPEntries() {
1238 unsigned MadeChange
= false;
1239 for (unsigned i
= 0, e
= CPEntries
.size(); i
!= e
; ++i
) {
1240 std::vector
<CPEntry
> &CPEs
= CPEntries
[i
];
1241 for (unsigned j
= 0, ee
= CPEs
.size(); j
!= ee
; ++j
) {
1242 if (CPEs
[j
].RefCount
== 0 && CPEs
[j
].CPEMI
) {
1243 RemoveDeadCPEMI(CPEs
[j
].CPEMI
);
1244 CPEs
[j
].CPEMI
= NULL
;
1252 /// BBIsInRange - Returns true if the distance between specific MI and
1253 /// specific BB can fit in MI's displacement field.
1254 bool ARMConstantIslands::BBIsInRange(MachineInstr
*MI
,MachineBasicBlock
*DestBB
,
1256 unsigned PCAdj
= isThumb
? 4 : 8;
1257 unsigned BrOffset
= GetOffsetOf(MI
) + PCAdj
;
1258 unsigned DestOffset
= BBOffsets
[DestBB
->getNumber()];
1260 DEBUG(errs() << "Branch of destination BB#" << DestBB
->getNumber()
1261 << " from BB#" << MI
->getParent()->getNumber()
1262 << " max delta=" << MaxDisp
1263 << " from " << GetOffsetOf(MI
) << " to " << DestOffset
1264 << " offset " << int(DestOffset
-BrOffset
) << "\t" << *MI
);
1266 if (BrOffset
<= DestOffset
) {
1267 // Branch before the Dest.
1268 if (DestOffset
-BrOffset
<= MaxDisp
)
1271 if (BrOffset
-DestOffset
<= MaxDisp
)
1277 /// FixUpImmediateBr - Fix up an immediate branch whose destination is too far
1278 /// away to fit in its displacement field.
1279 bool ARMConstantIslands::FixUpImmediateBr(MachineFunction
&MF
, ImmBranch
&Br
) {
1280 MachineInstr
*MI
= Br
.MI
;
1281 MachineBasicBlock
*DestBB
= MI
->getOperand(0).getMBB();
1283 // Check to see if the DestBB is already in-range.
1284 if (BBIsInRange(MI
, DestBB
, Br
.MaxDisp
))
1288 return FixUpUnconditionalBr(MF
, Br
);
1289 return FixUpConditionalBr(MF
, Br
);
1292 /// FixUpUnconditionalBr - Fix up an unconditional branch whose destination is
1293 /// too far away to fit in its displacement field. If the LR register has been
1294 /// spilled in the epilogue, then we can use BL to implement a far jump.
1295 /// Otherwise, add an intermediate branch instruction to a branch.
1297 ARMConstantIslands::FixUpUnconditionalBr(MachineFunction
&MF
, ImmBranch
&Br
) {
1298 MachineInstr
*MI
= Br
.MI
;
1299 MachineBasicBlock
*MBB
= MI
->getParent();
1301 llvm_unreachable("FixUpUnconditionalBr is Thumb1 only!");
1303 // Use BL to implement far jump.
1304 Br
.MaxDisp
= (1 << 21) * 2;
1305 MI
->setDesc(TII
->get(ARM::tBfar
));
1306 BBSizes
[MBB
->getNumber()] += 2;
1307 AdjustBBOffsetsAfter(MBB
, 2);
1311 DEBUG(errs() << " Changed B to long jump " << *MI
);
1316 /// FixUpConditionalBr - Fix up a conditional branch whose destination is too
1317 /// far away to fit in its displacement field. It is converted to an inverse
1318 /// conditional branch + an unconditional branch to the destination.
1320 ARMConstantIslands::FixUpConditionalBr(MachineFunction
&MF
, ImmBranch
&Br
) {
1321 MachineInstr
*MI
= Br
.MI
;
1322 MachineBasicBlock
*DestBB
= MI
->getOperand(0).getMBB();
1324 // Add an unconditional branch to the destination and invert the branch
1325 // condition to jump over it:
1331 ARMCC::CondCodes CC
= (ARMCC::CondCodes
)MI
->getOperand(1).getImm();
1332 CC
= ARMCC::getOppositeCondition(CC
);
1333 unsigned CCReg
= MI
->getOperand(2).getReg();
1335 // If the branch is at the end of its MBB and that has a fall-through block,
1336 // direct the updated conditional branch to the fall-through block. Otherwise,
1337 // split the MBB before the next instruction.
1338 MachineBasicBlock
*MBB
= MI
->getParent();
1339 MachineInstr
*BMI
= &MBB
->back();
1340 bool NeedSplit
= (BMI
!= MI
) || !BBHasFallthrough(MBB
);
1344 if (next(MachineBasicBlock::iterator(MI
)) == prior(MBB
->end()) &&
1345 BMI
->getOpcode() == Br
.UncondBr
) {
1346 // Last MI in the BB is an unconditional branch. Can we simply invert the
1347 // condition and swap destinations:
1353 MachineBasicBlock
*NewDest
= BMI
->getOperand(0).getMBB();
1354 if (BBIsInRange(MI
, NewDest
, Br
.MaxDisp
)) {
1355 DEBUG(errs() << " Invert Bcc condition and swap its destination with "
1357 BMI
->getOperand(0).setMBB(DestBB
);
1358 MI
->getOperand(0).setMBB(NewDest
);
1359 MI
->getOperand(1).setImm(CC
);
1366 SplitBlockBeforeInstr(MI
);
1367 // No need for the branch to the next block. We're adding an unconditional
1368 // branch to the destination.
1369 int delta
= TII
->GetInstSizeInBytes(&MBB
->back());
1370 BBSizes
[MBB
->getNumber()] -= delta
;
1371 MachineBasicBlock
* SplitBB
= next(MachineFunction::iterator(MBB
));
1372 AdjustBBOffsetsAfter(SplitBB
, -delta
);
1373 MBB
->back().eraseFromParent();
1374 // BBOffsets[SplitBB] is wrong temporarily, fixed below
1376 MachineBasicBlock
*NextBB
= next(MachineFunction::iterator(MBB
));
1378 DEBUG(errs() << " Insert B to BB#" << DestBB
->getNumber()
1379 << " also invert condition and change dest. to BB#"
1380 << NextBB
->getNumber() << "\n");
1382 // Insert a new conditional branch and a new unconditional branch.
1383 // Also update the ImmBranch as well as adding a new entry for the new branch.
1384 BuildMI(MBB
, DebugLoc::getUnknownLoc(),
1385 TII
->get(MI
->getOpcode()))
1386 .addMBB(NextBB
).addImm(CC
).addReg(CCReg
);
1387 Br
.MI
= &MBB
->back();
1388 BBSizes
[MBB
->getNumber()] += TII
->GetInstSizeInBytes(&MBB
->back());
1389 BuildMI(MBB
, DebugLoc::getUnknownLoc(), TII
->get(Br
.UncondBr
)).addMBB(DestBB
);
1390 BBSizes
[MBB
->getNumber()] += TII
->GetInstSizeInBytes(&MBB
->back());
1391 unsigned MaxDisp
= getUnconditionalBrDisp(Br
.UncondBr
);
1392 ImmBranches
.push_back(ImmBranch(&MBB
->back(), MaxDisp
, false, Br
.UncondBr
));
1394 // Remove the old conditional branch. It may or may not still be in MBB.
1395 BBSizes
[MI
->getParent()->getNumber()] -= TII
->GetInstSizeInBytes(MI
);
1396 MI
->eraseFromParent();
1398 // The net size change is an addition of one unconditional branch.
1399 int delta
= TII
->GetInstSizeInBytes(&MBB
->back());
1400 AdjustBBOffsetsAfter(MBB
, delta
);
1404 /// UndoLRSpillRestore - Remove Thumb push / pop instructions that only spills
1405 /// LR / restores LR to pc. FIXME: This is done here because it's only possible
1406 /// to do this if tBfar is not used.
1407 bool ARMConstantIslands::UndoLRSpillRestore() {
1408 bool MadeChange
= false;
1409 for (unsigned i
= 0, e
= PushPopMIs
.size(); i
!= e
; ++i
) {
1410 MachineInstr
*MI
= PushPopMIs
[i
];
1411 // First two operands are predicates, the third is a zero since there
1413 if (MI
->getOpcode() == ARM::tPOP_RET
&&
1414 MI
->getOperand(3).getReg() == ARM::PC
&&
1415 MI
->getNumExplicitOperands() == 4) {
1416 BuildMI(MI
->getParent(), MI
->getDebugLoc(), TII
->get(ARM::tBX_RET
));
1417 MI
->eraseFromParent();
1424 bool ARMConstantIslands::OptimizeThumb2Instructions(MachineFunction
&MF
) {
1425 bool MadeChange
= false;
1427 // Shrink ADR and LDR from constantpool.
1428 for (unsigned i
= 0, e
= CPUsers
.size(); i
!= e
; ++i
) {
1429 CPUser
&U
= CPUsers
[i
];
1430 unsigned Opcode
= U
.MI
->getOpcode();
1431 unsigned NewOpc
= 0;
1436 case ARM::t2LEApcrel
:
1437 if (isARMLowRegister(U
.MI
->getOperand(0).getReg())) {
1438 NewOpc
= ARM::tLEApcrel
;
1444 if (isARMLowRegister(U
.MI
->getOperand(0).getReg())) {
1445 NewOpc
= ARM::tLDRpci
;
1455 unsigned UserOffset
= GetOffsetOf(U
.MI
) + 4;
1456 unsigned MaxOffs
= ((1 << Bits
) - 1) * Scale
;
1457 // FIXME: Check if offset is multiple of scale if scale is not 4.
1458 if (CPEIsInRange(U
.MI
, UserOffset
, U
.CPEMI
, MaxOffs
, false, true)) {
1459 U
.MI
->setDesc(TII
->get(NewOpc
));
1460 MachineBasicBlock
*MBB
= U
.MI
->getParent();
1461 BBSizes
[MBB
->getNumber()] -= 2;
1462 AdjustBBOffsetsAfter(MBB
, -2);
1468 MadeChange
|= OptimizeThumb2Branches(MF
);
1469 MadeChange
|= OptimizeThumb2JumpTables(MF
);
1473 bool ARMConstantIslands::OptimizeThumb2Branches(MachineFunction
&MF
) {
1474 bool MadeChange
= false;
1476 for (unsigned i
= 0, e
= ImmBranches
.size(); i
!= e
; ++i
) {
1477 ImmBranch
&Br
= ImmBranches
[i
];
1478 unsigned Opcode
= Br
.MI
->getOpcode();
1479 unsigned NewOpc
= 0;
1498 unsigned MaxOffs
= ((1 << (Bits
-1))-1) * Scale
;
1499 MachineBasicBlock
*DestBB
= Br
.MI
->getOperand(0).getMBB();
1500 if (BBIsInRange(Br
.MI
, DestBB
, MaxOffs
)) {
1501 Br
.MI
->setDesc(TII
->get(NewOpc
));
1502 MachineBasicBlock
*MBB
= Br
.MI
->getParent();
1503 BBSizes
[MBB
->getNumber()] -= 2;
1504 AdjustBBOffsetsAfter(MBB
, -2);
1514 /// OptimizeThumb2JumpTables - Use tbb / tbh instructions to generate smaller
1515 /// jumptables when it's possible.
1516 bool ARMConstantIslands::OptimizeThumb2JumpTables(MachineFunction
&MF
) {
1517 bool MadeChange
= false;
1519 // FIXME: After the tables are shrunk, can we get rid some of the
1520 // constantpool tables?
1521 const MachineJumpTableInfo
*MJTI
= MF
.getJumpTableInfo();
1522 const std::vector
<MachineJumpTableEntry
> &JT
= MJTI
->getJumpTables();
1523 for (unsigned i
= 0, e
= T2JumpTables
.size(); i
!= e
; ++i
) {
1524 MachineInstr
*MI
= T2JumpTables
[i
];
1525 const TargetInstrDesc
&TID
= MI
->getDesc();
1526 unsigned NumOps
= TID
.getNumOperands();
1527 unsigned JTOpIdx
= NumOps
- (TID
.isPredicable() ? 3 : 2);
1528 MachineOperand JTOP
= MI
->getOperand(JTOpIdx
);
1529 unsigned JTI
= JTOP
.getIndex();
1530 assert(JTI
< JT
.size());
1533 bool HalfWordOk
= true;
1534 unsigned JTOffset
= GetOffsetOf(MI
) + 4;
1535 const std::vector
<MachineBasicBlock
*> &JTBBs
= JT
[JTI
].MBBs
;
1536 for (unsigned j
= 0, ee
= JTBBs
.size(); j
!= ee
; ++j
) {
1537 MachineBasicBlock
*MBB
= JTBBs
[j
];
1538 unsigned DstOffset
= BBOffsets
[MBB
->getNumber()];
1539 // Negative offset is not ok. FIXME: We should change BB layout to make
1540 // sure all the branches are forward.
1541 if (ByteOk
&& (DstOffset
- JTOffset
) > ((1<<8)-1)*2)
1543 unsigned TBHLimit
= ((1<<16)-1)*2;
1544 if (HalfWordOk
&& (DstOffset
- JTOffset
) > TBHLimit
)
1546 if (!ByteOk
&& !HalfWordOk
)
1550 if (ByteOk
|| HalfWordOk
) {
1551 MachineBasicBlock
*MBB
= MI
->getParent();
1552 unsigned BaseReg
= MI
->getOperand(0).getReg();
1553 bool BaseRegKill
= MI
->getOperand(0).isKill();
1556 unsigned IdxReg
= MI
->getOperand(1).getReg();
1557 bool IdxRegKill
= MI
->getOperand(1).isKill();
1558 MachineBasicBlock::iterator PrevI
= MI
;
1559 if (PrevI
== MBB
->begin())
1562 MachineInstr
*AddrMI
= --PrevI
;
1564 // Examine the instruction that calculate the jumptable entry address.
1565 // If it's not the one just before the t2BR_JT, we won't delete it, then
1566 // it's not worth doing the optimization.
1567 for (unsigned k
= 0, eee
= AddrMI
->getNumOperands(); k
!= eee
; ++k
) {
1568 const MachineOperand
&MO
= AddrMI
->getOperand(k
);
1569 if (!MO
.isReg() || !MO
.getReg())
1571 if (MO
.isDef() && MO
.getReg() != BaseReg
) {
1575 if (MO
.isUse() && !MO
.isKill() && MO
.getReg() != IdxReg
) {
1583 // The previous instruction should be a tLEApcrel or t2LEApcrelJT, we want
1584 // to delete it as well.
1585 MachineInstr
*LeaMI
= --PrevI
;
1586 if ((LeaMI
->getOpcode() != ARM::tLEApcrelJT
&&
1587 LeaMI
->getOpcode() != ARM::t2LEApcrelJT
) ||
1588 LeaMI
->getOperand(0).getReg() != BaseReg
)
1594 unsigned Opc
= ByteOk
? ARM::t2TBB
: ARM::t2TBH
;
1595 MachineInstr
*NewJTMI
= BuildMI(MBB
, MI
->getDebugLoc(), TII
->get(Opc
))
1596 .addReg(IdxReg
, getKillRegState(IdxRegKill
))
1597 .addJumpTableIndex(JTI
, JTOP
.getTargetFlags())
1598 .addImm(MI
->getOperand(JTOpIdx
+1).getImm());
1599 // FIXME: Insert an "ALIGN" instruction to ensure the next instruction
1600 // is 2-byte aligned. For now, asm printer will fix it up.
1601 unsigned NewSize
= TII
->GetInstSizeInBytes(NewJTMI
);
1602 unsigned OrigSize
= TII
->GetInstSizeInBytes(AddrMI
);
1603 OrigSize
+= TII
->GetInstSizeInBytes(LeaMI
);
1604 OrigSize
+= TII
->GetInstSizeInBytes(MI
);
1606 AddrMI
->eraseFromParent();
1607 LeaMI
->eraseFromParent();
1608 MI
->eraseFromParent();
1610 int delta
= OrigSize
- NewSize
;
1611 BBSizes
[MBB
->getNumber()] -= delta
;
1612 AdjustBBOffsetsAfter(MBB
, -delta
);