Bug Summary

File:lib/CodeGen/RegAllocPBQP.cpp
Warning:line 929, column 7
Potential leak of memory pointed to by field '_M_head_impl'

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 RegAllocPBQP.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn326551/build-llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-7~svn326551/lib/CodeGen -I /build/llvm-toolchain-snapshot-7~svn326551/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn326551/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn326551/build-llvm/lib/CodeGen -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-03-02-155150-1477-1 -x c++ /build/llvm-toolchain-snapshot-7~svn326551/lib/CodeGen/RegAllocPBQP.cpp

/build/llvm-toolchain-snapshot-7~svn326551/lib/CodeGen/RegAllocPBQP.cpp

1//===- RegAllocPBQP.cpp ---- PBQP Register Allocator ----------------------===//
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 Partitioned Boolean Quadratic Programming (PBQP) based
11// register allocator for LLVM. This allocator works by constructing a PBQP
12// problem representing the register allocation problem under consideration,
13// solving this using a PBQP solver, and mapping the solution back to a
14// register assignment. If any variables are selected for spilling then spill
15// code is inserted and the process repeated.
16//
17// The PBQP solver (pbqp.c) provided for this allocator uses a heuristic tuned
18// for register allocation. For more information on PBQP for register
19// allocation, see the following papers:
20//
21// (1) Hames, L. and Scholz, B. 2006. Nearly optimal register allocation with
22// PBQP. In Proceedings of the 7th Joint Modular Languages Conference
23// (JMLC'06). LNCS, vol. 4228. Springer, New York, NY, USA. 346-361.
24//
25// (2) Scholz, B., Eckstein, E. 2002. Register allocation for irregular
26// architectures. In Proceedings of the Joint Conference on Languages,
27// Compilers and Tools for Embedded Systems (LCTES'02), ACM Press, New York,
28// NY, USA, 139-148.
29//
30//===----------------------------------------------------------------------===//
31
32#include "llvm/CodeGen/RegAllocPBQP.h"
33#include "RegisterCoalescer.h"
34#include "Spiller.h"
35#include "llvm/ADT/ArrayRef.h"
36#include "llvm/ADT/BitVector.h"
37#include "llvm/ADT/DenseMap.h"
38#include "llvm/ADT/DenseSet.h"
39#include "llvm/ADT/STLExtras.h"
40#include "llvm/ADT/SmallPtrSet.h"
41#include "llvm/ADT/SmallVector.h"
42#include "llvm/ADT/StringRef.h"
43#include "llvm/Analysis/AliasAnalysis.h"
44#include "llvm/CodeGen/CalcSpillWeights.h"
45#include "llvm/CodeGen/LiveInterval.h"
46#include "llvm/CodeGen/LiveIntervals.h"
47#include "llvm/CodeGen/LiveRangeEdit.h"
48#include "llvm/CodeGen/LiveStacks.h"
49#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
50#include "llvm/CodeGen/MachineDominators.h"
51#include "llvm/CodeGen/MachineFunction.h"
52#include "llvm/CodeGen/MachineFunctionPass.h"
53#include "llvm/CodeGen/MachineInstr.h"
54#include "llvm/CodeGen/MachineLoopInfo.h"
55#include "llvm/CodeGen/MachineRegisterInfo.h"
56#include "llvm/CodeGen/PBQP/Graph.h"
57#include "llvm/CodeGen/PBQP/Math.h"
58#include "llvm/CodeGen/PBQP/Solution.h"
59#include "llvm/CodeGen/PBQPRAConstraint.h"
60#include "llvm/CodeGen/RegAllocRegistry.h"
61#include "llvm/CodeGen/SlotIndexes.h"
62#include "llvm/CodeGen/TargetRegisterInfo.h"
63#include "llvm/CodeGen/TargetSubtargetInfo.h"
64#include "llvm/CodeGen/VirtRegMap.h"
65#include "llvm/IR/Function.h"
66#include "llvm/IR/Module.h"
67#include "llvm/MC/MCRegisterInfo.h"
68#include "llvm/Pass.h"
69#include "llvm/Support/CommandLine.h"
70#include "llvm/Support/Compiler.h"
71#include "llvm/Support/Debug.h"
72#include "llvm/Support/FileSystem.h"
73#include "llvm/Support/Printable.h"
74#include "llvm/Support/raw_ostream.h"
75#include <algorithm>
76#include <cassert>
77#include <cstddef>
78#include <limits>
79#include <map>
80#include <memory>
81#include <queue>
82#include <set>
83#include <sstream>
84#include <string>
85#include <system_error>
86#include <tuple>
87#include <utility>
88#include <vector>
89
90using namespace llvm;
91
92#define DEBUG_TYPE"regalloc" "regalloc"
93
94static RegisterRegAlloc
95RegisterPBQPRepAlloc("pbqp", "PBQP register allocator",
96 createDefaultPBQPRegisterAllocator);
97
98static cl::opt<bool>
99PBQPCoalescing("pbqp-coalescing",
100 cl::desc("Attempt coalescing during PBQP register allocation."),
101 cl::init(false), cl::Hidden);
102
103#ifndef NDEBUG
104static cl::opt<bool>
105PBQPDumpGraphs("pbqp-dump-graphs",
106 cl::desc("Dump graphs for each function/round in the compilation unit."),
107 cl::init(false), cl::Hidden);
108#endif
109
110namespace {
111
112///
113/// PBQP based allocators solve the register allocation problem by mapping
114/// register allocation problems to Partitioned Boolean Quadratic
115/// Programming problems.
116class RegAllocPBQP : public MachineFunctionPass {
117public:
118 static char ID;
119
120 /// Construct a PBQP register allocator.
121 RegAllocPBQP(char *cPassID = nullptr)
122 : MachineFunctionPass(ID), customPassID(cPassID) {
123 initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
124 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
125 initializeLiveStacksPass(*PassRegistry::getPassRegistry());
126 initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
127 }
128
129 /// Return the pass name.
130 StringRef getPassName() const override { return "PBQP Register Allocator"; }
131
132 /// PBQP analysis usage.
133 void getAnalysisUsage(AnalysisUsage &au) const override;
134
135 /// Perform register allocation
136 bool runOnMachineFunction(MachineFunction &MF) override;
137
138 MachineFunctionProperties getRequiredProperties() const override {
139 return MachineFunctionProperties().set(
140 MachineFunctionProperties::Property::NoPHIs);
141 }
142
143private:
144 using LI2NodeMap = std::map<const LiveInterval *, unsigned>;
145 using Node2LIMap = std::vector<const LiveInterval *>;
146 using AllowedSet = std::vector<unsigned>;
147 using AllowedSetMap = std::vector<AllowedSet>;
148 using RegPair = std::pair<unsigned, unsigned>;
149 using CoalesceMap = std::map<RegPair, PBQP::PBQPNum>;
150 using RegSet = std::set<unsigned>;
151
152 char *customPassID;
153
154 RegSet VRegsToAlloc, EmptyIntervalVRegs;
155
156 /// Inst which is a def of an original reg and whose defs are already all
157 /// dead after remat is saved in DeadRemats. The deletion of such inst is
158 /// postponed till all the allocations are done, so its remat expr is
159 /// always available for the remat of all the siblings of the original reg.
160 SmallPtrSet<MachineInstr *, 32> DeadRemats;
161
162 /// \brief Finds the initial set of vreg intervals to allocate.
163 void findVRegIntervalsToAlloc(const MachineFunction &MF, LiveIntervals &LIS);
164
165 /// \brief Constructs an initial graph.
166 void initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM, Spiller &VRegSpiller);
167
168 /// \brief Spill the given VReg.
169 void spillVReg(unsigned VReg, SmallVectorImpl<unsigned> &NewIntervals,
170 MachineFunction &MF, LiveIntervals &LIS, VirtRegMap &VRM,
171 Spiller &VRegSpiller);
172
173 /// \brief Given a solved PBQP problem maps this solution back to a register
174 /// assignment.
175 bool mapPBQPToRegAlloc(const PBQPRAGraph &G,
176 const PBQP::Solution &Solution,
177 VirtRegMap &VRM,
178 Spiller &VRegSpiller);
179
180 /// \brief Postprocessing before final spilling. Sets basic block "live in"
181 /// variables.
182 void finalizeAlloc(MachineFunction &MF, LiveIntervals &LIS,
183 VirtRegMap &VRM) const;
184
185 void postOptimization(Spiller &VRegSpiller, LiveIntervals &LIS);
186};
187
188char RegAllocPBQP::ID = 0;
189
190/// @brief Set spill costs for each node in the PBQP reg-alloc graph.
191class SpillCosts : public PBQPRAConstraint {
192public:
193 void apply(PBQPRAGraph &G) override {
194 LiveIntervals &LIS = G.getMetadata().LIS;
195
196 // A minimum spill costs, so that register constraints can can be set
197 // without normalization in the [0.0:MinSpillCost( interval.
198 const PBQP::PBQPNum MinSpillCost = 10.0;
199
200 for (auto NId : G.nodeIds()) {
201 PBQP::PBQPNum SpillCost =
202 LIS.getInterval(G.getNodeMetadata(NId).getVReg()).weight;
203 if (SpillCost == 0.0)
204 SpillCost = std::numeric_limits<PBQP::PBQPNum>::min();
205 else
206 SpillCost += MinSpillCost;
207 PBQPRAGraph::RawVector NodeCosts(G.getNodeCosts(NId));
208 NodeCosts[PBQP::RegAlloc::getSpillOptionIdx()] = SpillCost;
209 G.setNodeCosts(NId, std::move(NodeCosts));
210 }
211 }
212};
213
214/// @brief Add interference edges between overlapping vregs.
215class Interference : public PBQPRAConstraint {
216private:
217 using AllowedRegVecPtr = const PBQP::RegAlloc::AllowedRegVector *;
218 using IKey = std::pair<AllowedRegVecPtr, AllowedRegVecPtr>;
219 using IMatrixCache = DenseMap<IKey, PBQPRAGraph::MatrixPtr>;
220 using DisjointAllowedRegsCache = DenseSet<IKey>;
221 using IEdgeKey = std::pair<PBQP::GraphBase::NodeId, PBQP::GraphBase::NodeId>;
222 using IEdgeCache = DenseSet<IEdgeKey>;
223
224 bool haveDisjointAllowedRegs(const PBQPRAGraph &G, PBQPRAGraph::NodeId NId,
225 PBQPRAGraph::NodeId MId,
226 const DisjointAllowedRegsCache &D) const {
227 const auto *NRegs = &G.getNodeMetadata(NId).getAllowedRegs();
228 const auto *MRegs = &G.getNodeMetadata(MId).getAllowedRegs();
229
230 if (NRegs == MRegs)
231 return false;
232
233 if (NRegs < MRegs)
234 return D.count(IKey(NRegs, MRegs)) > 0;
235
236 return D.count(IKey(MRegs, NRegs)) > 0;
237 }
238
239 void setDisjointAllowedRegs(const PBQPRAGraph &G, PBQPRAGraph::NodeId NId,
240 PBQPRAGraph::NodeId MId,
241 DisjointAllowedRegsCache &D) {
242 const auto *NRegs = &G.getNodeMetadata(NId).getAllowedRegs();
243 const auto *MRegs = &G.getNodeMetadata(MId).getAllowedRegs();
244
245 assert(NRegs != MRegs && "AllowedRegs can not be disjoint with itself")(static_cast <bool> (NRegs != MRegs && "AllowedRegs can not be disjoint with itself"
) ? void (0) : __assert_fail ("NRegs != MRegs && \"AllowedRegs can not be disjoint with itself\""
, "/build/llvm-toolchain-snapshot-7~svn326551/lib/CodeGen/RegAllocPBQP.cpp"
, 245, __extension__ __PRETTY_FUNCTION__))
;
246
247 if (NRegs < MRegs)
248 D.insert(IKey(NRegs, MRegs));
249 else
250 D.insert(IKey(MRegs, NRegs));
251 }
252
253 // Holds (Interval, CurrentSegmentID, and NodeId). The first two are required
254 // for the fast interference graph construction algorithm. The last is there
255 // to save us from looking up node ids via the VRegToNode map in the graph
256 // metadata.
257 using IntervalInfo =
258 std::tuple<LiveInterval*, size_t, PBQP::GraphBase::NodeId>;
259
260 static SlotIndex getStartPoint(const IntervalInfo &I) {
261 return std::get<0>(I)->segments[std::get<1>(I)].start;
262 }
263
264 static SlotIndex getEndPoint(const IntervalInfo &I) {
265 return std::get<0>(I)->segments[std::get<1>(I)].end;
266 }
267
268 static PBQP::GraphBase::NodeId getNodeId(const IntervalInfo &I) {
269 return std::get<2>(I);
270 }
271
272 static bool lowestStartPoint(const IntervalInfo &I1,
273 const IntervalInfo &I2) {
274 // Condition reversed because priority queue has the *highest* element at
275 // the front, rather than the lowest.
276 return getStartPoint(I1) > getStartPoint(I2);
277 }
278
279 static bool lowestEndPoint(const IntervalInfo &I1,
280 const IntervalInfo &I2) {
281 SlotIndex E1 = getEndPoint(I1);
282 SlotIndex E2 = getEndPoint(I2);
283
284 if (E1 < E2)
285 return true;
286
287 if (E1 > E2)
288 return false;
289
290 // If two intervals end at the same point, we need a way to break the tie or
291 // the set will assume they're actually equal and refuse to insert a
292 // "duplicate". Just compare the vregs - fast and guaranteed unique.
293 return std::get<0>(I1)->reg < std::get<0>(I2)->reg;
294 }
295
296 static bool isAtLastSegment(const IntervalInfo &I) {
297 return std::get<1>(I) == std::get<0>(I)->size() - 1;
298 }
299
300 static IntervalInfo nextSegment(const IntervalInfo &I) {
301 return std::make_tuple(std::get<0>(I), std::get<1>(I) + 1, std::get<2>(I));
302 }
303
304public:
305 void apply(PBQPRAGraph &G) override {
306 // The following is loosely based on the linear scan algorithm introduced in
307 // "Linear Scan Register Allocation" by Poletto and Sarkar. This version
308 // isn't linear, because the size of the active set isn't bound by the
309 // number of registers, but rather the size of the largest clique in the
310 // graph. Still, we expect this to be better than N^2.
311 LiveIntervals &LIS = G.getMetadata().LIS;
312
313 // Interferenc matrices are incredibly regular - they're only a function of
314 // the allowed sets, so we cache them to avoid the overhead of constructing
315 // and uniquing them.
316 IMatrixCache C;
317
318 // Finding an edge is expensive in the worst case (O(max_clique(G))). So
319 // cache locally edges we have already seen.
320 IEdgeCache EC;
321
322 // Cache known disjoint allowed registers pairs
323 DisjointAllowedRegsCache D;
324
325 using IntervalSet = std::set<IntervalInfo, decltype(&lowestEndPoint)>;
326 using IntervalQueue =
327 std::priority_queue<IntervalInfo, std::vector<IntervalInfo>,
328 decltype(&lowestStartPoint)>;
329 IntervalSet Active(lowestEndPoint);
330 IntervalQueue Inactive(lowestStartPoint);
331
332 // Start by building the inactive set.
333 for (auto NId : G.nodeIds()) {
334 unsigned VReg = G.getNodeMetadata(NId).getVReg();
335 LiveInterval &LI = LIS.getInterval(VReg);
336 assert(!LI.empty() && "PBQP graph contains node for empty interval")(static_cast <bool> (!LI.empty() && "PBQP graph contains node for empty interval"
) ? void (0) : __assert_fail ("!LI.empty() && \"PBQP graph contains node for empty interval\""
, "/build/llvm-toolchain-snapshot-7~svn326551/lib/CodeGen/RegAllocPBQP.cpp"
, 336, __extension__ __PRETTY_FUNCTION__))
;
337 Inactive.push(std::make_tuple(&LI, 0, NId));
338 }
339
340 while (!Inactive.empty()) {
341 // Tentatively grab the "next" interval - this choice may be overriden
342 // below.
343 IntervalInfo Cur = Inactive.top();
344
345 // Retire any active intervals that end before Cur starts.
346 IntervalSet::iterator RetireItr = Active.begin();
347 while (RetireItr != Active.end() &&
348 (getEndPoint(*RetireItr) <= getStartPoint(Cur))) {
349 // If this interval has subsequent segments, add the next one to the
350 // inactive list.
351 if (!isAtLastSegment(*RetireItr))
352 Inactive.push(nextSegment(*RetireItr));
353
354 ++RetireItr;
355 }
356 Active.erase(Active.begin(), RetireItr);
357
358 // One of the newly retired segments may actually start before the
359 // Cur segment, so re-grab the front of the inactive list.
360 Cur = Inactive.top();
361 Inactive.pop();
362
363 // At this point we know that Cur overlaps all active intervals. Add the
364 // interference edges.
365 PBQP::GraphBase::NodeId NId = getNodeId(Cur);
366 for (const auto &A : Active) {
367 PBQP::GraphBase::NodeId MId = getNodeId(A);
368
369 // Do not add an edge when the nodes' allowed registers do not
370 // intersect: there is obviously no interference.
371 if (haveDisjointAllowedRegs(G, NId, MId, D))
372 continue;
373
374 // Check that we haven't already added this edge
375 IEdgeKey EK(std::min(NId, MId), std::max(NId, MId));
376 if (EC.count(EK))
377 continue;
378
379 // This is a new edge - add it to the graph.
380 if (!createInterferenceEdge(G, NId, MId, C))
381 setDisjointAllowedRegs(G, NId, MId, D);
382 else
383 EC.insert(EK);
384 }
385
386 // Finally, add Cur to the Active set.
387 Active.insert(Cur);
388 }
389 }
390
391private:
392 // Create an Interference edge and add it to the graph, unless it is
393 // a null matrix, meaning the nodes' allowed registers do not have any
394 // interference. This case occurs frequently between integer and floating
395 // point registers for example.
396 // return true iff both nodes interferes.
397 bool createInterferenceEdge(PBQPRAGraph &G,
398 PBQPRAGraph::NodeId NId, PBQPRAGraph::NodeId MId,
399 IMatrixCache &C) {
400 const TargetRegisterInfo &TRI =
401 *G.getMetadata().MF.getSubtarget().getRegisterInfo();
402 const auto &NRegs = G.getNodeMetadata(NId).getAllowedRegs();
403 const auto &MRegs = G.getNodeMetadata(MId).getAllowedRegs();
404
405 // Try looking the edge costs up in the IMatrixCache first.
406 IKey K(&NRegs, &MRegs);
407 IMatrixCache::iterator I = C.find(K);
408 if (I != C.end()) {
409 G.addEdgeBypassingCostAllocator(NId, MId, I->second);
410 return true;
411 }
412
413 PBQPRAGraph::RawMatrix M(NRegs.size() + 1, MRegs.size() + 1, 0);
414 bool NodesInterfere = false;
415 for (unsigned I = 0; I != NRegs.size(); ++I) {
416 unsigned PRegN = NRegs[I];
417 for (unsigned J = 0; J != MRegs.size(); ++J) {
418 unsigned PRegM = MRegs[J];
419 if (TRI.regsOverlap(PRegN, PRegM)) {
420 M[I + 1][J + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity();
421 NodesInterfere = true;
422 }
423 }
424 }
425
426 if (!NodesInterfere)
427 return false;
428
429 PBQPRAGraph::EdgeId EId = G.addEdge(NId, MId, std::move(M));
430 C[K] = G.getEdgeCostsPtr(EId);
431
432 return true;
433 }
434};
435
436class Coalescing : public PBQPRAConstraint {
437public:
438 void apply(PBQPRAGraph &G) override {
439 MachineFunction &MF = G.getMetadata().MF;
440 MachineBlockFrequencyInfo &MBFI = G.getMetadata().MBFI;
441 CoalescerPair CP(*MF.getSubtarget().getRegisterInfo());
442
443 // Scan the machine function and add a coalescing cost whenever CoalescerPair
444 // gives the Ok.
445 for (const auto &MBB : MF) {
446 for (const auto &MI : MBB) {
447 // Skip not-coalescable or already coalesced copies.
448 if (!CP.setRegisters(&MI) || CP.getSrcReg() == CP.getDstReg())
449 continue;
450
451 unsigned DstReg = CP.getDstReg();
452 unsigned SrcReg = CP.getSrcReg();
453
454 const float Scale = 1.0f / MBFI.getEntryFreq();
455 PBQP::PBQPNum CBenefit = MBFI.getBlockFreq(&MBB).getFrequency() * Scale;
456
457 if (CP.isPhys()) {
458 if (!MF.getRegInfo().isAllocatable(DstReg))
459 continue;
460
461 PBQPRAGraph::NodeId NId = G.getMetadata().getNodeIdForVReg(SrcReg);
462
463 const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed =
464 G.getNodeMetadata(NId).getAllowedRegs();
465
466 unsigned PRegOpt = 0;
467 while (PRegOpt < Allowed.size() && Allowed[PRegOpt] != DstReg)
468 ++PRegOpt;
469
470 if (PRegOpt < Allowed.size()) {
471 PBQPRAGraph::RawVector NewCosts(G.getNodeCosts(NId));
472 NewCosts[PRegOpt + 1] -= CBenefit;
473 G.setNodeCosts(NId, std::move(NewCosts));
474 }
475 } else {
476 PBQPRAGraph::NodeId N1Id = G.getMetadata().getNodeIdForVReg(DstReg);
477 PBQPRAGraph::NodeId N2Id = G.getMetadata().getNodeIdForVReg(SrcReg);
478 const PBQPRAGraph::NodeMetadata::AllowedRegVector *Allowed1 =
479 &G.getNodeMetadata(N1Id).getAllowedRegs();
480 const PBQPRAGraph::NodeMetadata::AllowedRegVector *Allowed2 =
481 &G.getNodeMetadata(N2Id).getAllowedRegs();
482
483 PBQPRAGraph::EdgeId EId = G.findEdge(N1Id, N2Id);
484 if (EId == G.invalidEdgeId()) {
485 PBQPRAGraph::RawMatrix Costs(Allowed1->size() + 1,
486 Allowed2->size() + 1, 0);
487 addVirtRegCoalesce(Costs, *Allowed1, *Allowed2, CBenefit);
488 G.addEdge(N1Id, N2Id, std::move(Costs));
489 } else {
490 if (G.getEdgeNode1Id(EId) == N2Id) {
491 std::swap(N1Id, N2Id);
492 std::swap(Allowed1, Allowed2);
493 }
494 PBQPRAGraph::RawMatrix Costs(G.getEdgeCosts(EId));
495 addVirtRegCoalesce(Costs, *Allowed1, *Allowed2, CBenefit);
496 G.updateEdgeCosts(EId, std::move(Costs));
497 }
498 }
499 }
500 }
501 }
502
503private:
504 void addVirtRegCoalesce(
505 PBQPRAGraph::RawMatrix &CostMat,
506 const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed1,
507 const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed2,
508 PBQP::PBQPNum Benefit) {
509 assert(CostMat.getRows() == Allowed1.size() + 1 && "Size mismatch.")(static_cast <bool> (CostMat.getRows() == Allowed1.size
() + 1 && "Size mismatch.") ? void (0) : __assert_fail
("CostMat.getRows() == Allowed1.size() + 1 && \"Size mismatch.\""
, "/build/llvm-toolchain-snapshot-7~svn326551/lib/CodeGen/RegAllocPBQP.cpp"
, 509, __extension__ __PRETTY_FUNCTION__))
;
510 assert(CostMat.getCols() == Allowed2.size() + 1 && "Size mismatch.")(static_cast <bool> (CostMat.getCols() == Allowed2.size
() + 1 && "Size mismatch.") ? void (0) : __assert_fail
("CostMat.getCols() == Allowed2.size() + 1 && \"Size mismatch.\""
, "/build/llvm-toolchain-snapshot-7~svn326551/lib/CodeGen/RegAllocPBQP.cpp"
, 510, __extension__ __PRETTY_FUNCTION__))
;
511 for (unsigned I = 0; I != Allowed1.size(); ++I) {
512 unsigned PReg1 = Allowed1[I];
513 for (unsigned J = 0; J != Allowed2.size(); ++J) {
514 unsigned PReg2 = Allowed2[J];
515 if (PReg1 == PReg2)
516 CostMat[I + 1][J + 1] -= Benefit;
517 }
518 }
519 }
520};
521
522} // end anonymous namespace
523
524// Out-of-line destructor/anchor for PBQPRAConstraint.
525PBQPRAConstraint::~PBQPRAConstraint() = default;
526
527void PBQPRAConstraint::anchor() {}
528
529void PBQPRAConstraintList::anchor() {}
530
531void RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const {
532 au.setPreservesCFG();
533 au.addRequired<AAResultsWrapperPass>();
534 au.addPreserved<AAResultsWrapperPass>();
535 au.addRequired<SlotIndexes>();
536 au.addPreserved<SlotIndexes>();
537 au.addRequired<LiveIntervals>();
538 au.addPreserved<LiveIntervals>();
539 //au.addRequiredID(SplitCriticalEdgesID);
540 if (customPassID)
541 au.addRequiredID(*customPassID);
542 au.addRequired<LiveStacks>();
543 au.addPreserved<LiveStacks>();
544 au.addRequired<MachineBlockFrequencyInfo>();
545 au.addPreserved<MachineBlockFrequencyInfo>();
546 au.addRequired<MachineLoopInfo>();
547 au.addPreserved<MachineLoopInfo>();
548 au.addRequired<MachineDominatorTree>();
549 au.addPreserved<MachineDominatorTree>();
550 au.addRequired<VirtRegMap>();
551 au.addPreserved<VirtRegMap>();
552 MachineFunctionPass::getAnalysisUsage(au);
553}
554
555void RegAllocPBQP::findVRegIntervalsToAlloc(const MachineFunction &MF,
556 LiveIntervals &LIS) {
557 const MachineRegisterInfo &MRI = MF.getRegInfo();
558
559 // Iterate over all live ranges.
560 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
561 unsigned Reg = TargetRegisterInfo::index2VirtReg(I);
562 if (MRI.reg_nodbg_empty(Reg))
563 continue;
564 VRegsToAlloc.insert(Reg);
565 }
566}
567
568static bool isACalleeSavedRegister(unsigned reg, const TargetRegisterInfo &TRI,
569 const MachineFunction &MF) {
570 const MCPhysReg *CSR = MF.getRegInfo().getCalleeSavedRegs();
571 for (unsigned i = 0; CSR[i] != 0; ++i)
572 if (TRI.regsOverlap(reg, CSR[i]))
573 return true;
574 return false;
575}
576
577void RegAllocPBQP::initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM,
578 Spiller &VRegSpiller) {
579 MachineFunction &MF = G.getMetadata().MF;
580
581 LiveIntervals &LIS = G.getMetadata().LIS;
582 const MachineRegisterInfo &MRI = G.getMetadata().MF.getRegInfo();
583 const TargetRegisterInfo &TRI =
584 *G.getMetadata().MF.getSubtarget().getRegisterInfo();
585
586 std::vector<unsigned> Worklist(VRegsToAlloc.begin(), VRegsToAlloc.end());
587
588 std::map<unsigned, std::vector<unsigned>> VRegAllowedMap;
589
590 while (!Worklist.empty()) {
591 unsigned VReg = Worklist.back();
592 Worklist.pop_back();
593
594 LiveInterval &VRegLI = LIS.getInterval(VReg);
595
596 // If this is an empty interval move it to the EmptyIntervalVRegs set then
597 // continue.
598 if (VRegLI.empty()) {
599 EmptyIntervalVRegs.insert(VRegLI.reg);
600 VRegsToAlloc.erase(VRegLI.reg);
601 continue;
602 }
603
604 const TargetRegisterClass *TRC = MRI.getRegClass(VReg);
605
606 // Record any overlaps with regmask operands.
607 BitVector RegMaskOverlaps;
608 LIS.checkRegMaskInterference(VRegLI, RegMaskOverlaps);
609
610 // Compute an initial allowed set for the current vreg.
611 std::vector<unsigned> VRegAllowed;
612 ArrayRef<MCPhysReg> RawPRegOrder = TRC->getRawAllocationOrder(MF);
613 for (unsigned I = 0; I != RawPRegOrder.size(); ++I) {
614 unsigned PReg = RawPRegOrder[I];
615 if (MRI.isReserved(PReg))
616 continue;
617
618 // vregLI crosses a regmask operand that clobbers preg.
619 if (!RegMaskOverlaps.empty() && !RegMaskOverlaps.test(PReg))
620 continue;
621
622 // vregLI overlaps fixed regunit interference.
623 bool Interference = false;
624 for (MCRegUnitIterator Units(PReg, &TRI); Units.isValid(); ++Units) {
625 if (VRegLI.overlaps(LIS.getRegUnit(*Units))) {
626 Interference = true;
627 break;
628 }
629 }
630 if (Interference)
631 continue;
632
633 // preg is usable for this virtual register.
634 VRegAllowed.push_back(PReg);
635 }
636
637 // Check for vregs that have no allowed registers. These should be
638 // pre-spilled and the new vregs added to the worklist.
639 if (VRegAllowed.empty()) {
640 SmallVector<unsigned, 8> NewVRegs;
641 spillVReg(VReg, NewVRegs, MF, LIS, VRM, VRegSpiller);
642 Worklist.insert(Worklist.end(), NewVRegs.begin(), NewVRegs.end());
643 continue;
644 } else
645 VRegAllowedMap[VReg] = std::move(VRegAllowed);
646 }
647
648 for (auto &KV : VRegAllowedMap) {
649 auto VReg = KV.first;
650
651 // Move empty intervals to the EmptyIntervalVReg set.
652 if (LIS.getInterval(VReg).empty()) {
653 EmptyIntervalVRegs.insert(VReg);
654 VRegsToAlloc.erase(VReg);
655 continue;
656 }
657
658 auto &VRegAllowed = KV.second;
659
660 PBQPRAGraph::RawVector NodeCosts(VRegAllowed.size() + 1, 0);
661
662 // Tweak cost of callee saved registers, as using then force spilling and
663 // restoring them. This would only happen in the prologue / epilogue though.
664 for (unsigned i = 0; i != VRegAllowed.size(); ++i)
665 if (isACalleeSavedRegister(VRegAllowed[i], TRI, MF))
666 NodeCosts[1 + i] += 1.0;
667
668 PBQPRAGraph::NodeId NId = G.addNode(std::move(NodeCosts));
669 G.getNodeMetadata(NId).setVReg(VReg);
670 G.getNodeMetadata(NId).setAllowedRegs(
671 G.getMetadata().getAllowedRegs(std::move(VRegAllowed)));
672 G.getMetadata().setNodeIdForVReg(VReg, NId);
673 }
674}
675
676void RegAllocPBQP::spillVReg(unsigned VReg,
677 SmallVectorImpl<unsigned> &NewIntervals,
678 MachineFunction &MF, LiveIntervals &LIS,
679 VirtRegMap &VRM, Spiller &VRegSpiller) {
680 VRegsToAlloc.erase(VReg);
681 LiveRangeEdit LRE(&LIS.getInterval(VReg), NewIntervals, MF, LIS, &VRM,
682 nullptr, &DeadRemats);
683 VRegSpiller.spill(LRE);
684
685 const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
686 (void)TRI;
687 DEBUG(dbgs() << "VREG " << printReg(VReg, &TRI) << " -> SPILLED (Cost: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "VREG " << printReg(VReg
, &TRI) << " -> SPILLED (Cost: " << LRE.getParent
().weight << ", New vregs: "; } } while (false)
688 << LRE.getParent().weight << ", New vregs: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "VREG " << printReg(VReg
, &TRI) << " -> SPILLED (Cost: " << LRE.getParent
().weight << ", New vregs: "; } } while (false)
;
689
690 // Copy any newly inserted live intervals into the list of regs to
691 // allocate.
692 for (LiveRangeEdit::iterator I = LRE.begin(), E = LRE.end();
693 I != E; ++I) {
694 const LiveInterval &LI = LIS.getInterval(*I);
695 assert(!LI.empty() && "Empty spill range.")(static_cast <bool> (!LI.empty() && "Empty spill range."
) ? void (0) : __assert_fail ("!LI.empty() && \"Empty spill range.\""
, "/build/llvm-toolchain-snapshot-7~svn326551/lib/CodeGen/RegAllocPBQP.cpp"
, 695, __extension__ __PRETTY_FUNCTION__))
;
696 DEBUG(dbgs() << printReg(LI.reg, &TRI) << " ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << printReg(LI.reg, &TRI) <<
" "; } } while (false)
;
697 VRegsToAlloc.insert(LI.reg);
698 }
699
700 DEBUG(dbgs() << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << ")\n"; } } while (false)
;
701}
702
703bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAGraph &G,
704 const PBQP::Solution &Solution,
705 VirtRegMap &VRM,
706 Spiller &VRegSpiller) {
707 MachineFunction &MF = G.getMetadata().MF;
708 LiveIntervals &LIS = G.getMetadata().LIS;
709 const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
710 (void)TRI;
711
712 // Set to true if we have any spills
713 bool AnotherRoundNeeded = false;
714
715 // Clear the existing allocation.
716 VRM.clearAllVirt();
717
718 // Iterate over the nodes mapping the PBQP solution to a register
719 // assignment.
720 for (auto NId : G.nodeIds()) {
721 unsigned VReg = G.getNodeMetadata(NId).getVReg();
722 unsigned AllocOption = Solution.getSelection(NId);
723
724 if (AllocOption != PBQP::RegAlloc::getSpillOptionIdx()) {
725 unsigned PReg = G.getNodeMetadata(NId).getAllowedRegs()[AllocOption - 1];
726 DEBUG(dbgs() << "VREG " << printReg(VReg, &TRI) << " -> "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "VREG " << printReg(VReg
, &TRI) << " -> " << TRI.getName(PReg) <<
"\n"; } } while (false)
727 << TRI.getName(PReg) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "VREG " << printReg(VReg
, &TRI) << " -> " << TRI.getName(PReg) <<
"\n"; } } while (false)
;
728 assert(PReg != 0 && "Invalid preg selected.")(static_cast <bool> (PReg != 0 && "Invalid preg selected."
) ? void (0) : __assert_fail ("PReg != 0 && \"Invalid preg selected.\""
, "/build/llvm-toolchain-snapshot-7~svn326551/lib/CodeGen/RegAllocPBQP.cpp"
, 728, __extension__ __PRETTY_FUNCTION__))
;
729 VRM.assignVirt2Phys(VReg, PReg);
730 } else {
731 // Spill VReg. If this introduces new intervals we'll need another round
732 // of allocation.
733 SmallVector<unsigned, 8> NewVRegs;
734 spillVReg(VReg, NewVRegs, MF, LIS, VRM, VRegSpiller);
735 AnotherRoundNeeded |= !NewVRegs.empty();
736 }
737 }
738
739 return !AnotherRoundNeeded;
740}
741
742void RegAllocPBQP::finalizeAlloc(MachineFunction &MF,
743 LiveIntervals &LIS,
744 VirtRegMap &VRM) const {
745 MachineRegisterInfo &MRI = MF.getRegInfo();
746
747 // First allocate registers for the empty intervals.
748 for (RegSet::const_iterator
749 I = EmptyIntervalVRegs.begin(), E = EmptyIntervalVRegs.end();
750 I != E; ++I) {
751 LiveInterval &LI = LIS.getInterval(*I);
752
753 unsigned PReg = MRI.getSimpleHint(LI.reg);
754
755 if (PReg == 0) {
756 const TargetRegisterClass &RC = *MRI.getRegClass(LI.reg);
757 const ArrayRef<MCPhysReg> RawPRegOrder = RC.getRawAllocationOrder(MF);
758 for (unsigned CandidateReg : RawPRegOrder) {
759 if (!VRM.getRegInfo().isReserved(CandidateReg)) {
760 PReg = CandidateReg;
761 break;
762 }
763 }
764 assert(PReg &&(static_cast <bool> (PReg && "No un-reserved physical registers in this register class"
) ? void (0) : __assert_fail ("PReg && \"No un-reserved physical registers in this register class\""
, "/build/llvm-toolchain-snapshot-7~svn326551/lib/CodeGen/RegAllocPBQP.cpp"
, 765, __extension__ __PRETTY_FUNCTION__))
765 "No un-reserved physical registers in this register class")(static_cast <bool> (PReg && "No un-reserved physical registers in this register class"
) ? void (0) : __assert_fail ("PReg && \"No un-reserved physical registers in this register class\""
, "/build/llvm-toolchain-snapshot-7~svn326551/lib/CodeGen/RegAllocPBQP.cpp"
, 765, __extension__ __PRETTY_FUNCTION__))
;
766 }
767
768 VRM.assignVirt2Phys(LI.reg, PReg);
769 }
770}
771
772void RegAllocPBQP::postOptimization(Spiller &VRegSpiller, LiveIntervals &LIS) {
773 VRegSpiller.postOptimization();
774 /// Remove dead defs because of rematerialization.
775 for (auto DeadInst : DeadRemats) {
776 LIS.RemoveMachineInstrFromMaps(*DeadInst);
777 DeadInst->eraseFromParent();
778 }
779 DeadRemats.clear();
780}
781
782static inline float normalizePBQPSpillWeight(float UseDefFreq, unsigned Size,
783 unsigned NumInstr) {
784 // All intervals have a spill weight that is mostly proportional to the number
785 // of uses, with uses in loops having a bigger weight.
786 return NumInstr * normalizeSpillWeight(UseDefFreq, Size, 1);
787}
788
789bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) {
790 LiveIntervals &LIS = getAnalysis<LiveIntervals>();
791 MachineBlockFrequencyInfo &MBFI =
792 getAnalysis<MachineBlockFrequencyInfo>();
793
794 VirtRegMap &VRM = getAnalysis<VirtRegMap>();
795
796 calculateSpillWeightsAndHints(LIS, MF, &VRM, getAnalysis<MachineLoopInfo>(),
797 MBFI, normalizePBQPSpillWeight);
798
799 std::unique_ptr<Spiller> VRegSpiller(createInlineSpiller(*this, MF, VRM));
800
801 MF.getRegInfo().freezeReservedRegs(MF);
802
803 DEBUG(dbgs() << "PBQP Register Allocating for " << MF.getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "PBQP Register Allocating for "
<< MF.getName() << "\n"; } } while (false)
;
804
805 // Allocator main loop:
806 //
807 // * Map current regalloc problem to a PBQP problem
808 // * Solve the PBQP problem
809 // * Map the solution back to a register allocation
810 // * Spill if necessary
811 //
812 // This process is continued till no more spills are generated.
813
814 // Find the vreg intervals in need of allocation.
815 findVRegIntervalsToAlloc(MF, LIS);
816
817#ifndef NDEBUG
818 const Function &F = MF.getFunction();
819 std::string FullyQualifiedName =
820 F.getParent()->getModuleIdentifier() + "." + F.getName().str();
821#endif
822
823 // If there are non-empty intervals allocate them using pbqp.
824 if (!VRegsToAlloc.empty()) {
825 const TargetSubtargetInfo &Subtarget = MF.getSubtarget();
826 std::unique_ptr<PBQPRAConstraintList> ConstraintsRoot =
827 llvm::make_unique<PBQPRAConstraintList>();
828 ConstraintsRoot->addConstraint(llvm::make_unique<SpillCosts>());
829 ConstraintsRoot->addConstraint(llvm::make_unique<Interference>());
830 if (PBQPCoalescing)
831 ConstraintsRoot->addConstraint(llvm::make_unique<Coalescing>());
832 ConstraintsRoot->addConstraint(Subtarget.getCustomPBQPConstraints());
833
834 bool PBQPAllocComplete = false;
835 unsigned Round = 0;
836
837 while (!PBQPAllocComplete) {
838 DEBUG(dbgs() << " PBQP Regalloc round " << Round << ":\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << " PBQP Regalloc round " <<
Round << ":\n"; } } while (false)
;
839
840 PBQPRAGraph G(PBQPRAGraph::GraphMetadata(MF, LIS, MBFI));
841 initializeGraph(G, VRM, *VRegSpiller);
842 ConstraintsRoot->apply(G);
843
844#ifndef NDEBUG
845 if (PBQPDumpGraphs) {
846 std::ostringstream RS;
847 RS << Round;
848 std::string GraphFileName = FullyQualifiedName + "." + RS.str() +
849 ".pbqpgraph";
850 std::error_code EC;
851 raw_fd_ostream OS(GraphFileName, EC, sys::fs::F_Text);
852 DEBUG(dbgs() << "Dumping graph for round " << Round << " to \""do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Dumping graph for round " <<
Round << " to \"" << GraphFileName << "\"\n"
; } } while (false)
853 << GraphFileName << "\"\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Dumping graph for round " <<
Round << " to \"" << GraphFileName << "\"\n"
; } } while (false)
;
854 G.dump(OS);
855 }
856#endif
857
858 PBQP::Solution Solution = PBQP::RegAlloc::solve(G);
859 PBQPAllocComplete = mapPBQPToRegAlloc(G, Solution, VRM, *VRegSpiller);
860 ++Round;
861 }
862 }
863
864 // Finalise allocation, allocate empty ranges.
865 finalizeAlloc(MF, LIS, VRM);
866 postOptimization(*VRegSpiller, LIS);
867 VRegsToAlloc.clear();
868 EmptyIntervalVRegs.clear();
869
870 DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << VRM << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Post alloc VirtRegMap:\n" <<
VRM << "\n"; } } while (false)
;
871
872 return true;
873}
874
875/// Create Printable object for node and register info.
876static Printable PrintNodeInfo(PBQP::RegAlloc::PBQPRAGraph::NodeId NId,
877 const PBQP::RegAlloc::PBQPRAGraph &G) {
878 return Printable([NId, &G](raw_ostream &OS) {
879 const MachineRegisterInfo &MRI = G.getMetadata().MF.getRegInfo();
880 const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo();
881 unsigned VReg = G.getNodeMetadata(NId).getVReg();
882 const char *RegClassName = TRI->getRegClassName(MRI.getRegClass(VReg));
883 OS << NId << " (" << RegClassName << ':' << printReg(VReg, TRI) << ')';
884 });
885}
886
887#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
888LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void PBQP::RegAlloc::PBQPRAGraph::dump(raw_ostream &OS) const {
889 for (auto NId : nodeIds()) {
890 const Vector &Costs = getNodeCosts(NId);
891 assert(Costs.getLength() != 0 && "Empty vector in graph.")(static_cast <bool> (Costs.getLength() != 0 && "Empty vector in graph."
) ? void (0) : __assert_fail ("Costs.getLength() != 0 && \"Empty vector in graph.\""
, "/build/llvm-toolchain-snapshot-7~svn326551/lib/CodeGen/RegAllocPBQP.cpp"
, 891, __extension__ __PRETTY_FUNCTION__))
;
892 OS << PrintNodeInfo(NId, *this) << ": " << Costs << '\n';
893 }
894 OS << '\n';
895
896 for (auto EId : edgeIds()) {
897 NodeId N1Id = getEdgeNode1Id(EId);
898 NodeId N2Id = getEdgeNode2Id(EId);
899 assert(N1Id != N2Id && "PBQP graphs should not have self-edges.")(static_cast <bool> (N1Id != N2Id && "PBQP graphs should not have self-edges."
) ? void (0) : __assert_fail ("N1Id != N2Id && \"PBQP graphs should not have self-edges.\""
, "/build/llvm-toolchain-snapshot-7~svn326551/lib/CodeGen/RegAllocPBQP.cpp"
, 899, __extension__ __PRETTY_FUNCTION__))
;
900 const Matrix &M = getEdgeCosts(EId);
901 assert(M.getRows() != 0 && "No rows in matrix.")(static_cast <bool> (M.getRows() != 0 && "No rows in matrix."
) ? void (0) : __assert_fail ("M.getRows() != 0 && \"No rows in matrix.\""
, "/build/llvm-toolchain-snapshot-7~svn326551/lib/CodeGen/RegAllocPBQP.cpp"
, 901, __extension__ __PRETTY_FUNCTION__))
;
902 assert(M.getCols() != 0 && "No cols in matrix.")(static_cast <bool> (M.getCols() != 0 && "No cols in matrix."
) ? void (0) : __assert_fail ("M.getCols() != 0 && \"No cols in matrix.\""
, "/build/llvm-toolchain-snapshot-7~svn326551/lib/CodeGen/RegAllocPBQP.cpp"
, 902, __extension__ __PRETTY_FUNCTION__))
;
903 OS << PrintNodeInfo(N1Id, *this) << ' ' << M.getRows() << " rows / ";
904 OS << PrintNodeInfo(N2Id, *this) << ' ' << M.getCols() << " cols:\n";
905 OS << M << '\n';
906 }
907}
908
909LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void PBQP::RegAlloc::PBQPRAGraph::dump() const {
910 dump(dbgs());
911}
912#endif
913
914void PBQP::RegAlloc::PBQPRAGraph::printDot(raw_ostream &OS) const {
915 OS << "graph {\n";
916 for (auto NId : nodeIds()) {
917 OS << " node" << NId << " [ label=\""
918 << PrintNodeInfo(NId, *this) << "\\n"
919 << getNodeCosts(NId) << "\" ]\n";
920 }
921
922 OS << " edge [ len=" << nodeIds().size() << " ]\n";
923 for (auto EId : edgeIds()) {
924 OS << " node" << getEdgeNode1Id(EId)
925 << " -- node" << getEdgeNode2Id(EId)
926 << " [ label=\"";
927 const Matrix &EdgeCosts = getEdgeCosts(EId);
928 for (unsigned i = 0; i < EdgeCosts.getRows(); ++i) {
1
Loop condition is true. Entering loop body
929 OS << EdgeCosts.getRowAsVector(i) << "\\n";
2
Calling 'Matrix::getRowAsVector'
11
Returned allocated memory
12
Potential leak of memory pointed to by field '_M_head_impl'
930 }
931 OS << "\" ]\n";
932 }
933 OS << "}\n";
934}
935
936FunctionPass *llvm::createPBQPRegisterAllocator(char *customPassID) {
937 return new RegAllocPBQP(customPassID);
938}
939
940FunctionPass* llvm::createDefaultPBQPRegisterAllocator() {
941 return createPBQPRegisterAllocator();
942}

