ThreadSafetyTIL.h Source File (original) (raw)

46#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H

47#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H

52#include "llvm/ADT/ArrayRef.h"

53#include "llvm/ADT/StringRef.h"

54#include "llvm/Support/Casting.h"

55#include "llvm/Support/raw_ostream.h"

56#include

57#include

58#include

59#include

60#include

61#include

62#include

63#include

67class CallExpr;

68class Expr;

69class Stmt;

71namespace threadSafety {

72namespace til {

78#define TIL_OPCODE_DEF(X) COP_##X,

79#include "ThreadSafetyOps.def"

80#undef TIL_OPCODE_DEF

81};

110

111

114

115

117

118

120

121

123

124

126

127

130

139

140

142

143

145

146

147

148

149

150

151

162

172

175

177

178 template

180

184

185

187};

188

190 switch (nbytes) {

191 case 1: return ST_8;

192 case 2: return ST_16;

193 case 4: return ST_32;

194 case 8: return ST_64;

195 case 16: return ST_128;

196 default: return ST_0;

197 }

198}

199

200template<>

201inline ValueType ValueType::getValueType() {

203}

204

205template<>

206inline ValueType ValueType::getValueType() {

208}

209

210template<>

211inline ValueType ValueType::getValueType<int8_t>() {

213}

214

215template<>

216inline ValueType ValueType::getValueType<uint8_t>() {

218}

219

220template<>

221inline ValueType ValueType::getValueType<int16_t>() {

223}

224

225template<>

226inline ValueType ValueType::getValueType<uint16_t>() {

228}

229

230template<>

231inline ValueType ValueType::getValueType<int32_t>() {

233}

234

235template<>

236inline ValueType ValueType::getValueType<uint32_t>() {

238}

239

240template<>

241inline ValueType ValueType::getValueType<int64_t>() {

243}

244

245template<>

246inline ValueType ValueType::getValueType<uint64_t>() {

248}

249

250template<>

251inline ValueType ValueType::getValueType() {

253}

254

255template<>

256inline ValueType ValueType::getValueType() {

258}

259

260template<>

261inline ValueType ValueType::getValueType() {

263}

264

265template<>

266inline ValueType ValueType::getValueType() {

268}

269

270template<>

271inline ValueType ValueType::getValueType<void*>() {

273}

274

275

277public:

279

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

297 return ::operator new(S, R);

298 }

299

300

301 void *operator new(size_t) = delete;

302

303

304

305

306 void operator delete(void *) = delete;

307

308

309

311

312

313

315

316

318

319protected:

323

329};

330

331

332namespace ThreadSafetyTIL {

333

336 return Op == COP_Variable || Op == COP_Literal || Op == COP_LiteralPtr;

337}

338

339}

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

356public:

358

360

361

363

364

367

369 : SExpr(COP_Variable), Name(s), Definition(D) {

371 }

372

374 : SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"),

375 Definition(D), Cvdecl(Cvd) {

377 }

378

380 : SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl) {

382 }

383

384 static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; }

385

386

388

389

390 StringRef name() const { return Name; }

391

392

394

395

396

397

400

401 void setName(StringRef S) { Name = S; }

405

406 template

407 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

408

409 return Vs.reduceVariableRef(this);

410 }

411

412 template

414 return Cmp.compareVariableRefs(this, E);

415 }

416

417private:

422

423

424 StringRef Name;

425

426

427 SExpr *Definition;

428

429

430 const ValueDecl *Cvdecl = nullptr;

431};

432

433

434

436public:

442

445

446 static bool classof(const SExpr *E) { return E->opcode() == COP_Future; }

447

448

450

451

453

454

456 switch (Status) {

458 return force();

460 return nullptr;

462 return Result;

463 }

464 }

465

466 template

467 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

468 assert(Result && "Cannot traverse Future that has not been forced.");

469 return Vs.traverse(Result, Ctx);

470 }

471

472 template

474 if (!Result || ->Result)

475 return Cmp.comparePointers(this, E);

476 return Cmp.compare(Result, E->Result);

477 }

478

479private:

481

483 SExpr *Result = nullptr;

484};

485

486

488public:

491

492

493

495

496 static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; }

497

498 template

499 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

500 return Vs.reduceUndefined(*this);

501 }

502

503 template

505 return Cmp.trueResult();

506 }

507

508private:

509 const Stmt *Cstmt;

510};

511

512

514public:

517

518 static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; }

519

520 template typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

521 return Vs.reduceWildcard(*this);

522 }

523

524 template

526 return Cmp.trueResult();

527 }

528};

529

530template class LiteralT;

531

532

534public:

536 : SExpr(COP_Literal), ValType(ValueType::getValueType()), Cexpr(C) {}

539

540 static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; }

541

542

544

546

548 return *static_cast<const LiteralT*>(this);

549 }

552 }

553

554 template typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx);

555

556 template

558

559 return Cmp.trueResult();

560 }

561

562private:

564 const Expr *Cexpr = nullptr;

565};

566

567

568template

570public:

573

574

575

577

580

581private:

582 T Val;

