Reassociate.cpp Source File (original) (raw)

60#include

61#include

62#include

64using namespace llvm;

68#define DEBUG_TYPE "reassociate"

70 STATISTIC(NumChanged, "Number of insts reassociated");

71 STATISTIC(NumAnnihil, "Number of expr tree annihilated");

72 STATISTIC(NumFactor , "Number of multiplies factored");

76 cl::desc("Only reorder expressions within a basic block "

77 "when exposing CSE opportunities"),

80#ifndef NDEBUG

83 Module *M = I->getModule();

85 << *Ops[0].Op->getType() << '\t';

87 dbgs() << "[ ";

88 Op.Op->printAsOperand(dbgs(), false, M);

89 dbgs() << ", #" << Op.Rank << "] ";

90 }

91}

92#endif

100

101

103public:

105

106 bool isInvalid() const { return SymbolicPart == nullptr; }

112

113 void Invalidate() { SymbolicPart = OrigVal = nullptr; }

115

116private:

118 Value *SymbolicPart;

120 unsigned SymbolicRank;

121 bool isOr;

122};

123

126 OrigVal = V;

128 SymbolicRank = 0;

129

130 if (I && (I->getOpcode() == Instruction::Or ||

131 I->getOpcode() == Instruction::And)) {

132 Value *V0 = I->getOperand(0);

133 Value *V1 = I->getOperand(1);

137

139 ConstPart = *C;

140 SymbolicPart = V0;

141 isOr = (I->getOpcode() == Instruction::Or);

142 return;

143 }

144 }

145

146

147 SymbolicPart = V;

148 ConstPart = APInt::getZero(V->getType()->getScalarSizeInBits());

149 isOr = true;

150}

151

152

153

154

155

158 return I->hasAllowReassoc() && I->hasNoSignedZeros();

159}

160

161

162

165 if (BO && BO->hasOneUse() && BO->getOpcode() == Opcode)

167 return BO;

168 return nullptr;

169}

170

172 unsigned Opcode2) {

174 if (BO && BO->hasOneUse() &&

175 (BO->getOpcode() == Opcode1 || BO->getOpcode() == Opcode2))

177 return BO;

178 return nullptr;

179}

180

181void ReassociatePass::BuildRankMap(Function &F,

182 ReversePostOrderTraversal<Function*> &RPOT) {

183 unsigned Rank = 2;

184

185

186 for (auto &Arg : F.args()) {

187 ValueRankMap[&Arg] = ++Rank;

188 LLVM_DEBUG(dbgs() << "Calculated Rank[" << Arg.getName() << "] = " << Rank

189 << "\n");

190 }

191

192

193 for (BasicBlock *BB : RPOT) {

194 unsigned BBRank = RankMap[BB] = ++Rank << 16;

195

196

197

198

199 for (Instruction &I : *BB)

201 ValueRankMap[&I] = ++BBRank;

202 }

203}

204

205unsigned ReassociatePass::getRank(Value *V) {

207 if () {

208 if (isa(V)) return ValueRankMap[V];

209 return 0;

210 }

211

212 if (unsigned Rank = ValueRankMap[I])

213 return Rank;

214

215

216

217

218

219 unsigned Rank = 0, MaxRank = RankMap[I->getParent()];

220 for (unsigned i = 0, e = I->getNumOperands(); i != e && Rank != MaxRank; ++i)

221 Rank = std::max(Rank, getRank(I->getOperand(i)));

222

223

224

227 ++Rank;

228

229 LLVM_DEBUG(dbgs() << "Calculated Rank[" << V->getName() << "] = " << Rank

230 << "\n");

231

232 return ValueRankMap[I] = Rank;

233}

234

235

236void ReassociatePass::canonicalizeOperands(Instruction *I) {

238 assert(I->isCommutative() && "Expected commutative operator.");

239

243 return;

246 MadeChange = true;

247 }

248}

249

252 Value *FlagsOp) {

253 if (S1->getType()->isIntOrIntVectorTy())

254 return BinaryOperator::CreateAdd(S1, S2, Name, InsertBefore);

255 else {

257 BinaryOperator::CreateFAdd(S1, S2, Name, InsertBefore);

259 return Res;

260 }

261}

262

265 Value *FlagsOp) {

266 if (S1->getType()->isIntOrIntVectorTy())

267 return BinaryOperator::CreateMul(S1, S2, Name, InsertBefore);

268 else {

270 BinaryOperator::CreateFMul(S1, S2, Name, InsertBefore);

272 return Res;

273 }

274}

275

278 Value *FlagsOp) {

279 if (S1->getType()->isIntOrIntVectorTy())

281

284

285 return UnaryOperator::CreateFNeg(S1, Name, InsertBefore);

286}

287

288

291 "Expected a Negate!");

292

295 Constant *NegOne = Ty->isIntOrIntVectorTy() ?

297

304 return Res;

305}

306

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

387 "Expected a UnaryOperator or BinaryOperator!");

389 unsigned Opcode = I->getOpcode();

390 assert(I->isAssociative() && I->isCommutative() &&

391 "Expected an associative and commutative operation!");

392

393

394

395

396

397

398

399

400

401

402

404 Worklist.push_back(std::make_pair(I, 1));

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

423 LeafMap Leaves;

426

427#ifndef NDEBUG

429#endif

430 while (!Worklist.empty()) {

431

433

434 Flags.mergeFlags(*I);

435

436 for (unsigned OpIdx = 0; OpIdx < I->getNumOperands(); ++OpIdx) {

438 LLVM_DEBUG(dbgs() << "OPERAND: " << *Op << " (" << Weight << ")\n");

439 assert((->hasUseList() || ->use_empty()) &&

440 "No uses, so how did we get to it?!");

441

442

443

445 assert(Visited.insert(Op).second && "Not first visit!");

446 LLVM_DEBUG(dbgs() << "DIRECT ADD: " << *Op << " (" << Weight << ")\n");

447 Worklist.push_back(std::make_pair(BO, Weight));

448 continue;

449 }

450

451

452 LeafMap::iterator It = Leaves.find(Op);

453 if (It == Leaves.end()) {

454

455 assert(Visited.insert(Op).second && "Not first visit!");

456 if (->hasOneUse()) {

457

458

460 << "ADD USES LEAF: " << *Op << " (" << Weight << ")\n");

462 Leaves[Op] = Weight;

463 continue;

464 }

465

466 } else {

467

468 assert(It != Leaves.end() && Visited.count(Op) &&

469 "In leaf map but not visited!");

470

471

472 It->second += Weight;

473 assert(It->second >= Weight && "Weight overflows");

474

475

476

477 if (->hasOneUse())

478 continue;

479

480

481 Weight = It->second;

482 Leaves.erase(It);

483 }

484

485

486

487

488

493 "Should have been handled above!");

494 assert(Op->hasOneUse() && "Has uses outside the expression tree!");

495

496

497

498

499

500

506 << "MORPH LEAF: " << *Op << " (" << Weight << ") TO ");

509 Worklist.push_back(std::make_pair(Mul, Weight));

510 for (User *U : Mul->users()) {

512 ToRedo.insert(UserBO);

513 }

516 continue;

517 }

518

519

520

521 LLVM_DEBUG(dbgs() << "ADD LEAF: " << *Op << " (" << Weight << ")\n");

524 Leaves[Op] = Weight;

525 }

526 }

527

528

529

530 for (Value *V : LeafOrder) {

531 LeafMap::iterator It = Leaves.find(V);

532 if (It == Leaves.end())

533

534 continue;

536 uint64_t Weight = It->second;

537

538 It->second = 0;

539 Ops.push_back(std::make_pair(V, Weight));

540 if (Opcode == Instruction::Add && Flags.AllKnownNonNegative && Flags.HasNSW)

542 else if (Opcode == Instruction::Mul) {

543

544

545 if (Flags.AllKnownNonZero &&

546 (Flags.HasNUW || (Flags.HasNSW && Flags.AllKnownNonNegative))) {

548 if (Flags.HasNSW && Flags.AllKnownNonNegative)

550 }

551 }

552 }

553

554

555

556

