The use iterator not working...

Project Infrastructure LLVM Dev List Archives
#1

Hi,

I’m having a problem with the use iterator. Each “use” that I see, when using the use_iterator, is the same as the “def”. Meaning, in the code below the pDef is always equal to pUse pointer for every instruction in all basic blocks (except terminators).

for (auto i = inst_begin(f), ie = inst_end(f); i != ie; ++i)

Instruction* pDef = &(*i);
errs() << "Def: " << *pDef << “\n”;

for (auto ui = pDef->use_begin(), uie = pDef->use_end(); ui != uie; ++ui)
{

Instruction* pUse = dyn_cast(*ui);
errs() << " Use: \t" << *pUse << “\n”;
}
}

However, everything works as expected when using the range-based use iterator with the following code.

for (auto i = inst_begin(f), ie = inst_end(f); i != ie; ++i)
{
Instruction* pDef = &(*i);
errs() << "Def: " << *pDef << “\n”;

for (User* pUser : pDef->users())
{
Instruction* pUse = dyn_cast(pUser);
errs() << " Use: \t" << *pUse << “\n”;
}
}

Also, the code is executed inside a function pass. So was initially thinking I somehow screwed up the use information in a previous pass. However, I would assume the range-based iterator would not work as well but it does.

Finally, I’m currently using LLVM 3.5.1 built for Windows. Google hasn’t been much help. Anybody have any suggestions as to why the first example above doesn’t work?

Thanks,
Zack

#2

Hi,

I'm having a problem with the use iterator. Each "use" that I see, when
using the use_iterator, is the same as the "def". Meaning, in the code below
the pDef is always equal to pUse pointer for every instruction in all basic
blocks (except terminators).

            for (auto i = inst_begin(f), ie = inst_end(f); i != ie; ++i)

                Instruction* pDef = &(*i);
                errs() << "Def: " << *pDef << "\n";

                for (auto ui = pDef->use_begin(), uie = pDef->use_end(); ui
!= uie; ++ui)
                {
                    Instruction* pUse = dyn_cast<Instruction>(*ui);

This doesn't do what you think it does.

This gives you the places the instruction i occurs in some other
instruction. Those places are in fact, pointers to i already.

You are then calling operator *, which will return i, and then
dyn_casting it to an instruction, which is still i.

If you want the *instruction that uses i* (not the pointer to the
place in that instruction that *is* i), then you want the users, not
the uses.
IE this would be Instruction* pUse = dyn_cast<Instruction>(ui->getUser())

Or just iterator over the users, not the uses.

                    errs() << " Use: \t" << *pUse << "\n";
                }
            }

However, everything works as expected when using the range-based use
iterator with the following code.

            for (auto i = inst_begin(f), ie = inst_end(f); i != ie; ++i)
            {
                Instruction* pDef = &(*i);
                errs() << "Def: " << *pDef << "\n";

                for (User* pUser : pDef->users())
                {

This is not a use iterator, it is a user iterator, which is giving you
*the instructions that contain the uses*.

To illustrate the difference.

given
a = foo
b = a + c

(I'm simplifying, since LLVM does not represent LHS'en or have copies)

if you ask for a use iterator of a,

you will get &(operand 1 of b, which is a pointer to a).
If you dereference it, you will get "a" (and if you dyn_cast that to
an instruction, it will give you a = foo)
if you ask for it's user, you will get "a + c"

If you ask for a user iterator of a
you will get a + c

                    Instruction* pUse = dyn_cast<Instruction>(pUser);
                    errs() << " Use: \t" << *pUse << "\n";
                }
            }

Also, the code is executed inside a function pass. So was initially thinking
I somehow screwed up the use information in a previous pass. However, I
would assume the range-based iterator would not work as well but it does.

Because it is not, in fact, giving you uses :slight_smile:

#3

Hi,