583};

584

585template

587 if (Cexpr)

588 return Vs.reduceLiteral(*this);

589

590 switch (ValType.Base) {

592 break;

594 return Vs.reduceLiteralT(as());

596 switch (ValType.Size) {

599 return Vs.reduceLiteralT(as<int8_t>());

600 else

601 return Vs.reduceLiteralT(as<uint8_t>());

604 return Vs.reduceLiteralT(as<int16_t>());

605 else

606 return Vs.reduceLiteralT(as<uint16_t>());

609 return Vs.reduceLiteralT(as<int32_t>());

610 else

611 return Vs.reduceLiteralT(as<uint32_t>());

614 return Vs.reduceLiteralT(as<int64_t>());

615 else

616 return Vs.reduceLiteralT(as<uint64_t>());

617 default:

618 break;

619 }

620 }

622 switch (ValType.Size) {

624 return Vs.reduceLiteralT(as());

626 return Vs.reduceLiteralT(as());

627 default:

628 break;

629 }

630 }

632 return Vs.reduceLiteralT(as());

634 return Vs.reduceLiteralT(as<void*>());

636 break;

637 }

638 return Vs.reduceLiteral(*this);

639}

640

641

642

644public:

647

648 static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; }

649

650

653

654 template

655 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

656 return Vs.reduceLiteralPtr(*this);

657 }

658

659 template

661 if (!Cvdecl || ->Cvdecl)

662 return Cmp.comparePointers(this, E);

663 return Cmp.comparePointers(Cvdecl, E->Cvdecl);

664 }

665

666private:

668};

669

670

671

672

674public:

676 : SExpr(COP_Function), VarDecl(Vd), Body(Bd) {

678 }

679

683 }

684

685 static bool classof(const SExpr *E) { return E->opcode() == COP_Function; }

686

689

692

693 template

694 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

695

697

699 auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx));

701 return Vs.reduceFunction(*this, Nvd, E1);

702 }

703

704 template

706 typename C::CType Ct =

707 Cmp.compare(VarDecl->definition(), E->VarDecl->definition());

708 if (Cmp.notTrue(Ct))

709 return Ct;

710 Cmp.enterScope(variableDecl(), E->variableDecl());

711 Ct = Cmp.compare(body(), E->body());

712 Cmp.leaveScope();

713 return Ct;

714 }

715

716private:

719};

720

721

722

723

725public:

727 : SExpr(COP_SFunction), VarDecl(Vd), Body(B) {

728 assert(Vd->Definition == nullptr);

730 Vd->Definition = this;

731 }

732

735 assert(Vd->Definition == nullptr);

737 Vd->Definition = this;

738 }

739

740 static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; }

741

744

747

748 template

749 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

750

751

752

754 auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx));

756

757 return Vs.reduceSFunction(*this, Nvd, E1);

758 }

759

760 template

762 Cmp.enterScope(variableDecl(), E->variableDecl());

763 typename C::CType Ct = Cmp.compare(body(), E->body());

764 Cmp.leaveScope();

765 return Ct;

766 }

767

768private:

771};

772

773

775public:

778 : SExpr(C), ReturnType(T), Body(B) {}

779

780 static bool classof(const SExpr *E) { return E->opcode() == COP_Code; }

781

784

787

788 template

789 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

790 auto Nt = Vs.traverse(ReturnType, Vs.typeCtx(Ctx));

791 auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx));

792 return Vs.reduceCode(*this, Nt, Nb);

793 }

794

795 template

797 typename C::CType Ct = Cmp.compare(returnType(), E->returnType());

798 if (Cmp.notTrue(Ct))

799 return Ct;

800 return Cmp.compare(body(), E->body());

801 }

802

803private:

804 SExpr* ReturnType;

806};

807

808

810public:

813 : SExpr(C), Range(R), Body(B) {}

814

815 static bool classof(const SExpr *E) { return E->opcode() == COP_Field; }

816

819

822

823 template

824 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

825 auto Nr = Vs.traverse(Range, Vs.typeCtx(Ctx));

826 auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx));

827 return Vs.reduceField(*this, Nr, Nb);

828 }

829

830 template

832 typename C::CType Ct = Cmp.compare(range(), E->range());

833 if (Cmp.notTrue(Ct))

834 return Ct;

835 return Cmp.compare(body(), E->body());

836 }

837

838private:

841};

842

843

844

845

846

847

849public:

852 : SExpr(A), Fun(F), Arg(Ar) {}

853

854 static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; }

855

858

861

862 template

863 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

864 auto Nf = Vs.traverse(Fun, Vs.subExprCtx(Ctx));

865 auto Na = Vs.traverse(Arg, Vs.subExprCtx(Ctx));

866 return Vs.reduceApply(*this, Nf, Na);

867 }

868

869 template

871 typename C::CType Ct = Cmp.compare(fun(), E->fun());

872 if (Cmp.notTrue(Ct))

873 return Ct;

874 return Cmp.compare(arg(), E->arg());

875 }

876

877private:

880};

881

882

884public:

