This is an archive of the discontinued LLVM Phabricator instance.

[VPlan] Move initial skeleton construction to createInitialVPlan. (NFC)
ClosedPublic

Authored by fhahn on Aug 19 2023, 7:23 AM.

Details

Summary

This patch moves creating the middle VPBBs and an initial empty
vector loop region for the top-level loop to createInitialVPlan.

This consolidates code to create the initial VPlan skeleton and enables
adding other bits outside the main region during initial VPlan
construction. In particular, D150398 will add the exit check & branch to
the middle block.

Diff Detail

Event Timeline

fhahn created this revision.Aug 19 2023, 7:23 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 19 2023, 7:23 AM
fhahn requested review of this revision.Aug 19 2023, 7:23 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 19 2023, 7:23 AM
Herald added subscribers: wangpc, vkmr. · View Herald Transcript
Ayal added inline comments.Aug 28 2023, 4:55 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
8792

Moving the creation of top region and middle block into createInitialVPlan looks good, and follows the description above, except for the last sentence. Documentation of createInitialVPlan() in VPlan.h needs updating to keep in sync.
The initial VPlan conceptually consists of pre-header, top-region, and exit, all representing existing IR "in-place". A vector-pre-header is also part if the initial VPlan, currently.

The last sentence above: filling the top-region with header, latch, followed by VPBB's in-between, should take place as independent steps (VPlan-to-VPlan transforms), potentially after caching a cloned copy of the original "in-place" top-region to be used for fallback and/or remainder loops. Possibly as follow-up patches.

8801–8802

Comment line dropped accidentally? BTW, not sure I follow why splitting the range is avoided here nor how taking a uniform conservative decision across all VF's in Range relates to UF being unknown(?).

8919

nit: independent cleanup?

llvm/lib/Transforms/Vectorize/VPlan.cpp
718

nit: worth a comment that the top region is initially constructed empty here, as a placeholder, to be filled later with VPBB's for subsequent processing.

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp
107

"it will be" >> "the vector-pre-header VPBB was"?

Avoid setting both predecessors of (any) header here, i.e., early-return if BB is a header block, to avoid setting edges to predecessor only to be discarded later?
Likewise, avoid setting successors of latch blocks below, only to be discarded later.
(Possibly as independent preparatory patch(es); make sure important orders are maintained.)

318

nit: can assign VPRegionBlock *TheRegion = Plan.getVectorLoopRegion(); and reuse it below to set

  auto *VectorPreheaderVPBB = cast<VPBasicBlock>(TheRegion->getSinglePredecessor());
  BB2VPBB[ThePreheaderBB] = VectorPreheaderVPBB;
  BB2VPBB[LoopExitBB] = cast<VPBasicBlock>(TheRegion->getSingleSuccessor());
}

Note that ThePreheaderBB is associated with both Plan.getPreheader() and Plan.getEntry(); here we're interested in the latter, which stands for Vector-Preheader.

318
345–346
350–351

drop suffix: PH->H is no longer linked, neither here nor elsewhere.

"Loop H" >> "the header block of the top region."

407–408
407–408

Could the disconnects be avoided, and top region early continue?

408
fhahn updated this revision to Diff 554487.Aug 29 2023, 1:51 PM
fhahn marked 10 inline comments as done.

Rebased on top of D159136 and address comments, thanks!

fhahn updated this revision to Diff 555338.Sep 1 2023, 5:09 AM

Rebase after updates to D159136.

Ayal added inline comments.Sep 19 2023, 4:56 AM
llvm/lib/Transforms/Vectorize/VPlan.cpp
720
llvm/lib/Transforms/Vectorize/VPlan.h
2555
llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp
319

// These were created directly rather than via getOrCreateVPBB(), revisit them now to update BB2VPBB and Loop2region.

325

nit:
auto *VectorPreheaderVPBB = cast<VPBasicBlock>(TheRegion->getSinglePredecessor());
would be more consistent with how middle VPBB is retrieved.

326

Worth noting that ThePreheaderBB conceptually corresponds to both Plan.getPreheader() (which wraps the original preheader BB) and Plan.getEntry() (which represents the new vector preheader); here we're interested in setting BB2VPBB to the latter.

345–346

Is this redundant - createInitialVPlan() already sets the name of VectorPreheaderVPBB to "vector.ph" when creating it?

355

Is setting the parent of HeaderVPBB to TheRegion redundant - getOrCreateVPBB() should have done so already?

356

Should this setEntry be done along with all others?

372–373

nit: may be simpler to handle the non-header case first, then potentially else-if the header-of-non-TheRegion case.

391–392

nit: continue if TheRegion == Region?

391–392

If Exits of regions are set here when identifying latches during successor setting, should Entries be set above when identifying headers during predecessor setting?

fhahn updated this revision to Diff 557183.Sep 21 2023, 8:40 AM

