SeparateConstOffsetFromGEP.cpp Source File (original) (raw)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

167#include

168#include

169#include

170

171using namespace llvm;

173

175 "disable-separate-const-offset-from-gep", cl::init(false),

176 cl::desc("Do not separate the constant offset from a GEP instruction"),

178

179

180

181

184 cl::desc("Verify this pass produces no dead code"),

186

187namespace {

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202class ConstantOffsetExtractor {

203public:

204

205

206

207

208

209

210

211

212

214 User *&UserChainTail, bool &PreservesNUW);

215

216

217

218

220

221private:

223 : IP(InsertionPt), DL(InsertionPt->getDataLayout()) {}

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239 APInt find(Value *V, bool SignExtended, bool ZeroExtended, bool NonNegative);

240

241

242 APInt findInEitherOperand(BinaryOperator *BO, bool SignExtended,

243 bool ZeroExtended);

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260 Value *rebuildWithoutConstOffset();

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278 Value *distributeCastsAndCloneChain(unsigned ChainIndex);

279

280

281 Value *removeConstOffset(unsigned ChainIndex);

282

283

284

285

287

288

289

290

291

292

293

294

295 bool CanTraceInto(bool SignExtended, bool ZeroExtended, BinaryOperator *BO,

297

298

299

300 APInt extractDisjointBitsFromXor(BinaryOperator *XorInst);

301

302

303

304

305

306

307

309

310

311

313

314

316

317 const DataLayout &DL;

318};

319

320

321

322

323class SeparateConstOffsetFromGEPLegacyPass : public FunctionPass {

324public:

325 static char ID;

326

327 SeparateConstOffsetFromGEPLegacyPass(bool LowerGEP = false)

328 : FunctionPass(ID), LowerGEP(LowerGEP) {

331 }

332

333 void getAnalysisUsage(AnalysisUsage &AU) const override {

334 AU.addRequired();

335 AU.addRequired();

338 AU.addRequired();

339 }

340

342

343private:

344 bool LowerGEP;

345};

346

347

348

349

350class SeparateConstOffsetFromGEP {

351public:

352 SeparateConstOffsetFromGEP(

353 DominatorTree *DT, LoopInfo *LI, TargetLibraryInfo *TLI,

354 function_ref<TargetTransformInfo &(Function &)> GetTTI, bool LowerGEP)

355 : DT(DT), LI(LI), TLI(TLI), GetTTI(GetTTI), LowerGEP(LowerGEP) {}

356

357 bool run(Function &F);

358

359private:

360

361 using ExprKey = std::pair<Value *, Value *>;

362

363

364 static ExprKey createNormalizedCommutablePair(Value *A, Value *B) {

365 if (A < B)

366 return {A, B};

367 return {B, A};

368 }

369

370

371

372 bool splitGEP(GetElementPtrInst *GEP);

373

374

375

376

377 bool reorderGEP(GetElementPtrInst *GEP, TargetTransformInfo &TTI);

378

379

380

381

382

383

384

385

386 void lowerToSingleIndexGEPs(GetElementPtrInst *Variadic,

387 int64_t AccumulativeByteOffset);

388

389

390

391

392

393

394 int64_t accumulateByteOffset(GetElementPtrInst *GEP, bool &NeedsExtraction);

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411 bool canonicalizeArrayIndicesToIndexSize(GetElementPtrInst *GEP);

412

413

414

415

416

417

418

419

420

421

422 bool reuniteExts(Function &F);

423

424

425 bool reuniteExts(Instruction *I);

426

427

428 Instruction *findClosestMatchingDominator(

429 ExprKey Key, Instruction *Dominatee,

430 DenseMap<ExprKey, SmallVector<Instruction *, 2>> &DominatingExprs);

431

432

433 void verifyNoDeadCode(Function &F);

434

435 bool hasMoreThanOneUseInLoop(Value *v, Loop *L);

436

437

438 void swapGEPOperand(GetElementPtrInst *First, GetElementPtrInst *Second);

439

440

441 bool isLegalToSwapOperand(GetElementPtrInst *First, GetElementPtrInst *Second,

442 Loop *CurLoop);

443

444 const DataLayout *DL = nullptr;

445 DominatorTree *DT = nullptr;

446 LoopInfo *LI;

447 TargetLibraryInfo *TLI;

448

449 function_ref<TargetTransformInfo &(Function &)> GetTTI;

450

451

452

453 bool LowerGEP;

454

455 DenseMap<ExprKey, SmallVector<Instruction *, 2>> DominatingAdds;

456 DenseMap<ExprKey, SmallVector<Instruction *, 2>> DominatingSubs;

457};

458

459}

