IRSimilarityIdentifier.cpp Source File (original) (raw)

24using namespace llvm;

27namespace llvm {

31 cl::desc("disable similarity matching, and outlining, "

32 "across branches for debugging purposes."));

37 cl::desc("disable outlining indirect calls."));

41 cl::desc("only allow matching call instructions if the "

42 "name and type signature match."));

46 cl::desc("Don't match or outline intrinsics"));

47}

61 if (Predicate != C->getPredicate())

63 }

67 for (Use &OI : Inst->operands()) {

72 continue;

73 }

76 }

82}

94 BBNumIt = BasicBlockToInteger.find(BI->getParent());

95 assert(BBNumIt != BasicBlockToInteger.end() &&

96 "Could not find location for BasicBlock!");

98 int CurrentBlockNumber = static_cast<int>(BBNumIt->second);

103 assert(BBNumIt != BasicBlockToInteger.end() &&

104 "Could not find number for BasicBlock!");

105 int OtherBlockNumber = static_cast<int>(BBNumIt->second);

106

107 int Relative = OtherBlockNumber - CurrentBlockNumber;

109 }

110}

111

114 isa(Inst)) && "Instruction must be branch or PHINode");

115

118 std::next(OperVals.begin(), BI->isConditional() ? 1 : 0),

120 );

121

124 std::next(OperVals.begin(), PN->getNumIncomingValues()),

126 );

127

129}

130

133 assert(CI && "Instruction must be call");

134

137

138

139

142

143

147

148 else

150

151 return;

152 }

153

156}

157

161

164

165 BBNumIt = BasicBlockToInteger.find(PN->getParent());

166 assert(BBNumIt != BasicBlockToInteger.end() &&

167 "Could not find location for BasicBlock!");

168

169 int CurrentBlockNumber = static_cast<int>(BBNumIt->second);

170

171

172

175 BBNumIt = BasicBlockToInteger.find(Incoming);

176 assert(BBNumIt != BasicBlockToInteger.end() &&

177 "Could not find number for BasicBlock!");

178 int OtherBlockNumber = static_cast<int>(BBNumIt->second);

179

180 int Relative = OtherBlockNumber - CurrentBlockNumber;

182 }

183}

184

200

203 "Can only get a predicate from a compare instruction");

204

207

209}

210

213 "Can only get a name from a call instruction");

214

216

218}

219

222

223 if (.Legal || .Legal)

224 return false;

225

226

227

228 if (.Inst->isSameOperationAs(B.Inst)) {

229

230

231

233

234 if (A.getPredicate() != B.getPredicate())

235 return false;

236

237

238

239 auto ZippedTypes = zip(A.OperVals, B.OperVals);

240

242 ZippedTypes, [](std::tuple<llvm::Value *, llvm::Value *> R) {

243 return std::get<0>(R)->getType() == std::get<1>(R)->getType();

244 });

245 }

246

247 return false;

248 }

249

250

251

252

255

256

257

258 if (GEP->isInBounds() != OtherGEP->isInBounds())

259 return false;

260

261 auto ZippedOperands = zip(GEP->indices(), OtherGEP->indices());

262

263

264

265

267 [](std::tuple<llvm::Use &, llvm::Use &> R) {

268 return std::get<0>(R) == std::get<1>(R);

269 });

270 }

271

272

273

274

276 if (A.getCalleeName() != B.getCalleeName())

277 return false;

278 }

279

281 A.RelativeBlockLocations.size() != B.RelativeBlockLocations.size())

282 return false;

283

284 return true;

285}

286

287

288

290 BasicBlock &BB, std::vector<IRInstructionData *> &InstrList,

291 std::vector &IntegerMapping) {

293

294 std::vector IntegerMappingForBB;

295 std::vector<IRInstructionData *> InstrListForBB;

296

301 break;

304 break;

307 break;

308 }

309 }

310

314 this->IDL->push_back(*ID);

317}

318

319

320

323 std::vector<IRInstructionData *> &InstrListForBB) {

324

325

327

328

329

333

334

335

337 InstrListForBB.push_back(ID);

338

341

344

347

348

349 bool WasInserted;

351 ResultIt;

352 std::tie(ResultIt, WasInserted) =

354 unsigned INumber = ResultIt->second;

355

356

357 if (WasInserted)

359

360 IntegerMappingForBB.push_back(INumber);

361

362

364 "Instruction mapping overflow!");

365

367 "Tried to assign DenseMap tombstone or empty key to instruction.");

369 "Tried to assign DenseMap tombstone or empty key to instruction.");

370

371 return INumber;

372}

373

379

384

389

390

391

394 std::vector<IRInstructionData *> &InstrListForBB, bool End) {

395

397

398

401

403 if (!End)

405 else

407 InstrListForBB.push_back(ID);

408

409

413

415 "Instruction mapping overflow!");

416

418 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");

419

421 "IllegalInstrNumber cannot be DenseMap tombstone or empty key!");

422

423 return INumber;

424}

425

429 : StartIdx(StartIdx), Len(Len) {

430

431 assert(FirstInstIt != nullptr && "Instruction is nullptr!");

432 assert(LastInstIt != nullptr && "Instruction is nullptr!");

433 assert(StartIdx + Len > StartIdx &&

434 "Overflow for IRSimilarityCandidate range?");

435 assert(Len - 1 == static_cast<unsigned>(std::distance(

437 "Length of the first and last IRInstructionData do not match the "

438 "given length");

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455 unsigned LocalValNumber = 1;

457 for (unsigned Loc = StartIdx; Loc < StartIdx + Len; Loc++, ID++) {

458

459

460 for (Value *Arg : ID->OperVals)

461 if (ValueToNumber.try_emplace(Arg, LocalValNumber).second) {

462 NumberToValue.try_emplace(LocalValNumber, Arg);

463 LocalValNumber++;

464 }

465

466

467

468 if (ValueToNumber.try_emplace(ID->Inst, LocalValNumber).second) {

469 NumberToValue.try_emplace(LocalValNumber, ID->Inst);

470 LocalValNumber++;

471 }

472 }

473

474

475

476

477 FirstInst = FirstInstIt;

478 LastInst = LastInstIt;

479

480

484 if (ValueToNumber.try_emplace(BB, LocalValNumber).second) {

485 NumberToValue.try_emplace(LocalValNumber, BB);

486 LocalValNumber++;

487 }

488 }

489}

490

493 if (A.getLength() != B.getLength())

494 return false;

495

496 auto InstrDataForBoth =

498

499 return all_of(InstrDataForBoth,

500 [](std::tuple<IRInstructionData &, IRInstructionData &> R) {

503 if (.Legal || .Legal)

504 return false;

506 });

507}

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522

