diff options
Diffstat (limited to 'contrib/llvm-project/llvm/lib/Transforms/Vectorize/VPlanPredicator.cpp')
| -rw-r--r-- | contrib/llvm-project/llvm/lib/Transforms/Vectorize/VPlanPredicator.cpp | 248 |
1 files changed, 0 insertions, 248 deletions
diff --git a/contrib/llvm-project/llvm/lib/Transforms/Vectorize/VPlanPredicator.cpp b/contrib/llvm-project/llvm/lib/Transforms/Vectorize/VPlanPredicator.cpp deleted file mode 100644 index e879a33db6ee..000000000000 --- a/contrib/llvm-project/llvm/lib/Transforms/Vectorize/VPlanPredicator.cpp +++ /dev/null @@ -1,248 +0,0 @@ -//===-- VPlanPredicator.cpp -------------------------------------*- C++ -*-===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -/// -/// \file -/// This file implements the VPlanPredicator class which contains the public -/// interfaces to predicate and linearize the VPlan region. -/// -//===----------------------------------------------------------------------===// - -#include "VPlanPredicator.h" -#include "VPlan.h" -#include "llvm/ADT/DepthFirstIterator.h" -#include "llvm/ADT/GraphTraits.h" -#include "llvm/ADT/PostOrderIterator.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" - -#define DEBUG_TYPE "VPlanPredicator" - -using namespace llvm; - -// Generate VPInstructions at the beginning of CurrBB that calculate the -// predicate being propagated from PredBB to CurrBB depending on the edge type -// between them. For example if: -// i. PredBB is controlled by predicate %BP, and -// ii. The edge PredBB->CurrBB is the false edge, controlled by the condition -// bit value %CBV then this function will generate the following two -// VPInstructions at the start of CurrBB: -// %IntermediateVal = not %CBV -// %FinalVal = and %BP %IntermediateVal -// It returns %FinalVal. -VPValue *VPlanPredicator::getOrCreateNotPredicate(VPBasicBlock *PredBB, - VPBasicBlock *CurrBB) { - VPValue *CBV = PredBB->getCondBit(); - - // Set the intermediate value - this is either 'CBV', or 'not CBV' - // depending on the edge type. - EdgeType ET = getEdgeTypeBetween(PredBB, CurrBB); - VPValue *IntermediateVal = nullptr; - switch (ET) { - case EdgeType::TRUE_EDGE: - // CurrBB is the true successor of PredBB - nothing to do here. - IntermediateVal = CBV; - break; - - case EdgeType::FALSE_EDGE: - // CurrBB is the False successor of PredBB - compute not of CBV. - IntermediateVal = Builder.createNot(CBV, {}); - break; - } - - // Now AND intermediate value with PredBB's block predicate if it has one. - VPValue *BP = PredBB->getPredicate(); - if (BP) - return Builder.createAnd(BP, IntermediateVal, {}); - else - return IntermediateVal; -} - -// Generate a tree of ORs for all IncomingPredicates in WorkList. -// Note: This function destroys the original Worklist. -// -// P1 P2 P3 P4 P5 -// \ / \ / / -// OR1 OR2 / -// \ | / -// \ +/-+ -// \ / | -// OR3 | -// \ | -// OR4 <- Returns this -// | -// -// The algorithm uses a worklist of predicates as its main data structure. -// We pop a pair of values from the front (e.g. P1 and P2), generate an OR -// (in this example OR1), and push it back. In this example the worklist -// contains {P3, P4, P5, OR1}. -// The process iterates until we have only one element in the Worklist (OR4). -// The last element is the root predicate which is returned. -VPValue *VPlanPredicator::genPredicateTree(std::list<VPValue *> &Worklist) { - if (Worklist.empty()) - return nullptr; - - // The worklist initially contains all the leaf nodes. Initialize the tree - // using them. - while (Worklist.size() >= 2) { - // Pop a pair of values from the front. - VPValue *LHS = Worklist.front(); - Worklist.pop_front(); - VPValue *RHS = Worklist.front(); - Worklist.pop_front(); - - // Create an OR of these values. - VPValue *Or = Builder.createOr(LHS, RHS, {}); - - // Push OR to the back of the worklist. - Worklist.push_back(Or); - } - - assert(Worklist.size() == 1 && "Expected 1 item in worklist"); - - // The root is the last node in the worklist. - VPValue *Root = Worklist.front(); - - // This root needs to replace the existing block predicate. This is done in - // the caller function. - return Root; -} - -// Return whether the edge FromBlock -> ToBlock is a TRUE_EDGE or FALSE_EDGE -VPlanPredicator::EdgeType -VPlanPredicator::getEdgeTypeBetween(VPBlockBase *FromBlock, - VPBlockBase *ToBlock) { - unsigned Count = 0; - for (VPBlockBase *SuccBlock : FromBlock->getSuccessors()) { - if (SuccBlock == ToBlock) { - assert(Count < 2 && "Switch not supported currently"); - return (Count == 0) ? EdgeType::TRUE_EDGE : EdgeType::FALSE_EDGE; - } - Count++; - } - - llvm_unreachable("Broken getEdgeTypeBetween"); -} - -// Generate all predicates needed for CurrBlock by going through its immediate -// predecessor blocks. -void VPlanPredicator::createOrPropagatePredicates(VPBlockBase *CurrBlock, - VPRegionBlock *Region) { - // Blocks that dominate region exit inherit the predicate from the region. - // Return after setting the predicate. - if (VPDomTree.dominates(CurrBlock, Region->getExit())) { - VPValue *RegionBP = Region->getPredicate(); - CurrBlock->setPredicate(RegionBP); - return; - } - - // Collect all incoming predicates in a worklist. - std::list<VPValue *> IncomingPredicates; - - // Set the builder's insertion point to the top of the current BB - VPBasicBlock *CurrBB = cast<VPBasicBlock>(CurrBlock->getEntryBasicBlock()); - Builder.setInsertPoint(CurrBB, CurrBB->begin()); - - // For each predecessor, generate the VPInstructions required for - // computing 'BP AND (not) CBV" at the top of CurrBB. - // Collect the outcome of this calculation for all predecessors - // into IncomingPredicates. - for (VPBlockBase *PredBlock : CurrBlock->getPredecessors()) { - // Skip back-edges - if (VPBlockUtils::isBackEdge(PredBlock, CurrBlock, VPLI)) - continue; - - VPValue *IncomingPredicate = nullptr; - unsigned NumPredSuccsNoBE = - VPBlockUtils::countSuccessorsNoBE(PredBlock, VPLI); - - // If there is an unconditional branch to the currBB, then we don't create - // edge predicates. We use the predecessor's block predicate instead. - if (NumPredSuccsNoBE == 1) - IncomingPredicate = PredBlock->getPredicate(); - else if (NumPredSuccsNoBE == 2) { - // Emit recipes into CurrBlock if required - assert(isa<VPBasicBlock>(PredBlock) && "Only BBs have multiple exits"); - IncomingPredicate = - getOrCreateNotPredicate(cast<VPBasicBlock>(PredBlock), CurrBB); - } else - llvm_unreachable("FIXME: switch statement ?"); - - if (IncomingPredicate) - IncomingPredicates.push_back(IncomingPredicate); - } - - // Logically OR all incoming predicates by building the Predicate Tree. - VPValue *Predicate = genPredicateTree(IncomingPredicates); - - // Now update the block's predicate with the new one. - CurrBlock->setPredicate(Predicate); -} - -// Generate all predicates needed for Region. -void VPlanPredicator::predicateRegionRec(VPRegionBlock *Region) { - VPBasicBlock *EntryBlock = cast<VPBasicBlock>(Region->getEntry()); - ReversePostOrderTraversal<VPBlockBase *> RPOT(EntryBlock); - - // Generate edge predicates and append them to the block predicate. RPO is - // necessary since the predecessor blocks' block predicate needs to be set - // before the current block's block predicate can be computed. - for (VPBlockBase *Block : RPOT) { - // TODO: Handle nested regions once we start generating the same. - assert(!isa<VPRegionBlock>(Block) && "Nested region not expected"); - createOrPropagatePredicates(Block, Region); - } -} - -// Linearize the CFG within Region. -// TODO: Predication and linearization need RPOT for every region. -// This traversal is expensive. Since predication is not adding new -// blocks, we should be able to compute RPOT once in predication and -// reuse it here. This becomes even more important once we have nested -// regions. -void VPlanPredicator::linearizeRegionRec(VPRegionBlock *Region) { - ReversePostOrderTraversal<VPBlockBase *> RPOT(Region->getEntry()); - VPBlockBase *PrevBlock = nullptr; - - for (VPBlockBase *CurrBlock : RPOT) { - // TODO: Handle nested regions once we start generating the same. - assert(!isa<VPRegionBlock>(CurrBlock) && "Nested region not expected"); - - // Linearize control flow by adding an unconditional edge between PrevBlock - // and CurrBlock skipping loop headers and latches to keep intact loop - // header predecessors and loop latch successors. - if (PrevBlock && !VPLI->isLoopHeader(CurrBlock) && - !VPBlockUtils::blockIsLoopLatch(PrevBlock, VPLI)) { - - LLVM_DEBUG(dbgs() << "Linearizing: " << PrevBlock->getName() << "->" - << CurrBlock->getName() << "\n"); - - PrevBlock->clearSuccessors(); - CurrBlock->clearPredecessors(); - VPBlockUtils::connectBlocks(PrevBlock, CurrBlock); - } - - PrevBlock = CurrBlock; - } -} - -// Entry point. The driver function for the predicator. -void VPlanPredicator::predicate() { - // Predicate the blocks within Region. - predicateRegionRec(cast<VPRegionBlock>(Plan.getEntry())); - - // Linearlize the blocks with Region. - linearizeRegionRec(cast<VPRegionBlock>(Plan.getEntry())); -} - -VPlanPredicator::VPlanPredicator(VPlan &Plan) - : Plan(Plan), VPLI(&(Plan.getVPLoopInfo())) { - // FIXME: Predicator is currently computing the dominator information for the - // top region. Once we start storing dominator information in a VPRegionBlock, - // we can avoid this recalculation. - VPDomTree.recalculate(*(cast<VPRegionBlock>(Plan.getEntry()))); -} |