Differentiate array access at IR level

Hi LLVM community,

I am trying to differentiate access to different array elements, for example:

for (int i = 1; i < 10; i++) {

a[i] = a[i] + 10;

b[i] = a[i - 1] * 2;

}

If it is possible to tell it loads/stores 3 different array elements: a[i], b[i] and a[i - 1] at IR level?

Thanks for your time in advance!

Best,
Michael

It sounds like alias analysis can help: https://llvm.org/docs/AliasAnalysis.html

Note that a[i] are a[i-1] are accessing the same memory addresses,
just not in the same loop iteration. You may want to look into
DependenceInfo.

Michael

Hi Michael,

Thanks for your reply!

Since I want to collect the counts of unique array access to array elements in one iteration, so I consider a[i] and a[i - 1] as two accesses to different array elements. Would it be possible to get the notion of “i - 1” at IR level.

The IR looks like:

%11 = load float*, float** %a.addr, align 8, !dbg !954
%12 = load i32, i32* %i, align 4, !dbg !955
%sub = sub nsw i32 %12, 1, !dbg !956

%idxprom7 = sext i32 %sub to i64, !dbg !954

%arrayidx8 = getelementptr inbounds float, float* %11, i64 %idxprom7, !dbg !954

Working the the source level might be easier, but I wonder if it is possible to know idxprom7 → i - 1 with IR

Thanks again!
Michael

Hi Michael,

You should run mem2reg on your code, e.g. use the "create_ll.sh" script
in `polly/test/create_ll.sh` to transform little C files to '.ll' files.

The solution I would go for looks something like this, assuming this is
in a pass in which LoopInfo is available as LI and ScalarEvolution as SE.

  DenseMap<std::pair<Loop *, const SCEV *>, unsigned> Reads, Writes;

  void dealWithLoopAndSubLoops(Loop &L) {
    for (BasicBlock *BB : L.blocks()) {
      for (Instruction &I : *BB) {
        if (LoadInst *Load = dyn_cast<LoadInst>(&I)) {
          Reads[{&L, SE->getSCEVAtScope(Load->getPointerOperand())}] += 1
        } else if (StoreInst *Store = dyn_cast<StoreInst>(&I)) {
          Writes[{&L, SE->getSCEVAtScope(Store->getPointerOperand())}] += 1
        }
      }
    }
    for (Loop *SubL : L)
      dealWithLoopAndSubLoops(*SubL);
  }

  void run(...) {
    for (Loop *L : *LI)
      dealWithLoopAndSubLoops(*L);

    errs() << "Reads:\n";
    for (auto &It : Reads) {
      errs() << " - Location: " << *It.first.second << " Loop: " <<
      It.first.first->getName() << " Access count: " << It.second << "\n";
    }
    errs() << "Writes:\n";
    for (auto &It : Writes) {
      errs() << " - Location: " << *It.first.second << " Loop: " <<
      It.first.first->getName() << " Access count: " << It.second << "\n";
    }
  }

Note that this is not tested in any way.

Hope this helps.

Cheers,
  Johannes