Remove Vectorization Barriers and Use Compiler Hints

Topic Overview

Help the Compiler SIMD

Auto-vectorization needs provably independent iterations, aligned pointers, and no function calls in the inner loop. #pragma GCC ivdep, clang loop vectorize(enable), and OpenMP simd directives remove assumed dependencies the compiler cannot prove.

Vectorizable Loop Shape

Simple counting loop, no backward dependencies, stride-one access on arrays.

cCopy
Loading…

• -fopt-info-vec prints why vectorization failed
• __attribute__((aligned(32))) helps AVX loads
• restrict plus ivdep often unlocks SIMD together
• Compare scalar vs vector assembly with objdump -d -Mintel

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will add pragma or attribute hints to vectorize a loop and verify SIMD instructions in assembly. This exercise asks you to report speedup and name the SIMD width used.

Document one invariant you will assert in tests and how you would detect its violation from observable symptoms.

Your Task

Why did the compiler refuse to vectorise your loop? Write a small vectoriser legality checker, like the reasoning behind -fopt-info-vec-missed. It reads simple loops over index i, finds the barriers (calls, scatters, float reductions, loop-carried dependences, possible aliasing), and reports either why the loop cannot be vectorised or what vector code would result. Hints such as restrict, fast-math and omp-simd remove specific barriers, exactly as they do in GCC and Clang.

Input

cCopy
Loading…

An index is i, i+c, i-c, k*i, k*i+c or c (affine), or ARRAY[...] (indirect). name(...) in an expression is a function call. Data is float unless the int hint is given.

Rules, checked in this order

1. An unparsable statement (no =, a bad index, or a plain SCALAR = ...) gives cannot analyse: unsupported statement.
2. A function call gives not vectorized: call to NAME() (declare it simd, or use omp-simd), for the first call seen.
3. A store through an indirect index gives not vectorized: indirect store may write one element twice in a vector.
4. SCALAR += ... on float data gives not vectorized: floating-point reduction into S needs fast-math or omp-simd (reassociation).
5. For every written access and every other access to the same array: if either is not unit-stride affine, report not vectorized: unknown dependence on A (non-unit stride or indirect index). Otherwise let d = write offset - other offset, and keep the smallest positive d. Accesses to different arrays need a runtime alias check unless the restrict hint is given.
6. If 0 < d < W:
   • with omp-simd, warn and keep W;
   • if d = 1, the loop is not vectorized;
   • otherwise use the largest power of two <= d as the width.

The hints lift specific rules. omp-simd asserts safety: it skips rules 2, 3 and 4 and the "unknown dependence" check, and it removes the runtime alias check. fast-math or int lift rule 4. restrict removes the runtime alias check.

Output

cCopy
Loading…

The notes come in this order: alias check, masking (the loop has an if), the first strided access, the first indirect load, and the reduction. loop NAME: trip count must be positive and width: power of two, 2..64 are the input errors.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Parse every array access into (array, kind, coefficient, offset), and base all decisions on that table.
2. Treat a dependence of distance d >= W as harmless. The vector loads happen before any store that could affect them.

Hidden tests cover integer reductions, masked conditional loops, strided and gather loads, distance-2 and distance-8 dependences, anti-dependences (a[i] = a[i+1]), omp-simd overriding calls and dependences, several statements in one loop, and malformed statements.