OptimizedStructLayout.cpp Source File (original) (raw)

14#include

16using namespace llvm;

20#ifndef NDEBUG

24 Align ComputedMaxAlign;

25 for (auto &Field : Fields) {

27 "didn't assign a fixed offset to field");

29 "didn't assign a correctly-aligned offset to field");

31 "didn't assign offsets in ascending order");

34 "didn't compute MaxAlign correctly");

35 ComputedMaxAlign = std::max(Field.Alignment, MaxAlign);

36 }

37 assert(LastEnd == Size && "didn't compute LastEnd correctly");

38 assert(ComputedMaxAlign == MaxAlign && "didn't compute MaxAlign correctly");

39}

40#endif

42std::pair<uint64_t, Align>

44#ifndef NDEBUG

46 {

47 bool InFixedPrefix = true;

48 size_t LastEnd = 0;

49 for (auto &Field : Fields) {

52 assert(InFixedPrefix &&

53 "fixed-offset fields are not a strict prefix of array");

55 "fixed-offset fields overlap or are not in order");

58 "overflow in fixed-offset end offset");

59 } else {

60 InFixedPrefix = false;

61 }

62 }

63 }

64#endif

70 auto FirstFlexible = Fields.begin(), E = Fields.end();

71 while (FirstFlexible != E && FirstFlexible->hasFixedOffset()) {

72 MaxAlign = std::max(MaxAlign, FirstFlexible->Alignment);

73 ++FirstFlexible;

74 }

77 if (FirstFlexible == E) {

79 if (!Fields.empty())

80 Size = Fields.back().getEndOffset();

82#ifndef NDEBUG

84#endif

85 return std::make_pair(Size, MaxAlign);

86 }

93 {

94 uintptr_t UniqueNumber = 0;

95 for (auto I = FirstFlexible; I != E; ++I) {

96 I->Scratch = reinterpret_cast<void*>(UniqueNumber++);

97 MaxAlign = std::max(MaxAlign, I->Alignment);

98 }

99 }

100

101

102

103

104

105

107 [](const Field *lhs, const Field *rhs) -> int {

108

111

112

114 return (lhs->Size < rhs->Size ? 1 : -1);

115

116

117 auto lhsNumber = reinterpret_cast<uintptr_t>(lhs->Scratch);

118 auto rhsNumber = reinterpret_cast<uintptr_t>(rhs->Scratch);

119 if (lhsNumber != rhsNumber)

120 return (lhsNumber < rhsNumber ? -1 : 1);

121

122 return 0;

123 });

124

125

126

127

128

129

130

131 {

132 bool HasPadding = false;

134

135

136 for (auto I = Fields.begin(); I != FirstFlexible; ++I) {

137 assert(I->hasFixedOffset());

138 if (LastEnd != I->Offset) {

139 HasPadding = true;

140 break;

141 }

142 LastEnd = I->getEndOffset();

143 }

144

145

146

147

148

149

150 if (!HasPadding) {

151 for (auto I = FirstFlexible; I != E; ++I) {

153 if (LastEnd != Offset) {

154 HasPadding = true;

155 break;

156 }

158 LastEnd = I->getEndOffset();

159 }

160 }

161

162

163 if (!HasPadding) {

164#ifndef NDEBUG

166#endif

167 return std::make_pair(LastEnd, MaxAlign);

168 }

169 }

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236 struct AlignmentQueue {

237

239

240

241

242

243

244

246

247

249

252 }

253 };

255 for (auto I = FirstFlexible; I != E; ) {

256 auto Head = I;

257 auto Alignment = I->Alignment;

258

260 auto LastInQueue = I;

261 for (++I; I != E && I->Alignment == Alignment; ++I) {

262 LastInQueue->Scratch = I;

263 LastInQueue = I;

264 MinSize = std::min(MinSize, I->Size);

265 }

266 LastInQueue->Scratch = nullptr;

267

268 FlexibleFieldsByAlignment.push_back({MinSize, Head, Alignment});

269 }

270

271#ifndef NDEBUG

272

273 auto checkQueues = [&]{

274 bool FirstQueue = true;

275 Align LastQueueAlignment;

276 for (auto &Queue : FlexibleFieldsByAlignment) {

277 assert((FirstQueue || Queue.Alignment < LastQueueAlignment) &&

278 "bins not in order of descending alignment");

279 LastQueueAlignment = Queue.Alignment;

280 FirstQueue = false;

281

282 assert(Queue.Head && "queue was empty");

284 for (auto I = Queue.Head; I; I = Queue.getNext(I)) {

285 assert(I->Alignment == Queue.Alignment && "bad field in queue");

286 assert(I->Size <= LastSize && "queue not in descending size order");

287 LastSize = I->Size;

288 }

289 }

290 };

291 checkQueues();

292#endif

293

294

295 auto spliceFromQueue = [&](AlignmentQueue *Queue, Field *Last, Field *Cur) {

296 assert(Last ? Queue->getNext(Last) == Cur : Queue->Head == Cur);

297

298

299

301 Last->Scratch = Cur->Scratch;

302

303

304

305

306 if (!Cur->Scratch)

307 Queue->MinSize = Last->Size;

308

309

310 } else {

311 if (auto NewHead = Queue->getNext(Cur))

312 Queue->Head = NewHead;

313

314

315 else

316 FlexibleFieldsByAlignment.erase(Queue);

317 }

