InstCombineNegator.cpp Source File (original) (raw)

43#include

44#include

45#include

46#include

48using namespace llvm;

51#define DEBUG_TYPE "instcombine"

54 "Negator: Number of negations attempted to be sinked");

56 "Negator: Number of negations successfully sinked");

57 STATISTIC(NegatorMaxDepthVisited, "Negator: Maximal traversal depth ever "

58 "reached while attempting to sink negation");

60 "Negator: How many times did the traversal depth limit was reached "

61 "during sinking");

63 NegatorNumValuesVisited,

64 "Negator: Total number of values visited during attempts to sink negation");

66 "Negator: How many negations did we retrieve/reuse from cache");

68 "Negator: Maximal number of values ever visited while attempting to "

69 "sink negation");

70 STATISTIC(NegatorNumInstructionsCreatedTotal,

71 "Negator: Number of new negated instructions created, total");

73 "Negator: Maximal number of new instructions created during negation "

74 "attempt");

75 STATISTIC(NegatorNumInstructionsNegatedSuccess,

76 "Negator: Number of new negated instructions created in successful "

77 "negation sinking attempts");

80 "Controls Negator transformations in InstCombine pass");

84 cl::desc("Should we attempt to sink negations?"));

89 cl::desc("What is the maximal lookup depth when trying to "

90 "check for viability of negation sinking."));

93 bool IsTrulyNegation_)

96 ++NegatorNumInstructionsCreatedTotal;

97 NewInstructions.push_back(I);

98 })),

99 DT(DT_), IsTrulyNegation(IsTrulyNegation_) {}

100

101#if LLVM_ENABLE_STATS

102Negator::~Negator() {

103 NegatorMaxTotalValuesVisited.updateMax(NumValuesVisitedInThisNegator);

104}

105#endif

106

107

108

109

110

111std::array<Value *, 2> Negator::getSortedOperandsOfBinOp(Instruction *I) {

112 assert(I->getNumOperands() == 2 && "Only for binops!");

113 std::array<Value *, 2> Ops{I->getOperand(0), I->getOperand(1)};

117 return Ops;

118}

119

120

121

122[[nodiscard]] Value *Negator::visitImpl(Value *V, bool IsNSW, unsigned Depth) {

123

125 return V;

126

127

128 if (V->getType()->isIntOrIntVectorTy(1))

129 return V;

130

132

133

135 return X;

136

137

140 false);

141

142

144 return nullptr;

145

146

147

148

149 if (->hasOneUse() && !IsTrulyNegation)

150 return nullptr;

151

153 unsigned BitWidth = I->getType()->getScalarSizeInBits();

154

155

156

157 InstCombiner::BuilderTy::InsertPointGuard Guard(Builder);

158

159

160 Builder.SetInsertPoint(I);

161

162

163 switch (I->getOpcode()) {

164 case Instruction::Add: {

165 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);

166

168 return Builder.CreateNot(Ops[0], I->getName() + ".neg");

169 break;

170 }

171 case Instruction::Xor:

172

174 return Builder.CreateAdd(X, ConstantInt::get(X->getType(), 1),

175 I->getName() + ".neg");

176 break;

177 case Instruction::AShr:

178 case Instruction::LShr: {

179

180 const APInt *Op1Val;

182 Value *BO = I->getOpcode() == Instruction::AShr

183 ? Builder.CreateLShr(I->getOperand(0), I->getOperand(1))

184 : Builder.CreateAShr(I->getOperand(0), I->getOperand(1));

186 NewInstr->copyIRFlags(I);

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

188 }

189 return BO;

190 }

191

192

193

194

195 break;

196 }

197 case Instruction::SExt:

198 case Instruction::ZExt:

199

200 if (I->getOperand(0)->getType()->isIntOrIntVectorTy(1))

201 return I->getOpcode() == Instruction::SExt

202 ? Builder.CreateZExt(I->getOperand(0), I->getType(),

203 I->getName() + ".neg")

204 : Builder.CreateSExt(I->getOperand(0), I->getType(),

205 I->getName() + ".neg");

206 break;

207 case Instruction::Select: {

208

209

216 return Builder.CreateSelect(Sel->getCondition(), NegTrueC, NegFalseC,

217 I->getName() + ".neg", I);

218 }

219 break;

220 }

221 case Instruction::Call:

223 return Builder.CreateIntrinsic(CI->getType(), CI->getIntrinsicID(),

224 {CI->getRHS(), CI->getLHS()});

225 break;

226 default:

227 break;

228 }

229

230 if (I->getOpcode() == Instruction::Sub &&

232

233

234

235 return Builder.CreateSub(I->getOperand(1), I->getOperand(0),

236 I->getName() + ".neg", false,

237 IsNSW && I->hasNoSignedWrap());

238 }

