Bug Summary

File:lib/Target/ARM/ARMConstantIslandPass.cpp
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~svn329677/build-llvm/lib/Target/ARM -I /build/llvm-toolchain-snapshot-7~svn329677/lib/Target/ARM -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn329677/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/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/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-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn329677/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-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-04-11-031539-24776-1 -x c++ /build/llvm-toolchain-snapshot-7~svn329677/lib/Target/ARM/ARMConstantIslandPass.cpp

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