[ADCE] Add handling of PHI nodes when removing control flow

[david2050]

Summary

This is part of a series of patches to evolve ADCE.cpp to support
removing of unnecessary control flow.

This patch updates the propagation of liveness information to handle
special properties of PHI nodes.

We still force all terminators live for now until we add code to
handle removing control flow in a later patch.

No changes to effective behavior with this patch

Previous patches:

D23559 [ADCE] Add control dependence computation
D23225 [ADCE] Modify data structures to support removing control flow
D23065 [ADCE] Refactor anticipating new functionality (NFC)
D23102 [ADCE] Refactoring for new functionality (NFC)

[majnemer]

lib/Transforms/Scalar/ADCE.cpp

288–289

I'd use auto *.

327

Ditto.

423

Ditto.

[david2050]

Use auto keyword

[mehdi_amini]

lib/Transforms/Scalar/ADCE.cpp

116

Can you revisit the comment? I find it hard to figure what you want to do here.

Also, as a side note, "verify" makes me think of a "check", which does not go well with the name of the method prefixed with "mark".

428

This is not clear to me, I have no idea what is going on in this code?
I mean I can follow what your doing, but I don't know why.

[david2050]

Expand comments on actions taken by makeLivePhiNodeInputs

[mehdi_amini]

lib/Transforms/Scalar/ADCE.cpp

116

s/poeration/operation

121

s/hte/the

449

There is no br label %cond.false here.

450

Thanks for the extensive comment and the example, unfortunately this is not really the information I was looking for.
Phi nodes are dependent on the control flow, and we need to mark predecessors live in general, I got that part, but what isn't just clear to me is *why* only *some* blocks are marked live.

For instance:

define i8 @foo(i1 %cond1, i1 %cond2, i8 %a, i8 %b, i8 %c, i8 %d) nounwind {
entry:
  br i1 %cond1, label %first_true, label %first_false
first_true:
  br i1 %cond2, label %second_true, label %second_false
first_false:
  br label %end
second_true:
  br label %end
second_false:
  br label %end
end: 
  %result = phi i8 [ %a, %first_false ], [ %b, %second_true ], [ %c, %second_false ] 
  ret i8 %result
}

Assuming none of the br label %end is live, and considering the only phi, as written, all predecessors will be marked live.
If I replace the phi with phi i8 [ %a, %first_false ], [ %a, %second_true ], [ %c, %second_false ] , then only %second_false is marked live.

Now, what I find annoying is that with the same edges but just changing the order of the operands, you would get a different results. For instance: phi i8 [ %c, %second_false ], [ %a, %first_false ], [ %a, %second_true ] now %second_false is *not* marked live and instead %first_false and %second_true are.

452

s/CommonReachngDefintion/CommonReachingDefinition/

[david2050]

Address comments.
Remove code that is functionally redundant.

[mehdi_amini]

lib/Transforms/Scalar/ADCE.cpp

445

Sorry missed this one: S/tis/this

[david2050]

lib/Transforms/Scalar/ADCE.cpp

450

You are correct the it is sensitive to the order. Marking one is sufficient for correctness. I have considered marking the lexically first one as live which would provide more stability but it is a rare occurrence so it is not clear if it is worth fixing. I don't have any collected data on this.

[david2050]

fix typo

[david2050]

lib/Transforms/Scalar/ADCE.cpp

450

I ran an experiment by prioritize that we keep the lexically last defined value. This should bias toward forcing live earlier branch decisions which are likely to be forced live anyway if we mark a later branch live. This had minimal impact on the my set of C++ tests (two changes, in different directions).

[• dberlin]

lib/Transforms/Scalar/ADCE.cpp

463

I'm curious why you bother with this detection?
Pretty much every other pass we have can already do a better job of it :)
That is, they can determine not just if they are dead or trivially equivalent, but produce equivalent values.

You are basically detecting the block is not necessary to produce that value to the phi node.
That's, IMHO, more of a redundancy elimination technique than a dead code one.
The code isn't dead, it's just equivalent to some other code.
Or am i missing something?

Do you have examples where the standard pass pipeline doesn't remove the block producing the equivalent value?

[david2050]

lib/Transforms/Scalar/ADCE.cpp

463

This step is necessary otherwise we delete a branch which determines a live value. It is an artifact of the semantics of PHI nodes. This is about preserving existing structure not translating to a new form.

