Page MenuHomePhabricator

[Attributor] Liveness analysis.

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

Diff Detail


Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
jdoerfert added inline comments.Jul 3 2019, 2:58 PM
1017 ↗(On Diff #207891)

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.

1081 ↗(On Diff #207891)

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.

1116 ↗(On Diff #207891)

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.

723 ↗(On Diff #208080)

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

1016 ↗(On Diff #208080)

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.

1026 ↗(On Diff #208080)

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.

1024 ↗(On Diff #209704)

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

1058 ↗(On Diff #209704)

I think they have a count method.

1088 ↗(On Diff #209704)

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 ↗(On Diff #209704)

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

1108 ↗(On Diff #209704)

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

1111 ↗(On Diff #209704)

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

1139 ↗(On Diff #209704)

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

1170 ↗(On Diff #209704)

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

1172 ↗(On Diff #209704)

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.
1139 ↗(On Diff #209704)


1170 ↗(On Diff #209704)

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

1172 ↗(On Diff #209704)

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.)
1103 ↗(On Diff #209888)

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

1108 ↗(On Diff #209888)
if (ToBeExploredPaths.insert(Inst).second)
 HasNewPath = true;
1130 ↗(On Diff #209888)

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

1138 ↗(On Diff #209888)

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
1018 ↗(On Diff #209982)

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

1077 ↗(On Diff #209982)


1094 ↗(On Diff #209982)

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 ↗(On Diff #209982)

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.

1123 ↗(On Diff #209982)

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 ↗(On Diff #209982)

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

1144 ↗(On Diff #209982)

Just erase, no count necessary.

1108 ↗(On Diff #209888)

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.

14 ↗(On Diff #209982)

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 ↗(On Diff #209982)

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 ↗(On Diff #209982)

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.
1096 ↗(On Diff #209982)

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 ↗(On Diff #209982)

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

1135 ↗(On Diff #209982)

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

14 ↗(On Diff #209982)

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 ↗(On Diff #209982)

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
999 ↗(On Diff #210119)

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 ↗(On Diff #210119)

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

1103 ↗(On Diff #210119)

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

  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.
1103 ↗(On Diff #210119)

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?

723 ↗(On Diff #208080)

Improve the comments of these functions (mention BB)

1024 ↗(On Diff #209704)

Improve the description and make sure it is actually what happens

1037 ↗(On Diff #210583)

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

1044 ↗(On Diff #210583)

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

1069 ↗(On Diff #210583)

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 ↗(On Diff #210583)

Move the getAAFor into if (ICS) {

14 ↗(On Diff #209982)


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.

789 ↗(On Diff #210920)

Remove the BooleanState part.

819 ↗(On Diff #210920)

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.

1364 ↗(On Diff #210920)

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.

1389 ↗(On Diff #210920)

Get rid of these comments, also below.

1409 ↗(On Diff #210920)

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
Closed by commit rL366736: [Attributor] Liveness analysis. (authored by sstefan, committed by ). · Explain WhyJul 22 2019, 1:55 PM
This revision was automatically updated to reflect the committed changes.