This is an archive of the discontinued LLVM Phabricator instance.

[Attributor] Liveness analysis.
ClosedPublic

Authored by sstefan1 on Jul 3 2019, 2:32 PM.

Event Timeline

sstefan1 created this revision.Jul 3 2019, 2:32 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 3 2019, 2:32 PM

I'm going to add tests tomorrow morning. Posted without so you can have a chance to take a look, as this is not yet complete in my opinion.

jdoerfert added inline comments.Jul 3 2019, 2:58 PM
llvm/include/llvm/Transforms/IPO/Attributor.h
727

Put that as a class comment.

731

Leftover /

735

I think we can/should use EndAttrKinds + X from now on.

738

You should probably take a basic block here and below with a description that says the beginning (or end) of that block is assumed dead.

llvm/lib/Transforms/IPO/Attributor.cpp
1030

We do not want an attribute. Later we might want to place llvm_unreachables but first we need to get the logic right.

1043

Asssumed dead!

1052

If we want to get loop info, we should get it through the attributor/infocache. For now, I'd not do any of this "infinite loop logic".

1101

Erasing while iterating will eventually explode. Keep a second set with "now life" blocks that need to be replaced or a new "StillAssumedDead" set.

jdoerfert added inline comments.Jul 3 2019, 2:58 PM
llvm/lib/Transforms/IPO/Attributor.cpp
1019

While I proposed this method I think we can do something smarter. We can scan the function from the entry block (put the functionality somewhere as you need it again below) and mark blocks life that are reached on a path without a assumed or known noreturn function call. While doing so you want to record these function calls as well so we know what to look for in the update.

1083

This iteration order is expensive and not strictly necessary, in the worst case the first block has a noreturn call and you still make everything life.

I think you should perform a bit more analysis in the initialize (see above) and then:

  • Check all calls we stopped at before because they had an assumed or known noreturn. If they still do, skip them.
  • If they lost the assumed noreturn make every block reachable from the call life but stop at calls that are assumed or known noreturn and at already assumed life blocks. The calls that stopped the traversal go into the set that we traverse in the next update.

If I'm not mistaken, that should limit the traversal of this attribute to at most two visit of each instruction in the function.

1118

There is no optimistic fixpoint after a single update call because the information used above, e.g., isAssumedNoReturn, might change over time.

sstefan1 updated this revision to Diff 208080.Jul 4 2019, 2:21 PM

Addressed comments

I guess we need to implement a manifest to make testing easier.

I'd propose the following in the manifest method:
Split the block that is dead after the phi-nodes (see splitBasicBlock) and replace the unconditional jump with a llvm_unreachable.

On second thought, maybe manifest should go through the list of noreturn calls and place llvm_unreachable after them. Later, we will
have more "sources" in addition to noreturn and then we introduce the unreachable after all of them.

llvm/include/llvm/Transforms/IPO/Attributor.h
723

I think these methods need to take a basic block and/or instruction.

llvm/lib/Transforms/IPO/Attributor.cpp
1018

You need to explore the function in a different way:
Keep a list of "to be expored" paths defined by instructions.
Start with the first instruction in the entry block as a first "to be explored path".
Continue to the next instruction if it is not a noreturn call.
If it is the last in the block, add all successors instructions to the "to be explored" path list.
Make sure you never follow a path/instruction twice.

The functionality above should live in a separate function as it will be needed in the update method as well.
Basically, update is the same thing but the start points are all noreturn calls that are not noreturn anymore.

1028

The code after the noreturn call is assumed dead but not the block.

sstefan1 updated this revision to Diff 209704.Jul 13 2019, 10:55 AM
  • Change initialize, explore paths.

This looks close to what I was hoping for. Some comments inlined.

llvm/lib/Transforms/IPO/Attributor.cpp
1024

I think the return value should indicate if you explored new instructions or not.

1058

I think they have a count method.

1088

You don't need to look at the whole block if you want to start at I.
You can go from instruction to instruction with I->getNextNode().

1096

known always implies assumed. So it is sufficient to check for assumed.

1108