460

461char SeparateConstOffsetFromGEPLegacyPass::ID = 0;

462

464 SeparateConstOffsetFromGEPLegacyPass, "separate-const-offset-from-gep",

465 "Split GEPs to a variadic base and a constant offset for better CSE", false,

466 false)

473 SeparateConstOffsetFromGEPLegacyPass, "separate-const-offset-from-gep",

474 "Split GEPs to a variadic base and a constant offset for better CSE", false,

476

478 return new SeparateConstOffsetFromGEPLegacyPass(LowerGEP);

479}

480

481bool ConstantOffsetExtractor::CanTraceInto(bool SignExtended,

482 bool ZeroExtended,

485

486

487

488 if (BO->getOpcode() != Instruction::Add &&

489 BO->getOpcode() != Instruction::Sub &&

490 BO->getOpcode() != Instruction::Or) {

491 return false;

492 }

493

495

496

497 if (BO->getOpcode() == Instruction::Or &&

499 return false;

500

501

502

503

504 if (ZeroExtended && !SignExtended && BO->getOpcode() == Instruction::Sub)

505 return false;

506

507

508

509

510

511

512

513

514

515

516

517

519

520

521

522

523

524

525

526

528 if (!ConstLHS->isNegative())

529 return true;

530 }

532 if (!ConstRHS->isNegative())

533 return true;

534 }

535 }

536

537

538

539 if (BO->getOpcode() == Instruction::Add ||

540 BO->getOpcode() == Instruction::Sub) {

542 return false;

544 return false;

545 }

546

547 return true;

548}

549

550APInt ConstantOffsetExtractor::findInEitherOperand(BinaryOperator *BO,

551 bool SignExtended,

552 bool ZeroExtended) {

553

554 size_t ChainLength = UserChain.size();

555

556

557

558 APInt ConstantOffset = find(BO->getOperand(0), SignExtended, ZeroExtended,

559 false);

560

561

562

563

564

565 if (ConstantOffset != 0) return ConstantOffset;

566

567

568

569 UserChain.resize(ChainLength);

570

571 ConstantOffset = find(BO->getOperand(1), SignExtended, ZeroExtended,

572 false);

573

574

575 if (BO->getOpcode() == Instruction::Sub)

576 ConstantOffset = -ConstantOffset;

577

578

579 if (ConstantOffset == 0)

580 UserChain.resize(ChainLength);

581

582 return ConstantOffset;

583}

584

585APInt ConstantOffsetExtractor::find(Value *V, bool SignExtended,

587

588

589

591

592

594 if (U == nullptr) return APInt(BitWidth, 0);

595

596 APInt ConstantOffset(BitWidth, 0);

598

599 ConstantOffset = CI->getValue();

601

602 if (CanTraceInto(SignExtended, ZeroExtended, BO, NonNegative))

603 ConstantOffset = findInEitherOperand(BO, SignExtended, ZeroExtended);

604

605 else if (BO->getOpcode() == Instruction::Xor)

606 ConstantOffset = extractDisjointBitsFromXor(BO);

608 ConstantOffset =

609 find(U->getOperand(0), SignExtended, ZeroExtended, NonNegative)

612 ConstantOffset = find(U->getOperand(0), true,

615

616

617

618

619 ConstantOffset =

620 find(U->getOperand(0), false,

621 true, false).zext(BitWidth);

622 }

623

624

625

626

627 if (ConstantOffset != 0)

628 UserChain.push_back(U);

629 return ConstantOffset;

630}

631

632Value *ConstantOffsetExtractor::applyCasts(Value *V) {

634

635

638

640 if (Current)

641 continue;

642 }

643

646

647

648

649

650

654 Current = Cast;

655 }

656 return Current;

657}

658

659Value *ConstantOffsetExtractor::rebuildWithoutConstOffset() {

660 distributeCastsAndCloneChain(UserChain.size() - 1);

661

662 unsigned NewSize = 0;

663 for (User *I : UserChain) {

664 if (I != nullptr) {

665 UserChain[NewSize] = I;

666 NewSize++;

667 }

668 }

669 UserChain.resize(NewSize);

670 return removeConstOffset(UserChain.size() - 1);

671}

672

674ConstantOffsetExtractor::distributeCastsAndCloneChain(unsigned ChainIndex) {

675 User *U = UserChain[ChainIndex];

676 if (ChainIndex == 0) {

678

680 }

681

685 "Only following instructions can be traced: sext, zext & trunc");