318 };

319

320

321

324

325

327

328

329

330 auto addToLayout = [&](AlignmentQueue *Queue, Field *Last, Field *Cur,

333

334

335 spliceFromQueue(Queue, Last, Cur);

336

337

340 LastEnd = Layout.back().getEndOffset();

341

342

343 return true;

344 };

345

346

347

348

349 auto tryAddFillerFromQueue = [&](AlignmentQueue *Queue, uint64_t StartOffset,

350 std::optional<uint64_t> EndOffset) -> bool {

352 assert(StartOffset == alignTo(LastEnd, Queue->Alignment));

353 assert(!EndOffset || StartOffset < *EndOffset);

354

355

356

357 auto MaxViableSize =

358 (EndOffset ? *EndOffset - StartOffset : ~(uint64_t)0);

359 if (Queue->MinSize > MaxViableSize)

360 return false;

361

362

363

364 for (Field *Cur = Queue->Head, *Last = nullptr; true;

365 Last = Cur, Cur = Queue->getNext(Cur)) {

366 assert(Cur && "didn't find a match in queue despite its MinSize");

367 if (Cur->Size <= MaxViableSize)

368 return addToLayout(Queue, Last, Cur, StartOffset);

369 }

370

371 llvm_unreachable("didn't find a match in queue despite its MinSize");

372 };

373

374

375

376 auto tryAddBestField = [&](std::optional<uint64_t> BeforeOffset) -> bool {

377 assert(!BeforeOffset || LastEnd < *BeforeOffset);

378 auto QueueB = FlexibleFieldsByAlignment.begin();

379 auto QueueE = FlexibleFieldsByAlignment.end();

380

381

382

383 auto FirstQueueToSearch = QueueB;

384 for (; FirstQueueToSearch != QueueE; ++FirstQueueToSearch) {

385 if (isAligned(FirstQueueToSearch->Alignment, LastEnd))

386 break;

387 }

388

390 while (true) {

391

392

393

394

395

396 for (auto Queue = FirstQueueToSearch; Queue != QueueE; ++Queue) {

397 if (tryAddFillerFromQueue(Queue, Offset, BeforeOffset))

398 return true;

399 }

400

401

402 QueueE = FirstQueueToSearch;

403

404

405 if (FirstQueueToSearch == QueueB)

406 return false;

407

408

409

410

411 --FirstQueueToSearch;

412 Offset = alignTo(LastEnd, FirstQueueToSearch->Alignment);

413 if (BeforeOffset && Offset >= *BeforeOffset)

414 return false;

415 while (FirstQueueToSearch != QueueB &&

416 Offset == alignTo(LastEnd, FirstQueueToSearch[-1].Alignment))

417 --FirstQueueToSearch;

418 }

419 };

420

421

422

423 for (auto I = Fields.begin(); I != FirstFlexible; ++I) {

425 while (LastEnd != I->Offset) {

426 if (!tryAddBestField(I->Offset))

427 break;

428 }

430 LastEnd = I->getEndOffset();

431 }

432

433#ifndef NDEBUG

434 checkQueues();

435#endif

436

437

438

439 while (!FlexibleFieldsByAlignment.empty()) {

440 bool Success = tryAddBestField(std::nullopt);

441 assert(Success && "didn't find a field with no fixed limit?");

443 }

444

445

447 memcpy(Fields.data(), Layout.data(),

449

450#ifndef NDEBUG

451

453#endif

454

455 return std::make_pair(LastEnd, MaxAlign);

456}

static void checkValidLayout(ArrayRef< Field > Fields, uint64_t Size, Align MaxAlign)

This file provides an interface for laying out a sequence of fields as a struct in a way that attempt...

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

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

size_t size() const

size - Get the array size.

bool empty() const

empty - Check if the array is empty.

MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...

T & back() const

back - Get the last element.

void reserve(size_type N)

iterator erase(const_iterator CI)

void push_back(const T &Elt)

pointer data()

Return a pointer to the vector's buffer, even if empty().

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

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

This is an optimization pass for GlobalISel generic memory operations.

bool isAligned(Align Lhs, uint64_t SizeInBytes)

Checks that SizeInBytes is a multiple of the alignment.

std::pair< uint64_t, Align > performOptimizedStructLayout(MutableArrayRef< OptimizedStructLayoutField > Fields)

Compute a layout for a struct containing the given fields, making a best-effort attempt to minimize t...

uint64_t alignTo(uint64_t Size, Align A)

Returns a multiple of A needed to store Size bytes.

void array_pod_sort(IteratorTy Start, IteratorTy End)

array_pod_sort - This sorts an array with the specified start and end extent.

This struct is a compact representation of a valid (non-zero power of two) alignment.

Align Alignment

The required alignment of this field.

uint64_t getEndOffset() const

Given that this field has a fixed offset, return the offset of the first byte following it.

void * Scratch

Private scratch space for the algorithm.

bool hasFixedOffset() const

Return true if this field has been assigned a fixed offset.

uint64_t Offset

The offset of this field in the final layout.

uint64_t Size

The required size of this field in bytes.