for (BasicBlock *SuccBB : successors(BB)) {

1111

Keep an additional set or a SetVector to make this lookup cheap.

1139

I'm unsure if we need two sets here. I was hoping: "not in AssumedLive" means "assumed dead".

1170

Why do we need this logic. Above, you already explore exhaustively starting from old assumed noreturn instructions. I hoped that was enough.

1172

For now, I'd just return changed/unchanged. That can be determined by the return values of explorePath, e.g., if we did not explore any new instruction nothing has changed.

sstefan1 marked 6 inline comments as done.Jul 15 2019, 9:24 AM
sstefan1 added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
1139

Agreed.

1170

This was mainly left over code from last diff. Should have been removed.

1172

I'm not sure I can just return unchanged after one false explore. I'd stick with this for now.

sstefan1 updated this revision to Diff 209888.Jul 15 2019, 9:26 AM
sstefan1 marked 3 inline comments as done.
  • addressing comments

We need more tests, including but not limited to:

  • Unreachable blocks.
  • Dead blocks caused by something other than noreturn, e.g., infinite loops, recursion, undefined behavior etc. (these will be "FIXME" tests)
  • An assumed noreturn call that is later not assumed noreturn anymore. (I'll work basic on no-return deduction now.)
llvm/lib/Transforms/IPO/Attributor.cpp
1103

I think any advance above, e.g., any new live instruction, should result in a ChangeStatus::CHANGED result from updateImpl.

1108
if (ToBeExploredPaths.insert(Inst).second)
 HasNewPath = true;
1130

You need to update the NoReturnCalls set. However, now you modify it while iterating, that is a problem.

1138

You can have new live blocks even if not all blocks are live.

sstefan1 updated this revision to Diff 209982.Jul 15 2019, 3:55 PM
  • More tests.
  • Small changes.
jdoerfert added inline comments.Jul 15 2019, 7:00 PM
llvm/lib/Transforms/IPO/Attributor.cpp
1018

For now, we should mark the entry as live. (It would not if it contained a noreturn call right now -> test case)

1077

Leftover.

1094

Maybe make this two or three conditionals so it is easier to read. First exclude non call sites, then the ones marked noreturn, then the ones assumed noreturn.

1096

See the comment at the declaration. Basically, whenever we explored at least one instruction we have to report that back, e.g., to remove the NoReturnCall from the set.

1108

You do not need the count. Just insert it and check the return value if it was already there or if it was actually added.

1123

Do not use auto here. Not needed and not clear.

The NoReturnCalls are updated in explorePath so iterating over them while updating them is bad and will explode.

1135

Haven't we changed the "AssumedLiveSet" here already, when the size is different I mean.

1144

Just erase, no count necessary.

llvm/test/Transforms/FunctionAttrs/liveness.ll
14

Then do it and add the appropriate check lines :), here and in the other tests. It is an indirect test but it is better than nothing. So you will also need to use the liveness AA in the nosync AA.

91

I'm not sure what undefined behavior (UB) you mean here. Generally, we need something undefined that has a side-effect, e.g., a load null, or br undef.

147

you mean rec(). Also add this test again and do not call rec but testX where X is the number.

sstefan1 marked 13 inline comments as done.Jul 16 2019, 9:30 AM
sstefan1 added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
1096

This is checked and removed in updateImpl. In other words, when starting point is a noreturn instruction and we found a new live instruction, that call is deleted from NoReturnCalls as it is not noreturn anymore.

1123

I Changed this a bit now to avoid updating while iterating.

1135

Good point. State should already be CHANGED at this point.

llvm/test/Transforms/FunctionAttrs/liveness.ll
14

Is it ok if I do this in a separate patch, once this and noreturn go in? In that patch I can update all attributes to use AAIsDead and update these tests accordingly.

This test is kind of already present in the cond.true block. foo which is not nosync is called after noreturn call. I'm just proposing to add CHECK lines and liveness usage to other attributes in separate patch.

91

This is supposed to be signed overflow. It is not called anywhere, but I agree it is not the best test case.

sstefan1 updated this revision to Diff 210119.Jul 16 2019, 9:30 AM
sstefan1 marked 3 inline comments as done.
  • addressing comments
jdoerfert added inline comments.Jul 17 2019, 4:47 PM
llvm/lib/Transforms/IPO/Attributor.cpp
999

I guess that calling this a function attribute (here and elsewhere) is not really the right thing to do but we do not have any concept that would fit better right now.

1028

maybe print something like:
"LiveBBs(" << AssumedLiveBlocks.size() << "/" << getAnchoredScope().size() << ")"

1103

Let's assume you get in here for an assumed noreturn call NC which is not assume noreturn anymore, you iterate over the block until you find one that is noreturn. In that case you return false above which would *not* remove the former assumed noreturn call NC from the NoReturnCalls set, causing us to introduce an unreachable at the end! You have to return true whenever the original instruction I is not assumed noreturn anymore, e.g., one you call I->getNextNode we cannot return false anymore

test case sketch

bb:
  call %assumed_noreturn_but_actually_return
  call %noreturn
sstefan1 marked 2 inline comments as done.Jul 18 2019, 8:25 AM
sstefan1 added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
1103

Ok, I was wrong about this. Now it will return false only if we are looking at a noreturn call that is already in NoReturnCalls, in other words, still noreturn.

sstefan1 updated this revision to Diff 210583.Jul 18 2019, 8:27 AM
sstefan1 marked an inline comment as done.
  • explorePath now returns false only if starting point is a noreturn call that is still noreturn.

Almost there, I think the tests need to be improved (check lines as noted below). Also, do we add the entry block to the live blocks?

llvm/include/llvm/Transforms/IPO/Attributor.h
723

Improve the comments of these functions (mention BB)

llvm/lib/Transforms/IPO/Attributor.cpp
1024

Improve the description and make sure it is actually what happens

1037

I don't think you should check the second condition because the associated value is not really important here anyway.

1044

We need a check with a noreturn invoke as it is a terminator that does not have a next node. Does this work?

1069

if known is true, assumed is true so no need for this second conditional.
The count condition here and above could just be: return !AssumedLiveBlocks.count(BB);

1090

Move the getAAFor into if (ICS) {

llvm/test/Transforms/FunctionAttrs/liveness.ll
14

OK.

One thing though: do not only check for the existence of an unreachable, it could be anywhere. Check the surroundings (function name, then basic block name, etc.) and use CHECK-NEXT: to make sure the CFG looks as expected.

sstefan1 updated this revision to Diff 210809.Jul 19 2019, 5:48 AM
  • addressing comments.
sstefan1 updated this revision to Diff 210920.Jul 19 2019, 3:51 PM
  • Rebased and added AANoReturn declaration.
  • ninja check-all & test-suite passed fine.
sstefan1 retitled this revision from Summary: [Attributor] Liveness analysis abstract attribute used to indicate which BasicBlocks are dead and can therefore be ignored. to [Attributor] Liveness analysis..Jul 19 2019, 3:53 PM
sstefan1 edited the summary of this revision. (Show Details)

This looks generally fine to me. Some small comments that are easy to fix but on bigger request wrt. Invokes. After thinking about this I realized it is not as simple, and the code that already deals with this proved me right. We should reuse that logic to replace Invokes, or even better, to insert unreachables where possible. Take a look at the inlined comments and let me know if you encounter problems.

llvm/include/llvm/Transforms/IPO/Attributor.h
728

Remove the BooleanState part.

758

Just before you commit, make sure this is unique, thus no other attribute we comited in the meantime has EndAttrKinds + 1 as ID. I will come up with a "better" system soon.

llvm/lib/Transforms/IPO/Attributor.cpp
1045

Please make changeToCall(..) in llvm/lib/Transforms/Utils/Local.cpp visible to the outside (also rename it properly) and then use it. We do want to avoid duplication and changing invoke to call is not as simple as this.
We could even go further and expose the "insert unreachable" logic that is present in the Local.cpp such that you could call it here for each I.

1070

Get rid of these comments, also below.

1090

Make this a (Small)SetVector to ensure deterministic exploration. It is not strictly necessary for correctness but confusing if we get different results on a timeout. It also makes it harder to debug.

Also consider making the three members above private.

sstefan1 updated this revision to Diff 211144.Jul 22 2019, 10:46 AM
  • Make changeToCall available from Local.h
  • address comments
jdoerfert accepted this revision.Jul 22 2019, 12:50 PM

Assuming you pass the llvm test suite and ninja check-all, this LGTM.

This revision is now accepted and ready to land.Jul 22 2019, 12:50 PM
This revision was automatically updated to reflect the committed changes.