686 CastInsts.push_back(Cast);

687 UserChain[ChainIndex] = nullptr;

688 return distributeCastsAndCloneChain(ChainIndex - 1);

689 }

690

691

693

694 unsigned OpNo = (BO->getOperand(0) == UserChain[ChainIndex - 1] ? 0 : 1);

696 Value *NextInChain = distributeCastsAndCloneChain(ChainIndex - 1);

697

698 BinaryOperator *NewBO = nullptr;

699 if (OpNo == 0) {

702 } else {

705 }

706 return UserChain[ChainIndex] = NewBO;

707}

708

709Value *ConstantOffsetExtractor::removeConstOffset(unsigned ChainIndex) {

710 if (ChainIndex == 0) {

712 return ConstantInt::getNullValue(UserChain[ChainIndex]->getType());

713 }

714

717 "distributeCastsAndCloneChain clones each BinaryOperator in "

718 "UserChain, so no one should be used more than "

719 "once");

720

721 unsigned OpNo = (BO->getOperand(0) == UserChain[ChainIndex - 1] ? 0 : 1);

723 Value *NextInChain = removeConstOffset(ChainIndex - 1);

725

727 if (CI->isZero()) {

728

729

730

731

732 if (BO->getOpcode() == Instruction::Xor)

733 return BO;

734

735

736

737 if (!(BO->getOpcode() == Instruction::Sub && OpNo == 0))

738 return TheOther;

739 }

740 }

741

742 BinaryOperator::BinaryOps NewOp = BO->getOpcode();

743 if (BO->getOpcode() == Instruction::Or) {

744

745

746

747

748

749

750

751

752

753

754

755

756

757 NewOp = Instruction::Add;

758 }

759

760 BinaryOperator *NewBO;

761 if (OpNo == 0) {

763 } else {

765 }

767 return NewBO;

768}

769

770

771

772

773

774

775

776

777

778

779

780

781

782

783

784

785

786

787

788

789APInt ConstantOffsetExtractor::extractDisjointBitsFromXor(

790 BinaryOperator *XorInst) {

791 assert(XorInst && XorInst->getOpcode() == Instruction::Xor &&

792 "Expected XOR instruction");

793

795 Value *BaseOperand;

796 ConstantInt *XorConstant;

797

798

801

802

803 const SimplifyQuery SQ(DL);

804 const KnownBits BaseKnownBits = computeKnownBits(BaseOperand, SQ);

805 const APInt &ConstantValue = XorConstant->getValue();

806

807

808 const APInt DisjointBits = ConstantValue & BaseKnownBits.Zero;

809

810

811 if (DisjointBits.isZero())

813

814

815 const APInt NonDisjointBits = ConstantValue & ~DisjointBits;

816

817

818

819

820

821

822

823

824

825

826

827 UserChain.push_back(ConstantInt::get(XorInst->getType(), NonDisjointBits));

828 return DisjointBits;

829}

830

831

832

835

837 if (Opcode == BinaryOperator::Or) {

838

839

841 return true;

842 }

844 }

845

846

847

848

850 return TI->hasNoUnsignedWrap();

852 return true;

853}

854

855Value *ConstantOffsetExtractor::Extract(Value *Idx, GetElementPtrInst *GEP,

856 User *&UserChainTail,

857 bool &PreservesNUW) {

858 ConstantOffsetExtractor Extractor(GEP->getIterator());

859

860 APInt ConstantOffset =

861 Extractor.find(Idx, false, false,

862 GEP->isInBounds());

863 if (ConstantOffset == 0) {

864 UserChainTail = nullptr;

865 PreservesNUW = true;

866 return nullptr;

867 }

868

870

871

872 Value *IdxWithoutConstOffset = Extractor.rebuildWithoutConstOffset();

873 UserChainTail = Extractor.UserChain.back();

874 return IdxWithoutConstOffset;

875}

876

877int64_t ConstantOffsetExtractor::Find(Value *Idx, GetElementPtrInst *GEP) {

878

879 return ConstantOffsetExtractor(GEP->getIterator())

880 .find(Idx, false, false,

881 GEP->isInBounds())

882 .getSExtValue();

883}

884

885bool SeparateConstOffsetFromGEP::canonicalizeArrayIndicesToIndexSize(

886 GetElementPtrInst *GEP) {

888 Type *PtrIdxTy = DL->getIndexType(GEP->getType());

891 I != E; ++I, ++GTI) {

892

894 if ((*I)->getType() != PtrIdxTy) {

896 GEP->getIterator());

898 }

