Skip to content

Commit 79dffc6

Browse files
nikicnikic
committedApr 16, 2019
[IR] Add WithOverflowInst class
This adds a WithOverflowInst class with a few helper methods to get the underlying binop, signedness and nowrap type and makes use of it where sensible. There will be two more uses in D60650/D60656. The refactorings are all NFC, though I left some TODOs where things could be improved. In particular we have two places where add/sub are handled but mul isn't. Differential Revision: https://reviews.llvm.org/D60668 llvm-svn: 358512
·
llvmorg-21-initllvmorg-9.0.0-rc1
1 parent d8f776a commit 79dffc6

File tree

9 files changed

+154
-221
lines changed

9 files changed

+154
-221
lines changed
 

Diff for: ‎llvm/include/llvm/Analysis/ValueTracking.h

+4-3
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,7 @@ class DataLayout;
3232
class DominatorTree;
3333
class GEPOperator;
3434
class IntrinsicInst;
35+
class WithOverflowInst;
3536
struct KnownBits;
3637
class Loop;
3738
class LoopInfo;
@@ -454,10 +455,10 @@ class Value;
454455
const Instruction *CxtI,
455456
const DominatorTree *DT);
456457

457-
/// Returns true if the arithmetic part of the \p II 's result is
458+
/// Returns true if the arithmetic part of the \p WO 's result is
458459
/// used only along the paths control dependent on the computation
459-
/// not overflowing, \p II being an <op>.with.overflow intrinsic.
460-
bool isOverflowIntrinsicNoWrap(const IntrinsicInst *II,
460+
/// not overflowing, \p WO being an <op>.with.overflow intrinsic.
461+
bool isOverflowIntrinsicNoWrap(const WithOverflowInst *WO,
461462
const DominatorTree &DT);
462463

463464

Diff for: ‎llvm/include/llvm/IR/IntrinsicInst.h

+33
Original file line numberDiff line numberDiff line change
@@ -265,6 +265,39 @@ namespace llvm {
265265
}
266266
};
267267

268+
/// This class represents a op.with.overflow intrinsic.
269+
class WithOverflowInst : public IntrinsicInst {
270+
public:
271+
static bool classof(const IntrinsicInst *I) {
272+
switch (I->getIntrinsicID()) {
273+
case Intrinsic::uadd_with_overflow:
274+
case Intrinsic::sadd_with_overflow:
275+
case Intrinsic::usub_with_overflow:
276+
case Intrinsic::ssub_with_overflow:
277+
case Intrinsic::umul_with_overflow:
278+
case Intrinsic::smul_with_overflow:
279+
return true;
280+
default:
281+
return false;
282+
}
283+
}
284+
static bool classof(const Value *V) {
285+
return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
286+
}
287+
288+
Value *getLHS() const { return const_cast<Value*>(getArgOperand(0)); }
289+
Value *getRHS() const { return const_cast<Value*>(getArgOperand(1)); }
290+
291+
/// Returns the binary operation underlying the intrinsic.
292+
Instruction::BinaryOps getBinaryOp() const;
293+
294+
/// Whether the intrinsic is signed or unsigned.
295+
bool isSigned() const;
296+
297+
/// Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
298+
unsigned getNoWrapKind() const;
299+
};
300+
268301
/// Common base class for all memory intrinsics. Simply provides
269302
/// common methods.
270303
/// Written as CRTP to avoid a common base class amongst the

Diff for: ‎llvm/lib/Analysis/ScalarEvolution.cpp

+13-44
Original file line numberDiff line numberDiff line change
@@ -4575,52 +4575,21 @@ static Optional<BinaryOp> MatchBinaryOp(Value *V, DominatorTree &DT) {
45754575
if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0)
45764576
break;
45774577

4578-
auto *CI = dyn_cast<CallInst>(EVI->getAggregateOperand());
4579-
if (!CI)
4578+
auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand());
4579+
if (!WO)
45804580
break;
45814581

