This is an archive of the discontinued LLVM Phabricator instance.

[stack-safety] Check SCEV constraints at memory instructions.
ClosedPublic

Authored by fmayer on Nov 3 2021, 5:53 PM.

Diff Detail

Event Timeline

fmayer created this revision.Nov 3 2021, 5:53 PM
fmayer updated this revision to Diff 384906.Nov 4 2021, 4:43 PM

style changes

fmayer published this revision for review.Nov 4 2021, 4:45 PM
fmayer added reviewers: eugenis, vitalybuka.
fmayer added a subscriber: kstoimenov.
Herald added a project: Restricted Project. · View Herald TranscriptNov 4 2021, 4:45 PM

This looks nice. Any idea how much does it improve analysis success rate in practice?

Would be great to have a test with some loop, if it works.

llvm/lib/Analysis/StackSafetyAnalysis.cpp
344

It's a little strange to compute type size in a pointer, but SCEV does not care as long as the number of bits is the same, so I guess it is fine.

402–405

move getTypeStoreSize into getTypeSize

This looks nice. Any idea how much does it improve analysis success rate in practice?

Would be great to have a test with some loop, if it works.

It doesn't support loops yet, I've been experimenting with isKnownAtEveryIteration without success so far. Will keep trying.

llvm/lib/Analysis/StackSafetyAnalysis.cpp
402–405

The way it is now makes it more obvious that this TypeSize is the same that we use in the getAccessRange call, so I'd prefer to leave it like this. WDYT?

fmayer updated this revision to Diff 386379.Nov 10 2021, 5:41 PM

improve naming

llvm/lib/Analysis/StackSafetyAnalysis.cpp
402–405

I changed the name of getTypeSize to make more explicit what it does.

fmayer updated this revision to Diff 386404.Nov 10 2021, 7:14 PM

fix typo

LGTM but please wait for review from Vitaly, too

kstoimenov added inline comments.Nov 11 2021, 3:08 PM
llvm/lib/Analysis/StackSafetyAnalysis.cpp
121

Isn't that just a set?

258

If this is an output param, please consider moving it to the end of the argument list.

399

Add the var you are setting in comments like so: /*x=*/false to increase readability. Here and below.

kstoimenov added inline comments.Nov 11 2021, 3:19 PM
llvm/lib/Analysis/StackSafetyAnalysis.cpp
876

If converted to set this loop could be:

Info->AccessIsUnsafe[A.first].insert(KV.second.AccessIsUnsafe.first, KV.second.AccessIsUnsafe.end);

There is also set::merge in C++ 17, but it will move the elements from the second set I think.

fmayer updated this revision to Diff 386718.Nov 11 2021, 7:28 PM
fmayer marked 6 inline comments as done.

address comments

llvm/lib/Analysis/StackSafetyAnalysis.cpp
258

There is no output parameter in this. This is just non-const because getSCEV does not take const.

kstoimenov added inline comments.Nov 12 2021, 11:36 AM
llvm/lib/Analysis/StackSafetyAnalysis.cpp
121

I am not sure what is the ratio of unsafe to safe accesses is, but I would expect that more of them are unsafe, right? In that case it makes more sense to have a set of SafeAccesses to use less memory.

951

Nit: could be !Info.UnsafeAccesses.contains(&I).

fmayer marked 2 inline comments as done.Nov 12 2021, 11:45 AM
fmayer added inline comments.
llvm/lib/Analysis/StackSafetyAnalysis.cpp
121

That doesn't work though. What we want is

any(instr is unsafe for alloca for all allocas reachable)

for that we need to keep track of the unsafe instructions for each alloca.

951

No, that doesn't work because it's too new for LLVM code.

Unless otherwise documented, LLVM subprojects are written using standard C++14 code and avoid unnecessary vendor-specific extensions.

LGTM for my comments.

fmayer marked 2 inline comments as done.Nov 17 2021, 11:46 AM

@vitalybuka friendly ping

vitalybuka added inline comments.Nov 18 2021, 12:30 AM
llvm/lib/Analysis/StackSafetyAnalysis.cpp
260

Can you replace typeSizeToSCEV with two overloads?

bool isSafeAccess(... Value *AccessSize)

bool isSafeAccess(...TypeSize AccessSize)
319–325

why don't we do this in case if isSafeAccess?

344
auto *IntTy = IntegerType::getIntNTy(SE.getContext(), PointerSize);
  return SE.getConstant(IntTy, TS.getFixedSize());
