SeedCollector.h Source File (original) (raw)

12#ifndef LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_SEEDCOLLECTOR_H

13#define LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_SEEDCOLLECTOR_H

22#include

23#include

29public:

33 for (auto &S : Seeds)

35 }

63 return ElmIdx;

64 return Seeds.size();

65 }

72 assert(It != end() && "Instruction not in the bundle!");

73 auto Idx = It - begin();

74 setUsed(Idx, 1, false);

75 }

77 void setUsed(unsigned ElementIdx, unsigned Sz = 1, bool VerifyUnused = true) {

78 if (ElementIdx + Sz >= UsedLanes.size())

79 UsedLanes.resize(ElementIdx + Sz);

80 for (unsigned Idx : seq(ElementIdx, ElementIdx + Sz)) {

82 "Already marked as used!");

85 }

87 }

89 bool isUsed(unsigned Element) const {

91 }

100 getSlice(unsigned StartIdx, unsigned MaxVecRegBits, bool ForcePowOf2);

101

102

103 std::size_t size() const { return Seeds.size(); }

104

105protected:

107

109

111

113

114public:

115#ifndef NDEBUG

117 for (auto [ElmIdx, I] : enumerate(*this)) {

118 OS.indent(2) << ElmIdx << ". ";

120 OS << "[USED]";

121 else

122 OS << *I;

123 OS << "\n";

124 }

125 }

128 dbgs() << "\n";

129 }

130#endif

131};

132

133

134

135

137public:

140 static_assert(std::is_same<LoadOrStoreT, LoadInst>::value ||

141 std::is_same<LoadOrStoreT, StoreInst>::value,

142 "Expected LoadInst or StoreInst!");

144 "Expected Load or Store instructions!");

148 };

149 std::sort(Seeds.begin(), Seeds.end(), Cmp);

150 }

152 static_assert(std::is_same<LoadOrStoreT, LoadInst>::value ||

153 std::is_same<LoadOrStoreT, StoreInst>::value,

154 "Expected LoadInst or StoreInst!");

156 }

166};

167

170

171

172

173

174

176

177

178

179 using KeyT = std::tuple<Value *, Type *, Instruction::Opcode>;

180

181

182

183

184

187

188 BundleMapT Bundles;

189

191

193

194 template

195 KeyT getKey(LoadOrStoreT *LSI, bool AllowDiffTypes) const;

196

197public:

199

201 BundleMapT *Map = nullptr;

203 ValT *Vec = nullptr;

204 size_t VecIdx;

205

206 public:

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

233 : Map(&Map), MapIt(MapIt), Vec(Vec), VecIdx(VecIdx) {}

235 assert(Vec != nullptr && "Already at end!");

236 return *(*Vec)[VecIdx];

237 }

238

240 while (Vec && VecIdx < Vec->size() && this->operator*().allUsed())

241 ++(*this);

242 }

243

245 ++VecIdx;

246 if (VecIdx >= Vec->size()) {

247 assert(MapIt != Map->end() && "Already at end!");

248 VecIdx = 0;

249 ++MapIt;

250 if (MapIt != Map->end())

251 Vec = &MapIt->second;

252 else {

253 Vec = nullptr;

254 }

255 }

257 return *this;

258 }

260 auto Copy = *this;

261 ++(*this);

262 return Copy;

263 }

265 assert(Map == Other.Map && "Iterator of different objects!");

266 return MapIt == Other.MapIt && VecIdx == Other.VecIdx;

267 }

269 };

271 template

272 void insert(LoadOrStoreT *LSI, bool AllowDiffTypes);

273

274

276 bool erase(const KeyT &Key) { return Bundles.erase(Key); }

278 if (Bundles.empty())

279 return end();

280 auto BeginIt =

281 iterator(Bundles, Bundles.begin(), &Bundles.begin()->second, 0);

282 BeginIt.skipUsed();

283 return BeginIt;

284 }

286 unsigned size() const { return Bundles.size(); }

287

288#ifndef NDEBUG

291#endif

292};

293

294

299

305

306

307 unsigned totalNumSeedGroups() const {

308 return StoreSeeds.size() + LoadSeeds.size();

309 }

310

311public:

313 bool CollectStores, bool CollectLoads,

314 bool AllowDiffTypes = false);

316

319#ifndef NDEBUG

322#endif

323};

324

325}

326

327#endif

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

This file implements the BitVector class.

#define LLVM_TEMPLATE_ABI

#define LLVM_DUMP_METHOD

Mark debug helper function definitions like dump() that should not be stripped from debug builds.

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

An instruction for reading from memory.

This class implements a map that also provides access to all stored values in a deterministic order.

typename SmallVector< std::pair< KeyT, ValT >, 0 >::iterator iterator

typename SmallVector< std::pair< KeyT, ValT >, 0 >::const_iterator const_iterator

The main scalar evolution driver.

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

An instruction for storing to memory.

A range adaptor for a pair of iterators.

This class implements an extremely fast bulk output stream that can only output to a stream.

raw_ostream & indent(unsigned NumSpaces)

indent - Insert 'NumSpaces' spaces.

An ID for a registered callback.

A sandboxir::User with operands, opcode and linked with previous/next instructions in an instruction ...

Specialization of SeedBundle for memory access instructions.

Definition SeedCollector.h:136

MemSeedBundle(SmallVector< Instruction * > &&SV, ScalarEvolution &SE)

Definition SeedCollector.h:138

void insert(sandboxir::Instruction *I, ScalarEvolution &SE) override

Definition SeedCollector.h:157

MemSeedBundle(LoadOrStoreT *MemI)

Definition SeedCollector.h:151

A set of candidate Instructions for vectorizing together.

Definition SeedCollector.h:28

SeedBundle & operator=(const SeedBundle &)=delete