523

524

525

531

533

534 unsigned ArgVal;

535 bool WasInserted;

536

537

538

539

540

541 for (Value *V : SourceOperands) {

542 ArgVal = SourceValueToNumberMapping.find(V)->second;

543

544

545 std::tie(ValueMappingIt, WasInserted) = CurrentSrcTgtNumberMapping.insert(

546 std::make_pair(ArgVal, TargetValueNumbers));

547

548

549

550

552 for (unsigned &Curr : ValueMappingIt->second)

553

554 if (TargetValueNumbers.contains(Curr))

556

557

558 if (NewSet.empty())

559 return false;

560

561

562 if (NewSet.size() != ValueMappingIt->second.size())

563 ValueMappingIt->second.swap(NewSet);

564

565

566

567 if (ValueMappingIt->second.size() != 1)

568 continue;

569

570 unsigned ValToRemove = *ValueMappingIt->second.begin();

571

572

573

574 for (Value *InnerV : SourceOperands) {

575 if (V == InnerV)

576 continue;

577

578 unsigned InnerVal = SourceValueToNumberMapping.find(InnerV)->second;

579 ValueMappingIt = CurrentSrcTgtNumberMapping.find(InnerVal);

580 if (ValueMappingIt == CurrentSrcTgtNumberMapping.end())

581 continue;

582

583 ValueMappingIt->second.erase(ValToRemove);

584 if (ValueMappingIt->second.empty())

585 return false;

586 }

587 }

588

589 return true;

590}

591

592

593

594

595

596

597

598

599

600

601

602

605 unsigned SourceArgVal, unsigned TargetArgVal) {

606

607

608

609

610

611

612

613

614

615

616

617

618

619

620

621 bool WasInserted;

623

624 std::tie(Val, WasInserted) = CurrentSrcTgtNumberMapping.insert(

626

627

628 if (WasInserted)

629 return true;

630

631

632

633

634

635

637 if (TargetSet.size() > 1 && TargetSet.contains(TargetArgVal)) {

638 TargetSet.clear();

639 TargetSet.insert(TargetArgVal);

640 return true;

641 }

642

643

644 return TargetSet.contains(TargetArgVal);

645}

646

649

650

653 unsigned OperandLength = A.OperVals.size();

654

655

656 for (unsigned Idx = 0; Idx < OperandLength; Idx++, VItA++, VItB++) {

657 unsigned OperValA = A.IRSC.ValueToNumber.find(*VItA)->second;

658 unsigned OperValB = B.IRSC.ValueToNumber.find(*VItB)->second;

659

660

661

662

663

664

665

666

667

668

669

670

671

673 return false;

674

676 return false;

677 }

678 return true;

679}

680

685

688 unsigned OperandLength = A.OperVals.size();

689

690

691 for (unsigned Idx = 0; Idx < OperandLength;

692 Idx++, VItA++, VItB++) {

693 ValueNumbersA.insert(A.IRSC.ValueToNumber.find(*VItA)->second);

694 ValueNumbersB.insert(B.IRSC.ValueToNumber.find(*VItB)->second);

695 }

696

697

698

699

701 A.ValueNumberMapping, A.OperVals,

702 ValueNumbersB))

703 return false;

704

705

706

707

709 B.ValueNumberMapping, B.OperVals,

710 ValueNumbersA))

711 return false;

712

713 return true;

714}

715

717 const unsigned InstValA, const unsigned &InstValB,

721 bool WasInserted;

722 std::tie(ValueMappingIt, WasInserted) = ValueNumberMappingA.insert(

724 if (!WasInserted && !ValueMappingIt->second.contains(InstValB))

725 return false;

726 else if (ValueMappingIt->second.size() != 1) {

727 for (unsigned OtherVal : ValueMappingIt->second) {

728 if (OtherVal == InstValB)

729 continue;

730 auto OtherValIt = ValueNumberMappingA.find(OtherVal);

731 if (OtherValIt == ValueNumberMappingA.end())

732 continue;

733 OtherValIt->second.erase(InstValA);

734 }

735 ValueNumberMappingA.erase(ValueMappingIt);

736 std::tie(ValueMappingIt, WasInserted) = ValueNumberMappingA.insert(

738 }

739

740 return true;

741}

742

745

748

749

752 A.IRSC.getBasicBlocks(BasicBlockA);

753 B.IRSC.getBasicBlocks(BasicBlockB);

754

755

756 bool AContained = BasicBlockA.contains(ABB);

757 bool BContained = BasicBlockB.contains(BBB);

758

759

760

761 if (AContained != BContained)

762 return false;

763

764

765

766 if (AContained)

767 return A.RelativeLocation == B.RelativeLocation;

768 return true;

769}

770

777

782

787 if (A.getLength() != B.getLength())

788 return false;

789

790 if (A.ValueToNumber.size() != B.ValueToNumber.size())

791 return false;

792

795

796

797

798

799

800

801

802 unsigned SectionLength = A.getStartIdx() + A.getLength();

803 for (unsigned Loc = A.getStartIdx(); Loc < SectionLength;

804 ItA++, ItB++, Loc++) {

805

806 if ( isClose (*ItA, *ItB))

807 return false;

808

811

812 if (!ItA->Legal || !ItB->Legal)

813 return false;

814

815

818

819 unsigned InstValA = A.ValueToNumber.find(IA)->second;

820 unsigned InstValB = B.ValueToNumber.find(IB)->second;

821

822

824 ValueNumberMappingB))

825 return false;

826

828 ValueNumberMappingA))

829 return false;

830

831

832

833

837 {A, OperValsA, ValueNumberMappingA},

838 {B, OperValsB, ValueNumberMappingB}))

839 return false;

840 continue;

841 }

842

843

845 {A, OperValsA, ValueNumberMappingA},