887 : SExpr(A), Sfun(Sf), Arg(Ar) {}

888

889 static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; }

890

893

894 SExpr *arg() { return Arg ? Arg : Sfun; }

895 const SExpr *arg() const { return Arg ? Arg : Sfun; }

896

898

899 template

900 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

901 auto Nf = Vs.traverse(Sfun, Vs.subExprCtx(Ctx));

902 typename V::R_SExpr Na = Arg ? Vs.traverse(Arg, Vs.subExprCtx(Ctx))

903 : nullptr;

904 return Vs.reduceSApply(*this, Nf, Na);

905 }

906

907 template

909 typename C::CType Ct = Cmp.compare(sfun(), E->sfun());

910 if (Cmp.notTrue(Ct) || ( arg () && ->arg()))

911 return Ct;

912 return Cmp.compare(arg(), E->arg());

913 }

914

915private:

918};

919

920

922public:

924 : SExpr(COP_Project), Rec(R), Cvdecl(Cvd) {

925 assert(Cvd && "ValueDecl must not be null");

926 }

927

928 static bool classof(const SExpr *E) { return E->opcode() == COP_Project; }

929

932

934

936

938 if (b) Flags |= 0x01;

939 else Flags &= 0xFFFE;

940 }

941

944 return Cvdecl->getName();

945 if (!SlotName) {

946 SlotName = "";

947 llvm::raw_string_ostream OS(*SlotName);

949 }

950 return *SlotName;

951 }

952

953 template

954 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

955 auto Nr = Vs.traverse(Rec, Vs.subExprCtx(Ctx));

956 return Vs.reduceProject(*this, Nr);

957 }

958

959 template

961 typename C::CType Ct = Cmp.compare(record(), E->record());

962 if (Cmp.notTrue(Ct))

963 return Ct;

964 return Cmp.comparePointers(Cvdecl, E->Cvdecl);

965 }

966

967private:

969 mutable std::optionalstd::string SlotName;

971};

972

973

975public:

979

980 static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }

981

984

986

987 template

988 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

989 auto Nt = Vs.traverse(Target, Vs.subExprCtx(Ctx));

990 return Vs.reduceCall(*this, Nt);

991 }

992

993 template

995 return Cmp.compare(target(), E->target());

996 }

997

998private:

1001};

1002

1003

1005public:

1010

1013

1014 static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }

1015

1017

1020

1021 template

1022 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

1023 auto Nd = Vs.traverse(Dtype, Vs.declCtx(Ctx));

1024 return Vs.reduceAlloc(*this, Nd);

1025 }

1026

1027 template

1029 typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind());

1030 if (Cmp.notTrue(Ct))

1031 return Ct;

1032 return Cmp.compare(dataType(), E->dataType());

1033 }

1034

1035private:

1037};

1038

1039

1041public:

1044

1045 static bool classof(const SExpr *E) { return E->opcode() == COP_Load; }

1046

1049

1050 template

1051 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

1052 auto Np = Vs.traverse(Ptr, Vs.subExprCtx(Ctx));

1053 return Vs.reduceLoad(*this, Np);

1054 }

1055

1056 template

1058 return Cmp.compare(pointer(), E->pointer());

1059 }

1060

1061private:

1063};

1064

1065

1066

1068public:

1071

1072 static bool classof(const SExpr *E) { return E->opcode() == COP_Store; }

1073

1076

1079

1080 template

1081 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

1082 auto Np = Vs.traverse(Dest, Vs.subExprCtx(Ctx));

1083 auto Nv = Vs.traverse(Source, Vs.subExprCtx(Ctx));

1084 return Vs.reduceStore(*this, Np, Nv);

1085 }

1086

1087 template

1089 typename C::CType Ct = Cmp.compare(destination(), E->destination());

1090 if (Cmp.notTrue(Ct))

1091 return Ct;

1092 return Cmp.compare(source(), E->source());

1093 }

1094

1095private:

1098};

1099

1100

1101

1103public:

1106 : SExpr(E), Array(A), Index(N) {}

1107

1108 static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; }

1109

1112

1115

1116 template

1117 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

1118 auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));

1119 auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));

1120 return Vs.reduceArrayIndex(*this, Na, Ni);

1121 }

1122

1123 template

1125 typename C::CType Ct = Cmp.compare(array(), E->array());

1126 if (Cmp.notTrue(Ct))

1127 return Ct;

1128 return Cmp.compare(index(), E->index());

1129 }

1130

1131private:

1134};

1135

1136

1137

1138

1140public:

1143 : SExpr(E), Array(A), Index(N) {}

1144

1145 static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; }

1146

1149

1152

1153 template

1154 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

1155 auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));

1156 auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));

1157 return Vs.reduceArrayAdd(*this, Na, Ni);

1158 }

1159

1160 template

1162 typename C::CType Ct = Cmp.compare(array(), E->array());

1163 if (Cmp.notTrue(Ct))

1164 return Ct;

1165 return Cmp.compare(index(), E->index());

1166 }

1167

1168private:

1171};

1172

1173

1174

1176public:

1179 }

1180

1182