SmallVector< Instruction * >::iterator iterator

Definition SeedCollector.h:41

iterator begin()

Definition SeedCollector.h:43

bool isUsed(unsigned Element) const

\Returns whether or not Element has been used.

Definition SeedCollector.h:89

virtual ~SeedBundle()=default

bool allUsed() const

Definition SeedCollector.h:92

SmallVector< Instruction * > Seeds

Definition SeedCollector.h:106

void setUsed(unsigned ElementIdx, unsigned Sz=1, bool VerifyUnused=true)

Definition SeedCollector.h:77

LLVM_ABI ArrayRef< Instruction * > getSlice(unsigned StartIdx, unsigned MaxVecRegBits, bool ForcePowOf2)

\Returns a slice of seed elements, starting at the element StartIdx, with a total size <= MaxVecRegBi...

void insertAt(iterator Pos, Instruction *I)

Insert I into position P.

Definition SeedCollector.h:53

unsigned getNumUnusedBits() const

Definition SeedCollector.h:93

const_iterator begin() const

Definition SeedCollector.h:45

unsigned NumUnusedBits

Tracks the remaining bits available to vectorize.

Definition SeedCollector.h:112

SeedBundle(const SeedBundle &)=delete

No need to allow copies.

void setUsed(Instruction *I)

Marks instruction I "used" within the bundle.

Definition SeedCollector.h:70

iterator end()

Definition SeedCollector.h:44

SeedBundle(SmallVector< Instruction * > &&L)

Definition SeedCollector.h:32

virtual void insert(Instruction *I, ScalarEvolution &SE)=0

SeedBundle(Instruction *I)

Initialize a bundle with I.

Definition SeedCollector.h:31

unsigned getFirstUnusedElementIdx() const

Definition SeedCollector.h:60

std::size_t size() const

\Returns the number of seed elements in the bundle.

Definition SeedCollector.h:103

SmallVector< Instruction * >::const_iterator const_iterator

Definition SeedCollector.h:42

Instruction * operator[](unsigned Idx) const

Definition SeedCollector.h:48

BitVector UsedLanes

The lanes that we have already vectorized.

Definition SeedCollector.h:108

const_iterator end() const

Definition SeedCollector.h:46

unsigned UsedLaneCount

Tracks used lanes for constant-time accessor.

Definition SeedCollector.h:110

void dump(raw_ostream &OS) const

Definition SeedCollector.h:116

LLVM_DUMP_METHOD void dump() const

Definition SeedCollector.h:126

iterator_range< SeedContainer::iterator > getLoadSeeds()

Definition SeedCollector.h:318

LLVM_ABI SeedCollector(BasicBlock *BB, ScalarEvolution &SE, bool CollectStores, bool CollectLoads, bool AllowDiffTypes=false)

iterator_range< SeedContainer::iterator > getStoreSeeds()

Definition SeedCollector.h:317

Definition SeedCollector.h:200

iterator operator++(int)

Definition SeedCollector.h:259

value_type & operator*()

Definition SeedCollector.h:234

iterator & operator++()

Definition SeedCollector.h:244

value_type * pointer

Definition SeedCollector.h:209

void skipUsed()

Definition SeedCollector.h:239

value_type & reference

Definition SeedCollector.h:210

SeedBundle value_type

Definition SeedCollector.h:208

bool operator==(const iterator &Other) const

Definition SeedCollector.h:264

iterator(BundleMapT &Map, BundleMapT::iterator MapIt, ValT *Vec, int VecIdx)

Iterates over the Map of SeedBundle Vectors, starting at MapIt, and Vec at VecIdx,...

Definition SeedCollector.h:232

std::ptrdiff_t difference_type

Definition SeedCollector.h:207

std::input_iterator_tag iterator_category

Definition SeedCollector.h:211

bool operator!=(const iterator &Other) const

Definition SeedCollector.h:268

Class to conveniently track Seeds within SeedBundles.

Definition SeedCollector.h:175

void print(raw_ostream &OS) const

iterator end()

Definition SeedCollector.h:285

bool erase(const KeyT &Key)

Definition SeedCollector.h:276

void insert(LoadOrStoreT *LSI, bool AllowDiffTypes)

SeedContainer(ScalarEvolution &SE)

Definition SeedCollector.h:198

unsigned size() const

Definition SeedCollector.h:286

iterator begin()

Definition SeedCollector.h:277

BundleMapT::const_iterator const_iterator

Definition SeedCollector.h:270

LLVM_DUMP_METHOD void dump() const

LLVM_ABI bool erase(Instruction *I)

static bool atLowerAddress(LoadOrStoreT *I0, LoadOrStoreT *I1, ScalarEvolution &SE)

\Returns true if I0 accesses a memory location lower than I1.

static unsigned getNumBits(Type *Ty, const DataLayout &DL)

\Returns the number of bits of Ty.

This provides a very simple, boring adaptor for a begin and end iterator into a range type.

BasicBlock(llvm::BasicBlock *BB, Context &SBCtx)

MemSeedBundle< sandboxir::LoadInst > LoadSeedBundle

Definition SeedCollector.h:169

MemSeedBundle< sandboxir::StoreInst > StoreSeedBundle

Definition SeedCollector.h:168

void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)

auto find(R &&Range, const T &Val)

Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.

bool all_of(R &&range, UnaryPredicate P)

Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.

Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)

auto enumerate(FirstRange &&First, RestRanges &&...Rest)

Given two or more input ranges, returns a new range whose values are tuples (A, B,...

auto upper_bound(R &&Range, T &&Value)

Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key

OutputIt move(R &&Range, OutputIt Out)

Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

auto seq(T Begin, T End)

Iterate over an integral type from Begin up to - but not including - End.

Implement std::hash so that hash_code can be used in STL containers.