846 {B, OperValsB, ValueNumberMappingB}))

847 return false;

848

849

850

851

852

853

854

855

856

857

858

859

862 continue;

863

868

869

870

871 if (RelBlockLocsA.size() != RelBlockLocsB.size() &&

873 return false;

874

876 "Block information vectors not the same size.");

878 "Block information vectors not the same size.");

879

881 zip(RelBlockLocsA, RelBlockLocsB, ABL, BBL);

882 if (any_of(ZippedRelativeLocations,

883 [&A, &B](std::tuple<int, int, Value *, Value *> R) {

885 {A, std::get<0>(R), std::get<2>(R)},

886 {B, std::get<1>(R), std::get<3>(R)});

887 }))

888 return false;

889 }

890 return true;

891}

892

897

898

899

900 return X.StartIdx <= Y.getEndIdx() && Y.StartIdx >= X.StartIdx;

901 };

902

903 return DoesOverlap(A, B) || DoesOverlap(B, A);

904}

905

906void IRSimilarityIdentifier::populateMapper(

907 Module &M, std::vector<IRInstructionData *> &InstrList,

908 std::vector &IntegerMapping) {

909

910 std::vector<IRInstructionData *> InstrListForModule;

911 std::vector IntegerMappingForModule;

912

913

914 Mapper.initializeForBBs(M);

915

917

918 if (F.empty())

919 continue;

920

922

923

924

925

926 Mapper.convertToUnsignedVec(BB, InstrListForModule,

927 IntegerMappingForModule);

928 }

929

931 Mapper.mapToIllegalUnsigned(It, IntegerMappingForModule, InstrListForModule,

932 true);

933 if (InstrListForModule.size() > 0)

934 Mapper.IDL->push_back(*InstrListForModule.back());

935 }

936

937

938

940

942}

943

944void IRSimilarityIdentifier::populateMapper(

945 ArrayRef<std::unique_ptr> &Modules,

946 std::vector<IRInstructionData *> &InstrList,

947 std::vector &IntegerMapping) {

948

949

950 for (const std::unique_ptr &M : Modules)

951 populateMapper(*M, InstrList, IntegerMapping);

952}

953

954

955

956

957

958

959

960

961

962

964 const IRInstructionMapper& Mapper, std::vector<IRInstructionData *> &InstrList,

966 std::vector &CandsForRepSubstring) {

967

968 unsigned StringLen = RS.Length;

969 if (StringLen < 2)

970 return;

971

972

973 for (const unsigned &StartIdx : RS.StartIndices) {

974 unsigned EndIdx = StartIdx + StringLen - 1;

975

976

977 bool ContainsIllegal = false;

978 for (unsigned CurrIdx = StartIdx; CurrIdx <= EndIdx; CurrIdx++) {

979 unsigned Key = IntegerMapping[CurrIdx];

980 if (Key > Mapper.IllegalInstrNumber) {

981 ContainsIllegal = true;

982 break;

983 }

984 }

985

986

987

988 if (ContainsIllegal)

989 continue;

990

991

992

993

994 std::vector<IRInstructionData *>::iterator StartIt = InstrList.begin();

995 std::advance(StartIt, StartIdx);

996 std::vector<IRInstructionData *>::iterator EndIt = InstrList.begin();

997 std::advance(EndIt, EndIdx);

998

999 CandsForRepSubstring.emplace_back(StartIdx, StringLen, *StartIt, *EndIt);

1000 }

1001}

1002

1007 assert(SourceCand.CanonNumToNumber.size() != 0 &&

1008 "Base canonical relationship is empty!");

1009 assert(SourceCand.NumberToCanonNum.size() != 0 &&

1010 "Base canonical relationship is empty!");

1011

1012 assert(CanonNumToNumber.size() == 0 && "Canonical Relationship is non-empty");

1013 assert(NumberToCanonNum.size() == 0 && "Canonical Relationship is non-empty");

1014

1016

1017

1018

1019 for (std::pair<unsigned, DenseSet> &GVNMapping : ToSourceMapping) {

1020 unsigned SourceGVN = GVNMapping.first;

1021

1022 assert(GVNMapping.second.size() != 0 && "Possible GVNs is 0!");

1023

1024 unsigned ResultGVN;

1025

1026

1027

1028

1029 if (GVNMapping.second.size() > 1) {

1030 bool Found = false;

1031 for (unsigned Val : GVNMapping.second) {

1032

1034 continue;

1035

1036

1038 FromSourceMapping.find(Val);

1039

1040 if (!It->second.contains(SourceGVN))

1041 continue;

1042

1043

1044 Found = true;

1045 ResultGVN = Val;

1046 break;

1047 }

1048

1049 assert(Found && "Could not find matching value for source GVN");

1050 (void)Found;

1051

1052 } else

1053 ResultGVN = *GVNMapping.second.begin();

1054

1055

1056 UsedGVNs.insert(ResultGVN);

1057

1058 unsigned CanonNum = *SourceCand.getCanonicalNum(ResultGVN);

1059 CanonNumToNumber.insert(std::make_pair(CanonNum, SourceGVN));

1060 NumberToCanonNum.insert(std::make_pair(SourceGVN, CanonNum));

1061 }

1062

1065

1066

1067

1068

1069

1070

1072 unsigned BBGVNForCurrCand = ValueToNumber.find(BB)->second;

1073

1074

1075

1076 if (NumberToCanonNum.contains(BBGVNForCurrCand))

1077 continue;

1078

1079

1080

1081

1084 : &*BB->instructionsWithoutDebug().begin();

1085

1086 unsigned FirstInstGVN = *getGVN(FirstOutlineInst);

1087 unsigned FirstInstCanonNum = *getCanonicalNum(FirstInstGVN);

1088 unsigned SourceGVN = *SourceCand.fromCanonicalNum(FirstInstCanonNum);

1089 Value *SourceV = *SourceCand.fromGVN(SourceGVN);

1091 unsigned SourceBBGVN = *SourceCand.getGVN(SourceBB);

1092 unsigned SourceCanonBBGVN = *SourceCand.getCanonicalNum(SourceBBGVN);

1093 CanonNumToNumber.insert(std::make_pair(SourceCanonBBGVN, BBGVNForCurrCand));