557 if (Ops.empty()) {

559 assert(Identity && "Associative operation without identity!");

560 Ops.emplace_back(Identity, 1);

561 }

562

564}

565

566

567

568void ReassociatePass::RewriteExprTree(BinaryOperator *I,

569 SmallVectorImpl &Ops,

570 OverflowTracking Flags) {

571 assert(Ops.size() > 1 && "Single values should be used directly!");

572

573

574

575

576

577

578

579

580

581

582

583

585 unsigned Opcode = I->getOpcode();

586 BinaryOperator *Op = I;

587

588

589

590

591

592

593

594

595

596

597

598 SmallPtrSet<Value*, 8> NotRewritable;

601

602

603

604

605

606 BinaryOperator *ExpressionChangedStart = nullptr,

607 *ExpressionChangedEnd = nullptr;

608 for (unsigned i = 0; ; ++i) {

609

610

611

612 if (i+2 == Ops.size()) {

615 Value *OldLHS = Op->getOperand(0);

616 Value *OldRHS = Op->getOperand(1);

617

618 if (NewLHS == OldLHS && NewRHS == OldRHS)

619

620 break;

621

622 if (NewLHS == OldRHS && NewRHS == OldLHS) {

623

625 Op->swapOperands();

627 MadeChange = true;

628 ++NumChanged;

629 break;

630 }

631

632

633

635 if (NewLHS != OldLHS) {

637 if (BO && !NotRewritable.count(BO))

639 Op->setOperand(0, NewLHS);

640 }

641 if (NewRHS != OldRHS) {

643 if (BO && !NotRewritable.count(BO))

645 Op->setOperand(1, NewRHS);

646 }

648

649 ExpressionChangedStart = Op;

650 if (!ExpressionChangedEnd)

651 ExpressionChangedEnd = Op;

652 MadeChange = true;

653 ++NumChanged;

654

655 break;

656 }

657

658

659

661 if (NewRHS != Op->getOperand(1)) {

663 if (NewRHS == Op->getOperand(0)) {

664

665

666 Op->swapOperands();

667 } else {

668

670 if (BO && !NotRewritable.count(BO))

672 Op->setOperand(1, NewRHS);

673 ExpressionChangedStart = Op;

674 if (!ExpressionChangedEnd)

675 ExpressionChangedEnd = Op;

676 }

678 MadeChange = true;

679 ++NumChanged;

680 }

681

682

683

684

686 if (BO && !NotRewritable.count(BO)) {

687 Op = BO;

688 continue;

689 }

690

691

692

693

694

695

696

697

698 BinaryOperator *NewOp;

699 if (NodesToRewrite.empty()) {

702 Poison, "", I->getIterator());

705 } else {

707 }

708

710 Op->setOperand(0, NewOp);

712 ExpressionChangedStart = Op;

713 if (!ExpressionChangedEnd)

714 ExpressionChangedEnd = Op;

715 MadeChange = true;

716 ++NumChanged;

717 Op = NewOp;

718 }

719

720

721

722

723

724 if (ExpressionChangedStart) {

725 bool ClearFlags = true;

726 do {

727

728 if (ClearFlags) {

730 FastMathFlags Flags = I->getFastMathFlags();

733 } else {

734 Flags.applyFlags(*ExpressionChangedStart);

735 }

736 }

737

738 if (ExpressionChangedStart == ExpressionChangedEnd)

739 ClearFlags = false;

740 if (ExpressionChangedStart == I)

741 break;

742

743

744

745

746

747 if (ClearFlags)

749

750 ExpressionChangedStart->moveBefore(I->getIterator());

751 ExpressionChangedStart =

753 } while (true);

754 }

755

756

757 RedoInsts.insert_range(NodesToRewrite);

758}

759

760

761

762

763

764

765

766

771 Constant *Res = C->getType()->isFPOrFPVectorTy()

774 if (Res)

775 return Res;

776 }

777

778

779

780

781

782

783

784

785

786

789

790 I->setOperand(0, NegateValue(I->getOperand(0), BI, ToRedo));

791 I->setOperand(1, NegateValue(I->getOperand(1), BI, ToRedo));

792 if (I->getOpcode() == Instruction::Add) {

793 I->setHasNoUnsignedWrap(false);

794 I->setHasNoSignedWrap(false);

795 }

796

797

798

799

800

801

803 I->setName(I->getName()+".neg");

804

805

806

808 return I;

809 }

810

811

812

815 continue;

816

817

818

819

820

822

823

826 C->containsUndefOrPoisonElement())

827 continue;

828

829

830 if (!TheNeg ||

832 continue;

833

836 auto InsertPtOpt = InstInput->getInsertionPointAfterDef();

837 if (!InsertPtOpt)

838 continue;

839 InsertPt = *InsertPtOpt;

840 } else {

844 ->getIterator();

845 }

846

847

848

849

850 if (TheNeg->getParent() != InsertPt->getParent())

852 TheNeg->moveBefore(*InsertPt->getParent(), InsertPt);

853

854 if (TheNeg->getOpcode() == Instruction::Sub) {

857 } else {

859 }

860 ToRedo.insert(TheNeg);

861 return TheNeg;

862 }

863

864

865

868

870 ToRedo.insert(NewNeg);

871 return NewNeg;

872}

873

874

875

876

877

878

882

883 auto Enqueue = [&](Value *V) {

885

886 if ()

887 return false;

888

889 if (Visited.insert(I).second)

891 return true;

892 };

893

894 if (!Enqueue(Or))

895 return false;

896

897 while (!Worklist.empty()) {

899

900

901 switch (I->getOpcode()) {

902 case Instruction::Or:

903

904 for (Value *Op : I->operands())

905 if (!Enqueue(Op))

906 return false;

907 continue;

908

909 case Instruction::Shl:

910 case Instruction::ZExt:

911

912 if (!Enqueue(I->getOperand(0)))

913 return false;

914 continue;

915

916 case Instruction::Load:

917

918 continue;

919

920 default:

921 return false;

922 }

923 }

924

925 return true;

926}

927

928

930

931

932

934 for (auto Op : {Instruction::Add, Instruction::Sub, Instruction::Mul,

935 Instruction::Shl})

937 return true;

938 return false;

939 };

940

942 return true;

943

944 Value *VB = Or->user_back();

946 return true;

947

948 return false;

949}

950

951

952

954

956 Or->getIterator(), Or);

957 New->setHasNoSignedWrap();

958 New->setHasNoUnsignedWrap();

959 New->takeName(Or);

960

961

962 Or->replaceAllUsesWith(New);

963 New->setDebugLoc(Or->getDebugLoc());

964

965 LLVM_DEBUG(dbgs() << "Converted or into an add: " << *New << '\n');

966 return New;

967}

968

969

971

973 return false;

974

975

977 return false;

978

979

980

981 Value *V0 = Sub->getOperand(0);

982 if (isReassociableOp(V0, Instruction::Add, Instruction::FAdd) ||

984 return true;

985 Value *V1 = Sub->getOperand(1);

986 if (isReassociableOp(V1, Instruction::Add, Instruction::FAdd) ||

988 return true;

989 Value *VB = Sub->user_back();

990 if (Sub->hasOneUse() &&

991 (isReassociableOp(VB, Instruction::Add, Instruction::FAdd) ||

993 return true;

994

995 return false;

996}

997

998

999

1002

1003

1004

1005

1006

1012 New->takeName(Sub);

1013

1014

1015 Sub->replaceAllUsesWith(New);

1016 New->setDebugLoc(Sub->getDebugLoc());

1017

1019 return New;

1020}

1021

1022

1023

1028 assert(MulCst && "Constant folding of immediate constants failed");

1029

1033 Mul->takeName(Shl);

1034

1035

1038

1039

1040

1041

1042

1046 if (NSW && (NUW || SA->getValue().ult(BitWidth - 1)))

1047 Mul->setHasNoSignedWrap(true);

1048 Mul->setHasNoUnsignedWrap(NUW);

1049 return Mul;

1050}

1051

1052

1053

1054

1056 unsigned i, Value *X) {

1057 unsigned XRank = Ops[i].Rank;

1058 unsigned e = Ops.size();

1059 for (unsigned j = i+1; j != e && Ops[j].Rank == XRank; ++j) {

1061 return j;

1064 if (I1->isIdenticalTo(I2))

1065 return j;

1066 }

1067

1068 for (unsigned j = i-1; j != ~0U && Ops[j].Rank == XRank; --j) {

1070 return j;

1073 if (I1->isIdenticalTo(I2))

1074 return j;

1075 }

1076 return i;

1077}