1183 static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; }

1184

1187 }

1188

1191

1192 template

1193 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

1194 auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));

1195 return Vs.reduceUnaryOp(*this, Ne);

1196 }

1197

1198 template

1200 typename C::CType Ct =

1201 Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode());

1202 if (Cmp.notTrue(Ct))

1203 return Ct;

1204 return Cmp.compare(expr(), E->expr());

1205 }

1206

1207private:

1209};

1210

1211

1212

1214public:

1216 : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) {

1218 }

1219

1221 : SExpr(B), Expr0(E0), Expr1(E1) {

1223 }

1224

1225 static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; }

1226

1229 }

1230

1233

1236

1237 template

1238 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

1239 auto Ne0 = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));

1240 auto Ne1 = Vs.traverse(Expr1, Vs.subExprCtx(Ctx));

1241 return Vs.reduceBinaryOp(*this, Ne0, Ne1);

1242 }

1243

1244 template

1246 typename C::CType Ct =

1247 Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode());

1248 if (Cmp.notTrue(Ct))

1249 return Ct;

1250 Ct = Cmp.compare(expr0(), E->expr0());

1251 if (Cmp.notTrue(Ct))

1252 return Ct;

1253 return Cmp.compare(expr1(), E->expr1());

1254 }

1255

1256private:

1259};

1260

1261

1262

1263

1265public:

1268

1269 static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; }

1270

1273 }

1274

1277

1278 template

1279 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

1280 auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));

1281 return Vs.reduceCast(*this, Ne);

1282 }

1283

1284 template

1286 typename C::CType Ct =

1287 Cmp.compareIntegers(castOpcode(), E->castOpcode());

1288 if (Cmp.notTrue(Ct))

1289 return Ct;

1290 return Cmp.compare(expr(), E->expr());

1291 }

1292

1293private:

1295};

1296

1297class SCFG;

1298

1299

1300

1301

1303public:

1305

1306

1307

1308

1310 PH_MultiVal = 0,

1311 PH_SingleVal,

1314

1318

1319 static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; }

1320

1323

1326

1327

1329

1330

1332

1333 template

1334 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

1335 typename V::template Container<typename V::R_SExpr>

1336 Nvs(Vs, Values.size());

1337

1338 for (const auto *Val : Values)

1339 Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) );

1340 return Vs.reducePhi(*this, Nvs);

1341 }

1342

1343 template

1345

1346 return Cmp.comparePointers(this, E);

1347 }

1348

1349private:

1351 const ValueDecl* Cvdecl = nullptr;

1352};

1353

1354

1356protected:

1359

1360public:

1362 return E->opcode() >= COP_Goto && E->opcode() <= COP_Return;

1363 }

1364

1365

1367};

1368

1369

1370

1371

1372

1373

1375public:

1377 : Terminator(COP_Goto), TargetBlock(B), Index(I) {}

1379 : Terminator(COP_Goto), TargetBlock(B), Index(I) {}

1380

1381 static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; }

1382

1385

1386

1387 unsigned index() const { return Index; }

1388

1389

1391

1392 template

1393 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

1394 BasicBlock *Ntb = Vs.reduceBasicBlockRef(TargetBlock);

1395 return Vs.reduceGoto(*this, Ntb);

1396 }

1397

1398 template

1400

1401 return Cmp.comparePointers(this, E);

1402 }

1403

1404private:

1406 unsigned Index;

1407};

1408

1409

1410

1411

1413public:

1415 : Terminator(COP_Branch), Condition(C) {

1416 Branches[0] = T;

1417 Branches[1] = E;

1418 }

1419

1422 Branches[0] = T;

1423 Branches[1] = E;

1424 }

1425

1426 static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; }

1427

1430

1433

1436

1437

1439

1440 template

1441 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

1442 auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx));

1443 BasicBlock *Ntb = Vs.reduceBasicBlockRef(Branches[0]);

1444 BasicBlock *Nte = Vs.reduceBasicBlockRef(Branches[1]);

1445 return Vs.reduceBranch(*this, Nc, Ntb, Nte);

1446 }

1447

1448 template

1450

1451 return Cmp.comparePointers(this, E);

1452 }

1453

1454private:

1455 SExpr *Condition;

1457};

1458

1459

1460

1462public:

1465

1466 static bool classof(const SExpr *E) { return E->opcode() == COP_Return; }

1467

1468

1470

1473

1474 template

1475 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

1476 auto Ne = Vs.traverse(Retval, Vs.subExprCtx(Ctx));

1477 return Vs.reduceReturn(*this, Ne);

1478 }

1479

1480 template

1482 return Cmp.compare(Retval, E->Retval);

1483 }

1484

1485private:

1487};

1488

1491 case COP_Goto: return cast(this)->successors();

1492 case COP_Branch: return cast(this)->successors();

1493 case COP_Return: return cast(this)->successors();

1494 default:

1495 return {};

1496 }

1497}

1498

1499

1500

1501

1502

1503

1505public:

1508

1509

1510

1511

1512

1515

1516

1518

1519

1521

1523

1527 }

1528