And Yes, outside of loops, the baseline code catches almost all cases. The primary motivation was dead, may-be-infinute loops.

[• dberlin]

lib/Transforms/Scalar/ADCE.cpp

463

I understand the semantics of phi nodes :)

I'm asking why you don't just mark them *all* live.
Traditionally, in DCE, what would happen is that if the phi is live, you mark all values that are incoming to the phi as live (and in a control dependence DCE, any control dependences of the necessary edges)

Here, it seems like you are trying to figure out if the phi is useless by seeing if all branches have the same incoming value, and if so, you are arbitrarily choosing one so you can delete at least one branch.
That seems .. pointless.

It should only also matter in the case of either predecessors that only exist for control flow (IE empty basic blocks), or critical edges.

The only interesting loop case i'm aware of where this matters is:
if (b)
{
int i;
for (i = 0; i<1000; ++i);
j = 0;
}
return j;
}

But your current code won't allow deleting the loop in this case, AFAICT.
(among other things, you would need to determine what the control dependence would look like if the critical edge was split without splitting it. This is what GCC does)

[• dberlin]

lib/Transforms/Scalar/ADCE.cpp

463

(and to be super clear, when i say "I'm asking why you don't just mark them *all* live.", i mean "all the arguments and edges of a given phi node", not "all phis").

[david2050]

lib/Transforms/Scalar/ADCE.cpp

463

It is not all branches, it is all branches from dead predecessors since in the case that we should remove all such predecessors to be replaced with a single edge, we verify that there is a unique value for that edge. If not we select one predecessor to keep live. Consider

a = 0
if (x) { 
      if (y) a =1
      else  a = 2
 }
 else a  =3
 phi(...)

The phi node following this block has tree edges labeled with values 1,2,3 respectively.
The guarded basic blocks are empty because the assignments are folded into the phi node.
The branch decision at which tests 'y' is dead at this point because there are no live operations
in any block it controls.
Here we determine that we need to keep at least one of the empty blocks around to distinguish between 1 and 2, which models the behavior if the assignments to 'a' were instead explicitly in the original blocks.

Given a more complex example we might have

a = 0
if (x) { 
      if (z)  
         a=1
      else { 
         if (y)  { }  
         else { } 
      }
 }
 else a  =3
 phi(...)

Here there are 4 predecessors to the join, three are 2 but only two distinct values and we only
need to have the branch on 'z' live. The branch on 'y' need not be. This is why the code does not mark
all incoming edges live but does not do the extra work to try and pick and optimal choice (the path with a=1 in this case). The scenario is rare enough that it is not clear extra work is worth the effort.

In your example, I believe the current code will allow the remove the loop since the assignment to J is not control dependent on the loop but only on the branch testing 'b'. The subset of the CFG corresponding to the loop would be all marked dead and removed and the edge leaving the block holding the test on 'b' redirected to the block holding 'j=0'. I don't understand your reference to splitting a critical edge.

[• dberlin]

lib/Transforms/Scalar/ADCE.cpp

463

(Sorry if this is short, i lost this comment once already).
Okay, we are talking past each other.
I understand what you are doing, and why you are trying to mark only certain values of a phi live.
I'm saying "this is not worth it, and is complex" *compared to just marking all of them*. You produced an example showing it removes a single block. I agree it can remove that block.
Instead of arguing by example, i produced data:

I ran your patch on ~5000 C++ packages as is, and then ran it on ~5000 C++ packages with it changed to just mark all phi node inputs as live when the phi node is live.

The number of cases i find where it makes a difference is ~0.01%.
The average size of the binaries in which it does something are ~16 bytes smaller (which, for those binaries, amounts to an average size change of 0.00005%)

That seems "not worth it" to me :)

Now, i'm just trying to provide data not actually to say "we shouldn't do it this way", but more "if we are going to add complexity, let's do it where we have data that shows it's worth it". We both can clearly come up with contrived examples where it matters.

So if you have data showing trying to only mark single branches of unique values live is worth it, great, add the data and let's stop arguing, and let's do it.

"In your example, I believe the current code will allow the remove the loop since the assignment to J is not control dependent on the loop but only on the branch testing 'b'. The subset of the CFG corresponding to the loop would be all marked dead and removed and the edge leaving the block holding the test on 'b' redirected to the block holding 'j=0'. I don't understand your reference to splitting a critical edge."