1078

1079

1080

1083 if (Ops.size() == 1) return Ops.back();

1084

1085 Value *V1 = Ops.pop_back_val();

1087 auto *NewAdd = CreateAdd(V2, V1, "reass.add", I->getIterator(), I);

1088 NewAdd->setDebugLoc(I->getDebugLoc());

1089 return NewAdd;

1090}

1091

1092

1093

1094

1095

1096

1099 BinaryOperator *BO = isReassociableOp(V, Instruction::Mul, Instruction::FMul);

1100 if (!BO)

1101 return nullptr;

1102

1104 OverflowTracking Flags;

1110

1111 bool FoundFactor = false;

1112 bool NeedsNegate = false;

1113 for (unsigned i = 0, e = Factors.size(); i != e; ++i) {

1114 if (Factors[i].Op == Factor) {

1115 FoundFactor = true;

1117 break;

1118 }

1119

1120

1123 if (FC1->getValue() == -FC2->getValue()) {

1124 FoundFactor = NeedsNegate = true;

1126 break;

1127 }

1130 const APFloat &F1 = FC1->getValueAPF();

1131 APFloat F2(FC2->getValueAPF());

1132 F2.changeSign();

1133 if (F1 == F2) {

1134 FoundFactor = NeedsNegate = true;

1136 break;

1137 }

1138 }

1139 }

1140 }

1141

1142 if (!FoundFactor) {

1143

1144 RewriteExprTree(BO, Factors, Flags);

1145 return nullptr;

1146 }

1147

1149

1150

1151

1152 if (Factors.size() == 1) {

1153 RedoInsts.insert(BO);

1154 V = Factors[0].Op;

1155 } else {

1156 RewriteExprTree(BO, Factors, Flags);

1157 V = BO;

1158 }

1159

1160 if (NeedsNegate) {

1161 V = CreateNeg(V, "neg", InsertPt, BO);

1163 }

1164

1165 return V;

1166}

1167

1168

1169

1170

1171

1175 if (!BO) {

1177 return;

1178 }

1179

1180

1183}

1184

1185

1186

1187

1190

1191

1192 for (unsigned i = 0, e = Ops.size(); i != e; ++i) {

1193

1198 if (FoundX != i) {

1199 if (Opcode == Instruction::And)

1201

1202 if (Opcode == Instruction::Or)

1204 }

1205 }

1206

1207

1208

1210 if (i+1 != Ops.size() && Ops[i+1].Op == Ops[i].Op) {

1211 if (Opcode == Instruction::And || Opcode == Instruction::Or) {

1212

1213 Ops.erase(Ops.begin()+i);

1214 --i; --e;

1215 ++NumAnnihil;

1216 continue;

1217 }

1218

1219

1220 assert(Opcode == Instruction::Xor);

1221 if (e == 2)

1223

1224

1225 Ops.erase(Ops.begin()+i, Ops.begin()+i+2);

1226 i -= 1; e -= 2;

1227 ++NumAnnihil;

1228 }

1229 }

1230 return nullptr;

1231}

1232

1233

1234

1235

1236

1237

1239 const APInt &ConstOpnd) {

1240 if (ConstOpnd.isZero())

1241 return nullptr;

1242

1244 return Opnd;

1245

1247 Opnd, ConstantInt::get(Opnd->getType(), ConstOpnd), "and.ra",

1248 InsertBefore);

1249 I->setDebugLoc(InsertBefore->getDebugLoc());

1250 return I;

1251}

1252

1253

1254

1255

1256

1257

1258

1260 APInt &ConstOpnd, Value *&Res) {

1261

1262

1263

1264

1266 return false;

1267

1269 return false;

1270

1272 if (C1 != ConstOpnd)

1273 return false;

1274

1277

1278 ConstOpnd ^= C1;

1279

1281 RedoInsts.insert(T);

1282 return true;

1283}

1284

1285

1286

1287

1288

1289

1290

1291

1292

1294 XorOpnd *Opnd2, APInt &ConstOpnd,

1298 return false;

1299

1300

1301 int DeadInstNum = 1;

1303 DeadInstNum++;

1305 DeadInstNum++;

1306

1307

1308

1309

1310

1311

1312

1316

1319 APInt C3((~C1) ^ C2);

1320

1321

1322 if (!C3.isZero() && !C3.isAllOnes()) {

1323 int NewInstNum = ConstOpnd.getBoolValue() ? 1 : 2;

1324 if (NewInstNum > DeadInstNum)

1325 return false;

1326 }

1327

1329 ConstOpnd ^= C1;

1330 } else if (Opnd1->isOrExpr()) {

1331

1332

1335 APInt C3 = C1 ^ C2;

1336

1337

1339 int NewInstNum = ConstOpnd.getBoolValue() ? 1 : 2;

1340 if (NewInstNum > DeadInstNum)

1341 return false;

1342 }

1343

1345 ConstOpnd ^= C3;

1346 } else {

1347

1348

1351 APInt C3 = C1 ^ C2;

1353 }

1354

1355

1356

1358 RedoInsts.insert(T);

1360 RedoInsts.insert(T);

1361

1362 return true;

1363}

1364

1365

1366

1367

1368Value *ReassociatePass::OptimizeXor(Instruction *I,

1369 SmallVectorImpl &Ops) {

1371 return V;

1372

1373 if (Ops.size() == 1)

1374 return nullptr;

1375

1378 Type *Ty = Ops[0].Op->getType();

1380

1381

1384 const APInt *C;

1385

1387 ConstOpnd ^= *C;

1388 } else {

1390 O.setSymbolicRank(getRank(O.getSymbolicPart()));

1392 }

1393 }

1394

1395

1396

1397

1398

1399

1402

1403

1404

1405

1406

1407

1408

1409

1410

1411

1412

1413

1414

1415

1417 return LHS->getSymbolicRank() < RHS->getSymbolicRank();

1418 });

1419

1420

1421 XorOpnd *PrevOpnd = nullptr;

1423 for (unsigned i = 0, e = Opnds.size(); i < e; i++) {

1424 XorOpnd *CurrOpnd = OpndPtrs[i];

1425

1427

1428

1429 if (!ConstOpnd.isZero() &&

1430 CombineXorOpnd(I->getIterator(), CurrOpnd, ConstOpnd, CV)) {

1432 if (CV)

1433 *CurrOpnd = XorOpnd(CV);

1434 else {

1436 continue;

1437 }

1438 }

1439

1440 if (!PrevOpnd || CurrOpnd->getSymbolicPart() != PrevOpnd->getSymbolicPart()) {

1441 PrevOpnd = CurrOpnd;

1442 continue;

1443 }

1444

1445

1446

1447 if (CombineXorOpnd(I->getIterator(), CurrOpnd, PrevOpnd, ConstOpnd, CV)) {

1448

1449 PrevOpnd->Invalidate();

1450 if (CV) {

1451 *CurrOpnd = XorOpnd(CV);

1452 PrevOpnd = CurrOpnd;

1453 } else {

1455 PrevOpnd = nullptr;

1456 }

1458 }

1459 }

1460

1461

1463 Ops.clear();

1464 for (const XorOpnd &O : Opnds) {

1465 if (O.isInvalid())

1466 continue;

1467 ValueEntry VE(getRank(O.getValue()), O.getValue());

1468 Ops.push_back(VE);

1469 }

1470 if (!ConstOpnd.isZero()) {

1471 Value *C = ConstantInt::get(Ty, ConstOpnd);

1473 Ops.push_back(VE);

1474 }

1475 unsigned Sz = Ops.size();

1476 if (Sz == 1)