1532 }

1533 };

1534

1536 : SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false) {}

1539 : SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false),

1540 Args(std::move(As)), Instrs(std::move(Is)), TermInstr(T) {}

1541

1542 static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; }

1543

1544

1546

1547

1550

1551 const SCFG* cfg() const { return CFGPtr; }

1553

1556

1559

1562

1563

1564

1565

1568

1571

1574

1576

1579 }

1580

1583 }

1584

1585

1589 }

1590

1591

1595 }

1596

1597

1598

1600

1601

1603

1604

1606

1607

1609

1610

1612 auto I = llvm::find(Predecessors, BB);

1613 return std::distance(Predecessors.cbegin(), I);

1614 }

1615

1616 template

1617 typename V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx) {

1618 typename V::template Container<SExpr*> Nas(Vs, Args.size());

1619 typename V::template Container<SExpr*> Nis(Vs, Instrs.size());

1620

1621

1622 Vs.enterBasicBlock(*this);

1623

1624 for (const auto *E : Args) {

1625 auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx));

1626 Nas.push_back(Ne);

1627 }

1628 for (const auto *E : Instrs) {

1629 auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx));

1630 Nis.push_back(Ne);

1631 }

1632 auto Nt = Vs.traverse(TermInstr, Ctx);

1633

1634

1635 Vs.exitBasicBlock(*this);

1636

1637 return Vs.reduceBasicBlock(*this, Nas, Nis, Nt);

1638 }

1639

1640 template

1642

1643 return Cmp.comparePointers(this, E);

1644 }

1645

1646private:

1648

1649

1650 unsigned renumberInstrs(unsigned id);

1651

1654 void computeDominator();

1655 void computePostDominator();

1656

1657

1659

1660

1661 SCFG *CFGPtr = nullptr;

1662

1663

1664 unsigned BlockID : 31;

1665

1666

1668

1669

1671

1672

1674

1675

1677

1678

1680

1681

1683

1684

1686};

1687

1688

1689

1690

1692public:

1696

1698 : SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks) {

1701 auto *V = new (A) Phi();

1704 add(Entry);

1705 add(Exit);

1706 }

1707

1709 : SExpr(COP_SCFG), Arena(Cfg.Arena), Blocks(std::move(Ba)) {

1710

1711 }

1712

1713 static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; }

1714

1715

1716 bool valid() const { return Entry && Exit && Blocks.size() > 0; }

1717

1718

1719

1720

1721 bool normal() const { return Normal; }

1722

1725

1728

1731

1736

1737

1738

1740

1741

1742

1743

1745

1747 assert(BB->CFGPtr == nullptr);

1748 BB->CFGPtr = this;

1751 }

1752

1755

1757

1758 template

1759 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

1760 Vs.enterCFG(*this);

1761 typename V::template Container<BasicBlock *> Bbs(Vs, Blocks.size());

1762

1763 for (const auto *B : Blocks) {

1764 Bbs.push_back( B->traverse(Vs, Vs.subExprCtx(Ctx)) );

1765 }

1766 Vs.exitCFG(*this);

1767 return Vs.reduceSCFG(*this, Bbs);

1768 }

1769

1770 template

1772

1773 return Cmp.comparePointers(this, E);

1774 }

1775

1776private:

1777

1778 void renumberInstrs();

1779

1784 unsigned NumInstructions = 0;

1785 bool Normal = false;

1786};

1787

1788

1789

1791public:

1794

1795 static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; }

1796

1797 StringRef name() const { return Name; }

1798

1799 template

1800 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

1801 return Vs.reduceIdentifier(*this);

1802 }

1803

1804 template

1806 return Cmp.compareStrings(name(), E->name());

1807 }

1808

1809private:

1810 StringRef Name;

1811};

1812

1813

1814

1816public:

1818 : SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E) {}

1820 : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E) {}

1821

1822 static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; }

1823

1826

1829

1832

1833 template

1834 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

1835 auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx));

1836 auto Nt = Vs.traverse(ThenExpr, Vs.subExprCtx(Ctx));

1837 auto Ne = Vs.traverse(ElseExpr, Vs.subExprCtx(Ctx));

1838 return Vs.reduceIfThenElse(*this, Nc, Nt, Ne);

1839 }

1840

1841 template

1843 typename C::CType Ct = Cmp.compare(condition(), E->condition());

1844 if (Cmp.notTrue(Ct))

1845 return Ct;

1846 Ct = Cmp.compare(thenExpr(), E->thenExpr());

1847 if (Cmp.notTrue(Ct))

1848 return Ct;

1849 return Cmp.compare(elseExpr(), E->elseExpr());

1850 }

1851

1852private:

1853 SExpr* Condition;

1854 SExpr* ThenExpr;

1855 SExpr* ElseExpr;

1856};

1857

1858

1859

1861public:

1864 }

1865

1868 }

1869

1870 static bool classof(const SExpr *E) { return E->opcode() == COP_Let; }

1871

1874

1877

1878 template

1879 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {

1880

1882

1884 auto E1 = Vs.traverse(Body, Ctx);

1886 return Vs.reduceLet(*this, Nvd, E1);

1887 }