1094 NumberToCanonNum.insert(std::make_pair(BBGVNForCurrCand, SourceCanonBBGVN));

1095 }

1096}

1097

1101 assert(!SourceCand.CanonNumToNumber.empty() &&

1102 "Canonical Relationship is non-empty");

1103 assert(!SourceCand.NumberToCanonNum.empty() &&

1104 "Canonical Relationship is non-empty");

1105

1106 assert(!SourceCandLarge.CanonNumToNumber.empty() &&

1107 "Canonical Relationship is non-empty");

1108 assert(!SourceCandLarge.NumberToCanonNum.empty() &&

1109 "Canonical Relationship is non-empty");

1110

1111 assert(!TargetCandLarge.CanonNumToNumber.empty() &&

1112 "Canonical Relationship is non-empty");

1113 assert(!TargetCandLarge.NumberToCanonNum.empty() &&

1114 "Canonical Relationship is non-empty");

1115

1116 assert(CanonNumToNumber.empty() && "Canonical Relationship is non-empty");

1117 assert(NumberToCanonNum.empty() && "Canonical Relationship is non-empty");

1118

1119

1120

1121

1122

1123 for (std::pair<Value *, unsigned> &ValueNumPair : ValueToNumber) {

1124 Value *CurrVal = ValueNumPair.first;

1125 unsigned TargetCandGVN = ValueNumPair.second;

1126

1127

1128

1129 std::optional OLargeTargetGVN = TargetCandLarge.getGVN(CurrVal);

1130 assert(OLargeTargetGVN.has_value() && "GVN not found for Value");

1131

1132

1133 std::optional OTargetCandCanon =

1134 TargetCandLarge.getCanonicalNum(OLargeTargetGVN.value());

1135 assert(OTargetCandCanon.has_value() &&

1136 "Canononical Number not found for GVN");

1137

1138

1139 std::optional OLargeSourceGVN =

1141 assert(OLargeSourceGVN.has_value() &&

1142 "GVN Number not found for Canonical Number");

1143

1144

1145 std::optional<Value *> OLargeSourceV =

1146 SourceCandLarge.fromGVN(OLargeSourceGVN.value());

1147 assert(OLargeSourceV.has_value() && "Value not found for GVN");

1148

1149

1150 std::optional OSourceGVN =

1151 SourceCand.getGVN(OLargeSourceV.value());

1152 assert(OSourceGVN.has_value() && "GVN Number not found for Value");

1153

1154

1155 std::optional OSourceCanon =

1157 assert(OSourceCanon.has_value() && "Canon Number not found for GVN");

1158

1159

1160

1161 CanonNumToNumber.insert(

1162 std::make_pair(OSourceCanon.value(), TargetCandGVN));

1163 NumberToCanonNum.insert(

1164 std::make_pair(TargetCandGVN, OSourceCanon.value()));

1165 }

1166}

1167

1170 assert(CurrCand.CanonNumToNumber.size() == 0 &&

1171 "Canonical Relationship is non-empty");

1172 assert(CurrCand.NumberToCanonNum.size() == 0 &&

1173 "Canonical Relationship is non-empty");

1174

1175 unsigned CanonNum = 0;

1176

1177

1178 for (std::pair<unsigned, Value *> &NumToVal : CurrCand.NumberToValue) {

1179 CurrCand.NumberToCanonNum.insert(std::make_pair(NumToVal.first, CanonNum));

1180 CurrCand.CanonNumToNumber.insert(std::make_pair(CanonNum, NumToVal.first));

1181 CanonNum++;

1182 }

1183}

1184

1185

1186

1187

1188

1189

1190

1191

1192

1193

1194

1195

1196

1197

1198static std::optional<

1199 std::pair<IRSimilarityCandidate *, IRSimilarityCandidate *>>

1208

1209

1210

1211 auto IdxToCandidateIt = IndexToIncludedCand.find(CandA.getStartIdx());

1212 std::optional<std::pair<IRSimilarityCandidate *, IRSimilarityCandidate *>>

1213 Result;

1214

1215 unsigned CandAStart = CandA.getStartIdx();

1216 unsigned CandAEnd = CandA.getEndIdx();

1217 unsigned CandBStart = CandB.getStartIdx();

1218 unsigned CandBEnd = CandB.getEndIdx();

1219 if (IdxToCandidateIt == IndexToIncludedCand.end())

1220 return Result;

1222 if (MatchedCand->getStartIdx() > CandAStart ||

1223 (MatchedCand->getEndIdx() < CandAEnd))

1224 continue;

1225 unsigned GroupNum = CandToGroup.find(MatchedCand)->second;

1226 IncludedGroupAndCandA.insert(std::make_pair(GroupNum, MatchedCand));

1227 IncludedGroupsA.insert(GroupNum);

1228 }

1229

1230

1231

1232 IdxToCandidateIt = IndexToIncludedCand.find(CandBStart);

1233 if (IdxToCandidateIt == IndexToIncludedCand.end())

1234 return Result;

1236 if (MatchedCand->getStartIdx() > CandBStart ||

1237 MatchedCand->getEndIdx() < CandBEnd)

1238 continue;

1239 unsigned GroupNum = CandToGroup.find(MatchedCand)->second;

1240 IncludedGroupAndCandB.insert(std::make_pair(GroupNum, MatchedCand));

1241 IncludedGroupsB.insert(GroupNum);

1242 }

1243

1244

1245

1246 set_intersect(IncludedGroupsA, IncludedGroupsB);

1247

1248

1249

1250 if (IncludedGroupsA.empty())

1251 return Result;

1252

1253

1254 auto ItA = IncludedGroupAndCandA.find(*IncludedGroupsA.begin());

1255 auto ItB = IncludedGroupAndCandB.find(*IncludedGroupsA.begin());

1256 Result = std::make_pair(ItA->second, ItB->second);

1257 return Result;

1258}

1259

1260

1261

1262

1263

1264

1265

1266

1267

1268

1269

1270

1271

1272

1274 std::vector &CandsForRepSubstring,