Rebase after update to D159136

fhahn updated this revision to Diff 557700.Oct 13 2023, 2:05 PM
fhahn marked 12 inline comments as done.

Rebase and address comments, thanks!

ping :)

fhahn added inline comments.Oct 13 2023, 2:06 PM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
8792

Moving the creation of top region and middle block into createInitialVPlan looks good, and follows the description above, except for the last sentence. Documentation of createInitialVPlan() in VPlan.h needs updating to keep in sync.

The initial VPlan conceptually consists of pre-header, top-region, and exit, all representing existing IR "in-place". A vector-pre-header is also part if the initial VPlan, currently.

Updated the comment in VPlan.h to be in sync with the statement here (except last sentence).

The last sentence above: filling the top-region with header, latch, followed by VPBB's in-between, should take place as independent steps (VPlan-to-VPlan transforms), potentially after caching a cloned copy of the original "in-place" top-region to be used for fallback and/or remainder loops. Possibly as follow-up patches.

Creating the header & latch VPBBs is mostly done up-front at the moment, to simplify the code for recipe creation we have now. Going forward, it should probably be possible to eventually just use the blocks created during initial VPlan construction (like in the native path currently) and what's left to do is adding the canonical induction recipes separately.

8801–8802

Ah yes, accidentally remove. Added the comment back, thanks!

8919
llvm/lib/Transforms/Vectorize/VPlan.cpp
718

Added a comment, thanks!

720

Updated, thanks!

llvm/lib/Transforms/Vectorize/VPlan.h
2555

Fixed, thanks!

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp
107

I had look at this and it turned out a bit more complicated, but overall simpler and easier to update/change in this patch: D159136

318

Adjusted, thanks!

319

Added, thanks!

325

Updated, thanks!

326

added, thanks!

345–346

Adjusted naming, thanks!

345–346

Indeed, removed, thanks!

350–351

Adjusted, thanks!

355

Indeed, removed, thanks!

356

At the other point we would need extra checks for the block being a header.

372–373

the non-header case should be handled first now

391–392

Entries are set at a different point now.

407–408

This code is now gone, based on D159136

407–408

Adjusted, thanks!

408

Adjusted, thanks!

Ayal added a comment.Oct 22 2023, 11:01 AM

In summary: "This patch moves creating the preheader and middle VPBBs as well as the
initial empty vector loop region to createInitialVPlan" - only middle VPBB and region are moved, preheader is already there.

llvm/lib/Transforms/Vectorize/VPlan.cpp
713

This should be auto Entry = new VPBasicBlock("entry") plus updating VPlan's "entry" to refer to this VPBB rather than VecPreHeader. Can be done in a separate patch.

llvm/lib/Transforms/Vectorize/VPlan.h
2553

The original scalar pre-header no longer acts as a pre-header in VPlan's skeleton and best be renamed "entry". Can be done as part of rewording VPlan's "Entry" and "VectorPreHeader" in a separate patch.

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp
180

If LoopOfBB == TheLoop then RegionExists because it was constructed in buildInitialVPlan, but the header VPBB of TheLoop is not - it gets constructed by calling getOrCreateVPBB(). I.e., that BB is exceptional in being a header (not in BB2VPBB) of an existing region (in Loop2Region).

183

Better to assert !isHeaderBB(BB, LoopOfBB) || LoopOfBB == TheLoop here?

184