1888

1889 template

1891 typename C::CType Ct =

1892 Cmp.compare(VarDecl->definition(), E->VarDecl->definition());

1893 if (Cmp.notTrue(Ct))

1894 return Ct;

1895 Cmp.enterScope(variableDecl(), E->variableDecl());

1896 Ct = Cmp.compare(body(), E->body());

1897 Cmp.leaveScope();

1898 return Ct;

1899 }

1900

1901private:

1904};

1905

1909

1910}

1911}

1912

1913}

1914

1915#endif

llvm::DenseSet< const void * > Visited

Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified.

llvm::MachO::Target Target

static std::string getName(const CallEvent &Call)

__device__ __2f16 float __ockl_bool s

CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).

bool isIdentifier() const

Predicate functions for querying what type of name this is.

This represents one expression.

StringRef getName() const

Get the name of identifier for this declaration as a StringRef.

DeclarationName getDeclName() const

Get the actual, stored name of the declaration, which may be a special name.

virtual void printName(raw_ostream &OS, const PrintingPolicy &Policy) const

Pretty-print the unqualified name of this declaration.

Stmt - This represents one statement.

Represent the declaration of a variable (in which case it is an lvalue) a function (in which case it ...

Represents a variable declaration or definition.

@ Definition

This declaration is definitely a definition.

Allocate memory for a new value on the heap or stack.

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

static bool classof(const SExpr *E)

Alloc(const Alloc &A, SExpr *Dt)

C::CType compare(const Alloc *E, C &Cmp) const

Alloc(SExpr *D, AllocKind K)

const SExpr * dataType() const

Apply an argument to a function.

const SExpr * arg() const

Apply(const Apply &A, SExpr *F, SExpr *Ar)

Apply(SExpr *F, SExpr *A)

const SExpr * fun() const

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

static bool classof(const SExpr *E)

C::CType compare(const Apply *E, C &Cmp) const

Pointer arithmetic, restricted to arrays only.

const SExpr * array() const

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

ArrayAdd(SExpr *A, SExpr *N)

ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N)

C::CType compare(const ArrayAdd *E, C &Cmp) const

const SExpr * index() const

static bool classof(const SExpr *E)

If p is a reference to an array, then p[i] is a reference to the i'th element of the array.

ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N)

static bool classof(const SExpr *E)

ArrayIndex(SExpr *A, SExpr *N)

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

C::CType compare(const ArrayIndex *E, C &Cmp) const

const SExpr * array() const

const SExpr * index() const

A basic block is part of an SCFG.

unsigned addPredecessor(BasicBlock *Pred)

BasicBlock(BasicBlock &B, MemRegionRef A, InstrArray &&As, InstrArray &&Is, Terminator *T)

int blockID() const

Returns the block ID. Every block has a unique ID in the CFG.

const InstrArray & arguments() const

const InstrArray & instructions() const

bool Dominates(const BasicBlock &Other)

void reserveInstructions(unsigned Nins)

const Terminator * terminator() const

const BlockArray & predecessors() const

size_t numSuccessors() const

ArrayRef< BasicBlock * > successors() const

void reserveArguments(unsigned Nargs)

C::CType compare(const BasicBlock *E, C &Cmp) const

ArrayRef< BasicBlock * > successors()

void addArgument(Phi *V)

Add a new argument.

Terminator * terminator()

size_t numPredecessors() const

Returns the number of predecessors.

bool PostDominates(const BasicBlock &Other)

BasicBlock(MemRegionRef A)

V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx)

static bool classof(const SExpr *E)

InstrArray & instructions()

void reservePredecessors(unsigned NumPreds)

unsigned findPredecessorIndex(const BasicBlock *BB) const

Return the index of BB, or Predecessors.size if BB is not a predecessor.

void setTerminator(Terminator *E)

BlockArray & predecessors()

Returns a list of predecessors.

const BasicBlock * parent() const

void addInstruction(SExpr *V)

Add a new instruction.

Simple arithmetic binary operations, e.g.

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1)

const SExpr * expr0() const

static bool classof(const SExpr *E)

BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1)

TIL_BinaryOpcode binaryOpcode() const

C::CType compare(const BinaryOp *E, C &Cmp) const

const SExpr * expr1() const

A conditional branch to two other blocks.

const SExpr * condition() const

Branch(SExpr *C, BasicBlock *T, BasicBlock *E)

const BasicBlock * elseBlock() const

C::CType compare(const Branch *E, C &Cmp) const

Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E)

static bool classof(const SExpr *E)

ArrayRef< BasicBlock * > successors() const

Return the list of basic blocks that this terminator can branch to.

const BasicBlock * thenBlock() const

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

Call a function (after all arguments have been applied).

const SExpr * target() const

Call(const Call &C, SExpr *T)

Call(SExpr *T, const CallExpr *Ce=nullptr)

C::CType compare(const Call *E, C &Cmp) const

static bool classof(const SExpr *E)

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

const CallExpr * clangCallExpr() const