239

240

241

242 if (->hasOneUse())

243 return nullptr;

244

245 switch (I->getOpcode()) {

246 case Instruction::ZExt: {

247

248

249 Value *SrcOp = I->getOperand(0);

251 const APInt &FullShift = APInt(SrcWidth, SrcWidth - 1);

252 if (IsTrulyNegation &&

254 Value *Ashr = Builder.CreateAShr(X, FullShift);

255 return Builder.CreateSExt(Ashr, I->getType());

256 }

257 break;

258 }

259 case Instruction::And: {

261

265 unsigned BW = X->getType()->getScalarSizeInBits();

266 Constant *BWMinusOne = ConstantInt::get(X->getType(), BW - 1);

267 Value *R = Builder.CreateShl(X, Builder.CreateSub(BWMinusOne, ShAmt));

268 R = Builder.CreateAShr(R, BWMinusOne);

269 return Builder.CreateTruncOrBitCast(R, I->getType());

270 }

271 break;

272 }

273 case Instruction::SDiv:

274

275

276

278 if (!Op1C->containsUndefOrPoisonElement() &&

279 Op1C->isNotMinSignedValue() && Op1C->isNotOneValue()) {

284 NewInstr->setIsExact(I->isExact());

285 return BO;

286 }

287 }

288 break;

289 }

290

291

293 LLVM_DEBUG(dbgs() << "Negator: reached maximal allowed traversal depth in "

294 << *V << ". Giving up.\n");

295 ++NegatorTimesDepthLimitReached;

296 return nullptr;

297 }

298

299 switch (I->getOpcode()) {

300 case Instruction::Freeze: {

301

302 Value *NegOp = negate(I->getOperand(0), IsNSW, Depth + 1);

303 if (!NegOp)

304 return nullptr;

305 return Builder.CreateFreeze(NegOp, I->getName() + ".neg");

306 }

307 case Instruction::PHI: {

308

311 for (auto I : zip(PHI->incoming_values(), NegatedIncomingValues)) {

312

313 if (DT.dominates(PHI->getParent(), std::get<0>(I)))

314 return nullptr;

315 if (!(std::get<1>(I) =

316 negate(std::get<0>(I), IsNSW, Depth + 1)))

317 return nullptr;

318 }

319

320 PHINode *NegatedPHI = Builder.CreatePHI(

321 PHI->getType(), PHI->getNumOperands(), PHI->getName() + ".neg");

322 for (auto I : zip(NegatedIncomingValues, PHI->blocks()))

323 NegatedPHI->addIncoming(std::get<0>(I), std::get<1>(I));

324 return NegatedPHI;

325 }

326 case Instruction::Select: {

327 if (isKnownNegation(I->getOperand(1), I->getOperand(2), false,

328 false)) {

329

330

332

333 NewSelect->swapValues();

334

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

336

337 Value *TV = NewSelect->getTrueValue();

338 Value *FV = NewSelect->getFalseValue();

343 else {

346 }

347 Builder.Insert(NewSelect);

348 return NewSelect;

349 }

350

351 Value *NegOp1 = negate(I->getOperand(1), IsNSW, Depth + 1);

352 if (!NegOp1)

353 return nullptr;

354 Value *NegOp2 = negate(I->getOperand(2), IsNSW, Depth + 1);

355 if (!NegOp2)

356 return nullptr;

357

358 return Builder.CreateSelect(I->getOperand(0), NegOp1, NegOp2,

359 I->getName() + ".neg", I);

360 }

361 case Instruction::ShuffleVector: {

362

364 Value *NegOp0 = negate(I->getOperand(0), IsNSW, Depth + 1);

365 if (!NegOp0)

366 return nullptr;

367 Value *NegOp1 = negate(I->getOperand(1), IsNSW, Depth + 1);

368 if (!NegOp1)

369 return nullptr;

370 return Builder.CreateShuffleVector(NegOp0, NegOp1, Shuf->getShuffleMask(),

371 I->getName() + ".neg");

372 }

373 case Instruction::ExtractElement: {

374

376 Value *NegVector = negate(EEI->getVectorOperand(), IsNSW, Depth + 1);

377 if (!NegVector)

378 return nullptr;

379 return Builder.CreateExtractElement(NegVector, EEI->getIndexOperand(),

380 I->getName() + ".neg");

381 }

382 case Instruction::InsertElement: {

383

384

386 Value *NegVector = negate(IEI->getOperand(0), IsNSW, Depth + 1);

387 if (!NegVector)

388 return nullptr;

389 Value *NegNewElt = negate(IEI->getOperand(1), IsNSW, Depth + 1);

390 if (!NegNewElt)

391 return nullptr;

392 return Builder.CreateInsertElement(NegVector, NegNewElt, IEI->getOperand(2),

393 I->getName() + ".neg");

394 }

395 case Instruction::Trunc: {

396

397 Value *NegOp = negate(I->getOperand(0), false, Depth + 1);

398 if (!NegOp)

399 return nullptr;

400 return Builder.CreateTrunc(NegOp, I->getType(), I->getName() + ".neg");

401 }

402 case Instruction::Shl: {

403

404 IsNSW &= I->hasNoSignedWrap();

405 if (Value *NegOp0 = negate(I->getOperand(0), IsNSW, Depth + 1))

406 return Builder.CreateShl(NegOp0, I->getOperand(1), I->getName() + ".neg",

407 false, IsNSW);

408

411 return nullptr;

412 return Builder.CreateMul(

413 I->getOperand(0),

415 I->getName() + ".neg", false, IsNSW);

416 }

417 case Instruction::Or: {

419 return nullptr;

420 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);

421

422

424 return Builder.CreateNot(Ops[0], I->getName() + ".neg");

425

426 [[fallthrough]];

427 }

