[LSR] Canonicalize a formula before insert it into the list

[mdchen]

Summary

In GenerateConstantOffsetsImpl, we may generate non canonical
Formula if BaseRegs of that Formula is updated and includes a
recurrent expr reg related with current loop while its ScaledReg
is not.

Bugzilla: https://bugs.llvm.org/show_bug.cgi?id=47329

[lebedev.ri]

Tests missing

[mdchen]

add a test case

[qcolombet]

LGTM, nitpicks below.

llvm/test/Transforms/LoopStrengthReduce/AArch64/pr47329.ll

1 ↗

(On Diff #289433)

Could you add a check that we generate something sensible?
(Not crashing is not a good enough check :))

22 ↗

(On Diff #289433)

Please get rid of the implicit variables (%[0-9]+). (You can use opt -instnamer for that.)

[mdchen]

llvm/test/Transforms/LoopStrengthReduce/AArch64/pr47329.ll

1 ↗

(On Diff #289433)

I agree it's not good enough. However, the IR generated with assertions turned off is no difference with the one generated with this fix patch and I can't come up with reasonable checks here. I'd appreciate it if you can give some guidance :)

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

void LSRInstance::GenerateConstantOffsetsImpl(
   if (G->isZero() || Imm == 0)
     return;
   Formula F = Base;
   F.BaseOffset = (uint64_t)F.BaseOffset + Imm;
   if (!isLegalUse(TTI, LU.MinOffset, LU.MaxOffset, LU.Kind, LU.AccessTy, F))
     return;
   if (IsScaledReg)
     F.ScaledReg = G;
-  else
+  else {
     F.BaseRegs[Idx] = G;
+    // We may generate non canonical Formula if G is a recurrent expr reg
+    // related with current loop while F.ScaledReg is not.
+    F.canonicalize(*L);
+  }
   (void)InsertFormula(LU, LUIdx, F);
 }
 
 /// GenerateConstantOffsets - Generate reuse formulae using symbolic offsets.
 void LSRInstance::GenerateConstantOffsets(LSRUse &LU, unsigned LUIdx,
                                           Formula Base) {
   // TODO: For now, just add the min and max offset, because it usually isn't
   // worthwhile looking at everything inbetween.