Bug Summary

File:lib/Target/ARM/ARMBasicBlockInfo.h
Warning:line 34, column 32
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-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 -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -mframe-pointer=none -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-10/lib/clang/10.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-10~svn372306/build-llvm/lib/Target/ARM -I /build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM -I /build/llvm-toolchain-snapshot-10~svn372306/build-llvm/include -I /build/llvm-toolchain-snapshot-10~svn372306/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-10/lib/clang/10.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++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-10~svn372306/build-llvm/lib/Target/ARM -fdebug-prefix-map=/build/llvm-toolchain-snapshot-10~svn372306=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2019-09-19-172240-30738-1 -x c++ /build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp

/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMConstantIslandPass.cpp

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

1//===- llvm/ADT/ilist_iterator.h - Intrusive List Iterator ------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef LLVM_ADT_ILIST_ITERATOR_H
10#define LLVM_ADT_ILIST_ITERATOR_H
11
12#include "llvm/ADT/ilist_node.h"
13#include <cassert>
14#include <cstddef>
15#include <iterator>
16#include <type_traits>
17
18namespace llvm {
19
20namespace ilist_detail {
21
22/// Find const-correct node types.
23template <class OptionsT, bool IsConst> struct IteratorTraits;
24template <class OptionsT> struct IteratorTraits<OptionsT, false> {
25 using value_type = typename OptionsT::value_type;
26 using pointer = typename OptionsT::pointer;
27 using reference = typename OptionsT::reference;
28 using node_pointer = ilist_node_impl<OptionsT> *;
29 using node_reference = ilist_node_impl<OptionsT> &;
30};
31template <class OptionsT> struct IteratorTraits<OptionsT, true> {
32 using value_type = const typename OptionsT::value_type;
33 using pointer = typename OptionsT::const_pointer;
34 using reference = typename OptionsT::const_reference;
35 using node_pointer = const ilist_node_impl<OptionsT> *;
36 using node_reference = const ilist_node_impl<OptionsT> &;
37};
38
39template <bool IsReverse> struct IteratorHelper;
40template <> struct IteratorHelper<false> : ilist_detail::NodeAccess {
41 using Access = ilist_detail::NodeAccess;
42
43 template <class T> static void increment(T *&I) { I = Access::getNext(*I); }
44 template <class T> static void decrement(T *&I) { I = Access::getPrev(*I); }
45};
46template <> struct IteratorHelper<true> : ilist_detail::NodeAccess {
47 using Access = ilist_detail::NodeAccess;
48
49 template <class T> static void increment(T *&I) { I = Access::getPrev(*I); }
50 template <class T> static void decrement(T *&I) { I = Access::getNext(*I); }
51};
52
53} // end namespace ilist_detail
54
55/// Iterator for intrusive lists based on ilist_node.
56template <class OptionsT, bool IsReverse, bool IsConst>
57class ilist_iterator : ilist_detail::SpecificNodeAccess<OptionsT> {
58 friend ilist_iterator<OptionsT, IsReverse, !IsConst>;
59 friend ilist_iterator<OptionsT, !IsReverse, IsConst>;
60 friend ilist_iterator<OptionsT, !IsReverse, !IsConst>;
61
62 using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>;
63 using Access = ilist_detail::SpecificNodeAccess<OptionsT>;
64
65public:
66 using value_type = typename Traits::value_type;
67 using pointer = typename Traits::pointer;
68 using reference = typename Traits::reference;
69 using difference_type = ptrdiff_t;
70 using iterator_category = std::bidirectional_iterator_tag;
71 using const_pointer = typename OptionsT::const_pointer;
72 using const_reference = typename OptionsT::const_reference;
73
74private:
75 using node_pointer = typename Traits::node_pointer;
76 using node_reference = typename Traits::node_reference;
77
78 node_pointer NodePtr = nullptr;
79
80public:
81 /// Create from an ilist_node.
82 explicit ilist_iterator(node_reference N) : NodePtr(&N) {}
83
84 explicit ilist_iterator(pointer NP) : NodePtr(Access::getNodePtr(NP)) {}
85 explicit ilist_iterator(reference NR) : NodePtr(Access::getNodePtr(&NR)) {}
86 ilist_iterator() = default;
87
88 // This is templated so that we can allow constructing a const iterator from
89 // a nonconst iterator...
90 template <bool RHSIsConst>
91 ilist_iterator(
92 const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS,
93 typename std::enable_if<IsConst || !RHSIsConst, void *>::type = nullptr)
94 : NodePtr(RHS.NodePtr) {}
95
96 // This is templated so that we can allow assigning to a const iterator from
97 // a nonconst iterator...
98 template <bool RHSIsConst>
99 typename std::enable_if<IsConst || !RHSIsConst, ilist_iterator &>::type
100 operator=(const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS) {
101 NodePtr = RHS.NodePtr;
102 return *this;
103 }
104
105 /// Explicit conversion between forward/reverse iterators.
106 ///
107 /// Translate between forward and reverse iterators without changing range
108 /// boundaries. The resulting iterator will dereference (and have a handle)
109 /// to the previous node, which is somewhat unexpected; but converting the
110 /// two endpoints in a range will give the same range in reverse.
111 ///
112 /// This matches std::reverse_iterator conversions.
113 explicit ilist_iterator(
114 const ilist_iterator<OptionsT, !IsReverse, IsConst> &RHS)
115 : ilist_iterator(++RHS.getReverse()) {}
116
117 /// Get a reverse iterator to the same node.
118 ///
119 /// Gives a reverse iterator that will dereference (and have a handle) to the
120 /// same node. Converting the endpoint iterators in a range will give a
121 /// different range; for range operations, use the explicit conversions.
122 ilist_iterator<OptionsT, !IsReverse, IsConst> getReverse() const {
123 if (NodePtr)
124 return ilist_iterator<OptionsT, !IsReverse, IsConst>(*NodePtr);
125 return ilist_iterator<OptionsT, !IsReverse, IsConst>();
126 }
127
128 /// Const-cast.
129 ilist_iterator<OptionsT, IsReverse, false> getNonConst() const {
130 if (NodePtr)
131 return ilist_iterator<OptionsT, IsReverse, false>(
132 const_cast<typename ilist_iterator<OptionsT, IsReverse,
133 false>::node_reference>(*NodePtr));
134 return ilist_iterator<OptionsT, IsReverse, false>();
135 }
136
137 // Accessors...
138 reference operator*() const {
139 assert(!NodePtr->isKnownSentinel())((!NodePtr->isKnownSentinel()) ? static_cast<void> (
0) : __assert_fail ("!NodePtr->isKnownSentinel()", "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/ADT/ilist_iterator.h"
, 139, __PRETTY_FUNCTION__))
;
140 return *Access::getValuePtr(NodePtr);
141 }
142 pointer operator->() const { return &operator*(); }
143
144 // Comparison operators
145 friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) {
146 return LHS.NodePtr == RHS.NodePtr;
26
Assuming 'LHS.NodePtr' is equal to 'RHS.NodePtr'
27
Returning the value 1, which participates in a condition later
147 }
148 friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) {
149 return LHS.NodePtr != RHS.NodePtr;
150 }
151
152 // Increment and decrement operators...
153 ilist_iterator &operator--() {
154 NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev();
155 return *this;
156 }
157 ilist_iterator &operator++() {
158 NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext();
159 return *this;
160 }
161 ilist_iterator operator--(int) {
162 ilist_iterator tmp = *this;
163 --*this;
164 return tmp;
165 }
166 ilist_iterator operator++(int) {
167 ilist_iterator tmp = *this;
168 ++*this;
169 return tmp;
170 }
171
172 /// Get the underlying ilist_node.
173 node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); }
174
175 /// Check for end. Only valid if ilist_sentinel_tracking<true>.
176 bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; }
177};
178
179template <typename From> struct simplify_type;
180
181/// Allow ilist_iterators to convert into pointers to a node automatically when
182/// used by the dyn_cast, cast, isa mechanisms...
183///
184/// FIXME: remove this, since there is no implicit conversion to NodeTy.
185template <class OptionsT, bool IsConst>
186struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> {
187 using iterator = ilist_iterator<OptionsT, false, IsConst>;
188 using SimpleType = typename iterator::pointer;
189
190 static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; }
191};
192template <class OptionsT, bool IsConst>
193struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>>
194 : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {};
195
196} // end namespace llvm
197
198#endif // LLVM_ADT_ILIST_ITERATOR_H

