This is an archive of the discontinued LLVM Phabricator instance.

[ValueTracking] Let isGuaranteedNotToBeUndefOrPoison use canCreateUndefOrPoison
ClosedPublic

Authored by aqjune on Jul 15 2020, 7:15 PM.

Diff Detail

Event Timeline

aqjune created this revision.Jul 15 2020, 7:15 PM
nikic added a comment.EditedJul 16 2020, 10:13 AM

While you're here, I'd suggest to go through all of Instructions.def and add an entry in the switch for all instructions that have a return value, so we at least know what we're missing. This is what I see:

  • udiv, sdiv, urem, srem: If exact not set, recursively check operands. (Division by zero etc is undefined behavior, not poison.)
  • shl, lshr, ashr: Apart from exact, these also have the bitwidth case, which could be checked for constant shamt.
  • alloca: Never undef/poison. (The pointer, not the content...)
  • load: We don't know. (Might want !noundef metadata in the future, if that's useful)
  • atomicrmw, cmpxchg: No idea, no familiarity.
  • trunc, sext, zext: Check operands, no special cases.
  • fptoui, fptosi: These poison on overflow, can't infer anything useful.
  • uitofp, sitofp: These stopped poisoning on overflow at some point, just check operands.
  • fpext, fptrunc: Presumably just check operand, but I'm not familiar.
  • ptrtoint, inttoptr: Check operand.
  • addrspacecast: I would assume this is also just "check operand", but with addrspacecasts you never know :)
  • call/invoke: Check noundef attribute on return value.
  • select: Check operands and FMF.
  • extractelement, insertelement, extractvalue, insertvalue: Check operands.
  • shufflevalue: Have to take undef lanes into account.

It might make sense to add some of the straightforward cases (like trunc/sext/zext) to this review and leave the rest as TODOs.

llvm/lib/Analysis/ValueTracking.cpp
4815–4816

Should be cast<> rather than dyn_cast<>.

4817

Move this case into the switch? Similar to how you handle FPMathOperator.

4818

Use OpCheck(Opr->getOperand(0)) here?

aqjune added a comment.EditedJul 17 2020, 12:01 AM

For this, canCreatePoison seems to be helpful. I'll add a patch that

  • refactors canCreatePoison so it takes an operator
  • add a function canCreateUndef

and make this patch invoke canCreateUndef.

aqjune updated this revision to Diff 278730.Jul 17 2020, 5:11 AM

Call canCreateUndef so it does all things about opcode inspection

Only one nit from my side, don't wait for me.

llvm/lib/Analysis/ValueTracking.cpp
4826

Nit: Can we have a comment /* something */ true so I know what true means ?

aqjune updated this revision to Diff 279067.Jul 19 2020, 12:24 AM

Use canCreateUndefOrPoison

aqjune retitled this revision from [ValueTracking] Let isGuaranteedNotToBeUndefOrPoison use Operator, look into more ops to [ValueTracking] Let isGuaranteedNotToBeUndefOrPoison use canCreateUndefOrPoison.Jul 19 2020, 12:25 AM
aqjune edited the summary of this revision. (Show Details)
aqjune marked an inline comment as done.
aqjune added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
4786

Added support for calls with noundef ret attribute since it's a small change

nikic added inline comments.Jul 19 2020, 6:29 AM
llvm/include/llvm/Analysis/ValueTracking.h
611

paddings -> padding

llvm/lib/Analysis/ValueTracking.cpp
4790

The positioning here is a bit odd, I'd move this below (or inside) the Operator check.

4833

