Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Support/ArrayRecycler.h
Line
Count
Source
1
//==- llvm/Support/ArrayRecycler.h - Recycling of Arrays ---------*- C++ -*-==//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This file defines the ArrayRecycler class template which can recycle small
10
// arrays allocated from one of the allocators in Allocator.h
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef LLVM_SUPPORT_ARRAYRECYCLER_H
15
#define LLVM_SUPPORT_ARRAYRECYCLER_H
16
17
#include "llvm/ADT/SmallVector.h"
18
#include "llvm/Support/Allocator.h"
19
#include "llvm/Support/MathExtras.h"
20
21
namespace llvm {
22
23
/// Recycle small arrays allocated from a BumpPtrAllocator.
24
///
25
/// Arrays are allocated in a small number of fixed sizes. For each supported
26
/// array size, the ArrayRecycler keeps a free list of available arrays.
27
///
28
template <class T, size_t Align = alignof(T)> class ArrayRecycler {
29
  // The free list for a given array size is a simple singly linked list.
30
  // We can't use iplist or Recycler here since those classes can't be copied.
31
  struct FreeList {
32
    FreeList *Next;
33
  };
34
35
  static_assert(Align >= alignof(FreeList), "Object underaligned");
36
  static_assert(sizeof(T) >= sizeof(FreeList), "Objects are too small");
37
38
  // Keep a free list for each array size.
39
  SmallVector<FreeList*, 8> Bucket;
40
41
  // Remove an entry from the free list in Bucket[Idx] and return it.
42
  // Return NULL if no entries are available.
43
107M
  T *pop(unsigned Idx) {
44
107M
    if (Idx >= Bucket.size())
45
27.1M
      return nullptr;
46
80.2M
    FreeList *Entry = Bucket[Idx];
47
80.2M
    if (!Entry)
48
36.6M
      return nullptr;
49
43.5M
    __asan_unpoison_memory_region(Entry, Capacity::get(Idx).getSize());
50
43.5M
    Bucket[Idx] = Entry->Next;
51
43.5M
    __msan_allocated_memory(Entry, Capacity::get(Idx).getSize());
52
43.5M
    return reinterpret_cast<T*>(Entry);
53
43.5M
  }
llvm::ArrayRecycler<llvm::MachineOperand, 8ul>::pop(unsigned int)
Line
Count
Source
43
74.6M
  T *pop(unsigned Idx) {
44
74.6M
    if (Idx >= Bucket.size())
45
10.3M
      return nullptr;
46
64.2M
    FreeList *Entry = Bucket[Idx];
47
64.2M
    if (!Entry)
48
32.3M
      return nullptr;
49
31.9M
    __asan_unpoison_memory_region(Entry, Capacity::get(Idx).getSize());
50
31.9M
    Bucket[Idx] = Entry->Next;
51
31.9M
    __msan_allocated_memory(Entry, Capacity::get(Idx).getSize());
52
31.9M
    return reinterpret_cast<T*>(Entry);
53
31.9M
  }
llvm::ArrayRecycler<llvm::Value*, 8ul>::pop(unsigned int)
Line
Count
Source
43
3.47k
  T *pop(unsigned Idx) {
44
3.47k
    if (Idx >= Bucket.size())
45
1.19k
      return nullptr;
46
2.27k
    FreeList *Entry = Bucket[Idx];
47
2.27k
    if (!Entry)
48
1.48k
      return nullptr;
49
796
    __asan_unpoison_memory_region(Entry, Capacity::get(Idx).getSize());
50
796
    Bucket[Idx] = Entry->Next;
51
796
    __msan_allocated_memory(Entry, Capacity::get(Idx).getSize());
52
796
    return reinterpret_cast<T*>(Entry);
53
796
  }
llvm::ArrayRecycler<llvm::SDUse, 8ul>::pop(unsigned int)
Line
Count
Source
43
32.7M
  T *pop(unsigned Idx) {
44
32.7M
    if (Idx >= Bucket.size())
45
16.7M
      return nullptr;
46
15.9M
    FreeList *Entry = Bucket[Idx];
47
15.9M
    if (!Entry)
48
4.35M
      return nullptr;
49
11.6M
    __asan_unpoison_memory_region(Entry, Capacity::get(Idx).getSize());
50
11.6M
    Bucket[Idx] = Entry->Next;
51
11.6M
    __msan_allocated_memory(Entry, Capacity::get(Idx).getSize());
52
11.6M
    return reinterpret_cast<T*>(Entry);
53
11.6M
  }
54
55
  // Add an entry to the free list at Bucket[Idx].
56
82.4M
  void push(unsigned Idx, T *Ptr) {
57
82.4M
    assert(Ptr && "Cannot recycle NULL pointer");
58
82.4M
    FreeList *Entry = reinterpret_cast<FreeList*>(Ptr);
59
82.4M
    if (Idx >= Bucket.size())
60
3.96M
      Bucket.resize(size_t(Idx) + 1);
61
82.4M
    Entry->Next = Bucket[Idx];
62
82.4M
    Bucket[Idx] = Entry;
63
82.4M
    __asan_poison_memory_region(Ptr, Capacity::get(Idx).getSize());
64
82.4M
  }
llvm::ArrayRecycler<llvm::MachineOperand, 8ul>::push(unsigned int, llvm::MachineOperand*)
Line
Count
Source
56
49.7M
  void push(unsigned Idx, T *Ptr) {
57
49.7M
    assert(Ptr && "Cannot recycle NULL pointer");
58
49.7M
    FreeList *Entry = reinterpret_cast<FreeList*>(Ptr);
59
49.7M
    if (Idx >= Bucket.size())
60
1.15M
      Bucket.resize(size_t(Idx) + 1);
61
49.7M
    Entry->Next = Bucket[Idx];
62
49.7M
    Bucket[Idx] = Entry;
63
49.7M
    __asan_poison_memory_region(Ptr, Capacity::get(Idx).getSize());
64
49.7M
  }
llvm::ArrayRecycler<llvm::SDUse, 8ul>::push(unsigned int, llvm::SDUse*)
Line
Count
Source
56
32.7M
  void push(unsigned Idx, T *Ptr) {
57
32.7M
    assert(Ptr && "Cannot recycle NULL pointer");
58
32.7M
    FreeList *Entry = reinterpret_cast<FreeList*>(Ptr);
59
32.7M
    if (Idx >= Bucket.size())
60
2.80M
      Bucket.resize(size_t(Idx) + 1);
61
32.7M
    Entry->Next = Bucket[Idx];
62
32.7M
    Bucket[Idx] = Entry;
63
32.7M
    __asan_poison_memory_region(Ptr, Capacity::get(Idx).getSize());
64
32.7M
  }
llvm::ArrayRecycler<llvm::Value*, 8ul>::push(unsigned int, llvm::Value**)
Line
Count
Source
56
861
  void push(unsigned Idx, T *Ptr) {
57
861
    assert(Ptr && "Cannot recycle NULL pointer");
58
861
    FreeList *Entry = reinterpret_cast<FreeList*>(Ptr);
59
861
    if (Idx >= Bucket.size())
60
200
      Bucket.resize(size_t(Idx) + 1);
61
861
    Entry->Next = Bucket[Idx];
62
861
    Bucket[Idx] = Entry;
63
861
    __asan_poison_memory_region(Ptr, Capacity::get(Idx).getSize());
64
861
  }
65
66
public:
67
  /// The size of an allocated array is represented by a Capacity instance.
68
  ///
69
  /// This class is much smaller than a size_t, and it provides methods to work
70
  /// with the set of legal array capacities.
71
  class Capacity {
72
    uint8_t Index;
73
140M
    explicit Capacity(uint8_t idx) : Index(idx) {}
llvm::ArrayRecycler<llvm::MachineOperand, 8ul>::Capacity::Capacity(unsigned char)
Line
Count
Source
73
74.6M
    explicit Capacity(uint8_t idx) : Index(idx) {}
llvm::ArrayRecycler<llvm::Value*, 8ul>::Capacity::Capacity(unsigned char)
Line
Count
Source
73
4.33k
    explicit Capacity(uint8_t idx) : Index(idx) {}
llvm::ArrayRecycler<llvm::SDUse, 8ul>::Capacity::Capacity(unsigned char)
Line
Count
Source
73
65.4M
    explicit Capacity(uint8_t idx) : Index(idx) {}
74
75
  public:
76
66.5M
    Capacity() : Index(0) {}
77
78
    /// Get the capacity of an array that can hold at least N elements.
79
131M
    static Capacity get(size_t N) {
80
131M
      return Capacity(N ? 
Log2_64_Ceil(N)131M
:
0247k
);
81
131M
    }
llvm::ArrayRecycler<llvm::SDUse, 8ul>::Capacity::get(unsigned long)
Line
Count
Source
79
65.4M
    static Capacity get(size_t N) {
80
65.4M
      return Capacity(N ? 
Log2_64_Ceil(N)65.2M
:
0245k
);
81
65.4M
    }
llvm::ArrayRecycler<llvm::MachineOperand, 8ul>::Capacity::get(unsigned long)
Line
Count
Source
79
66.4M
    static Capacity get(size_t N) {
80
66.4M
      return Capacity(N ? 
Log2_64_Ceil(N)66.4M
:
02.58k
);
81
66.4M
    }
llvm::ArrayRecycler<llvm::Value*, 8ul>::Capacity::get(unsigned long)
Line
Count
Source
79
4.33k
    static Capacity get(size_t N) {
80
4.33k
      return Capacity(N ? 
Log2_64_Ceil(N)4.30k
:
032
);
81
4.33k
    }
82
83
    /// Get the number of elements in an array with this capacity.
84
261M
    size_t getSize() const { return size_t(1u) << Index; }
llvm::ArrayRecycler<llvm::MachineOperand, 8ul>::Capacity::getSize() const
Line
Count
Source
84
240M
    size_t getSize() const { return size_t(1u) << Index; }
llvm::ArrayRecycler<llvm::Value*, 8ul>::Capacity::getSize() const
Line
Count
Source
84
2.67k
    size_t getSize() const { return size_t(1u) << Index; }
llvm::ArrayRecycler<llvm::SDUse, 8ul>::Capacity::getSize() const
Line
Count
Source
84
21.1M
    size_t getSize() const { return size_t(1u) << Index; }
85
86
    /// Get the bucket number for this capacity.
87
189M
    unsigned getBucket() const { return Index; }
llvm::ArrayRecycler<llvm::MachineOperand, 8ul>::Capacity::getBucket() const
Line
Count
Source
87
124M
    unsigned getBucket() const { return Index; }
llvm::ArrayRecycler<llvm::SDUse, 8ul>::Capacity::getBucket() const
Line
Count
Source
87
65.4M
    unsigned getBucket() const { return Index; }
llvm::ArrayRecycler<llvm::Value*, 8ul>::Capacity::getBucket() const
Line
Count
Source
87
4.33k
    unsigned getBucket() const { return Index; }
88
89
    /// Get the next larger capacity. Large capacities grow exponentially, so
90
    /// this function can be used to reallocate incrementally growing vectors
91
    /// in amortized linear time.
92
8.23M
    Capacity getNext() const { return Capacity(Index + 1); }
93
  };
94
95
549k
  ~ArrayRecycler() {
96
549k
    // The client should always call clear() so recycled arrays can be returned
97
549k
    // to the allocator.
98
549k
    assert(Bucket.empty() && "Non-empty ArrayRecycler deleted!");
99
549k
  }
llvm::ArrayRecycler<llvm::MachineOperand, 8ul>::~ArrayRecycler()
Line
Count
Source
95
510k
  ~ArrayRecycler() {
96
510k
    // The client should always call clear() so recycled arrays can be returned
97
510k
    // to the allocator.
98
510k
    assert(Bucket.empty() && "Non-empty ArrayRecycler deleted!");
99
510k
  }
llvm::ArrayRecycler<llvm::Value*, 8ul>::~ArrayRecycler()
Line
Count
Source
95
368
  ~ArrayRecycler() {
96
368
    // The client should always call clear() so recycled arrays can be returned
97
368
    // to the allocator.
98
368
    assert(Bucket.empty() && "Non-empty ArrayRecycler deleted!");
99
368
  }
llvm::ArrayRecycler<llvm::SDUse, 8ul>::~ArrayRecycler()
Line
Count
Source
95
37.9k
  ~ArrayRecycler() {
96
37.9k
    // The client should always call clear() so recycled arrays can be returned
97
37.9k
    // to the allocator.
98
37.9k
    assert(Bucket.empty() && "Non-empty ArrayRecycler deleted!");
99
37.9k
  }
100
101
  /// Release all the tracked allocations to the allocator. The recycler must
102
  /// be free of any tracked allocations before being deleted.
103
  template<class AllocatorType>
104
  void clear(AllocatorType &Allocator) {
105
    for (; !Bucket.empty(); Bucket.pop_back())
106
      while (T *Ptr = pop(Bucket.size() - 1))
107
        Allocator.Deallocate(Ptr);
108
  }
109
110
  /// Special case for BumpPtrAllocator which has an empty Deallocate()
111
  /// function.
112
  ///
113
  /// There is no need to traverse the free lists, pulling all the objects into
114
  /// cache.
115
1.81M
  void clear(BumpPtrAllocator&) {
116
1.81M
    Bucket.clear();
117
1.81M
  }
llvm::ArrayRecycler<llvm::MachineOperand, 8ul>::clear(llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul>&)
Line
Count
Source
115
526k
  void clear(BumpPtrAllocator&) {
116
526k
    Bucket.clear();
117
526k
  }
llvm::ArrayRecycler<llvm::Value*, 8ul>::clear(llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul>&)
Line
Count
Source
115
333
  void clear(BumpPtrAllocator&) {
116
333
    Bucket.clear();
117
333
  }
llvm::ArrayRecycler<llvm::SDUse, 8ul>::clear(llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul>&)
Line
Count
Source
115
1.28M
  void clear(BumpPtrAllocator&) {
116
1.28M
    Bucket.clear();
117
1.28M
  }
118
119
  /// Allocate an array of at least the requested capacity.
120
  ///
121
  /// Return an existing recycled array, or allocate one from Allocator if
122
  /// none are available for recycling.
123
  ///
124
  template<class AllocatorType>
125
107M
  T *allocate(Capacity Cap, AllocatorType &Allocator) {
126
107M
    // Try to recycle an existing array.
127
107M
    if (T *Ptr = pop(Cap.getBucket()))
128
43.5M
      return Ptr;
129
63.8M
    // Nope, get more memory.
130
63.8M
    return static_cast<T*>(Allocator.Allocate(sizeof(T)*Cap.getSize(), Align));
131
63.8M
  }
llvm::MachineOperand* llvm::ArrayRecycler<llvm::MachineOperand, 8ul>::allocate<llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul> >(llvm::ArrayRecycler<llvm::MachineOperand, 8ul>::Capacity, llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul>&)
Line
Count
Source
125
74.6M
  T *allocate(Capacity Cap, AllocatorType &Allocator) {
126
74.6M
    // Try to recycle an existing array.
127
74.6M
    if (T *Ptr = pop(Cap.getBucket()))
128
31.9M
      return Ptr;
129
42.6M
    // Nope, get more memory.
130
42.6M
    return static_cast<T*>(Allocator.Allocate(sizeof(T)*Cap.getSize(), Align));
131
42.6M
  }
llvm::Value** llvm::ArrayRecycler<llvm::Value*, 8ul>::allocate<llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul> >(llvm::ArrayRecycler<llvm::Value*, 8ul>::Capacity, llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul>&)
Line
Count
Source
125
3.47k
  T *allocate(Capacity Cap, AllocatorType &Allocator) {
126
3.47k
    // Try to recycle an existing array.
127
3.47k
    if (T *Ptr = pop(Cap.getBucket()))
128
796
      return Ptr;
129
2.67k
    // Nope, get more memory.
130
2.67k
    return static_cast<T*>(Allocator.Allocate(sizeof(T)*Cap.getSize(), Align));
131
2.67k
  }
llvm::SDUse* llvm::ArrayRecycler<llvm::SDUse, 8ul>::allocate<llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul> >(llvm::ArrayRecycler<llvm::SDUse, 8ul>::Capacity, llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul>&)
Line
Count
Source
125
32.7M
  T *allocate(Capacity Cap, AllocatorType &Allocator) {
126
32.7M
    // Try to recycle an existing array.
127
32.7M
    if (T *Ptr = pop(Cap.getBucket()))
128
11.6M
      return Ptr;
129
21.1M
    // Nope, get more memory.
130
21.1M
    return static_cast<T*>(Allocator.Allocate(sizeof(T)*Cap.getSize(), Align));
131
21.1M
  }
132
133
  /// Deallocate an array with the specified Capacity.
134
  ///
135
  /// Cap must be the same capacity that was given to allocate().
136
  ///
137
82.4M
  void deallocate(Capacity Cap, T *Ptr) {
138
82.4M
    push(Cap.getBucket(), Ptr);
139
82.4M
  }
llvm::ArrayRecycler<llvm::MachineOperand, 8ul>::deallocate(llvm::ArrayRecycler<llvm::MachineOperand, 8ul>::Capacity, llvm::MachineOperand*)
Line
Count
Source
137
49.7M
  void deallocate(Capacity Cap, T *Ptr) {
138
49.7M
    push(Cap.getBucket(), Ptr);
139
49.7M
  }
llvm::ArrayRecycler<llvm::SDUse, 8ul>::deallocate(llvm::ArrayRecycler<llvm::SDUse, 8ul>::Capacity, llvm::SDUse*)
Line
Count
Source
137
32.7M
  void deallocate(Capacity Cap, T *Ptr) {
138
32.7M
    push(Cap.getBucket(), Ptr);
139
32.7M
  }
llvm::ArrayRecycler<llvm::Value*, 8ul>::deallocate(llvm::ArrayRecycler<llvm::Value*, 8ul>::Capacity, llvm::Value**)
Line
Count
Source
137
861
  void deallocate(Capacity Cap, T *Ptr) {
138
861
    push(Cap.getBucket(), Ptr);
139
861
  }
140
};
141
142
} // end llvm namespace
143
144
#endif