/build/llvm-toolchain-snapshot-10~svn372306/lib/Target/ARM/ARMBasicBlockInfo.h

1//===-- ARMBasicBlockInfo.h - Basic Block Information -----------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Utility functions and data structure for computing block size.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_LIB_TARGET_ARM_ARMBASICBLOCKINFO_H
14#define LLVM_LIB_TARGET_ARM_ARMBASICBLOCKINFO_H
15
16#include "ARMBaseInstrInfo.h"
17#include "ARMMachineFunctionInfo.h"
18#include "llvm/Support/MathExtras.h"
19#include <algorithm>
20#include <cstdint>
21
22namespace llvm {
23
24using BBInfoVector = SmallVectorImpl<BasicBlockInfo>;
25
26/// UnknownPadding - Return the worst case padding that could result from
27/// unknown offset bits. This does not include alignment padding caused by
28/// known offset bits.
29///
30/// @param Align alignment
31/// @param KnownBits Number of known low offset bits.
32inline unsigned UnknownPadding(llvm::Align Align, unsigned KnownBits) {
33 if (KnownBits < Log2(Align))
53
Assuming the condition is true
54
Taking true branch
34 return Align.value() - (1u << KnownBits);
55
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'
35 return 0;
36}
37
38/// BasicBlockInfo - Information about the offset and size of a single
39/// basic block.
40struct BasicBlockInfo {
41 /// Offset - Distance from the beginning of the function to the beginning
42 /// of this basic block.
43 ///
44 /// Offsets are computed assuming worst case padding before an aligned
45 /// block. This means that subtracting basic block offsets always gives a
46 /// conservative estimate of the real distance which may be smaller.
47 ///
48 /// Because worst case padding is used, the computed offset of an aligned
49 /// block may not actually be aligned.
50 unsigned Offset = 0;
51
52 /// Size - Size of the basic block in bytes. If the block contains
53 /// inline assembly, this is a worst case estimate.
54 ///
55 /// The size does not include any alignment padding whether from the
56 /// beginning of the block, or from an aligned jump table at the end.
57 unsigned Size = 0;
58
59 /// KnownBits - The number of low bits in Offset that are known to be
60 /// exact. The remaining bits of Offset are an upper bound.
61 uint8_t KnownBits = 0;
62
63 /// Unalign - When non-zero, the block contains instructions (inline asm)
64 /// of unknown size. The real size may be smaller than Size bytes by a
65 /// multiple of 1 << Unalign.
66 uint8_t Unalign = 0;
67
68 /// PostAlign - When > 1, the block terminator contains a .align
69 /// directive, so the end of the block is aligned to PostAlign bytes.
70 llvm::Align PostAlign;
71
72 BasicBlockInfo() = default;
73
74 /// Compute the number of known offset bits internally to this block.
75 /// This number should be used to predict worst case padding when
76 /// splitting the block.
77 unsigned internalKnownBits() const {
78 unsigned Bits = Unalign ? Unalign : KnownBits;
35
Assuming field 'Unalign' is 0
36
'?' condition is false
79 // If the block size isn't a multiple of the known bits, assume the
80 // worst case padding.
81 if (Size & ((1u << Bits) - 1))
37
Assuming the condition is true
38
Taking true branch
82 Bits = countTrailingZeros(Size);
39
Calling 'countTrailingZeros<unsigned int>'
46
Returning from 'countTrailingZeros<unsigned int>'
47
The value 32 is assigned to 'Bits'
83 return Bits;
48
Returning the value 32 (loaded from 'Bits')
84 }
85
86 /// Compute the offset immediately following this block. If Align is
87 /// specified, return the offset the successor block will get if it has
88 /// this alignment.
89 unsigned postOffset(llvm::Align Align = llvm::Align::None()) const {
90 unsigned PO = Offset + Size;
91 const llvm::Align PA = std::max(PostAlign, Align);
92 if (PA == llvm::Align::None())
93 return PO;
94 // Add alignment padding from the terminator.
95 return PO + UnknownPadding(PA, internalKnownBits());
96 }
97
98 /// Compute the number of known low bits of postOffset. If this block
99 /// contains inline asm, the number of known bits drops to the
100 /// instruction alignment. An aligned terminator may increase the number
101 /// of know bits.
102 /// If LogAlign is given, also consider the alignment of the next block.
103 unsigned postKnownBits(llvm::Align Align = llvm::Align::None()) const {
104 return std::max(Log2(std::max(PostAlign, Align)), internalKnownBits());
105 }
106};
107
108class ARMBasicBlockUtils {
109
110private:
111 MachineFunction &MF;
112 bool isThumb = false;
113 const ARMBaseInstrInfo *TII = nullptr;
114 SmallVector<BasicBlockInfo, 8> BBInfo;
115
116public:
117 ARMBasicBlockUtils(MachineFunction &MF) : MF(MF) {
118 TII =
119 static_cast<const ARMBaseInstrInfo*>(MF.getSubtarget().getInstrInfo());
120 isThumb = MF.getInfo<ARMFunctionInfo>()->isThumbFunction();
121 }
122
123 void computeAllBlockSizes() {
124 BBInfo.resize(MF.getNumBlockIDs());
125 for (MachineBasicBlock &MBB : MF)
126 computeBlockSize(&MBB);
127 }
128
129 void computeBlockSize(MachineBasicBlock *MBB);
130
131 unsigned getOffsetOf(MachineInstr *MI) const;
132
133 unsigned getOffsetOf(MachineBasicBlock *MBB) const {
134 return BBInfo[MBB->getNumber()].Offset;
135 }
136
137 void adjustBBOffsetsAfter(MachineBasicBlock *MBB);
138
139 void adjustBBSize(MachineBasicBlock *MBB, int Size) {
140 BBInfo[MBB->getNumber()].Size += Size;
141 }
142
143 bool isBBInRange(MachineInstr *MI, MachineBasicBlock *DestBB,
144 unsigned MaxDisp) const;
145
146 void insert(unsigned BBNum, BasicBlockInfo BBI) {
147 BBInfo.insert(BBInfo.begin() + BBNum, BBI);
148 }
149
150 void clear() { BBInfo.clear(); }
151
152 BBInfoVector &getBBInfo() { return BBInfo; }
153
154};
155
156} // end namespace llvm
157
158#endif // LLVM_LIB_TARGET_ARM_ARMBASICBLOCKINFO_H

