GCC: Vektorisierungsunterschied zwischen zwei ähnlichen Schleifen

Beim Kompilieren mit gcc -O3warum vektorisiert die folgende Schleife nicht (automatisch):

#define SIZE (65536)

int a[SIZE], b[SIZE], c[SIZE];

int foo () {
  int i, j;

  for (i=0; i<SIZE; i++){
    for (j=i; j<SIZE; j++) {
      a[i] = b[i] > c[j] ? b[i] : c[j];
    }
  }
  return a[0];
}

wenn das folgende tut?

#define SIZE (65536)

int a[SIZE], b[SIZE], c[SIZE];

int foov () {
  int i, j;

  for (i=0; i<SIZE; i++){
    for (j=i; j<SIZE; j++) {
      a[i] += b[i] > c[j] ? b[i] : c[j];
    }
  }
  return a[0];
}

Der einzige Unterschied besteht darin, ob das Ergebnis des Ausdrucks in der inneren Schleife liegt zugeordnet zu a[i]oder zu a hinzugefügt[i].

Als Referenz -ftree-vectorizer-verbose=6 ergibt die folgende Ausgabe für die erste (nicht vektorisierende) Schleife.

v.c:8: note: not vectorized: inner-loop count not invariant.
v.c:9: note: Unknown alignment for access: c
v.c:9: note: Alignment of access forced using peeling.
v.c:9: note: not vectorized: live stmt not supported: D.2700_5 = c[j_20];

v.c:5: note: vectorized 0 loops in function.

Und die gleiche Ausgabe für die Schleife, die vektorisiert, ist:

v.c:8: note: not vectorized: inner-loop count not invariant.
v.c:9: note: Unknown alignment for access: c
v.c:9: note: Alignment of access forced using peeling.
v.c:9: note: vect_model_load_cost: aligned.
v.c:9: note: vect_model_load_cost: inside_cost = 1, outside_cost = 0 .
v.c:9: note: vect_model_simple_cost: inside_cost = 1, outside_cost = 1 .
v.c:9: note: vect_model_reduction_cost: inside_cost = 1, outside_cost = 6 .
v.c:9: note: cost model: prologue peel iters set to vf/2.
v.c:9: note: cost model: epilogue peel iters set to vf/2 because peeling for alignment is unknown .
v.c:9: note: Cost model analysis:
  Vector inside of loop cost: 3
  Vector outside of loop cost: 27
  Scalar iteration cost: 3
  Scalar outside cost: 7
  prologue iterations: 2
  epilogue iterations: 2
  Calculated minimum iters for profitability: 8

v.c:9: note:   Profitability threshold = 7

v.c:9: note: Profitability threshold is 7 loop iterations.
v.c:9: note: LOOP VECTORIZED.
v.c:5: note: vectorized 1 loops in function.

Im ersten Fall: Der Code überschreibt denselben Speicherplatz a[i] in jeder Iteration. Dies sequenziert die Schleife von Natur aus, da die Schleifeniterationen nicht unabhängig sind.
(In Wirklichkeit wird nur die letzte Iteration benötigt. Daher könnte die gesamte innere Schleife herausgenommen werden.)

Im zweiten Fall: GCC erkennt die Schleife als Reduktionsoperation – für die es eine Sonderfallbehandlung zum Vektorisieren hat.

Die Compiler-Vektorisierung wird oft als eine Art “Musterabgleich” implementiert. Das heißt, der Compiler analysiert den Code, um zu sehen, ob er zu einem bestimmten Muster passt, das er vektorisieren kann. Wenn ja, wird es vektorisiert. Wenn nicht, dann nicht.

Dies scheint ein Eckfall zu sein, bei dem die erste Schleife zu keinem der vorcodierten Muster passt, die GCC verarbeiten kann. Aber der zweite Fall passt zum Muster der “vektorisierbaren Reduktion”.

Hier ist der relevante Teil des Quellcodes von GCC, der das ausspuckt "not vectorized: live stmt not supported: " Botschaft:

http://svn.open64.net/svnroot/open64/trunk/osprey-gcc-4.2.0/gcc/tree-vect-analyze.c

if (STMT_VINFO_LIVE_P (stmt_info))
{
    ok = vectorizable_reduction (stmt, NULL, NULL);

    if (ok)
        need_to_vectorize = true;
    else
        ok = vectorizable_live_operation (stmt, NULL, NULL);

    if (!ok)
    {
        if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
        {
            fprintf (vect_dump, 
                "not vectorized: live stmt not supported: ");
            print_generic_expr (vect_dump, stmt, TDF_SLIM);
        }
        return false;
    }
}

Aus nur der Zeile:

vectorizable_reduction (stmt, NULL, NULL);

Es ist klar, dass GCC prüft, ob es mit einem “vektorisierbaren Reduktionsmuster” übereinstimmt.

Der GCC-Vektorisierer ist wahrscheinlich nicht schlau genug, um die erste Schleife zu vektorisieren. Der Additionsfall ist einfacher zu vektorisieren, weil a + 0 == a. In Betracht ziehen SIZE==4:

  0 1 2 3 i
0 X
1 X X
2 X X X
3 X X X X
j

X bezeichnet die Kombinationen von i und j Wenn a zugeordnet oder erhöht werden. Für den Fall der Addition können wir die Ergebnisse von berechnen b[i] > c[j] ? b[i] : c[j] denn, sagen wir, j==1 und i==0..4 und setze es in einen Vektor D. Dann brauchen wir nur noch auf Null D[2..3] und füge den resultierenden Vektor hinzu a[0..3]. Bei der Zuordnung ist es etwas kniffliger. Wir müssen nicht nur null D[2..3]sondern auch null A[0..1] und erst dann die Ergebnisse kombinieren. Ich denke, hier versagt der Vektorisierer.

Die erste Schleife ist äquivalent zu

#define SIZE (65536)

int a[SIZE], b[SIZE], c[SIZE];

int foo () {
  int i, j;

  for (i=0; i<SIZE; i++){
    a[i] = b[i] > c[SIZE - 1] ? b[i] : c[SIZE - 1];
  }
  return a[0];
}

Das Problem mit dem ursprünglichen Ausdruck ist, dass er wirklich nicht viel Sinn macht, daher ist es nicht allzu überraschend, dass gcc ihn nicht vektorisieren kann.

Zuerst ändert man einfach a[] viele Male (vorübergehend). Der zweite verwendet den letzten Wert von a[] jedes Mal (nicht vorübergehend).

Bis zu einer Patch-Version konnten Sie “flüchtige” Variablen zum Vektorisieren verwenden.

Verwenden

int * c=malloc(sizeof(int));

um es ausgerichtet zu machen;

v.c:9: note: Unknown alignment for access: c

Zeigt “c” mit einem anderen Speicherbereich als b und a.

Ich nehme “movaps”-ähnliche Anweisungen an, um “vektorisiert” zu werden (aus der SSE-AVX-Anweisungsliste).

Hier: http://gcc.gnu.org/projects/tree-ssa/vectorization.html#using

das 6. und 7. Beispiel zeigen ähnliche Schwierigkeiten.