1477 return Ops.back().Op;

1478 if (Sz == 0) {

1480 return ConstantInt::get(Ty, ConstOpnd);

1481 }

1482 }

1483

1484 return nullptr;

1485}

1486

1487

1488

1489

1490Value *ReassociatePass::OptimizeAdd(Instruction *I,

1491 SmallVectorImpl &Ops) {

1492

1493

1494

1495

1496

1497 for (unsigned i = 0, e = Ops.size(); i != e; ++i) {

1499

1500

1501

1502 if (i+1 != Ops.size() && Ops[i+1].Op == TheOp) {

1503

1504 unsigned NumFound = 0;

1505 do {

1506 Ops.erase(Ops.begin()+i);

1507 ++NumFound;

1508 } while (i != Ops.size() && Ops[i].Op == TheOp);

1509

1510 LLVM_DEBUG(dbgs() << "\nFACTORING [" << NumFound << "]: " << *TheOp

1511 << '\n');

1512 ++NumFactor;

1513

1514

1517 ConstantInt::get(Ty, NumFound) : ConstantFP::get(Ty, NumFound);

1519 Mul->setDebugLoc(I->getDebugLoc());

1520

1521

1522

1523

1524 RedoInsts.insert(Mul);

1525

1526

1527 if (Ops.empty())

1528 return Mul;

1529

1530

1531

1532

1534

1535 --i;

1536 e = Ops.size();

1537 continue;

1538 }

1539

1540

1544 continue;

1545

1547 if (FoundX == i)

1548 continue;

1549

1550

1551 if (Ops.size() == 2 &&

1554

1555

1558

1559 Ops.erase(Ops.begin()+i);

1560 if (i < FoundX)

1561 --FoundX;

1562 else

1563 --i;

1564 Ops.erase(Ops.begin()+FoundX);

1565 ++NumAnnihil;

1566 --i;

1567 e -= 2;

1568

1569

1573 e += 1;

1574 }

1575 }

1576

1577

1578

1579

1580

1581

1582 DenseMap<Value*, unsigned> FactorOccurrences;

1583

1584

1585

1586 unsigned MaxOcc = 0;

1587 Value *MaxOccVal = nullptr;

1589 BinaryOperator *BOp =

1591 if (!BOp)

1592 continue;

1593

1594

1595 SmallVector<Value*, 8> Factors;

1597 assert(Factors.size() > 1 && "Bad linearize!");

1598

1599

1600 SmallPtrSet<Value*, 8> Duplicates;

1603 continue;

1604

1605 unsigned Occ = ++FactorOccurrences[Factor];

1606 if (Occ > MaxOcc) {

1607 MaxOcc = Occ;

1609 }

1610

1611

1612

1613

1615 if (CI->isNegative() && !CI->isMinValue(true)) {

1616 Factor = ConstantInt::get(CI->getContext(), -CI->getValue());

1618 continue;

1619 unsigned Occ = ++FactorOccurrences[Factor];

1620 if (Occ > MaxOcc) {

1621 MaxOcc = Occ;

1623 }

1624 }

1626 if (CF->isNegative()) {

1627 APFloat F(CF->getValueAPF());

1628 F.changeSign();

1629 Factor = ConstantFP::get(CF->getContext(), F);

1631 continue;

1632 unsigned Occ = ++FactorOccurrences[Factor];

1633 if (Occ > MaxOcc) {

1634 MaxOcc = Occ;

1636 }

1637 }

1638 }

1639 }

1640 }

1641

1642

1643 if (MaxOcc > 1) {

1644 LLVM_DEBUG(dbgs() << "\nFACTORING [" << MaxOcc << "]: " << *MaxOccVal

1645 << '\n');

1646 ++NumFactor;

1647

1648

1649

1650

1651

1653 I->getType()->isIntOrIntVectorTy()

1654 ? BinaryOperator::CreateAdd(MaxOccVal, MaxOccVal)

1655 : BinaryOperator::CreateFAdd(MaxOccVal, MaxOccVal);

1656

1658 for (unsigned i = 0; i != Ops.size(); ++i) {

1659

1660 BinaryOperator *BOp =

1662 if (!BOp)

1663 continue;

1664

1665 if (Value *V = RemoveFactorFromExpression(Ops[i].Op, MaxOccVal,

1666 I->getDebugLoc())) {

1667

1668

1669 for (unsigned j = Ops.size(); j != i;) {

1670 --j;

1673 Ops.erase(Ops.begin()+j);

1674 }

1675 }

1676 --i;

1677 }

1678 }

1679

1680

1682

1683 unsigned NumAddedValues = NewMulOps.size();

1685

1686

1687

1688

1689 assert(NumAddedValues > 1 && "Each occurrence should contribute a value");

1690 (void)NumAddedValues;

1692 RedoInsts.insert(VI);

1693

1694

1697

1698

1699

1700 RedoInsts.insert(V2);

1701

1702

1703

1704 if (Ops.empty())

1705 return V2;

1706

1707

1708

1709

1711 }

1712

1713 return nullptr;

1714}

1715

1716

1717

1718

1719

1720

1721

1722

1723

1724

1725

1726

1729

1730

1731 unsigned FactorPowerSum = 0;

1732 for (unsigned Idx = 1, Size = Ops.size(); Idx < Size; ++Idx) {

1734

1735

1736 unsigned Count = 1;

1737 for (; Idx < Size && Ops[Idx].Op == Op; ++Idx)

1739

1741 FactorPowerSum += Count;

1742 }

1743

1744

1745

1746

1747

1748 if (FactorPowerSum < 4)

1749 return false;

1750

1751

1752 FactorPowerSum = 0;

1753 for (unsigned Idx = 1; Idx < Ops.size(); ++Idx) {

1755

1756

1757 unsigned Count = 1;

1758 for (; Idx < Ops.size() && Ops[Idx].Op == Op; ++Idx)

1761 continue;

1762

1765 FactorPowerSum += Count;

1768 }

1769

1770

1771

1772 assert(FactorPowerSum >= 4);

1773

1775 return LHS.Power > RHS.Power;

1776 });

1777 return true;

1778}

1779

1780

1783 if (Ops.size() == 1)

1784 return Ops.back();

1785

1787 do {

1788 if (LHS->getType()->isIntOrIntVectorTy())

1789 LHS = Builder.CreateMul(LHS, Ops.pop_back_val());

1790 else

1791 LHS = Builder.CreateFMul(LHS, Ops.pop_back_val());

1792 } while ( Ops .empty());

1793

1794 return LHS;

1795}

1796

1797

1798

1799

1800

1801

1802

1804ReassociatePass::buildMinimalMultiplyDAG(IRBuilderBase &Builder,

1805 SmallVectorImpl &Factors) {

1806 assert(Factors[0].Power);

1808 for (unsigned LastIdx = 0, Idx = 1, Size = Factors.size();

1809 Idx < Size && Factors[Idx].Power > 0; ++Idx) {

1810 if (Factors[Idx].Power != Factors[LastIdx].Power) {

1811 LastIdx = Idx;

1812 continue;

1813 }

1814

1815

1816

1817

1820 do {

1822 ++Idx;

1823 } while (Idx < Size && Factors[Idx].Power == Factors[LastIdx].Power);

1824

1825

1826

1829 RedoInsts.insert(MI);

1830

1831 LastIdx = Idx;

1832 }

1833

1834

1837 return LHS.Power == RHS.Power;

1838 }),

1839 Factors.end());

1840

1841

1842

1843

1844 for (Factor &F : Factors) {

1845 if (F.Power & 1)

1847 F.Power >>= 1;

1848 }

1849 if (Factors[0].Power) {

1850 Value *SquareRoot = buildMinimalMultiplyDAG(Builder, Factors);

1851 OuterProduct.push_back(SquareRoot);

1852 OuterProduct.push_back(SquareRoot);

1853 }

1854 if (OuterProduct.size() == 1)

1855 return OuterProduct.front();

1856

1858 return V;

1859}

1860

