thr3ads.net - llvm dev - [llvm-dev] Differentiate array access at IR level [Feb 2020]

If this information is useful, please help other people find it:
Share via:

Michael Meng via llvm-dev

2020-Feb-21 03:08 UTC

[llvm-dev] Differentiate array access at IR level

Hello Johannes,

Thanks for your suggestion! The ScalarEvolution analysis is very helpful.

I had a follow-up question. It would be great if you can take a look.

 %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

For the above code, the result for %idxprom7 is: (-1 + (sext i32 %12 to
i64))<nsw>. Just wondering if you have any suggestion that I can replace
(sext i32 %12 to i64) with symbol %i


Thanks,
Michael

________________________________
From: Johannes Doerfert
Sent: Tuesday, February 18, 2020 5:34 PM
To: Michael Meng
Cc: Michael Kruse; via llvm-dev
Subject: Re: [llvm-dev] Differentiate array access at IR level

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

On 02/19, Michael Meng via llvm-dev wrote:> 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
> ________________________________
> From: Michael Kruse <llvmdev at meinersbur.de>
> Sent: Tuesday, February 18, 2020 9:26 AM
> To: Michael Meng <overrainbow2013 at hotmail.com>
> Cc: via llvm-dev <llvm-dev at lists.llvm.org>
> Subject: Re: [llvm-dev] Differentiate array access at IR level
>
> 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
>
> Am Mo., 17. Feb. 2020 um 00:04 Uhr schrieb Michael Meng via llvm-dev
> <llvm-dev at lists.llvm.org>:
> >
> > 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
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org
> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

--

Johannes Doerfert
Researcher

Argonne National Laboratory
Lemont, IL 60439, USA

jdoerfert at anl.gov
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200221/e9c45278/attachment-0001.html>

Johannes Doerfert via llvm-dev

2020-Feb-21 06:04 UTC

head link

[llvm-dev] Differentiate array access at IR level

On 02/21, Michael Meng wrote:> Hello Johannes,
> 
> Thanks for your suggestion! The ScalarEvolution analysis is very helpful.
> 
> I had a follow-up question. It would be great if you can take a look.
> 
>  %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
> 
> For the above code, the result for %idxprom7 is: (-1 + (sext i32 %12
> to i64))<nsw>. Just wondering if you have any suggestion that I can
> replace (sext i32 %12 to i64) with symbol %i
You need to "effectively" run mem2reg on your code first. If your code
was build without -O{1,2,3} the functions have probably the `optnone`
attribute. Remove it from the file and run mem2reg afterwards.

Maybe take a look at the create_ll.sh script (see below) as it shows how
.c -> .ll transformation should be done.


> Thanks,
> Michael
> 
> ________________________________
> From: Johannes Doerfert
> Sent: Tuesday, February 18, 2020 5:34 PM
> To: Michael Meng
> Cc: Michael Kruse; via llvm-dev
> Subject: Re: [llvm-dev] Differentiate array access at IR level
> 
> 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
> 
> On 02/19, Michael Meng via llvm-dev wrote:
> > 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
> > ________________________________
> > From: Michael Kruse <llvmdev at meinersbur.de>
> > Sent: Tuesday, February 18, 2020 9:26 AM
> > To: Michael Meng <overrainbow2013 at hotmail.com>
> > Cc: via llvm-dev <llvm-dev at lists.llvm.org>
> > Subject: Re: [llvm-dev] Differentiate array access at IR level
> >
> > 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
> >
> > Am Mo., 17. Feb. 2020 um 00:04 Uhr schrieb Michael Meng via llvm-dev
> > <llvm-dev at lists.llvm.org>:
> > >
> > > 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
> > > _______________________________________________
> > > LLVM Developers mailing list
> > > llvm-dev at lists.llvm.org
> > > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> 
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org
> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> 
> 
> --
> 
> Johannes Doerfert
> Researcher
> 
> Argonne National Laboratory
> Lemont, IL 60439, USA
> 
> jdoerfert at anl.gov
-- 

Johannes Doerfert
Researcher

Argonne National Laboratory
Lemont, IL 60439, USA

jdoerfert at anl.gov
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 228 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200221/b8a71572/attachment.sig>

Michael Kruse via llvm-dev

2020-Feb-21 19:55 UTC

head link

[llvm-dev] Differentiate array access at IR level

In the snippet, %i represents an address, but %12 represents the value
loaded from that address (and %idxprom7 an index computed from %12).
You probably don't want to mix the two.

What I assume from you question is that you would like to get rid of
the sign-extension (sext). It is part of the semantics, so it is
probably unwise to just ignore it, it it depends on what you actually
want to do. You could write you original program to use int64_t for
the variable i.

Michael


Am Do., 20. Feb. 2020 um 21:08 Uhr schrieb Michael Meng
<overrainbow2013 at hotmail.com>:>
> Hello Johannes,
>
> Thanks for your suggestion! The ScalarEvolution analysis is very helpful.
>
> I had a follow-up question. It would be great if you can take a look.
>
>  %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
>
> For the above code, the result for %idxprom7 is: (-1 + (sext i32 %12 to
i64))<nsw>. Just wondering if you have any suggestion that I can replace
(sext i32 %12 to i64) with symbol %i
>
>
> Thanks,
> Michael
>
> ________________________________ From: Johannes Doerfert
> Sent: Tuesday, February 18, 2020 5:34 PM
> To: Michael Meng
> Cc: Michael Kruse; via llvm-dev
> Subject: Re: [llvm-dev] Differentiate array access at IR level
>
> 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
>
> On 02/19, Michael Meng via llvm-dev wrote:
> > 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
> > ________________________________
> > From: Michael Kruse <llvmdev at meinersbur.de>
> > Sent: Tuesday, February 18, 2020 9:26 AM
> > To: Michael Meng <overrainbow2013 at hotmail.com>
> > Cc: via llvm-dev <llvm-dev at lists.llvm.org>
> > Subject: Re: [llvm-dev] Differentiate array access at IR level
> >
> > 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
> >
> > Am Mo., 17. Feb. 2020 um 00:04 Uhr schrieb Michael Meng via llvm-dev
> > <llvm-dev at lists.llvm.org>:
> > >
> > > 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
> > > _______________________________________________
> > > LLVM Developers mailing list
> > > llvm-dev at lists.llvm.org
> > > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org
> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
> --
>
> Johannes Doerfert
> Researcher
>
> Argonne National Laboratory
> Lemont, IL 60439, USA
>
> jdoerfert at anl.gov

llvm dev - Feb 2020 - Differentiate array access at IR level

[llvm-dev] Differentiate array access at IR level

[llvm-dev] Differentiate array access at IR level

[llvm-dev] Differentiate array access at IR level