899 }

900 }

902}

903

904int64_t

905SeparateConstOffsetFromGEP::accumulateByteOffset(GetElementPtrInst *GEP,

906 bool &NeedsExtraction) {

907 NeedsExtraction = false;

908 int64_t AccumulativeByteOffset = 0;

910 for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {

912

914 continue;

915

916

917 int64_t ConstantOffset =

918 ConstantOffsetExtractor::Find(GEP->getOperand(I), GEP);

919 if (ConstantOffset != 0) {

920 NeedsExtraction = true;

921

922

923

924 AccumulativeByteOffset +=

926 }

927 } else if (LowerGEP) {

930

931 if (Field != 0) {

932 NeedsExtraction = true;

933 AccumulativeByteOffset +=

934 DL->getStructLayout(StTy)->getElementOffset(Field);

935 }

936 }

937 }

938 return AccumulativeByteOffset;

939}

940

941void SeparateConstOffsetFromGEP::lowerToSingleIndexGEPs(

942 GetElementPtrInst *Variadic, int64_t AccumulativeByteOffset) {

944 Type *PtrIndexTy = DL->getIndexType(Variadic->getType());

945

948

949 bool isSwapCandidate =

950 L && L->isLoopInvariant(ResultPtr) &&

951 !hasMoreThanOneUseInLoop(ResultPtr, L);

952 Value *FirstResult = nullptr;

953

955

956

957 for (unsigned I = 1, E = Variadic->getNumOperands(); I != E; ++I, ++GTI) {

960

962 if (CI->isZero())

963 continue;

964

967

968 if (ElementSize != 1) {

970 Idx = Builder.CreateShl(

971 Idx, ConstantInt::get(PtrIndexTy, ElementSize.logBase2()));

972 } else {

973 Idx =

974 Builder.CreateMul(Idx, ConstantInt::get(PtrIndexTy, ElementSize));

975 }

976 }

977

978 ResultPtr = Builder.CreatePtrAdd(ResultPtr, Idx, "uglygep");

979 if (FirstResult == nullptr)

980 FirstResult = ResultPtr;

981 }

982 }

983

984

985 if (AccumulativeByteOffset != 0) {

986 Value *Offset = ConstantInt::get(PtrIndexTy, AccumulativeByteOffset);

987 ResultPtr = Builder.CreatePtrAdd(ResultPtr, Offset, "uglygep");

988 } else

989 isSwapCandidate = false;

990

991

992

993

996 if (isSwapCandidate && isLegalToSwapOperand(FirstGEP, SecondGEP, L))

997 swapGEPOperand(FirstGEP, SecondGEP);

998

999 Variadic->replaceAllUsesWith(ResultPtr);

1000 Variadic->eraseFromParent();

1001}

1002

1003bool SeparateConstOffsetFromGEP::reorderGEP(GetElementPtrInst *GEP,

1004 TargetTransformInfo &TTI) {

1006 if (!PtrGEP)

1007 return false;

1008

1009 bool NestedNeedsExtraction;

1010 int64_t NestedByteOffset =

1011 accumulateByteOffset(PtrGEP, NestedNeedsExtraction);

1012 if (!NestedNeedsExtraction)

1013 return false;

1014

1015 unsigned AddrSpace = PtrGEP->getPointerAddressSpace();

1017 nullptr, NestedByteOffset,

1018 true, 0, AddrSpace))

1019 return false;

1020

1021 bool GEPInBounds = GEP->isInBounds();

1022 bool PtrGEPInBounds = PtrGEP->isInBounds();

1023 bool IsChainInBounds = GEPInBounds && PtrGEPInBounds;

1024 if (IsChainInBounds) {

1025 auto IsKnownNonNegative = [this](Value *V) {

1027 };

1028 IsChainInBounds &= all_of(GEP->indices(), IsKnownNonNegative);

1029 if (IsChainInBounds)

1030 IsChainInBounds &= all_of(PtrGEP->indices(), IsKnownNonNegative);

1031 }

1032

1034

1035 Value *NewSrc = Builder.CreateGEP(

1036 GEP->getSourceElementType(), PtrGEP->getPointerOperand(),

1038 Value *NewGEP = Builder.CreateGEP(PtrGEP->getSourceElementType(), NewSrc,

1040 "", IsChainInBounds);

1041 GEP->replaceAllUsesWith(NewGEP);

1043 return true;

1044}

1045

