[IndVars] Teach replaceCongruentIVs to avoid scrambling induction variables

[efriedma]

Summary

replaceCongruentIVs analysis is based on ScalarEvolution; this makes comparing different PHIs and performing the replacement straightforward. However, it can have some side-effects: it isn't aware whether an induction variable is in canonical form, so it can perform replacements which obscure the meaning of the IR.

In test22 in widen-loop-comp.ll, the resulting loop can't be analyzed by ScalarEvolution at all.

My attempted solution is to restrict the transform: don't try to replace induction variables using PHI nodes that don't represent simple induction variables.

I'm not sure if this is the best solution; suggestions welcome.

[efriedma]

Ping

[fhahn]

However, it can have some side-effects: it isn't aware whether an induction variable is in canonical form, so it can perform replacements which obscure the meaning of the IR.

Agreed, it seems like the restriction should keep loops more analyzable throughout the pipeline. Aggressively removing phis would probably make more sense late in the pipeline/the backend, if it turns out to be needed.

LGTM, but please wait a day or so with committing in case there are additional opinions.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

2074

Could you add a comment with an explanation why this is restricted here?

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

for (PHINode *Phi : Phis) {
     if (!SE.isSCEVable(Phi->getType()))
       continue;
 
     PHINode *&OrigPhiRef = ExprToIVMap[SE.getSCEV(Phi)];
     if (!OrigPhiRef) {
       OrigPhiRef = Phi;
       if (Phi->getType()->isIntegerTy() && TTI &&
           TTI->isTruncateFree(Phi->getType(), Phis.back()->getType())) {
+        const SCEV *PhiExpr = SE.getSCEV(Phi);
+        if (isa<SCEVAddRecExpr>(PhiExpr)) {
           // This phi can be freely truncated to the narrowest phi type. Map the
           // truncated expression to it so it will be reused for narrow types.
           const SCEV *TruncExpr =
-          SE.getTruncateExpr(SE.getSCEV(Phi), Phis.back()->getType());
+            SE.getTruncateExpr(PhiExpr, Phis.back()->getType());
           ExprToIVMap[TruncExpr] = Phi;
         }
+      }
       continue;
     }
 
     // Replacing a pointer phi with an integer phi or vice-versa doesn't make
     // sense.
     if (OrigPhiRef->getType()->isPointerTy() != Phi->getType()->isPointerTy())
       continue;
 

llvm/test/Transforms/IndVarSimplify/AArch64/widen-loop-comp.ll

 }
 
 define void @test22(i16* %ptr) {
 ; CHECK-LABEL: @test22(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    store i16 0, i16* [[PTR:%.*]], align 4
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[INDVARS:%.*]] = trunc i32 [[IV]] to i16
-; CHECK-NEXT:    [[VAL_INC:%.*]] = add i16 [[INDVARS]], 1
+; CHECK-NEXT:    [[VAL:%.*]] = phi i16 [ [[VAL_INC:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY]] ]
+; CHECK-NEXT:    [[VAL_INC]] = add i16 [[VAL]], 1
 ; CHECK-NEXT:    store i16 [[VAL_INC]], i16* [[PTR]], align 4
 ; CHECK-NEXT:    [[IV_WIDE:%.*]] = zext i32 [[IV]] to i64
 ; CHECK-NEXT:    call void @foo(i64 [[IV_WIDE]])
 ; CHECK-NEXT:    [[IV_NEXT]] = zext i16 [[VAL_INC]] to i32
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp eq i32 [[IV]], 1000
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void