C::CType compare(const Cast *E, C &Cmp) const

const SExpr * expr() const

Cast(TIL_CastOpcode Op, SExpr *E)

static bool classof(const SExpr *E)

Cast(const Cast &C, SExpr *E)

TIL_CastOpcode castOpcode() const

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

A block of code – e.g. the body of a function.

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

static bool classof(const SExpr *E)

const SExpr * returnType() const

C::CType compare(const Code *E, C &Cmp) const

const SExpr * body() const

Code(const Code &C, SExpr *T, SExpr *B)

A typed, writable location in memory.

const SExpr * range() const

const SExpr * body() const

static bool classof(const SExpr *E)

Field(SExpr *R, SExpr *B)

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

C::CType compare(const Field *E, C &Cmp) const

Field(const Field &C, SExpr *R, SExpr *B)

const SExpr * body() const

Function(const Function &F, Variable *Vd, SExpr *Bd)

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

const Variable * variableDecl() const

C::CType compare(const Function *E, C &Cmp) const

static bool classof(const SExpr *E)

Variable * variableDecl()

Function(Variable *Vd, SExpr *Bd)

Placeholder for an expression that has not yet been created.

C::CType compare(const Future *E, C &Cmp) const

static bool classof(const SExpr *E)

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

SExpr * maybeGetResult() const

virtual SExpr * compute()

Jump to another basic block.

BasicBlock * targetBlock()

ArrayRef< BasicBlock * > successors() const

Return the list of basic blocks that this terminator can branch to.

Goto(const Goto &G, BasicBlock *B, unsigned I)

C::CType compare(const Goto *E, C &Cmp) const

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

Goto(BasicBlock *B, unsigned I)

unsigned index() const

Returns the index into the.

static bool classof(const SExpr *E)

const BasicBlock * targetBlock() const

C::CType compare(const Identifier *E, C &Cmp) const

Identifier(const Identifier &)=default

static bool classof(const SExpr *E)

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

An if-then-else expression.

const SExpr * condition() const

IfThenElse(const IfThenElse &I, SExpr *C, SExpr *T, SExpr *E)

const SExpr * thenExpr() const

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

C::CType compare(const IfThenElse *E, C &Cmp) const

static bool classof(const SExpr *E)

const SExpr * elseExpr() const

IfThenElse(SExpr *C, SExpr *T, SExpr *E)

Let(const Let &L, Variable *Vd, SExpr *Bd)

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

const Variable * variableDecl() const

C::CType compare(const Let *E, C &Cmp) const

Let(Variable *Vd, SExpr *Bd)

static bool classof(const SExpr *E)

const SExpr * body() const

Variable * variableDecl()

A Literal pointer to an object allocated in memory.

const ValueDecl * clangDecl() const

C::CType compare(const LiteralPtr *E, C &Cmp) const

LiteralPtr(const LiteralPtr &)=default

void setClangDecl(const ValueDecl *VD)

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

LiteralPtr(const ValueDecl *D)

static bool classof(const SExpr *E)

LiteralT & operator=(const LiteralT< T > &)=delete

LiteralT(const LiteralT< T > &L)

Literal(const Literal &)=default

static bool classof(const SExpr *E)

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

const LiteralT< T > & as() const

ValueType valueType() const

C::CType compare(const Literal *E, C &Cmp) const

const Expr * clangExpr() const

Load a value from memory.

const SExpr * pointer() const

C::CType compare(const Load *E, C &Cmp) const

static bool classof(const SExpr *E)

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

Load(const Load &L, SExpr *P)

Phi Node, for code in SSA form.

SimpleArray< SExpr * > ValArray

static bool classof(const SExpr *E)

C::CType compare(const Phi *E, C &Cmp) const

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

const ValueDecl * clangDecl() const

Return the clang declaration of the variable for this Phi node, if any.

void setClangDecl(const ValueDecl *Cvd)

Set the clang variable associated with this Phi node.

Phi(MemRegionRef A, unsigned Nvals)

Phi(const Phi &P, ValArray &&Vs)

const ValArray & values() const

Project a named slot from a C++ struct or class.

const ValueDecl * clangDecl() const

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

const SExpr * record() const

static bool classof(const SExpr *E)

C::CType compare(const Project *E, C &Cmp) const

Project(SExpr *R, const ValueDecl *Cvd)

StringRef slotName() const

Return from the enclosing function, passing the return value to the caller.

Return(const Return &R, SExpr *Rval)

const SExpr * returnValue() const

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

ArrayRef< BasicBlock * > successors() const

Return an empty list.

static bool classof(const SExpr *E)

C::CType compare(const Return *E, C &Cmp) const

Apply a self-argument to a self-applicable function.

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

const SExpr * sfun() const

bool isDelegation() const

SApply(SExpr *Sf, SExpr *A=nullptr)

const SExpr * arg() const

C::CType compare(const SApply *E, C &Cmp) const

SApply(SApply &A, SExpr *Sf, SExpr *Ar=nullptr)

static bool classof(const SExpr *E)

An SCFG is a control-flow graph.

void setEntry(BasicBlock *BB)

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