1046bool SeparateConstOffsetFromGEP::splitGEP(GetElementPtrInst *GEP) {

1047

1048 if (GEP->getType()->isVectorTy())

1049 return false;

1050

1051

1052

1053

1055 const APInt *BaseOffset;

1056 const bool ExtractBase =

1057 match(GEP->getPointerOperand(),

1059

1060 const int64_t BaseByteOffset = ExtractBase ? BaseOffset->getSExtValue() : 0;

1061

1062

1063

1064 if (GEP->hasAllConstantIndices() && !ExtractBase)

1065 return false;

1066

1067 bool Changed = canonicalizeArrayIndicesToIndexSize(GEP);

1068

1069 bool NeedsExtraction;

1070 int64_t AccumulativeByteOffset =

1071 BaseByteOffset + accumulateByteOffset(GEP, NeedsExtraction);

1072

1073 TargetTransformInfo &TTI = GetTTI(*GEP->getFunction());

1074

1075 if (!NeedsExtraction && !ExtractBase) {

1078 }

1079

1080

1081

1082

1083

1084

1085

1086

1087 if (!LowerGEP) {

1088 unsigned AddrSpace = GEP->getPointerAddressSpace();

1090 nullptr, AccumulativeByteOffset,

1091 true, 0,

1092 AddrSpace)) {

1094 }

1095 }

1096

1097

1098 bool AllOffsetsNonNegative = AccumulativeByteOffset >= 0;

1099 bool AllNUWPreserved = GEP->hasNoUnsignedWrap();

1100 bool NewGEPInBounds = GEP->isInBounds();

1101 bool NewGEPNUSW = GEP->hasNoUnsignedSignedWrap();

1102

1103

1104

1105

1106

1107

1108

1109

1111 for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {

1113

1115 continue;

1116

1117

1118

1119 Value *Idx = GEP->getOperand(I);

1120 User *UserChainTail;

1121 bool PreservesNUW;

1122 Value *NewIdx = ConstantOffsetExtractor::Extract(Idx, GEP, UserChainTail,

1123 PreservesNUW);

1124 if (NewIdx != nullptr) {

1125

1126 GEP->setOperand(I, NewIdx);

1127

1128

1131 Idx = NewIdx;

1132 AllNUWPreserved &= PreservesNUW;

1133 }

1134 AllOffsetsNonNegative =

1136 }

1137 }

1138 if (ExtractBase) {

1140 AllNUWPreserved &= Base->hasNoUnsignedWrap();

1141 NewGEPInBounds &= Base->isInBounds();

1142 NewGEPNUSW &= Base->hasNoUnsignedSignedWrap();

1143 AllOffsetsNonNegative &= BaseByteOffset >= 0;

1144

1145 GEP->setOperand(0, NewBase);

1147 }

1148

1149

1150

1151

1152

1153

1154

1155

1156

1157

1158

1159

1160

1161

1162

1163

1164

1166

1167

1168

1169

1170

1171 bool CanPreserveInBoundsNUSW = AllOffsetsNonNegative;

1172

1173

1174

1175 if (AllNUWPreserved) {

1177

1178

1179

1180

1181

1182

1183 CanPreserveInBoundsNUSW |= NewGEPNUSW;

1184 }

1185

1186 if (CanPreserveInBoundsNUSW) {

1187 if (NewGEPInBounds)

1189 else if (NewGEPNUSW)

1191 }

1192

1193 GEP->setNoWrapFlags(NewGEPFlags);

1194

1195

1196 if (LowerGEP) {

1197 lowerToSingleIndexGEPs(GEP, AccumulativeByteOffset);

1198 return true;

1199 }

1200

1201

1202 if (AccumulativeByteOffset == 0)

1203 return true;

1204

1205

1206

1207

1208

1209

1210

1211

1212

1213

1214

1215

1216

1217

1218

1219

1220

1221

1224

1225 Type *PtrIdxTy = DL->getIndexType(GEP->getType());

1228 NewGEP, ConstantInt::get(PtrIdxTy, AccumulativeByteOffset, true),

1229 GEP->getName(), NewGEPFlags));

1231

1232 GEP->replaceAllUsesWith(NewGEP);

1233 GEP->eraseFromParent();

1234

1235 return true;

1236}

1237

1238bool SeparateConstOffsetFromGEPLegacyPass::runOnFunction(Function &F) {

1239 if (skipFunction(F))

1240 return false;

1241 auto *DT = &getAnalysis().getDomTree();

1242 auto *LI = &getAnalysis().getLoopInfo();

1243 auto *TLI = &getAnalysis().getTLI(F);

1244 auto GetTTI = [this](Function &F) -> TargetTransformInfo & {

1245 return this->getAnalysis().getTTI(F);

1246 };

1247 SeparateConstOffsetFromGEP Impl(DT, LI, TLI, GetTTI, LowerGEP);

1248 return Impl.run(F);

1249}