/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h

1//===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains some functions that are useful for math stuff.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_SUPPORT_MATHEXTRAS_H
14#define LLVM_SUPPORT_MATHEXTRAS_H
15
16#include "llvm/Support/Compiler.h"
17#include "llvm/Support/SwapByteOrder.h"
18#include <algorithm>
19#include <cassert>
20#include <climits>
21#include <cstring>
22#include <limits>
23#include <type_traits>
24
25#ifdef __ANDROID_NDK__
26#include <android/api-level.h>
27#endif
28
29#ifdef _MSC_VER
30// Declare these intrinsics manually rather including intrin.h. It's very
31// expensive, and MathExtras.h is popular.
32// #include <intrin.h>
33extern "C" {
34unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask);
35unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask);
36unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask);
37unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask);
38}
39#endif
40
41namespace llvm {
42/// The behavior an operation has on an input of 0.
43enum ZeroBehavior {
44 /// The returned value is undefined.
45 ZB_Undefined,
46 /// The returned value is numeric_limits<T>::max()
47 ZB_Max,
48 /// The returned value is numeric_limits<T>::digits
49 ZB_Width
50};
51
52namespace detail {
53template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter {
54 static unsigned count(T Val, ZeroBehavior) {
55 if (!Val)
56 return std::numeric_limits<T>::digits;
57 if (Val & 0x1)
58 return 0;
59
60 // Bisection method.
61 unsigned ZeroBits = 0;
62 T Shift = std::numeric_limits<T>::digits >> 1;
63 T Mask = std::numeric_limits<T>::max() >> Shift;
64 while (Shift) {
65 if ((Val & Mask) == 0) {
66 Val >>= Shift;
67 ZeroBits |= Shift;
68 }
69 Shift >>= 1;
70 Mask >>= Shift;
71 }
72 return ZeroBits;
73 }
74};
75
76#if defined(__GNUC__4) || defined(_MSC_VER)
77template <typename T> struct TrailingZerosCounter<T, 4> {
78 static unsigned count(T Val, ZeroBehavior ZB) {
79 if (ZB
40.1
'ZB' is not equal to ZB_Undefined
40.1
'ZB' is not equal to ZB_Undefined
40.1
'ZB' is not equal to ZB_Undefined
40.1
'ZB' is not equal to ZB_Undefined
!= ZB_Undefined && Val == 0)
41
Assuming 'Val' is equal to 0
42
Taking true branch
80 return 32;
43
Returning the value 32
81
82#if __has_builtin(__builtin_ctz)1 || defined(__GNUC__4)
83 return __builtin_ctz(Val);
84#elif defined(_MSC_VER)
85 unsigned long Index;
86 _BitScanForward(&Index, Val);
87 return Index;
88#endif
89 }
90};
91
92#if !defined(_MSC_VER) || defined(_M_X64)
93template <typename T> struct TrailingZerosCounter<T, 8> {
94 static unsigned count(T Val, ZeroBehavior ZB) {
95 if (ZB != ZB_Undefined && Val == 0)
96 return 64;
97
98#if __has_builtin(__builtin_ctzll)1 || defined(__GNUC__4)
99 return __builtin_ctzll(Val);
100#elif defined(_MSC_VER)
101 unsigned long Index;
102 _BitScanForward64(&Index, Val);
103 return Index;
104#endif
105 }
106};
107#endif
108#endif
109} // namespace detail
110
111/// Count number of 0's from the least significant bit to the most
112/// stopping at the first 1.
113///
114/// Only unsigned integral types are allowed.
115///
116/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
117/// valid arguments.
118template <typename T>
119unsigned countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
120 static_assert(std::numeric_limits<T>::is_integer &&
121 !std::numeric_limits<T>::is_signed,
122 "Only unsigned integral types are allowed.");
123 return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
40
Calling 'TrailingZerosCounter::count'
44
Returning from 'TrailingZerosCounter::count'
45
Returning the value 32
124}
125
126namespace detail {
127template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter {
128 static unsigned count(T Val, ZeroBehavior) {
129 if (!Val)
130 return std::numeric_limits<T>::digits;
131
132 // Bisection method.
133 unsigned ZeroBits = 0;
134 for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
135 T Tmp = Val >> Shift;
136 if (Tmp)
137 Val = Tmp;
138 else
139 ZeroBits |= Shift;
140 }
141 return ZeroBits;
142 }
143};
144
145#if defined(__GNUC__4) || defined(_MSC_VER)
146template <typename T> struct LeadingZerosCounter<T, 4> {
147 static unsigned count(T Val, ZeroBehavior ZB) {
148 if (ZB != ZB_Undefined && Val == 0)
149 return 32;
150
151#if __has_builtin(__builtin_clz)1 || defined(__GNUC__4)
152 return __builtin_clz(Val);
153#elif defined(_MSC_VER)
154 unsigned long Index;
155 _BitScanReverse(&Index, Val);
156 return Index ^ 31;
157#endif
158 }
159};
160
161#if !defined(_MSC_VER) || defined(_M_X64)
162template <typename T> struct LeadingZerosCounter<T, 8> {
163 static unsigned count(T Val, ZeroBehavior ZB) {
164 if (ZB != ZB_Undefined && Val == 0)
165 return 64;
166
167#if __has_builtin(__builtin_clzll)1 || defined(__GNUC__4)
168 return __builtin_clzll(Val);
169#elif defined(_MSC_VER)
170 unsigned long Index;
171 _BitScanReverse64(&Index, Val);
172 return Index ^ 63;
173#endif
174 }
175};
176#endif
177#endif
178} // namespace detail
179
180/// Count number of 0's from the most significant bit to the least
181/// stopping at the first 1.
182///
183/// Only unsigned integral types are allowed.
184///
185/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
186/// valid arguments.
187template <typename T>
188unsigned countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
189 static_assert(std::numeric_limits<T>::is_integer &&
190 !std::numeric_limits<T>::is_signed,
191 "Only unsigned integral types are allowed.");
192 return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val, ZB);
193}
194
195/// Get the index of the first set bit starting from the least
196/// significant bit.
197///
198/// Only unsigned integral types are allowed.
199///
200/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
201/// valid arguments.
202template <typename T> T findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) {
203 if (ZB == ZB_Max && Val == 0)
204 return std::numeric_limits<T>::max();
205
206 return countTrailingZeros(Val, ZB_Undefined);
207}
208
209/// Create a bitmask with the N right-most bits set to 1, and all other
210/// bits set to 0. Only unsigned types are allowed.
211template <typename T> T maskTrailingOnes(unsigned N) {
212 static_assert(std::is_unsigned<T>::value, "Invalid type!");
213 const unsigned Bits = CHAR_BIT8 * sizeof(T);
214 assert(N <= Bits && "Invalid bit index")((N <= Bits && "Invalid bit index") ? static_cast<
void> (0) : __assert_fail ("N <= Bits && \"Invalid bit index\""
, "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h"
, 214, __PRETTY_FUNCTION__))
;
215 return N == 0 ? 0 : (T(-1) >> (Bits - N));
216}
217
218/// Create a bitmask with the N left-most bits set to 1, and all other
219/// bits set to 0. Only unsigned types are allowed.
220template <typename T> T maskLeadingOnes(unsigned N) {
221 return ~maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
222}
223
224/// Create a bitmask with the N right-most bits set to 0, and all other
225/// bits set to 1. Only unsigned types are allowed.
226template <typename T> T maskTrailingZeros(unsigned N) {
227 return maskLeadingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
228}
229
230/// Create a bitmask with the N left-most bits set to 0, and all other
231/// bits set to 1. Only unsigned types are allowed.
232template <typename T> T maskLeadingZeros(unsigned N) {
233 return maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
234}
235
236/// Get the index of the last set bit starting from the least
237/// significant bit.
238///
239/// Only unsigned integral types are allowed.
240///
241/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
242/// valid arguments.
243template <typename T> T findLastSet(T Val, ZeroBehavior ZB = ZB_Max) {
244 if (ZB == ZB_Max && Val == 0)
245 return std::numeric_limits<T>::max();
246
247 // Use ^ instead of - because both gcc and llvm can remove the associated ^
248 // in the __builtin_clz intrinsic on x86.
249 return countLeadingZeros(Val, ZB_Undefined) ^
250 (std::numeric_limits<T>::digits - 1);
251}
252
253/// Macro compressed bit reversal table for 256 bits.
254///
255/// http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
256static const unsigned char BitReverseTable256[256] = {
257#define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64
258#define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16)
259#define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4)
260 R6(0), R6(2), R6(1), R6(3)
261#undef R2
262#undef R4
263#undef R6
264};
265
266/// Reverse the bits in \p Val.
267template <typename T>
268T reverseBits(T Val) {
269 unsigned char in[sizeof(Val)];
270 unsigned char out[sizeof(Val)];
271 std::memcpy(in, &Val, sizeof(Val));
272 for (unsigned i = 0; i < sizeof(Val); ++i)
273 out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
274 std::memcpy(&Val, out, sizeof(Val));
275 return Val;
276}
277
278// NOTE: The following support functions use the _32/_64 extensions instead of
279// type overloading so that signed and unsigned integers can be used without
280// ambiguity.
281
282/// Return the high 32 bits of a 64 bit value.
283constexpr inline uint32_t Hi_32(uint64_t Value) {
284 return static_cast<uint32_t>(Value >> 32);
285}
286
287/// Return the low 32 bits of a 64 bit value.
288constexpr inline uint32_t Lo_32(uint64_t Value) {
289 return static_cast<uint32_t>(Value);
290}
291
292/// Make a 64-bit integer from a high / low pair of 32-bit integers.
293constexpr inline uint64_t Make_64(uint32_t High, uint32_t Low) {
294 return ((uint64_t)High << 32) | (uint64_t)Low;
295}
296
297/// Checks if an integer fits into the given bit width.
298template <unsigned N> constexpr inline bool isInt(int64_t x) {
299 return N >= 64 || (-(INT64_C(1)1L<<(N-1)) <= x && x < (INT64_C(1)1L<<(N-1)));
300}
301// Template specializations to get better code for common cases.
302template <> constexpr inline bool isInt<8>(int64_t x) {
303 return static_cast<int8_t>(x) == x;
304}
305template <> constexpr inline bool isInt<16>(int64_t x) {
306 return static_cast<int16_t>(x) == x;
307}
308template <> constexpr inline bool isInt<32>(int64_t x) {
309 return static_cast<int32_t>(x) == x;
310}
311
312/// Checks if a signed integer is an N bit number shifted left by S.
313template <unsigned N, unsigned S>
314constexpr inline bool isShiftedInt(int64_t x) {
315 static_assert(
316 N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
317 static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
318 return isInt<N + S>(x) && (x % (UINT64_C(1)1UL << S) == 0);
319}
320
321/// Checks if an unsigned integer fits into the given bit width.
322///
323/// This is written as two functions rather than as simply
324///
325/// return N >= 64 || X < (UINT64_C(1) << N);
326///
327/// to keep MSVC from (incorrectly) warning on isUInt<64> that we're shifting
328/// left too many places.
329template <unsigned N>
330constexpr inline typename std::enable_if<(N < 64), bool>::type
331isUInt(uint64_t X) {
332 static_assert(N > 0, "isUInt<0> doesn't make sense");
333 return X < (UINT64_C(1)1UL << (N));
334}
335template <unsigned N>
336constexpr inline typename std::enable_if<N >= 64, bool>::type
337isUInt(uint64_t X) {
338 return true;
339}
340
341// Template specializations to get better code for common cases.
342template <> constexpr inline bool isUInt<8>(uint64_t x) {
343 return static_cast<uint8_t>(x) == x;
344}
345template <> constexpr inline bool isUInt<16>(uint64_t x) {
346 return static_cast<uint16_t>(x) == x;
347}
348template <> constexpr inline bool isUInt<32>(uint64_t x) {
349 return static_cast<uint32_t>(x) == x;
350}
351
352/// Checks if a unsigned integer is an N bit number shifted left by S.
353template <unsigned N, unsigned S>
354constexpr inline bool isShiftedUInt(uint64_t x) {
355 static_assert(
356 N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
357 static_assert(N + S <= 64,
358 "isShiftedUInt<N, S> with N + S > 64 is too wide.");
359 // Per the two static_asserts above, S must be strictly less than 64. So
360 // 1 << S is not undefined behavior.
361 return isUInt<N + S>(x) && (x % (UINT64_C(1)1UL << S) == 0);
362}
363
364/// Gets the maximum value for a N-bit unsigned integer.
365inline uint64_t maxUIntN(uint64_t N) {
366 assert(N > 0 && N <= 64 && "integer width out of range")((N > 0 && N <= 64 && "integer width out of range"
) ? static_cast<void> (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h"
, 366, __PRETTY_FUNCTION__))
;
367
368 // uint64_t(1) << 64 is undefined behavior, so we can't do
369 // (uint64_t(1) << N) - 1
370 // without checking first that N != 64. But this works and doesn't have a
371 // branch.
372 return UINT64_MAX(18446744073709551615UL) >> (64 - N);
373}
374
375/// Gets the minimum value for a N-bit signed integer.
376inline int64_t minIntN(int64_t N) {
377 assert(N > 0 && N <= 64 && "integer width out of range")((N > 0 && N <= 64 && "integer width out of range"
) ? static_cast<void> (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h"
, 377, __PRETTY_FUNCTION__))
;
378
379 return -(UINT64_C(1)1UL<<(N-1));
380}
381
382/// Gets the maximum value for a N-bit signed integer.
383inline int64_t maxIntN(int64_t N) {
384 assert(N > 0 && N <= 64 && "integer width out of range")((N > 0 && N <= 64 && "integer width out of range"
) ? static_cast<void> (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h"
, 384, __PRETTY_FUNCTION__))
;
385
386 // This relies on two's complement wraparound when N == 64, so we convert to
387 // int64_t only at the very end to avoid UB.
388 return (UINT64_C(1)1UL << (N - 1)) - 1;
389}
390
391/// Checks if an unsigned integer fits into the given (dynamic) bit width.
392inline bool isUIntN(unsigned N, uint64_t x) {
393 return N >= 64 || x <= maxUIntN(N);
394}
395
396/// Checks if an signed integer fits into the given (dynamic) bit width.
397inline bool isIntN(unsigned N, int64_t x) {
398 return N >= 64 || (minIntN(N) <= x && x <= maxIntN(N));
399}
400
401/// Return true if the argument is a non-empty sequence of ones starting at the
402/// least significant bit with the remainder zero (32 bit version).
403/// Ex. isMask_32(0x0000FFFFU) == true.
404constexpr inline bool isMask_32(uint32_t Value) {
405 return Value && ((Value + 1) & Value) == 0;
406}
407
408/// Return true if the argument is a non-empty sequence of ones starting at the
409/// least significant bit with the remainder zero (64 bit version).
410constexpr inline bool isMask_64(uint64_t Value) {
411 return Value && ((Value + 1) & Value) == 0;
412}
413
414/// Return true if the argument contains a non-empty sequence of ones with the
415/// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true.
416constexpr inline bool isShiftedMask_32(uint32_t Value) {
417 return Value && isMask_32((Value - 1) | Value);
418}
419
420/// Return true if the argument contains a non-empty sequence of ones with the
421/// remainder zero (64 bit version.)
422constexpr inline bool isShiftedMask_64(uint64_t Value) {
423 return Value && isMask_64((Value - 1) | Value);
424}
425
426/// Return true if the argument is a power of two > 0.
427/// Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
428constexpr inline bool isPowerOf2_32(uint32_t Value) {
429 return Value && !(Value & (Value - 1));
430}
431
432/// Return true if the argument is a power of two > 0 (64 bit edition.)
433constexpr inline bool isPowerOf2_64(uint64_t Value) {
434 return Value && !(Value & (Value - 1));
435}
436
437/// Return a byte-swapped representation of the 16-bit argument.
438inline uint16_t ByteSwap_16(uint16_t Value) {
439 return sys::SwapByteOrder_16(Value);
440}
441
442/// Return a byte-swapped representation of the 32-bit argument.
443inline uint32_t ByteSwap_32(uint32_t Value) {
444 return sys::SwapByteOrder_32(Value);
445}
446
447/// Return a byte-swapped representation of the 64-bit argument.
448inline uint64_t ByteSwap_64(uint64_t Value) {
449 return sys::SwapByteOrder_64(Value);
450}
451
452/// Count the number of ones from the most significant bit to the first
453/// zero bit.
454///
455/// Ex. countLeadingOnes(0xFF0FFF00) == 8.
456/// Only unsigned integral types are allowed.
457///
458/// \param ZB the behavior on an input of all ones. Only ZB_Width and
459/// ZB_Undefined are valid arguments.
460template <typename T>
461unsigned countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
462 static_assert(std::numeric_limits<T>::is_integer &&
463 !std::numeric_limits<T>::is_signed,
464 "Only unsigned integral types are allowed.");
465 return countLeadingZeros<T>(~Value, ZB);
466}
467
468/// Count the number of ones from the least significant bit to the first
469/// zero bit.
470///
471/// Ex. countTrailingOnes(0x00FF00FF) == 8.
472/// Only unsigned integral types are allowed.
473///
474/// \param ZB the behavior on an input of all ones. Only ZB_Width and
475/// ZB_Undefined are valid arguments.
476template <typename T>
477unsigned countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
478 static_assert(std::numeric_limits<T>::is_integer &&
479 !std::numeric_limits<T>::is_signed,
480 "Only unsigned integral types are allowed.");
481 return countTrailingZeros<T>(~Value, ZB);
482}
483
484namespace detail {
485template <typename T, std::size_t SizeOfT> struct PopulationCounter {
486 static unsigned count(T Value) {
487 // Generic version, forward to 32 bits.
488 static_assert(SizeOfT <= 4, "Not implemented!");
489#if defined(__GNUC__4)
490 return __builtin_popcount(Value);
491#else
492 uint32_t v = Value;
493 v = v - ((v >> 1) & 0x55555555);
494 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
495 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
496#endif
497 }
498};
499
500template <typename T> struct PopulationCounter<T, 8> {
501 static unsigned count(T Value) {
502#if defined(__GNUC__4)
503 return __builtin_popcountll(Value);
504#else
505 uint64_t v = Value;
506 v = v - ((v >> 1) & 0x5555555555555555ULL);
507 v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
508 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
509 return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
510#endif
511 }
512};
513} // namespace detail
514
515/// Count the number of set bits in a value.
516/// Ex. countPopulation(0xF000F000) = 8
517/// Returns 0 if the word is zero.
518template <typename T>
519inline unsigned countPopulation(T Value) {
520 static_assert(std::numeric_limits<T>::is_integer &&
521 !std::numeric_limits<T>::is_signed,
522 "Only unsigned integral types are allowed.");
523 return detail::PopulationCounter<T, sizeof(T)>::count(Value);
524}
525
526/// Return the log base 2 of the specified value.
527inline double Log2(double Value) {
528#if defined(__ANDROID_API__) && __ANDROID_API__ < 18
529 return __builtin_log(Value) / __builtin_log(2.0);
530#else
531 return log2(Value);
532#endif
533}
534
535/// Return the floor log base 2 of the specified value, -1 if the value is zero.
536/// (32 bit edition.)
537/// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
538inline unsigned Log2_32(uint32_t Value) {
539 return 31 - countLeadingZeros(Value);
540}
541
542/// Return the floor log base 2 of the specified value, -1 if the value is zero.
543/// (64 bit edition.)
544inline unsigned Log2_64(uint64_t Value) {
545 return 63 - countLeadingZeros(Value);
546}
547
548/// Return the ceil log base 2 of the specified value, 32 if the value is zero.
549/// (32 bit edition).
550/// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
551inline unsigned Log2_32_Ceil(uint32_t Value) {
552 return 32 - countLeadingZeros(Value - 1);
553}
554
555/// Return the ceil log base 2 of the specified value, 64 if the value is zero.
556/// (64 bit edition.)
557inline unsigned Log2_64_Ceil(uint64_t Value) {
558 return 64 - countLeadingZeros(Value - 1);
559}
560
561/// Return the greatest common divisor of the values using Euclid's algorithm.
562template <typename T>
563inline T greatestCommonDivisor(T A, T B) {
564 while (B) {
565 T Tmp = B;
566 B = A % B;
567 A = Tmp;
568 }
569 return A;
570}
571
572inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
573 return greatestCommonDivisor<uint64_t>(A, B);
574}
575
576/// This function takes a 64-bit integer and returns the bit equivalent double.
577inline double BitsToDouble(uint64_t Bits) {
578 double D;
579 static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
580 memcpy(&D, &Bits, sizeof(Bits));
581 return D;
582}
583
584/// This function takes a 32-bit integer and returns the bit equivalent float.
585inline float BitsToFloat(uint32_t Bits) {
586 float F;
587 static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
588 memcpy(&F, &Bits, sizeof(Bits));
589 return F;
590}
591
592/// This function takes a double and returns the bit equivalent 64-bit integer.
593/// Note that copying doubles around changes the bits of NaNs on some hosts,
594/// notably x86, so this routine cannot be used if these bits are needed.
595inline uint64_t DoubleToBits(double Double) {
596 uint64_t Bits;
597 static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
598 memcpy(&Bits, &Double, sizeof(Double));
599 return Bits;
600}
601
602/// This function takes a float and returns the bit equivalent 32-bit integer.
603/// Note that copying floats around changes the bits of NaNs on some hosts,
604/// notably x86, so this routine cannot be used if these bits are needed.
605inline uint32_t FloatToBits(float Float) {
606 uint32_t Bits;
607 static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
608 memcpy(&Bits, &Float, sizeof(Float));
609 return Bits;
610}
611
612/// A and B are either alignments or offsets. Return the minimum alignment that
613/// may be assumed after adding the two together.
614constexpr inline uint64_t MinAlign(uint64_t A, uint64_t B) {
615 // The largest power of 2 that divides both A and B.
616 //
617 // Replace "-Value" by "1+~Value" in the following commented code to avoid
618 // MSVC warning C4146
619 // return (A | B) & -(A | B);
620 return (A | B) & (1 + ~(A | B));
621}
622
623/// Aligns \c Addr to \c Alignment bytes, rounding up.
624///
625/// Alignment should be a power of two. This method rounds up, so
626/// alignAddr(7, 4) == 8 and alignAddr(8, 4) == 8.
627inline uintptr_t alignAddr(const void *Addr, size_t Alignment) {
628 assert(Alignment && isPowerOf2_64((uint64_t)Alignment) &&((Alignment && isPowerOf2_64((uint64_t)Alignment) &&
"Alignment is not a power of two!") ? static_cast<void>
(0) : __assert_fail ("Alignment && isPowerOf2_64((uint64_t)Alignment) && \"Alignment is not a power of two!\""
, "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h"
, 629, __PRETTY_FUNCTION__))
629 "Alignment is not a power of two!")((Alignment && isPowerOf2_64((uint64_t)Alignment) &&
"Alignment is not a power of two!") ? static_cast<void>
(0) : __assert_fail ("Alignment && isPowerOf2_64((uint64_t)Alignment) && \"Alignment is not a power of two!\""
, "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h"
, 629, __PRETTY_FUNCTION__))
;
630
631 assert((uintptr_t)Addr + Alignment - 1 >= (uintptr_t)Addr)(((uintptr_t)Addr + Alignment - 1 >= (uintptr_t)Addr) ? static_cast
<void> (0) : __assert_fail ("(uintptr_t)Addr + Alignment - 1 >= (uintptr_t)Addr"
, "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h"
, 631, __PRETTY_FUNCTION__))
;
632
633 return (((uintptr_t)Addr + Alignment - 1) & ~(uintptr_t)(Alignment - 1));
634}
635
636/// Returns the necessary adjustment for aligning \c Ptr to \c Alignment
637/// bytes, rounding up.
638inline size_t alignmentAdjustment(const void *Ptr, size_t Alignment) {
639 return alignAddr(Ptr, Alignment) - (uintptr_t)Ptr;
640}
641
642/// Returns the next power of two (in 64-bits) that is strictly greater than A.
643/// Returns zero on overflow.
644inline uint64_t NextPowerOf2(uint64_t A) {
645 A |= (A >> 1);
646 A |= (A >> 2);
647 A |= (A >> 4);
648 A |= (A >> 8);
649 A |= (A >> 16);
650 A |= (A >> 32);
651 return A + 1;
652}
653
654/// Returns the power of two which is less than or equal to the given value.
655/// Essentially, it is a floor operation across the domain of powers of two.
656inline uint64_t PowerOf2Floor(uint64_t A) {
657 if (!A) return 0;
658 return 1ull << (63 - countLeadingZeros(A, ZB_Undefined));
659}
660
661/// Returns the power of two which is greater than or equal to the given value.
662/// Essentially, it is a ceil operation across the domain of powers of two.
663inline uint64_t PowerOf2Ceil(uint64_t A) {
664 if (!A)
665 return 0;
666 return NextPowerOf2(A - 1);
667}
668
669/// Returns the next integer (mod 2**64) that is greater than or equal to
670/// \p Value and is a multiple of \p Align. \p Align must be non-zero.
671///
672/// If non-zero \p Skew is specified, the return value will be a minimal
673/// integer that is greater than or equal to \p Value and equal to
674/// \p Align * N + \p Skew for some integer N. If \p Skew is larger than
675/// \p Align, its value is adjusted to '\p Skew mod \p Align'.
676///
677/// Examples:
678/// \code
679/// alignTo(5, 8) = 8
680/// alignTo(17, 8) = 24
681/// alignTo(~0LL, 8) = 0
682/// alignTo(321, 255) = 510
683///
684/// alignTo(5, 8, 7) = 7
685/// alignTo(17, 8, 1) = 17
686/// alignTo(~0LL, 8, 3) = 3
687/// alignTo(321, 255, 42) = 552
688/// \endcode
689inline uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
690 assert(Align != 0u && "Align can't be 0.")((Align != 0u && "Align can't be 0.") ? static_cast<
void> (0) : __assert_fail ("Align != 0u && \"Align can't be 0.\""
, "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h"
, 690, __PRETTY_FUNCTION__))
;
691 Skew %= Align;
692 return (Value + Align - 1 - Skew) / Align * Align + Skew;
693}
694
695/// Returns the next integer (mod 2**64) that is greater than or equal to
696/// \p Value and is a multiple of \c Align. \c Align must be non-zero.
697template <uint64_t Align> constexpr inline uint64_t alignTo(uint64_t Value) {
698 static_assert(Align != 0u, "Align must be non-zero");
699 return (Value + Align - 1) / Align * Align;
700}
701
702/// Returns the integer ceil(Numerator / Denominator).
703inline uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator) {
704 return alignTo(Numerator, Denominator) / Denominator;
705}
706
707/// Returns the largest uint64_t less than or equal to \p Value and is
708/// \p Skew mod \p Align. \p Align must be non-zero
709inline uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
710 assert(Align != 0u && "Align can't be 0.")((Align != 0u && "Align can't be 0.") ? static_cast<
void> (0) : __assert_fail ("Align != 0u && \"Align can't be 0.\""
, "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h"
, 710, __PRETTY_FUNCTION__))
;
711 Skew %= Align;
712 return (Value - Skew) / Align * Align + Skew;
713}
714
715/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
716/// Requires 0 < B <= 32.
717template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
718 static_assert(B > 0, "Bit width can't be 0.");
719 static_assert(B <= 32, "Bit width out of range.");
720 return int32_t(X << (32 - B)) >> (32 - B);
721}
722
723/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
724/// Requires 0 < B < 32.
725inline int32_t SignExtend32(uint32_t X, unsigned B) {
726 assert(B > 0 && "Bit width can't be 0.")((B > 0 && "Bit width can't be 0.") ? static_cast<
void> (0) : __assert_fail ("B > 0 && \"Bit width can't be 0.\""
, "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h"
, 726, __PRETTY_FUNCTION__))
;
727 assert(B <= 32 && "Bit width out of range.")((B <= 32 && "Bit width out of range.") ? static_cast
<void> (0) : __assert_fail ("B <= 32 && \"Bit width out of range.\""
, "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h"
, 727, __PRETTY_FUNCTION__))
;
728 return int32_t(X << (32 - B)) >> (32 - B);
729}
730
731/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
732/// Requires 0 < B < 64.
733template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
734 static_assert(B > 0, "Bit width can't be 0.");
735 static_assert(B <= 64, "Bit width out of range.");
736 return int64_t(x << (64 - B)) >> (64 - B);
737}
738
739/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
740/// Requires 0 < B < 64.
741inline int64_t SignExtend64(uint64_t X, unsigned B) {
742 assert(B > 0 && "Bit width can't be 0.")((B > 0 && "Bit width can't be 0.") ? static_cast<
void> (0) : __assert_fail ("B > 0 && \"Bit width can't be 0.\""
, "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h"
, 742, __PRETTY_FUNCTION__))
;
743 assert(B <= 64 && "Bit width out of range.")((B <= 64 && "Bit width out of range.") ? static_cast
<void> (0) : __assert_fail ("B <= 64 && \"Bit width out of range.\""
, "/build/llvm-toolchain-snapshot-10~svn372306/include/llvm/Support/MathExtras.h"
, 743, __PRETTY_FUNCTION__))
;
744 return int64_t(X << (64 - B)) >> (64 - B);
745}
746
747/// Subtract two unsigned integers, X and Y, of type T and return the absolute
748/// value of the result.
749template <typename T>
750typename std::enable_if<std::is_unsigned<T>::value, T>::type
751AbsoluteDifference(T X, T Y) {
752 return std::max(X, Y) - std::min(X, Y);
753}
754
755/// Add two unsigned integers, X and Y, of type T. Clamp the result to the
756/// maximum representable value of T on overflow. ResultOverflowed indicates if
757/// the result is larger than the maximum representable value of type T.
758template <typename T>
759typename std::enable_if<std::is_unsigned<T>::value, T>::type
760SaturatingAdd(T X, T Y, bool *ResultOverflowed = nullptr) {
761 bool Dummy;
762 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
763 // Hacker's Delight, p. 29
764 T Z = X + Y;
765 Overflowed = (Z < X || Z < Y);
766 if (Overflowed)
767 return std::numeric_limits<T>::max();
768 else
769 return Z;
770}
771
772/// Multiply two unsigned integers, X and Y, of type T. Clamp the result to the
773/// maximum representable value of T on overflow. ResultOverflowed indicates if
774/// the result is larger than the maximum representable value of type T.
775template <typename T>
776typename std::enable_if<std::is_unsigned<T>::value, T>::type
777SaturatingMultiply(T X, T Y, bool *ResultOverflowed = nullptr) {
778 bool Dummy;
779 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
780
781 // Hacker's Delight, p. 30 has a different algorithm, but we don't use that
782 // because it fails for uint16_t (where multiplication can have undefined
783 // behavior due to promotion to int), and requires a division in addition
784 // to the multiplication.
785
786 Overflowed = false;
787
788 // Log2(Z) would be either Log2Z or Log2Z + 1.
789 // Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z
790 // will necessarily be less than Log2Max as desired.
791 int Log2Z = Log2_64(X) + Log2_64(Y);
792 const T Max = std::numeric_limits<T>::max();
793 int Log2Max = Log2_64(Max);
794 if (Log2Z < Log2Max) {
795 return X * Y;
796 }
797 if (Log2Z > Log2Max) {
798 Overflowed = true;
799 return Max;
800 }
801
802 // We're going to use the top bit, and maybe overflow one
803 // bit past it. Multiply all but the bottom bit then add
804 // that on at the end.
805 T Z = (X >> 1) * Y;
806 if (Z & ~(Max >> 1)) {
807 Overflowed = true;
808 return Max;
809 }
810 Z <<= 1;
811 if (X & 1)
812 return SaturatingAdd(Z, Y, ResultOverflowed);
813
814 return Z;
815}
816
817/// Multiply two unsigned integers, X and Y, and add the unsigned integer, A to
818/// the product. Clamp the result to the maximum representable value of T on
819/// overflow. ResultOverflowed indicates if the result is larger than the
820/// maximum representable value of type T.
821template <typename T>
822typename std::enable_if<std::is_unsigned<T>::value, T>::type
823SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed = nullptr) {
824 bool Dummy;
825 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
826
827 T Product = SaturatingMultiply(X, Y, &Overflowed);
828 if (Overflowed)
829 return Product;
830
831 return SaturatingAdd(A, Product, &Overflowed);
832}
833
834/// Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
835extern const float huge_valf;
836
837
838/// Add two signed integers, computing the two's complement truncated result,
839/// returning true if overflow occured.
840template <typename T>
841typename std::enable_if<std::is_signed<T>::value, T>::type
842AddOverflow(T X, T Y, T &Result) {
843#if __has_builtin(__builtin_add_overflow)1
844 return __builtin_add_overflow(X, Y, &Result);
845#else
846 // Perform the unsigned addition.
847 using U = typename std::make_unsigned<T>::type;
848 const U UX = static_cast<U>(X);
849 const U UY = static_cast<U>(Y);
850 const U UResult = UX + UY;
851
852 // Convert to signed.
853 Result = static_cast<T>(UResult);
854
855 // Adding two positive numbers should result in a positive number.
856 if (X > 0 && Y > 0)
857 return Result <= 0;
858 // Adding two negatives should result in a negative number.
859 if (X < 0 && Y < 0)
860 return Result >= 0;
861 return false;
862#endif
863}
864
865/// Subtract two signed integers, computing the two's complement truncated
866/// result, returning true if an overflow ocurred.
867template <typename T>
868typename std::enable_if<std::is_signed<T>::value, T>::type
869SubOverflow(T X, T Y, T &Result) {
870#if __has_builtin(__builtin_sub_overflow)1
871 return __builtin_sub_overflow(X, Y, &Result);
872#else
873 // Perform the unsigned addition.
874 using U = typename std::make_unsigned<T>::type;
875 const U UX = static_cast<U>(X);
876 const U UY = static_cast<U>(Y);
877 const U UResult = UX - UY;
878
879 // Convert to signed.
880 Result = static_cast<T>(UResult);
881
882 // Subtracting a positive number from a negative results in a negative number.
883 if (X <= 0 && Y > 0)
884 return Result >= 0;
885 // Subtracting a negative number from a positive results in a positive number.
886 if (X >= 0 && Y < 0)
887 return Result <= 0;
888 return false;
889#endif
890}
891
892
893/// Multiply two signed integers, computing the two's complement truncated
894/// result, returning true if an overflow ocurred.
895template <typename T>
896typename std::enable_if<std::is_signed<T>::value, T>::type
897MulOverflow(T X, T Y, T &Result) {
898 // Perform the unsigned multiplication on absolute values.
899 using U = typename std::make_unsigned<T>::type;
900 const U UX = X < 0 ? (0 - static_cast<U>(X)) : static_cast<U>(X);
901 const U UY = Y < 0 ? (0 - static_cast<U>(Y)) : static_cast<U>(Y);
902 const U UResult = UX * UY;
903
904 // Convert to signed.
905 const bool IsNegative = (X < 0) ^ (Y < 0);
906 Result = IsNegative ? (0 - UResult) : UResult;
907
908 // If any of the args was 0, result is 0 and no overflow occurs.
909 if (UX == 0 || UY == 0)
910 return false;
911
912 // UX and UY are in [1, 2^n], where n is the number of digits.
913 // Check how the max allowed absolute value (2^n for negative, 2^(n-1) for
914 // positive) divided by an argument compares to the other.
915 if (IsNegative)
916 return UX > (static_cast<U>(std::numeric_limits<T>::max()) + U(1)) / UY;
917 else
918 return UX > (static_cast<U>(std::numeric_limits<T>::max())) / UY;
919}
920
921} // End llvm namespace
922
923#endif