const BasicBlock * entry() const

void setExit(BasicBlock *BB)

C::CType compare(const SCFG *E, C &Cmp) const

bool normal() const

Return true if this CFG has been normalized.

static bool classof(const SExpr *E)

const_iterator begin() const

const_iterator end() const

const_iterator cend() const

const BasicBlock * exit() const

const_iterator cbegin() const

unsigned numInstructions()

Return the total number of instructions in the CFG.

size_t numBlocks() const

Return the number of blocks in the CFG.

bool valid() const

Return true if this CFG is valid.

SimpleArray< BasicBlock * > BlockArray

Base class for AST nodes in the typed intermediate language.

BasicBlock * block() const

Returns the block, if this is an instruction in a basic block, otherwise returns null.

void setID(BasicBlock *B, unsigned id)

Set the basic block and instruction ID for this expression.

SExpr & operator=(const SExpr &)=delete

TIL_Opcode opcode() const

unsigned id() const

Returns the instruction ID for this expression.

A self-applicable function.

static bool classof(const SExpr *E)

Variable * variableDecl()

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

SFunction(Variable *Vd, SExpr *B)

SFunction(const SFunction &F, Variable *Vd, SExpr *B)

const Variable * variableDecl() const

const SExpr * body() const

C::CType compare(const SFunction *E, C &Cmp) const

void reserve(size_t Ncp, MemRegionRef A)

const_iterator cend() const

void push_back(const T &Elem)

const_iterator cbegin() const

void reserveCheck(size_t N, MemRegionRef A)

const BasicBlock * * const_iterator

Store(SExpr *P, SExpr *V)

C::CType compare(const Store *E, C &Cmp) const

const SExpr * destination() const

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

Store(const Store &S, SExpr *P, SExpr *V)

const SExpr * source() const

static bool classof(const SExpr *E)

Base class for basic block terminators: Branch, Goto, and Return.

ArrayRef< BasicBlock * > successors() const

Return the list of basic blocks that this terminator can branch to.

Terminator(const SExpr &E)

static bool classof(const SExpr *E)

Terminator(TIL_Opcode Op)

Simple arithmetic unary operations, e.g.

static bool classof(const SExpr *E)

const SExpr * expr() const

UnaryOp(const UnaryOp &U, SExpr *E)

TIL_UnaryOpcode unaryOpcode() const

C::CType compare(const UnaryOp *E, C &Cmp) const

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

UnaryOp(TIL_UnaryOpcode Op, SExpr *E)

Placeholder for expressions that cannot be represented in the TIL.

C::CType compare(const Undefined *E, C &Cmp) const

Undefined & operator=(const Undefined &)=delete

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

Undefined(const Stmt *S=nullptr)

static bool classof(const SExpr *E)

Undefined(const Undefined &U)

Variable(SExpr *D, const ValueDecl *Cvd=nullptr)

void setName(StringRef S)

Variable(const Variable &Vd, SExpr *D)

C::CType compare(const Variable *E, C &Cmp) const

void setDefinition(SExpr *E)

StringRef name() const

Return the name of the variable, if any.

static bool classof(const SExpr *E)

Variable(StringRef s, SExpr *D=nullptr)

SExpr * definition()

Return the definition of the variable.

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

const SExpr * definition() const

const ValueDecl * clangDecl() const

Return the clang declaration for this variable, if any.

void setClangDecl(const ValueDecl *VD)

@ VK_SFun

SFunction (self) parameter.

@ VK_Fun

Function parameter.

void setKind(VariableKind K)

VariableKind kind() const

Return the kind of variable (let, function param, or self)

Placeholder for a wildcard that matches any other expression.

V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)

static bool classof(const SExpr *E)

C::CType compare(const Wildcard *E, C &Cmp) const

Wildcard(const Wildcard &)=default

bool isTrivial(const SExpr *E)

TIL_UnaryOpcode

Opcode for unary arithmetic operations.

void simplifyIncompleteArg(til::Phi *Ph)

const TIL_BinaryOpcode BOP_Min

const TIL_UnaryOpcode UOP_Min

StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op)

Return the name of a binary opcode.

StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op)

Return the name of a unary opcode.

TIL_CastOpcode

Opcode for cast operations.

const TIL_CastOpcode CAST_Max

TIL_BinaryOpcode

Opcode for binary arithmetic operations.

SExpr * simplifyToCanonicalVal(SExpr *E)

const TIL_BinaryOpcode BOP_Max

const TIL_CastOpcode CAST_Min

const TIL_UnaryOpcode UOP_Max

const SExpr * getCanonicalVal(const SExpr *E)

TIL_Opcode

Enum for the different distinct classes of SExpr.

The JSON file list parser is used to communicate input to InstallAPI.

const FunctionProtoType * T

@ Other

Other implicit parameter.

bool isParentOf(const TopologyNode &OtherNode)

bool isParentOfOrEqual(const TopologyNode &OtherNode)

ValueTypes are data types that can actually be held in registers.

ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS)

static ValueType getValueType()

static SizeType getSizeType(unsigned nbytes)