428 case Instruction::Add: {

429

430 SmallVector<Value *, 2> NegatedOps, NonNegatedOps;

431 for (Value *Op : I->operands()) {

432

433 if (Value *NegOp = negate(Op, false, Depth + 1)) {

434 NegatedOps.emplace_back(NegOp);

435 continue;

436 }

437

438

439 if (!IsTrulyNegation)

440 return nullptr;

441 NonNegatedOps.emplace_back(Op);

442 }

443 assert((NegatedOps.size() + NonNegatedOps.size()) == 2 &&

444 "Internal consistency check failed.");

445

446 if (NegatedOps.size() == 2)

447 return Builder.CreateAdd(NegatedOps[0], NegatedOps[1],

448 I->getName() + ".neg");

449 assert(IsTrulyNegation && "We should have early-exited then.");

450

451 if (NonNegatedOps.size() == 2)

452 return nullptr;

453

454 return Builder.CreateSub(NegatedOps[0], NonNegatedOps[0],

455 I->getName() + ".neg");

456 }

457 case Instruction::Xor: {

458 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);

459

460

462 if (IsTrulyNegation) {

464 return Builder.CreateAdd(Xor, ConstantInt::get(Xor->getType(), 1),

465 I->getName() + ".neg");

466 }

467 }

468 return nullptr;

469 }

470 case Instruction::Mul: {

471 std::array<Value *, 2> Ops = getSortedOperandsOfBinOp(I);

472

473 Value *NegatedOp, *OtherOp;

474

475

476 if (Value *NegOp1 = negate(Ops[1], false, Depth + 1)) {

477 NegatedOp = NegOp1;

478 OtherOp = Ops[0];

479 } else if (Value *NegOp0 = negate(Ops[0], false, Depth + 1)) {

480 NegatedOp = NegOp0;

481 OtherOp = Ops[1];

482 } else

483

484 return nullptr;

485 return Builder.CreateMul(NegatedOp, OtherOp, I->getName() + ".neg",

486 false, IsNSW && I->hasNoSignedWrap());

487 }

488 default:

489 return nullptr;

490 }

491

492 llvm_unreachable("Can't get here. We always return from switch.");

493}

494

495[[nodiscard]] Value *Negator::negate(Value *V, bool IsNSW, unsigned Depth) {

496 NegatorMaxDepthVisited.updateMax(Depth);

497 ++NegatorNumValuesVisited;

498

499#if LLVM_ENABLE_STATS

500 ++NumValuesVisitedInThisNegator;

501#endif

502

503#ifndef NDEBUG

504

505 Value *Placeholder = reinterpret_cast<Value *>(static_cast<uintptr_t>(-1));

506#endif

507

508

509 auto NegationsCacheIterator = NegationsCache.find(V);

510 if (NegationsCacheIterator != NegationsCache.end()) {

511 ++NegatorNumNegationsFoundInCache;

512 Value *NegatedV = NegationsCacheIterator->second;

513 assert(NegatedV != Placeholder && "Encountered a cycle during negation.");

514 return NegatedV;

515 }

516

517#ifndef NDEBUG

518

519

520

521 NegationsCache[V] = Placeholder;

522#endif

523

524

525 Value *NegatedV = visitImpl(V, IsNSW, Depth);

526

527 NegationsCache[V] = NegatedV;

528

529 return NegatedV;

530}

531

