llvm/llvm/lib/Transforms/Vectorize/VPlanSLP.cpp

//===- VPlanSLP.cpp - SLP Analysis based on VPlan -------------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
/// This file implements SLP analysis based on VPlan. The analysis is based on
/// the ideas described in
///
///   Look-ahead SLP: auto-vectorization in the presence of commutative
///   operations, CGO 2018 by Vasileios Porpodas, Rodrigo C. O. Rocha,
///   Luís F. W. Góes
///
//===----------------------------------------------------------------------===//

#include "VPlan.h"
#include "VPlanValue.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <optional>
#include <utility>

usingnamespacellvm;

#define DEBUG_TYPE …

// Number of levels to look ahead when re-ordering multi node operands.
static unsigned LookaheadMaxDepth = …;

VPInstruction *VPlanSlp::markFailed() { … }

void VPlanSlp::addCombined(ArrayRef<VPValue *> Operands, VPInstruction *New) { … }

bool VPlanSlp::areVectorizable(ArrayRef<VPValue *> Operands) const { … }

static SmallVector<VPValue *, 4> getOperands(ArrayRef<VPValue *> Values,
                                             unsigned OperandIndex) { … }

static bool areCommutative(ArrayRef<VPValue *> Values) { … }

static SmallVector<SmallVector<VPValue *, 4>, 4>
getOperands(ArrayRef<VPValue *> Values) { … }

/// Returns the opcode of Values or ~0 if they do not all agree.
static std::optional<unsigned> getOpcode(ArrayRef<VPValue *> Values) { … }

/// Returns true if A and B access sequential memory if they are loads or
/// stores or if they have identical opcodes otherwise.
static bool areConsecutiveOrMatch(VPInstruction *A, VPInstruction *B,
                                  VPInterleavedAccessInfo &IAI) { … }

/// Implements getLAScore from Listing 7 in the paper.
/// Traverses and compares operands of V1 and V2 to MaxLevel.
static unsigned getLAScore(VPValue *V1, VPValue *V2, unsigned MaxLevel,
                           VPInterleavedAccessInfo &IAI) { … }

std::pair<VPlanSlp::OpMode, VPValue *>
VPlanSlp::getBest(OpMode Mode, VPValue *Last,
                  SmallPtrSetImpl<VPValue *> &Candidates,
                  VPInterleavedAccessInfo &IAI) { … }

SmallVector<VPlanSlp::MultiNodeOpTy, 4> VPlanSlp::reorderMultiNodeOps() { … }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void VPlanSlp::dumpBundle(ArrayRef<VPValue *> Values) {
  dbgs() << " Ops: ";
  for (auto *Op : Values) {
    if (auto *VPInstr = cast_or_null<VPInstruction>(Op))
      if (auto *Instr = VPInstr->getUnderlyingInstr()) {
        dbgs() << *Instr << " | ";
        continue;
      }
    dbgs() << " nullptr | ";
  }
  dbgs() << "\n";
}
#endif

VPInstruction *VPlanSlp::buildGraph(ArrayRef<VPValue *> Values) { … }