Does this conservative return still make sense? At this point this should only be an optimization (don't bother with dominator checks for const exprs) than something that is needed for correctness.

aqjune updated this revision to Diff 279091.Jul 19 2020, 9:09 AM

Reflect comments

This revision is now accepted and ready to land.Jul 19 2020, 9:20 AM
aqjune updated this revision to Diff 279093.Jul 19 2020, 9:21 AM
aqjune marked an inline comment as done.

Remove the ConstExpr check

No objections from me anymore.

llvm/lib/Analysis/ValueTracking.cpp
4785

Personally, I'd keep freeze up top, easy case after all ;). No strong opinion though.

aqjune marked an inline comment as done.Jul 19 2020, 10:10 AM

Since isGuaranteedNotToBeUndefOrPoison now traverses over many ops, there is 0.3% slowdown from ReleaseLTO-O3 in average on CTMark:

+-----------------------------------------------+---------+-------+----------+-------+-------+----------+
|                                               | compile |       |          | link  |       |          |
+-----------------------------------------------+---------+-------+----------+-------+-------+----------+
|                                               | base    |       | slowdown | base  |       | slowdown |
| CTMark/7zip/7zip-benchmark.test               | 89.31   | 89.96 | 0.72%    | 46.73 | 46.93 | 0.43%    |
| CTMark/Bullet/bullet.test                     | 62.76   | 63.13 | 0.59%    | 9.59  |  9.62 | 0.31%    |
| CTMark/ClamAV/clamscan.test                   | 26.91   | 26.95 | 0.13%    | 24.70 | 24.82 | 0.48%    |
| CTMark/SPASS/SPASS.test                       | 26.07   | 26.18 | 0.42%    | 19.60 | 19.72 | 0.60%    |
| CTMark/consumer-typeset/consumer-typeset.test | 19.58   | 19.65 | 0.36%    | 18.41 | 18.49 | 0.44%    |
| CTMark/kimwitu++/kc.test                      | 26.50   | 26.56 | 0.22%    | 14.54 | 14.51 | -0.21%   |
| CTMark/lencod/lencod.test                     | 34.48   | 34.47 | -0.03%   | 38.38 | 38.67 | 0.76%    |
| CTMark/mafft/pairlocalalign.test              | 16.17   | 16.25 | 0.44%    | 8.64  |  8.64 | 0.00%    |
| CTMark/sqlite3/sqlite3.test                   | 24.49   | 24.42 | -0.28%   | 24.43 | 24.52 | 0.36%    |
| CTMark/tramp3d-v4/tramp3d-v4.test             | 49.14   | 49.10 | -0.08%   | 35.64 | 35.85 | 0.59%    |
+-----------------------------------------------+---------+-------+----------+-------+-------+----------+

The solution for this doesn't seem trivial. Fixing existing undef/poison-related bugs might introduce more calls to this function, which will bring more slowdown.
What would be the right direction to address this issue?

llvm/lib/Analysis/ValueTracking.cpp
4785

Since constants and noundefs (after relevant patches are landed) are/will be very common, locating those checks at the top seemed beneficial.
I saw slight degradation from compilation time from this patch - maybe a single isa<> might be super cheap so it won't make affect the result, but wanted to make things optimal :)

Unlike load/stores, the instructions we're targetting are likely to be changed by many transformations, maintaining a cache for the analysis result should be costly?
One possible approach that I can come up with is to reduce MaxDepth & add !noundef.

Since isGuaranteedNotToBeUndefOrPoison now traverses over many ops, there is 0.3% slowdown from ReleaseLTO-O3 in average on CTMark:
...
The solution for this doesn't seem trivial. Fixing existing undef/poison-related bugs might introduce more calls to this function, which will bring more slowdown.
What would be the right direction to address this issue?

I'm not seeing any measurable impact from this change in terms of instructions retired: https://llvm-compile-time-tracker.com/compare.php?from=ef66e3d086308800d7947a385c2ae09d3f55a695&to=081c25553185740fde7d93d2a32ef4e87ae480aa&stat=instructions Most likely the difference you see is within noise for wall time measurements, which tends to be high.

Maybe it will become a problem in the future if this functions sees heavier usage, but I don't think compile-time is a big concern right now.

Okay, thank you for the info!

This revision was automatically updated to reflect the committed changes.

Oops, I'll have a look

fhahn added a subscriber: fhahn.Jul 24 2020, 4:09 AM

Oops, I'll have a look

I also looked into this a day ago or so.

The problem seems to be that containsConstantExpression/containsUndefElement are called on non ConstantDataVector/ConstantVector, which segfaults. I will put up a patch soon.

aqjune added a comment.EditedJul 24 2020, 4:21 AM

@fhahn Yes, C was like <4 x i64*> getelementptr (i64, i64* null, <4 x i64> <i64 0, i64 0, i64 0, i64 -128>).

Thank you for the info..! I'm fine if you are making the patch.