[llvm-dev] [llvm] r281947 - Merge branch 'ADCE5'

[David Callahan via llvm-dev]

Here is the commit message before the merge:

commit 31ef23572a34b5a72fb7fafb366f33145a65040f
Author: David Callahan <dcallahan at fb.com>
Date:   Mon Sep 19 10:35:53 2016 -0700

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

    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)

    Reviewers: nadav, mehdi_amini, majnemer

    Subscribers: dberlin, david2050, twoh, freik, llvm-commits

    Differential Revision: https://reviews.llvm.org/D23824



On 9/19/16, 4:27 PM, "davide.italiano at gmail.com on behalf of Davide
Italiano" <davide.italiano at gmail.com on behalf of davide at freebsd.org>
wrote:

>On Mon, Sep 19, 2016 at 4:17 PM, David Callahan via llvm-commits
><llvm-commits at lists.llvm.org> wrote:
>> Author: david2050
>> Date: Mon Sep 19 18:17:58 2016
>> New Revision: 281947
>>
>> URL: 
>>https://urldefense.proofpoint.com/v2/url?u=http-3A__llvm.org_viewvc_llvm-
>>2Dproject-3Frev-3D281947-26view-3Drev&d=DQIBaQ&c=5VD0RTtNlTh3ycd41b3MUw&r
>>=lFyiPUrFdOHdaobP7i4hoA&m=aF4YjS_zffE7xmWFF3NHixWmJDryeTmgfitEV2eM6uM&s=5
>>S3QnxofIoK-gW1X9ECn8uoglysRzrFnV0jSKwZZtN0&e=
>> Log:
>> Merge branch 'ADCE5'
>>
>
>Uh, could you provide a saner commit message next time? :)
>
>> Modified:
>>     llvm/trunk/lib/Transforms/Scalar/ADCE.cpp
>>
>> Modified: llvm/trunk/lib/Transforms/Scalar/ADCE.cpp
>> URL: 
>>https://urldefense.proofpoint.com/v2/url?u=http-3A__llvm.org_viewvc_llvm-
>>2Dproject_llvm_trunk_lib_Transforms_Scalar_ADCE.cpp-3Frev-3D281947-26r1-3
>>D281946-26r2-3D281947-26view-3Ddiff&d=DQIBaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=l
>>FyiPUrFdOHdaobP7i4hoA&m=aF4YjS_zffE7xmWFF3NHixWmJDryeTmgfitEV2eM6uM&s=dL0
>>ax0P5ToacB94_q2QZBWFwmnsJsBpUDI6lb9WVxZI&e=
>> 
>>=========================================================================
>>=====
>> --- llvm/trunk/lib/Transforms/Scalar/ADCE.cpp (original)
>> +++ llvm/trunk/lib/Transforms/Scalar/ADCE.cpp Mon Sep 19 18:17:58 2016
>> @@ -58,6 +58,10 @@ struct BlockInfoType {
>>    bool Live = false;
>>    /// True when this block ends in an unconditional branch.
>>    bool UnconditionalBranch = false;
>> +  /// True when this block is known to have live PHI nodes.
>> +  bool HasLivePhiNodes = false;
>> +  /// Control dependence sources need to be live for this block.
>> +  bool CFLive = false;
>>
>>    /// Quick access to the LiveInfo for the terminator,
>>    /// holds the value &InstInfo[Terminator]
>> @@ -109,6 +113,9 @@ class AggressiveDeadCodeElimination {
>>    void markLiveInstructions();
>>    /// Mark an instruction as live.
>>    void markLive(Instruction *I);
>> +
>> +  /// Mark terminators of control predecessors of a PHI node live.
>> +  void markPhiLive(PHINode *PN);
>>
>>    /// Record the Debug Scopes which surround live debug information.
>>    void collectLiveScopes(const DILocalScope &LS);
>> @@ -269,15 +276,18 @@ void AggressiveDeadCodeElimination::mark
>>      // 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);
>> +
>> +      if (auto *PN = dyn_cast<PHINode>(LiveInst))
>> +        markPhiLive(PN);
>>      }
>>      markLiveBranchesFromControlDependences();
>>
>> @@ -315,7 +325,10 @@ void AggressiveDeadCodeElimination::mark
>>
>>    DEBUG(dbgs() << "mark block live: " << BBInfo.BB->getName() << '\n');
>>    BBInfo.Live = true;
>> -  NewLiveBlocks.insert(BBInfo.BB);
>> +  if (!BBInfo.CFLive) {
>> +    BBInfo.CFLive = true;
>> +    NewLiveBlocks.insert(BBInfo.BB);
>> +  }
>>
>>    // Mark unconditional branches at the end of live
>>    // blocks as live since there is no work to do for them later
>> @@ -348,6 +361,25 @@ void AggressiveDeadCodeElimination::coll
>>      collectLiveScopes(*IA);
>>  }
>>
>> +void AggressiveDeadCodeElimination::markPhiLive(PHINode *PN) {
>> +  auto &Info = BlockInfo[PN->getParent()];
>> +  // Only need to check this once per block.
>> +  if (Info.HasLivePhiNodes)
>> +    return;
>> +  Info.HasLivePhiNodes = true;
>> +
>> +  // If a predecessor block is not live, mark it as control-flow live
>> +  // which will trigger marking live branches upon which
>> +  // that block is control dependent.
>> +  for (auto *PredBB : predecessors(Info.BB)) {
>> +    auto &Info = BlockInfo[PredBB];
>> +    if (!Info.CFLive) {
>> +      Info.CFLive = true;
>> +      NewLiveBlocks.insert(PredBB);
>> +    }
>> +  }
>> +}
>> +
>>  void 
>>AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() {
>>
>>    if (BlocksWithDeadTerminators.empty())
>> @@ -382,6 +414,11 @@ void AggressiveDeadCodeElimination::mark
>>    }
>>  }
>>
>> 
>>+//===-------------------------------------------------------------------
>>---===//
>> +//
>> +//  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
>>
>>
>> _______________________________________________
>> llvm-commits mailing list
>> llvm-commits at lists.llvm.org
>> 
>>https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.llvm.org_cgi-2D
>>bin_mailman_listinfo_llvm-2Dcommits&d=DQIBaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=l
>>FyiPUrFdOHdaobP7i4hoA&m=aF4YjS_zffE7xmWFF3NHixWmJDryeTmgfitEV2eM6uM&s=mGB
>>ELsqyo--1-TSIzg5j3k_ow1LyEia8CFhTdi2h0a8&e=
>
>-- 
>Davide
>
>"There are no solved problems; there are only problems that are more
>or less solved" -- Henri Poincare