1278 ) {

1279 std::vector::iterator CandIt, CandEndIt, InnerCandIt,

1280 InnerCandEndIt;

1281

1282

1283

1284

1285

1286

1288

1289

1290

1291

1292 bool SameStructure;

1293 bool Inserted;

1294 unsigned CurrentGroupNum = 0;

1295 unsigned OuterGroupNum;

1299

1300

1301

1304 for (CandIt = CandsForRepSubstring.begin(),

1305 CandEndIt = CandsForRepSubstring.end();

1306 CandIt != CandEndIt; CandIt++) {

1307

1308

1309

1310 std::tie(CandToGroupIt, Inserted) =

1311 CandToGroup.try_emplace(&*CandIt, CurrentGroupNum);

1312 if (Inserted)

1313 ++CurrentGroupNum;

1314

1315

1316 OuterGroupNum = CandToGroupIt->second;

1317

1318

1319

1320 CurrentGroupPair = StructuralGroups.find(OuterGroupNum);

1321 if (CurrentGroupPair == StructuralGroups.end()) {

1323 std::tie(CurrentGroupPair, Inserted) = StructuralGroups.insert(

1324 std::make_pair(OuterGroupNum, SimilarityGroup({*CandIt})));

1325 }

1326

1327

1328

1329

1330

1331 for (InnerCandIt = std::next(CandIt),

1332 InnerCandEndIt = CandsForRepSubstring.end();

1333 InnerCandIt != InnerCandEndIt; InnerCandIt++) {

1334

1335

1336 CandToGroupItInner = CandToGroup.find(&*InnerCandIt);

1337 if (CandToGroupItInner != CandToGroup.end())

1338 continue;

1339

1340

1341

1342 std::optional<std::pair<IRSimilarityCandidate *, IRSimilarityCandidate *>>

1344 *CandIt, *InnerCandIt, IndexToIncludedCand, CandToOverallGroup);

1345

1346

1347

1348

1349 if (LargerPair.has_value()) {

1350 SameStructure = true;

1351 InnerCandIt->createCanonicalRelationFrom(

1352 *CandIt, *LargerPair.value().first, *LargerPair.value().second);

1353 CandToGroup.insert(std::make_pair(&*InnerCandIt, OuterGroupNum));

1354 CurrentGroupPair->second.push_back(*InnerCandIt);

1355 continue;

1356 }

1357

1358

1359

1360 ValueNumberMappingA.clear();

1361 ValueNumberMappingB.clear();

1363 *CandIt, *InnerCandIt, ValueNumberMappingA, ValueNumberMappingB);

1364 if (!SameStructure)

1365 continue;

1366

1367 InnerCandIt->createCanonicalRelationFrom(*CandIt, ValueNumberMappingA,

1368 ValueNumberMappingB);

1369 CandToGroup.insert(std::make_pair(&*InnerCandIt, OuterGroupNum));

1370 CurrentGroupPair->second.push_back(*InnerCandIt);

1371 }

1372 }

1373}

1374

1375void IRSimilarityIdentifier::findCandidates(

1376 std::vector<IRInstructionData *> &InstrList,

1377 std::vector &IntegerMapping) {

1378 SuffixTree ST(IntegerMapping);

1379

1380 std::vector CandsForRepSubstring;

1381 std::vector NewCandidateGroups;

1382

1383 DenseMap<unsigned, SimilarityGroup> StructuralGroups;

1384 DenseMap<unsigned, DenseSet<IRSimilarityCandidate *>> IndexToIncludedCand;

1385 DenseMap<IRSimilarityCandidate *, unsigned> CandToGroup;

1386

1387

1388

1389

1390

1391

1392 std::vectorSuffixTree::RepeatedSubstring RSes;

1393 for (SuffixTree::RepeatedSubstring &RS : ST)

1394 RSes.push_back(RS);

1395

1397 const SuffixTree::RepeatedSubstring &RHS) {

1398 return LHS.Length > RHS.Length;

1399 });

1400 for (SuffixTree::RepeatedSubstring &RS : RSes) {

1402 CandsForRepSubstring);

1403

1404 if (CandsForRepSubstring.size() < 2)

1405 continue;

1406

1408 IndexToIncludedCand, CandToGroup);

1409 for (std::pair<unsigned, SimilarityGroup> &Group : StructuralGroups) {

1410

1411

1412

1413 if (Group.second.size() > 1) {

1414 SimilarityCandidates->push_back(Group.second);

1415

1416

1417

1418 for (IRSimilarityCandidate &IRCand : SimilarityCandidates->back()) {

1419 for (unsigned Idx = IRCand.getStartIdx(), Edx = IRCand.getEndIdx();

1420 Idx <= Edx; ++Idx)

1421 IndexToIncludedCand[Idx].insert(&IRCand);

1422

1424 std::make_pair(&IRCand, SimilarityCandidates->size() - 1));

1425 }

1426 }

1427 }

1428

1429 CandsForRepSubstring.clear();

1430 StructuralGroups.clear();

1431 NewCandidateGroups.clear();

1432 }

1433}

1434

1436 ArrayRef<std::unique_ptr> Modules) {

1438

1439 std::vector<IRInstructionData *> InstrList;

1440 std::vector IntegerMapping;

1441 Mapper.InstClassifier.EnableBranches = this->EnableBranches;

1442 Mapper.InstClassifier.EnableIndirectCalls = EnableIndirectCalls;

1443 Mapper.EnableMatchCallsByName = EnableMatchingCallsByName;

1444 Mapper.InstClassifier.EnableIntrinsics = EnableIntrinsics;

1445 Mapper.InstClassifier.EnableMustTailCalls = EnableMustTailCalls;

1446

1447 populateMapper(Modules, InstrList, IntegerMapping);

1448 findCandidates(InstrList, IntegerMapping);

1449

1450 return *SimilarityCandidates;

1451}

1452

1455 Mapper.InstClassifier.EnableBranches = this->EnableBranches;

1456 Mapper.InstClassifier.EnableIndirectCalls = EnableIndirectCalls;

1457 Mapper.EnableMatchCallsByName = EnableMatchingCallsByName;

1458 Mapper.InstClassifier.EnableIntrinsics = EnableIntrinsics;

1459 Mapper.InstClassifier.EnableMustTailCalls = EnableMustTailCalls;

1460

1461 std::vector<IRInstructionData *> InstrList;

1462 std::vector IntegerMapping;

1463

1464 populateMapper(M, InstrList, IntegerMapping);

1465 findCandidates(InstrList, IntegerMapping);

1466

1467 return *SimilarityCandidates;

1468}

1469

1471 "ir-similarity-identifier", false, true)

1472

1475

1479 false));

1480 return false;

1481}

1482

1484 IRSI.reset();

1485 return false;

1486}

1487

1489 IRSI->findSimilarity(M);

1490 return false;

1491}

1492

1498 false);

1499 IRSI.findSimilarity(M);

1500 return IRSI;

1501}

1502

1506 std::optional &SimilarityCandidatesOpt =

1508

1509 for (std::vector &CandVec : *SimilarityCandidatesOpt) {

1510 OS << CandVec.size() << " candidates of length "

1511 << CandVec.begin()->getLength() << ". Found in: \n";

1513 OS << " Function: " << Cand.front()->Inst->getFunction()->getName().str()

1514 << ", Basic Block: ";

1515 if (Cand.front()->Inst->getParent()->getName().str() == "")

1516 OS << "(unnamed)";

1517 else

1518 OS << Cand.front()->Inst->getParent()->getName().str();

1519 OS << "\n Start Instruction: ";

1520 Cand.frontInstruction()->print(OS);

1521 OS << "\n End Instruction: ";

1522 Cand.backInstruction()->print(OS);

1523 OS << "\n";

1524 }

1525 }

1526

1528}

1529

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

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

This file defines the DenseMap class.

bool checkNumberingAndReplace(DenseMap< unsigned, DenseSet< unsigned > > &CurrentSrcTgtNumberMapping, unsigned SourceArgVal, unsigned TargetArgVal)

Determine if operand number TargetArgVal is in the current mapping set for operand number SourceArgVa...

Definition IRSimilarityIdentifier.cpp:603

detail::zippy< detail::zip_shortest, SmallVector< int, 4 > &, SmallVector< int, 4 > &, ArrayRef< Value * > &, ArrayRef< Value * > & > ZippedRelativeLocationsT

Definition IRSimilarityIdentifier.cpp:781

static void findCandidateStructures(std::vector< IRSimilarityCandidate > &CandsForRepSubstring, DenseMap< unsigned, SimilarityGroup > &StructuralGroups, DenseMap< unsigned, DenseSet< IRSimilarityCandidate * > > &IndexToIncludedCand, DenseMap< IRSimilarityCandidate *, unsigned > &CandToOverallGroup)

From the list of IRSimilarityCandidates, perform a comparison between each IRSimilarityCandidate to d...

Definition IRSimilarityIdentifier.cpp:1273

static void createCandidatesFromSuffixTree(const IRInstructionMapper &Mapper, std::vector< IRInstructionData * > &InstrList, std::vector< unsigned > &IntegerMapping, SuffixTree::RepeatedSubstring &RS, std::vector< IRSimilarityCandidate > &CandsForRepSubstring)

From a repeated subsequence, find all the different instances of the subsequence from the InstrList,...

Definition IRSimilarityIdentifier.cpp:963

static bool checkNumberingAndReplaceCommutative(const DenseMap< Value *, unsigned > &SourceValueToNumberMapping, DenseMap< unsigned, DenseSet< unsigned > > &CurrentSrcTgtNumberMapping, ArrayRef< Value * > &SourceOperands, DenseSet< unsigned > &TargetValueNumbers)

Determine if one or more of the assigned global value numbers for the operands in TargetValueNumbers ...

Definition IRSimilarityIdentifier.cpp:526

static std::optional< std::pair< IRSimilarityCandidate *, IRSimilarityCandidate * > > CheckLargerCands(IRSimilarityCandidate &CandA, IRSimilarityCandidate &CandB, DenseMap< unsigned, DenseSet< IRSimilarityCandidate * > > &IndexToIncludedCand, DenseMap< IRSimilarityCandidate *, unsigned > &CandToGroup)

Look for larger IRSimilarityCandidates From the previously matched IRSimilarityCandidates that fully ...

Definition IRSimilarityIdentifier.cpp:1200

uint64_t IntrinsicInst * II

#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)

This file defines generic set operations that may be used on set's of different types,...

static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")

static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

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

size_t size() const

size - Get the array size.

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

const Function * getParent() const

Return the enclosing method, or null if none.

InstListType::iterator iterator

Instruction iterators...

Conditional or Unconditional Branch instruction.

Function * getCalledFunction() const

Returns the function called, or null if this is an indirect function invocation or the function signa...

LLVM_ABI bool isIndirectCall() const

Return true if the callsite is an indirect call.

This class represents a function call, abstracting a target machine's calling convention.

This class is the base class for the comparison instructions.

Predicate

This enumeration lists the possible predicates for CmpInst subclasses.

@ FCMP_OGT

0 0 1 0 True if ordered and greater than

@ FCMP_OGE

0 0 1 1 True if ordered and greater than or equal

@ ICMP_UGE

unsigned greater or equal

@ ICMP_UGT

unsigned greater than

@ ICMP_SGT

signed greater than

@ FCMP_UGT

1 0 1 0 True if unordered or greater than

@ ICMP_SGE

signed greater or equal

@ FCMP_UGE

1 0 1 1 True if unordered, greater than, or equal

Predicate getSwappedPredicate() const

For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.

Predicate getPredicate() const

Return the predicate for this instruction.

iterator find(const_arg_type_t< KeyT > Val)

std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)

bool erase(const KeyT &Val)

DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator

bool contains(const_arg_type_t< KeyT > Val) const

Return true if the specified key is in the map, false otherwise.

std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)

Implements a dense probed hash-table based set.

Class to represent function types.

ArrayRef< Type * > params() const

LLVM_ABI PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)

Definition IRSimilarityIdentifier.cpp:1504

An analysis pass that runs and returns the IRSimilarityIdentifier run on the Module.

LLVM_ABI Result run(Module &M, ModuleAnalysisManager &)

Definition IRSimilarityIdentifier.cpp:1494

An analysis pass based on legacy pass manager that runs and returns IRSimilarityIdentifier run on the...

bool doInitialization(Module &M) override

doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...

Definition IRSimilarityIdentifier.cpp:1476

bool doFinalization(Module &M) override

doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...

Definition IRSimilarityIdentifier.cpp:1483

bool runOnModule(Module &M) override

runOnModule - Virtual method overriden by subclasses to process the module being operated on.

Definition IRSimilarityIdentifier.cpp:1488

This is a class that wraps a range of IRInstructionData from one point to another in the vector of IR...

LLVM_ABI void createCanonicalRelationFrom(IRSimilarityCandidate &SourceCand, DenseMap< unsigned, DenseSet< unsigned > > &ToSourceMapping, DenseMap< unsigned, DenseSet< unsigned > > &FromSourceMapping)

Create a mapping for the value numbering of the calling IRSimilarityCandidate, to a different separat...

Definition IRSimilarityIdentifier.cpp:1003

static LLVM_ABI bool isSimilar(const IRSimilarityCandidate &A, const IRSimilarityCandidate &B)

Definition IRSimilarityIdentifier.cpp:491

std::optional< unsigned > getGVN(Value *V)

Finds the positive number associated with V if it has been mapped.

unsigned getEndIdx() const

static LLVM_ABI bool compareAssignmentMapping(const unsigned InstValA, const unsigned &InstValB, DenseMap< unsigned, DenseSet< unsigned > > &ValueNumberMappingA, DenseMap< unsigned, DenseSet< unsigned > > &ValueNumberMappingB)

Compare the GVN of the assignment value in corresponding instructions in IRSimilarityCandidates A and...

Definition IRSimilarityIdentifier.cpp:716

void getBasicBlocks(DenseSet< BasicBlock * > &BBSet) const

std::optional< Value * > fromGVN(unsigned Num)

Finds the Value associate with Num if it exists.

IRInstructionDataList::iterator iterator

Instruction * frontInstruction()

static LLVM_ABI bool checkRelativeLocations(RelativeLocMapping A, RelativeLocMapping B)

Compare the relative locations in A and B and check that the distances match if both locations are co...

Definition IRSimilarityIdentifier.cpp:743

static LLVM_ABI bool compareStructure(const IRSimilarityCandidate &A, const IRSimilarityCandidate &B)

Definition IRSimilarityIdentifier.cpp:771

static LLVM_ABI void createCanonicalMappingFor(IRSimilarityCandidate &CurrCand)

Create a mapping from the value numbering to a different separate set of numbers.

Definition IRSimilarityIdentifier.cpp:1168

static LLVM_ABI bool overlap(const IRSimilarityCandidate &A, const IRSimilarityCandidate &B)

Compare the start and end indices of the two IRSimilarityCandidates for whether they overlap.

Definition IRSimilarityIdentifier.cpp:893

unsigned getStartIdx() const

BasicBlock * getStartBB()

LLVM_ABI IRSimilarityCandidate(unsigned StartIdx, unsigned Len, IRInstructionData *FirstInstIt, IRInstructionData *LastInstIt)

Definition IRSimilarityIdentifier.cpp:426

std::optional< unsigned > getCanonicalNum(unsigned N)

Find the canonical number from the global value number N stored in the candidate.

std::optional< unsigned > fromCanonicalNum(unsigned N)

Find the global value number from the canonical number N stored in the candidate.

static LLVM_ABI bool compareNonCommutativeOperandMapping(OperandMapping A, OperandMapping B)

Compare the operands in A and B and check that the current mapping of global value numbers from A to ...

Definition IRSimilarityIdentifier.cpp:647

static LLVM_ABI bool compareCommutativeOperandMapping(OperandMapping A, OperandMapping B)

Compare the operands in A and B and check that the current mapping of global value numbers from A to ...

Definition IRSimilarityIdentifier.cpp:681

This class puts all the pieces of the IRInstructionData, IRInstructionMapper, IRSimilarityCandidate t...

void resetSimilarityCandidates()

LLVM_ABI SimilarityGroupList & findSimilarity(ArrayRef< std::unique_ptr< Module > > Modules)

Definition IRSimilarityIdentifier.cpp:1435

std::optional< SimilarityGroupList > & getSimilarity()

A wrapper class for inspecting calls to intrinsic functions.

ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...

A Module instance is used to store all the information related to an LLVM module.

BasicBlock * getIncomingBlock(unsigned i) const

Return incoming basic block number i.

unsigned getNumIncomingValues() const

Return the number of incoming edges.

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

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

StringRef - Represent a constant reference to a string, i.e.

std::string str() const

str - Get the contents as an std::string.

A Use represents the edge between a Value definition and its users.

LLVM Value Representation.

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

std::pair< iterator, bool > insert(const ValueT &V)

iterator find(const_arg_type_t< ValueT > V)

bool contains(const_arg_type_t< ValueT > V) const

Check if the set contains the given element.

const ParentTy * getParent() const

ilist_select_iterator_type< OptionsT, false, false > iterator

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

@ C

The default llvm calling convention, compatible with C.

std::vector< SimilarityGroup > SimilarityGroupList

std::vector< IRSimilarityCandidate > SimilarityGroup

LLVM_ABI bool isClose(const IRInstructionData &A, const IRInstructionData &B)

Compare one IRInstructionData class to another IRInstructionData class for whether they are performin...

Definition IRSimilarityIdentifier.cpp:220

LLVM_ABI StringRef getName(ID id)

Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".

LLVM_ABI bool isOverloaded(ID id)

Returns true if the intrinsic can be overloaded.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

auto drop_begin(T &&RangeOrContainer, size_t N=1)

Return a range covering RangeOrContainer with the first N elements excluded.

detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)

zip iterator for two or more iteratable types.

void stable_sort(R &&Range)

bool all_of(R &&range, UnaryPredicate P)

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

void set_intersect(S1Ty &S1, const S2Ty &S2)

set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...

decltype(auto) dyn_cast(const From &Val)

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

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

void append_range(Container &C, Range &&R)

Wrapper function to append range R to container C.

cl::opt< bool > DisableIndirectCalls("no-ir-sim-indirect-calls", cl::init(false), cl::ReallyHidden, cl::desc("disable outlining indirect calls."))

bool any_of(R &&range, UnaryPredicate P)

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

bool isa(const From &Val)

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

cl::opt< bool > DisableBranches("no-ir-sim-branch-matching", cl::init(false), cl::ReallyHidden, cl::desc("disable similarity matching, and outlining, " "across branches for debugging purposes."))

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

