Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

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

/build/llvm-toolchain-snapshot-8~svn345461/lib/Target/ARM/ARMConstantIslandPass.cpp

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

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

/build/llvm-toolchain-snapshot-8~svn345461/include/llvm/Support/MathExtras.h

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