This is an archive of the discontinued LLVM Phabricator instance.

[llvm-reduce] Introduce operands-skip pass.
ClosedPublic

Authored by Meinersbur on Oct 14 2021, 9:48 AM.

Details

Summary

Add a new "operands-skip" pass whose goal is to remove instructions in the middle of dependency chains. For instance:

%baseptr = alloca i32
%arrayidx = getelementptr i32, i32* %baseptr, i32 %idxprom
store i32 42, i32* %arrayidx

might be reducible to

%baseptr = alloca i32
%arrayidx = getelementptr ...  ; now dead, together with the computation of %idxprom
store i32 42, i32* %baseptr

Other passes would either replace %baseptr with undef (operands, instructions) or move it to become a function argument (operands-to-args), both of which might fail the interestingness check.

In principle the implementation allows operand replacement with any value or instruction in the function that passes the filter constraints (same type, dominance, "more reduced"), but is limited in this patch to values that are directly or indirectly used to compute the current operand value, motivated by the example above. Additionally, function arguments are added to the candidate set which helps reducing the number of relevant arguments mitigating a concern of too many arguments mentioned in https://reviews.llvm.org/D110274#3025013.

Possible future extensions:

  • Instead of requiring the same type, bitcast/trunc/zext could be automatically inserted for some more flexibility.
  • If undef is added to the candidate set, "operands-skip"is able to produce any reduction that "operands" can do. Additional candidates might be zero and one, where the "reductive power" classification can prefer one over the other. If undefined behaviour should not be introduced, undef can be removed from the candidate set.

Diff Detail

Event Timeline

Meinersbur created this revision.Oct 14 2021, 9:48 AM
Meinersbur requested review of this revision.Oct 14 2021, 9:48 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 14 2021, 9:48 AM

this looks very cool!

llvm/test/tools/llvm-reduce/operands-skip.ll
3

leftover debugging?

llvm/tools/llvm-reduce/deltas/ReduceOperandsSkip.cpp
23
49

I thought we preferred ConstantData over undef

76

consistency

78

I'd prefer a function_ref<void(Use &, ArrayRef<Value *>)> over templates

81–84

DominatorTree DT(F);
the pass manager infra doesn't give us anything here

86
117
133

is && necessary? the result of collectReferencedValues() should be moved into a local variable

Meinersbur marked 9 inline comments as done.
Meinersbur edited the summary of this revision. (Show Details)
  • Address revier comments
  • Skip over declarations
Meinersbur added inline comments.Oct 18 2021, 9:11 PM
llvm/tools/llvm-reduce/deltas/ReduceOperandsSkip.cpp
49

You mentioned this as "reduce to undef/1/0, probably in that order" in https://reviews.llvm.org/D110274#3062642, but I didn't interpret this as consensus. My approach here was to mimic the current behaviour where everything is reduced to undef if possible. If introducing undef is not desired, then an option could avoid adding it to the set of possibilities. In this approach, it could only be added if there there is already an undef somewhere.

Changing the order of preference might still be better. I changed it accordingly.

133

It's not necessary, but would save the invocation of move-ctor.

143

removed && here too

the latest diff also contains the reduce-operands-to-args pass

  • Rebase
  • Remove operands-to-args pass from diff
aeubanks accepted this revision.Oct 28 2021, 3:55 PM
aeubanks added inline comments.
llvm/tools/llvm-reduce/deltas/ReduceOperandsSkip.cpp
56

an UndefValue is a ConstantData, so this should be moved into the ConstantData if block above

This revision is now accepted and ready to land.Oct 28 2021, 3:55 PM

Address last comment before landing

This revision was landed with ongoing or failed builds.Nov 11 2021, 4:54 PM
This revision was automatically updated to reflect the committed changes.