1250

1251bool SeparateConstOffsetFromGEP::run(Function &F) {

1253 return false;

1254

1255 DL = &F.getDataLayout();

1257

1258 ReversePostOrderTraversal<Function *> RPOT(&F);

1259 for (BasicBlock *B : RPOT) {

1261 continue;

1262

1266

1267

1268 }

1269

1271

1273 verifyNoDeadCode(F);

1274

1276}

1277

1278Instruction *SeparateConstOffsetFromGEP::findClosestMatchingDominator(

1279 ExprKey Key, Instruction *Dominatee,

1280 DenseMap<ExprKey, SmallVector<Instruction *, 2>> &DominatingExprs) {

1281 auto Pos = DominatingExprs.find(Key);

1282 if (Pos == DominatingExprs.end())

1283 return nullptr;

1284

1285 auto &Candidates = Pos->second;

1286

1287

1288

1289

1290 while (!Candidates.empty()) {

1291 Instruction *Candidate = Candidates.back();

1292 if (DT->dominates(Candidate, Dominatee))

1293 return Candidate;

1294 Candidates.pop_back();

1295 }

1296 return nullptr;

1297}

1298

1299bool SeparateConstOffsetFromGEP::reuniteExts(Instruction *I) {

1300 if (->getType()->isIntOrIntVectorTy())

1301 return false;

1302

1303

1304

1305

1306

1310 ExprKey Key = createNormalizedCommutablePair(LHS, RHS);

1311 if (auto *Dom = findClosestMatchingDominator(Key, I, DominatingAdds)) {

1313 new SExtInst(Dom, I->getType(), "", I->getIterator());

1315 I->replaceAllUsesWith(NewSExt);

1318 return true;

1319 }

1320 }

1323 if (auto *Dom =

1324 findClosestMatchingDominator({LHS, RHS}, I, DominatingSubs)) {

1326 new SExtInst(Dom, I->getType(), "", I->getIterator());

1328 I->replaceAllUsesWith(NewSExt);

1331 return true;

1332 }

1333 }

1334 }

1335

1336

1339 ExprKey Key = createNormalizedCommutablePair(LHS, RHS);

1340 DominatingAdds[Key].push_back(I);

1341 }

1344 DominatingSubs[{LHS, RHS}].push_back(I);

1345 }

1346 return false;

1347}

1348

1349bool SeparateConstOffsetFromGEP::reuniteExts(Function &F) {

1351 DominatingAdds.clear();

1352 DominatingSubs.clear();

1353 for (const auto Node : depth_first(DT)) {

1357 }

1359}

1360

1361void SeparateConstOffsetFromGEP::verifyNoDeadCode(Function &F) {

1362 for (BasicBlock &B : F) {

1363 for (Instruction &I : B) {

1365 std::string ErrMessage;

1366 raw_string_ostream RSO(ErrMessage);

1367 RSO << "Dead instruction detected!\n" << I << "\n";

1369 }

1370 }

1371 }

1372}

1373

1374bool SeparateConstOffsetFromGEP::isLegalToSwapOperand(

1375 GetElementPtrInst *FirstGEP, GetElementPtrInst *SecondGEP, Loop *CurLoop) {

1376 if (!FirstGEP || !FirstGEP->hasOneUse())

1377 return false;

1378

1380 return false;

1381

1382 if (FirstGEP == SecondGEP)

1383 return false;

1384

1387

1388 if (FirstNum != SecondNum || FirstNum != 2)

1389 return false;

1390

1394

1396 return false;

1397

1398

1400 return false;

1401

1403

1404

1405

1406

1407

1408

1409

1410

1411

1412

1413 if (FirstOffsetDef && FirstOffsetDef->isShift() &&

1416

1417

1418

1419 if (FirstOffsetDef)

1422 if ((opc == Instruction::Add || opc == Instruction::Sub) &&

1425 return false;

1426 }

1427 return true;

1428}

1429

1430bool SeparateConstOffsetFromGEP::hasMoreThanOneUseInLoop(Value *V, Loop *L) {

1431

1432

1434 return false;

1435

1436 int UsesInLoop = 0;

1437 for (User *U : V->users()) {

1439 if (L->contains(User))

1440 if (++UsesInLoop > 1)

1441 return true;

1442 }

1443 return false;

1444}

1445

1446void SeparateConstOffsetFromGEP::swapGEPOperand(GetElementPtrInst *First,

1447 GetElementPtrInst *Second) {

1448 Value *Offset1 = First->getOperand(1);

1450 First->setOperand(1, Offset2);

1452

1453

1454 const DataLayout &DAL = First->getDataLayout();

1457 0);

1458 Value *NewBase =

1460 uint64_t ObjectSize;

1461 if ( getObjectSize (NewBase, ObjectSize, DAL, TLI) ||

1462 Offset.ugt(ObjectSize)) {

1463

1466 } else

1467 First->setIsInBounds(true);

1468}