4582-
if (auto *F = CI->getCalledFunction())
4583-
switch (F->getIntrinsicID()) {
4584-
case Intrinsic::sadd_with_overflow:
4585-
case Intrinsic::uadd_with_overflow:
4586-
if (!isOverflowIntrinsicNoWrap(cast<IntrinsicInst>(CI), DT))
4587-
return BinaryOp(Instruction::Add, CI->getArgOperand(0),
4588-
CI->getArgOperand(1));
4589-
4590-
// Now that we know that all uses of the arithmetic-result component of
4591-
// CI are guarded by the overflow check, we can go ahead and pretend
4592-
// that the arithmetic is non-overflowing.
4593-
if (F->getIntrinsicID() == Intrinsic::sadd_with_overflow)
4594-
return BinaryOp(Instruction::Add, CI->getArgOperand(0),
4595-
CI->getArgOperand(1), /* IsNSW = */ true,
4596-
/* IsNUW = */ false);
4597-
else
4598-
return BinaryOp(Instruction::Add, CI->getArgOperand(0),
4599-
CI->getArgOperand(1), /* IsNSW = */ false,
4600-
/* IsNUW*/ true);
4601-
case Intrinsic::ssub_with_overflow:
4602-
case Intrinsic::usub_with_overflow:
4603-
if (!isOverflowIntrinsicNoWrap(cast<IntrinsicInst>(CI), DT))
4604-
return BinaryOp(Instruction::Sub, CI->getArgOperand(0),
4605-
CI->getArgOperand(1));
4606-
4607-
// The same reasoning as sadd/uadd above.
4608-
if (F->getIntrinsicID() == Intrinsic::ssub_with_overflow)
4609-
return BinaryOp(Instruction::Sub, CI->getArgOperand(0),
4610-
CI->getArgOperand(1), /* IsNSW = */ true,
4611-
/* IsNUW = */ false);
4612-
else
4613-
return BinaryOp(Instruction::Sub, CI->getArgOperand(0),
4614-
CI->getArgOperand(1), /* IsNSW = */ false,
4615-
/* IsNUW = */ true);
4616-
case Intrinsic::smul_with_overflow:
4617-
case Intrinsic::umul_with_overflow:
4618-
return BinaryOp(Instruction::Mul, CI->getArgOperand(0),
4619-
CI->getArgOperand(1));
4620-
default:
4621-
break;
4622-
}
4623-
break;
4582+
Instruction::BinaryOps BinOp = WO->getBinaryOp();
4583+
bool Signed = WO->isSigned();
4584+
// TODO: Should add nuw/nsw flags for mul as well.
4585+
if (BinOp == Instruction::Mul || !isOverflowIntrinsicNoWrap(WO, DT))
4586+
return BinaryOp(BinOp, WO->getLHS(), WO->getRHS());
4587+
4588+
// Now that we know that all uses of the arithmetic-result component of
4589+
// CI are guarded by the overflow check, we can go ahead and pretend
4590+
// that the arithmetic is non-overflowing.
4591+
return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(),
4592+
/* IsNSW = */ Signed, /* IsNUW = */ !Signed);
46244593
}
46254594

46264595
default:

Diff for: ‎llvm/lib/Analysis/ValueTracking.cpp

+2-13
Original file line numberDiff line numberDiff line change
@@ -4206,23 +4206,12 @@ OverflowResult llvm::computeOverflowForSignedSub(const Value *LHS,
42064206
return mapOverflowResult(LHSRange.signedSubMayOverflow(RHSRange));
42074207
}
42084208

