Bug Summary

File:lib/Target/ARM/ARMBasicBlockInfo.h
Warning:line 31, column 35
The result of the left shift is undefined due to shifting by '32', which is greater or equal to the width of type 'unsigned int'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name ARMConstantIslandPass.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/lib/Target/ARM -I /build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM -I /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn338205/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/x86_64-linux-gnu/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/x86_64-linux-gnu/c++/8 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.0.0/include -internal-externc-isystem /usr/lib/gcc/x86_64-linux-gnu/8/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn338205/build-llvm/lib/Target/ARM -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-07-29-043837-17923-1 -x c++ /build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp -faddrsig

/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp

1//===- ARMConstantIslandPass.cpp - ARM constant islands -------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// 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.
13//
14//===----------------------------------------------------------------------===//
15
16#include "ARM.h"
17#include "ARMBaseInstrInfo.h"
18#include "ARMBasicBlockInfo.h"
19#include "ARMMachineFunctionInfo.h"
20#include "ARMSubtarget.h"
21#include "MCTargetDesc/ARMBaseInfo.h"
22#include "Thumb2InstrInfo.h"
23#include "Utils/ARMBaseInfo.h"
24#include "llvm/ADT/DenseMap.h"
25#include "llvm/ADT/STLExtras.h"
26#include "llvm/ADT/SmallSet.h"
27#include "llvm/ADT/SmallVector.h"
28#include "llvm/ADT/Statistic.h"
29#include "llvm/ADT/StringRef.h"
30#include "llvm/CodeGen/MachineBasicBlock.h"
31#include "llvm/CodeGen/MachineConstantPool.h"
32#include "llvm/CodeGen/MachineFunction.h"
33#include "llvm/CodeGen/MachineFunctionPass.h"
34#include "llvm/CodeGen/MachineInstr.h"
35#include "llvm/CodeGen/MachineJumpTableInfo.h"
36#include "llvm/CodeGen/MachineOperand.h"
37#include "llvm/CodeGen/MachineRegisterInfo.h"
38#include "llvm/Config/llvm-config.h"
39#include "llvm/IR/DataLayout.h"
40#include "llvm/IR/DebugLoc.h"
41#include "llvm/MC/MCInstrDesc.h"
42#include "llvm/Pass.h"
43#include "llvm/Support/CommandLine.h"
44#include "llvm/Support/Compiler.h"
45#include "llvm/Support/Debug.h"
46#include "llvm/Support/ErrorHandling.h"
47#include "llvm/Support/Format.h"
48#include "llvm/Support/MathExtras.h"
49#include "llvm/Support/raw_ostream.h"
50#include <algorithm>
51#include <cassert>
52#include <cstdint>
53#include <iterator>
54#include <utility>
55#include <vector>
56
57using namespace llvm;
58
59#define DEBUG_TYPE"arm-cp-islands" "arm-cp-islands"
60
61#define ARM_CP_ISLANDS_OPT_NAME"ARM constant island placement and branch shortening pass" \
62 "ARM constant island placement and branch shortening pass"
63STATISTIC(NumCPEs, "Number of constpool entries")static llvm::Statistic NumCPEs = {"arm-cp-islands", "NumCPEs"
, "Number of constpool entries", {0}, {false}}
;
64STATISTIC(NumSplit, "Number of uncond branches inserted")static llvm::Statistic NumSplit = {"arm-cp-islands", "NumSplit"
, "Number of uncond branches inserted", {0}, {false}}
;
65STATISTIC(NumCBrFixed, "Number of cond branches fixed")static llvm::Statistic NumCBrFixed = {"arm-cp-islands", "NumCBrFixed"
, "Number of cond branches fixed", {0}, {false}}
;
66STATISTIC(NumUBrFixed, "Number of uncond branches fixed")static llvm::Statistic NumUBrFixed = {"arm-cp-islands", "NumUBrFixed"
, "Number of uncond branches fixed", {0}, {false}}
;
67STATISTIC(NumTBs, "Number of table branches generated")static llvm::Statistic NumTBs = {"arm-cp-islands", "NumTBs", "Number of table branches generated"
, {0}, {false}}
;
68STATISTIC(NumT2CPShrunk, "Number of Thumb2 constantpool instructions shrunk")static llvm::Statistic NumT2CPShrunk = {"arm-cp-islands", "NumT2CPShrunk"
, "Number of Thumb2 constantpool instructions shrunk", {0}, {
false}}
;
69STATISTIC(NumT2BrShrunk, "Number of Thumb2 immediate branches shrunk")static llvm::Statistic NumT2BrShrunk = {"arm-cp-islands", "NumT2BrShrunk"
, "Number of Thumb2 immediate branches shrunk", {0}, {false}}
;
70STATISTIC(NumCBZ, "Number of CBZ / CBNZ formed")static llvm::Statistic NumCBZ = {"arm-cp-islands", "NumCBZ", "Number of CBZ / CBNZ formed"
, {0}, {false}}
;
71STATISTIC(NumJTMoved, "Number of jump table destination blocks moved")static llvm::Statistic NumJTMoved = {"arm-cp-islands", "NumJTMoved"
, "Number of jump table destination blocks moved", {0}, {false
}}
;
72STATISTIC(NumJTInserted, "Number of jump table intermediate blocks inserted")static llvm::Statistic NumJTInserted = {"arm-cp-islands", "NumJTInserted"
, "Number of jump table intermediate blocks inserted", {0}, {
false}}
;
73
74static cl::opt<bool>
75AdjustJumpTableBlocks("arm-adjust-jump-tables", cl::Hidden, cl::init(true),
76 cl::desc("Adjust basic block layout to better use TB[BH]"));
77
78static cl::opt<unsigned>
79CPMaxIteration("arm-constant-island-max-iteration", cl::Hidden, cl::init(30),
80 cl::desc("The max number of iteration for converge"));
81
82static cl::opt<bool> SynthesizeThumb1TBB(
83 "arm-synthesize-thumb-1-tbb", cl::Hidden, cl::init(true),
84 cl::desc("Use compressed jump tables in Thumb-1 by synthesizing an "
85 "equivalent to the TBB/TBH instructions"));
86
87namespace {
88
89 /// ARMConstantIslands - Due to limited PC-relative displacements, ARM
90 /// requires constant pool entries to be scattered among the instructions
91 /// inside a function. To do this, it completely ignores the normal LLVM
92 /// constant pool; instead, it places constants wherever it feels like with
93 /// special instructions.
94 ///
95 /// The terminology used in this pass includes:
96 /// Islands - Clumps of constants placed in the function.
97 /// Water - Potential places where an island could be formed.
98 /// CPE - A constant pool entry that has been placed somewhere, which
99 /// tracks a list of users.
100 class ARMConstantIslands : public MachineFunctionPass {
101 std::vector<BasicBlockInfo> BBInfo;
102
103 /// WaterList - A sorted list of basic blocks where islands could be placed
104 /// (i.e. blocks that don't fall through to the following block, due
105 /// to a return, unreachable, or unconditional branch).
106 std::vector<MachineBasicBlock*> WaterList;
107
108 /// NewWaterList - The subset of WaterList that was created since the
109 /// previous iteration by inserting unconditional branches.
110 SmallSet<MachineBasicBlock*, 4> NewWaterList;
111
112 using water_iterator = std::vector<MachineBasicBlock *>::iterator;
113
114 /// CPUser - One user of a constant pool, keeping the machine instruction
115 /// pointer, the constant pool being referenced, and the max displacement
116 /// allowed from the instruction to the CP. The HighWaterMark records the
117 /// highest basic block where a new CPEntry can be placed. To ensure this
118 /// pass terminates, the CP entries are initially placed at the end of the
119 /// function and then move monotonically to lower addresses. The
120 /// exception to this rule is when the current CP entry for a particular
121 /// CPUser is out of range, but there is another CP entry for the same
122 /// constant value in range. We want to use the existing in-range CP
123 /// entry, but if it later moves out of range, the search for new water
124 /// should resume where it left off. The HighWaterMark is used to record
125 /// that point.
126 struct CPUser {
127 MachineInstr *MI;
128 MachineInstr *CPEMI;
129 MachineBasicBlock *HighWaterMark;
130 unsigned MaxDisp;
131 bool NegOk;
132 bool IsSoImm;
133 bool KnownAlignment = false;
134
135 CPUser(MachineInstr *mi, MachineInstr *cpemi, unsigned maxdisp,
136 bool neg, bool soimm)
137 : MI(mi), CPEMI(cpemi), MaxDisp(maxdisp), NegOk(neg), IsSoImm(soimm) {
138 HighWaterMark = CPEMI->getParent();
139 }
140
141 /// getMaxDisp - Returns the maximum displacement supported by MI.
142 /// Correct for unknown alignment.
143 /// Conservatively subtract 2 bytes to handle weird alignment effects.
144 unsigned getMaxDisp() const {
145 return (KnownAlignment ? MaxDisp : MaxDisp - 2) - 2;
146 }
147 };
148
149 /// CPUsers - Keep track of all of the machine instructions that use various
150 /// constant pools and their max displacement.
151 std::vector<CPUser> CPUsers;
152
153 /// CPEntry - One per constant pool entry, keeping the machine instruction
154 /// pointer, the constpool index, and the number of CPUser's which
155 /// reference this entry.
156 struct CPEntry {
157 MachineInstr *CPEMI;
158 unsigned CPI;
159 unsigned RefCount;
160
161 CPEntry(MachineInstr *cpemi, unsigned cpi, unsigned rc = 0)
162 : CPEMI(cpemi), CPI(cpi), RefCount(rc) {}
163 };
164
165 /// CPEntries - Keep track of all of the constant pool entry machine
166 /// instructions. For each original constpool index (i.e. those that existed
167 /// upon entry to this pass), it keeps a vector of entries. Original
168 /// elements are cloned as we go along; the clones are put in the vector of
169 /// the original element, but have distinct CPIs.
170 ///
171 /// The first half of CPEntries contains generic constants, the second half
172 /// contains jump tables. Use getCombinedIndex on a generic CPEMI to look up
173 /// which vector it will be in here.
174 std::vector<std::vector<CPEntry>> CPEntries;
175
176 /// Maps a JT index to the offset in CPEntries containing copies of that
177 /// table. The equivalent map for a CONSTPOOL_ENTRY is the identity.
178 DenseMap<int, int> JumpTableEntryIndices;
179
180 /// Maps a JT index to the LEA that actually uses the index to calculate its
181 /// base address.
182 DenseMap<int, int> JumpTableUserIndices;
183
184 /// ImmBranch - One per immediate branch, keeping the machine instruction
185 /// pointer, conditional or unconditional, the max displacement,
186 /// and (if isCond is true) the corresponding unconditional branch
187 /// opcode.
188 struct ImmBranch {
189 MachineInstr *MI;
190 unsigned MaxDisp : 31;
191 bool isCond : 1;
192 unsigned UncondBr;
193
194 ImmBranch(MachineInstr *mi, unsigned maxdisp, bool cond, unsigned ubr)
195 : MI(mi), MaxDisp(maxdisp), isCond(cond), UncondBr(ubr) {}
196 };
197
198 /// ImmBranches - Keep track of all the immediate branch instructions.
199 std::vector<ImmBranch> ImmBranches;
200
201 /// PushPopMIs - Keep track of all the Thumb push / pop instructions.
202 SmallVector<MachineInstr*, 4> PushPopMIs;
203
204 /// T2JumpTables - Keep track of all the Thumb2 jumptable instructions.
205 SmallVector<MachineInstr*, 4> T2JumpTables;
206
207 /// HasFarJump - True if any far jump instruction has been emitted during
208 /// the branch fix up pass.
209 bool HasFarJump;
210
211 MachineFunction *MF;
212 MachineConstantPool *MCP;
213 const ARMBaseInstrInfo *TII;
214 const ARMSubtarget *STI;
215 ARMFunctionInfo *AFI;
216 bool isThumb;
217 bool isThumb1;
218 bool isThumb2;
219 bool isPositionIndependentOrROPI;
220
221 public:
222 static char ID;
223
224 ARMConstantIslands() : MachineFunctionPass(ID) {}
225
226 bool runOnMachineFunction(MachineFunction &MF) override;
227
228 MachineFunctionProperties getRequiredProperties() const override {
229 return MachineFunctionProperties().set(
230 MachineFunctionProperties::Property::NoVRegs);
231 }
232
233 StringRef getPassName() const override {
234 return ARM_CP_ISLANDS_OPT_NAME"ARM constant island placement and branch shortening pass";
235 }
236
237 private:
238 void doInitialConstPlacement(std::vector<MachineInstr *> &CPEMIs);
239 void doInitialJumpTablePlacement(std::vector<MachineInstr *> &CPEMIs);
240 bool BBHasFallthrough(MachineBasicBlock *MBB);
241 CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI);
242 unsigned getCPELogAlign(const MachineInstr *CPEMI);
243 void scanFunctionJumpTables();
244 void initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs);
245 MachineBasicBlock *splitBlockBeforeInstr(MachineInstr *MI);
246 void updateForInsertedWaterBlock(MachineBasicBlock *NewBB);
247 void adjustBBOffsetsAfter(MachineBasicBlock *BB);
248 bool decrementCPEReferenceCount(unsigned CPI, MachineInstr* CPEMI);
249 unsigned getCombinedIndex(const MachineInstr *CPEMI);
250 int findInRangeCPEntry(CPUser& U, unsigned UserOffset);
251 bool findAvailableWater(CPUser&U, unsigned UserOffset,
252 water_iterator &WaterIter, bool CloserWater);
253 void createNewWater(unsigned CPUserIndex, unsigned UserOffset,
254 MachineBasicBlock *&NewMBB);
255 bool handleConstantPoolUser(unsigned CPUserIndex, bool CloserWater);
256 void removeDeadCPEMI(MachineInstr *CPEMI);
257 bool removeUnusedCPEntries();
258 bool isCPEntryInRange(MachineInstr *MI, unsigned UserOffset,
259 MachineInstr *CPEMI, unsigned Disp, bool NegOk,
260 bool DoDump = false);
261 bool isWaterInRange(unsigned UserOffset, MachineBasicBlock *Water,
262 CPUser &U, unsigned &Growth);
263 bool isBBInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp);
264 bool fixupImmediateBr(ImmBranch &Br);
265 bool fixupConditionalBr(ImmBranch &Br);
266 bool fixupUnconditionalBr(ImmBranch &Br);
267 bool undoLRSpillRestore();
268 bool optimizeThumb2Instructions();
269 bool optimizeThumb2Branches();
270 bool reorderThumb2JumpTables();
271 bool preserveBaseRegister(MachineInstr *JumpMI, MachineInstr *LEAMI,
272 unsigned &DeadSize, bool &CanDeleteLEA,
273 bool &BaseRegKill);
274 bool optimizeThumb2JumpTables();
275 MachineBasicBlock *adjustJTTargetBlockForward(MachineBasicBlock *BB,
276 MachineBasicBlock *JTBB);
277
278 unsigned getOffsetOf(MachineInstr *MI) const;
279 unsigned getUserOffset(CPUser&) const;
280 void dumpBBs();
281 void verify();
282
283 bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset,
284 unsigned Disp, bool NegativeOK, bool IsSoImm = false);
285 bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset,
286 const CPUser &U) {
287 return isOffsetInRange(UserOffset, TrialOffset,
288 U.getMaxDisp(), U.NegOk, U.IsSoImm);
289 }
290 };
291
292} // end anonymous namespace
293
294char ARMConstantIslands::ID = 0;
295
296/// verify - check BBOffsets, BBSizes, alignment of islands
297void ARMConstantIslands::verify() {
298#ifndef NDEBUG
299 assert(std::is_sorted(MF->begin(), MF->end(),(static_cast <bool> (std::is_sorted(MF->begin(), MF->
end(), [this](const MachineBasicBlock &LHS, const MachineBasicBlock
&RHS) { return BBInfo[LHS.getNumber()].postOffset() <
BBInfo[RHS.getNumber()].postOffset(); })) ? void (0) : __assert_fail
("std::is_sorted(MF->begin(), MF->end(), [this](const MachineBasicBlock &LHS, const MachineBasicBlock &RHS) { return BBInfo[LHS.getNumber()].postOffset() < BBInfo[RHS.getNumber()].postOffset(); })"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 304, __extension__ __PRETTY_FUNCTION__))
300 [this](const MachineBasicBlock &LHS,(static_cast <bool> (std::is_sorted(MF->begin(), MF->
end(), [this](const MachineBasicBlock &LHS, const MachineBasicBlock
&RHS) { return BBInfo[LHS.getNumber()].postOffset() <
BBInfo[RHS.getNumber()].postOffset(); })) ? void (0) : __assert_fail
("std::is_sorted(MF->begin(), MF->end(), [this](const MachineBasicBlock &LHS, const MachineBasicBlock &RHS) { return BBInfo[LHS.getNumber()].postOffset() < BBInfo[RHS.getNumber()].postOffset(); })"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 304, __extension__ __PRETTY_FUNCTION__))
301 const MachineBasicBlock &RHS) {(static_cast <bool> (std::is_sorted(MF->begin(), MF->
end(), [this](const MachineBasicBlock &LHS, const MachineBasicBlock
&RHS) { return BBInfo[LHS.getNumber()].postOffset() <
BBInfo[RHS.getNumber()].postOffset(); })) ? void (0) : __assert_fail
("std::is_sorted(MF->begin(), MF->end(), [this](const MachineBasicBlock &LHS, const MachineBasicBlock &RHS) { return BBInfo[LHS.getNumber()].postOffset() < BBInfo[RHS.getNumber()].postOffset(); })"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 304, __extension__ __PRETTY_FUNCTION__))
302 return BBInfo[LHS.getNumber()].postOffset() <(static_cast <bool> (std::is_sorted(MF->begin(), MF->
end(), [this](const MachineBasicBlock &LHS, const MachineBasicBlock
&RHS) { return BBInfo[LHS.getNumber()].postOffset() <
BBInfo[RHS.getNumber()].postOffset(); })) ? void (0) : __assert_fail
("std::is_sorted(MF->begin(), MF->end(), [this](const MachineBasicBlock &LHS, const MachineBasicBlock &RHS) { return BBInfo[LHS.getNumber()].postOffset() < BBInfo[RHS.getNumber()].postOffset(); })"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 304, __extension__ __PRETTY_FUNCTION__))
303 BBInfo[RHS.getNumber()].postOffset();(static_cast <bool> (std::is_sorted(MF->begin(), MF->
end(), [this](const MachineBasicBlock &LHS, const MachineBasicBlock
&RHS) { return BBInfo[LHS.getNumber()].postOffset() <
BBInfo[RHS.getNumber()].postOffset(); })) ? void (0) : __assert_fail
("std::is_sorted(MF->begin(), MF->end(), [this](const MachineBasicBlock &LHS, const MachineBasicBlock &RHS) { return BBInfo[LHS.getNumber()].postOffset() < BBInfo[RHS.getNumber()].postOffset(); })"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 304, __extension__ __PRETTY_FUNCTION__))
304 }))(static_cast <bool> (std::is_sorted(MF->begin(), MF->
end(), [this](const MachineBasicBlock &LHS, const MachineBasicBlock
&RHS) { return BBInfo[LHS.getNumber()].postOffset() <
BBInfo[RHS.getNumber()].postOffset(); })) ? void (0) : __assert_fail
("std::is_sorted(MF->begin(), MF->end(), [this](const MachineBasicBlock &LHS, const MachineBasicBlock &RHS) { return BBInfo[LHS.getNumber()].postOffset() < BBInfo[RHS.getNumber()].postOffset(); })"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 304, __extension__ __PRETTY_FUNCTION__))
;
305 LLVM_DEBUG(dbgs() << "Verifying " << CPUsers.size() << " CP users.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Verifying " << CPUsers
.size() << " CP users.\n"; } } while (false)
;
306 for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) {
307 CPUser &U = CPUsers[i];
308 unsigned UserOffset = getUserOffset(U);
309 // Verify offset using the real max displacement without the safety
310 // adjustment.
311 if (isCPEntryInRange(U.MI, UserOffset, U.CPEMI, U.getMaxDisp()+2, U.NegOk,
312 /* DoDump = */ true)) {
313 LLVM_DEBUG(dbgs() << "OK\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "OK\n"; } } while (false
)
;
314 continue;
315 }
316 LLVM_DEBUG(dbgs() << "Out of range.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Out of range.\n"; } } while
(false)
;
317 dumpBBs();
318 LLVM_DEBUG(MF->dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { MF->dump(); } } while (false)
;
319 llvm_unreachable("Constant pool entry out of range!")::llvm::llvm_unreachable_internal("Constant pool entry out of range!"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 319)
;
320 }
321#endif
322}
323
324#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
325/// print block size and offset information - debugging
326LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void ARMConstantIslands::dumpBBs() {
327 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { { for (unsigned J = 0, E = BBInfo.size(
); J !=E; ++J) { const BasicBlockInfo &BBI = BBInfo[J]; dbgs
() << format("%08x %bb.%u\t", BBI.Offset, J) << " kb="
<< unsigned(BBI.KnownBits) << " ua=" << unsigned
(BBI.Unalign) << " pa=" << unsigned(BBI.PostAlign
) << format(" size=%#x\n", BBInfo[J].Size); } }; } } while
(false)
328 for (unsigned J = 0, E = BBInfo.size(); J !=E; ++J) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { { for (unsigned J = 0, E = BBInfo.size(
); J !=E; ++J) { const BasicBlockInfo &BBI = BBInfo[J]; dbgs
() << format("%08x %bb.%u\t", BBI.Offset, J) << " kb="
<< unsigned(BBI.KnownBits) << " ua=" << unsigned
(BBI.Unalign) << " pa=" << unsigned(BBI.PostAlign
) << format(" size=%#x\n", BBInfo[J].Size); } }; } } while
(false)
329 const BasicBlockInfo &BBI = BBInfo[J];do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { { for (unsigned J = 0, E = BBInfo.size(
); J !=E; ++J) { const BasicBlockInfo &BBI = BBInfo[J]; dbgs
() << format("%08x %bb.%u\t", BBI.Offset, J) << " kb="
<< unsigned(BBI.KnownBits) << " ua=" << unsigned
(BBI.Unalign) << " pa=" << unsigned(BBI.PostAlign
) << format(" size=%#x\n", BBInfo[J].Size); } }; } } while
(false)
330 dbgs() << format("%08x %bb.%u\t", BBI.Offset, J)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { { for (unsigned J = 0, E = BBInfo.size(
); J !=E; ++J) { const BasicBlockInfo &BBI = BBInfo[J]; dbgs
() << format("%08x %bb.%u\t", BBI.Offset, J) << " kb="
<< unsigned(BBI.KnownBits) << " ua=" << unsigned
(BBI.Unalign) << " pa=" << unsigned(BBI.PostAlign
) << format(" size=%#x\n", BBInfo[J].Size); } }; } } while
(false)
331 << " kb=" << unsigned(BBI.KnownBits)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { { for (unsigned J = 0, E = BBInfo.size(
); J !=E; ++J) { const BasicBlockInfo &BBI = BBInfo[J]; dbgs
() << format("%08x %bb.%u\t", BBI.Offset, J) << " kb="
<< unsigned(BBI.KnownBits) << " ua=" << unsigned
(BBI.Unalign) << " pa=" << unsigned(BBI.PostAlign
) << format(" size=%#x\n", BBInfo[J].Size); } }; } } while
(false)
332 << " ua=" << unsigned(BBI.Unalign)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { { for (unsigned J = 0, E = BBInfo.size(
); J !=E; ++J) { const BasicBlockInfo &BBI = BBInfo[J]; dbgs
() << format("%08x %bb.%u\t", BBI.Offset, J) << " kb="
<< unsigned(BBI.KnownBits) << " ua=" << unsigned
(BBI.Unalign) << " pa=" << unsigned(BBI.PostAlign
) << format(" size=%#x\n", BBInfo[J].Size); } }; } } while
(false)
333 << " pa=" << unsigned(BBI.PostAlign)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { { for (unsigned J = 0, E = BBInfo.size(
); J !=E; ++J) { const BasicBlockInfo &BBI = BBInfo[J]; dbgs
() << format("%08x %bb.%u\t", BBI.Offset, J) << " kb="
<< unsigned(BBI.KnownBits) << " ua=" << unsigned
(BBI.Unalign) << " pa=" << unsigned(BBI.PostAlign
) << format(" size=%#x\n", BBInfo[J].Size); } }; } } while
(false)
334 << format(" size=%#x\n", BBInfo[J].Size);do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { { for (unsigned J = 0, E = BBInfo.size(
); J !=E; ++J) { const BasicBlockInfo &BBI = BBInfo[J]; dbgs
() << format("%08x %bb.%u\t", BBI.Offset, J) << " kb="
<< unsigned(BBI.KnownBits) << " ua=" << unsigned
(BBI.Unalign) << " pa=" << unsigned(BBI.PostAlign
) << format(" size=%#x\n", BBInfo[J].Size); } }; } } while
(false)
335 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { { for (unsigned J = 0, E = BBInfo.size(
); J !=E; ++J) { const BasicBlockInfo &BBI = BBInfo[J]; dbgs
() << format("%08x %bb.%u\t", BBI.Offset, J) << " kb="
<< unsigned(BBI.KnownBits) << " ua=" << unsigned
(BBI.Unalign) << " pa=" << unsigned(BBI.PostAlign
) << format(" size=%#x\n", BBInfo[J].Size); } }; } } while
(false)
336 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { { for (unsigned J = 0, E = BBInfo.size(
); J !=E; ++J) { const BasicBlockInfo &BBI = BBInfo[J]; dbgs
() << format("%08x %bb.%u\t", BBI.Offset, J) << " kb="
<< unsigned(BBI.KnownBits) << " ua=" << unsigned
(BBI.Unalign) << " pa=" << unsigned(BBI.PostAlign
) << format(" size=%#x\n", BBInfo[J].Size); } }; } } while
(false)
;
337}
338#endif
339
340bool ARMConstantIslands::runOnMachineFunction(MachineFunction &mf) {
341 MF = &mf;
342 MCP = mf.getConstantPool();
343
344 LLVM_DEBUG(dbgs() << "***** ARMConstantIslands: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "***** ARMConstantIslands: "
<< MCP->getConstants().size() << " CP entries, aligned to "
<< MCP->getConstantPoolAlignment() << " bytes *****\n"
; } } while (false)
345 << MCP->getConstants().size() << " CP entries, aligned to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "***** ARMConstantIslands: "
<< MCP->getConstants().size() << " CP entries, aligned to "
<< MCP->getConstantPoolAlignment() << " bytes *****\n"
; } } while (false)
346 << MCP->getConstantPoolAlignment() << " bytes *****\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "***** ARMConstantIslands: "
<< MCP->getConstants().size() << " CP entries, aligned to "
<< MCP->getConstantPoolAlignment() << " bytes *****\n"
; } } while (false)
;
347
348 STI = &static_cast<const ARMSubtarget &>(MF->getSubtarget());
349 TII = STI->getInstrInfo();
350 isPositionIndependentOrROPI =
351 STI->getTargetLowering()->isPositionIndependent() || STI->isROPI();
1
Assuming the condition is false
352 AFI = MF->getInfo<ARMFunctionInfo>();
353
354 isThumb = AFI->isThumbFunction();
355 isThumb1 = AFI->isThumb1OnlyFunction();
356 isThumb2 = AFI->isThumb2Function();
357
358 HasFarJump = false;
359 bool GenerateTBB = isThumb2 || (isThumb1 && SynthesizeThumb1TBB);
360
361 // This pass invalidates liveness information when it splits basic blocks.
362 MF->getRegInfo().invalidateLiveness();
363
364 // Renumber all of the machine basic blocks in the function, guaranteeing that
365 // the numbers agree with the position of the block in the function.
366 MF->RenumberBlocks();
367
368 // Try to reorder and otherwise adjust the block layout to make good use
369 // of the TB[BH] instructions.
370 bool MadeChange = false;
371 if (GenerateTBB && AdjustJumpTableBlocks) {
372 scanFunctionJumpTables();
373 MadeChange |= reorderThumb2JumpTables();
374 // Data is out of date, so clear it. It'll be re-computed later.
375 T2JumpTables.clear();
376 // Blocks may have shifted around. Keep the numbering up to date.
377 MF->RenumberBlocks();
378 }
379
380 // Perform the initial placement of the constant pool entries. To start with,
381 // we put them all at the end of the function.
382 std::vector<MachineInstr*> CPEMIs;
383 if (!MCP->isEmpty())
2
Assuming the condition is false
3
Taking false branch
384 doInitialConstPlacement(CPEMIs);
385
386 if (MF->getJumpTableInfo())
4
Assuming the condition is false
5
Taking false branch
387 doInitialJumpTablePlacement(CPEMIs);
388
389 /// The next UID to take is the first unused one.
390 AFI->initPICLabelUId(CPEMIs.size());
391
392 // Do the initial scan of the function, building up information about the
393 // sizes of each block, the location of all the water, and finding all of the
394 // constant pool users.
395 initializeFunctionInfo(CPEMIs);
396 CPEMIs.clear();
397 LLVM_DEBUG(dumpBBs())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dumpBBs(); } } while (false)
;
398
399 // Functions with jump tables need an alignment of 4 because they use the ADR
400 // instruction, which aligns the PC to 4 bytes before adding an offset.
401 if (!T2JumpTables.empty())
6
Taking true branch
402 MF->ensureAlignment(2);
403
404 /// Remove dead constant pool entries.
405 MadeChange |= removeUnusedCPEntries();
406
407 // Iteratively place constant pool entries and fix up branches until there
408 // is no change.
409 unsigned NoCPIters = 0, NoBRIters = 0;
410 while (true) {
7
Loop condition is true. Entering loop body
411 LLVM_DEBUG(dbgs() << "Beginning CP iteration #" << NoCPIters << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Beginning CP iteration #"
<< NoCPIters << '\n'; } } while (false)
;
412 bool CPChange = false;
413 for (unsigned i = 0, e = CPUsers.size(); i != e; ++i)
8
Assuming 'i' is not equal to 'e'
9
Loop condition is true. Entering loop body
414 // For most inputs, it converges in no more than 5 iterations.
415 // If it doesn't end in 10, the input may have huge BB or many CPEs.
416 // In this case, we will try different heuristics.
417 CPChange |= handleConstantPoolUser(i, NoCPIters >= CPMaxIteration / 2);
10
Assuming the condition is false
11
Calling 'ARMConstantIslands::handleConstantPoolUser'
418 if (CPChange && ++NoCPIters > CPMaxIteration)
419 report_fatal_error("Constant Island pass failed to converge!");
420 LLVM_DEBUG(dumpBBs())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dumpBBs(); } } while (false)
;
421
422 // Clear NewWaterList now. If we split a block for branches, it should
423 // appear as "new water" for the next iteration of constant pool placement.
424 NewWaterList.clear();
425
426 LLVM_DEBUG(dbgs() << "Beginning BR iteration #" << NoBRIters << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Beginning BR iteration #"
<< NoBRIters << '\n'; } } while (false)
;
427 bool BRChange = false;
428 for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i)
429 BRChange |= fixupImmediateBr(ImmBranches[i]);
430 if (BRChange && ++NoBRIters > 30)
431 report_fatal_error("Branch Fix Up pass failed to converge!");
432 LLVM_DEBUG(dumpBBs())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dumpBBs(); } } while (false)
;
433
434 if (!CPChange && !BRChange)
435 break;
436 MadeChange = true;
437 }
438
439 // Shrink 32-bit Thumb2 load and store instructions.
440 if (isThumb2 && !STI->prefers32BitThumb())
441 MadeChange |= optimizeThumb2Instructions();
442
443 // Shrink 32-bit branch instructions.
444 if (isThumb && STI->hasV8MBaselineOps())
445 MadeChange |= optimizeThumb2Branches();
446
447 // Optimize jump tables using TBB / TBH.
448 if (GenerateTBB && !STI->genExecuteOnly())
449 MadeChange |= optimizeThumb2JumpTables();
450
451 // After a while, this might be made debug-only, but it is not expensive.
452 verify();
453
454 // If LR has been forced spilled and no far jump (i.e. BL) has been issued,
455 // undo the spill / restore of LR if possible.
456 if (isThumb && !HasFarJump && AFI->isLRSpilledForFarJump())
457 MadeChange |= undoLRSpillRestore();
458
459 // Save the mapping between original and cloned constpool entries.
460 for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) {
461 for (unsigned j = 0, je = CPEntries[i].size(); j != je; ++j) {
462 const CPEntry & CPE = CPEntries[i][j];
463 if (CPE.CPEMI && CPE.CPEMI->getOperand(1).isCPI())
464 AFI->recordCPEClone(i, CPE.CPI);
465 }
466 }
467
468 LLVM_DEBUG(dbgs() << '\n'; dumpBBs())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << '\n'; dumpBBs(); } } while
(false)
;
469
470 BBInfo.clear();
471 WaterList.clear();
472 CPUsers.clear();
473 CPEntries.clear();
474 JumpTableEntryIndices.clear();
475 JumpTableUserIndices.clear();
476 ImmBranches.clear();
477 PushPopMIs.clear();
478 T2JumpTables.clear();
479
480 return MadeChange;
481}
482
483/// Perform the initial placement of the regular constant pool entries.
484/// To start with, we put them all at the end of the function.
485void
486ARMConstantIslands::doInitialConstPlacement(std::vector<MachineInstr*> &CPEMIs) {
487 // Create the basic block to hold the CPE's.
488 MachineBasicBlock *BB = MF->CreateMachineBasicBlock();
489 MF->push_back(BB);
490
491 // MachineConstantPool measures alignment in bytes. We measure in log2(bytes).
492 unsigned MaxAlign = Log2_32(MCP->getConstantPoolAlignment());
493
494 // Mark the basic block as required by the const-pool.
495 BB->setAlignment(MaxAlign);
496
497 // The function needs to be as aligned as the basic blocks. The linker may
498 // move functions around based on their alignment.
499 MF->ensureAlignment(BB->getAlignment());
500
501 // Order the entries in BB by descending alignment. That ensures correct
502 // alignment of all entries as long as BB is sufficiently aligned. Keep
503 // track of the insertion point for each alignment. We are going to bucket
504 // sort the entries as they are created.
505 SmallVector<MachineBasicBlock::iterator, 8> InsPoint(MaxAlign + 1, BB->end());
506
507 // Add all of the constants from the constant pool to the end block, use an
508 // identity mapping of CPI's to CPE's.
509 const std::vector<MachineConstantPoolEntry> &CPs = MCP->getConstants();
510
511 const DataLayout &TD = MF->getDataLayout();
512 for (unsigned i = 0, e = CPs.size(); i != e; ++i) {
513 unsigned Size = TD.getTypeAllocSize(CPs[i].getType());
514 unsigned Align = CPs[i].getAlignment();
515 assert(isPowerOf2_32(Align) && "Invalid alignment")(static_cast <bool> (isPowerOf2_32(Align) && "Invalid alignment"
) ? void (0) : __assert_fail ("isPowerOf2_32(Align) && \"Invalid alignment\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 515, __extension__ __PRETTY_FUNCTION__))
;
516 // Verify that all constant pool entries are a multiple of their alignment.
517 // If not, we would have to pad them out so that instructions stay aligned.
518 assert((Size % Align) == 0 && "CP Entry not multiple of 4 bytes!")(static_cast <bool> ((Size % Align) == 0 && "CP Entry not multiple of 4 bytes!"
) ? void (0) : __assert_fail ("(Size % Align) == 0 && \"CP Entry not multiple of 4 bytes!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 518, __extension__ __PRETTY_FUNCTION__))
;
519
520 // Insert CONSTPOOL_ENTRY before entries with a smaller alignment.
521 unsigned LogAlign = Log2_32(Align);
522 MachineBasicBlock::iterator InsAt = InsPoint[LogAlign];
523 MachineInstr *CPEMI =
524 BuildMI(*BB, InsAt, DebugLoc(), TII->get(ARM::CONSTPOOL_ENTRY))
525 .addImm(i).addConstantPoolIndex(i).addImm(Size);
526 CPEMIs.push_back(CPEMI);
527
528 // Ensure that future entries with higher alignment get inserted before
529 // CPEMI. This is bucket sort with iterators.
530 for (unsigned a = LogAlign + 1; a <= MaxAlign; ++a)
531 if (InsPoint[a] == InsAt)
532 InsPoint[a] = CPEMI;
533
534 // Add a new CPEntry, but no corresponding CPUser yet.
535 CPEntries.emplace_back(1, CPEntry(CPEMI, i));
536 ++NumCPEs;
537 LLVM_DEBUG(dbgs() << "Moved CPI#" << i << " to end of function, size = "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Moved CPI#" << i
<< " to end of function, size = " << Size <<
", align = " << Align << '\n'; } } while (false)
538 << Size << ", align = " << Align << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Moved CPI#" << i
<< " to end of function, size = " << Size <<
", align = " << Align << '\n'; } } while (false)
;
539 }
540 LLVM_DEBUG(BB->dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { BB->dump(); } } while (false)
;
541}
542
543/// Do initial placement of the jump tables. Because Thumb2's TBB and TBH
544/// instructions can be made more efficient if the jump table immediately
545/// follows the instruction, it's best to place them immediately next to their
546/// jumps to begin with. In almost all cases they'll never be moved from that
547/// position.
548void ARMConstantIslands::doInitialJumpTablePlacement(
549 std::vector<MachineInstr *> &CPEMIs) {
550 unsigned i = CPEntries.size();
551 auto MJTI = MF->getJumpTableInfo();
552 const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables();
553
554 MachineBasicBlock *LastCorrectlyNumberedBB = nullptr;
555 for (MachineBasicBlock &MBB : *MF) {
556 auto MI = MBB.getLastNonDebugInstr();
557 if (MI == MBB.end())
558 continue;
559
560 unsigned JTOpcode;
561 switch (MI->getOpcode()) {
562 default:
563 continue;
564 case ARM::BR_JTadd:
565 case ARM::BR_JTr:
566 case ARM::tBR_JTr:
567 case ARM::BR_JTm_i12:
568 case ARM::BR_JTm_rs:
569 JTOpcode = ARM::JUMPTABLE_ADDRS;
570 break;
571 case ARM::t2BR_JT:
572 JTOpcode = ARM::JUMPTABLE_INSTS;
573 break;
574 case ARM::tTBB_JT:
575 case ARM::t2TBB_JT:
576 JTOpcode = ARM::JUMPTABLE_TBB;
577 break;
578 case ARM::tTBH_JT:
579 case ARM::t2TBH_JT:
580 JTOpcode = ARM::JUMPTABLE_TBH;
581 break;
582 }
583
584 unsigned NumOps = MI->getDesc().getNumOperands();
585 MachineOperand JTOp =
586 MI->getOperand(NumOps - (MI->isPredicable() ? 2 : 1));
587 unsigned JTI = JTOp.getIndex();
588 unsigned Size = JT[JTI].MBBs.size() * sizeof(uint32_t);
589 MachineBasicBlock *JumpTableBB = MF->CreateMachineBasicBlock();
590 MF->insert(std::next(MachineFunction::iterator(MBB)), JumpTableBB);
591 MachineInstr *CPEMI = BuildMI(*JumpTableBB, JumpTableBB->begin(),
592 DebugLoc(), TII->get(JTOpcode))
593 .addImm(i++)
594 .addJumpTableIndex(JTI)
595 .addImm(Size);
596 CPEMIs.push_back(CPEMI);
597 CPEntries.emplace_back(1, CPEntry(CPEMI, JTI));
598 JumpTableEntryIndices.insert(std::make_pair(JTI, CPEntries.size() - 1));
599 if (!LastCorrectlyNumberedBB)
600 LastCorrectlyNumberedBB = &MBB;
601 }
602
603 // If we did anything then we need to renumber the subsequent blocks.
604 if (LastCorrectlyNumberedBB)
605 MF->RenumberBlocks(LastCorrectlyNumberedBB);
606}
607
608/// BBHasFallthrough - Return true if the specified basic block can fallthrough
609/// into the block immediately after it.
610bool ARMConstantIslands::BBHasFallthrough(MachineBasicBlock *MBB) {
611 // Get the next machine basic block in the function.
612 MachineFunction::iterator MBBI = MBB->getIterator();
613 // Can't fall off end of function.
614 if (std::next(MBBI) == MBB->getParent()->end())
615 return false;
616
617 MachineBasicBlock *NextBB = &*std::next(MBBI);
618 if (!MBB->isSuccessor(NextBB))
619 return false;
620
621 // Try to analyze the end of the block. A potential fallthrough may already
622 // have an unconditional branch for whatever reason.
623 MachineBasicBlock *TBB, *FBB;
624 SmallVector<MachineOperand, 4> Cond;
625 bool TooDifficult = TII->analyzeBranch(*MBB, TBB, FBB, Cond);
626 return TooDifficult || FBB == nullptr;
627}
628
629/// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI,
630/// look up the corresponding CPEntry.
631ARMConstantIslands::CPEntry *
632ARMConstantIslands::findConstPoolEntry(unsigned CPI,
633 const MachineInstr *CPEMI) {
634 std::vector<CPEntry> &CPEs = CPEntries[CPI];
635 // Number of entries per constpool index should be small, just do a
636 // linear search.
637 for (unsigned i = 0, e = CPEs.size(); i != e; ++i) {
638 if (CPEs[i].CPEMI == CPEMI)
639 return &CPEs[i];
640 }
641 return nullptr;
642}
643
644/// getCPELogAlign - Returns the required alignment of the constant pool entry
645/// represented by CPEMI. Alignment is measured in log2(bytes) units.
646unsigned ARMConstantIslands::getCPELogAlign(const MachineInstr *CPEMI) {
647 switch (CPEMI->getOpcode()) {
648 case ARM::CONSTPOOL_ENTRY:
649 break;
650 case ARM::JUMPTABLE_TBB:
651 return isThumb1 ? 2 : 0;
652 case ARM::JUMPTABLE_TBH:
653 return isThumb1 ? 2 : 1;
654 case ARM::JUMPTABLE_INSTS:
655 return 1;
656 case ARM::JUMPTABLE_ADDRS:
657 return 2;
658 default:
659 llvm_unreachable("unknown constpool entry kind")::llvm::llvm_unreachable_internal("unknown constpool entry kind"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 659)
;
660 }
661
662 unsigned CPI = getCombinedIndex(CPEMI);
663 assert(CPI < MCP->getConstants().size() && "Invalid constant pool index.")(static_cast <bool> (CPI < MCP->getConstants().size
() && "Invalid constant pool index.") ? void (0) : __assert_fail
("CPI < MCP->getConstants().size() && \"Invalid constant pool index.\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 663, __extension__ __PRETTY_FUNCTION__))
;
664 unsigned Align = MCP->getConstants()[CPI].getAlignment();
665 assert(isPowerOf2_32(Align) && "Invalid CPE alignment")(static_cast <bool> (isPowerOf2_32(Align) && "Invalid CPE alignment"
) ? void (0) : __assert_fail ("isPowerOf2_32(Align) && \"Invalid CPE alignment\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 665, __extension__ __PRETTY_FUNCTION__))
;
666 return Log2_32(Align);
667}
668
669/// scanFunctionJumpTables - Do a scan of the function, building up
670/// information about the sizes of each block and the locations of all
671/// the jump tables.
672void ARMConstantIslands::scanFunctionJumpTables() {
673 for (MachineBasicBlock &MBB : *MF) {
674 for (MachineInstr &I : MBB)
675 if (I.isBranch() &&
676 (I.getOpcode() == ARM::t2BR_JT || I.getOpcode() == ARM::tBR_JTr))
677 T2JumpTables.push_back(&I);
678 }
679}
680
681/// initializeFunctionInfo - Do the initial scan of the function, building up
682/// information about the sizes of each block, the location of all the water,
683/// and finding all of the constant pool users.
684void ARMConstantIslands::
685initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs) {
686
687 BBInfo = computeAllBlockSizes(MF);
688
689 // The known bits of the entry block offset are determined by the function
690 // alignment.
691 BBInfo.front().KnownBits = MF->getAlignment();
692
693 // Compute block offsets and known bits.
694 adjustBBOffsetsAfter(&MF->front());
695
696 // Now go back through the instructions and build up our data structures.
697 for (MachineBasicBlock &MBB : *MF) {
698 // If this block doesn't fall through into the next MBB, then this is
699 // 'water' that a constant pool island could be placed.
700 if (!BBHasFallthrough(&MBB))
701 WaterList.push_back(&MBB);
702
703 for (MachineInstr &I : MBB) {
704 if (I.isDebugInstr())
705 continue;
706
707 unsigned Opc = I.getOpcode();
708 if (I.isBranch()) {
709 bool isCond = false;
710 unsigned Bits = 0;
711 unsigned Scale = 1;
712 int UOpc = Opc;
713 switch (Opc) {
714 default:
715 continue; // Ignore other JT branches
716 case ARM::t2BR_JT:
717 case ARM::tBR_JTr:
718 T2JumpTables.push_back(&I);
719 continue; // Does not get an entry in ImmBranches
720 case ARM::Bcc:
721 isCond = true;
722 UOpc = ARM::B;
723 LLVM_FALLTHROUGH[[clang::fallthrough]];
724 case ARM::B:
725 Bits = 24;
726 Scale = 4;
727 break;
728 case ARM::tBcc:
729 isCond = true;
730 UOpc = ARM::tB;
731 Bits = 8;
732 Scale = 2;
733 break;
734 case ARM::tB:
735 Bits = 11;
736 Scale = 2;
737 break;
738 case ARM::t2Bcc:
739 isCond = true;
740 UOpc = ARM::t2B;
741 Bits = 20;
742 Scale = 2;
743 break;
744 case ARM::t2B:
745 Bits = 24;
746 Scale = 2;
747 break;
748 }
749
750 // Record this immediate branch.
751 unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale;
752 ImmBranches.push_back(ImmBranch(&I, MaxOffs, isCond, UOpc));
753 }
754
755 if (Opc == ARM::tPUSH || Opc == ARM::tPOP_RET)
756 PushPopMIs.push_back(&I);
757
758 if (Opc == ARM::CONSTPOOL_ENTRY || Opc == ARM::JUMPTABLE_ADDRS ||
759 Opc == ARM::JUMPTABLE_INSTS || Opc == ARM::JUMPTABLE_TBB ||
760 Opc == ARM::JUMPTABLE_TBH)
761 continue;
762
763 // Scan the instructions for constant pool operands.
764 for (unsigned op = 0, e = I.getNumOperands(); op != e; ++op)
765 if (I.getOperand(op).isCPI() || I.getOperand(op).isJTI()) {
766 // We found one. The addressing mode tells us the max displacement
767 // from the PC that this instruction permits.
768
769 // Basic size info comes from the TSFlags field.
770 unsigned Bits = 0;
771 unsigned Scale = 1;
772 bool NegOk = false;
773 bool IsSoImm = false;
774
775 switch (Opc) {
776 default:
777 llvm_unreachable("Unknown addressing mode for CP reference!")::llvm::llvm_unreachable_internal("Unknown addressing mode for CP reference!"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 777)
;
778
779 // Taking the address of a CP entry.
780 case ARM::LEApcrel:
781 case ARM::LEApcrelJT:
782 // This takes a SoImm, which is 8 bit immediate rotated. We'll
783 // pretend the maximum offset is 255 * 4. Since each instruction
784 // 4 byte wide, this is always correct. We'll check for other
785 // displacements that fits in a SoImm as well.
786 Bits = 8;
787 Scale = 4;
788 NegOk = true;
789 IsSoImm = true;
790 break;
791 case ARM::t2LEApcrel:
792 case ARM::t2LEApcrelJT:
793 Bits = 12;
794 NegOk = true;
795 break;
796 case ARM::tLEApcrel:
797 case ARM::tLEApcrelJT:
798 Bits = 8;
799 Scale = 4;
800 break;
801
802 case ARM::LDRBi12:
803 case ARM::LDRi12:
804 case ARM::LDRcp:
805 case ARM::t2LDRpci:
806 case ARM::t2LDRHpci:
807 case ARM::t2LDRBpci:
808 Bits = 12; // +-offset_12
809 NegOk = true;
810 break;
811
812 case ARM::tLDRpci:
813 Bits = 8;
814 Scale = 4; // +(offset_8*4)
815 break;
816
817 case ARM::VLDRD:
818 case ARM::VLDRS:
819 Bits = 8;
820 Scale = 4; // +-(offset_8*4)
821 NegOk = true;
822 break;
823 case ARM::VLDRH:
824 Bits = 8;
825 Scale = 2; // +-(offset_8*2)
826 NegOk = true;
827 break;
828
829 case ARM::tLDRHi:
830 Bits = 5;
831 Scale = 2; // +(offset_5*2)
832 break;
833 }
834
835 // Remember that this is a user of a CP entry.
836 unsigned CPI = I.getOperand(op).getIndex();
837 if (I.getOperand(op).isJTI()) {
838 JumpTableUserIndices.insert(std::make_pair(CPI, CPUsers.size()));
839 CPI = JumpTableEntryIndices[CPI];
840 }
841
842 MachineInstr *CPEMI = CPEMIs[CPI];
843 unsigned MaxOffs = ((1 << Bits)-1) * Scale;
844 CPUsers.push_back(CPUser(&I, CPEMI, MaxOffs, NegOk, IsSoImm));
845
846 // Increment corresponding CPEntry reference count.
847 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
848 assert(CPE && "Cannot find a corresponding CPEntry!")(static_cast <bool> (CPE && "Cannot find a corresponding CPEntry!"
) ? void (0) : __assert_fail ("CPE && \"Cannot find a corresponding CPEntry!\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 848, __extension__ __PRETTY_FUNCTION__))
;
849 CPE->RefCount++;
850
851 // Instructions can only use one CP entry, don't bother scanning the
852 // rest of the operands.
853 break;
854 }
855 }
856 }
857}
858
859/// getOffsetOf - Return the current offset of the specified machine instruction
860/// from the start of the function. This offset changes as stuff is moved
861/// around inside the function.
862unsigned ARMConstantIslands::getOffsetOf(MachineInstr *MI) const {
863 MachineBasicBlock *MBB = MI->getParent();
864
865 // The offset is composed of two things: the sum of the sizes of all MBB's
866 // before this instruction's block, and the offset from the start of the block
867 // it is in.
868 unsigned Offset = BBInfo[MBB->getNumber()].Offset;
869
870 // Sum instructions before MI in MBB.
871 for (MachineBasicBlock::iterator I = MBB->begin(); &*I != MI; ++I) {
872 assert(I != MBB->end() && "Didn't find MI in its own basic block?")(static_cast <bool> (I != MBB->end() && "Didn't find MI in its own basic block?"
) ? void (0) : __assert_fail ("I != MBB->end() && \"Didn't find MI in its own basic block?\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 872, __extension__ __PRETTY_FUNCTION__))
;
873 Offset += TII->getInstSizeInBytes(*I);
874 }
875 return Offset;
876}
877
878/// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB
879/// ID.
880static bool CompareMBBNumbers(const MachineBasicBlock *LHS,
881 const MachineBasicBlock *RHS) {
882 return LHS->getNumber() < RHS->getNumber();
883}
884
885/// updateForInsertedWaterBlock - When a block is newly inserted into the
886/// machine function, it upsets all of the block numbers. Renumber the blocks
887/// and update the arrays that parallel this numbering.
888void ARMConstantIslands::updateForInsertedWaterBlock(MachineBasicBlock *NewBB) {
889 // Renumber the MBB's to keep them consecutive.
890 NewBB->getParent()->RenumberBlocks(NewBB);
891
892 // Insert an entry into BBInfo to align it properly with the (newly
893 // renumbered) block numbers.
894 BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
895
896 // Next, update WaterList. Specifically, we need to add NewMBB as having
897 // available water after it.
898 water_iterator IP =
899 std::lower_bound(WaterList.begin(), WaterList.end(), NewBB,
900 CompareMBBNumbers);
901 WaterList.insert(IP, NewBB);
902}
903
904/// Split the basic block containing MI into two blocks, which are joined by
905/// an unconditional branch. Update data structures and renumber blocks to
906/// account for this change and returns the newly created block.
907MachineBasicBlock *ARMConstantIslands::splitBlockBeforeInstr(MachineInstr *MI) {
908 MachineBasicBlock *OrigBB = MI->getParent();
909
910 // Create a new MBB for the code after the OrigBB.
911 MachineBasicBlock *NewBB =
912 MF->CreateMachineBasicBlock(OrigBB->getBasicBlock());
913 MachineFunction::iterator MBBI = ++OrigBB->getIterator();
914 MF->insert(MBBI, NewBB);
915
916 // Splice the instructions starting with MI over to NewBB.
917 NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end());
918
919 // Add an unconditional branch from OrigBB to NewBB.
920 // Note the new unconditional branch is not being recorded.
921 // There doesn't seem to be meaningful DebugInfo available; this doesn't
922 // correspond to anything in the source.
923 unsigned Opc = isThumb ? (isThumb2 ? ARM::t2B : ARM::tB) : ARM::B;
924 if (!isThumb)
925 BuildMI(OrigBB, DebugLoc(), TII->get(Opc)).addMBB(NewBB);
926 else
927 BuildMI(OrigBB, DebugLoc(), TII->get(Opc))
928 .addMBB(NewBB)
929 .add(predOps(ARMCC::AL));
930 ++NumSplit;
931
932 // Update the CFG. All succs of OrigBB are now succs of NewBB.
933 NewBB->transferSuccessors(OrigBB);
934
935 // OrigBB branches to NewBB.
936 OrigBB->addSuccessor(NewBB);
937
938 // Update internal data structures to account for the newly inserted MBB.
939 // This is almost the same as updateForInsertedWaterBlock, except that
940 // the Water goes after OrigBB, not NewBB.
941 MF->RenumberBlocks(NewBB);
942
943 // Insert an entry into BBInfo to align it properly with the (newly
944 // renumbered) block numbers.
945 BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo());
946
947 // Next, update WaterList. Specifically, we need to add OrigMBB as having
948 // available water after it (but not if it's already there, which happens
949 // when splitting before a conditional branch that is followed by an
950 // unconditional branch - in that case we want to insert NewBB).
951 water_iterator IP =
952 std::lower_bound(WaterList.begin(), WaterList.end(), OrigBB,
953 CompareMBBNumbers);
954 MachineBasicBlock* WaterBB = *IP;
955 if (WaterBB == OrigBB)
956 WaterList.insert(std::next(IP), NewBB);
957 else
958 WaterList.insert(IP, OrigBB);
959 NewWaterList.insert(OrigBB);
960
961 // Figure out how large the OrigBB is. As the first half of the original
962 // block, it cannot contain a tablejump. The size includes
963 // the new jump we added. (It should be possible to do this without
964 // recounting everything, but it's very confusing, and this is rarely
965 // executed.)
966 computeBlockSize(MF, OrigBB, BBInfo[OrigBB->getNumber()]);
967
968 // Figure out how large the NewMBB is. As the second half of the original
969 // block, it may contain a tablejump.
970 computeBlockSize(MF, NewBB, BBInfo[NewBB->getNumber()]);
971
972 // All BBOffsets following these blocks must be modified.
973 adjustBBOffsetsAfter(OrigBB);
974
975 return NewBB;
976}
977
978/// getUserOffset - Compute the offset of U.MI as seen by the hardware
979/// displacement computation. Update U.KnownAlignment to match its current
980/// basic block location.
981unsigned ARMConstantIslands::getUserOffset(CPUser &U) const {
982 unsigned UserOffset = getOffsetOf(U.MI);
983 const BasicBlockInfo &BBI = BBInfo[U.MI->getParent()->getNumber()];
984 unsigned KnownBits = BBI.internalKnownBits();
985
986 // The value read from PC is offset from the actual instruction address.
987 UserOffset += (isThumb ? 4 : 8);
988
989 // Because of inline assembly, we may not know the alignment (mod 4) of U.MI.
990 // Make sure U.getMaxDisp() returns a constrained range.
991 U.KnownAlignment = (KnownBits >= 2);
992
993 // On Thumb, offsets==2 mod 4 are rounded down by the hardware for
994 // purposes of the displacement computation; compensate for that here.
995 // For unknown alignments, getMaxDisp() constrains the range instead.
996 if (isThumb && U.KnownAlignment)
997 UserOffset &= ~3u;
998
999 return UserOffset;
1000}
1001
1002/// isOffsetInRange - Checks whether UserOffset (the location of a constant pool
1003/// reference) is within MaxDisp of TrialOffset (a proposed location of a
1004/// constant pool entry).
1005/// UserOffset is computed by getUserOffset above to include PC adjustments. If
1006/// the mod 4 alignment of UserOffset is not known, the uncertainty must be
1007/// subtracted from MaxDisp instead. CPUser::getMaxDisp() does that.
1008bool ARMConstantIslands::isOffsetInRange(unsigned UserOffset,
1009 unsigned TrialOffset, unsigned MaxDisp,
1010 bool NegativeOK, bool IsSoImm) {
1011 if (UserOffset <= TrialOffset) {
1012 // User before the Trial.
1013 if (TrialOffset - UserOffset <= MaxDisp)
1014 return true;
1015 // FIXME: Make use full range of soimm values.
1016 } else if (NegativeOK) {
1017 if (UserOffset - TrialOffset <= MaxDisp)
1018 return true;
1019 // FIXME: Make use full range of soimm values.
1020 }
1021 return false;
1022}
1023
1024/// isWaterInRange - Returns true if a CPE placed after the specified
1025/// Water (a basic block) will be in range for the specific MI.
1026///
1027/// Compute how much the function will grow by inserting a CPE after Water.
1028bool ARMConstantIslands::isWaterInRange(unsigned UserOffset,
1029 MachineBasicBlock* Water, CPUser &U,
1030 unsigned &Growth) {
1031 unsigned CPELogAlign = getCPELogAlign(U.CPEMI);
1032 unsigned CPEOffset = BBInfo[Water->getNumber()].postOffset(CPELogAlign);
1033 unsigned NextBlockOffset, NextBlockAlignment;
1034 MachineFunction::const_iterator NextBlock = Water->getIterator();
1035 if (++NextBlock == MF->end()) {
1036 NextBlockOffset = BBInfo[Water->getNumber()].postOffset();
1037 NextBlockAlignment = 0;
1038 } else {
1039 NextBlockOffset = BBInfo[NextBlock->getNumber()].Offset;
1040 NextBlockAlignment = NextBlock->getAlignment();
1041 }
1042 unsigned Size = U.CPEMI->getOperand(2).getImm();
1043 unsigned CPEEnd = CPEOffset + Size;
1044
1045 // The CPE may be able to hide in the alignment padding before the next
1046 // block. It may also cause more padding to be required if it is more aligned
1047 // that the next block.
1048 if (CPEEnd > NextBlockOffset) {
1049 Growth = CPEEnd - NextBlockOffset;
1050 // Compute the padding that would go at the end of the CPE to align the next
1051 // block.
1052 Growth += OffsetToAlignment(CPEEnd, 1ULL << NextBlockAlignment);
1053
1054 // If the CPE is to be inserted before the instruction, that will raise
1055 // the offset of the instruction. Also account for unknown alignment padding
1056 // in blocks between CPE and the user.
1057 if (CPEOffset < UserOffset)
1058 UserOffset += Growth + UnknownPadding(MF->getAlignment(), CPELogAlign);
1059 } else
1060 // CPE fits in existing padding.
1061 Growth = 0;
1062
1063 return isOffsetInRange(UserOffset, CPEOffset, U);
1064}
1065
1066/// isCPEntryInRange - Returns true if the distance between specific MI and
1067/// specific ConstPool entry instruction can fit in MI's displacement field.
1068bool ARMConstantIslands::isCPEntryInRange(MachineInstr *MI, unsigned UserOffset,
1069 MachineInstr *CPEMI, unsigned MaxDisp,
1070 bool NegOk, bool DoDump) {
1071 unsigned CPEOffset = getOffsetOf(CPEMI);
1072
1073 if (DoDump) {
1074 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { { unsigned Block = MI->getParent()->
getNumber(); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs
() << "User of CPE#" << CPEMI->getOperand(0).getImm
() << " max delta=" << MaxDisp << format(" insn address=%#x"
, UserOffset) << " in " << printMBBReference(*MI->
getParent()) << ": " << format("%#x-%x\t", BBI.Offset
, BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: "
, CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false
)
1075 unsigned Block = MI->getParent()->getNumber();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { { unsigned Block = MI->getParent()->
getNumber(); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs
() << "User of CPE#" << CPEMI->getOperand(0).getImm
() << " max delta=" << MaxDisp << format(" insn address=%#x"
, UserOffset) << " in " << printMBBReference(*MI->
getParent()) << ": " << format("%#x-%x\t", BBI.Offset
, BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: "
, CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false
)
1076 const BasicBlockInfo &BBI = BBInfo[Block];do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { { unsigned Block = MI->getParent()->
getNumber(); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs
() << "User of CPE#" << CPEMI->getOperand(0).getImm
() << " max delta=" << MaxDisp << format(" insn address=%#x"
, UserOffset) << " in " << printMBBReference(*MI->
getParent()) << ": " << format("%#x-%x\t", BBI.Offset
, BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: "
, CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false
)
1077 dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { { unsigned Block = MI->getParent()->
getNumber(); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs
() << "User of CPE#" << CPEMI->getOperand(0).getImm
() << " max delta=" << MaxDisp << format(" insn address=%#x"
, UserOffset) << " in " << printMBBReference(*MI->
getParent()) << ": " << format("%#x-%x\t", BBI.Offset
, BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: "
, CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false
)
1078 << " max delta=" << MaxDispdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { { unsigned Block = MI->getParent()->
getNumber(); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs
() << "User of CPE#" << CPEMI->getOperand(0).getImm
() << " max delta=" << MaxDisp << format(" insn address=%#x"
, UserOffset) << " in " << printMBBReference(*MI->
getParent()) << ": " << format("%#x-%x\t", BBI.Offset
, BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: "
, CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false
)
1079 << format(" insn address=%#x", UserOffset) << " in "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { { unsigned Block = MI->getParent()->
getNumber(); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs
() << "User of CPE#" << CPEMI->getOperand(0).getImm
() << " max delta=" << MaxDisp << format(" insn address=%#x"
, UserOffset) << " in " << printMBBReference(*MI->
getParent()) << ": " << format("%#x-%x\t", BBI.Offset
, BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: "
, CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false
)
1080 << printMBBReference(*MI->getParent()) << ": "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { { unsigned Block = MI->getParent()->
getNumber(); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs
() << "User of CPE#" << CPEMI->getOperand(0).getImm
() << " max delta=" << MaxDisp << format(" insn address=%#x"
, UserOffset) << " in " << printMBBReference(*MI->
getParent()) << ": " << format("%#x-%x\t", BBI.Offset
, BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: "
, CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false
)
1081 << format("%#x-%x\t", BBI.Offset, BBI.postOffset()) << *MIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { { unsigned Block = MI->getParent()->
getNumber(); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs
() << "User of CPE#" << CPEMI->getOperand(0).getImm
() << " max delta=" << MaxDisp << format(" insn address=%#x"
, UserOffset) << " in " << printMBBReference(*MI->
getParent()) << ": " << format("%#x-%x\t", BBI.Offset
, BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: "
, CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false
)
1082 << format("CPE address=%#x offset=%+d: ", CPEOffset,do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { { unsigned Block = MI->getParent()->
getNumber(); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs
() << "User of CPE#" << CPEMI->getOperand(0).getImm
() << " max delta=" << MaxDisp << format(" insn address=%#x"
, UserOffset) << " in " << printMBBReference(*MI->
getParent()) << ": " << format("%#x-%x\t", BBI.Offset
, BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: "
, CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false
)
1083 int(CPEOffset - UserOffset));do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { { unsigned Block = MI->getParent()->
getNumber(); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs
() << "User of CPE#" << CPEMI->getOperand(0).getImm
() << " max delta=" << MaxDisp << format(" insn address=%#x"
, UserOffset) << " in " << printMBBReference(*MI->
getParent()) << ": " << format("%#x-%x\t", BBI.Offset
, BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: "
, CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false
)
1084 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { { unsigned Block = MI->getParent()->
getNumber(); const BasicBlockInfo &BBI = BBInfo[Block]; dbgs
() << "User of CPE#" << CPEMI->getOperand(0).getImm
() << " max delta=" << MaxDisp << format(" insn address=%#x"
, UserOffset) << " in " << printMBBReference(*MI->
getParent()) << ": " << format("%#x-%x\t", BBI.Offset
, BBI.postOffset()) << *MI << format("CPE address=%#x offset=%+d: "
, CPEOffset, int(CPEOffset - UserOffset)); }; } } while (false
)
;
1085 }
1086
1087 return isOffsetInRange(UserOffset, CPEOffset, MaxDisp, NegOk);
1088}
1089
1090#ifndef NDEBUG
1091/// BBIsJumpedOver - Return true of the specified basic block's only predecessor
1092/// unconditionally branches to its only successor.
1093static bool BBIsJumpedOver(MachineBasicBlock *MBB) {
1094 if (MBB->pred_size() != 1 || MBB->succ_size() != 1)
1095 return false;
1096
1097 MachineBasicBlock *Succ = *MBB->succ_begin();
1098 MachineBasicBlock *Pred = *MBB->pred_begin();
1099 MachineInstr *PredMI = &Pred->back();
1100 if (PredMI->getOpcode() == ARM::B || PredMI->getOpcode() == ARM::tB
1101 || PredMI->getOpcode() == ARM::t2B)
1102 return PredMI->getOperand(0).getMBB() == Succ;
1103 return false;
1104}
1105#endif // NDEBUG
1106
1107void ARMConstantIslands::adjustBBOffsetsAfter(MachineBasicBlock *BB) {
1108 unsigned BBNum = BB->getNumber();
1109 for(unsigned i = BBNum + 1, e = MF->getNumBlockIDs(); i < e; ++i) {
1110 // Get the offset and known bits at the end of the layout predecessor.
1111 // Include the alignment of the current block.
1112 unsigned LogAlign = MF->getBlockNumbered(i)->getAlignment();
1113 unsigned Offset = BBInfo[i - 1].postOffset(LogAlign);
1114 unsigned KnownBits = BBInfo[i - 1].postKnownBits(LogAlign);
1115
1116 // This is where block i begins. Stop if the offset is already correct,
1117 // and we have updated 2 blocks. This is the maximum number of blocks
1118 // changed before calling this function.
1119 if (i > BBNum + 2 &&
1120 BBInfo[i].Offset == Offset &&
1121 BBInfo[i].KnownBits == KnownBits)
1122 break;
1123
1124 BBInfo[i].Offset = Offset;
1125 BBInfo[i].KnownBits = KnownBits;
1126 }
1127}
1128
1129/// decrementCPEReferenceCount - find the constant pool entry with index CPI
1130/// and instruction CPEMI, and decrement its refcount. If the refcount
1131/// becomes 0 remove the entry and instruction. Returns true if we removed
1132/// the entry, false if we didn't.
1133bool ARMConstantIslands::decrementCPEReferenceCount(unsigned CPI,
1134 MachineInstr *CPEMI) {
1135 // Find the old entry. Eliminate it if it is no longer used.
1136 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI);
1137 assert(CPE && "Unexpected!")(static_cast <bool> (CPE && "Unexpected!") ? void
(0) : __assert_fail ("CPE && \"Unexpected!\"", "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 1137, __extension__ __PRETTY_FUNCTION__))
;
1138 if (--CPE->RefCount == 0) {
1139 removeDeadCPEMI(CPEMI);
1140 CPE->CPEMI = nullptr;
1141 --NumCPEs;
1142 return true;
1143 }
1144 return false;
1145}
1146
1147unsigned ARMConstantIslands::getCombinedIndex(const MachineInstr *CPEMI) {
1148 if (CPEMI->getOperand(1).isCPI())
1149 return CPEMI->getOperand(1).getIndex();
1150
1151 return JumpTableEntryIndices[CPEMI->getOperand(1).getIndex()];
1152}
1153
1154/// LookForCPEntryInRange - see if the currently referenced CPE is in range;
1155/// if not, see if an in-range clone of the CPE is in range, and if so,
1156/// change the data structures so the user references the clone. Returns:
1157/// 0 = no existing entry found
1158/// 1 = entry found, and there were no code insertions or deletions
1159/// 2 = entry found, and there were code insertions or deletions
1160int ARMConstantIslands::findInRangeCPEntry(CPUser& U, unsigned UserOffset) {
1161 MachineInstr *UserMI = U.MI;
1162 MachineInstr *CPEMI = U.CPEMI;
1163
1164 // Check to see if the CPE is already in-range.
1165 if (isCPEntryInRange(UserMI, UserOffset, CPEMI, U.getMaxDisp(), U.NegOk,
1166 true)) {
1167 LLVM_DEBUG(dbgs() << "In range\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "In range\n"; } } while
(false)
;
1168 return 1;
1169 }
1170
1171 // No. Look for previously created clones of the CPE that are in range.
1172 unsigned CPI = getCombinedIndex(CPEMI);
1173 std::vector<CPEntry> &CPEs = CPEntries[CPI];
1174 for (unsigned i = 0, e = CPEs.size(); i != e; ++i) {
1175 // We already tried this one
1176 if (CPEs[i].CPEMI == CPEMI)
1177 continue;
1178 // Removing CPEs can leave empty entries, skip
1179 if (CPEs[i].CPEMI == nullptr)
1180 continue;
1181 if (isCPEntryInRange(UserMI, UserOffset, CPEs[i].CPEMI, U.getMaxDisp(),
1182 U.NegOk)) {
1183 LLVM_DEBUG(dbgs() << "Replacing CPE#" << CPI << " with CPE#"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Replacing CPE#" <<
CPI << " with CPE#" << CPEs[i].CPI << "\n"
; } } while (false)
1184 << CPEs[i].CPI << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Replacing CPE#" <<
CPI << " with CPE#" << CPEs[i].CPI << "\n"
; } } while (false)
;
1185 // Point the CPUser node to the replacement
1186 U.CPEMI = CPEs[i].CPEMI;
1187 // Change the CPI in the instruction operand to refer to the clone.
1188 for (unsigned j = 0, e = UserMI->getNumOperands(); j != e; ++j)
1189 if (UserMI->getOperand(j).isCPI()) {
1190 UserMI->getOperand(j).setIndex(CPEs[i].CPI);
1191 break;
1192 }
1193 // Adjust the refcount of the clone...
1194 CPEs[i].RefCount++;
1195 // ...and the original. If we didn't remove the old entry, none of the
1196 // addresses changed, so we don't need another pass.
1197 return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1;
1198 }
1199 }
1200 return 0;
1201}
1202
1203/// getUnconditionalBrDisp - Returns the maximum displacement that can fit in
1204/// the specific unconditional branch instruction.
1205static inline unsigned getUnconditionalBrDisp(int Opc) {
1206 switch (Opc) {
1207 case ARM::tB:
1208 return ((1<<10)-1)*2;
1209 case ARM::t2B:
1210 return ((1<<23)-1)*2;
1211 default:
1212 break;
1213 }
1214
1215 return ((1<<23)-1)*4;
1216}
1217
1218/// findAvailableWater - Look for an existing entry in the WaterList in which
1219/// we can place the CPE referenced from U so it's within range of U's MI.
1220/// Returns true if found, false if not. If it returns true, WaterIter
1221/// is set to the WaterList entry. For Thumb, prefer water that will not
1222/// introduce padding to water that will. To ensure that this pass
1223/// terminates, the CPE location for a particular CPUser is only allowed to
1224/// move to a lower address, so search backward from the end of the list and
1225/// prefer the first water that is in range.
1226bool ARMConstantIslands::findAvailableWater(CPUser &U, unsigned UserOffset,
1227 water_iterator &WaterIter,
1228 bool CloserWater) {
1229 if (WaterList.empty())
1230 return false;
1231
1232 unsigned BestGrowth = ~0u;
1233 // The nearest water without splitting the UserBB is right after it.
1234 // If the distance is still large (we have a big BB), then we need to split it
1235 // if we don't converge after certain iterations. This helps the following
1236 // situation to converge:
1237 // BB0:
1238 // Big BB
1239 // BB1:
1240 // Constant Pool
1241 // When a CP access is out of range, BB0 may be used as water. However,
1242 // inserting islands between BB0 and BB1 makes other accesses out of range.
1243 MachineBasicBlock *UserBB = U.MI->getParent();
1244 unsigned MinNoSplitDisp =
1245 BBInfo[UserBB->getNumber()].postOffset(getCPELogAlign(U.CPEMI));
1246 if (CloserWater && MinNoSplitDisp > U.getMaxDisp() / 2)
1247 return false;
1248 for (water_iterator IP = std::prev(WaterList.end()), B = WaterList.begin();;
1249 --IP) {
1250 MachineBasicBlock* WaterBB = *IP;
1251 // Check if water is in range and is either at a lower address than the
1252 // current "high water mark" or a new water block that was created since
1253 // the previous iteration by inserting an unconditional branch. In the
1254 // latter case, we want to allow resetting the high water mark back to
1255 // this new water since we haven't seen it before. Inserting branches
1256 // should be relatively uncommon and when it does happen, we want to be
1257 // sure to take advantage of it for all the CPEs near that block, so that
1258 // we don't insert more branches than necessary.
1259 // When CloserWater is true, we try to find the lowest address after (or
1260 // equal to) user MI's BB no matter of padding growth.
1261 unsigned Growth;
1262 if (isWaterInRange(UserOffset, WaterBB, U, Growth) &&
1263 (WaterBB->getNumber() < U.HighWaterMark->getNumber() ||
1264 NewWaterList.count(WaterBB) || WaterBB == U.MI->getParent()) &&
1265 Growth < BestGrowth) {
1266 // This is the least amount of required padding seen so far.
1267 BestGrowth = Growth;
1268 WaterIter = IP;
1269 LLVM_DEBUG(dbgs() << "Found water after " << printMBBReference(*WaterBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Found water after " <<
printMBBReference(*WaterBB) << " Growth=" << Growth
<< '\n'; } } while (false)
1270 << " Growth=" << Growth << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Found water after " <<
printMBBReference(*WaterBB) << " Growth=" << Growth
<< '\n'; } } while (false)
;
1271
1272 if (CloserWater && WaterBB == U.MI->getParent())
1273 return true;
1274 // Keep looking unless it is perfect and we're not looking for the lowest
1275 // possible address.
1276 if (!CloserWater && BestGrowth == 0)
1277 return true;
1278 }
1279 if (IP == B)
1280 break;
1281 }
1282 return BestGrowth != ~0u;
1283}
1284
1285/// createNewWater - No existing WaterList entry will work for
1286/// CPUsers[CPUserIndex], so create a place to put the CPE. The end of the
1287/// block is used if in range, and the conditional branch munged so control
1288/// flow is correct. Otherwise the block is split to create a hole with an
1289/// unconditional branch around it. In either case NewMBB is set to a
1290/// block following which the new island can be inserted (the WaterList
1291/// is not adjusted).
1292void ARMConstantIslands::createNewWater(unsigned CPUserIndex,
1293 unsigned UserOffset,
1294 MachineBasicBlock *&NewMBB) {
1295 CPUser &U = CPUsers[CPUserIndex];
1296 MachineInstr *UserMI = U.MI;
1297 MachineInstr *CPEMI = U.CPEMI;
1298 unsigned CPELogAlign = getCPELogAlign(CPEMI);
1299 MachineBasicBlock *UserMBB = UserMI->getParent();
1300 const BasicBlockInfo &UserBBI = BBInfo[UserMBB->getNumber()];
1301
1302 // If the block does not end in an unconditional branch already, and if the
1303 // end of the block is within range, make new water there. (The addition
1304 // below is for the unconditional branch we will be adding: 4 bytes on ARM +
1305 // Thumb2, 2 on Thumb1.
1306 if (BBHasFallthrough(UserMBB)) {
16
Taking false branch
1307 // Size of branch to insert.
1308 unsigned Delta = isThumb1 ? 2 : 4;
1309 // Compute the offset where the CPE will begin.
1310 unsigned CPEOffset = UserBBI.postOffset(CPELogAlign) + Delta;
1311
1312 if (isOffsetInRange(UserOffset, CPEOffset, U)) {
1313 LLVM_DEBUG(dbgs() << "Split at end of " << printMBBReference(*UserMBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Split at end of " <<
printMBBReference(*UserMBB) << format(", expected CPE offset %#x\n"
, CPEOffset); } } while (false)
1314 << format(", expected CPE offset %#x\n", CPEOffset))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Split at end of " <<
printMBBReference(*UserMBB) << format(", expected CPE offset %#x\n"
, CPEOffset); } } while (false)
;
1315 NewMBB = &*++UserMBB->getIterator();
1316 // Add an unconditional branch from UserMBB to fallthrough block. Record
1317 // it for branch lengthening; this new branch will not get out of range,
1318 // but if the preceding conditional branch is out of range, the targets
1319 // will be exchanged, and the altered branch may be out of range, so the
1320 // machinery has to know about it.
1321 int UncondBr = isThumb ? ((isThumb2) ? ARM::t2B : ARM::tB) : ARM::B;
1322 if (!isThumb)
1323 BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr)).addMBB(NewMBB);
1324 else
1325 BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr))
1326 .addMBB(NewMBB)
1327 .add(predOps(ARMCC::AL));
1328 unsigned MaxDisp = getUnconditionalBrDisp(UncondBr);
1329 ImmBranches.push_back(ImmBranch(&UserMBB->back(),
1330 MaxDisp, false, UncondBr));
1331 computeBlockSize(MF, UserMBB, BBInfo[UserMBB->getNumber()]);
1332 adjustBBOffsetsAfter(UserMBB);
1333 return;
1334 }
1335 }
1336
1337 // What a big block. Find a place within the block to split it. This is a
1338 // little tricky on Thumb1 since instructions are 2 bytes and constant pool
1339 // entries are 4 bytes: if instruction I references island CPE, and
1340 // instruction I+1 references CPE', it will not work well to put CPE as far
1341 // forward as possible, since then CPE' cannot immediately follow it (that
1342 // location is 2 bytes farther away from I+1 than CPE was from I) and we'd
1343 // need to create a new island. So, we make a first guess, then walk through
1344 // the instructions between the one currently being looked at and the
1345 // possible insertion point, and make sure any other instructions that
1346 // reference CPEs will be able to use the same island area; if not, we back
1347 // up the insertion point.
1348
1349 // Try to split the block so it's fully aligned. Compute the latest split
1350 // point where we can add a 4-byte branch instruction, and then align to
1351 // LogAlign which is the largest possible alignment in the function.
1352 unsigned LogAlign = MF->getAlignment();
1353 assert(LogAlign >= CPELogAlign && "Over-aligned constant pool entry")(static_cast <bool> (LogAlign >= CPELogAlign &&
"Over-aligned constant pool entry") ? void (0) : __assert_fail
("LogAlign >= CPELogAlign && \"Over-aligned constant pool entry\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 1353, __extension__ __PRETTY_FUNCTION__))
;
1354 unsigned KnownBits = UserBBI.internalKnownBits();
1355 unsigned UPad = UnknownPadding(LogAlign, KnownBits);
17
Calling 'UnknownPadding'
1356 unsigned BaseInsertOffset = UserOffset + U.getMaxDisp() - UPad;
1357 LLVM_DEBUG(dbgs() << format("Split in middle of big block before %#x",do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << format("Split in middle of big block before %#x"
, BaseInsertOffset); } } while (false)
1358 BaseInsertOffset))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << format("Split in middle of big block before %#x"
, BaseInsertOffset); } } while (false)
;
1359
1360 // The 4 in the following is for the unconditional branch we'll be inserting
1361 // (allows for long branch on Thumb1). Alignment of the island is handled
1362 // inside isOffsetInRange.
1363 BaseInsertOffset -= 4;
1364
1365 LLVM_DEBUG(dbgs() << format(", adjusted to %#x", BaseInsertOffset)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << format(", adjusted to %#x"
, BaseInsertOffset) << " la=" << LogAlign <<
" kb=" << KnownBits << " up=" << UPad <<
'\n'; } } while (false)
1366 << " la=" << LogAlign << " kb=" << KnownBitsdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << format(", adjusted to %#x"
, BaseInsertOffset) << " la=" << LogAlign <<
" kb=" << KnownBits << " up=" << UPad <<
'\n'; } } while (false)
1367 << " up=" << UPad << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << format(", adjusted to %#x"
, BaseInsertOffset) << " la=" << LogAlign <<
" kb=" << KnownBits << " up=" << UPad <<
'\n'; } } while (false)
;
1368
1369 // This could point off the end of the block if we've already got constant
1370 // pool entries following this block; only the last one is in the water list.
1371 // Back past any possible branches (allow for a conditional and a maximally
1372 // long unconditional).
1373 if (BaseInsertOffset + 8 >= UserBBI.postOffset()) {
1374 // Ensure BaseInsertOffset is larger than the offset of the instruction
1375 // following UserMI so that the loop which searches for the split point
1376 // iterates at least once.
1377 BaseInsertOffset =
1378 std::max(UserBBI.postOffset() - UPad - 8,
1379 UserOffset + TII->getInstSizeInBytes(*UserMI) + 1);
1380 LLVM_DEBUG(dbgs() << format("Move inside block: %#x\n", BaseInsertOffset))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << format("Move inside block: %#x\n"
, BaseInsertOffset); } } while (false)
;
1381 }
1382 unsigned EndInsertOffset = BaseInsertOffset + 4 + UPad +
1383 CPEMI->getOperand(2).getImm();
1384 MachineBasicBlock::iterator MI = UserMI;
1385 ++MI;
1386 unsigned CPUIndex = CPUserIndex+1;
1387 unsigned NumCPUsers = CPUsers.size();
1388 MachineInstr *LastIT = nullptr;
1389 for (unsigned Offset = UserOffset + TII->getInstSizeInBytes(*UserMI);
1390 Offset < BaseInsertOffset;
1391 Offset += TII->getInstSizeInBytes(*MI), MI = std::next(MI)) {
1392 assert(MI != UserMBB->end() && "Fell off end of block")(static_cast <bool> (MI != UserMBB->end() &&
"Fell off end of block") ? void (0) : __assert_fail ("MI != UserMBB->end() && \"Fell off end of block\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 1392, __extension__ __PRETTY_FUNCTION__))
;
1393 if (CPUIndex < NumCPUsers && CPUsers[CPUIndex].MI == &*MI) {
1394 CPUser &U = CPUsers[CPUIndex];
1395 if (!isOffsetInRange(Offset, EndInsertOffset, U)) {
1396 // Shift intertion point by one unit of alignment so it is within reach.
1397 BaseInsertOffset -= 1u << LogAlign;
1398 EndInsertOffset -= 1u << LogAlign;
1399 }
1400 // This is overly conservative, as we don't account for CPEMIs being
1401 // reused within the block, but it doesn't matter much. Also assume CPEs
1402 // are added in order with alignment padding. We may eventually be able
1403 // to pack the aligned CPEs better.
1404 EndInsertOffset += U.CPEMI->getOperand(2).getImm();
1405 CPUIndex++;
1406 }
1407
1408 // Remember the last IT instruction.
1409 if (MI->getOpcode() == ARM::t2IT)
1410 LastIT = &*MI;
1411 }
1412
1413 --MI;
1414
1415 // Avoid splitting an IT block.
1416 if (LastIT) {
1417 unsigned PredReg = 0;
1418 ARMCC::CondCodes CC = getITInstrPredicate(*MI, PredReg);
1419 if (CC != ARMCC::AL)
1420 MI = LastIT;
1421 }
1422
1423 // We really must not split an IT block.
1424 LLVM_DEBUG(unsigned PredReg; assert(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { unsigned PredReg; (static_cast <bool
> (!isThumb || getITInstrPredicate(*MI, PredReg) == ARMCC::
AL) ? void (0) : __assert_fail ("!isThumb || getITInstrPredicate(*MI, PredReg) == ARMCC::AL"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 1425, __extension__ __PRETTY_FUNCTION__)); } } while (false
)
1425 !isThumb || getITInstrPredicate(*MI, PredReg) == ARMCC::AL))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { unsigned PredReg; (static_cast <bool
> (!isThumb || getITInstrPredicate(*MI, PredReg) == ARMCC::
AL) ? void (0) : __assert_fail ("!isThumb || getITInstrPredicate(*MI, PredReg) == ARMCC::AL"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 1425, __extension__ __PRETTY_FUNCTION__)); } } while (false
)
;
1426
1427 NewMBB = splitBlockBeforeInstr(&*MI);
1428}
1429
1430/// handleConstantPoolUser - Analyze the specified user, checking to see if it
1431/// is out-of-range. If so, pick up the constant pool value and move it some
1432/// place in-range. Return true if we changed any addresses (thus must run
1433/// another pass of branch lengthening), false otherwise.
1434bool ARMConstantIslands::handleConstantPoolUser(unsigned CPUserIndex,
1435 bool CloserWater) {
1436 CPUser &U = CPUsers[CPUserIndex];
1437 MachineInstr *UserMI = U.MI;
1438 MachineInstr *CPEMI = U.CPEMI;
1439 unsigned CPI = getCombinedIndex(CPEMI);
1440 unsigned Size = CPEMI->getOperand(2).getImm();
1441 // Compute this only once, it's expensive.
1442 unsigned UserOffset = getUserOffset(U);
1443
1444 // See if the current entry is within range, or there is a clone of it
1445 // in range.
1446 int result = findInRangeCPEntry(U, UserOffset);
1447 if (result==1) return false;
12
Taking false branch
1448 else if (result==2) return true;
13
Taking false branch
1449
1450 // No existing clone of this CPE is within range.
1451 // We will be generating a new clone. Get a UID for it.
1452 unsigned ID = AFI->createPICLabelUId();
1453
1454 // Look for water where we can place this CPE.
1455 MachineBasicBlock *NewIsland = MF->CreateMachineBasicBlock();
1456 MachineBasicBlock *NewMBB;
1457 water_iterator IP;
1458 if (findAvailableWater(U, UserOffset, IP, CloserWater)) {
14
Taking false branch
1459 LLVM_DEBUG(dbgs() << "Found water in range\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Found water in range\n"
; } } while (false)
;
1460 MachineBasicBlock *WaterBB = *IP;
1461
1462 // If the original WaterList entry was "new water" on this iteration,
1463 // propagate that to the new island. This is just keeping NewWaterList
1464 // updated to match the WaterList, which will be updated below.
1465 if (NewWaterList.erase(WaterBB))
1466 NewWaterList.insert(NewIsland);
1467
1468 // The new CPE goes before the following block (NewMBB).
1469 NewMBB = &*++WaterBB->getIterator();
1470 } else {
1471 // No water found.
1472 LLVM_DEBUG(dbgs() << "No water found\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "No water found\n"; } }
while (false)
;
1473 createNewWater(CPUserIndex, UserOffset, NewMBB);
15
Calling 'ARMConstantIslands::createNewWater'
1474
1475 // splitBlockBeforeInstr adds to WaterList, which is important when it is
1476 // called while handling branches so that the water will be seen on the
1477 // next iteration for constant pools, but in this context, we don't want
1478 // it. Check for this so it will be removed from the WaterList.
1479 // Also remove any entry from NewWaterList.
1480 MachineBasicBlock *WaterBB = &*--NewMBB->getIterator();
1481 IP = find(WaterList, WaterBB);
1482 if (IP != WaterList.end())
1483 NewWaterList.erase(WaterBB);
1484
1485 // We are adding new water. Update NewWaterList.
1486 NewWaterList.insert(NewIsland);
1487 }
1488 // Always align the new block because CP entries can be smaller than 4
1489 // bytes. Be careful not to decrease the existing alignment, e.g. NewMBB may
1490 // be an already aligned constant pool block.
1491 const unsigned Align = isThumb ? 1 : 2;
1492 if (NewMBB->getAlignment() < Align)
1493 NewMBB->setAlignment(Align);
1494
1495 // Remove the original WaterList entry; we want subsequent insertions in
1496 // this vicinity to go after the one we're about to insert. This
1497 // considerably reduces the number of times we have to move the same CPE
1498 // more than once and is also important to ensure the algorithm terminates.
1499 if (IP != WaterList.end())
1500 WaterList.erase(IP);
1501
1502 // Okay, we know we can put an island before NewMBB now, do it!
1503 MF->insert(NewMBB->getIterator(), NewIsland);
1504
1505 // Update internal data structures to account for the newly inserted MBB.
1506 updateForInsertedWaterBlock(NewIsland);
1507
1508 // Now that we have an island to add the CPE to, clone the original CPE and
1509 // add it to the island.
1510 U.HighWaterMark = NewIsland;
1511 U.CPEMI = BuildMI(NewIsland, DebugLoc(), CPEMI->getDesc())
1512 .addImm(ID)
1513 .add(CPEMI->getOperand(1))
1514 .addImm(Size);
1515 CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1));
1516 ++NumCPEs;
1517
1518 // Decrement the old entry, and remove it if refcount becomes 0.
1519 decrementCPEReferenceCount(CPI, CPEMI);
1520
1521 // Mark the basic block as aligned as required by the const-pool entry.
1522 NewIsland->setAlignment(getCPELogAlign(U.CPEMI));
1523
1524 // Increase the size of the island block to account for the new entry.
1525 BBInfo[NewIsland->getNumber()].Size += Size;
1526 adjustBBOffsetsAfter(&*--NewIsland->getIterator());
1527
1528 // Finally, change the CPI in the instruction operand to be ID.
1529 for (unsigned i = 0, e = UserMI->getNumOperands(); i != e; ++i)
1530 if (UserMI->getOperand(i).isCPI()) {
1531 UserMI->getOperand(i).setIndex(ID);
1532 break;
1533 }
1534
1535 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << " Moved CPE to #" <<
ID << " CPI=" << CPI << format(" offset=%#x\n"
, BBInfo[NewIsland->getNumber()].Offset); } } while (false
)
1536 dbgs() << " Moved CPE to #" << ID << " CPI=" << CPIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << " Moved CPE to #" <<
ID << " CPI=" << CPI << format(" offset=%#x\n"
, BBInfo[NewIsland->getNumber()].Offset); } } while (false
)
1537 << format(" offset=%#x\n", BBInfo[NewIsland->getNumber()].Offset))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << " Moved CPE to #" <<
ID << " CPI=" << CPI << format(" offset=%#x\n"
, BBInfo[NewIsland->getNumber()].Offset); } } while (false
)
;
1538
1539 return true;
1540}
1541
1542/// removeDeadCPEMI - Remove a dead constant pool entry instruction. Update
1543/// sizes and offsets of impacted basic blocks.
1544void ARMConstantIslands::removeDeadCPEMI(MachineInstr *CPEMI) {
1545 MachineBasicBlock *CPEBB = CPEMI->getParent();
1546 unsigned Size = CPEMI->getOperand(2).getImm();
1547 CPEMI->eraseFromParent();
1548 BBInfo[CPEBB->getNumber()].Size -= Size;
1549 // All succeeding offsets have the current size value added in, fix this.
1550 if (CPEBB->empty()) {
1551 BBInfo[CPEBB->getNumber()].Size = 0;
1552
1553 // This block no longer needs to be aligned.
1554 CPEBB->setAlignment(0);
1555 } else
1556 // Entries are sorted by descending alignment, so realign from the front.
1557 CPEBB->setAlignment(getCPELogAlign(&*CPEBB->begin()));
1558
1559 adjustBBOffsetsAfter(CPEBB);
1560 // An island has only one predecessor BB and one successor BB. Check if
1561 // this BB's predecessor jumps directly to this BB's successor. This
1562 // shouldn't happen currently.
1563 assert(!BBIsJumpedOver(CPEBB) && "How did this happen?")(static_cast <bool> (!BBIsJumpedOver(CPEBB) && "How did this happen?"
) ? void (0) : __assert_fail ("!BBIsJumpedOver(CPEBB) && \"How did this happen?\""
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 1563, __extension__ __PRETTY_FUNCTION__))
;
1564 // FIXME: remove the empty blocks after all the work is done?
1565}
1566
1567/// removeUnusedCPEntries - Remove constant pool entries whose refcounts
1568/// are zero.
1569bool ARMConstantIslands::removeUnusedCPEntries() {
1570 unsigned MadeChange = false;
1571 for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) {
1572 std::vector<CPEntry> &CPEs = CPEntries[i];
1573 for (unsigned j = 0, ee = CPEs.size(); j != ee; ++j) {
1574 if (CPEs[j].RefCount == 0 && CPEs[j].CPEMI) {
1575 removeDeadCPEMI(CPEs[j].CPEMI);
1576 CPEs[j].CPEMI = nullptr;
1577 MadeChange = true;
1578 }
1579 }
1580 }
1581 return MadeChange;
1582}
1583
1584/// isBBInRange - Returns true if the distance between specific MI and
1585/// specific BB can fit in MI's displacement field.
1586bool ARMConstantIslands::isBBInRange(MachineInstr *MI,MachineBasicBlock *DestBB,
1587 unsigned MaxDisp) {
1588 unsigned PCAdj = isThumb ? 4 : 8;
1589 unsigned BrOffset = getOffsetOf(MI) + PCAdj;
1590 unsigned DestOffset = BBInfo[DestBB->getNumber()].Offset;
1591
1592 LLVM_DEBUG(dbgs() << "Branch of destination " << printMBBReference(*DestBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Branch of destination "
<< printMBBReference(*DestBB) << " from " <<
printMBBReference(*MI->getParent()) << " max delta="
<< MaxDisp << " from " << getOffsetOf(MI) <<
" to " << DestOffset << " offset " << int(
DestOffset - BrOffset) << "\t" << *MI; } } while (
false)
1593 << " from " << printMBBReference(*MI->getParent())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Branch of destination "
<< printMBBReference(*DestBB) << " from " <<
printMBBReference(*MI->getParent()) << " max delta="
<< MaxDisp << " from " << getOffsetOf(MI) <<
" to " << DestOffset << " offset " << int(
DestOffset - BrOffset) << "\t" << *MI; } } while (
false)
1594 << " max delta=" << MaxDisp << " from " << getOffsetOf(MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Branch of destination "
<< printMBBReference(*DestBB) << " from " <<
printMBBReference(*MI->getParent()) << " max delta="
<< MaxDisp << " from " << getOffsetOf(MI) <<
" to " << DestOffset << " offset " << int(
DestOffset - BrOffset) << "\t" << *MI; } } while (
false)
1595 << " to " << DestOffset << " offset "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Branch of destination "
<< printMBBReference(*DestBB) << " from " <<
printMBBReference(*MI->getParent()) << " max delta="
<< MaxDisp << " from " << getOffsetOf(MI) <<
" to " << DestOffset << " offset " << int(
DestOffset - BrOffset) << "\t" << *MI; } } while (
false)
1596 << int(DestOffset - BrOffset) << "\t" << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Branch of destination "
<< printMBBReference(*DestBB) << " from " <<
printMBBReference(*MI->getParent()) << " max delta="
<< MaxDisp << " from " << getOffsetOf(MI) <<
" to " << DestOffset << " offset " << int(
DestOffset - BrOffset) << "\t" << *MI; } } while (
false)
;
1597
1598 if (BrOffset <= DestOffset) {
1599 // Branch before the Dest.
1600 if (DestOffset-BrOffset <= MaxDisp)
1601 return true;
1602 } else {
1603 if (BrOffset-DestOffset <= MaxDisp)
1604 return true;
1605 }
1606 return false;
1607}
1608
1609/// fixupImmediateBr - Fix up an immediate branch whose destination is too far
1610/// away to fit in its displacement field.
1611bool ARMConstantIslands::fixupImmediateBr(ImmBranch &Br) {
1612 MachineInstr *MI = Br.MI;
1613 MachineBasicBlock *DestBB = MI->getOperand(0).getMBB();
1614
1615 // Check to see if the DestBB is already in-range.
1616 if (isBBInRange(MI, DestBB, Br.MaxDisp))
1617 return false;
1618
1619 if (!Br.isCond)
1620 return fixupUnconditionalBr(Br);
1621 return fixupConditionalBr(Br);
1622}
1623
1624/// fixupUnconditionalBr - Fix up an unconditional branch whose destination is
1625/// too far away to fit in its displacement field. If the LR register has been
1626/// spilled in the epilogue, then we can use BL to implement a far jump.
1627/// Otherwise, add an intermediate branch instruction to a branch.
1628bool
1629ARMConstantIslands::fixupUnconditionalBr(ImmBranch &Br) {
1630 MachineInstr *MI = Br.MI;
1631 MachineBasicBlock *MBB = MI->getParent();
1632 if (!isThumb1)
1633 llvm_unreachable("fixupUnconditionalBr is Thumb1 only!")::llvm::llvm_unreachable_internal("fixupUnconditionalBr is Thumb1 only!"
, "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 1633)
;
1634
1635 // Use BL to implement far jump.
1636 Br.MaxDisp = (1 << 21) * 2;
1637 MI->setDesc(TII->get(ARM::tBfar));
1638 BBInfo[MBB->getNumber()].Size += 2;
1639 adjustBBOffsetsAfter(MBB);
1640 HasFarJump = true;
1641 ++NumUBrFixed;
1642
1643 LLVM_DEBUG(dbgs() << " Changed B to long jump " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << " Changed B to long jump "
<< *MI; } } while (false)
;
1644
1645 return true;
1646}
1647
1648/// fixupConditionalBr - Fix up a conditional branch whose destination is too
1649/// far away to fit in its displacement field. It is converted to an inverse
1650/// conditional branch + an unconditional branch to the destination.
1651bool
1652ARMConstantIslands::fixupConditionalBr(ImmBranch &Br) {
1653 MachineInstr *MI = Br.MI;
1654 MachineBasicBlock *DestBB = MI->getOperand(0).getMBB();
1655
1656 // Add an unconditional branch to the destination and invert the branch
1657 // condition to jump over it:
1658 // blt L1
1659 // =>
1660 // bge L2
1661 // b L1
1662 // L2:
1663 ARMCC::CondCodes CC = (ARMCC::CondCodes)MI->getOperand(1).getImm();
1664 CC = ARMCC::getOppositeCondition(CC);
1665 unsigned CCReg = MI->getOperand(2).getReg();
1666
1667 // If the branch is at the end of its MBB and that has a fall-through block,
1668 // direct the updated conditional branch to the fall-through block. Otherwise,
1669 // split the MBB before the next instruction.
1670 MachineBasicBlock *MBB = MI->getParent();
1671 MachineInstr *BMI = &MBB->back();
1672 bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB);
1673
1674 ++NumCBrFixed;
1675 if (BMI != MI) {
1676 if (std::next(MachineBasicBlock::iterator(MI)) == std::prev(MBB->end()) &&
1677 BMI->getOpcode() == Br.UncondBr) {
1678 // Last MI in the BB is an unconditional branch. Can we simply invert the
1679 // condition and swap destinations:
1680 // beq L1
1681 // b L2
1682 // =>
1683 // bne L2
1684 // b L1
1685 MachineBasicBlock *NewDest = BMI->getOperand(0).getMBB();
1686 if (isBBInRange(MI, NewDest, Br.MaxDisp)) {
1687 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << " Invert Bcc condition and swap its destination with "
<< *BMI; } } while (false)
1688 dbgs() << " Invert Bcc condition and swap its destination with "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << " Invert Bcc condition and swap its destination with "
<< *BMI; } } while (false)
1689 << *BMI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << " Invert Bcc condition and swap its destination with "
<< *BMI; } } while (false)
;
1690 BMI->getOperand(0).setMBB(DestBB);
1691 MI->getOperand(0).setMBB(NewDest);
1692 MI->getOperand(1).setImm(CC);
1693 return true;
1694 }
1695 }
1696 }
1697
1698 if (NeedSplit) {
1699 splitBlockBeforeInstr(MI);
1700 // No need for the branch to the next block. We're adding an unconditional
1701 // branch to the destination.
1702 int delta = TII->getInstSizeInBytes(MBB->back());
1703 BBInfo[MBB->getNumber()].Size -= delta;
1704 MBB->back().eraseFromParent();
1705
1706 // The conditional successor will be swapped between the BBs after this, so
1707 // update CFG.
1708 MBB->addSuccessor(DestBB);
1709 std::next(MBB->getIterator())->removeSuccessor(DestBB);
1710
1711 // BBInfo[SplitBB].Offset is wrong temporarily, fixed below
1712 }
1713 MachineBasicBlock *NextBB = &*++MBB->getIterator();
1714
1715 LLVM_DEBUG(dbgs() << " Insert B to " << printMBBReference(*DestBB)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << " Insert B to " <<
printMBBReference(*DestBB) << " also invert condition and change dest. to "
<< printMBBReference(*NextBB) << "\n"; } } while
(false)
1716 << " also invert condition and change dest. to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << " Insert B to " <<
printMBBReference(*DestBB) << " also invert condition and change dest. to "
<< printMBBReference(*NextBB) << "\n"; } } while
(false)
1717 << printMBBReference(*NextBB) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << " Insert B to " <<
printMBBReference(*DestBB) << " also invert condition and change dest. to "
<< printMBBReference(*NextBB) << "\n"; } } while
(false)
;
1718
1719 // Insert a new conditional branch and a new unconditional branch.
1720 // Also update the ImmBranch as well as adding a new entry for the new branch.
1721 BuildMI(MBB, DebugLoc(), TII->get(MI->getOpcode()))
1722 .addMBB(NextBB).addImm(CC).addReg(CCReg);
1723 Br.MI = &MBB->back();
1724 BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MBB->back());
1725 if (isThumb)
1726 BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr))
1727 .addMBB(DestBB)
1728 .add(predOps(ARMCC::AL));
1729 else
1730 BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr)).addMBB(DestBB);
1731 BBInfo[MBB->getNumber()].Size += TII->getInstSizeInBytes(MBB->back());
1732 unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr);
1733 ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr));
1734
1735 // Remove the old conditional branch. It may or may not still be in MBB.
1736 BBInfo[MI->getParent()->getNumber()].Size -= TII->getInstSizeInBytes(*MI);
1737 MI->eraseFromParent();
1738 adjustBBOffsetsAfter(MBB);
1739 return true;
1740}
1741
1742/// undoLRSpillRestore - Remove Thumb push / pop instructions that only spills
1743/// LR / restores LR to pc. FIXME: This is done here because it's only possible
1744/// to do this if tBfar is not used.
1745bool ARMConstantIslands::undoLRSpillRestore() {
1746 bool MadeChange = false;
1747 for (unsigned i = 0, e = PushPopMIs.size(); i != e; ++i) {
1748 MachineInstr *MI = PushPopMIs[i];
1749 // First two operands are predicates.
1750 if (MI->getOpcode() == ARM::tPOP_RET &&
1751 MI->getOperand(2).getReg() == ARM::PC &&
1752 MI->getNumExplicitOperands() == 3) {
1753 // Create the new insn and copy the predicate from the old.
1754 BuildMI(MI->getParent(), MI->getDebugLoc(), TII->get(ARM::tBX_RET))
1755 .add(MI->getOperand(0))
1756 .add(MI->getOperand(1));
1757 MI->eraseFromParent();
1758 MadeChange = true;
1759 } else if (MI->getOpcode() == ARM::tPUSH &&
1760 MI->getOperand(2).getReg() == ARM::LR &&
1761 MI->getNumExplicitOperands() == 3) {
1762 // Just remove the push.
1763 MI->eraseFromParent();
1764 MadeChange = true;
1765 }
1766 }
1767 return MadeChange;
1768}
1769
1770bool ARMConstantIslands::optimizeThumb2Instructions() {
1771 bool MadeChange = false;
1772
1773 // Shrink ADR and LDR from constantpool.
1774 for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) {
1775 CPUser &U = CPUsers[i];
1776 unsigned Opcode = U.MI->getOpcode();
1777 unsigned NewOpc = 0;
1778 unsigned Scale = 1;
1779 unsigned Bits = 0;
1780 switch (Opcode) {
1781 default: break;
1782 case ARM::t2LEApcrel:
1783 if (isARMLowRegister(U.MI->getOperand(0).getReg())) {
1784 NewOpc = ARM::tLEApcrel;
1785 Bits = 8;
1786 Scale = 4;
1787 }
1788 break;
1789 case ARM::t2LDRpci:
1790 if (isARMLowRegister(U.MI->getOperand(0).getReg())) {
1791 NewOpc = ARM::tLDRpci;
1792 Bits = 8;
1793 Scale = 4;
1794 }
1795 break;
1796 }
1797
1798 if (!NewOpc)
1799 continue;
1800
1801 unsigned UserOffset = getUserOffset(U);
1802 unsigned MaxOffs = ((1 << Bits) - 1) * Scale;
1803
1804 // Be conservative with inline asm.
1805 if (!U.KnownAlignment)
1806 MaxOffs -= 2;
1807
1808 // FIXME: Check if offset is multiple of scale if scale is not 4.
1809 if (isCPEntryInRange(U.MI, UserOffset, U.CPEMI, MaxOffs, false, true)) {
1810 LLVM_DEBUG(dbgs() << "Shrink: " << *U.MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Shrink: " << *U.
MI; } } while (false)
;
1811 U.MI->setDesc(TII->get(NewOpc));
1812 MachineBasicBlock *MBB = U.MI->getParent();
1813 BBInfo[MBB->getNumber()].Size -= 2;
1814 adjustBBOffsetsAfter(MBB);
1815 ++NumT2CPShrunk;
1816 MadeChange = true;
1817 }
1818 }
1819
1820 return MadeChange;
1821}
1822
1823bool ARMConstantIslands::optimizeThumb2Branches() {
1824 bool MadeChange = false;
1825
1826 // The order in which branches appear in ImmBranches is approximately their
1827 // order within the function body. By visiting later branches first, we reduce
1828 // the distance between earlier forward branches and their targets, making it
1829 // more likely that the cbn?z optimization, which can only apply to forward
1830 // branches, will succeed.
1831 for (unsigned i = ImmBranches.size(); i != 0; --i) {
1832 ImmBranch &Br = ImmBranches[i-1];
1833 unsigned Opcode = Br.MI->getOpcode();
1834 unsigned NewOpc = 0;
1835 unsigned Scale = 1;
1836 unsigned Bits = 0;
1837 switch (Opcode) {
1838 default: break;
1839 case ARM::t2B:
1840 NewOpc = ARM::tB;
1841 Bits = 11;
1842 Scale = 2;
1843 break;
1844 case ARM::t2Bcc:
1845 NewOpc = ARM::tBcc;
1846 Bits = 8;
1847 Scale = 2;
1848 break;
1849 }
1850 if (NewOpc) {
1851 unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale;
1852 MachineBasicBlock *DestBB = Br.MI->getOperand(0).getMBB();
1853 if (isBBInRange(Br.MI, DestBB, MaxOffs)) {
1854 LLVM_DEBUG(dbgs() << "Shrink branch: " << *Br.MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Shrink branch: " <<
*Br.MI; } } while (false)
;
1855 Br.MI->setDesc(TII->get(NewOpc));
1856 MachineBasicBlock *MBB = Br.MI->getParent();
1857 BBInfo[MBB->getNumber()].Size -= 2;
1858 adjustBBOffsetsAfter(MBB);
1859 ++NumT2BrShrunk;
1860 MadeChange = true;
1861 }
1862 }
1863
1864 Opcode = Br.MI->getOpcode();
1865 if (Opcode != ARM::tBcc)
1866 continue;
1867
1868 // If the conditional branch doesn't kill CPSR, then CPSR can be liveout
1869 // so this transformation is not safe.
1870 if (!Br.MI->killsRegister(ARM::CPSR))
1871 continue;
1872
1873 NewOpc = 0;
1874 unsigned PredReg = 0;
1875 ARMCC::CondCodes Pred = getInstrPredicate(*Br.MI, PredReg);
1876 if (Pred == ARMCC::EQ)
1877 NewOpc = ARM::tCBZ;
1878 else if (Pred == ARMCC::NE)
1879 NewOpc = ARM::tCBNZ;
1880 if (!NewOpc)
1881 continue;
1882 MachineBasicBlock *DestBB = Br.MI->getOperand(0).getMBB();
1883 // Check if the distance is within 126. Subtract starting offset by 2
1884 // because the cmp will be eliminated.
1885 unsigned BrOffset = getOffsetOf(Br.MI) + 4 - 2;
1886 unsigned DestOffset = BBInfo[DestBB->getNumber()].Offset;
1887 if (BrOffset < DestOffset && (DestOffset - BrOffset) <= 126) {
1888 MachineBasicBlock::iterator CmpMI = Br.MI;
1889 if (CmpMI != Br.MI->getParent()->begin()) {
1890 --CmpMI;
1891 if (CmpMI->getOpcode() == ARM::tCMPi8) {
1892 unsigned Reg = CmpMI->getOperand(0).getReg();
1893 Pred = getInstrPredicate(*CmpMI, PredReg);
1894 if (Pred == ARMCC::AL &&
1895 CmpMI->getOperand(1).getImm() == 0 &&
1896 isARMLowRegister(Reg)) {
1897 MachineBasicBlock *MBB = Br.MI->getParent();
1898 LLVM_DEBUG(dbgs() << "Fold: " << *CmpMI << " and: " << *Br.MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Fold: " << *CmpMI
<< " and: " << *Br.MI; } } while (false)
;
1899 MachineInstr *NewBR =
1900 BuildMI(*MBB, CmpMI, Br.MI->getDebugLoc(), TII->get(NewOpc))
1901 .addReg(Reg).addMBB(DestBB,Br.MI->getOperand(0).getTargetFlags());
1902 CmpMI->eraseFromParent();
1903 Br.MI->eraseFromParent();
1904 Br.MI = NewBR;
1905 BBInfo[MBB->getNumber()].Size -= 2;
1906 adjustBBOffsetsAfter(MBB);
1907 ++NumCBZ;
1908 MadeChange = true;
1909 }
1910 }
1911 }
1912 }
1913 }
1914
1915 return MadeChange;
1916}
1917
1918static bool isSimpleIndexCalc(MachineInstr &I, unsigned EntryReg,
1919 unsigned BaseReg) {
1920 if (I.getOpcode() != ARM::t2ADDrs)
1921 return false;
1922
1923 if (I.getOperand(0).getReg() != EntryReg)
1924 return false;
1925
1926 if (I.getOperand(1).getReg() != BaseReg)
1927 return false;
1928
1929 // FIXME: what about CC and IdxReg?
1930 return true;
1931}
1932
1933/// While trying to form a TBB/TBH instruction, we may (if the table
1934/// doesn't immediately follow the BR_JT) need access to the start of the
1935/// jump-table. We know one instruction that produces such a register; this
1936/// function works out whether that definition can be preserved to the BR_JT,
1937/// possibly by removing an intervening addition (which is usually needed to
1938/// calculate the actual entry to jump to).
1939bool ARMConstantIslands::preserveBaseRegister(MachineInstr *JumpMI,
1940 MachineInstr *LEAMI,
1941 unsigned &DeadSize,
1942 bool &CanDeleteLEA,
1943 bool &BaseRegKill) {
1944 if (JumpMI->getParent() != LEAMI->getParent())
1945 return false;
1946
1947 // Now we hope that we have at least these instructions in the basic block:
1948 // BaseReg = t2LEA ...
1949 // [...]
1950 // EntryReg = t2ADDrs BaseReg, ...
1951 // [...]
1952 // t2BR_JT EntryReg
1953 //
1954 // We have to be very conservative about what we recognise here though. The
1955 // main perturbing factors to watch out for are:
1956 // + Spills at any point in the chain: not direct problems but we would
1957 // expect a blocking Def of the spilled register so in practice what we
1958 // can do is limited.
1959 // + EntryReg == BaseReg: this is the one situation we should allow a Def
1960 // of BaseReg, but only if the t2ADDrs can be removed.
1961 // + Some instruction other than t2ADDrs computing the entry. Not seen in
1962 // the wild, but we should be careful.
1963 unsigned EntryReg = JumpMI->getOperand(0).getReg();
1964 unsigned BaseReg = LEAMI->getOperand(0).getReg();
1965
1966 CanDeleteLEA = true;
1967 BaseRegKill = false;
1968 MachineInstr *RemovableAdd = nullptr;
1969 MachineBasicBlock::iterator I(LEAMI);
1970 for (++I; &*I != JumpMI; ++I) {
1971 if (isSimpleIndexCalc(*I, EntryReg, BaseReg)) {
1972 RemovableAdd = &*I;
1973 break;
1974 }
1975
1976 for (unsigned K = 0, E = I->getNumOperands(); K != E; ++K) {
1977 const MachineOperand &MO = I->getOperand(K);
1978 if (!MO.isReg() || !MO.getReg())
1979 continue;
1980 if (MO.isDef() && MO.getReg() == BaseReg)
1981 return false;
1982 if (MO.isUse() && MO.getReg() == BaseReg) {
1983 BaseRegKill = BaseRegKill || MO.isKill();
1984 CanDeleteLEA = false;
1985 }
1986 }
1987 }
1988
1989 if (!RemovableAdd)
1990 return true;
1991
1992 // Check the add really is removable, and that nothing else in the block
1993 // clobbers BaseReg.
1994 for (++I; &*I != JumpMI; ++I) {
1995 for (unsigned K = 0, E = I->getNumOperands(); K != E; ++K) {
1996 const MachineOperand &MO = I->getOperand(K);
1997 if (!MO.isReg() || !MO.getReg())
1998 continue;
1999 if (MO.isDef() && MO.getReg() == BaseReg)
2000 return false;
2001 if (MO.isUse() && MO.getReg() == EntryReg)
2002 RemovableAdd = nullptr;
2003 }
2004 }
2005
2006 if (RemovableAdd) {
2007 RemovableAdd->eraseFromParent();
2008 DeadSize += isThumb2 ? 4 : 2;
2009 } else if (BaseReg == EntryReg) {
2010 // The add wasn't removable, but clobbered the base for the TBB. So we can't
2011 // preserve it.
2012 return false;
2013 }
2014
2015 // We reached the end of the block without seeing another definition of
2016 // BaseReg (except, possibly the t2ADDrs, which was removed). BaseReg can be
2017 // used in the TBB/TBH if necessary.
2018 return true;
2019}
2020
2021/// Returns whether CPEMI is the first instruction in the block
2022/// immediately following JTMI (assumed to be a TBB or TBH terminator). If so,
2023/// we can switch the first register to PC and usually remove the address
2024/// calculation that preceded it.
2025static bool jumpTableFollowsTB(MachineInstr *JTMI, MachineInstr *CPEMI) {
2026 MachineFunction::iterator MBB = JTMI->getParent()->getIterator();
2027 MachineFunction *MF = MBB->getParent();
2028 ++MBB;
2029
2030 return MBB != MF->end() && MBB->begin() != MBB->end() &&
2031 &*MBB->begin() == CPEMI;
2032}
2033
2034static void RemoveDeadAddBetweenLEAAndJT(MachineInstr *LEAMI,
2035 MachineInstr *JumpMI,
2036 unsigned &DeadSize) {
2037 // Remove a dead add between the LEA and JT, which used to compute EntryReg,
2038 // but the JT now uses PC. Finds the last ADD (if any) that def's EntryReg
2039 // and is not clobbered / used.
2040 MachineInstr *RemovableAdd = nullptr;
2041 unsigned EntryReg = JumpMI->getOperand(0).getReg();
2042
2043 // Find the last ADD to set EntryReg
2044 MachineBasicBlock::iterator I(LEAMI);
2045 for (++I; &*I != JumpMI; ++I) {
2046 if (I->getOpcode() == ARM::t2ADDrs && I->getOperand(0).getReg() == EntryReg)
2047 RemovableAdd = &*I;
2048 }
2049
2050 if (!RemovableAdd)
2051 return;
2052
2053 // Ensure EntryReg is not clobbered or used.
2054 MachineBasicBlock::iterator J(RemovableAdd);
2055 for (++J; &*J != JumpMI; ++J) {
2056 for (unsigned K = 0, E = J->getNumOperands(); K != E; ++K) {
2057 const MachineOperand &MO = J->getOperand(K);
2058 if (!MO.isReg() || !MO.getReg())
2059 continue;
2060 if (MO.isDef() && MO.getReg() == EntryReg)
2061 return;
2062 if (MO.isUse() && MO.getReg() == EntryReg)
2063 return;
2064 }
2065 }
2066
2067 LLVM_DEBUG(dbgs() << "Removing Dead Add: " << *RemovableAdd)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Removing Dead Add: " <<
*RemovableAdd; } } while (false)
;
2068 RemovableAdd->eraseFromParent();
2069 DeadSize += 4;
2070}
2071
2072static bool registerDefinedBetween(unsigned Reg,
2073 MachineBasicBlock::iterator From,
2074 MachineBasicBlock::iterator To,
2075 const TargetRegisterInfo *TRI) {
2076 for (auto I = From; I != To; ++I)
2077 if (I->modifiesRegister(Reg, TRI))
2078 return true;
2079 return false;
2080}
2081
2082/// optimizeThumb2JumpTables - Use tbb / tbh instructions to generate smaller
2083/// jumptables when it's possible.
2084bool ARMConstantIslands::optimizeThumb2JumpTables() {
2085 bool MadeChange = false;
2086
2087 // FIXME: After the tables are shrunk, can we get rid some of the
2088 // constantpool tables?
2089 MachineJumpTableInfo *MJTI = MF->getJumpTableInfo();
2090 if (!MJTI) return false;
2091
2092 const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables();
2093 for (unsigned i = 0, e = T2JumpTables.size(); i != e; ++i) {
2094 MachineInstr *MI = T2JumpTables[i];
2095 const MCInstrDesc &MCID = MI->getDesc();
2096 unsigned NumOps = MCID.getNumOperands();
2097 unsigned JTOpIdx = NumOps - (MI->isPredicable() ? 2 : 1);
2098 MachineOperand JTOP = MI->getOperand(JTOpIdx);
2099 unsigned JTI = JTOP.getIndex();
2100 assert(JTI < JT.size())(static_cast <bool> (JTI < JT.size()) ? void (0) : __assert_fail
("JTI < JT.size()", "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 2100, __extension__ __PRETTY_FUNCTION__))
;
2101
2102 bool ByteOk = true;
2103 bool HalfWordOk = true;
2104 unsigned JTOffset = getOffsetOf(MI) + 4;
2105 const std::vector<MachineBasicBlock*> &JTBBs = JT[JTI].MBBs;
2106 for (unsigned j = 0, ee = JTBBs.size(); j != ee; ++j) {
2107 MachineBasicBlock *MBB = JTBBs[j];
2108 unsigned DstOffset = BBInfo[MBB->getNumber()].Offset;
2109 // Negative offset is not ok. FIXME: We should change BB layout to make
2110 // sure all the branches are forward.
2111 if (ByteOk && (DstOffset - JTOffset) > ((1<<8)-1)*2)
2112 ByteOk = false;
2113 unsigned TBHLimit = ((1<<16)-1)*2;
2114 if (HalfWordOk && (DstOffset - JTOffset) > TBHLimit)
2115 HalfWordOk = false;
2116 if (!ByteOk && !HalfWordOk)
2117 break;
2118 }
2119
2120 if (!ByteOk && !HalfWordOk)
2121 continue;
2122
2123 CPUser &User = CPUsers[JumpTableUserIndices[JTI]];
2124 MachineBasicBlock *MBB = MI->getParent();
2125 if (!MI->getOperand(0).isKill()) // FIXME: needed now?
2126 continue;
2127
2128 unsigned DeadSize = 0;
2129 bool CanDeleteLEA = false;
2130 bool BaseRegKill = false;
2131
2132 unsigned IdxReg = ~0U;
2133 bool IdxRegKill = true;
2134 if (isThumb2) {
2135 IdxReg = MI->getOperand(1).getReg();
2136 IdxRegKill = MI->getOperand(1).isKill();
2137
2138 bool PreservedBaseReg =
2139 preserveBaseRegister(MI, User.MI, DeadSize, CanDeleteLEA, BaseRegKill);
2140 if (!jumpTableFollowsTB(MI, User.CPEMI) && !PreservedBaseReg)
2141 continue;
2142 } else {
2143 // We're in thumb-1 mode, so we must have something like:
2144 // %idx = tLSLri %idx, 2
2145 // %base = tLEApcrelJT
2146 // %t = tLDRr %base, %idx
2147 unsigned BaseReg = User.MI->getOperand(0).getReg();
2148
2149 if (User.MI->getIterator() == User.MI->getParent()->begin())
2150 continue;
2151 MachineInstr *Shift = User.MI->getPrevNode();
2152 if (Shift->getOpcode() != ARM::tLSLri ||
2153 Shift->getOperand(3).getImm() != 2 ||
2154 !Shift->getOperand(2).isKill())
2155 continue;
2156 IdxReg = Shift->getOperand(2).getReg();
2157 unsigned ShiftedIdxReg = Shift->getOperand(0).getReg();
2158
2159 // It's important that IdxReg is live until the actual TBB/TBH. Most of
2160 // the range is checked later, but the LEA might still clobber it and not
2161 // actually get removed.
2162 if (BaseReg == IdxReg && !jumpTableFollowsTB(MI, User.CPEMI))
2163 continue;
2164
2165 MachineInstr *Load = User.MI->getNextNode();
2166 if (Load->getOpcode() != ARM::tLDRr)
2167 continue;
2168 if (Load->getOperand(1).getReg() != BaseReg ||
2169 Load->getOperand(2).getReg() != ShiftedIdxReg ||
2170 !Load->getOperand(2).isKill())
2171 continue;
2172
2173 // If we're in PIC mode, there should be another ADD following.
2174 auto *TRI = STI->getRegisterInfo();
2175
2176 // %base cannot be redefined after the load as it will appear before
2177 // TBB/TBH like:
2178 // %base =
2179 // %base =
2180 // tBB %base, %idx
2181 if (registerDefinedBetween(BaseReg, Load->getNextNode(), MBB->end(), TRI))
2182 continue;
2183
2184 if (isPositionIndependentOrROPI) {
2185 MachineInstr *Add = Load->getNextNode();
2186 if (Add->getOpcode() != ARM::tADDrr ||
2187 Add->getOperand(2).getReg() != BaseReg ||
2188 Add->getOperand(3).getReg() != Load->getOperand(0).getReg() ||
2189 !Add->getOperand(3).isKill())
2190 continue;
2191 if (Add->getOperand(0).getReg() != MI->getOperand(0).getReg())
2192 continue;
2193 if (registerDefinedBetween(IdxReg, Add->getNextNode(), MI, TRI))
2194 // IdxReg gets redefined in the middle of the sequence.
2195 continue;
2196 Add->eraseFromParent();
2197 DeadSize += 2;
2198 } else {
2199 if (Load->getOperand(0).getReg() != MI->getOperand(0).getReg())
2200 continue;
2201 if (registerDefinedBetween(IdxReg, Load->getNextNode(), MI, TRI))
2202 // IdxReg gets redefined in the middle of the sequence.
2203 continue;
2204 }
2205
2206 // Now safe to delete the load and lsl. The LEA will be removed later.
2207 CanDeleteLEA = true;
2208 Shift->eraseFromParent();
2209 Load->eraseFromParent();
2210 DeadSize += 4;
2211 }
2212
2213 LLVM_DEBUG(dbgs() << "Shrink JT: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << "Shrink JT: " << *
MI; } } while (false)
;
2214 MachineInstr *CPEMI = User.CPEMI;
2215 unsigned Opc = ByteOk ? ARM::t2TBB_JT : ARM::t2TBH_JT;
2216 if (!isThumb2)
2217 Opc = ByteOk ? ARM::tTBB_JT : ARM::tTBH_JT;
2218
2219 MachineBasicBlock::iterator MI_JT = MI;
2220 MachineInstr *NewJTMI =
2221 BuildMI(*MBB, MI_JT, MI->getDebugLoc(), TII->get(Opc))
2222 .addReg(User.MI->getOperand(0).getReg(),
2223 getKillRegState(BaseRegKill))
2224 .addReg(IdxReg, getKillRegState(IdxRegKill))
2225 .addJumpTableIndex(JTI, JTOP.getTargetFlags())
2226 .addImm(CPEMI->getOperand(0).getImm());
2227 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": " << *NewJTMI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("arm-cp-islands")) { dbgs() << printMBBReference(*MBB)
<< ": " << *NewJTMI; } } while (false)
;
2228
2229 unsigned JTOpc = ByteOk ? ARM::JUMPTABLE_TBB : ARM::JUMPTABLE_TBH;
2230 CPEMI->setDesc(TII->get(JTOpc));
2231
2232 if (jumpTableFollowsTB(MI, User.CPEMI)) {
2233 NewJTMI->getOperand(0).setReg(ARM::PC);
2234 NewJTMI->getOperand(0).setIsKill(false);
2235
2236 if (CanDeleteLEA) {
2237 if (isThumb2)
2238 RemoveDeadAddBetweenLEAAndJT(User.MI, MI, DeadSize);
2239
2240 User.MI->eraseFromParent();
2241 DeadSize += isThumb2 ? 4 : 2;
2242
2243 // The LEA was eliminated, the TBB instruction becomes the only new user
2244 // of the jump table.
2245 User.MI = NewJTMI;
2246 User.MaxDisp = 4;
2247 User.NegOk = false;
2248 User.IsSoImm = false;
2249 User.KnownAlignment = false;
2250 } else {
2251 // The LEA couldn't be eliminated, so we must add another CPUser to
2252 // record the TBB or TBH use.
2253 int CPEntryIdx = JumpTableEntryIndices[JTI];
2254 auto &CPEs = CPEntries[CPEntryIdx];
2255 auto Entry =
2256 find_if(CPEs, [&](CPEntry &E) { return E.CPEMI == User.CPEMI; });
2257 ++Entry->RefCount;
2258 CPUsers.emplace_back(CPUser(NewJTMI, User.CPEMI, 4, false, false));
2259 }
2260 }
2261
2262 unsigned NewSize = TII->getInstSizeInBytes(*NewJTMI);
2263 unsigned OrigSize = TII->getInstSizeInBytes(*MI);
2264 MI->eraseFromParent();
2265
2266 int Delta = OrigSize - NewSize + DeadSize;
2267 BBInfo[MBB->getNumber()].Size -= Delta;
2268 adjustBBOffsetsAfter(MBB);
2269
2270 ++NumTBs;
2271 MadeChange = true;
2272 }
2273
2274 return MadeChange;
2275}
2276
2277/// reorderThumb2JumpTables - Adjust the function's block layout to ensure that
2278/// jump tables always branch forwards, since that's what tbb and tbh need.
2279bool ARMConstantIslands::reorderThumb2JumpTables() {
2280 bool MadeChange = false;
2281
2282 MachineJumpTableInfo *MJTI = MF->getJumpTableInfo();
2283 if (!MJTI) return false;
2284
2285 const std::vector<MachineJumpTableEntry> &JT = MJTI->getJumpTables();
2286 for (unsigned i = 0, e = T2JumpTables.size(); i != e; ++i) {
2287 MachineInstr *MI = T2JumpTables[i];
2288 const MCInstrDesc &MCID = MI->getDesc();
2289 unsigned NumOps = MCID.getNumOperands();
2290 unsigned JTOpIdx = NumOps - (MI->isPredicable() ? 2 : 1);
2291 MachineOperand JTOP = MI->getOperand(JTOpIdx);
2292 unsigned JTI = JTOP.getIndex();
2293 assert(JTI < JT.size())(static_cast <bool> (JTI < JT.size()) ? void (0) : __assert_fail
("JTI < JT.size()", "/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMConstantIslandPass.cpp"
, 2293, __extension__ __PRETTY_FUNCTION__))
;
2294
2295 // We prefer if target blocks for the jump table come after the jump
2296 // instruction so we can use TB[BH]. Loop through the target blocks
2297 // and try to adjust them such that that's true.
2298 int JTNumber = MI->getParent()->getNumber();
2299 const std::vector<MachineBasicBlock*> &JTBBs = JT[JTI].MBBs;
2300 for (unsigned j = 0, ee = JTBBs.size(); j != ee; ++j) {
2301 MachineBasicBlock *MBB = JTBBs[j];
2302 int DTNumber = MBB->getNumber();
2303
2304 if (DTNumber < JTNumber) {
2305 // The destination precedes the switch. Try to move the block forward
2306 // so we have a positive offset.
2307 MachineBasicBlock *NewBB =
2308 adjustJTTargetBlockForward(MBB, MI->getParent());
2309 if (NewBB)
2310 MJTI->ReplaceMBBInJumpTable(JTI, JTBBs[j], NewBB);
2311 MadeChange = true;
2312 }
2313 }
2314 }
2315
2316 return MadeChange;
2317}
2318
2319MachineBasicBlock *ARMConstantIslands::
2320adjustJTTargetBlockForward(MachineBasicBlock *BB, MachineBasicBlock *JTBB) {
2321 // If the destination block is terminated by an unconditional branch,
2322 // try to move it; otherwise, create a new block following the jump
2323 // table that branches back to the actual target. This is a very simple
2324 // heuristic. FIXME: We can definitely improve it.
2325 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
2326 SmallVector<MachineOperand, 4> Cond;
2327 SmallVector<MachineOperand, 4> CondPrior;
2328 MachineFunction::iterator BBi = BB->getIterator();
2329 MachineFunction::iterator OldPrior = std::prev(BBi);
2330
2331 // If the block terminator isn't analyzable, don't try to move the block
2332 bool B = TII->analyzeBranch(*BB, TBB, FBB, Cond);
2333
2334 // If the block ends in an unconditional branch, move it. The prior block
2335 // has to have an analyzable terminator for us to move this one. Be paranoid
2336 // and make sure we're not trying to move the entry block of the function.
2337 if (!B && Cond.empty() && BB != &MF->front() &&
2338 !TII->analyzeBranch(*OldPrior, TBB, FBB, CondPrior)) {
2339 BB->moveAfter(JTBB);
2340 OldPrior->updateTerminator();
2341 BB->updateTerminator();
2342 // Update numbering to account for the block being moved.
2343 MF->RenumberBlocks();
2344 ++NumJTMoved;
2345 return nullptr;
2346 }
2347
2348 // Create a new MBB for the code after the jump BB.
2349 MachineBasicBlock *NewBB =
2350 MF->CreateMachineBasicBlock(JTBB->getBasicBlock());
2351 MachineFunction::iterator MBBI = ++JTBB->getIterator();
2352 MF->insert(MBBI, NewBB);
2353
2354 // Add an unconditional branch from NewBB to BB.
2355 // There doesn't seem to be meaningful DebugInfo available; this doesn't
2356 // correspond directly to anything in the source.
2357 if (isThumb2)
2358 BuildMI(NewBB, DebugLoc(), TII->get(ARM::t2B))
2359 .addMBB(BB)
2360 .add(predOps(ARMCC::AL));
2361 else
2362 BuildMI(NewBB, DebugLoc(), TII->get(ARM::tB))
2363 .addMBB(BB)
2364 .add(predOps(ARMCC::AL));
2365
2366 // Update internal data structures to account for the newly inserted MBB.
2367 MF->RenumberBlocks(NewBB);
2368
2369 // Update the CFG.
2370 NewBB->addSuccessor(BB);
2371 JTBB->replaceSuccessor(BB, NewBB);
2372
2373 ++NumJTInserted;
2374 return NewBB;
2375}
2376
2377/// createARMConstantIslandPass - returns an instance of the constpool
2378/// island pass.
2379FunctionPass *llvm::createARMConstantIslandPass() {
2380 return new ARMConstantIslands();
2381}
2382
2383INITIALIZE_PASS(ARMConstantIslands, "arm-cp-islands", ARM_CP_ISLANDS_OPT_NAME,static void *initializeARMConstantIslandsPassOnce(PassRegistry
&Registry) { PassInfo *PI = new PassInfo( "ARM constant island placement and branch shortening pass"
, "arm-cp-islands", &ARMConstantIslands::ID, PassInfo::NormalCtor_t
(callDefaultCtor<ARMConstantIslands>), false, false); Registry
.registerPass(*PI, true); return PI; } static llvm::once_flag
InitializeARMConstantIslandsPassFlag; void llvm::initializeARMConstantIslandsPass
(PassRegistry &Registry) { llvm::call_once(InitializeARMConstantIslandsPassFlag
, initializeARMConstantIslandsPassOnce, std::ref(Registry)); }
2384 false, false)static void *initializeARMConstantIslandsPassOnce(PassRegistry
&Registry) { PassInfo *PI = new PassInfo( "ARM constant island placement and branch shortening pass"
, "arm-cp-islands", &ARMConstantIslands::ID, PassInfo::NormalCtor_t
(callDefaultCtor<ARMConstantIslands>), false, false); Registry
.registerPass(*PI, true); return PI; } static llvm::once_flag
InitializeARMConstantIslandsPassFlag; void llvm::initializeARMConstantIslandsPass
(PassRegistry &Registry) { llvm::call_once(InitializeARMConstantIslandsPassFlag
, initializeARMConstantIslandsPassOnce, std::ref(Registry)); }