1469

1474 OS << '<';

1475 if (LowerGEP)

1476 OS << "lower-gep";

1477 OS << '>';

1478}

1479

1487 };

1488 SeparateConstOffsetFromGEP Impl(DT, LI, TLI, GetTTI, LowerGEP);

1489 if (!Impl.run(F))

1493 return PA;

1494}

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

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

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

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

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

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

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

This file defines the DenseMap class.

This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.

static bool runOnFunction(Function &F, bool PostInlining)

Module.h This file contains the declarations for the Module class.

This header defines various interfaces for pass management in LLVM.

static const T * Find(StringRef S, ArrayRef< T > A)

Find KV in array using binary search.

OptimizedStructLayoutField Field

#define INITIALIZE_PASS_DEPENDENCY(depName)

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

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

static cl::opt< bool > DisableSeparateConstOffsetFromGEP("disable-separate-const-offset-from-gep", cl::init(false), cl::desc("Do not separate the constant offset from a GEP instruction"), cl::Hidden)

static bool allowsPreservingNUW(const User *U)

A helper function to check if reassociating through an entry in the user chain would invalidate the G...

Definition SeparateConstOffsetFromGEP.cpp:833

static cl::opt< bool > VerifyNoDeadCode("reassociate-geps-verify-no-dead-code", cl::init(false), cl::desc("Verify this pass produces no dead code"), cl::Hidden)

This file defines the SmallVector class.

static SymbolRef::Type getType(const Symbol *Sym)

This pass exposes codegen information to IR-level passes.

LLVM_ABI APInt zext(unsigned width) const

Zero extend to a new width.

LLVM_ABI APInt trunc(unsigned width) const

Truncate to new width.

bool isZero() const

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

unsigned logBase2() const

LLVM_ABI APInt sext(unsigned width) const

Sign extend to a new width.

bool isPowerOf2() const

Check if this APInt's value is a power of two greater than zero.

static APInt getZero(unsigned numBits)

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

int64_t getSExtValue() const

Get sign extended value.

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

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

AnalysisUsage & addRequired()

LLVM_ABI void setPreservesCFG()

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

InstListType::iterator iterator

Instruction iterators...

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 CastInst * CreateIntegerCast(Value *S, Type *Ty, bool isSigned, const Twine &Name="", InsertPosition InsertBefore=nullptr)

Create a ZExt, BitCast, or Trunc for int -> int casts.

const APInt & getValue() const

Return the constant as an APInt value reference.

unsigned getIndexSizeInBits(unsigned AS) const

The size in bits of indices used for address calculation in getelementptr and for addresses in the gi...

Analysis pass which computes a DominatorTree.

Legacy analysis pass which computes a DominatorTree.

LLVM_ABI bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const

Return true if the (end of the) basic block BB dominates the use U.

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

static GEPNoWrapFlags inBounds()

static GEPNoWrapFlags noUnsignedWrap()

static GEPNoWrapFlags noUnsignedSignedWrap()

static GEPNoWrapFlags none()

an instruction for type-safe pointer arithmetic to access elements of arrays and structs

LLVM_ABI void setNoWrapFlags(GEPNoWrapFlags NW)

Set nowrap flags for GEP instruction.

LLVM_ABI bool hasNoUnsignedWrap() const LLVM_READONLY

Determine whether the no unsigned wrap flag is set.

LLVM_ABI bool hasNoSignedWrap() const LLVM_READONLY

Determine whether the no signed wrap flag is set.

LLVM_ABI void insertBefore(InstListType::iterator InsertPos)

Insert an unlinked instruction into a basic block immediately before the specified position.

LLVM_ABI void dropPoisonGeneratingFlags()

Drops flags that may cause this instruction to evaluate to poison despite having non-poison inputs.

void setDebugLoc(DebugLoc Loc)

Set the debug location information for this instruction.

LLVM_ABI void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())

Copy metadata from SrcInst to this instruction.