You should try it before you knock it :)

You may have to change it to j=b or add a new parameter somewhere, depending on what passes you run before it (otherwise the phi ends up with the constant propagated into it).

You will end up with a phi node in the end block that merges the else-condition value (IE from outside the condition entirely) of jwith the inside-condition value. Control-dependence will force you to keep the empty loop live due to the critical edge (again, whether the edge stays critical or not depends on where you end up in the pass pipeline)

This case is more common, it affects at least ~1% of the *packages*.
I did not fix it, so i can't say how much it saves or not saves.
It is common enough that gcc special cases it (as i said) and has regression tests to make sure the loop is eliminated by DCE.

[david2050]

lib/Transforms/Scalar/ADCE.cpp

463

Thanks for great due diligence for the patch.

The experiment you ran seems doomed because the patches submitted so far are incomplete. If you look around line 305 there is loop which forces all branches live. This is temporary waiting for the next patch which includes the code to delete branches. Right now the patch reduces to prior behavior of not actually deleting in branches although it takes a long way to get there. Thus any changes you see based on your edit are curious since it should not have any impact on the generated code at all.

I certainly agree that even the relatively simple pick-one-value here may have no value. Perhaps we can accept this change as is, with a TODO to evaluate this point after the next (and final) patch is up? (Assuming there is nothing else to change along the way)

[• dberlin]

lib/Transforms/Scalar/ADCE.cpp

463

I feel like you are implying something here.

In this case, I simply hacked in the right parts of the rest of the old patch (and a little work) before it was broken up before running the experiment. (You could have simply asked for the code if you are concerned).

You are talking about something that is < 50 lines of code to make work (control dependence DCE is not that hard, nor is this even the first implementation of it in LLVM!), so i'm not sure why you would think i didn't run the experiment properly?
(I could also point out i don't actually care about correctness of the generated code, only the maximum optimization value)

If you would like to actually run *your own experiment* show that this is worth it, you are, as i said, welcome. You may want to focus on that instead of trying to pick mine apart ;)

Right now, like I said, i see *nothing* that makes it seem like this is worth it, and your response here doesn't help that. If you want to produce data that says it's worth it, great!. Otherwise, I'm loathe to start by adding complexity and then try to take it away later. That never works.

[david2050]

lib/Transforms/Scalar/ADCE.cpp

463

No implications, and apologies for suggesting you were incomplete in your analysis.

To be clear then, in your variant, you marked every basic block which is a predecessor of a live-phi as live?

[david2050]

I ran this test:

int foo(int a, int b, int N) {
  int j = 0;
  if (b) {
    int i;
    for (i = 0; i < N; i++)
      ;
    j = 1;
  }
  return j;
}

compiled to bc and then processed: opt -sroa -adce -adce-remove-loops and it did successfully remove the loop. I also tried this variant

int foo(int b, int N) {
  int j = 0;
  if (b) {
    int i;
    j = 1;
    for (i = 0; i < N; i++)
      ;
  }
  return j;
}

The final output for that one looked like:

define i32 @foo(i32 %b, i32 %N) #0 {
  %1 = icmp ne i32 %b, 0
  br i1 %1, label %2, label %3

; <label>:2:                                      ; preds = %0
  br label %3

; <label>:3:                                      ; preds = %2, %0
  %j.0 = phi i32 [ 0, %0 ], [ 1, %2 ]
  ret i32 %j.0
}

[david2050]

This snippet

int foo(int b, int j, int N) {
  if (b) {
    int i;
    for (i = 0; i < N; i++)
      ;
    j =	0;
  }
  return j;
}

via

clang -c -emit-llvm -O0 ...
opt -sroa -adce -adce-remove-loops -S ...

generates

define i32 @foo(i32 %b, i32 %j, i32 %N) #0 {
  %1 = icmp ne i32 %b, 0
  br i1 %1, label %2, label %3

; <label>:2:                                      ; preds = %0
  br label %3

; <label>:3:                                      ; preds = %2, %0
  %.0 = phi i32 [ %j, %0 ], [ 0, %2 ]
  ret i32 %.0
}

[david2050]

Change handling of PHI nodes to force predecessors live

[david2050]

Introduce CFLive field to mark blocks whose control dependence sources should be live; use this for PHI predecessors and blocks with live operations

