[TableGen] Make OpcodeMappings sort comparator strict weak ordering compliant

[danlark]

Summary

This did not satisfy equivalence of transitivity. There was an attempt
to fix it in https://reviews.llvm.org/D58687 but it was not fully
correct. Masks might not be equivalent but be equal according to LessThan lambda

I don't have commit rights. Danila Kutenin [e-mail]

[danlark]

Ping

[andrewng]

Sorry, but I'm quite busy right now and I haven't had a chance to look into this in detail. At a glance, I believe that the code here is OK because LessThan is always used after inequality has already been established. However, I agree that LessThan itself is not a "complete" < operator but I don't think it needs to be in this use case.

[danlark]

Friendly ping

[aeubanks]

I'm also not seeing where the issue is with the current code

[danlark]

In D157955#4625396, @aeubanks wrote:

I'm also not seeing where the issue is with the current code

Comparator checks that if (LhsMasks.first != RhsMasks.first) and then compares by popcount and left bit. We can construct an example where transitivity of equivalence is broken, for example different masks with the same popcount and left bit

a = (1010, 0000)
b = (0110, 1010)
c = (1010, 1111)

a < b is false, b < a is false (left bit counts from the right)
b < c is false, c < b is false

But a < c because .first are equal and popcount of .second of c is bigger

[asbirlea]

I thought the zero count is from the most significant bit but I may be wrong. In any case, your point is valid. I see how you can construct an example where the .first fields are not equal, but then the popcount and countl_zero are both equal, leading to a "false" on the LessThan call for both (a,b) and (b,a) comparison.
The change proposed here does provide an absolute ordering so it resolves the issue you found and it's reasonable to go with it. I'm not sure it's the "desired" one (or if it even matters). It will rely more often on the Idx default, than on the two comparisons, and perhaps that's ok.
A more classical comparison would be for LessThan to provide a full <; so comparing on the .first for equivalency, but then determining the follow up on conditions which defines a strict ordering (e.g. bitsToDouble()?).

I would appreciate a code owner chiming in on whether there's a preferred resolution.

[aeubanks]

ah I see, lgtm

[danlark]

In D157955#4626217, @aeubanks wrote:

ah I see, lgtm

Thanks, please, submit on my behalf

llvm/utils/TableGen/CodeGenSchedule.cpp

processSTIPredicate(STIPredicateFunction &Fn,
   // As a last resort, order elements by opcode identifier.
   llvm::sort(OpcodeMappings,
              [&](const OpcodeMapPair &Lhs, const OpcodeMapPair &Rhs) {
                unsigned LhsIdx = Opcode2Index[Lhs.first];
                unsigned RhsIdx = Opcode2Index[Rhs.first];
                const std::pair<APInt, APInt> &LhsMasks = OpcodeMasks[LhsIdx];
                const std::pair<APInt, APInt> &RhsMasks = OpcodeMasks[RhsIdx];
 
-               auto LessThan = [](const APInt &Lhs, const APInt &Rhs) {
-                 unsigned LhsCountPopulation = Lhs.popcount();
-                 unsigned RhsCountPopulation = Rhs.popcount();
-                 return ((LhsCountPopulation < RhsCountPopulation) ||
-                         ((LhsCountPopulation == RhsCountPopulation) &&
-                          (Lhs.countl_zero() > Rhs.countl_zero())));
+               auto PopulationCountAndLeftBit =
+                   [](const APInt &Other) -> std::pair<int, int> {
+                 return std::pair<int, int>(Other.popcount(),
+                                            -Other.countl_zero());
                };
-
-               if (LhsMasks.first != RhsMasks.first)
-                 return LessThan(LhsMasks.first, RhsMasks.first);
-
-               if (LhsMasks.second != RhsMasks.second)
-                 return LessThan(LhsMasks.second, RhsMasks.second);
+               auto lhsmask_first = PopulationCountAndLeftBit(LhsMasks.first);
+               auto rhsmask_first = PopulationCountAndLeftBit(RhsMasks.first);
+               if (lhsmask_first != rhsmask_first)
+                 return lhsmask_first < rhsmask_first;
+
+               auto lhsmask_second = PopulationCountAndLeftBit(LhsMasks.second);
+               auto rhsmask_second = PopulationCountAndLeftBit(RhsMasks.second);
+               if (lhsmask_second != rhsmask_second)
+                 return lhsmask_second < rhsmask_second;
 
                return LhsIdx < RhsIdx;
              });
 
   // Now construct opcode groups. Groups are used by the SubtargetEmitter when
   // expanding the body of a STIPredicate function. In particular, each opcode
   // group is expanded into a sequence of labels in a switch statement.
   // It identifies opcodes for which different processors define same predicates