Analysis pass that exposes the LoopInfo for a function.

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

The legacy pass manager's analysis pass to compute loop information.

bool isLoopInvariant(const Value *V) const

Return true if the specified value is loop invariant.

static LLVM_ABI PassRegistry * getPassRegistry()

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

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.

void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)

Definition SeparateConstOffsetFromGEP.cpp:1470

PreservedAnalyses run(Function &F, FunctionAnalysisManager &)

Definition SeparateConstOffsetFromGEP.cpp:1481

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

Analysis pass providing the TargetTransformInfo.

Analysis pass providing the TargetLibraryInfo.

Wrapper pass for TargetTransformInfo.

This pass provides access to the codegen interfaces that are needed for IR-level transformations.

LLVM_ABI bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset, bool HasBaseReg, int64_t Scale, unsigned AddrSpace=0, Instruction *I=nullptr, int64_t ScalableOffset=0) const

Return true if the addressing mode represented by AM is legal for this target, for a load/store of th...

This class represents a truncation of integer types.

LLVM_ABI unsigned getIntegerBitWidth() const

LLVM_ABI bool isScalableTy(SmallPtrSetImpl< const Type * > &Visited) const

Return true if this is a type whose size is a known multiple of vscale.

LLVM_ABI unsigned getScalarSizeInBits() const LLVM_READONLY

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

void setOperand(unsigned i, Value *Val)

Value * getOperand(unsigned i) const

unsigned getNumOperands() const

LLVM Value Representation.

Type * getType() const

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

const Value * stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL, APInt &Offset) const

This is a wrapper around stripAndAccumulateConstantOffsets with the in-bounds requirement set to fals...

bool hasOneUse() const

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

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

LLVM_ABI void takeName(Value *V)

Transfer the name from V to this value.

An efficient, type-erasing, non-owning reference to a callable.

bool isSequential() const

StructType * getStructType() const

TypeSize getSequentialElementStride(const DataLayout &DL) const

Type * getIndexedType() const

const ParentTy * getParent() const

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

#define llvm_unreachable(msg)

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

@ C

The default llvm calling convention, compatible with C.

@ BasicBlock

Various leaf nodes.

PtrAdd_match< PointerOpTy, OffsetOpTy > m_PtrAdd(const PointerOpTy &PointerOp, const OffsetOpTy &OffsetOp)

Matches GEP with i8 source element type.

BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)

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

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

BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)

OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap > m_NSWSub(const LHS &L, const RHS &R)

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

class_match< ConstantInt > m_ConstantInt()

Match an arbitrary ConstantInt and ignore it.

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoSignedWrap > m_NSWAdd(const LHS &L, const RHS &R)

CastInst_match< OpTy, SExtInst > m_SExt(const OpTy &Op)

Matches SExt.

BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)

initializer< Ty > init(const Ty &Val)

PointerTypeMap run(const Module &M)

Compute the PointerTypeMap for the module M.

@ User

could "use" a pointer

NodeAddr< NodeBase * > Node

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

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

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

bool all_of(R &&range, UnaryPredicate P)

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

LLVM_ABI bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())

If the specified value is a trivially dead instruction, delete it.

decltype(auto) dyn_cast(const From &Val)

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

iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)

Make a range that does early increment to allow mutation of the underlying range without disrupting i...

LLVM_ABI void initializeSeparateConstOffsetFromGEPLegacyPassPass(PassRegistry &)

auto dyn_cast_or_null(const Y &Val)

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 bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL, const TargetLibraryInfo *TLI, ObjectSizeOpts Opts={})

Compute the size of the object pointed by Ptr.

auto reverse(ContainerTy &&C)

LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)

Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...

LLVM_ABI bool programUndefinedIfPoison(const Instruction *Inst)

generic_gep_type_iterator<> gep_type_iterator

LLVM_ABI Constant * ConstantFoldCastOperand(unsigned Opcode, Constant *C, Type *DestTy, const DataLayout &DL)

Attempt to constant fold a cast with the specified operand.

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_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key

LLVM_ABI FunctionPass * createSeparateConstOffsetFromGEPPass(bool LowerGEP=false)

Definition SeparateConstOffsetFromGEP.cpp:477

@ First

Helpers to iterate all locations in the MemoryEffectsBase class.

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

constexpr unsigned BitWidth

decltype(auto) cast(const From &Val)

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

gep_type_iterator gep_type_begin(const User *GEP)

iterator_range< df_iterator< T > > depth_first(const T &G)

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.

A CRTP mix-in to automatically provide informational APIs needed for passes.