[GlobalISel] LegalizerInfo: Enable legalization of non-power-of-2 types

[volkan]

Summary

Legalize only if the type is marked as Legal or Custom. If not, return Unsupported as LegalizerHelper is not able to handle non-power-of-2 types right now.

[kristof.beyls]

lib/CodeGen/GlobalISel/LegalizerInfo.cpp

75–76

I was confused by the summary on this patch - I thought you wanted to make sure vector types like <3 x s32> definitely wouldn't be legalized and thought the existing code could sometimes legalize them. It then started doing the following train-of-thought:
"""
For vector types, getSizeInBits() returns the "number of elements" times "element size in bits".
That result can only be a power of 2 if both "number of elements" and "element size in bits" are both a power of 2.
So, the effect of this change would be to allow more vector data types, like <3 x s32> to be legalized."

So, in summary, by the time this gets committed, I think the commit message must be clearer, and e.g. state "Enable legalization of vector types with non-power-of-2 number of elements".

This patch clearly is missing tests.

[volkan]

lib/CodeGen/GlobalISel/LegalizerInfo.cpp

75–76

I was confused by the summary on this patch - I thought you wanted to make sure vector types like <3 x s32> definitely wouldn't be legalized and thought the existing code could sometimes legalize them. It then started doing the following train-of-thought:
"""
For vector types, getSizeInBits() returns the "number of elements" times "element size in bits".
That result can only be a power of 2 if both "number of elements" and "element size in bits" are both a power of 2.
So, the effect of this change would be to allow more vector data types, like <3 x s32> to be legalized."

So, in summary, by the time this gets committed, I think the commit message must be clearer, and e.g. state "Enable legalization of vector types with non-power-of-2 number of elements".

Yes, it seems I mixed the intent and the patch. I'll update the title.

This patch clearly is missing tests.

I didn’t add a test case because there wasn't any legal operations on vector types with non-power-of-2 number of elements, but I just realized I can use G_MERGE_VALUES.

Thank you,
Volkan

[volkan]

Added a test.

[kristof.beyls]

lib/CodeGen/GlobalISel/LegalizerInfo.cpp

75–76

Thanks for those changes.

I'm wondering now if we shouldn't just completely drop the following:

if (!isPowerOf2_64(SizeInBits))
  return std::make_pair(Unsupported, LLT());

and just let the fall-back mechanism catch the many/all cases where non-power-of-2-sized types aren't supported.
Removing that if statement alltogether makes it a bit easier to also work towards legalizing non-power-of-2 scalar types.
IIRC, Tim introduced this, so I guess he has the best view on the tradeoffs here.

@t.p.northover : Do you have any thoughts on this?

[ab]

LGTM after removing the whole check and adding a good explanation in the commit message.

Can you add a simple vector test in test/CodeGen/AArch64/GlobalISel/arm64-fallback.ll? It already has a scalar test (that shows the change is OK if it continues reporting a fallback)

lib/CodeGen/GlobalISel/LegalizerInfo.cpp

75–76

I agree, we should probably drop the check completely.

I think it was more of a defensive way to avoid even considering non-power-of-2 types elsewhere. But looking around, it seems we're robust enough to fail legalization properly, so it's fine to do that.

[volkan]

lib/CodeGen/GlobalISel/LegalizerInfo.cpp

75–76

I think we can’t drop the check right now because LegalizerHelper is not able to handle these cases. If we remove the check, LegalizerInfo is going to try to find a legal type for non-power-of-2 types and the compiler may hit the assertions in LLT::halfScalarSize() or LLT::halfElements() as they don’t expect a non-power-of-2 type.

Instead, we can just check if a non-power-of-2 type is marked as Legal or Custom and return Unsupported if not. What do you think?

[volkan]

• Updated the patch per my previous comment.
• Added a vector fallback test.

[kristof.beyls]

lib/CodeGen/GlobalISel/LegalizerInfo.cpp

75–76

Right - I forgot about the doubling/halving behaviour of LegalizerHelper right now.
TBH, I think the way forward is to get more reviews going on https://reviews.llvm.org/D30529, which makes the other parts of the legalizer handle non-power-of-2 types.
If you need to have support urgently for 3-element vector types, I'd be fine with this going in, but as stated above, I think helping towards making D30529 reach a committable state is probably the most constructive way forward.
I this goes in, I think it would be good to add a FIXME here explaining this is a temporary hack until general non-power-of-2 legalization works.

[volkan]

lib/CodeGen/GlobalISel/LegalizerInfo.cpp

75–76

I plan to push this because it is going to add more vector support and it’s not possible to add a fallback test if we drop the check.

I’ll add a comment explaining this is temporary.

Thanks,
Volkan

[volkan]

• Updated the comment.

