This is an archive of the discontinued LLVM Phabricator instance.

[mlgo] Add in-development instruction based features for regalloc advisor
ClosedPublic

Authored by aidengrossman on Aug 15 2022, 4:44 PM.

Details

Summary

This patch adds in instruction based features to the regalloc advisor
gated behind a flag so a user can decide at runtime whether or not they
want to enable the feature. The features are only enabled when LLVM is
compiled in MLGO develpment mode (LLVM_HAVE_TF_API) is set to true.

To extract the instruction features, I'm taking a list of segments from
each LiveInterval and noting the start and end SlotIndices. This list is then
sorted based on the start SlotIndex and I iterate through each SlotIndex
to grab instructions, making sure to check for overlaps. This results in
a vector of opcodes and binary mapping matrix that maps live ranges to the
opcodes of the instructions within that LR.

Diff Detail

Event Timeline

aidengrossman created this revision.Aug 15 2022, 4:44 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 15 2022, 4:44 PM
aidengrossman requested review of this revision.Aug 15 2022, 4:44 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 15 2022, 4:44 PM
mtrofin added inline comments.Aug 16 2022, 12:48 PM
llvm/test/CodeGen/MLRegalloc/dev-mode-extra-features-logging.ll
2

Because the output very verbose, perhaps just checking specific values may be more maintainable? Like checking that you counted things correctly in your 33x300 matrix - add some comments maybe about what the output looks like and why certain sentinel values are expected. This would also help one identify, later, if the test breaks legitimately due to a change (e.g. some machine instruction is now not present anymore -> of course the features change) vs due to a bug.

Changed up dev mode extra features test to make it less fragile by getting rid
of the exact logging diff check and adding more FileCheck checks on the
instructions and mapping matrix for the first eviction problem.

aidengrossman added inline comments.Aug 16 2022, 2:29 PM
llvm/test/CodeGen/MLRegalloc/dev-mode-extra-features-logging.ll
2

That's a very good point. The test could potentially be pretty fragile if checking the exact code output. I reworked the check to get rid of the exact diff and added a lot more FileCheck checks along with comments to make sure that the output looks as expected to some reasonable degree.

mtrofin added inline comments.Aug 16 2022, 5:45 PM
llvm/lib/CodeGen/MLRegallocEvictAdvisor.cpp
925

this deserves more comments about: the whole structure of the data packet you're preparing and the various steps along the way - it'll greatly help with maintainability, etc.

926

may be more readable to have a small struct with the 2 slot indices and size_t with nice readable names, and then avoid the whole std::get<x> business.

942

nit: we generally do if (!CurrentMachineInstruction).

1033

nit: or, // continue from the feature index the previous loop left off ?

llvm/test/CodeGen/MLRegalloc/dev-mode-extra-features-logging.ll
2

thanks, this looks way more manageable!

34

add a new line

aidengrossman marked 4 inline comments as done.

Adjust comments to better document the extraction algorithm and the data that
it returns. Also refactor to passing around a struct rather than a tuple and
adjust a comment in the dev mode logging.

llvm/lib/CodeGen/MLRegallocEvictAdvisor.cpp
925

I've added quite a few more comments on the structure of the extraction algorithm itself and the structure of the data that it extracts. Let me know if anything is unclear or too verbose and I'll work on fixing it.

1033