4209-
bool llvm::isOverflowIntrinsicNoWrap(const IntrinsicInst *II,
4209+
bool llvm::isOverflowIntrinsicNoWrap(const WithOverflowInst *WO,
42104210
const DominatorTree &DT) {
4211-
#ifndef NDEBUG
4212-
auto IID = II->getIntrinsicID();
4213-
assert((IID == Intrinsic::sadd_with_overflow ||
4214-
IID == Intrinsic::uadd_with_overflow ||
4215-
IID == Intrinsic::ssub_with_overflow ||
4216-
IID == Intrinsic::usub_with_overflow ||
4217-
IID == Intrinsic::smul_with_overflow ||
4218-
IID == Intrinsic::umul_with_overflow) &&
4219-
"Not an overflow intrinsic!");
4220-
#endif
4221-
42224211
SmallVector<const BranchInst *, 2> GuardingBranches;
42234212
SmallVector<const ExtractValueInst *, 2> Results;
42244213

4225-
for (const User *U : II->users()) {
4214+
for (const User *U : WO->users()) {
42264215
if (const auto *EVI = dyn_cast<ExtractValueInst>(U)) {
42274216
assert(EVI->getNumIndices() == 1 && "Obvious from CI's type");
42284217

Diff for: ‎llvm/lib/IR/IntrinsicInst.cpp

+34
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,7 @@
2121
//===----------------------------------------------------------------------===//
2222

2323
#include "llvm/IR/IntrinsicInst.h"
24+
#include "llvm/IR/Operator.h"
2425
#include "llvm/ADT/StringSwitch.h"
2526
#include "llvm/IR/Constants.h"
2627
#include "llvm/IR/DebugInfoMetadata.h"
@@ -168,3 +169,36 @@ bool ConstrainedFPIntrinsic::isTernaryOp() const {
168169
}
169170
}
170171

172+
Instruction::BinaryOps WithOverflowInst::getBinaryOp() const {
173+
switch (getIntrinsicID()) {
174+
case Intrinsic::uadd_with_overflow:
175+
case Intrinsic::sadd_with_overflow:
176+
return Instruction::Add;
177+
case Intrinsic::usub_with_overflow:
178+
case Intrinsic::ssub_with_overflow:
179+
return Instruction::Sub;
180+
case Intrinsic::umul_with_overflow:
181+
case Intrinsic::smul_with_overflow:
182+
return Instruction::Mul;
183+
default:
184+
llvm_unreachable("Invalid intrinsic");
185+
}
186+
}
187+
188+
bool WithOverflowInst::isSigned() const {
189+
switch (getIntrinsicID()) {
190+
case Intrinsic::sadd_with_overflow:
191+
case Intrinsic::ssub_with_overflow:
192+
case Intrinsic::smul_with_overflow:
193+
return true;
194+
default:
195+
return false;
196+
}
197+
}
198+
199+
unsigned WithOverflowInst::getNoWrapKind() const {
200+
if (isSigned())
201+
return OverflowingBinaryOperator::NoSignedWrap;
202+
else
203+
return OverflowingBinaryOperator::NoUnsignedWrap;
204+
}

Diff for: ‎llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

+20-45
Original file line numberDiff line numberDiff line change
@@ -2667,53 +2667,28 @@ Instruction *InstCombiner::visitExtractValueInst(ExtractValueInst &EV) {
26672667
return ExtractValueInst::Create(IV->getInsertedValueOperand(),
26682668
makeArrayRef(exti, exte));
26692669
}
2670-
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Agg)) {
2671-
// We're extracting from an intrinsic, see if we're the only user, which
2672-
// allows us to simplify multiple result intrinsics to simpler things that
2673-
// just get one value.
2674-
if (II->hasOneUse()) {
2675-
// Check if we're grabbing the overflow bit or the result of a 'with
2676-
// overflow' intrinsic. If it's the latter we can remove the intrinsic
2670+
if (WithOverflowInst *WO = dyn_cast<WithOverflowInst>(Agg)) {
2671+
// We're extracting from an overflow intrinsic, see if we're the only user,
2672+
// which allows us to simplify multiple result intrinsics to simpler
2673+
// things that just get one value.
2674+
if (WO->hasOneUse()) {
2675+
// Check if we're grabbing only the result of a 'with overflow' intrinsic
26772676
// and replace it with a traditional binary instruction.
2678-
switch (II->getIntrinsicID()) {
2679-
case Intrinsic::uadd_with_overflow:
2680-
case Intrinsic::sadd_with_overflow:
2681-
if (*EV.idx_begin() == 0) { // Normal result.
2682-
Value *LHS = II->getArgOperand(0), *RHS = II->getArgOperand(1);
2683-
replaceInstUsesWith(*II, UndefValue::get(II->getType()));
2684-
eraseInstFromFunction(*II);
2685-
return BinaryOperator::CreateAdd(LHS, RHS);
2686-
}
2687-
2688-
// If the normal result of the add is dead, and the RHS is a constant,
2689-
// we can transform this into a range comparison.
2690-
// overflow = uadd a, -4 --> overflow = icmp ugt a, 3
2691-
if (II->getIntrinsicID() == Intrinsic::uadd_with_overflow)
2692-
if (ConstantInt *CI = dyn_cast<ConstantInt>(II->getArgOperand(1)))
2693-
return new ICmpInst(ICmpInst::ICMP_UGT, II->getArgOperand(0),
2694-
ConstantExpr::getNot(CI));
2695-
break;
2696-
case Intrinsic::usub_with_overflow:
2697-
case Intrinsic::ssub_with_overflow:
2698-
if (*EV.idx_begin() == 0) { // Normal result.
2699-
Value *LHS = II->getArgOperand(0), *RHS = II->getArgOperand(1);
2700-
replaceInstUsesWith(*II, UndefValue::get(II->getType()));
2701-
eraseInstFromFunction(*II);
2702-
return BinaryOperator::CreateSub(LHS, RHS);
2703-
}
2704-
break;
2705-
case Intrinsic::umul_with_overflow:
2706-
case Intrinsic::smul_with_overflow:
2707-
if (*EV.idx_begin() == 0) { // Normal result.
2708-
Value *LHS = II->getArgOperand(0), *RHS = II->getArgOperand(1);
2709-
replaceInstUsesWith(*II, UndefValue::get(II->getType()));
2710-
eraseInstFromFunction(*II);
2711-
return BinaryOperator::CreateMul(LHS, RHS);
2712-
}
2713-
break;
2714-
default:
2715-
break;
2677+
if (*EV.idx_begin() == 0) {
2678+
Instruction::BinaryOps BinOp = WO->getBinaryOp();
2679+
Value *LHS = WO->getLHS(), *RHS = WO->getRHS();
2680+
replaceInstUsesWith(*WO, UndefValue::get(WO->getType()));
2681+
eraseInstFromFunction(*WO);
2682+
return BinaryOperator::Create(BinOp, LHS, RHS);
27162683
}
2684+
2685+
// If the normal result of the add is dead, and the RHS is a constant,
2686+
// we can transform this into a range comparison.
2687+
// overflow = uadd a, -4 --> overflow = icmp ugt a, 3
2688+
if (WO->getIntrinsicID() == Intrinsic::uadd_with_overflow)
2689+
if (ConstantInt *CI = dyn_cast<ConstantInt>(WO->getRHS()))
2690+
return new ICmpInst(ICmpInst::ICMP_UGT, WO->getLHS(),
2691+
ConstantExpr::getNot(CI));
27172692
}
27182693
}
27192694
if (LoadInst *L = dyn_cast<LoadInst>(Agg))

Diff for: ‎llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

+32-53
Original file line numberDiff line numberDiff line change
@@ -399,69 +399,48 @@ static bool processSwitch(SwitchInst *SI, LazyValueInfo *LVI,
399399
}
400400

401401
// See if we can prove that the given overflow intrinsic will not overflow.
402-
static bool willNotOverflow(IntrinsicInst *II, LazyValueInfo *LVI) {
403-
using OBO = OverflowingBinaryOperator;
404-
auto NoWrap = [&] (Instruction::BinaryOps BinOp, unsigned NoWrapKind) {
405-
Value *RHS = II->getOperand(1);
406-
ConstantRange RRange = LVI->getConstantRange(RHS, II->getParent(), II);
407-
ConstantRange NWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
408-
BinOp, RRange, NoWrapKind);
409-
// As an optimization, do not compute LRange if we do not need it.
410-
if (NWRegion.isEmptySet())
411-
return false;
412-
Value *LHS = II->getOperand(0);
413-
ConstantRange LRange = LVI->getConstantRange(LHS, II->getParent(), II);
414-
return NWRegion.contains(LRange);
415-
};
416-
switch (II->getIntrinsicID()) {
417-
default:
418-
break;
419-
case Intrinsic::uadd_with_overflow:
420-
return NoWrap(Instruction::Add, OBO::NoUnsignedWrap);
421-
case Intrinsic::sadd_with_overflow:
422-
return NoWrap(Instruction::Add, OBO::NoSignedWrap);
423-
case Intrinsic::usub_with_overflow:
424-
return NoWrap(Instruction::Sub, OBO::NoUnsignedWrap);
425-
case Intrinsic::ssub_with_overflow:
426-
return NoWrap(Instruction::Sub, OBO::NoSignedWrap);
427-
}
428-
return false;
402+
static bool willNotOverflow(WithOverflowInst *WO, LazyValueInfo *LVI) {
403+
// TODO: Also support multiplication.
404+
Instruction::BinaryOps BinOp = WO->getBinaryOp();
405+
if (BinOp == Instruction::Mul)
406+
return false;
407+
408+
Value *RHS = WO->getRHS();
409+
ConstantRange RRange = LVI->getConstantRange(RHS, WO->getParent(), WO);
410+
ConstantRange NWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
411+
BinOp, RRange, WO->getNoWrapKind());
412+
// As an optimization, do not compute LRange if we do not need it.
413+
if (NWRegion.isEmptySet())
414+
return false;
415+
Value *LHS = WO->getLHS();
416+
ConstantRange LRange = LVI->getConstantRange(LHS, WO->getParent(), WO);
417+
return NWRegion.contains(LRange);
429418
}
430419

431-
static void processOverflowIntrinsic(IntrinsicInst *II) {
432-
IRBuilder<> B(II);
433-
Value *NewOp = nullptr;
434-
switch (II->getIntrinsicID()) {
435-
default:
436-
llvm_unreachable("Unexpected instruction.");
437-
case Intrinsic::uadd_with_overflow:
438-
NewOp = B.CreateNUWAdd(II->getOperand(0), II->getOperand(1), II->getName());
439-
break;
440-
case Intrinsic::sadd_with_overflow:
441-
NewOp = B.CreateNSWAdd(II->getOperand(0), II->getOperand(1), II->getName());
442-
break;
443-
case Intrinsic::usub_with_overflow:
444-
NewOp = B.CreateNUWSub(II->getOperand(0), II->getOperand(1), II->getName());
445-
break;
446-
case Intrinsic::ssub_with_overflow:
447-
NewOp = B.CreateNSWSub(II->getOperand(0), II->getOperand(1), II->getName());
448-
break;
449-
}
420+
static void processOverflowIntrinsic(WithOverflowInst *WO) {
421+
IRBuilder<> B(WO);
422+
Value *NewOp = B.CreateBinOp(
423+
WO->getBinaryOp(), WO->getLHS(), WO->getRHS(), WO->getName());
424+
if (WO->isSigned())
425+
cast<Instruction>(NewOp)->setHasNoSignedWrap();
426+
else
427+
cast<Instruction>(NewOp)->setHasNoUnsignedWrap();
428+
429+
Value *NewI = B.CreateInsertValue(UndefValue::get(WO->getType()), NewOp, 0);
430+
NewI = B.CreateInsertValue(NewI, ConstantInt::getFalse(WO->getContext()), 1);
431+
WO->replaceAllUsesWith(NewI);
432+
WO->eraseFromParent();
450433
++NumOverflows;
451-
Value *NewI = B.CreateInsertValue(UndefValue::get(II->getType()), NewOp, 0);
452-
NewI = B.CreateInsertValue(NewI, ConstantInt::getFalse(II->getContext()), 1);
453-
II->replaceAllUsesWith(NewI);
454-
II->eraseFromParent();
455434
}
456435

457436
/// Infer nonnull attributes for the arguments at the specified callsite.
458437
static bool processCallSite(CallSite CS, LazyValueInfo *LVI) {
459438
SmallVector<unsigned, 4> ArgNos;
460439
unsigned ArgNo = 0;
461440

462-
if (auto *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
463-
if (willNotOverflow(II, LVI)) {
464-
processOverflowIntrinsic(II);
441+
if (auto *WO = dyn_cast<WithOverflowInst>(CS.getInstruction())) {
442+
if (willNotOverflow(WO, LVI)) {
443+
processOverflowIntrinsic(WO);
465444
return true;
466445
}
467446
}

0 commit comments

Comments
 (0)
Please sign in to comment.