Anderson's analysis, getresult instruction on x86_64

Hi,

I was trying to run Anderson’s pointer analysis using opt on a 64 bit x86 system (running Ubuntu 8.04) and it seems that the ‘getresult’ instruction is not currently handled. When I run the same analysis on the bitcode got by compiling (using llvm-gcc on a 32 bit machine) on a 32-bit x86 machine, it runs fine. I was trying to see if it is possible to quickly add a ‘visitGetResultInst’ to Andersons.cpp but could not quite find the right constraint to add to the pointer analysis. Can a instruction like :

%mrv_gr = getresult { i64*, i64* } %74, 0

be modelled as a load/store/getelementpointer and a Constraint::Load/Store/Copy be added to handle this case ?

Right now though, the opt crash in my case seems to be due to getresult that does not access pointers (i am guessing from {i64, i64} type though i may be wrong):

$ opt -anders-aa < 175.vpr.bc >/dev/null
Unknown instruction: %mrv_gr = getresult { i64, i64 } %74, 0 ; [#uses=1]
opt[0xb522ba]
opt[0xb523e4]
/lib/libc.so.6[0x2b4f6da277d0]
/lib/libc.so.6(gsignal+0x35)[0x2b4f6da27765]
/lib/libc.so.6(abort+0x110)[0x2b4f6da291c0]
opt[0x9aab0e]
opt(_ZN4llvm11InstVisitorIN83_GLOBAL__N__home_pprabhu_llvm_llvm_lib_Analysis_IPA_Andersens.cpp_00000000_1E0AD01D9AndersensEvE18visitGetResultInstERNS_13GetResultInstE+0x1d)[0x9c0a6b]
opt(_ZN4llvm11InstVisitorIN83_GLOBAL__N__home_pprabhu_llvm_llvm_lib_Analysis_IPA_Andersens.cpp_00000000_1E0AD01D9AndersensEvE14visitGetResultERNS_13GetResultInstE+0x1d)[0x9c0a8b]
opt(_ZN4llvm11InstVisitorIN83_GLOBAL__N__home_pprabhu_llvm_llvm_lib_Analysis_IPA_Andersens.cpp_00000000_1E0AD01D9AndersensEvE5visitERNS_11InstructionE+0x3eb)[0x9c1083]
opt(ZN4llvm11InstVisitorIN83_GLOBAL__N__home_pprabhu_llvm_llvm_lib_Analysis_IPA_Andersens.cpp_00000000_1E0AD01D9AndersensEvE5visitINS_14ilist_iteratorINS_11InstructionEEEEEvT_S8+0x3d)[0x9c10ff]
opt(_ZN4llvm11InstVisitorIN83_GLOBAL__N__home_pprabhu_llvm_llvm_lib_Analysis_IPA_Andersens.cpp_00000000_1E0AD01D9AndersensEvE5visitERNS_10BasicBlockE+0x42)[0x9c1154]
opt(ZN4llvm11InstVisitorIN83_GLOBAL__N__home_pprabhu_llvm_llvm_lib_Analysis_IPA_Andersens.cpp_00000000_1E0AD01D9AndersensEvE5visitINS_14ilist_iteratorINS_10BasicBlockEEEEEvT_S8+0x3d)[0x9c1199]
opt(_ZN4llvm11InstVisitorIN83_GLOBAL__N__home_pprabhu_llvm_llvm_lib_Analysis_IPA_Andersens.cpp_00000000_1E0AD01D9AndersensEvE5visitERNS_8FunctionE+0x42)[0x9c11ee]
opt(_ZN4llvm11InstVisitorIN83_GLOBAL__N__home_pprabhu_llvm_llvm_lib_Analysis_IPA_Andersens.cpp_00000000_1E0AD01D9AndersensEvE5visitEPNS_8FunctionE+0x1d)[0x9c1213]
opt[0x9add12]
opt[0x9c1252]
opt(_ZN4llvm13MPPassManager11runOnModuleERNS_6ModuleE+0xee)[0xadf60c]
opt(_ZN4llvm15PassManagerImpl3runERNS_6ModuleE+0x74)[0xadf79e]
opt(_ZN4llvm11PassManager3runERNS_6ModuleE+0x21)[0xadf801]
opt(main+0xb44)[0x7fab36]
/lib/libc.so.6(__libc_start_main+0xf4)[0x2b4f6da13b44]
opt[0x7ebd99]
Aborted (core dumped)

Thanks for any pointers (:)) !

  • Prakash

Hi,

I was trying to run Anderson's pointer analysis using opt on a 64 bit x86
system (running Ubuntu 8.04) and it seems that the 'getresult' instruction
is not currently handled. When I run the same analysis on the bitcode got by
compiling (using llvm-gcc on a 32 bit machine) on a 32-bit x86 machine, it
runs fine. I was trying to see if it is possible to quickly add a
'visitGetResultInst' to Andersons.cpp but could not quite find the right
constraint to add to the pointer analysis. Can a instruction like :

%mrv_gr = getresult { i64*, i64* } %74, 0

be modelled as a load/store/getelementpointer and a
Constraint::Load/Store/Copy be added to handle this case ?