1861Value *ReassociatePass::OptimizeMul(BinaryOperator *I,

1862 SmallVectorImpl &Ops) {

1863

1864

1865 if (Ops.size() < 4)

1866 return nullptr;

1867

1868

1869

1870

1873 return nullptr;

1874

1876

1877

1878

1881

1882 Value *V = buildMinimalMultiplyDAG(Builder, Factors);

1883 if (Ops.empty())

1884 return V;

1885

1888 return nullptr;

1889}

1890

1891Value *ReassociatePass::OptimizeExpression(BinaryOperator *I,

1892 SmallVectorImpl &Ops) {

1893

1894

1895 const DataLayout &DL = I->getDataLayout();

1897 unsigned Opcode = I->getOpcode();

1898 while ( Ops .empty()) {

1900 if (!Cst) {

1901 Ops.pop_back();

1902 Cst = C;

1903 continue;

1904 }

1906 Ops.pop_back();

1907 Cst = Res;

1908 continue;

1909 }

1910 }

1911 break;

1912 }

1913

1914 if (Ops.empty())

1915 return Cst;

1916

1917

1918

1919

1922 return Cst;

1924 }

1925

1926 if (Ops.size() == 1) return Ops[0].Op;

1927

1928

1929

1931 switch (Opcode) {

1932 default: break;

1933 case Instruction::And:

1934 case Instruction::Or:

1937 break;

1938

1939 case Instruction::Xor:

1940 if (Value *Result = OptimizeXor(I, Ops))

1942 break;

1943

1944 case Instruction::Add:

1945 case Instruction::FAdd:

1946 if (Value *Result = OptimizeAdd(I, Ops))

1948 break;

1949

1950 case Instruction::Mul:

1951 case Instruction::FMul:

1952 if (Value *Result = OptimizeMul(I, Ops))

1954 break;

1955 }

1956

1958 return OptimizeExpression(I, Ops);

1959 return nullptr;

1960}

1961

1962

1963

1964void ReassociatePass::RecursivelyEraseDeadInsts(Instruction *I,

1965 OrderedSet &Insts) {

1968 ValueRankMap.erase(I);

1969 Insts.remove(I);

1970 RedoInsts.remove(I);

1972 I->eraseFromParent();

1973 for (auto *Op : Ops)

1975 if (OpInst->use_empty())

1976 Insts.insert(OpInst);

1977}

1978

1979

1980void ReassociatePass::EraseInst(Instruction *I) {

1983

1984 SmallVector<Value *, 8> Ops(I->operands());

1985

1986 ValueRankMap.erase(I);

1987 RedoInsts.remove(I);

1989 I->eraseFromParent();

1990

1991 SmallPtrSet<Instruction *, 8> Visited;

1994

1995

1996 unsigned Opcode = Op->getOpcode();

1997 while (Op->hasOneUse() && Op->user_back()->getOpcode() == Opcode &&

1999 Op = Op->user_back();

2000

2001

2002

2003

2004

2005

2006 if (ValueRankMap.contains(Op))

2007 RedoInsts.insert(Op);

2008 }

2009

2010 MadeChange = true;

2011}

2012

2013

2014

2015

2018

2019

2022 return;

2023

2024

2025

2027 switch (I->getOpcode()) {

2028 case Instruction::FMul:

2029

2031 break;

2032

2035 LLVM_DEBUG(dbgs() << "FMul with negative constant: " << *I << '\n');

2036 }

2039 break;

2040 case Instruction::FDiv:

2041

2044 break;

2045

2046 if ((match(I->getOperand(0), m_APFloat(C)) && C->isNegative()) ||

2049 LLVM_DEBUG(dbgs() << "FDiv with negative constant: " << *I << '\n');

2050 }

2053 break;

2054 default:

2055 break;

2056 }

2057}

2058

2059

2060

2061

2062Instruction *ReassociatePass::canonicalizeNegFPConstantsForOp(Instruction *I,

2063 Instruction *Op,

2064 Value *OtherOp) {

2065 assert((I->getOpcode() == Instruction::FAdd ||

2066 I->getOpcode() == Instruction::FSub) && "Expected fadd/fsub");

2067

2068

2069

2070 SmallVector<Instruction *, 4> Candidates;

2072 if (Candidates.empty())

2073 return nullptr;

2074

2075

2076

2077

2078 bool IsFSub = I->getOpcode() == Instruction::FSub;

2079 bool NeedsSubtract = !IsFSub && Candidates.size() % 2 == 1;

2081 return nullptr;

2082

2083 for (Instruction *Negatible : Candidates) {

2087 "Expecting only 1 constant operand");

2088 assert(C->isNegative() && "Expected negative FP constant");

2089 Negatible->setOperand(0, ConstantFP::get(Negatible->getType(), abs(*C)));

2090 MadeChange = true;

2091 }

2094 "Expecting only 1 constant operand");

2095 assert(C->isNegative() && "Expected negative FP constant");

2096 Negatible->setOperand(1, ConstantFP::get(Negatible->getType(), abs(*C)));

2097 MadeChange = true;

2098 }

2099 }

2100 assert(MadeChange == true && "Negative constant candidate was not changed");

2101

2102

2103 if (Candidates.size() % 2 == 0)

2104 return I;

2105

2106

2107

2108 assert(Candidates.size() % 2 == 1 && "Expected odd number");

2113 RedoInsts.insert(I);

2115}

2116

2117

2118

2119

2120

2121

2122

2123

2124

2125Instruction *ReassociatePass::canonicalizeNegFPConstants(Instruction *I) {

2126 LLVM_DEBUG(dbgs() << "Combine negations for: " << *I << '\n');

2130 if (Instruction *R = canonicalizeNegFPConstantsForOp(I, Op, X))

2131 I = R;

2133 if (Instruction *R = canonicalizeNegFPConstantsForOp(I, Op, X))

2134 I = R;

2136 if (Instruction *R = canonicalizeNegFPConstantsForOp(I, Op, X))

2137 I = R;

2138 return I;

2139}

2140

2141

2142

2143void ReassociatePass::OptimizeInst(Instruction *I) {

2144

2146 return;

2147

2148 if (I->getOpcode() == Instruction::Shl && isa(I->getOperand(1)))

2149

2150

2152 (I->hasOneUse() &&

2156 RedoInsts.insert(I);

2157 MadeChange = true;

2158 I = NI;

2159 }

2160

2161

2162

2163

2164 if (I->isCommutative())

2165 canonicalizeOperands(I);

2166

2167

2168 if (Instruction *Res = canonicalizeNegFPConstants(I))

2169 I = Res;

2170

2171

2172

2174 return;

2175

2176

2177

2178

2179

2180

2181

2182

2183 if (I->getType()->isIntOrIntVectorTy(1))

2184 return;

2185

2186

2187

2188 if (I->getOpcode() == Instruction::Or &&

2192 SimplifyQuery(I->getDataLayout(),

2193 nullptr, nullptr, I)))) {

2195 RedoInsts.insert(I);

2196 MadeChange = true;

2197 I = NI;

2198 }

2199

2200

2201

2202 if (I->getOpcode() == Instruction::Sub) {

2205 RedoInsts.insert(I);

2206 MadeChange = true;

2207 I = NI;

2209

2210

2212 (->hasOneUse() ||

2215

2216

2217 for (User *U : NI->users()) {

2219 RedoInsts.insert(Tmp);

2220 }

2221 RedoInsts.insert(I);

2222 MadeChange = true;

2223 I = NI;

2224 }

2225 }

2226 } else if (I->getOpcode() == Instruction::FNeg ||

2227 I->getOpcode() == Instruction::FSub) {

2230 RedoInsts.insert(I);

2231 MadeChange = true;

2232 I = NI;

2234

2235

2237 I->getOperand(0);

2239 (->hasOneUse() ||

2241

2242

2244 for (User *U : NI->users()) {

2246 RedoInsts.insert(Tmp);

2247 }

2248 RedoInsts.insert(I);

2249 MadeChange = true;

2250 I = NI;

2251 }

2252 }

2253 }

2254

2255

2256 if (->isAssociative()) return;

2258

2259

2260

2261 unsigned Opcode = BO->getOpcode();

2263

2264

2265