[david2050]

ping

[mehdi_amini]

A lot simpler now!

LGTM, thanks.

[majnemer]

lib/Transforms/Scalar/ADCE.cpp

371

I don't think you need llvm:: here.

374

Needs a space after 'if'

[david2050]

lib/Transforms/Scalar/ADCE.cpp

371

stupid xcode autocompletion :-)

[david2050]

Respond to David's comments

[majnemer]

LGTM

lib/Transforms/Scalar/ADCE.cpp

class AggressiveDeadCodeElimination {
   /// Return true for instrumentation instructions for value profiling.
   bool isInstrumentsConstant(Instruction &I);
 
   /// Propagate liveness to reaching definitions.
   void markLiveInstructions();
   /// Mark an instruction as live.
   void markLive(Instruction *I);
 
+  /// A PHI node records values associated with different paths in the
+  /// control flow graph as if a logical copy operation was performed from
+  /// an input value to the named value of the PHI node. Here we identify
+  /// where multiple distinct values reach a live PHI node from otherwise
+  /// dead predecessors. We force some predecessors terminators to be live
+  /// effectively live so that the control which determines the final values
+  /// is preserved.
+  void markLivePhiNodeInputs();
+  void markLivePhiNodeInputs(BasicBlock *BB);
+
   /// Record the Debug Scopes which surround live debug information.
   void collectLiveScopes(const DILocalScope &LS);
   void collectLiveScopes(const DILocation &DL);
 