Sure, it is equivalent to a copy from the function result.

Right now though, the opt crash in my case seems to be due to getresult that
does not access pointers (i am guessing from {i64, i64} type though i may be
wrong):

Ignoring non-pointers in every single case is an optimization, it is
not required for correctness.
We do in most cases, but it is harder in cases like structs, etc,
because they may contain pointers and it generally takes more time to
ignore the resulting constraints than it does to process them.

Hi Prakash,

I think this is highly related to PR2527 [1] and PR2451 [2]. I assume you are
using LLVM 2.3, since current svn automatically replaces getresult with
extractvalue instructions (but doesn't help for Andersen's).

In either case, it seems that Andersen's currently has no ready made way to
indicate a part of a first-class aggregate (or vector), which is the essence
of the problem here. For aggregates in memory, the pointer to the part of the
aggregate can simply be used, but no such thing for first class values.

I'm not really into how Andersen's works, so I won't be able to help you along
with this any further, I'm afraid.

Gr.

Matthijs

[1]: 2557 – Anders pass asserts on extractvalue/insertvalue
[2]: 2451 – Anders pass asserts on extractelement/insertelement

Thanks for the replies, Daniel and Matthijs. I added some code to generate the copy constraint, which I think (in the present form) is wrong (or at best not field sensitive):

+void Andersens::visitGetResultInst(GetResultInst &GR) {

  • if (isa(GR.getType()))
  • {
  • // P1 = getresult P2 → <Copy/P1/P2>
  • Constraints.push_back(Constraint(Constraint::Copy, getNodeValue(GR),
  • getNode(GR.getOperand(0))));
  • }
    +}

Take for example the getresult statement:

%mrv_gr = getresult { i64*, i64* } %74, 0 ; ; <i64*> [#uses=1]

The above code would add the constraint as Copy/%mrv_gr/%74 instead of Copy/%mrv_gr/%74.0 (the actual field which is a pointer). Is there a way in which
one can extract the Value* of the appropriate field of getresult using the index (0 in this case) and the base structure (%74) ? (or is this what you were refering to: “For aggregates in memory, the pointer to the part of the aggregate can simply be used, but no such thing for first class values.”, Matthjis ?)

Since in all the programs on which I am running Andersen’s analysis, the only usage of getresult is in accessing non-pointers:

%mrv_gr205 = getresult { i64, i64 } %615, 1 ; [#uses=1]

, for now, it seems to be ok to just ignore such instructions for pointer analysis (by the above code).

thanks,
Prakash

Hi Prakash,

The above code would add the constraint as Copy/%mrv_gr/%74 instead of
Copy/%mrv_gr/%74.0 (the actual field which is a pointer).

It does slightly depend on how you handle the multiple return statement in
this case (or for the svn version, insertvalue instructions). I guess that if
those are handled as copies as well (and Andersen's throws all the fields from
the struct on the same pile of "may alias"), then your code could be correct
(but certainly not optimal).

Is there a way in which one can extract the Value* of the appropriate field
of getresult using the index (0 in this case) and the base structure (%74) ?
(or is this what you were refering to: "For aggregates in memory, the
pointer to the part of the aggregate can simply be used, but no such thing
for first class values.", Matthjis ?)

The problem is that there is no such Value*, or at best %mrv_gr in the above
example is that Value*. This requires some special handling AFAICS, but
something like that might already be present for structs in memory.

Since in all the programs on which I am running Andersen's analysis, the
only usage of getresult is in accessing non-pointers:

%mrv_gr205 = getresult { i64, i64 } %615, 1 ; <i64> [#uses=1]

, for now, it seems to be ok to just ignore such instructions for pointer
analysis (by the above code).

Probably, this is how we "solved" this problem a while back as well. By now we
no longer need Andersen's, so this not biting us anymore.

Good luck!

Gr.

Matthijs

Thanks for the replies, Daniel and Matthijs. I added some code to generate
the copy constraint, which I think (in the present form) is wrong (or at
best not field sensitive):

This andersen's implementation is not field sensitive anyway.
I

+void Andersens::visitGetResultInst(GetResultInst &GR) {
+ if (isa<PointerType>(GR.getType()))
+ {
+ // P1 = getresult P2 --> <Copy/P1/P2>
+ Constraints.push_back(Constraint(Constraint::Copy,
getNodeValue(GR),
+
getNode(GR.getOperand(0))));
+ }
+}

Take for example the getresult statement:

%mrv_gr = getresult { i64*, i64* } %74, 0 ; ; <i64*> [#uses=1]

The above code would add the constraint as Copy/%mrv_gr/%74 instead of
Copy/%mrv_gr/%74.0 (the actual field which is a pointer). Is there a way in
which
one can extract the Value* of the appropriate field of getresult using the
index (0 in this case) and the base structure (%74) ? (or is this what you
were refering to: "For aggregates in memory, the pointer to the part of the
aggregate can simply be used, but no such thing for first class values.",
Matthjis ?)

There is a lot more work than this involved in supporting field
sensitive analysis in andersen's.in llvm.
Last time i chatted with Ben Hardekopf, he had a prototype for it.