2268 RedoInsts.insert(BO->user_back());

2269 return;

2270 }

2271

2272

2273

2276 return;

2279 return;

2280

2281 ReassociateExpression(BO);

2282}

2283

2284void ReassociatePass::ReassociateExpression(BinaryOperator *I) {

2285

2286

2288 OverflowTracking Flags;

2291 Ops.reserve(Tree.size());

2293 Ops.append(E.second, ValueEntry(getRank(E.first), E.first));

2294

2296

2297

2298

2299

2300

2301

2302

2304

2305

2306

2307 if (Value *V = OptimizeExpression(I, Ops)) {

2308 if (V == I)

2309

2310 return;

2311

2312

2313 LLVM_DEBUG(dbgs() << "Reassoc to scalar: " << *V << '\n');

2314 I->replaceAllUsesWith(V);

2316 if (I->getDebugLoc())

2317 VI->setDebugLoc(I->getDebugLoc());

2318 RedoInsts.insert(I);

2319 ++NumAnnihil;

2320 return;

2321 }

2322

2323

2324

2325

2326

2327 if (I->hasOneUse()) {

2328 if (I->getOpcode() == Instruction::Mul &&

2329 cast(I->user_back())->getOpcode() == Instruction::Add &&

2333 Ops.insert(Ops.begin(), Tmp);

2334 } else if (I->getOpcode() == Instruction::FMul &&

2336 Instruction::FAdd &&

2340 Ops.insert(Ops.begin(), Tmp);

2341 }

2342 }

2343

2345

2346 if (Ops.size() == 1) {

2348

2349 return;

2350

2351

2352

2353 I->replaceAllUsesWith(Ops[0].Op);

2355 OI->setDebugLoc(I->getDebugLoc());

2356 RedoInsts.insert(I);

2357 return;

2358 }

2359

2360 if (Ops.size() > 2 && Ops.size() <= GlobalReassociateLimit) {

2361

2362

2363

2364

2365

2366

2367 unsigned Max = 1;

2368 unsigned BestRank = 0;

2369 std::pair<unsigned, unsigned> BestPair;

2370 unsigned Idx = I->getOpcode() - Instruction::BinaryOpsBegin;

2371 unsigned LimitIdx = 0;

2372

2373

2374

2375

2376

2377

2378

2380 const BasicBlock *FirstSeenBB = nullptr;

2381 int StartIdx = Ops.size() - 1;

2382

2383

2384

2385

2386 for (int i = StartIdx - 1; i != -1; --i) {

2387 const Value *Val = Ops[i].Op;

2390 if (!CurrLeafInstr) {

2391

2392

2393

2394

2395

2396

2397

2398

2399

2400

2401

2402

2403

2404

2405

2406

2407

2408

2410 } else {

2411 SeenBB = CurrLeafInstr->getParent();

2412 }

2413

2414 if (!FirstSeenBB) {

2415 FirstSeenBB = SeenBB;

2416 continue;

2417 }

2418 if (FirstSeenBB != SeenBB) {

2419

2420

2421

2422 LimitIdx = i + 1;

2423 LLVM_DEBUG(dbgs() << "CSE reordering: Consider values between ["

2424 << LimitIdx << ", " << StartIdx << "]\n");

2425 break;

2426 }

2427 }

2428 }

2429 for (unsigned i = Ops.size() - 1; i > LimitIdx; --i) {

2430

2431 for (int j = i - 1; j >= (int)LimitIdx; --j) {

2432 unsigned Score = 0;

2435 if (std::less<Value *>()(Op1, Op0))

2437 auto it = PairMap[Idx].find({Op0, Op1});

2438 if (it != PairMap[Idx].end()) {

2439

2440

2441

2442

2443

2444 if (it->second.isValid())

2445 Score += it->second.Score;

2446 }

2447

2448 unsigned MaxRank = std::max(Ops[i].Rank, Ops[j].Rank);

2449

2450

2451

2452

2453

2454

2455

2456

2457

2458

2459

2460

2461

2462 if (Score > Max || (Score == Max && MaxRank < BestRank)) {

2463 BestPair = {j, i};

2464 Max = Score;

2465 BestRank = MaxRank;

2466 }

2467 }

2468 }

2469 if (Max > 1) {

2470 auto Op0 = Ops[BestPair.first];

2471 auto Op1 = Ops[BestPair.second];

2472 Ops.erase(&Ops[BestPair.second]);

2473 Ops.erase(&Ops[BestPair.first]);

2474 Ops.push_back(Op0);

2475 Ops.push_back(Op1);

2476 }

2477 }

2479 dbgs() << '\n');

2480

2481

2482 RewriteExprTree(I, Ops, Flags);

2483}

2484

2485void

2486ReassociatePass::BuildPairMap(ReversePostOrderTraversal<Function *> &RPOT) {

2487

2488 for (BasicBlock *BI : RPOT) {

2489 for (Instruction &I : *BI) {

2490 if (.isAssociative() || .isBinaryOp())

2491 continue;

2492

2493

2494 if (I.hasOneUse() && I.user_back()->getOpcode() == I.getOpcode())

2495 continue;

2496

2497

2498

2499

2500 SmallVector<Value *, 8> Worklist = { I.getOperand(0), I.getOperand(1) };

2501 SmallVector<Value *, 8> Ops;

2502 while (!Worklist.empty() && Ops.size() <= GlobalReassociateLimit) {

2506 Ops.push_back(Op);

2507 continue;

2508 }

2509

2514 }

2515

2516 if (Ops.size() > GlobalReassociateLimit)

2517 continue;

2518

2519

2520 unsigned BinaryIdx = I.getOpcode() - Instruction::BinaryOpsBegin;

2521 SmallSet<std::pair<Value *, Value*>, 32> Visited;

2522 for (unsigned i = 0; i < Ops.size() - 1; ++i) {

2523 for (unsigned j = i + 1; j < Ops.size(); ++j) {

2524

2527 if (std::less<Value *>()(Op1, Op0))

2529 if (!Visited.insert({Op0, Op1}).second)

2530 continue;

2531 auto res = PairMap[BinaryIdx].insert({{Op0, Op1}, {Op0, Op1, 1}});

2532 if (!res.second) {

2533

2534

2535

2536

2537 assert(res.first->second.isValid() && "WeakVH invalidated");

2538 ++res.first->second.Score;

2539 }

2540 }

2541 }

2542 }

2543 }

2544}

2545

2547

2548

2549

2550

2552

2553

2554 BuildRankMap(F, RPOT);

2555

2556

2557

2558

2559

2560

2561

2562

2563

2564

2565 BuildPairMap(RPOT);

2566

2568

2569

2571 assert(RankMap.count(&*BI) && "BB should be ranked.");

2572

2575 EraseInst(&*II++);

2576 } else {

2577 OptimizeInst(&*II);

2578 assert(II->getParent() == &*BI && "Moved to a different block!");

2579 ++II;

2580 }

2581

2582

2583

2585

2586

2587

2588

2589 while (!ToRedo.empty()) {

2592 RecursivelyEraseDeadInsts(I, ToRedo);

2594 }

2595 }

2596

2597

2598

2603 EraseInst(I);

2604 else

2605 OptimizeInst(I);

2606 }

2607 }

2608

2609

2612 for (auto &Entry : PairMap)

2613 Entry.clear();

2614

2618 return PA;

2619 }

2620

2622}

2623

2624namespace {

2625

2626class ReassociateLegacyPass : public FunctionPass {

2628

2629public:

2630 static char ID;

2631

2634 }

2635

2637 if (skipFunction(F))

2638 return false;

2639

2641 auto PA = Impl.run(F, DummyFAM);

2642 return !PA.areAllPreserved();

2643 }

2644

2645 void getAnalysisUsage(AnalysisUsage &AU) const override {

2650 }

2651};

2652

2653}

2654

2655char ReassociateLegacyPass::ID = 0;

2656

2658 "Reassociate expressions", false, false)

2659

2660

2662 return new ReassociateLegacyPass();

2663}

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

This file declares a class to represent arbitrary precision floating point values and provide a varie...