I'm having a problem with the use iterator. Each "use" that I see, when
using the use_iterator, is the same as the "def". Meaning, in the code
below the pDef is always equal to pUse pointer for every instruction in
all basic blocks (except terminators).

             for (auto i = inst_begin(f), ie = inst_end(f); i != ie; ++i)
                 Instruction* pDef = &(*i);
                 errs() << "Def: " << *pDef << "\n";

                 for (auto ui = pDef->use_begin(), uie =
pDef->use_end(); ui != uie; ++ui)
                 {

'user' != 'use'.

Think of llvm::Use as the edge between the place where a value is produced, and the place where that value is consumed. The consumer is the 'User', and the Use points at it.

http://llvm.org/docs/doxygen/html/classllvm_1_1Use.html

The confusing thing that's happening below is that the llvm::Use is implicitly converted via `llvm::Use::operator Value *() const` to a `Value*`, and that `Value*` is `pDef`.

HTH,

Jon

#4

Thanks Dan and Jon. I made an incorrect assumption that the “use” iterator was actually giving me the “user” when de-referencing it.

Did it always have this behavior in previous LLVM versions? I’ve seen lots of examples of the “use” iterator being dereferenced and resulting Instruction pointer being treated as the “user”?

Thanks,
Zack

#5

Thanks Dan and Jon. I made an incorrect assumption that the "use"
iterator was actually giving me the "user" when de-referencing it.

Did it always have this behavior in previous LLVM versions?

Not sure.... I don't know the history of it. Best guess is: "probably".

I've seen
lots of examples of the "use" iterator being dereferenced and resulting
Instruction pointer being treated as the "user"?

Can you point out specific examples?

Jon

#6

Here are some specific examples:

http://www.cs.cmu.edu/afs/cs/academic/class/15745-f09/www/lectures/lect3-llvm.pdf - Slide 30

http://aviral.lab.asu.edu/?p=1699 - LLVM Def-Use & Use-Def Chains.

http://stackoverflow.com/questions/6807743/def-use-chain-in-llvm

https://github.com/codelion/pa.llvm/blob/master/CVA/CVA.cpp - RunAnalysis starting line 234

http://lists.cs.uiuc.edu/pipermail/llvmdev/2010-September/034909.html

https://github.com/karrenberg/wfv/blob/master/src/functionPasses/loopLiveValueAnalysis.hpp - See findUseOutsideLoop function at line 227.

I’ve seen other projects using LLVM 3.3 that have similar code.

Zack

#7

It has, AFAIK, always been this way.
It is also a common source of bugs, as I believe you have discovered.

If we had llvm-specific "clang warnings", this would be one i added
(IE "Dereferencing use iterator of x gives x") :slight_smile:

In the past 6 months, i did this twice by accident in passes and then
spent hours tracking it down.

It actually makes me wonder whether use_iterator should even have an
operator * for the use_iterator_impl<Use> case. ISTM to basically
always be a bug (though this is an idle thought, i haven't thought
through the implications at all).

#8

It appears dereferencing the use iterator returned the “user” in older LLVM versions. See the following commit to Use.h. You can see that the intention is to return the “user”. So this is not the behavior anymore.

https://github.com/llvm-mirror/llvm/commit/d1fe495464e4abc384565813cbf1cb8b130e5a6d

  • // Retrieve a pointer to the current User.
    • UserTy operator() const {
    • assert(U && “Cannot dereference end iterator!”);
    • return U->getUser();
    • }
#9

It appears dereferencing the use iterator returned the "user" in older
LLVM versions. See the following commit to Use.h. You can see that the
intention is to return the "user". So this is not the behavior anymore.

https://github.com/llvm-mirror/llvm/commit/d1fe495464e4abc384565813cbf1cb8b130e5a6d

- // Retrieve a pointer to the current User.
    - UserTy *operator*() const {
    - assert(U && "Cannot dereference end iterator!");
    - return U->getUser();
    - }

Looks like the change actually happened in: https://github.com/llvm-mirror/llvm/commit/36b699f2b139a30a2dfa4448223d6985b55daa8a (r203364), and from the commit message, it was deliberate. Whether or not that part of it was a "good" change is a different question.

Jon

#10

I stand corrected :slight_smile:

#11

This kind of change can really make it difficult to migrate a large LLVM based compiler from an older version to the latest when you’re not aware of it and its a silent error.