lib/CodeGen/GlobalISel/LegalizerInfo.cpp

 // probably going to need specialized lookup structures for various types before
 // we have any hope of doing well with something like <13 x i3>. Even the common
 // cases should do better than what we have now.
 std::pair<LegalizerInfo::LegalizeAction, LLT>
 LegalizerInfo::getAction(const InstrAspect &Aspect) const {
   assert(TablesInitialized && "backend forgot to call computeTables");
   // These *have* to be implemented for now, they're the fundamental basis of
   // how everything else is transformed.
 
-  // Nothing is going to go well with types that aren't a power of 2 yet, so
-  // don't even try because we might make things worse.
-  if (!isPowerOf2_64(Aspect.Type.getSizeInBits()))
-      return std::make_pair(Unsupported, LLT());
-
   // FIXME: the long-term plan calls for expansion in terms of load/store (if
   // they're not legal).
   if (Aspect.Opcode == TargetOpcode::G_SEQUENCE ||
       Aspect.Opcode == TargetOpcode::G_EXTRACT ||
       Aspect.Opcode == TargetOpcode::G_MERGE_VALUES ||
       Aspect.Opcode == TargetOpcode::G_UNMERGE_VALUES)
     return std::make_pair(Legal, Aspect.Type);
 
+  LLT Ty = Aspect.Type;
   LegalizeAction Action = findInActions(Aspect);
+  // LegalizerHelper is not able to handle non-power-of-2 types right now, so do
+  // not try to legalize them unless they are marked as Legal or Custom.
+  if (!isPowerOf2_64(Ty.getSizeInBits()) &&
+      !(Action == Legal || Action == Custom))
+    return std::make_pair(Unsupported, LLT());
+
   if (Action != NotFound)
     return findLegalAction(Aspect, Action);
 
   unsigned Opcode = Aspect.Opcode;
-  LLT Ty = Aspect.Type;
   if (!Ty.isVector()) {
     auto DefaultAction = DefaultActions.find(Aspect.Opcode);
     if (DefaultAction != DefaultActions.end() && DefaultAction->second == Legal)
       return std::make_pair(Legal, Ty);
 
     if (DefaultAction != DefaultActions.end() && DefaultAction->second == Lower)
       return std::make_pair(Lower, Ty);
 

test/CodeGen/AArch64/GlobalISel/arm64-fallback.ll

 ; FALLBACK-WITH-REPORT-ERR: remark: <unknown>:0:0: unable to legalize instruction: %vreg1<def>(s42) = G_LOAD %vreg0; mem:LD6[%addr](align=8) (in function: odd_type)
 ; FALLBACK-WITH-REPORT-ERR: warning: Instruction selection used fallback path for odd_type
 ; FALLBACK-WITH-REPORT-OUT-LABEL: odd_type:
 define void @odd_type(i42* %addr) {
   %val42 = load i42, i42* %addr
   ret void
 }
 
+; FALLBACK-WITH-REPORT-ERR: remark: <unknown>:0:0: unable to legalize instruction: %vreg1<def>(<7 x s32>) = G_LOAD %vreg0; mem:LD28[%addr](align=32) (in function: odd_vector)
+; FALLBACK-WITH-REPORT-ERR: warning: Instruction selection used fallback path for odd_vector
+; FALLBACK-WITH-REPORT-OUT-LABEL: odd_vector:
+define void @odd_vector(<7 x i32>* %addr) {
+  %vec = load <7 x i32>, <7 x i32>* %addr
+  ret void
+}
+
   ; RegBankSelect crashed when given invalid mappings, and AArch64's
   ; implementation produce valid-but-nonsense mappings for G_SEQUENCE.
 ; FALLBACK-WITH-REPORT-ERR: remark: <unknown>:0:0: unable to map instruction
 ; FALLBACK-WITH-REPORT-ERR: warning: Instruction selection used fallback path for sequence_mapping
 ; FALLBACK-WITH-REPORT-OUT-LABEL: sequence_mapping:
 define void @sequence_mapping([2 x i64] %in) {
   ret void
 }

test/CodeGen/AArch64/GlobalISel/legalize-nonpowerof2eltsvec.mir

+# RUN: llc -O0 -run-pass=legalizer -global-isel %s -o - | FileCheck %s
+
+--- |
+  target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+  target triple = "aarch64--"
+  define void @test_legalize_merge_v3s32() {
+    ret void
+  }
+...
+---
+name:            test_legalize_merge_v3s32
+registers:
+  - { id: 0, class: _ }
+  - { id: 1, class: _ }
+  - { id: 2, class: _ }
+  - { id: 3, class: _ }
+body: |
+  bb.0:
+    liveins: %w0, %w1, %w2
+    ; CHECK-LABEL: name: test_legalize_merge_v3s32
+    ; CHECK: [[ARG1:%[0-9]+]](s32) = COPY %w0
+    ; CHECK: [[ARG2:%[0-9]+]](s32) = COPY %w1
+    ; CHECK: [[ARG3:%[0-9]+]](s32) = COPY %w2
+    ; CHECK: (<3 x s32>) = G_MERGE_VALUES [[ARG1]](s32), [[ARG2]](s32), [[ARG3]](s32)
+    %0(s32) = COPY %w0
+    %1(s32) = COPY %w1
+    %2(s32) = COPY %w2
+    %3(<3 x s32>) = G_MERGE_VALUES %0(s32), %1(s32), %2(s32)
+...