This is an archive of the discontinued LLVM Phabricator instance.

[IndVarSimplify] Transform the trip count into a simpler form
Needs RevisionPublic

Authored by TiehuZhang on Feb 15 2023, 3:45 AM.

Details

Summary

LoopVectorizer will create a loop guard based on the SCEV expression of ExitCount, and complex ExitCount will introduce redundant instructions. This patch simplifies the ExitCount by offsetting the trip count and induction variable so that there will be fewer redundant conditions after vectorization, e.g., llvm.smax.i64 as shown in test.

Before the optimization

int initial = 0;
for(int i = 0; i < nOut; i++) {
  double temp_value = 0.0;
  for (int j = initial; j < initial + nIn; j++) {
    temp_value += values[j] * x[idx[j]];
  }
  initial += nIn;
  b[i] = temp_value;
}

After the optimization

int initial = 0;
for(int i = 0; i < nOut; i++) {
  double temp_value = 0.0;
  for (int k = 0; k < nIn; k++) {
    temp_value += values[k + initial] * x[idx[k + initial]];
  }
  initial += nIn;
  b[i] = temp_value;
}

Diff Detail

Event Timeline

TiehuZhang created this revision.Feb 15 2023, 3:45 AM
TiehuZhang requested review of this revision.Feb 15 2023, 3:45 AM
TiehuZhang retitled this revision from [IndVarSimplify] Transform the trip count to a simpler form to [IndVarSimplify] Transform the trip count into a simpler form.Feb 15 2023, 3:48 AM
mkazantsev requested changes to this revision.EditedFeb 19 2023, 11:08 PM
  1. I think it should be moved to existing utils and re-implemented using SCEVs rather than values. Most of prerequisite logic here looks duplicating the existing code.
  2. Can you please provide a motivating test here? It should be a test that only runs passes=indvars or something like it. These tests with -O3 are too cryptic to understand what you are trying to achieve.
llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
2045

L->isInnermost()

2049

If so, the check above is redundant. Write a TODO to lift it? It practically happens very rarely.

2086

We already have this available in functions like SimplifyIndvar::simplifyUsers. It seems that you are replicating a lot of existing code. Did you try to integrate what you are doing into SimplifyIndVars.cpp?

This revision now requires changes to proceed.Feb 19 2023, 11:08 PM