Helper analyses optimization

[fabianbs96]

The helper analyses of PhASAR - especially the LLVMPointsToSet and LLVMBasedICFG perform unnecessary work leading to runtimes of several hours on large target modules.

This PR reduces the runtime to just a few minutes for the OpenSSL codebase, even when running PhASAR in debug mode.

[blipper]

Thank you thank you thank you!

[fabianbs96]

Do not merge! There was a bug in the code and the fix again slowed down the analysis. I will improve it next week. If you have an idea on how to improve it before that, feel free to do the changes directly in this branch

[MMory]

Current state breaks previously fixed issue #206 .

[blipper]

Yes. My statement should have been stronger. AA alias is definitely not threadsafe and will crash if you try to use it as such. When I was getting bitten by the slowness AA.alias was where a significant amount of time was being spent.

M

On Tue, Aug 31, 2021, 4:03 AM Florian Sattler @.***> wrote:

@.**** commented on this pull request.

In lib/PhasarLLVM/Pointer/LLVMPointsToSet.cpp https://github.com/secure-software-engineering/phasar/pull/413#discussion_r699082483 :

 }

• if (EvalAAMD && llvm::isa(&*I)) {

• Loads.insert(&*I);

• llvm::Type *I1ElTy = V->getType()->getPointerElementType();

• return I1ElTy->isSized() ? DL.getTypeStoreSize(I1ElTy)

• : llvm::MemoryLocation::UnknownSize;

• };

• auto mayAlias = [&AA](const llvm::Value *V1, uint64_t V1Size,

• const llvm::Value *V2, uint64_t V2Size) {

• return AA.alias(V1, V1Size, V2, V2Size) != llvm::AliasResult::NoAlias;

As far as I know, AA does not guarantee thread safety (the accesser methods to AAResults are not even const and "could" potentially change the state of the result) and LLVM for the most part is also not thread safe. From a brief glimps into the implementation I could not find anything that "should" not work, however, everything there and in phasar builds on LLVMContext and not ThreadSafeContext, so I guess we don't have any guarantees.

One thing we could try to explore this a bit further, is to build phasar (and probably LLVM) with clangs TSA and just try to run it in parallel, see what breaks. However, in the end, we probably need a thorough check of the code to not run into spurious behavior and threading bugs 🤣.

So, before checking this out further, do you have profiles of an analysis that show this to be the major bottleneck? From my experience, I often found other spots in phasar that could be optimized with much less risk/work needed.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/secure-software-engineering/phasar/pull/413#discussion_r699082483, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAHCY7JO5WLGZYHU4AOWXNDT7SEDVANCNFSM5CNYF2HQ . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.

[vulder]

Yes. My statement should have been stronger. AA alias is definitely not threadsafe and will crash if you try to use it as such. When I was getting bitten by the slowness AA.alias was where a significant amount of time was being spent. M …

I see. One relatively cheap idea we could try is a thread safe LRU cache around queries to AAResult (or queries to phasars AA points to abstraction). The cache itself queries AAResults synchronously but offers a TS API to the rest, meaning, we can access the results from multiple threads and only need to be single threaded when a result was not previously computed (is cached). This would allow us to trade a bit of run-time against memory (depending on the cache size). However, if this really saves time depends highly on the workload (AA queries). So, before we build this we probably should have a look at the access behavior/patterns or different codes/analyses*.

*if the cache is not always profitable, we could it a feature that can be switched on/off.

[blipper]

I had a couple thoughts here 1). Keep multiple instances of bitcode loaded and run one thread per instance 2) Implement own thread safe versus of AA algorithm

The problem we have is that llvm parallelism is designed to be done per process (e.g. make -j) and we really want per thread.

On Tue, Aug 31, 2021, 8:00 AM Florian Sattler @.***> wrote:

Yes. My statement should have been stronger. AA alias is definitely not threadsafe and will crash if you try to use it as such. When I was getting bitten by the slowness AA.alias was where a significant amount of time was being spent. M … <#m-791637013587854254>

I see. One relatively cheap idea we could try is a thread safe LRU cache around queries to AAResult (or queries to phasars AA points to abstraction). The cache itself queries AAResults synchronously but offers a TS API to the rest, meaning, we can access the results from multiple threads and only need to be single threaded when a result was not previously computed (is cached). This would allow us to trade a bit of run-time against memory (depending on the cache size). However, if this really saves time depends highly on the workload (AA queries). So, before we build this we probably should have a look at the access behavior/patterns or different codes/analyses*.

*if the cache is not always profitable, we could it a feature that can be switched on/off.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/secure-software-engineering/phasar/pull/413#issuecomment-909169824, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAHCY7KPKKHMGOCTMCA3RJ3T7S75PANCNFSM5CNYF2HQ . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.

[vulder]

@MMory Can the AA you're working on be run in parallel? Or do you know, what it would take to do this?

[vulder]

@fabianbs96 I took a look at the unique_ptr version, I'm not sure where the time overhead comes in. What workload/test command do you use for benchmarking? If you could send it to me I could take a closer look, I guess there some small thing were are currently missing.

PS: If you like to have a quick talk about it, we can schedule a meeting or, if you have time on Tuesday 15:00, you can join our weekly meeting with Phlipp, Martin, and me.

[fabianbs96]

@vulder I am mostly using the following two files for testing/benchmarking the alias analysis: target_ir.zip To measure the runtime, I use the UNIX time command (On such large files, the differences are in multiple seconds, so this should be precise enough).

I would really like to talk about it with you. Maybe, we can setup a meeting via a different channel