532[[nodiscard]] std::optionalNegator::Result Negator::run(Value *Root,

533 bool IsNSW) {

534 Value *Negated = negate(Root, IsNSW, 0);

535 if (!Negated) {

536

537

538 for (Instruction *I : llvm::reverse(NewInstructions))

539 I->eraseFromParent();

540 return std::nullopt;

541 }

543}

544

547 ++NegatorTotalNegationsAttempted;

548 LLVM_DEBUG(dbgs() << "Negator: attempting to sink negation into " << *Root

549 << "\n");

550

552 return nullptr;

553

555 LHSIsZero);

556 std::optional Res = N.run(Root, IsNSW);

557 if (!Res) {

558 LLVM_DEBUG(dbgs() << "Negator: failed to sink negation into " << *Root

559 << "\n");

560 return nullptr;

561 }

562

563 LLVM_DEBUG(dbgs() << "Negator: successfully sunk negation into " << *Root

564 << "\n NEW: " << *Res->second << "\n");

565 ++NegatorNumTreesNegated;

566

567

568

569

573

574

575

576 LLVM_DEBUG(dbgs() << "Negator: Propagating " << Res->first.size()

577 << " instrs to InstCombine\n");

578 NegatorMaxInstructionsCreated.updateMax(Res->first.size());

579 NegatorNumInstructionsNegatedSuccess += Res->first.size();

580

581

584

585

586 return Res->second;

587}

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

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

This file provides an implementation of debug counters.

#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)

This file defines the DenseMap class.

This defines the Use class.

This file provides internal interfaces used to implement the InstCombine.

static constexpr unsigned NegatorDefaultMaxDepth

static cl::opt< bool > NegatorEnabled("instcombine-negator-enabled", cl::init(true), cl::desc("Should we attempt to sink negations?"))

static cl::opt< unsigned > NegatorMaxDepth("instcombine-negator-max-depth", cl::init(NegatorDefaultMaxDepth), cl::desc("What is the maximal lookup depth when trying to " "check for viability of negation sinking."))

This file provides the interface for the instcombine pass implementation.

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

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 LLVM_ABI Constant * getNot(Constant *C)

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

static LLVM_ABI Constant * getAllOnesValue(Type *Ty)

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

static bool shouldExecute(CounterInfo &Counter)

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

void SetCurrentDebugLocation(DebugLoc L)

Set location information used by debugging information.

InstTy * Insert(InstTy *I, const Twine &Name="") const

Insert and return the specified instruction.

void ClearInsertionPoint()

Clear the insertion point: created instructions will not be inserted into a block.

Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...

const DataLayout & getDataLayout() const

DominatorTree & getDominatorTree() const

static unsigned getComplexity(Value *V)

Assign a complexity or rank value to LLVM Values.

This is an important class for using LLVM in a threaded context.

static Value * Negate(bool LHSIsZero, bool IsNSW, Value *Root, InstCombinerImpl &IC)

Attempt to negate Root.

Definition InstCombineNegator.cpp:545

void addIncoming(Value *V, BasicBlock *BB)

Add an incoming value to the end of the PHI list.

reference emplace_back(ArgTypes &&... Args)

TargetFolder - Create constants with target dependent folding.

LLVM_ABI unsigned getScalarSizeInBits() const LLVM_READONLY

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

LLVM Value Representation.

Type * getType() const

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

LLVM_ABI LLVMContext & getContext() const

All values hold a context through their type.

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

#define llvm_unreachable(msg)

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

@ C

The default llvm calling convention, compatible with C.

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)

BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)

match_combine_or< CastInst_match< OpTy, TruncInst >, OpTy > m_TruncOrSelf(const OpTy &Op)

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)

specificval_ty m_Specific(const Value *V)

Match if we have a specific specified value.

specific_intval< true > m_SpecificIntAllowPoison(const APInt &V)

cst_pred_ty< is_one > m_One()

Match an integer 1 or a vector with all elements equal to 1.

cst_pred_ty< is_any_apint > m_AnyIntegralConstant()

Match an integer or vector with any integral constant.

match_immconstant_ty m_ImmConstant()

Match an arbitrary immediate Constant and ignore it.

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)

auto m_Undef()

Match an arbitrary undef constant.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

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

zip iterator for two or more iteratable types.

FunctionAddr VTableAddr Value

decltype(auto) dyn_cast(const From &Val)

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

auto reverse(ContainerTy &&C)

LLVM_ABI raw_ostream & dbgs()

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

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...

@ Xor

Bitwise or logical XOR of integers.

DWARFExpression::Operation Op

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

constexpr unsigned BitWidth

decltype(auto) cast(const From &Val)

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

LLVM_ABI bool isKnownNegation(const Value *X, const Value *Y, bool NeedNSW=false, bool AllowPoison=true)

Return true if the two given values are negation.

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

Implement std::swap in terms of BitVector swap.