[Polly] Align newly created arrays to the first level cache line boundary

[gareevroman]

Summary

Aligning data to cache lines boundaries helps to avoid overheads related to an access to it ([1]). This patch aligns newly created arrays and adds an option to specify the first level cache line size. By default we use 64 bytes, which is a typical cache-line size ([2]).

In case of Intel Core i7-3820 SandyBridge and the following options,

clang -O3 gemm.c -I utilities/ utilities/polybench.c -DPOLYBENCH_TIME -march=native -mllvm -polly -mllvm -polly-pattern-matching-based-opts=true -DPOLYBENCH_USE_SCALAR_LB -mllvm -polly-target-cache-level-associativity=8,8 -mllvm -polly-target-cache-level-sizes=32768,262144 -mllvm -polly-target-latency-vector-fma=8

it helps to improve the performance from 11.303 GFlops/sec (39,247% of theoretical peak) to 12.63 GFlops/sec (43,8542% of theoretical peak).

Refs.:

[1] - http://www.alexonlinux.com/aligned-vs-unaligned-memory-access
[2] - http://igoro.com/archive/gallery-of-processor-cache-effects/

[grosser]

LGTM, could you add the theoretical performance into the commit message as well?

[gareevroman]

Update according to the comments.

[grosser]

Hi Roman,

any plans to commit this?

[gareevroman]

Hi Roman,

any plans to commit this?

Hi Tobias,

this was committed in r290253.

[etherzhhb]

Interesting, maybe we need to get this from TargetTransformInfo eventually, because I saw a similar global variable/option in LoadStoreVectorizer as well.

[gareevroman]

Hi Hongbin,

thanks for the comment!

In D28020#650943, @etherzhhb wrote:

Interesting, maybe we need to get this from TargetTransformInfo eventually, because I saw a similar global variable/option in LoadStoreVectorizer as well.

Right. We decided not to do it now, because it would probably require passing of a TargetTransformInfo object to IslNodeBuilder. It seems that such an object wouldn't be useful for anything else at the moment. Furthermore, in case of some platforms (e.g. Intel Core i7-3820 SandyBridge), it reports that the cache line size is equal to zero.

lib/CodeGen/IslNodeBuilder.cpp

 // memory accesses. Without this option set we regenerate expressions using the
 // original SCEV expressions and only generate new expressions in case the
 // access relation has been changed and consequently must be regenerated.
 static cl::opt<bool> PollyGenerateExpressions(
     "polly-codegen-generate-expressions",
     cl::desc("Generate AST expressions for unmodified and modified accesses"),
     cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
 
+static cl::opt<int> PollyTargetFirstLevelCacheLineSize(
+    "polly-target-first-level-cache-line-size",
+    cl::desc("The size of the first level cache line size specified in bytes."),
+    cl::Hidden, cl::init(64), cl::ZeroOrMore, cl::cat(PollyCategory));
+
 __isl_give isl_ast_expr *
 IslNodeBuilder::getUpperBound(__isl_keep isl_ast_node *For,
                               ICmpInst::Predicate &Predicate) {
   isl_id *UBID, *IteratorID;
   isl_ast_expr *Cond, *Iterator, *UB, *Arg0;
   isl_ast_op_type Type;
 
   Cond = isl_ast_node_for_get_cond(For);
for (int i = SAI->getNumberOfDimensions() - 1; i >= 0; i--) {
       if (!NewArrayType)
         NewArrayType = SAI->getElementType();
 
       NewArrayType = ArrayType::get(NewArrayType, UnsignedDimSize);
     }
 
     auto InstIt =
         Builder.GetInsertBlock()->getParent()->getEntryBlock().getTerminator();
-    Value *CreatedArray =
-        new AllocaInst(NewArrayType, SAI->getName(), &*InstIt);
+    auto *CreatedArray = new AllocaInst(NewArrayType, SAI->getName(), &*InstIt);
+    CreatedArray->setAlignment(PollyTargetFirstLevelCacheLineSize);
     SAI->setBasePtr(CreatedArray);
   }
 }
 
 bool IslNodeBuilder::preloadInvariantLoads() {
 
   auto &InvariantEquivClasses = S.getInvariantAccesses();
   if (InvariantEquivClasses.empty())