/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h

1//===- Math.h - PBQP Vector and Matrix classes ------------------*- 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#ifndef LLVM_CODEGEN_PBQP_MATH_H
11#define LLVM_CODEGEN_PBQP_MATH_H
12
13#include "llvm/ADT/Hashing.h"
14#include "llvm/ADT/STLExtras.h"
15#include <algorithm>
16#include <cassert>
17#include <functional>
18#include <memory>
19
20namespace llvm {
21namespace PBQP {
22
23using PBQPNum = float;
24
25/// \brief PBQP Vector class.
26class Vector {
27 friend hash_code hash_value(const Vector &);
28
29public:
30 /// \brief Construct a PBQP vector of the given size.
31 explicit Vector(unsigned Length)
32 : Length(Length), Data(llvm::make_unique<PBQPNum []>(Length)) {}
4
Calling 'make_unique'
6
Returned allocated memory
33
34 /// \brief Construct a PBQP vector with initializer.
35 Vector(unsigned Length, PBQPNum InitVal)
36 : Length(Length), Data(llvm::make_unique<PBQPNum []>(Length)) {
37 std::fill(Data.get(), Data.get() + Length, InitVal);
38 }
39
40 /// \brief Copy construct a PBQP vector.
41 Vector(const Vector &V)
42 : Length(V.Length), Data(llvm::make_unique<PBQPNum []>(Length)) {
43 std::copy(V.Data.get(), V.Data.get() + Length, Data.get());
44 }
45
46 /// \brief Move construct a PBQP vector.
47 Vector(Vector &&V)
48 : Length(V.Length), Data(std::move(V.Data)) {
49 V.Length = 0;
50 }
51
52 /// \brief Comparison operator.
53 bool operator==(const Vector &V) const {
54 assert(Length != 0 && Data && "Invalid vector")(static_cast <bool> (Length != 0 && Data &&
"Invalid vector") ? void (0) : __assert_fail ("Length != 0 && Data && \"Invalid vector\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 54, __extension__ __PRETTY_FUNCTION__))
;
55 if (Length != V.Length)
56 return false;
57 return std::equal(Data.get(), Data.get() + Length, V.Data.get());
58 }
59
60 /// \brief Return the length of the vector
61 unsigned getLength() const {
62 assert(Length != 0 && Data && "Invalid vector")(static_cast <bool> (Length != 0 && Data &&
"Invalid vector") ? void (0) : __assert_fail ("Length != 0 && Data && \"Invalid vector\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 62, __extension__ __PRETTY_FUNCTION__))
;
63 return Length;
64 }
65
66 /// \brief Element access.
67 PBQPNum& operator[](unsigned Index) {
68 assert(Length != 0 && Data && "Invalid vector")(static_cast <bool> (Length != 0 && Data &&
"Invalid vector") ? void (0) : __assert_fail ("Length != 0 && Data && \"Invalid vector\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 68, __extension__ __PRETTY_FUNCTION__))
;
69 assert(Index < Length && "Vector element access out of bounds.")(static_cast <bool> (Index < Length && "Vector element access out of bounds."
) ? void (0) : __assert_fail ("Index < Length && \"Vector element access out of bounds.\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 69, __extension__ __PRETTY_FUNCTION__))
;
70 return Data[Index];
71 }
72
73 /// \brief Const element access.
74 const PBQPNum& operator[](unsigned Index) const {
75 assert(Length != 0 && Data && "Invalid vector")(static_cast <bool> (Length != 0 && Data &&
"Invalid vector") ? void (0) : __assert_fail ("Length != 0 && Data && \"Invalid vector\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 75, __extension__ __PRETTY_FUNCTION__))
;
76 assert(Index < Length && "Vector element access out of bounds.")(static_cast <bool> (Index < Length && "Vector element access out of bounds."
) ? void (0) : __assert_fail ("Index < Length && \"Vector element access out of bounds.\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 76, __extension__ __PRETTY_FUNCTION__))
;
77 return Data[Index];
78 }
79
80 /// \brief Add another vector to this one.
81 Vector& operator+=(const Vector &V) {
82 assert(Length != 0 && Data && "Invalid vector")(static_cast <bool> (Length != 0 && Data &&
"Invalid vector") ? void (0) : __assert_fail ("Length != 0 && Data && \"Invalid vector\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 82, __extension__ __PRETTY_FUNCTION__))
;
83 assert(Length == V.Length && "Vector length mismatch.")(static_cast <bool> (Length == V.Length && "Vector length mismatch."
) ? void (0) : __assert_fail ("Length == V.Length && \"Vector length mismatch.\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 83, __extension__ __PRETTY_FUNCTION__))
;
84 std::transform(Data.get(), Data.get() + Length, V.Data.get(), Data.get(),
85 std::plus<PBQPNum>());
86 return *this;
87 }
88
89 /// \brief Returns the index of the minimum value in this vector
90 unsigned minIndex() const {
91 assert(Length != 0 && Data && "Invalid vector")(static_cast <bool> (Length != 0 && Data &&
"Invalid vector") ? void (0) : __assert_fail ("Length != 0 && Data && \"Invalid vector\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 91, __extension__ __PRETTY_FUNCTION__))
;
92 return std::min_element(Data.get(), Data.get() + Length) - Data.get();
93 }
94
95private:
96 unsigned Length;
97 std::unique_ptr<PBQPNum []> Data;
98};
99
100/// \brief Return a hash_value for the given vector.
101inline hash_code hash_value(const Vector &V) {
102 unsigned *VBegin = reinterpret_cast<unsigned*>(V.Data.get());
103 unsigned *VEnd = reinterpret_cast<unsigned*>(V.Data.get() + V.Length);
104 return hash_combine(V.Length, hash_combine_range(VBegin, VEnd));
105}
106
107/// \brief Output a textual representation of the given vector on the given
108/// output stream.
109template <typename OStream>
110OStream& operator<<(OStream &OS, const Vector &V) {
111 assert((V.getLength() != 0) && "Zero-length vector badness.")(static_cast <bool> ((V.getLength() != 0) && "Zero-length vector badness."
) ? void (0) : __assert_fail ("(V.getLength() != 0) && \"Zero-length vector badness.\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 111, __extension__ __PRETTY_FUNCTION__))
;
112
113 OS << "[ " << V[0];
114 for (unsigned i = 1; i < V.getLength(); ++i)
115 OS << ", " << V[i];
116 OS << " ]";
117
118 return OS;
119}
120
121/// \brief PBQP Matrix class
122class Matrix {
123private:
124 friend hash_code hash_value(const Matrix &);
125
126public:
127 /// \brief Construct a PBQP Matrix with the given dimensions.
128 Matrix(unsigned Rows, unsigned Cols) :
129 Rows(Rows), Cols(Cols), Data(llvm::make_unique<PBQPNum []>(Rows * Cols)) {
130 }
131
132 /// \brief Construct a PBQP Matrix with the given dimensions and initial
133 /// value.
134 Matrix(unsigned Rows, unsigned Cols, PBQPNum InitVal)
135 : Rows(Rows), Cols(Cols),
136 Data(llvm::make_unique<PBQPNum []>(Rows * Cols)) {
137 std::fill(Data.get(), Data.get() + (Rows * Cols), InitVal);
138 }
139
140 /// \brief Copy construct a PBQP matrix.
141 Matrix(const Matrix &M)
142 : Rows(M.Rows), Cols(M.Cols),
143 Data(llvm::make_unique<PBQPNum []>(Rows * Cols)) {
144 std::copy(M.Data.get(), M.Data.get() + (Rows * Cols), Data.get());
145 }
146
147 /// \brief Move construct a PBQP matrix.
148 Matrix(Matrix &&M)
149 : Rows(M.Rows), Cols(M.Cols), Data(std::move(M.Data)) {
150 M.Rows = M.Cols = 0;
151 }
152
153 /// \brief Comparison operator.
154 bool operator==(const Matrix &M) const {
155 assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix")(static_cast <bool> (Rows != 0 && Cols != 0 &&
Data && "Invalid matrix") ? void (0) : __assert_fail
("Rows != 0 && Cols != 0 && Data && \"Invalid matrix\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 155, __extension__ __PRETTY_FUNCTION__))
;
156 if (Rows != M.Rows || Cols != M.Cols)
157 return false;
158 return std::equal(Data.get(), Data.get() + (Rows * Cols), M.Data.get());
159 }
160
161 /// \brief Return the number of rows in this matrix.
162 unsigned getRows() const {
163 assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix")(static_cast <bool> (Rows != 0 && Cols != 0 &&
Data && "Invalid matrix") ? void (0) : __assert_fail
("Rows != 0 && Cols != 0 && Data && \"Invalid matrix\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 163, __extension__ __PRETTY_FUNCTION__))
;
164 return Rows;
165 }
166
167 /// \brief Return the number of cols in this matrix.
168 unsigned getCols() const {
169 assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix")(static_cast <bool> (Rows != 0 && Cols != 0 &&
Data && "Invalid matrix") ? void (0) : __assert_fail
("Rows != 0 && Cols != 0 && Data && \"Invalid matrix\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 169, __extension__ __PRETTY_FUNCTION__))
;
170 return Cols;
171 }
172
173 /// \brief Matrix element access.
174 PBQPNum* operator[](unsigned R) {
175 assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix")(static_cast <bool> (Rows != 0 && Cols != 0 &&
Data && "Invalid matrix") ? void (0) : __assert_fail
("Rows != 0 && Cols != 0 && Data && \"Invalid matrix\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 175, __extension__ __PRETTY_FUNCTION__))
;
176 assert(R < Rows && "Row out of bounds.")(static_cast <bool> (R < Rows && "Row out of bounds."
) ? void (0) : __assert_fail ("R < Rows && \"Row out of bounds.\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 176, __extension__ __PRETTY_FUNCTION__))
;
177 return Data.get() + (R * Cols);
178 }
179
180 /// \brief Matrix element access.
181 const PBQPNum* operator[](unsigned R) const {
182 assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix")(static_cast <bool> (Rows != 0 && Cols != 0 &&
Data && "Invalid matrix") ? void (0) : __assert_fail
("Rows != 0 && Cols != 0 && Data && \"Invalid matrix\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 182, __extension__ __PRETTY_FUNCTION__))
;
183 assert(R < Rows && "Row out of bounds.")(static_cast <bool> (R < Rows && "Row out of bounds."
) ? void (0) : __assert_fail ("R < Rows && \"Row out of bounds.\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 183, __extension__ __PRETTY_FUNCTION__))
;
184 return Data.get() + (R * Cols);
185 }
186
187 /// \brief Returns the given row as a vector.
188 Vector getRowAsVector(unsigned R) const {
189 assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix")(static_cast <bool> (Rows != 0 && Cols != 0 &&
Data && "Invalid matrix") ? void (0) : __assert_fail
("Rows != 0 && Cols != 0 && Data && \"Invalid matrix\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 189, __extension__ __PRETTY_FUNCTION__))
;
190 Vector V(Cols);
3
Calling constructor for 'Vector'
7
Returning from constructor for 'Vector'
191 for (unsigned C = 0; C < Cols; ++C)
8
Loop condition is true. Entering loop body
9
Assuming the condition is false
10
Loop condition is false. Execution continues on line 193
192 V[C] = (*this)[R][C];
193 return V;
194 }
195
196 /// \brief Returns the given column as a vector.
197 Vector getColAsVector(unsigned C) const {
198 assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix")(static_cast <bool> (Rows != 0 && Cols != 0 &&
Data && "Invalid matrix") ? void (0) : __assert_fail
("Rows != 0 && Cols != 0 && Data && \"Invalid matrix\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 198, __extension__ __PRETTY_FUNCTION__))
;
199 Vector V(Rows);
200 for (unsigned R = 0; R < Rows; ++R)
201 V[R] = (*this)[R][C];
202 return V;
203 }
204
205 /// \brief Matrix transpose.
206 Matrix transpose() const {
207 assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix")(static_cast <bool> (Rows != 0 && Cols != 0 &&
Data && "Invalid matrix") ? void (0) : __assert_fail
("Rows != 0 && Cols != 0 && Data && \"Invalid matrix\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 207, __extension__ __PRETTY_FUNCTION__))
;
208 Matrix M(Cols, Rows);
209 for (unsigned r = 0; r < Rows; ++r)
210 for (unsigned c = 0; c < Cols; ++c)
211 M[c][r] = (*this)[r][c];
212 return M;
213 }
214
215 /// \brief Add the given matrix to this one.
216 Matrix& operator+=(const Matrix &M) {
217 assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix")(static_cast <bool> (Rows != 0 && Cols != 0 &&
Data && "Invalid matrix") ? void (0) : __assert_fail
("Rows != 0 && Cols != 0 && Data && \"Invalid matrix\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 217, __extension__ __PRETTY_FUNCTION__))
;
218 assert(Rows == M.Rows && Cols == M.Cols &&(static_cast <bool> (Rows == M.Rows && Cols == M
.Cols && "Matrix dimensions mismatch.") ? void (0) : __assert_fail
("Rows == M.Rows && Cols == M.Cols && \"Matrix dimensions mismatch.\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 219, __extension__ __PRETTY_FUNCTION__))
219 "Matrix dimensions mismatch.")(static_cast <bool> (Rows == M.Rows && Cols == M
.Cols && "Matrix dimensions mismatch.") ? void (0) : __assert_fail
("Rows == M.Rows && Cols == M.Cols && \"Matrix dimensions mismatch.\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 219, __extension__ __PRETTY_FUNCTION__))
;
220 std::transform(Data.get(), Data.get() + (Rows * Cols), M.Data.get(),
221 Data.get(), std::plus<PBQPNum>());
222 return *this;
223 }
224
225 Matrix operator+(const Matrix &M) {
226 assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix")(static_cast <bool> (Rows != 0 && Cols != 0 &&
Data && "Invalid matrix") ? void (0) : __assert_fail
("Rows != 0 && Cols != 0 && Data && \"Invalid matrix\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 226, __extension__ __PRETTY_FUNCTION__))
;
227 Matrix Tmp(*this);
228 Tmp += M;
229 return Tmp;
230 }
231
232private:
233 unsigned Rows, Cols;
234 std::unique_ptr<PBQPNum []> Data;
235};
236
237/// \brief Return a hash_code for the given matrix.
238inline hash_code hash_value(const Matrix &M) {
239 unsigned *MBegin = reinterpret_cast<unsigned*>(M.Data.get());
240 unsigned *MEnd =
241 reinterpret_cast<unsigned*>(M.Data.get() + (M.Rows * M.Cols));
242 return hash_combine(M.Rows, M.Cols, hash_combine_range(MBegin, MEnd));
243}
244
245/// \brief Output a textual representation of the given matrix on the given
246/// output stream.
247template <typename OStream>
248OStream& operator<<(OStream &OS, const Matrix &M) {
249 assert((M.getRows() != 0) && "Zero-row matrix badness.")(static_cast <bool> ((M.getRows() != 0) && "Zero-row matrix badness."
) ? void (0) : __assert_fail ("(M.getRows() != 0) && \"Zero-row matrix badness.\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/CodeGen/PBQP/Math.h"
, 249, __extension__ __PRETTY_FUNCTION__))
;
250 for (unsigned i = 0; i < M.getRows(); ++i)
251 OS << M.getRowAsVector(i) << "\n";
252 return OS;
253}
254
255template <typename Metadata>
256class MDVector : public Vector {
257public:
258 MDVector(const Vector &v) : Vector(v), md(*this) {}
259 MDVector(Vector &&v) : Vector(std::move(v)), md(*this) { }
260
261 const Metadata& getMetadata() const { return md; }
262
263private:
264 Metadata md;
265};
266
267template <typename Metadata>
268inline hash_code hash_value(const MDVector<Metadata> &V) {
269 return hash_value(static_cast<const Vector&>(V));
270}
271
272template <typename Metadata>
273class MDMatrix : public Matrix {
274public:
275 MDMatrix(const Matrix &m) : Matrix(m), md(*this) {}
276 MDMatrix(Matrix &&m) : Matrix(std::move(m)), md(*this) { }
277
278 const Metadata& getMetadata() const { return md; }
279
280private:
281 Metadata md;
282};
283
284template <typename Metadata>
285inline hash_code hash_value(const MDMatrix<Metadata> &M) {
286 return hash_value(static_cast<const Matrix&>(M));
287}
288
289} // end namespace PBQP
290} // end namespace llvm
291
292#endif // LLVM_CODEGEN_PBQP_MATH_H

/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/ADT/STLExtras.h

1//===- llvm/ADT/STLExtras.h - Useful STL related 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 templates that are useful if you are working with the
11// STL at all.
12//
13// No library is required when using these functions.
14//
15//===----------------------------------------------------------------------===//
16
17#ifndef LLVM_ADT_STLEXTRAS_H
18#define LLVM_ADT_STLEXTRAS_H
19
20#include "llvm/ADT/Optional.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/ADT/iterator.h"
23#include "llvm/ADT/iterator_range.h"
24#include "llvm/Support/ErrorHandling.h"
25#include <algorithm>
26#include <cassert>
27#include <cstddef>
28#include <cstdint>
29#include <cstdlib>
30#include <functional>
31#include <initializer_list>
32#include <iterator>
33#include <limits>
34#include <memory>
35#include <tuple>
36#include <type_traits>
37#include <utility>
38
39namespace llvm {
40
41// Only used by compiler if both template types are the same. Useful when
42// using SFINAE to test for the existence of member functions.
43template <typename T, T> struct SameType;
44
45namespace detail {
46
47template <typename RangeT>
48using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
49
50template <typename RangeT>
51using ValueOfRange = typename std::remove_reference<decltype(
52 *std::begin(std::declval<RangeT &>()))>::type;
53
54} // end namespace detail
55
56//===----------------------------------------------------------------------===//
57// Extra additions to <functional>
58//===----------------------------------------------------------------------===//
59
60template <class Ty> struct identity {
61 using argument_type = Ty;
62
63 Ty &operator()(Ty &self) const {
64 return self;
65 }
66 const Ty &operator()(const Ty &self) const {
67 return self;
68 }
69};
70
71template <class Ty> struct less_ptr {
72 bool operator()(const Ty* left, const Ty* right) const {
73 return *left < *right;
74 }
75};
76
77template <class Ty> struct greater_ptr {
78 bool operator()(const Ty* left, const Ty* right) const {
79 return *right < *left;
80 }
81};
82
83/// An efficient, type-erasing, non-owning reference to a callable. This is
84/// intended for use as the type of a function parameter that is not used
85/// after the function in question returns.
86///
87/// This class does not own the callable, so it is not in general safe to store
88/// a function_ref.
89template<typename Fn> class function_ref;
90
91template<typename Ret, typename ...Params>
92class function_ref<Ret(Params...)> {
93 Ret (*callback)(intptr_t callable, Params ...params) = nullptr;
94 intptr_t callable;
95
96 template<typename Callable>
97 static Ret callback_fn(intptr_t callable, Params ...params) {
98 return (*reinterpret_cast<Callable*>(callable))(
99 std::forward<Params>(params)...);
100 }
101
102public:
103 function_ref() = default;
104 function_ref(std::nullptr_t) {}
105
106 template <typename Callable>
107 function_ref(Callable &&callable,
108 typename std::enable_if<
109 !std::is_same<typename std::remove_reference<Callable>::type,
110 function_ref>::value>::type * = nullptr)
111 : callback(callback_fn<typename std::remove_reference<Callable>::type>),
112 callable(reinterpret_cast<intptr_t>(&callable)) {}
113
114 Ret operator()(Params ...params) const {
115 return callback(callable, std::forward<Params>(params)...);
116 }
117
118 operator bool() const { return callback; }
119};
120
121// deleter - Very very very simple method that is used to invoke operator
122// delete on something. It is used like this:
123//
124// for_each(V.begin(), B.end(), deleter<Interval>);
125template <class T>
126inline void deleter(T *Ptr) {
127 delete Ptr;
128}
129
130//===----------------------------------------------------------------------===//
131// Extra additions to <iterator>
132//===----------------------------------------------------------------------===//
133
134namespace adl_detail {
135
136using std::begin;
137
138template <typename ContainerTy>
139auto adl_begin(ContainerTy &&container)
140 -> decltype(begin(std::forward<ContainerTy>(container))) {
141 return begin(std::forward<ContainerTy>(container));
142}
143
144using std::end;
145
146template <typename ContainerTy>
147auto adl_end(ContainerTy &&container)
148 -> decltype(end(std::forward<ContainerTy>(container))) {
149 return end(std::forward<ContainerTy>(container));
150}
151
152using std::swap;
153
154template <typename T>
155void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
156 std::declval<T>()))) {
157 swap(std::forward<T>(lhs), std::forward<T>(rhs));
158}
159
160} // end namespace adl_detail
161
162template <typename ContainerTy>
163auto adl_begin(ContainerTy &&container)
164 -> decltype(adl_detail::adl_begin(std::forward<ContainerTy>(container))) {
165 return adl_detail::adl_begin(std::forward<ContainerTy>(container));
166}
167
168template <typename ContainerTy>
169auto adl_end(ContainerTy &&container)
170 -> decltype(adl_detail::adl_end(std::forward<ContainerTy>(container))) {
171 return adl_detail::adl_end(std::forward<ContainerTy>(container));
172}
173
174template <typename T>
175void adl_swap(T &&lhs, T &&rhs) noexcept(
176 noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {
177 adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));
178}
179
180// mapped_iterator - This is a simple iterator adapter that causes a function to
181// be applied whenever operator* is invoked on the iterator.
182
183template <typename ItTy, typename FuncTy,
184 typename FuncReturnTy =
185 decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
186class mapped_iterator
187 : public iterator_adaptor_base<
188 mapped_iterator<ItTy, FuncTy>, ItTy,
189 typename std::iterator_traits<ItTy>::iterator_category,
190 typename std::remove_reference<FuncReturnTy>::type> {
191public:
192 mapped_iterator(ItTy U, FuncTy F)
193 : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {}
194
195 ItTy getCurrent() { return this->I; }
196
197 FuncReturnTy operator*() { return F(*this->I); }
198
199private:
200 FuncTy F;
201};
202
203// map_iterator - Provide a convenient way to create mapped_iterators, just like
204// make_pair is useful for creating pairs...
205template <class ItTy, class FuncTy>
206inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) {
207 return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
208}
209
210/// Helper to determine if type T has a member called rbegin().
211template <typename Ty> class has_rbegin_impl {
212 using yes = char[1];
213 using no = char[2];
214
215 template <typename Inner>
216 static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);
217
218 template <typename>
219 static no& test(...);
220
221public:
222 static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
223};
224
225/// Metafunction to determine if T& or T has a member called rbegin().
226template <typename Ty>
227struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> {
228};
229
230// Returns an iterator_range over the given container which iterates in reverse.
231// Note that the container must have rbegin()/rend() methods for this to work.
232template <typename ContainerTy>
233auto reverse(ContainerTy &&C,
234 typename std::enable_if<has_rbegin<ContainerTy>::value>::type * =
235 nullptr) -> decltype(make_range(C.rbegin(), C.rend())) {
236 return make_range(C.rbegin(), C.rend());
237}
238
239// Returns a std::reverse_iterator wrapped around the given iterator.
240template <typename IteratorTy>
241std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
242 return std::reverse_iterator<IteratorTy>(It);
243}
244
245// Returns an iterator_range over the given container which iterates in reverse.
246// Note that the container must have begin()/end() methods which return
247// bidirectional iterators for this to work.
248template <typename ContainerTy>
249auto reverse(
250 ContainerTy &&C,
251 typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
252 -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
253 llvm::make_reverse_iterator(std::begin(C)))) {
254 return make_range(llvm::make_reverse_iterator(std::end(C)),
255 llvm::make_reverse_iterator(std::begin(C)));
256}
257
258/// An iterator adaptor that filters the elements of given inner iterators.
259///
260/// The predicate parameter should be a callable object that accepts the wrapped
261/// iterator's reference type and returns a bool. When incrementing or
262/// decrementing the iterator, it will call the predicate on each element and
263/// skip any where it returns false.
264///
265/// \code
266/// int A[] = { 1, 2, 3, 4 };
267/// auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
268/// // R contains { 1, 3 }.
269/// \endcode
270template <typename WrappedIteratorT, typename PredicateT>
271class filter_iterator
272 : public iterator_adaptor_base<
273 filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT,
274 typename std::common_type<
275 std::forward_iterator_tag,
276 typename std::iterator_traits<
277 WrappedIteratorT>::iterator_category>::type> {
278 using BaseT = iterator_adaptor_base<
279 filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT,
280 typename std::common_type<
281 std::forward_iterator_tag,
282 typename std::iterator_traits<WrappedIteratorT>::iterator_category>::
283 type>;
284
285 struct PayloadType {
286 WrappedIteratorT End;
287 PredicateT Pred;
288 };
289
290 Optional<PayloadType> Payload;
291
292 void findNextValid() {
293 assert(Payload && "Payload should be engaged when findNextValid is called")(static_cast <bool> (Payload && "Payload should be engaged when findNextValid is called"
) ? void (0) : __assert_fail ("Payload && \"Payload should be engaged when findNextValid is called\""
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/ADT/STLExtras.h"
, 293, __extension__ __PRETTY_FUNCTION__))
;
294 while (this->I != Payload->End && !Payload->Pred(*this->I))
295 BaseT::operator++();
296 }
297
298 // Construct the begin iterator. The begin iterator requires to know where end
299 // is, so that it can properly stop when it hits end.
300 filter_iterator(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred)
301 : BaseT(std::move(Begin)),
302 Payload(PayloadType{std::move(End), std::move(Pred)}) {
303 findNextValid();
304 }
305
306 // Construct the end iterator. It's not incrementable, so Payload doesn't
307 // have to be engaged.
308 filter_iterator(WrappedIteratorT End) : BaseT(End) {}
309
310public:
311 using BaseT::operator++;
312
313 filter_iterator &operator++() {
314 BaseT::operator++();
315 findNextValid();
316 return *this;
317 }
318
319 template <typename RT, typename PT>
320 friend iterator_range<filter_iterator<detail::IterOfRange<RT>, PT>>
321 make_filter_range(RT &&, PT);
322};
323
324/// Convenience function that takes a range of elements and a predicate,
325/// and return a new filter_iterator range.
326///
327/// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the
328/// lifetime of that temporary is not kept by the returned range object, and the
329/// temporary is going to be dropped on the floor after the make_iterator_range
330/// full expression that contains this function call.
331template <typename RangeT, typename PredicateT>
332iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>>
333make_filter_range(RangeT &&Range, PredicateT Pred) {
334 using FilterIteratorT =
335 filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
336 return make_range(FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
337 std::end(std::forward<RangeT>(Range)),
338 std::move(Pred)),
339 FilterIteratorT(std::end(std::forward<RangeT>(Range))));
340}
341
342// forward declarations required by zip_shortest/zip_first
343template <typename R, typename UnaryPredicate>
344bool all_of(R &&range, UnaryPredicate P);
345
346template <size_t... I> struct index_sequence;
347
348template <class... Ts> struct index_sequence_for;
349
350namespace detail {
351
352using std::declval;
353
354// We have to alias this since inlining the actual type at the usage site
355// in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.
356template<typename... Iters> struct ZipTupleType {
357 using type = std::tuple<decltype(*declval<Iters>())...>;
358};
359
360template <typename ZipType, typename... Iters>
361using zip_traits = iterator_facade_base<
362 ZipType, typename std::common_type<std::bidirectional_iterator_tag,
363 typename std::iterator_traits<
364 Iters>::iterator_category...>::type,
365 // ^ TODO: Implement random access methods.
366 typename ZipTupleType<Iters...>::type,
367 typename std::iterator_traits<typename std::tuple_element<
368 0, std::tuple<Iters...>>::type>::difference_type,
369 // ^ FIXME: This follows boost::make_zip_iterator's assumption that all
370 // inner iterators have the same difference_type. It would fail if, for
371 // instance, the second field's difference_type were non-numeric while the
372 // first is.
373 typename ZipTupleType<Iters...>::type *,
374 typename ZipTupleType<Iters...>::type>;
375
376template <typename ZipType, typename... Iters>
377struct zip_common : public zip_traits<ZipType, Iters...> {
378 using Base = zip_traits<ZipType, Iters...>;
379 using value_type = typename Base::value_type;
380
381 std::tuple<Iters...> iterators;
382
383protected:
384 template <size_t... Ns> value_type deref(index_sequence<Ns...>) const {
385 return value_type(*std::get<Ns>(iterators)...);
386 }
387
388 template <size_t... Ns>
389 decltype(iterators) tup_inc(index_sequence<Ns...>) const {
390 return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
391 }
392
393 template <size_t... Ns>
394 decltype(iterators) tup_dec(index_sequence<Ns...>) const {
395 return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
396 }
397
398public:
399 zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
400
401 value_type operator*() { return deref(index_sequence_for<Iters...>{}); }
402
403 const value_type operator*() const {
404 return deref(index_sequence_for<Iters...>{});
405 }
406
407 ZipType &operator++() {
408 iterators = tup_inc(index_sequence_for<Iters...>{});
409 return *reinterpret_cast<ZipType *>(this);
410 }
411
412 ZipType &operator--() {
413 static_assert(Base::IsBidirectional,
414 "All inner iterators must be at least bidirectional.");
415 iterators = tup_dec(index_sequence_for<Iters...>{});
416 return *reinterpret_cast<ZipType *>(this);
417 }
418};
419
420template <typename... Iters>
421struct zip_first : public zip_common<zip_first<Iters...>, Iters...> {
422 using Base = zip_common<zip_first<Iters...>, Iters...>;
423
424 bool operator==(const zip_first<Iters...> &other) const {
425 return std::get<0>(this->iterators) == std::get<0>(other.iterators);
426 }
427
428 zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
429};
430
431template <typename... Iters>
432class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> {
433 template <size_t... Ns>
434 bool test(const zip_shortest<Iters...> &other, index_sequence<Ns...>) const {
435 return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
436 std::get<Ns>(other.iterators)...},
437 identity<bool>{});
438 }
439
440public:
441 using Base = zip_common<zip_shortest<Iters...>, Iters...>;
442
443 zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
444
445 bool operator==(const zip_shortest<Iters...> &other) const {
446 return !test(other, index_sequence_for<Iters...>{});
447 }
448};
449
450template <template <typename...> class ItType, typename... Args> class zippy {
451public:
452 using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>;
453 using iterator_category = typename iterator::iterator_category;
454 using value_type = typename iterator::value_type;
455 using difference_type = typename iterator::difference_type;
456 using pointer = typename iterator::pointer;
457 using reference = typename iterator::reference;
458
459private:
460 std::tuple<Args...> ts;
461
462 template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const {
463 return iterator(std::begin(std::get<Ns>(ts))...);
464 }
465 template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const {
466 return iterator(std::end(std::get<Ns>(ts))...);
467 }
468
469public:
470 zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
471
472 iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); }
473 iterator end() const { return end_impl(index_sequence_for<Args...>{}); }
474};
475
476} // end namespace detail
477
478/// zip iterator for two or more iteratable types.
479template <typename T, typename U, typename... Args>
480detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u,
481 Args &&... args) {
482 return detail::zippy<detail::zip_shortest, T, U, Args...>(
483 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
484}
485
486/// zip iterator that, for the sake of efficiency, assumes the first iteratee to
487/// be the shortest.
488template <typename T, typename U, typename... Args>
489detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u,
490 Args &&... args) {
491 return detail::zippy<detail::zip_first, T, U, Args...>(
492 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
493}
494
495/// Iterator wrapper that concatenates sequences together.
496///
497/// This can concatenate different iterators, even with different types, into
498/// a single iterator provided the value types of all the concatenated
499/// iterators expose `reference` and `pointer` types that can be converted to
500/// `ValueT &` and `ValueT *` respectively. It doesn't support more
501/// interesting/customized pointer or reference types.
502///
503/// Currently this only supports forward or higher iterator categories as
504/// inputs and always exposes a forward iterator interface.
505template <typename ValueT, typename... IterTs>
506class concat_iterator
507 : public iterator_facade_base<concat_iterator<ValueT, IterTs...>,
508 std::forward_iterator_tag, ValueT> {
509 using BaseT = typename concat_iterator::iterator_facade_base;
510
511 /// We store both the current and end iterators for each concatenated
512 /// sequence in a tuple of pairs.
513 ///
514 /// Note that something like iterator_range seems nice at first here, but the
515 /// range properties are of little benefit and end up getting in the way
516 /// because we need to do mutation on the current iterators.
517 std::tuple<std::pair<IterTs, IterTs>...> IterPairs;
518
519 /// Attempts to increment a specific iterator.
520 ///
521 /// Returns true if it was able to increment the iterator. Returns false if
522 /// the iterator is already at the end iterator.
523 template <size_t Index> bool incrementHelper() {
524 auto &IterPair = std::get<Index>(IterPairs);
525 if (IterPair.first == IterPair.second)
526 return false;
527
528 ++IterPair.first;
529 return true;
530 }
531
532 /// Increments the first non-end iterator.
533 ///
534 /// It is an error to call this with all iterators at the end.
535 template <size_t... Ns> void increment(index_sequence<Ns...>) {
536 // Build a sequence of functions to increment each iterator if possible.
537 bool (concat_iterator::*IncrementHelperFns[])() = {
538 &concat_iterator::incrementHelper<Ns>...};
539
540 // Loop over them, and stop as soon as we succeed at incrementing one.
541 for (auto &IncrementHelperFn : IncrementHelperFns)
542 if ((this->*IncrementHelperFn)())
543 return;
544
545 llvm_unreachable("Attempted to increment an end concat iterator!")::llvm::llvm_unreachable_internal("Attempted to increment an end concat iterator!"
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/ADT/STLExtras.h"
, 545)
;
546 }
547
548 /// Returns null if the specified iterator is at the end. Otherwise,
549 /// dereferences the iterator and returns the address of the resulting
550 /// reference.
551 template <size_t Index> ValueT *getHelper() const {
552 auto &IterPair = std::get<Index>(IterPairs);
553 if (IterPair.first == IterPair.second)
554 return nullptr;
555
556 return &*IterPair.first;
557 }
558
559 /// Finds the first non-end iterator, dereferences, and returns the resulting
560 /// reference.
561 ///
562 /// It is an error to call this with all iterators at the end.
563 template <size_t... Ns> ValueT &get(index_sequence<Ns...>) const {
564 // Build a sequence of functions to get from iterator if possible.
565 ValueT *(concat_iterator::*GetHelperFns[])() const = {
566 &concat_iterator::getHelper<Ns>...};
567
568 // Loop over them, and return the first result we find.
569 for (auto &GetHelperFn : GetHelperFns)
570 if (ValueT *P = (this->*GetHelperFn)())
571 return *P;
572
573 llvm_unreachable("Attempted to get a pointer from an end concat iterator!")::llvm::llvm_unreachable_internal("Attempted to get a pointer from an end concat iterator!"
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/ADT/STLExtras.h"
, 573)
;
574 }
575
576public:
577 /// Constructs an iterator from a squence of ranges.
578 ///
579 /// We need the full range to know how to switch between each of the
580 /// iterators.
581 template <typename... RangeTs>
582 explicit concat_iterator(RangeTs &&... Ranges)
583 : IterPairs({std::begin(Ranges), std::end(Ranges)}...) {}
584
585 using BaseT::operator++;
586
587 concat_iterator &operator++() {
588 increment(index_sequence_for<IterTs...>());
589 return *this;
590 }
591
592 ValueT &operator*() const { return get(index_sequence_for<IterTs...>()); }
593
594 bool operator==(const concat_iterator &RHS) const {
595 return IterPairs == RHS.IterPairs;
596 }
597};
598
599namespace detail {
600
601/// Helper to store a sequence of ranges being concatenated and access them.
602///
603/// This is designed to facilitate providing actual storage when temporaries
604/// are passed into the constructor such that we can use it as part of range
605/// based for loops.
606template <typename ValueT, typename... RangeTs> class concat_range {
607public:
608 using iterator =
609 concat_iterator<ValueT,
610 decltype(std::begin(std::declval<RangeTs &>()))...>;
611
612private:
613 std::tuple<RangeTs...> Ranges;
614
615 template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) {
616 return iterator(std::get<Ns>(Ranges)...);
617 }
618 template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) {
619 return iterator(make_range(std::end(std::get<Ns>(Ranges)),
620 std::end(std::get<Ns>(Ranges)))...);
621 }
622
623public:
624 concat_range(RangeTs &&... Ranges)
625 : Ranges(std::forward<RangeTs>(Ranges)...) {}
626
627 iterator begin() { return begin_impl(index_sequence_for<RangeTs...>{}); }
628 iterator end() { return end_impl(index_sequence_for<RangeTs...>{}); }
629};
630
631} // end namespace detail
632
633/// Concatenated range across two or more ranges.
634///
635/// The desired value type must be explicitly specified.
636template <typename ValueT, typename... RangeTs>
637detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
638 static_assert(sizeof...(RangeTs) > 1,
639 "Need more than one range to concatenate!");
640 return detail::concat_range<ValueT, RangeTs...>(
641 std::forward<RangeTs>(Ranges)...);
642}
643
644//===----------------------------------------------------------------------===//
645// Extra additions to <utility>
646//===----------------------------------------------------------------------===//
647
648/// \brief Function object to check whether the first component of a std::pair
649/// compares less than the first component of another std::pair.
650struct less_first {
651 template <typename T> bool operator()(const T &lhs, const T &rhs) const {
652 return lhs.first < rhs.first;
653 }
654};
655
656/// \brief Function object to check whether the second component of a std::pair
657/// compares less than the second component of another std::pair.
658struct less_second {
659 template <typename T> bool operator()(const T &lhs, const T &rhs) const {
660 return lhs.second < rhs.second;
661 }
662};
663
664// A subset of N3658. More stuff can be added as-needed.
665
666/// \brief Represents a compile-time sequence of integers.
667template <class T, T... I> struct integer_sequence {
668 using value_type = T;
669
670 static constexpr size_t size() { return sizeof...(I); }
671};
672
673/// \brief Alias for the common case of a sequence of size_ts.
674template <size_t... I>
675struct index_sequence : integer_sequence<std::size_t, I...> {};
676
677template <std::size_t N, std::size_t... I>
678struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {};
679template <std::size_t... I>
680struct build_index_impl<0, I...> : index_sequence<I...> {};
681
682/// \brief Creates a compile-time integer sequence for a parameter pack.
683template <class... Ts>
684struct index_sequence_for : build_index_impl<sizeof...(Ts)> {};
685
686/// Utility type to build an inheritance chain that makes it easy to rank
687/// overload candidates.
688template <int N> struct rank : rank<N - 1> {};
689template <> struct rank<0> {};
690
691/// \brief traits class for checking whether type T is one of any of the given
692/// types in the variadic list.
693template <typename T, typename... Ts> struct is_one_of {
694 static const bool value = false;
695};
696
697template <typename T, typename U, typename... Ts>
698struct is_one_of<T, U, Ts...> {
699 static const bool value =
700 std::is_same<T, U>::value || is_one_of<T, Ts...>::value;
701};
702
703/// \brief traits class for checking whether type T is a base class for all
704/// the given types in the variadic list.
705template <typename T, typename... Ts> struct are_base_of {
706 static const bool value = true;
707};
708
709template <typename T, typename U, typename... Ts>
710struct are_base_of<T, U, Ts...> {
711 static const bool value =
712 std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value;
713};
714
715//===----------------------------------------------------------------------===//
716// Extra additions for arrays
717//===----------------------------------------------------------------------===//
718
719/// Find the length of an array.
720template <class T, std::size_t N>
721constexpr inline size_t array_lengthof(T (&)[N]) {
722 return N;
723}
724
725/// Adapt std::less<T> for array_pod_sort.
726template<typename T>
727inline int array_pod_sort_comparator(const void *P1, const void *P2) {
728 if (std::less<T>()(*reinterpret_cast<const T*>(P1),
729 *reinterpret_cast<const T*>(P2)))
730 return -1;
731 if (std::less<T>()(*reinterpret_cast<const T*>(P2),
732 *reinterpret_cast<const T*>(P1)))
733 return 1;
734 return 0;
735}
736
737/// get_array_pod_sort_comparator - This is an internal helper function used to
738/// get type deduction of T right.
739template<typename T>
740inline int (*get_array_pod_sort_comparator(const T &))
741 (const void*, const void*) {
742 return array_pod_sort_comparator<T>;
743}
744
745/// array_pod_sort - This sorts an array with the specified start and end
746/// extent. This is just like std::sort, except that it calls qsort instead of
747/// using an inlined template. qsort is slightly slower than std::sort, but
748/// most sorts are not performance critical in LLVM and std::sort has to be
749/// template instantiated for each type, leading to significant measured code
750/// bloat. This function should generally be used instead of std::sort where
751/// possible.
752///
753/// This function assumes that you have simple POD-like types that can be
754/// compared with std::less and can be moved with memcpy. If this isn't true,
755/// you should use std::sort.
756///
757/// NOTE: If qsort_r were portable, we could allow a custom comparator and
758/// default to std::less.
759template<class IteratorTy>
760inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
761 // Don't inefficiently call qsort with one element or trigger undefined
762 // behavior with an empty sequence.
763 auto NElts = End - Start;
764 if (NElts <= 1) return;
765 qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
766}
767
768template <class IteratorTy>
769inline void array_pod_sort(
770 IteratorTy Start, IteratorTy End,
771 int (*Compare)(
772 const typename std::iterator_traits<IteratorTy>::value_type *,
773 const typename std::iterator_traits<IteratorTy>::value_type *)) {
774 // Don't inefficiently call qsort with one element or trigger undefined
775 // behavior with an empty sequence.
776 auto NElts = End - Start;
777 if (NElts <= 1) return;
778 qsort(&*Start, NElts, sizeof(*Start),
779 reinterpret_cast<int (*)(const void *, const void *)>(Compare));
780}
781
782//===----------------------------------------------------------------------===//
783// Extra additions to <algorithm>
784//===----------------------------------------------------------------------===//
785
786/// For a container of pointers, deletes the pointers and then clears the
787/// container.
788template<typename Container>
789void DeleteContainerPointers(Container &C) {
790 for (auto V : C)
791 delete V;
792 C.clear();
793}
794
795/// In a container of pairs (usually a map) whose second element is a pointer,
796/// deletes the second elements and then clears the container.
797template<typename Container>
798void DeleteContainerSeconds(Container &C) {
799 for (auto &V : C)
800 delete V.second;
801 C.clear();
802}
803
804/// Provide wrappers to std::for_each which take ranges instead of having to
805/// pass begin/end explicitly.
806template <typename R, typename UnaryPredicate>
807UnaryPredicate for_each(R &&Range, UnaryPredicate P) {
808 return std::for_each(adl_begin(Range), adl_end(Range), P);
809}
810
811/// Provide wrappers to std::all_of which take ranges instead of having to pass
812/// begin/end explicitly.
813template <typename R, typename UnaryPredicate>
814bool all_of(R &&Range, UnaryPredicate P) {
815 return std::all_of(adl_begin(Range), adl_end(Range), P);
816}
817
818/// Provide wrappers to std::any_of which take ranges instead of having to pass
819/// begin/end explicitly.
820template <typename R, typename UnaryPredicate>
821bool any_of(R &&Range, UnaryPredicate P) {
822 return std::any_of(adl_begin(Range), adl_end(Range), P);
823}
824
825/// Provide wrappers to std::none_of which take ranges instead of having to pass
826/// begin/end explicitly.
827template <typename R, typename UnaryPredicate>
828bool none_of(R &&Range, UnaryPredicate P) {
829 return std::none_of(adl_begin(Range), adl_end(Range), P);
830}
831
832/// Provide wrappers to std::find which take ranges instead of having to pass
833/// begin/end explicitly.
834template <typename R, typename T>
835auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range)) {
836 return std::find(adl_begin(Range), adl_end(Range), Val);
837}
838
839/// Provide wrappers to std::find_if which take ranges instead of having to pass
840/// begin/end explicitly.
841template <typename R, typename UnaryPredicate>
842auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
843 return std::find_if(adl_begin(Range), adl_end(Range), P);
844}
845
846template <typename R, typename UnaryPredicate>
847auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
848 return std::find_if_not(adl_begin(Range), adl_end(Range), P);
849}
850
851/// Provide wrappers to std::remove_if which take ranges instead of having to
852/// pass begin/end explicitly.
853template <typename R, typename UnaryPredicate>
854auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
855 return std::remove_if(adl_begin(Range), adl_end(Range), P);
856}
857
858/// Provide wrappers to std::copy_if which take ranges instead of having to
859/// pass begin/end explicitly.
860template <typename R, typename OutputIt, typename UnaryPredicate>
861OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
862 return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
863}
864
865template <typename R, typename OutputIt>
866OutputIt copy(R &&Range, OutputIt Out) {
867 return std::copy(adl_begin(Range), adl_end(Range), Out);
868}
869
870/// Wrapper function around std::find to detect if an element exists
871/// in a container.
872template <typename R, typename E>
873bool is_contained(R &&Range, const E &Element) {
874 return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
875}
876
877/// Wrapper function around std::count to count the number of times an element
878/// \p Element occurs in the given range \p Range.
879template <typename R, typename E>
880auto count(R &&Range, const E &Element) ->
881 typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
882 return std::count(adl_begin(Range), adl_end(Range), Element);
883}
884
885/// Wrapper function around std::count_if to count the number of times an
886/// element satisfying a given predicate occurs in a range.
887template <typename R, typename UnaryPredicate>
888auto count_if(R &&Range, UnaryPredicate P) ->
889 typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
890 return std::count_if(adl_begin(Range), adl_end(Range), P);
891}
892
893/// Wrapper function around std::transform to apply a function to a range and
894/// store the result elsewhere.
895template <typename R, typename OutputIt, typename UnaryPredicate>
896OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) {
897 return std::transform(adl_begin(Range), adl_end(Range), d_first, P);
898}
899
900/// Provide wrappers to std::partition which take ranges instead of having to
901/// pass begin/end explicitly.
902template <typename R, typename UnaryPredicate>
903auto partition(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
904 return std::partition(adl_begin(Range), adl_end(Range), P);
905}
906
907/// Provide wrappers to std::lower_bound which take ranges instead of having to
908/// pass begin/end explicitly.
909template <typename R, typename ForwardIt>
910auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
911 return std::lower_bound(adl_begin(Range), adl_end(Range), I);
912}
913
914/// \brief Given a range of type R, iterate the entire range and return a
915/// SmallVector with elements of the vector. This is useful, for example,
916/// when you want to iterate a range and then sort the results.
917template <unsigned Size, typename R>
918SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size>
919to_vector(R &&Range) {
920 return {adl_begin(Range), adl_end(Range)};
921}
922
923/// Provide a container algorithm similar to C++ Library Fundamentals v2's
924/// `erase_if` which is equivalent to:
925///
926/// C.erase(remove_if(C, pred), C.end());
927///
928/// This version works for any container with an erase method call accepting
929/// two iterators.
930template <typename Container, typename UnaryPredicate>
931void erase_if(Container &C, UnaryPredicate P) {
932 C.erase(remove_if(C, P), C.end());
933}
934
935//===----------------------------------------------------------------------===//
936// Extra additions to <memory>
937//===----------------------------------------------------------------------===//
938
939// Implement make_unique according to N3656.
940
941/// \brief Constructs a `new T()` with the given args and returns a
942/// `unique_ptr<T>` which owns the object.
943///
944/// Example:
945///
946/// auto p = make_unique<int>();
947/// auto p = make_unique<std::tuple<int, int>>(0, 1);
948template <class T, class... Args>
949typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
950make_unique(Args &&... args) {
951 return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
952}
953
954/// \brief Constructs a `new T[n]` with the given args and returns a
955/// `unique_ptr<T[]>` which owns the object.
956///
957/// \param n size of the new array.
958///
959/// Example:
960///
961/// auto p = make_unique<int[]>(2); // value-initializes the array with 0's.
962template <class T>
963typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
964 std::unique_ptr<T>>::type
965make_unique(size_t n) {
966 return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
5
Memory is allocated
967}
968
969/// This function isn't used and is only here to provide better compile errors.
970template <class T, class... Args>
971typename std::enable_if<std::extent<T>::value != 0>::type
972make_unique(Args &&...) = delete;
973
974struct FreeDeleter {
975 void operator()(void* v) {
976 ::free(v);
977 }
978};
979
980template<typename First, typename Second>
981struct pair_hash {
982 size_t operator()(const std::pair<First, Second> &P) const {
983 return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
984 }
985};
986
987/// A functor like C++14's std::less<void> in its absence.
988struct less {
989 template <typename A, typename B> bool operator()(A &&a, B &&b) const {
990 return std::forward<A>(a) < std::forward<B>(b);
991 }
992};
993
994/// A functor like C++14's std::equal<void> in its absence.
995struct equal {
996 template <typename A, typename B> bool operator()(A &&a, B &&b) const {
997 return std::forward<A>(a) == std::forward<B>(b);
998 }
999};
1000
1001/// Binary functor that adapts to any other binary functor after dereferencing
1002/// operands.
1003template <typename T> struct deref {
1004 T func;
1005
1006 // Could be further improved to cope with non-derivable functors and
1007 // non-binary functors (should be a variadic template member function
1008 // operator()).
1009 template <typename A, typename B>
1010 auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) {
1011 assert(lhs)(static_cast <bool> (lhs) ? void (0) : __assert_fail ("lhs"
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/ADT/STLExtras.h"
, 1011, __extension__ __PRETTY_FUNCTION__))
;
1012 assert(rhs)(static_cast <bool> (rhs) ? void (0) : __assert_fail ("rhs"
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/ADT/STLExtras.h"
, 1012, __extension__ __PRETTY_FUNCTION__))
;
1013 return func(*lhs, *rhs);
1014 }
1015};
1016
1017namespace detail {
1018
1019template <typename R> class enumerator_iter;
1020
1021template <typename R> struct result_pair {
1022 friend class enumerator_iter<R>;
1023
1024 result_pair() = default;
1025 result_pair(std::size_t Index, IterOfRange<R> Iter)
1026 : Index(Index), Iter(Iter) {}
1027
1028 result_pair<R> &operator=(const result_pair<R> &Other) {
1029 Index = Other.Index;
1030 Iter = Other.Iter;
1031 return *this;
1032 }
1033
1034 std::size_t index() const { return Index; }
1035 const ValueOfRange<R> &value() const { return *Iter; }
1036 ValueOfRange<R> &value() { return *Iter; }
1037
1038private:
1039 std::size_t Index = std::numeric_limits<std::size_t>::max();
1040 IterOfRange<R> Iter;
1041};
1042
1043template <typename R>
1044class enumerator_iter
1045 : public iterator_facade_base<
1046 enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>,
1047 typename std::iterator_traits<IterOfRange<R>>::difference_type,
1048 typename std::iterator_traits<IterOfRange<R>>::pointer,
1049 typename std::iterator_traits<IterOfRange<R>>::reference> {
1050 using result_type = result_pair<R>;
1051
1052public:
1053 explicit enumerator_iter(IterOfRange<R> EndIter)
1054 : Result(std::numeric_limits<size_t>::max(), EndIter) {}
1055
1056 enumerator_iter(std::size_t Index, IterOfRange<R> Iter)
1057 : Result(Index, Iter) {}
1058
1059 result_type &operator*() { return Result; }
1060 const result_type &operator*() const { return Result; }
1061
1062 enumerator_iter<R> &operator++() {
1063 assert(Result.Index != std::numeric_limits<size_t>::max())(static_cast <bool> (Result.Index != std::numeric_limits
<size_t>::max()) ? void (0) : __assert_fail ("Result.Index != std::numeric_limits<size_t>::max()"
, "/build/llvm-toolchain-snapshot-7~svn326551/include/llvm/ADT/STLExtras.h"
, 1063, __extension__ __PRETTY_FUNCTION__))
;
1064 ++Result.Iter;
1065 ++Result.Index;
1066 return *this;
1067 }
1068
1069 bool operator==(const enumerator_iter<R> &RHS) const {
1070 // Don't compare indices here, only iterators. It's possible for an end
1071 // iterator to have different indices depending on whether it was created
1072 // by calling std::end() versus incrementing a valid iterator.
1073 return Result.Iter == RHS.Result.Iter;
1074 }
1075
1076 enumerator_iter<R> &operator=(const enumerator_iter<R> &Other) {
1077 Result = Other.Result;
1078 return *this;
1079 }
1080
1081private:
1082 result_type Result;
1083};
1084
1085template <typename R> class enumerator {
1086public:
1087 explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
1088
1089 enumerator_iter<R> begin() {
1090 return enumerator_iter<R>(0, std::begin(TheRange));
1091 }
1092
1093 enumerator_iter<R> end() {
1094 return enumerator_iter<R>(std::end(TheRange));
1095 }
1096
1097private:
1098 R TheRange;
1099};
1100
1101} // end namespace detail
1102
1103/// Given an input range, returns a new range whose values are are pair (A,B)
1104/// such that A is the 0-based index of the item in the sequence, and B is
1105/// the value from the original sequence. Example:
1106///
1107/// std::vector<char> Items = {'A', 'B', 'C', 'D'};
1108/// for (auto X : enumerate(Items)) {
1109/// printf("Item %d - %c\n", X.index(), X.value());
1110/// }
1111///
1112/// Output:
1113/// Item 0 - A
1114/// Item 1 - B
1115/// Item 2 - C
1116/// Item 3 - D
1117///
1118template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
1119 return detail::enumerator<R>(std::forward<R>(TheRange));
1120}
1121
1122namespace detail {
1123
1124template <typename F, typename Tuple, std::size_t... I>
1125auto apply_tuple_impl(F &&f, Tuple &&t, index_sequence<I...>)
1126 -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)) {
1127 return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...);
1128}
1129
1130} // end namespace detail
1131
1132/// Given an input tuple (a1, a2, ..., an), pass the arguments of the
1133/// tuple variadically to f as if by calling f(a1, a2, ..., an) and
1134/// return the result.
1135template <typename F, typename Tuple>
1136auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl(
1137 std::forward<F>(f), std::forward<Tuple>(t),
1138 build_index_impl<
1139 std::tuple_size<typename std::decay<Tuple>::type>::value>{})) {
1140 using Indices = build_index_impl<
1141 std::tuple_size<typename std::decay<Tuple>::type>::value>;
1142
1143 return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t),
1144 Indices{});
1145}
1146
1147} // end namespace llvm
1148
1149#endif // LLVM_ADT_STLEXTRAS_H