(otherwise VPBB's parent gets set to a new region upon constructing the latter below.)

185

Better to assert isHeaderBB(BB, LoopOfBB) here?

191
320
320

Note that header/entry and latch/exiting VPBB's of top-level region have yet to be created.

355

OTOH, perhaps its clearer to create HeaderVPBB next to stage 0 above:

BasicBlock *HeaderBB = TheLoop->getHeader();
VPBasicBlock *HeaderVPBB = new VPBasicBlock(HeaderBB->getName());
BB2VPBB[HeaderBB] = HeaderVPBB;
HeaderVPBB->setParent(TheRegion);

thereby also slightly simplifying getOrCreateVPBB?

367–369
370

// Except for the top region, whose predecessor was set when creating VPlan's skeleton.

401

// Except for the top region, whose successor was set when creating VPlan's skeleton.

fhahn edited the summary of this revision. (Show Details)Oct 22 2023, 1:05 PM
fhahn updated this revision to Diff 557837.Oct 22 2023, 1:08 PM
fhahn marked 12 inline comments as done.

Address latest comments, thanks!

In summary: "This patch moves creating the preheader and middle VPBBs as well as the
initial empty vector loop region to createInitialVPlan" - only middle VPBB and region are moved, preheader is already there.

Adjusted, thanks!

Ayal added a comment.Nov 6 2023, 2:31 AM

Address latest comments, thanks!

In summary: "This patch moves creating the preheader and middle VPBBs as well as the
initial empty vector loop region to createInitialVPlan" - only middle VPBB and region are moved, preheader is already there.

Adjusted, thanks!

There are still some pending comments, right? In particular regarding simplifying getOrCreateVPBB() wrt the exceptional header VPBB of TheLoop.

fhahn updated this revision to Diff 558033.Nov 6 2023, 12:41 PM

Added early exit if BB is header of TheLoop to getOrCreateVPBB, also submit pending responses.

llvm/lib/Transforms/Vectorize/VPlan.cpp
713

Will do separately, thanks!

llvm/lib/Transforms/Vectorize/VPlan.h
2553

Clarified, thanks!

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp
180

Handled the case hat BB is the header of TheLoop in the early exit above, as setEntry in the caller will take care of setting the region. This simplifies the asserts below.

183

Added assert, thanks!

185

added assert, thanks!

191

Simplified, thanks!

320

Added the note, thanks!

367–369

Adjusted, thanks!

370

Clarified, thanks!

401

Clarified, thanks!

Ayal added a comment.Nov 9 2023, 2:16 PM

Still wonder if the exceptional case of top region's header VPBB could be dealt with better, if not entirely outside getOrCreateVPBB() then perhaps entirely inside it?

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp
176

Better have getOrCreateVPBB() fully handle TheLoop's header (see below), and retain this early-exit only if !LoopOfBB? (Or explain its partial treatment here - region created (and registered in Loop2Region) before the call but hooking up VPBB as its entry/parent and fixing its name is left for the caller to fix after the call.)

179–180

This assert to be removed now?

180

An alternative to early exiting, leaving setEntry to the caller, is to provide full treatment for top loop header BB; would something as follows work better, also taking care of updating Loop2Region?

  auto *RegionOfVPBB = Loop2Region.lookup(LoopOfBB);
  if (!isHeaderBB(BB, LoopOfBB)) {
    assert(RegionOfVPBB && "Region should have been created by visiting header earlier");
    VPBB->setParent(RegionOfVPBB);
    return VPBB;
  }

  // Handle a header - take care of its Region.
  assert(!RegionOfVPBB && "...");
  if (LoopOfBB == TheLoop) {
    RegionOfVPBB = Plan.getVectorLoopRegion();
  } else {
    RegionOfVPBB =
      new VPRegionBlock(BB->getName().str(), false /*isReplicator*/);
    RegionOfVPBB->setParent(Loop2Region[LoopOfBB->getParentLoop()]);
  }
  RegionOfVPBB->setEntry(VPBB);
  Loop2Region[LoopOfBB] = RegionOfVPBB;
  return VPBB;
}
323

fold this into its natural place in getOrCreateVPBB()?

353

nit: cleaner to provide the name as an (optional) parameter to getOrCreateVPBB()?

354

fold this into its natural place in getOrCreateVPBB()?

fhahn marked 6 inline comments as done.Nov 10 2023, 2:45 AM
llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp
176

Updated, thanks! The caller now doesn't add the region to Loop2Region, all headers are handled here now.

179–180

removed, thanks!

180

Updated, thanks!

323

Done, thanks!

353

Done, thanks!

354

Done, thanks!

fhahn updated this revision to Diff 558073.Nov 10 2023, 2:45 AM
fhahn marked 6 inline comments as done.

Still wonder if the exceptional case of top region's header VPBB could be dealt with better, if not entirely outside getOrCreateVPBB() then perhaps entirely inside it?

Adjusted as suggested, thanks!

Ayal added a comment.Nov 10 2023, 7:10 AM

Thanks for accommodating! A couple of final cleanups and nits.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
8802

nit: worth adding a note to revisit this comment, unless fully agreed upon?

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp
172

Alternatively, can check if isHeaderBB(BB, TheLoop) and set its name to "vector.body". This method already handles this case, and taking care of the name here would simplify and unify the caller(s) below.

Would be good if these debug messages were covered by some test.

187

... should be filled in with some message, e.g., "First visit of a header basic block expects to register its region"

192

?

320
321
354–355

If getOrCreateVPBB() takes care of all blocks equally, creating VPBB for header block of top region can be done as part of the RPO scan below, along with all other VPBB's?

fhahn updated this revision to Diff 558079.Nov 11 2023, 1:11 PM
fhahn marked 7 inline comments as done.

Address comments, thanks!

fhahn added inline comments.Nov 11 2023, 1:17 PM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
8802

Added, thanks!

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp
172

Adjusted, thanks!

187

Forgot about this one, added, thanks!

192

Adjusted, thanks!

320

Adjusted, thanks!

321

Adjusted, thanks!

354–355

Removed, thanks!

Ayal accepted this revision.Nov 11 2023, 2:36 PM

Thanks, Ship it!

This revision is now accepted and ready to land.Nov 11 2023, 2:36 PM