This was left over from some experimentation that I have since removed and thus was commenting a line that isn't even there. I've changed it to note your suggestion and also to explain why the indexing is slightly odd (only going to FeaturesWithDevelopmentCount -1 1 rather than FeaturesWithDevelopmentCount itself.

Fixed release mode build and gated more of the development feature tooling
with the preprocessing behind the LLVM_HAVE_TF_API flag.

Just making sure this patch doesn't go anywhere yet. When built with assertions on, the new development features are currently tripping an assertion when CurrentIndex.getNextIndex() is called when CurrentMachineInstruction is equal to nullptr. Need to do some more debugging/investigation see why this is going on.

Add if statement to handle edge case where the current machine instruction
is null and it tries to skip to the slotindex in the next machine instruction
but can't due to it being at the of the slotindex analysis.

mtrofin added inline comments.Sep 12 2022, 5:10 PM
llvm/lib/CodeGen/MLRegallocEvictAdvisor.cpp
149

rename this to OpcodeValueCutoff - Count to me refers at this point to how many opcodes in the tensor, but IIUC you actually mean values larger than that are unknown to us. Same for the comment.

265

you can avoid the -1 thing by splitting your RA_EVICT_FEATURES_UNDER_DEVELOPMENT_LIST in 2, the "first" and the "rest", and then forcing the index of the first to be == FeatureCount

#ifdef LLVM_HAVE_TF_API
#define RA_FIRST_EXTRA_FEATURE(M)  \
    M(int64_t, instructions, InstructionsShape,                                  \
    "Opcodes of the instructions covered by the eviction problem") 
#define RA_REST_EXTRA_FEATURES(M)                            \
  M(int64_t, instructions_mapping, InstructionsMappingShape,                   \
    "A binary matrix mapping LRs to instruction opcodes")
#define RA_EVICT_FEATURES_UNDER_DEVELOPMENT(M) \
  RA_FIRST_EXTRA_FEATURE(M) \
  RA_REST_EXTRA_FEATURES(M)
#else
#define RA_FIRST_EXTRA_FEATURE(M)
#define   RA_REST_EXTRA_FEATURES(M)
#endif

#define RA_EVICT_FEATURES_UNDER_DEVELOPMENT(M) \
  RA_FIRST_EXTRA_FEATURE(M) \
  RA_REST_EXTRA_FEATURES(M)
enum FeatureIDs {
#define _FEATURE_IDX_SIMPLE(_, name, __, ___) name
#define _FEATURE_IDX(A,B,C,D) _FEATURE_IDX_SIMPLE(A,B,C,D),
  RA_EVICT_FEATURES_LIST(_FEATURE_IDX) FeatureCount,
  RA_FIRST_EXTRA_FEATURE(_FEATURE_IDX_SIMPLE) = FeatureCount,
  RA_REST_EXTRA_FEATURES(_FEATURE_IDX)
      FeaturesWithDevelopmentCount
#undef _FEATURE_IDX
};
286

Initialize things that don't have default ctors easy to do at def, and avoids nondeterministic bugs. Like Pos, at minimum, set it to 0.

288

add a comment as to what Pos is - it's the index of the column corresponding to the physical register of the live interval segment captured by this LRStartEndInfo, right? (or the candidate)

also a comment for LRStartEndInfo overall

999

This feels like it'd benefit from a unittest. The core logic is about intervals that cover instruction opcodes, so the only LLVM-ness of it is in LIS->getInstructionFromIndex(CurrentIndex) (because LIS->getSlotIndexes()->getLastIndex()) is basically a constant you can pass in)

You can test it by making a small change: make this into a utility that takes LRPosInfo and a std::function (or a llvm::function_ref, whatever) that gives the opcode for a SlotIndex. The utility doesn't need to know about mlevictadvisor or anything - it's just dealing with intervals. You can also pass a Runner in, and in the test case, just use the NoInferenceModelRunner.

So then you can set up all sorts of interesting interval overlapping cases, and you can just populate your opcodes with incrementing numbers or something.

The nice thing is that the unittest doesn't need any #define specific stuff - it's generic.

The rest can stay the same - meaning, let MLEvictAdvisor::extractInstructionFeatures call that utility, etc.

1004

(nit - it took me a few reads to get it) "A vector of size "max instruction count". It contains the instruction opcodes of instructions covered by all intervals in LRPosInfo"

wdyt?

1013

This is rather the Instruction "Index" or something like that, right? Count to me means total.

1014

Nit: CurrentSegmentIdx

1020

typo: process"ed"

1043

you don't need the -1 thing here if you split the extra list in 2

1058

the exit condition could include LRPosInfo[OverlapCheckCurrentSegment].Begin > CurrentIndex, for more clarity?

1068

can't LRPosInfo[OverlapCheckCurrentSegment].End < CurrentIndex? So we know the CurrentIndex is below Begin, but it could also be below this segment's end?

Current instruction: 5
CurrentSegment: [1,7)
NextSegment: [2,4)
NextNextSegment: [2, 8)

1084

you just need to go to the next segment and potentially set CurrentIndex to that one's beginning if it's after CurrentIndex (simpler code)

aidengrossman marked 10 inline comments as done.Sep 13 2022, 1:26 AM
aidengrossman added inline comments.
llvm/lib/CodeGen/MLRegallocEvictAdvisor.cpp
286

That's a good point. Done for Pos. The SlotIndex class has a default constructor creating an invalid index, so we should be good there.

288

Added a comment for the entirety of LRStartEndInfo which also covers the meaning of the Pos member.

aidengrossman marked 2 inline comments as done.

Address some of the inline comments (still a couple more to get to).

aidengrossman marked 4 inline comments as done.

Addressed more inline comments. Still some to go.

llvm/lib/CodeGen/MLRegallocEvictAdvisor.cpp
1068

LRPosInfo[OverlapCheckCurrentSegment].End can be less than CurrentIndex, but it shouldn't be missing any instructions. It's not checking if CurrentIndex is below begin, but rather if CurrentIndex is above the beginning of the current segment, because if the beginning of the current segment being checked is greater than the current index under analysis, it is guaranteed that the segment currently being processed as well as all future segments don't contain the currently being processed index due to the segments being sorted in ascending order by beginning index.

aidengrossman added inline comments.Sep 15 2022, 4:18 PM
llvm/lib/CodeGen/MLRegallocEvictAdvisor.cpp
1068

Nevermind my previous comment. Not sure what I was thinking there. This was an actual issue and I ended up catching it while looking through some unit test cases. Should be fixed on the next push as I added in a condition to only set the relevant element of the instructions_mapping matrix if CurrentIndex <= LRPosInfo[OverlapCheckCurrentSegment].End.

Refactor for unit tests, add unit tests, and modify main feature extraction code
to fix some edge cases found through unit testing.

Removed conditional compilation for the feature extraction for the in
development features and moved size constants to MLRegallocEvictAdvisor.h to
allow for the constants to be used during unit testing.

mtrofin added inline comments.Sep 16 2022, 4:24 PM
llvm/include/llvm/CodeGen/SlotIndexes.h
148 ↗(On Diff #460937)

(just noticed this) can you avoid this, because it's just for test, and instead just replace the SlotIndex in your collection?

aidengrossman added inline comments.Sep 16 2022, 4:29 PM
llvm/include/llvm/CodeGen/SlotIndexes.h
148 ↗(On Diff #460937)

This is for instantiation of each SlotIndex within the list. I would like to avoid it if possible too, but in order to setup the test case the SlotIndex needs to have a valid IndexListEntry* pointer, and there is no publicly exposed constructor that allows setting that, so I'm calling the default constructor and setting the pointer with this function. So it doesn't seem like there's a super practical way to avoid this. Unless there's some easy way to avoid this that I'm just not seeing?

mtrofin added inline comments.Sep 16 2022, 5:03 PM
llvm/include/llvm/CodeGen/SlotIndexes.h
148 ↗(On Diff #460937)

Ugh... I'd rather the ctor be public - that way, the state management of a SlotIndex stays the same (once created, it doesn't change its lie - easier to understand / maintain)

or (my initial preference) introduce an abstraction around the slot index stuff. IIRC there isn't that much you actually need from that API.

Changed test setup to use SlotIndex constructor instead of setting the
ListIndexEntry pointer directly by getting rid of the pointer setter
and making the constructor public with a comment nothing that the
constructor isn't for general public consumption.

Fixed conditional compilation for dev features so that the default case
doesn't break.

mtrofin accepted this revision.Sep 17 2022, 9:27 AM
This revision is now accepted and ready to land.Sep 17 2022, 9:27 AM
This revision was landed with ongoing or failed builds.Sep 17 2022, 12:55 PM
This revision was automatically updated to reflect the committed changes.
lkail added a subscriber: lkail.Sep 18 2022, 6:03 AM