cl::opt< bool > DisableIntrinsics("no-ir-sim-intrinsics", cl::init(false), cl::ReallyHidden, cl::desc("Don't match or outline intrinsics"))

ArrayRef(const T &OneElt) -> ArrayRef< T >

static cl::opt< bool > MatchCallsByName("ir-sim-calls-by-name", cl::init(false), cl::ReallyHidden, cl::desc("only allow matching call instructions if the " "name and type signature match."))

decltype(auto) cast(const From &Val)

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

AnalysisManager< Module > ModuleAnalysisManager

Convenience typedef for the Module analysis manager.

A special type used by analysis passes to provide an address that identifies that particular analysis...

An information struct used to provide DenseMap with the various necessary components for a given valu...

This provides the utilities for hashing an Instruction to an unsigned integer.

LLVM_ABI StringRef getCalleeName() const

Get the callee name that the call instruction is using for hashing the instruction.

Definition IRSimilarityIdentifier.cpp:211

LLVM_ABI void initializeInstruction()

Fills data stuctures for IRInstructionData when it is constructed from a.

Definition IRSimilarityIdentifier.cpp:55

SmallVector< int, 4 > RelativeBlockLocations

This structure holds the distances of how far "ahead of" or "behind" the target blocks of a branch,...

std::optional< std::string > CalleeName

This is only relevant if we are wrapping a CallInst.

LLVM_ABI IRInstructionData(Instruction &I, bool Legality, IRInstructionDataList &IDL)

Gather the information that is difficult to gather for an Instruction, or is changed.

Definition IRSimilarityIdentifier.cpp:49

LLVM_ABI ArrayRef< Value * > getBlockOperVals()

Get the BasicBlock based operands for PHINodes and BranchInsts.

Definition IRSimilarityIdentifier.cpp:112

Instruction * Inst

The source Instruction that is being wrapped.

IRInstructionDataList * IDL

static LLVM_ABI CmpInst::Predicate predicateForConsistency(CmpInst *CI)

A function that swaps the predicates to their less than form if they are in a greater than form.

Definition IRSimilarityIdentifier.cpp:185

LLVM_ABI void setPHIPredecessors(DenseMap< BasicBlock *, unsigned > &BasicBlockToInteger)

For an IRInstructionData containing a PHINode, finds the relative distances from the incoming basic b...

Definition IRSimilarityIdentifier.cpp:158

SmallVector< Value *, 4 > OperVals

The values of the operands in the Instruction.

LLVM_ABI void setBranchSuccessors(DenseMap< BasicBlock *, unsigned > &BasicBlockToInteger)

For an IRInstructionData containing a branch, finds the relative distances from the source basic bloc...

Definition IRSimilarityIdentifier.cpp:87

bool Legal

The legality of the wrapped instruction.

LLVM_ABI void setCalleeName(bool MatchByName=true)

For an IRInstructionData containing a CallInst, set the function name appropriately.

Definition IRSimilarityIdentifier.cpp:131

LLVM_ABI CmpInst::Predicate getPredicate() const

Get the predicate that the compare instruction is using for hashing the instruction.

Definition IRSimilarityIdentifier.cpp:201

std::optional< CmpInst::Predicate > RevisedPredicate

This is only relevant if we are wrapping a CmpInst where we needed to change the predicate of a compa...

Helper struct for converting the Instructions in a Module into a vector of unsigned integers.

DenseMap< IRInstructionData *, unsigned, IRInstructionDataTraits > InstructionIntegerMap

Correspondence from IRInstructionData to unsigned integers.

SpecificBumpPtrAllocator< IRInstructionDataList > * IDLAllocator

This allocator pointer is in charge of creating the IRInstructionDataList so it is not deallocated un...

SpecificBumpPtrAllocator< IRInstructionData > * InstDataAllocator

This allocator pointer is in charge of holding on to the IRInstructionData so it is not deallocated u...

bool EnableMatchCallsByName

Marks whether we should use exact function names, as well as types to find similarity between calls.

unsigned LegalInstrNumber

The next available integer to assign to a legal Instruction to.

unsigned IllegalInstrNumber

The starting illegal instruction number to map to.

InstructionClassification InstClassifier

Maps an Instruction to a member of InstrType.

bool HaveLegalRange

Marks whether we have found a set of instructions that is long enough to be considered for similarity...

LLVM_ABI IRInstructionData * allocateIRInstructionData(Instruction &I, bool Legality, IRInstructionDataList &IDL)

Get an allocated IRInstructionData struct using the InstDataAllocator.

Definition IRSimilarityIdentifier.cpp:375

bool CanCombineWithPrevInstr

Marks whether we found a illegal instruction in the previous step.

IRInstructionDataList * IDL

DenseMap< BasicBlock *, unsigned > BasicBlockToInteger

A mapping for a basic block in a module to its assigned number/location in the module.

LLVM_ABI IRInstructionDataList * allocateIRInstructionDataList()

Get an allocated IRInstructionDataList object using the IDLAllocator.

Definition IRSimilarityIdentifier.cpp:386

LLVM_ABI unsigned mapToLegalUnsigned(BasicBlock::iterator &It, std::vector< unsigned > &IntegerMappingForBB, std::vector< IRInstructionData * > &InstrListForBB)

Maps an Instruction to a legal integer.

Definition IRSimilarityIdentifier.cpp:321

LLVM_ABI void convertToUnsignedVec(BasicBlock &BB, std::vector< IRInstructionData * > &InstrList, std::vector< unsigned > &IntegerMapping)

Maps the Instructions in a BasicBlock BB to legal or illegal integers determined by InstrType.

Definition IRSimilarityIdentifier.cpp:289

bool AddedIllegalLastTime

Set if we added an illegal number in the previous step.

LLVM_ABI unsigned mapToIllegalUnsigned(BasicBlock::iterator &It, std::vector< unsigned > &IntegerMappingForBB, std::vector< IRInstructionData * > &InstrListForBB, bool End=false)

Maps an Instruction to an illegal integer.

Definition IRSimilarityIdentifier.cpp:392

A helper struct to hold the candidate, for a branch instruction, the relative location of a label,...

Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...

A repeated substring in the tree.