David Callahan via llvm-dev
2016-Sep-19 23:30 UTC
[llvm-dev] [llvm] r281947 - Merge branch 'ADCE5'
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
Mehdi Amini via llvm-dev
2016-Sep-20 16:35 UTC
[llvm-dev] [llvm] r281947 - Merge branch 'ADCE5'
Hi, Right, this is the commit that should have been pushed. I.e. do not merge when it is not fast-forward (rebase first). — Mehdi> On Sep 19, 2016, at 4:30 PM, David Callahan via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > 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 > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev