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

[fhahn]

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.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8773

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.

8782–8783

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

8901

Split off to b1115f8ccefb380824a9d997622cc84fc0d84a89

llvm/lib/Transforms/Vectorize/VPlan.cpp

717

Added a comment, thanks!

719

Updated, thanks!

llvm/lib/Transforms/Vectorize/VPlan.h

2566

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

321

Adjusted, thanks!

322

Added, thanks!

328

Updated, thanks!

329

added, thanks!

348–349

Adjusted naming, thanks!

348–349

Indeed, removed, thanks!

353–354

Adjusted, thanks!

356

Indeed, removed, thanks!

357

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.

409–410

This code is now gone, based on D159136

409–410

Adjusted, thanks!

410

Adjusted, thanks!

[Ayal]

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

712

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

2564–2568

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

181

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).

184

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

185

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

193

Better to assert isHeaderBB(BB, LoopOfBB) here?

194

323

323

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

356

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?

366–368

368–370

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

400–401

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

[fhahn]

Address latest comments, thanks!

In D158333#4654821, @Ayal wrote:

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]

In D158333#4654836, @fhahn wrote:

Address latest comments, thanks!

In D158333#4654821, @Ayal wrote:

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]

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

llvm/lib/Transforms/Vectorize/VPlan.cpp

712

Will do separately, thanks!

llvm/lib/Transforms/Vectorize/VPlan.h

2564–2568

Clarified, thanks!

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

181

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.

184

Added assert, thanks!

193

added assert, thanks!

194

Simplified, thanks!

323

Added the note, thanks!

366–368

Adjusted, thanks!

368–370

Clarified, thanks!

400–401

Clarified, thanks!

[Ayal]

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

177

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.)

180–181

This assert to be removed now?

181

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;
}

326

fold this into its natural place in getOrCreateVPBB()?

353–354

fold this into its natural place in getOrCreateVPBB()?

353–354

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

[fhahn]

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

177

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

180–181

removed, thanks!

181

Updated, thanks!

326

Done, thanks!

353–354

Done, thanks!

353–354

Done, thanks!

[fhahn]

In D158333#4656541, @Ayal wrote:

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]

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

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8783

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

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

171

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.

188

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

195

?

323

324

353–354

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]

Address comments, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8783

Added, thanks!

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

171

Adjusted, thanks!

188

Forgot about this one, added, thanks!

195

Adjusted, thanks!

323

Adjusted, thanks!

324

Adjusted, thanks!

353–354

Removed, thanks!

[Ayal]

Thanks, Ship it!