This file implements a class to represent arbitrary precision integral constant values and operations...

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

This is the interface for LLVM's primary stateless and local alias analysis.

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

This file contains the declarations for the subclasses of Constant, which represent the different fla...

This file defines the DenseMap class.

static bool runOnFunction(Function &F, bool PostInlining)

This is the interface for a simple mod/ref and alias analysis over globals.

This file provides various utilities for inspecting and working with the control flow graph in LLVM I...

This header defines various interfaces for pass management in LLVM.

static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L, ScalarEvolution *SE, LoopInfo *LI)

isInteresting - Test whether the given expression is "interesting" when used by the given expression,...

const size_t AbstractManglingParser< Derived, Alloc >::NumOps

const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]

static bool isReassociableOp(Instruction *I, unsigned IntOpcode, unsigned FPOpcode)

MachineInstr unsigned OpIdx

uint64_t IntrinsicInst * II

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

This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.

static bool LinearizeExprTree(Instruction *I, SmallVectorImpl< RepeatedValue > &Ops, ReassociatePass::OrderedSet &ToRedo, OverflowTracking &Flags)

Given an associative binary expression, return the leaf nodes in Ops along with their weights (how ma...

Definition Reassociate.cpp:382

static void PrintOps(Instruction *I, const SmallVectorImpl< ValueEntry > &Ops)

Print out the expression identified in the Ops list.

Definition Reassociate.cpp:82

static bool ShouldBreakUpSubtract(Instruction *Sub)

Return true if we should break up this subtract of X-Y into (X + -Y).

Definition Reassociate.cpp:970

static Value * buildMultiplyTree(IRBuilderBase &Builder, SmallVectorImpl< Value * > &Ops)

Build a tree of multiplies, computing the product of Ops.

Definition Reassociate.cpp:1781

static void getNegatibleInsts(Value *V, SmallVectorImpl< Instruction * > &Candidates)

Recursively analyze an expression to build a list of instructions that have negative floating-point c...

Definition Reassociate.cpp:2016

static BinaryOperator * CreateMul(Value *S1, Value *S2, const Twine &Name, BasicBlock::iterator InsertBefore, Value *FlagsOp)

Definition Reassociate.cpp:263

static BinaryOperator * BreakUpSubtract(Instruction *Sub, ReassociatePass::OrderedSet &ToRedo)

If we have (X-Y), and if either X is an add, or if this is only used by an add, transform this into (...

Definition Reassociate.cpp:1000

static void FindSingleUseMultiplyFactors(Value *V, SmallVectorImpl< Value * > &Factors)

If V is a single-use multiply, recursively add its operands as factors, otherwise add V to the list o...

Definition Reassociate.cpp:1172

std::pair< Value *, uint64_t > RepeatedValue

Definition Reassociate.cpp:307

static Value * OptimizeAndOrXor(unsigned Opcode, SmallVectorImpl< ValueEntry > &Ops)

Optimize a series of operands to an 'and', 'or', or 'xor' instruction.

Definition Reassociate.cpp:1188

static BinaryOperator * convertOrWithNoCommonBitsToAdd(Instruction *Or)

If we have (X|Y), and iff X and Y have no common bits set, transform this into (X+Y) to allow arithme...

Definition Reassociate.cpp:953

static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, BasicBlock::iterator InsertBefore, Value *FlagsOp)

Definition Reassociate.cpp:250

static bool collectMultiplyFactors(SmallVectorImpl< ValueEntry > &Ops, SmallVectorImpl< Factor > &Factors)

Build up a vector of value/power pairs factoring a product.

Definition Reassociate.cpp:1727

static BinaryOperator * ConvertShiftToMul(Instruction *Shl)

If this is a shift of a reassociable multiply or is used by one, change this into a multiply by a con...

Definition Reassociate.cpp:1024

static cl::opt< bool > UseCSELocalOpt(DEBUG_TYPE "-use-cse-local", cl::desc("Only reorder expressions within a basic block " "when exposing CSE opportunities"), cl::init(true), cl::Hidden)

static unsigned FindInOperandList(const SmallVectorImpl< ValueEntry > &Ops, unsigned i, Value *X)

Scan backwards and forwards among values with the same rank as element i to see if X exists.

Definition Reassociate.cpp:1055

static BinaryOperator * LowerNegateToMultiply(Instruction *Neg)

Replace 0-X with X*-1.

Definition Reassociate.cpp:289

static Instruction * CreateNeg(Value *S1, const Twine &Name, BasicBlock::iterator InsertBefore, Value *FlagsOp)

Definition Reassociate.cpp:276

static bool hasFPAssociativeFlags(Instruction *I)

Return true if I is an instruction with the FastMathFlags that are needed for general reassociation s...

Definition Reassociate.cpp:156

static Value * createAndInstr(BasicBlock::iterator InsertBefore, Value *Opnd, const APInt &ConstOpnd)

Helper function of CombineXorOpnd().

Definition Reassociate.cpp:1238

static Value * NegateValue(Value *V, Instruction *BI, ReassociatePass::OrderedSet &ToRedo)

Insert instructions before the instruction pointed to by BI, that computes the negative version of th...

Definition Reassociate.cpp:767

static bool shouldConvertOrWithNoCommonBitsToAdd(Instruction *Or)

Return true if it may be profitable to convert this (X|Y) into (X+Y).

Definition Reassociate.cpp:929

static bool isLoadCombineCandidate(Instruction *Or)

Definition Reassociate.cpp:879

static Value * EmitAddTreeOfValues(Instruction *I, SmallVectorImpl< WeakTrackingVH > &Ops)

Emit a tree of add instructions, summing Ops together and returning the result.

Definition Reassociate.cpp:1081

This file defines the SmallPtrSet class.

This file defines the SmallSet class.

This file defines the SmallVector class.

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

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

static std::optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)

Returns the opcode of Values or ~0 if they do not all agree.

Class for arbitrary precision integers.

bool isAllOnes() const

Determine if all bits are set. This is true for zero-width values.

bool isZero() const

Determine if this value is zero, i.e. all bits are clear.

bool getBoolValue() const

Convert APInt to a boolean value.

static APInt getZero(unsigned numBits)

Get the '0' value for the specified bit-width.

AnalysisUsage & addPreserved()

Add the specified Pass class to the set of analyses preserved by this pass.

LLVM_ABI void setPreservesCFG()

This function should be called by the pass, iff they do not:

LLVM Basic Block Representation.

const Function * getParent() const

Return the enclosing method, or null if none.

LLVM_ABI InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const

Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...

InstListType::iterator iterator

Instruction iterators...

static LLVM_ABI BinaryOperator * CreateNeg(Value *Op, const Twine &Name="", InsertPosition InsertBefore=nullptr)

Helper functions to construct and inspect unary operations (NEG and NOT) via binary operators SUB and...

BinaryOps getOpcode() const

static LLVM_ABI BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), InsertPosition InsertBefore=nullptr)

Construct a binary instruction, given the opcode and the two operands.

Represents analyses that only rely on functions' control flow.

static LLVM_ABI Constant * getBinOpAbsorber(unsigned Opcode, Type *Ty, bool AllowLHSConstant=false)

Return the absorbing element for the given binary operation, i.e.

static LLVM_ABI Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false, bool NSZ=false)

Return the identity constant for a binary opcode.

static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)

This is an important base class in LLVM.

static LLVM_ABI Constant * getAllOnesValue(Type *Ty)

static LLVM_ABI Constant * getNullValue(Type *Ty)

Constructor to create a '0' constant of arbitrary type.

A parsed version of the target data layout string in and methods for querying it.

This provides a helper for copying FMF from an instruction or setting specified flags.

FunctionPass class - This class is used to implement most global optimizations.

const BasicBlock & getEntryBlock() const

Module * getParent()

Get the module that this global value is contained inside of...

Common base class shared among various IRBuilders.

Value * CreateFSubFMF(Value *L, Value *R, FMFSource FMFSource, const Twine &Name="", MDNode *FPMD=nullptr)

void setFastMathFlags(FastMathFlags NewFMF)

Set the fast-math flags to be used with generated fp-math operators.