   /// Analyze dead branches to find those whose branches are the sources
   /// of control dependences impacting a live block. Those branches are
   /// marked live.
   void markLiveBranchesFromControlDependences();
if (Function *Callee = CI->getCalledFunction())
         if (isa<Constant>(CI->getArgOperand(0)))
           return true;
   return false;
 }
 
 void AggressiveDeadCodeElimination::markLiveInstructions() {
 
   // Propagate liveness backwards to operands.
+  bool PhiNodeInputsChecked = false;
   do {
     // Worklist holds newly discovered live instructions
     // where we need to mark the inputs as live.
     while (!Worklist.empty()) {
       Instruction *LiveInst = Worklist.pop_back_val();
+      DEBUG(dbgs() << "work live: "; LiveInst->dump(););
 
       // Collect the live debug info scopes attached to this instruction.
       if (const DILocation *DL = LiveInst->getDebugLoc())
         collectLiveScopes(*DL);
 
-      DEBUG(dbgs() << "work live: "; LiveInst->dump(););
       for (Use &OI : LiveInst->operands())
         if (Instruction *Inst = dyn_cast<Instruction>(OI))
           markLive(Inst);
     }
     markLiveBranchesFromControlDependences();
 
+    // After we have incorporated all data and control flow effects, make
+    // a scan of phi nodes to make sure there are no situations where the
+    // effects of a branch are realized only in different reaching values
+    // at a live phi node.
+    if (Worklist.empty() && !PhiNodeInputsChecked) {
+      PhiNodeInputsChecked = true;
+      markLivePhiNodeInputs();
+    }
+
     if (Worklist.empty()) {
       // Temporary until we can actually delete branches.
       SmallVector<TerminatorInst *, 16> DeadTerminators;
       for (auto *BB : BlocksWithDeadTerminators)
         DeadTerminators.push_back(BB->getTerminator());
       for (auto *I : DeadTerminators)
         markLive(I);
       assert(BlocksWithDeadTerminators.empty());
       // End temporary.
     }
   } while (!Worklist.empty());
 
   assert(BlocksWithDeadTerminators.empty());
 }
 
 void AggressiveDeadCodeElimination::markLive(Instruction *I) {
 
   auto &Info = InstInfo[I];
   if (Info.Live)
     return;
 
   DEBUG(dbgs() << "mark live: "; I->dump());
   Info.Live = true;
   Worklist.push_back(I);
 
   // Mark the containing block live
   auto &BBInfo = *Info.Block;
   if (BBInfo.Terminator == I)
     BlocksWithDeadTerminators.erase(BBInfo.BB);
   if (BBInfo.Live)
     return;
 
void AggressiveDeadCodeElimination::collectLiveScopes(const DILocation &DL) {
   // Collect live scopes from the scope chain.
   collectLiveScopes(*DL.getScope());
 
   // Tail-recurse through the inlined-at chain.
   if (const DILocation *IA = DL.getInlinedAt())
     collectLiveScopes(*IA);
 }
 
 void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() {
 
   if (BlocksWithDeadTerminators.empty())
     return;
 
   DEBUG({
     dbgs() << "new live blocks:\n";
     for (auto *BB : NewLiveBlocks)
       dbgs() << "\t" << BB->getName() << '\n';
     dbgs() << "dead terminator blocks:\n";
     for (auto *BB : BlocksWithDeadTerminators)
       dbgs() << "\t" << BB->getName() << '\n';
void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() {
 
   // Dead terminators which control live blocks are now marked live.
   for (auto BB : IDFBlocks) {
     DEBUG(dbgs() << "live control in: " << BB->getName() << '\n');
     markLive(BB->getTerminator());
   }
 }
 
+void AggressiveDeadCodeElimination::markLivePhiNodeInputs() {
+  SmallPtrSet<BasicBlock *, 16> LiveJoinBlocks;
+
+  // Find all successors of blocks with dead terminators
+  // and mark the live phi nodes in them.
+  SmallVector<BasicBlock *, 16> Elements(BlocksWithDeadTerminators.begin(),
+                                         BlocksWithDeadTerminators.end());
+  for (auto *BB : Elements)
+    for (auto *SuccBB : successors(BB))
+      if (LiveJoinBlocks.insert(SuccBB).second)
+        markLivePhiNodeInputs(SuccBB);
+}
+
+void AggressiveDeadCodeElimination::markLivePhiNodeInputs(BasicBlock *BB) {
+  auto &Info = BlockInfo[BB];
+  if (!Info.Live)
+    return;
+  // Iterate over all live PHINodes.
+  for (auto it = BB->begin(); auto *PN = dyn_cast<PHINode>(it); ++it) {
+    if (!isLive(PN))
+      continue;
+
+    // A PHI node has implicit assignments along the control flow edges from
+    // predecessors and these implicit assignments may induce a control
+    // dependences that is not visible in the data flow.
+    
+    // As an example:
+    
+    // %tobool = icmp ne i32 %a, 0
+    // br i1 %tobool, label %cond.true, label %cond.false
+    //
+    // cond.true:                           ; preds = %entry
+    // br label %cond.end
+    //
+    // cond.false:                          ; preds = %entry
+    // br label %cond.end
+    //
+    // cond.end:                            ; preds = %cond.false, %cond.true
+    // %cond = phi i32 [ %b, %cond.true ], [ %c, %cond.false ]
+    
+    // In tis example, there are no live instructions determined by the
+    // first branch but it does determine the value which is assigned into
+    // %cond as if there were copy operations in the two empty blocks.
+    // We detected the multiple distinct values from dead predecessors and
+    // force some predecessors live (such as "br label %end" in block
+    // "cond.false") to correctly model the control dependence.
+    
+    Value *CommonReachngDefinition = nullptr;
+    auto NumIdx = PN->getNumIncomingValues();
+    for (unsigned Idx = 0; Idx < NumIdx; ++Idx) {
+      auto PredTerm = PN->getIncomingBlock(Idx)->getTerminator();
+      if (isLive(PredTerm))
+        continue;
+      auto *Value = PN->getIncomingValue(Idx);
+      if (!CommonReachngDefinition) {
+        CommonReachngDefinition = Value;
+        continue;
+      }
+      if (CommonReachngDefinition != Value) {
+        // When there are two definitions from "dead" predecessor paths we
+        // preserve one of those paths so the two values can be distinguished.
+        DEBUG(dbgs() << "Live due to phi conflict "; PredTerm->dump());
+        markLive(PredTerm);
+      }
+    }
+  }
+}
+
+//===----------------------------------------------------------------------===//
+//
+//  Routines to update the CFG and SSA information before removing dead code.
+//
+//===----------------------------------------------------------------------===//
 bool AggressiveDeadCodeElimination::removeDeadInstructions() {
 
   // The inverse of the live set is the dead set.  These are those instructions
   // which have no side effects and do not influence the control flow or return
   // value of the function, and may therefore be deleted safely.
   // NOTE: We reuse the Worklist vector here for memory efficiency.
   for (Instruction &I : instructions(F)) {
     // Check if the instruction is alive.