/build/llvm-toolchain-snapshot-7~svn338205/lib/Target/ARM/ARMBasicBlockInfo.h

1//===-- ARMBasicBlockInfo.h - Basic Block Information -----------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// Utility functions and data structure for computing block size.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_LIB_TARGET_ARM_ARMBASICBLOCKINFO_H
15#define LLVM_LIB_TARGET_ARM_ARMBASICBLOCKINFO_H
16
17#include "llvm/Support/MathExtras.h"
18#include <algorithm>
19#include <cstdint>
20
21namespace llvm {
22
23/// UnknownPadding - Return the worst case padding that could result from
24/// unknown offset bits. This does not include alignment padding caused by
25/// known offset bits.
26///
27/// @param LogAlign log2(alignment)
28/// @param KnownBits Number of known low offset bits.
29inline unsigned UnknownPadding(unsigned LogAlign, unsigned KnownBits) {
30 if (KnownBits < LogAlign)
18
Assuming 'KnownBits' is < 'LogAlign'
19
Taking true branch
31 return (1u << LogAlign) - (1u << KnownBits);
20
The result of the left shift is undefined due to shifting by '32', which is greater or equal to the width of type 'unsigned int'
32 return 0;
33}
34
35/// BasicBlockInfo - Information about the offset and size of a single
36/// basic block.
37struct BasicBlockInfo {
38 /// Offset - Distance from the beginning of the function to the beginning
39 /// of this basic block.
40 ///
41 /// Offsets are computed assuming worst case padding before an aligned
42 /// block. This means that subtracting basic block offsets always gives a
43 /// conservative estimate of the real distance which may be smaller.
44 ///
45 /// Because worst case padding is used, the computed offset of an aligned
46 /// block may not actually be aligned.
47 unsigned Offset = 0;
48
49 /// Size - Size of the basic block in bytes. If the block contains
50 /// inline assembly, this is a worst case estimate.
51 ///
52 /// The size does not include any alignment padding whether from the
53 /// beginning of the block, or from an aligned jump table at the end.
54 unsigned Size = 0;
55
56 /// KnownBits - The number of low bits in Offset that are known to be
57 /// exact. The remaining bits of Offset are an upper bound.
58 uint8_t KnownBits = 0;
59
60 /// Unalign - When non-zero, the block contains instructions (inline asm)
61 /// of unknown size. The real size may be smaller than Size bytes by a
62 /// multiple of 1 << Unalign.
63 uint8_t Unalign = 0;
64
65 /// PostAlign - When non-zero, the block terminator contains a .align
66 /// directive, so the end of the block is aligned to 1 << PostAlign
67 /// bytes.
68 uint8_t PostAlign = 0;
69
70 BasicBlockInfo() = default;
71
72 /// Compute the number of known offset bits internally to this block.
73 /// This number should be used to predict worst case padding when
74 /// splitting the block.
75 unsigned internalKnownBits() const {
76 unsigned Bits = Unalign ? Unalign : KnownBits;
77 // If the block size isn't a multiple of the known bits, assume the
78 // worst case padding.
79 if (Size & ((1u << Bits) - 1))
80 Bits = countTrailingZeros(Size);
81 return Bits;
82 }
83
84 /// Compute the offset immediately following this block. If LogAlign is
85 /// specified, return the offset the successor block will get if it has
86 /// this alignment.
87 unsigned postOffset(unsigned LogAlign = 0) const {
88 unsigned PO = Offset + Size;
89 unsigned LA = std::max(unsigned(PostAlign), LogAlign);
90 if (!LA)
91 return PO;
92 // Add alignment padding from the terminator.
93 return PO + UnknownPadding(LA, internalKnownBits());
94 }
95
96 /// Compute the number of known low bits of postOffset. If this block
97 /// contains inline asm, the number of known bits drops to the
98 /// instruction alignment. An aligned terminator may increase the number
99 /// of know bits.
100 /// If LogAlign is given, also consider the alignment of the next block.
101 unsigned postKnownBits(unsigned LogAlign = 0) const {
102 return std::max(std::max(unsigned(PostAlign), LogAlign),
103 internalKnownBits());
104 }
105};
106
107} // end namespace llvm
108
109#endif // LLVM_LIB_TARGET_ARM_ARMBASICBLOCKINFO_H