Value * CreateFAddFMF(Value *L, Value *R, FMFSource FMFSource, const Twine &Name="", MDNode *FPMD=nullptr)

LLVM_ABI void setHasNoUnsignedWrap(bool b=true)

Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.

LLVM_ABI void setHasNoSignedWrap(bool b=true)

Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.

LLVM_ABI void dropLocation()

Drop the instruction's debug location.

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

LLVM_ABI void andIRFlags(const Value *V)

Logical 'and' of any supported wrapping, exact, and fast-math flags of V and this instruction.

LLVM_ABI void moveBefore(InstListType::iterator InsertPos)

Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...

LLVM_ABI void setFastMathFlags(FastMathFlags FMF)

Convenience function for setting multiple fast-math flags on this instruction, which must be an opera...

Instruction * user_back()

Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...

LLVM_ABI const Function * getFunction() const

Return the function this instruction belongs to.

const char * getOpcodeName() const

unsigned getOpcode() const

Returns a member of one of the enums like Instruction::Add.

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

LLVM_ABI const DataLayout & getDataLayout() const

Get the data layout of the module this instruction belongs to.

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

static LLVM_ABI PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

static LLVM_ABI PoisonValue * get(Type *T)

Static factory methods - Return an 'poison' object of the specified type.

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.

PreservedAnalyses & preserveSet()

Mark an analysis set as preserved.

Reassociate commutative expressions.

DenseMap< BasicBlock *, unsigned > RankMap

DenseMap< AssertingVH< Value >, unsigned > ValueRankMap

LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &)

Definition Reassociate.cpp:2546

SetVector< AssertingVH< Instruction >, std::deque< AssertingVH< Instruction > > > OrderedSet

DenseMap< std::pair< Value *, Value * >, PairMapValue > PairMap[NumBinaryOps]

bool empty() const

Determine if the SetVector is empty or not.

bool insert(const value_type &X)

Insert a new element into the SetVector.

value_type pop_back_val()

size_type count(ConstPtrType Ptr) const

count - Return 1 if the specified pointer is in the set, 0 otherwise.

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

std::pair< const_iterator, bool > insert(const T &V)

insert - Insert an element into the set if it isn't already there.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

reference emplace_back(ArgTypes &&... Args)

void reserve(size_type N)

iterator erase(const_iterator CI)

void append(ItTy in_start, ItTy in_end)

Add the specified range to the end of the SmallVector.

void push_back(const T &Elt)

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

Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...

The instances of the Type class are immutable: once they are created, they are never changed.

bool isIntOrIntVectorTy() const

Return true if this is an integer type or a vector of integer types.

LLVM_ABI unsigned getScalarSizeInBits() const LLVM_READONLY

If this is a vector type, return the getPrimitiveSizeInBits value for the element type.

static UnaryOperator * CreateFNegFMF(Value *Op, Instruction *FMFSource, const Twine &Name="", InsertPosition InsertBefore=nullptr)

void setOperand(unsigned i, Value *Val)

Value * getOperand(unsigned i) const

LLVM Value Representation.

Type * getType() const

All values are typed, get the type of this value.

user_iterator user_begin()

bool hasOneUse() const

Return true if there is exactly one use of this value.

LLVM_ABI void replaceAllUsesWith(Value *V)

Change all uses of this to point to a new Value.

iterator_range< user_iterator > users()

void clearSubclassOptionalData()

Clear the optional flags contained in this value.

LLVM_ABI void deleteValue()

Delete a pointer to a generic Value.

LLVM_ABI void takeName(Value *V)

Transfer the name from V to this value.

const ParentTy * getParent() const

self_iterator getIterator()

Utility class representing a non-constant Xor-operand.

Definition Reassociate.cpp:102

Value * getSymbolicPart() const

Definition Reassociate.cpp:109

bool isInvalid() const

Definition Reassociate.cpp:106

unsigned getSymbolicRank() const

Definition Reassociate.cpp:110

void setSymbolicRank(unsigned R)

Definition Reassociate.cpp:114

Value * getValue() const

Definition Reassociate.cpp:108

bool isOrExpr() const

Definition Reassociate.cpp:107

const APInt & getConstPart() const

Definition Reassociate.cpp:111

XorOpnd(Value *V)

Definition Reassociate.cpp:124

void Invalidate()

Definition Reassociate.cpp:113

unsigned ID

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

@ C

The default llvm calling convention, compatible with C.

@ BasicBlock

Various leaf nodes.

BinaryOp_match< SpecificConstantMatch, SrcTy, TargetOpcode::G_SUB > m_Neg(const SrcTy &&Src)

Matches a register negated by a G_SUB.

BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)

Matches a register not-ed by a G_XOR.

OneUse_match< SubPat > m_OneUse(const SubPat &SP)

class_match< BinaryOperator > m_BinOp()

Match an arbitrary binary operation and ignore it.

BinaryOp_match< LHS, RHS, Instruction::FSub > m_FSub(const LHS &L, const RHS &R)

class_match< Constant > m_Constant()

Match an arbitrary Constant and ignore it.

ap_match< APInt > m_APInt(const APInt *&Res)

Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.

bool match(Val *V, const Pattern &P)

bind_ty< Instruction > m_Instruction(Instruction *&I)

Match an instruction, capturing it if we match.

ap_match< APFloat > m_APFloat(const APFloat *&Res)

Match a ConstantFP or splatted ConstantVector, binding the specified pointer to the contained APFloat...

BinaryOp_match< LHS, RHS, Instruction::FAdd > m_FAdd(const LHS &L, const RHS &R)

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

FNeg_match< OpTy > m_FNeg(const OpTy &X)

Match 'fneg X' as 'fsub -0.0, X'.

initializer< Ty > init(const Ty &Val)

A private "module" namespace for types and utilities used by Reassociate.

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

LLVM_ABI bool haveNoCommonBitsSet(const WithCache< const Value * > &LHSCache, const WithCache< const Value * > &RHSCache, const SimplifyQuery &SQ)

Return true if LHS and RHS have no common bits set.

FunctionAddr VTableAddr Value

void stable_sort(R &&Range)

decltype(auto) dyn_cast(const From &Val)

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

LLVM_ABI void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)

Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...

APFloat abs(APFloat X)

Returns the absolute value of the argument.

auto unique(Range &&R, Predicate P)

bool any_of(R &&range, UnaryPredicate P)

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

LLVM_ABI bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)

Return true if the result produced by the instruction is not used, and the instruction will return.

LLVM_ABI Constant * ConstantFoldUnaryOpOperand(unsigned Opcode, Constant *Op, const DataLayout &DL)

Attempt to constant fold a unary operation with the specified operand.

decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)

LLVM_ABI raw_ostream & dbgs()

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

FunctionAddr VTableAddr Count

LLVM_ABI void initializeReassociateLegacyPassPass(PassRegistry &)

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

bool isa(const From &Val)

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

LLVM_ABI Constant * ConstantFoldBinaryOpOperands(unsigned Opcode, Constant *LHS, Constant *RHS, const DataLayout &DL)

Attempt to constant fold a binary operation with the specified operands.

LLVM_ABI bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)

Return true if the given value is known to be non-zero when defined.

IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >

LLVM_ABI FunctionPass * createReassociatePass()

LLVM_ABI bool replaceDbgUsesWithUndef(Instruction *I)

Replace all the uses of an SSA value in @llvm.dbg intrinsics with undef.

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

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

@ Mul

Product of integers.

@ Sub

Subtraction of integers.

DWARFExpression::Operation Op

constexpr unsigned BitWidth

decltype(auto) cast(const From &Val)

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

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

LLVM_ABI bool isKnownNonNegative(const Value *V, const SimplifyQuery &SQ, unsigned Depth=0)

Returns true if the give value is known to be non-negative.

LLVM_ABI bool mayHaveNonDefUseDependency(const Instruction &I)

Returns true if the result or effects of the given instructions I depend values not reachable through...

LLVM_ABI Constant * ConstantFoldBinaryInstruction(unsigned Opcode, Constant *V1, Constant *V2)

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

Utility class representing a base and exponent pair which form one factor of some product.