353

UI -> U

354

I is not needed, it can be retrived from U

367–369

In all 3 cases can you please replace
toCharPtr with getIntNTy, at least for readability not sure if it make a difference for SCEV

399

maybe add for this case a dedicated function US.addUnsaveAccess(I);

466

for consistency
either (i prefer this one):

US.addRange(I, getAccessRange(UI, Ptr, TypeSize);,
                        isSafeAccess(UI, AI, I, typeSizeToSCEV(TypeSize)));

or:

auto AccessRange = getAccessRange(UI, Ptr, TypeSize);
bool Safe = isSafeAccess(UI, AI, I, typeSizeToSCEV(TypeSize));
US.addRange(I, AccessRange, Safe);
fmayer updated this revision to Diff 388666.Nov 19 2021, 4:48 PM
fmayer marked 7 inline comments as done.

address comments

llvm/lib/Analysis/StackSafetyAnalysis.cpp
260

I think that just adds more complexity, as this way we will need

bool isSafeAccess(... Value *AccessSize)
bool isSafeAccess(... TypeSize AccessSize)

which only do the conversion and call some

isSafeAccess(... SCEV *AccessSize).

Doing the conversion explicitly in the caller seems more readable to me.

319–325

Added this and a test that fails without this. Thanks!

353

Ok.

Although this is called UI in analyzeAllUses.

399

Let's hold off of this for now, as that needs some changes (UnknownRange is in StackSafetyLocalAnalysis).

fmayer updated this revision to Diff 388667.Nov 19 2021, 4:51 PM

formatting

vitalybuka added inline comments.Nov 19 2021, 6:52 PM
llvm/lib/Analysis/StackSafetyAnalysis.cpp
260

please do this to remove SCEV stuff from that long loop

367–369

maybe: can you make toCharPtr same local lambda? or you plan to use it outside?

447

it's going to make instruction safe even if user is not alloca

For consistency isSafeMemIntrinsicAccess will help

fmayer added inline comments.Nov 19 2021, 6:55 PM
llvm/lib/Analysis/StackSafetyAnalysis.cpp
447

This is consistent with the API this is used in

// Returns true if the instruction can be proven to do only two types of
// memory accesses:
//  (1) live stack locations in-bounds or
//  (2) non-stack locations.

If the user is not alloca, that is (2).

vitalybuka added inline comments.Nov 20 2021, 12:39 AM
llvm/lib/Analysis/StackSafetyAnalysis.cpp
121

Just noticed:
Why this is in UseInfo and per alloca, and then we merge them latter anyway?
It should be FunctionInfo::UnsafeAccesses?

Then you pass that reference to the set as new arg of analyzeAllUses

447

it's going to make instruction safe even if *user* is not alloca

*user* -> location

isSafeAccess() line 355
return false for !AI

I don't like to have undefined behavior for (2) even if you don't use it now. It's trivial to make it defined either true or false. However if instruction access function argument, we don't know if it a stack of another function. So unsafe (false) seems reasonable choose here. BTW why this is not important for current callers?

fmayer updated this revision to Diff 389270.Nov 23 2021, 11:25 AM
fmayer marked 6 inline comments as done.

address comments

llvm/lib/Analysis/StackSafetyAnalysis.cpp
121

Can we do this in a separate change? This doesn't really belong here.

447

Good point, if !AI in isSafeAccess we should also return true, for consistency. Then the semantics remain well-defined and the same: "all *stack* accesses done by this instruction are safe.

The callers check findAllocaForValue to make sure this is definitely a stack access before calling stackAccessIsSafe.

vitalybuka accepted this revision.Nov 23 2021, 12:08 PM
vitalybuka added inline comments.
llvm/lib/Analysis/StackSafetyAnalysis.cpp
121

sure
in would be nice in follow up patches also to switch from UnsafeAccesses to SaveAccessesOnAlloca
probably we can track two sets:
a. all instructions on any alloca
b. unsafe instructions on any alloca
and then keep (a-b) for result.

447

i don't like this assumption on what user will do
this seems like a goal of this analysis and it should tell without external tricks.

However It should be easier to do after "UnsafeAccesses" followup patch.

This revision is now accepted and ready to land.Nov 23 2021, 12:08 PM
This revision was landed with ongoing or failed builds.Nov 23 2021, 3:29 PM
This revision was automatically updated to reflect the committed changes.