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

   1 //===- VPlanSLP.cpp - SLP Analysis based on VPlan -------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 /// This file implements SLP analysis based on VPlan. The analysis is based on
  10 /// the ideas described in
  11 ///
  12 ///   Look-ahead SLP: auto-vectorization in the presence of commutative
  13 ///   operations, CGO 2018 by Vasileios Porpodas, Rodrigo C. O. Rocha,
  14 ///   Luís F. W. Góes
  15 ///
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "VPlan.h"
  19 #include "llvm/ADT/DepthFirstIterator.h"
  20 #include "llvm/ADT/PostOrderIterator.h"
  21 #include "llvm/ADT/SmallVector.h"
  22 #include "llvm/ADT/Twine.h"
  23 #include "llvm/Analysis/LoopInfo.h"
  24 #include "llvm/Analysis/VectorUtils.h"
  25 #include "llvm/IR/BasicBlock.h"
  26 #include "llvm/IR/CFG.h"
  27 #include "llvm/IR/Dominators.h"
  28 #include "llvm/IR/InstrTypes.h"
  29 #include "llvm/IR/Instruction.h"
  30 #include "llvm/IR/Instructions.h"
  31 #include "llvm/IR/Type.h"
  32 #include "llvm/IR/Value.h"
  33 #include "llvm/Support/Casting.h"
  34 #include "llvm/Support/Debug.h"
  35 #include "llvm/Support/ErrorHandling.h"
  36 #include "llvm/Support/GraphWriter.h"
  37 #include "llvm/Support/raw_ostream.h"
  38 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  39 #include <cassert>
  40 #include <iterator>
  41 #include <string>
  42 #include <vector>
  43
  44 using namespace llvm;
  45
  46 #define DEBUG_TYPE "vplan-slp"
  47
  48 // Number of levels to look ahead when re-ordering multi node operands.
  49 static unsigned LookaheadMaxDepth = 5;
  50
  51 VPInstruction *VPlanSlp::markFailed() {
  52   // FIXME: Currently this is used to signal we hit instructions we cannot
  53   //        trivially SLP'ize.
  54   CompletelySLP = false;
  55   return nullptr;
  56 }
  57
  58 void VPlanSlp::addCombined(ArrayRef<VPValue *> Operands, VPInstruction *New) {
  59   if (all_of(Operands, [](VPValue *V) {
  60         return cast<VPInstruction>(V)->getUnderlyingInstr();
  61       })) {
  62     unsigned BundleSize = 0;
  63     for (VPValue *V : Operands) {
  64       Type *T = cast<VPInstruction>(V)->getUnderlyingInstr()->getType();
  65       assert(!T->isVectorTy() && "Only scalar types supported for now");
  66       BundleSize += T->getScalarSizeInBits();
  67     }
  68     WidestBundleBits = std::max(WidestBundleBits, BundleSize);
  69   }
  70
  71   auto Res = BundleToCombined.try_emplace(to_vector<4>(Operands), New);
  72   assert(Res.second &&
  73          "Already created a combined instruction for the operand bundle");
  74   (void)Res;
  75 }
  76
  77 bool VPlanSlp::areVectorizable(ArrayRef<VPValue *> Operands) const {
  78   // Currently we only support VPInstructions.
  79   if (!all_of(Operands, [](VPValue *Op) {
  80         return Op && isa<VPInstruction>(Op) &&
  81                cast<VPInstruction>(Op)->getUnderlyingInstr();
  82       })) {
  83     LLVM_DEBUG(dbgs() << "VPSLP: not all operands are VPInstructions\n");
  84     return false;
  85   }
  86
  87   // Check if opcodes and type width agree for all instructions in the bundle.
  88   // FIXME: Differing widths/opcodes can be handled by inserting additional
  89   //        instructions.
  90   // FIXME: Deal with non-primitive types.
  91   const Instruction *OriginalInstr =
  92       cast<VPInstruction>(Operands[0])->getUnderlyingInstr();
  93   unsigned Opcode = OriginalInstr->getOpcode();
  94   unsigned Width = OriginalInstr->getType()->getPrimitiveSizeInBits();
  95   if (!all_of(Operands, [Opcode, Width](VPValue *Op) {
  96         const Instruction *I = cast<VPInstruction>(Op)->getUnderlyingInstr();
  97         return I->getOpcode() == Opcode &&
  98                I->getType()->getPrimitiveSizeInBits() == Width;
  99       })) {
 100     LLVM_DEBUG(dbgs() << "VPSLP: Opcodes do not agree \n");
 101     return false;
 102   }
 103
 104   // For now, all operands must be defined in the same BB.
 105   if (any_of(Operands, [this](VPValue *Op) {
 106         return cast<VPInstruction>(Op)->getParent() != &this->BB;
 107       })) {
 108     LLVM_DEBUG(dbgs() << "VPSLP: operands in different BBs\n");
 109     return false;
 110   }
 111
 112   if (any_of(Operands,
 113              [](VPValue *Op) { return Op->hasMoreThanOneUniqueUser(); })) {
 114     LLVM_DEBUG(dbgs() << "VPSLP: Some operands have multiple users.\n");
 115     return false;
 116   }
 117
 118   // For loads, check that there are no instructions writing to memory in
 119   // between them.
 120   // TODO: we only have to forbid instructions writing to memory that could
 121   //       interfere with any of the loads in the bundle
 122   if (Opcode == Instruction::Load) {
 123     unsigned LoadsSeen = 0;
 124     VPBasicBlock *Parent = cast<VPInstruction>(Operands[0])->getParent();
 125     for (auto &I : *Parent) {
 126       auto *VPI = cast<VPInstruction>(&I);
 127       if (VPI->getOpcode() == Instruction::Load &&
 128           std::find(Operands.begin(), Operands.end(), VPI) != Operands.end())
 129         LoadsSeen++;
 130
 131       if (LoadsSeen == Operands.size())
 132         break;
 133       if (LoadsSeen > 0 && VPI->mayWriteToMemory()) {
 134         LLVM_DEBUG(
 135             dbgs() << "VPSLP: instruction modifying memory between loads\n");
 136         return false;
 137       }
 138     }
 139
 140     if (!all_of(Operands, [](VPValue *Op) {
 141           return cast<LoadInst>(cast<VPInstruction>(Op)->getUnderlyingInstr())
 142               ->isSimple();
 143         })) {
 144       LLVM_DEBUG(dbgs() << "VPSLP: only simple loads are supported.\n");
 145       return false;
 146     }
 147   }
 148
 149   if (Opcode == Instruction::Store)
 150     if (!all_of(Operands, [](VPValue *Op) {
 151           return cast<StoreInst>(cast<VPInstruction>(Op)->getUnderlyingInstr())
 152               ->isSimple();
 153         })) {
 154       LLVM_DEBUG(dbgs() << "VPSLP: only simple stores are supported.\n");
 155       return false;
 156     }
 157
 158   return true;
 159 }
 160
 161 static SmallVector<VPValue *, 4> getOperands(ArrayRef<VPValue *> Values,
 162                                              unsigned OperandIndex) {
 163   SmallVector<VPValue *, 4> Operands;
 164   for (VPValue *V : Values) {
 165     auto *U = cast<VPUser>(V);
 166     Operands.push_back(U->getOperand(OperandIndex));
 167   }
 168   return Operands;
 169 }
 170
 171 static bool areCommutative(ArrayRef<VPValue *> Values) {
 172   return Instruction::isCommutative(
 173       cast<VPInstruction>(Values[0])->getOpcode());
 174 }
 175
 176 static SmallVector<SmallVector<VPValue *, 4>, 4>
 177 getOperands(ArrayRef<VPValue *> Values) {
 178   SmallVector<SmallVector<VPValue *, 4>, 4> Result;
 179   auto *VPI = cast<VPInstruction>(Values[0]);
 180
 181   switch (VPI->getOpcode()) {
 182   case Instruction::Load:
 183     llvm_unreachable("Loads terminate a tree, no need to get operands");
 184   case Instruction::Store:
 185     Result.push_back(getOperands(Values, 0));
 186     break;
 187   default:
 188     for (unsigned I = 0, NumOps = VPI->getNumOperands(); I < NumOps; ++I)
 189       Result.push_back(getOperands(Values, I));
 190     break;
 191   }
 192
 193   return Result;
 194 }
 195
 196 /// Returns the opcode of Values or ~0 if they do not all agree.
 197 static Optional<unsigned> getOpcode(ArrayRef<VPValue *> Values) {
 198   unsigned Opcode = cast<VPInstruction>(Values[0])->getOpcode();
 199   if (any_of(Values, [Opcode](VPValue *V) {
 200         return cast<VPInstruction>(V)->getOpcode() != Opcode;
 201       }))
 202     return None;
 203   return {Opcode};
 204 }
 205
 206 /// Returns true if A and B access sequential memory if they are loads or
 207 /// stores or if they have identical opcodes otherwise.
 208 static bool areConsecutiveOrMatch(VPInstruction *A, VPInstruction *B,
 209                                   VPInterleavedAccessInfo &IAI) {
 210   if (A->getOpcode() != B->getOpcode())
 211     return false;
 212
 213   if (A->getOpcode() != Instruction::Load &&
 214       A->getOpcode() != Instruction::Store)
 215     return true;
 216   auto *GA = IAI.getInterleaveGroup(A);
 217   auto *GB = IAI.getInterleaveGroup(B);
 218
 219   return GA && GB && GA == GB && GA->getIndex(A) + 1 == GB->getIndex(B);
 220 }
 221
 222 /// Implements getLAScore from Listing 7 in the paper.
 223 /// Traverses and compares operands of V1 and V2 to MaxLevel.
 224 static unsigned getLAScore(VPValue *V1, VPValue *V2, unsigned MaxLevel,
 225                            VPInterleavedAccessInfo &IAI) {
 226   if (!isa<VPInstruction>(V1) || !isa<VPInstruction>(V2))
 227     return 0;
 228
 229   if (MaxLevel == 0)
 230     return (unsigned)areConsecutiveOrMatch(cast<VPInstruction>(V1),
 231                                            cast<VPInstruction>(V2), IAI);
 232
 233   unsigned Score = 0;
 234   for (unsigned I = 0, EV1 = cast<VPUser>(V1)->getNumOperands(); I < EV1; ++I)
 235     for (unsigned J = 0, EV2 = cast<VPUser>(V2)->getNumOperands(); J < EV2; ++J)
 236       Score += getLAScore(cast<VPUser>(V1)->getOperand(I),
 237                           cast<VPUser>(V2)->getOperand(J), MaxLevel - 1, IAI);
 238   return Score;
 239 }
 240
 241 std::pair<VPlanSlp::OpMode, VPValue *>
 242 VPlanSlp::getBest(OpMode Mode, VPValue *Last,
 243                   SmallPtrSetImpl<VPValue *> &Candidates,
 244                   VPInterleavedAccessInfo &IAI) {
 245   assert((Mode == OpMode::Load || Mode == OpMode::Opcode) &&
 246          "Currently we only handle load and commutative opcodes");
 247   LLVM_DEBUG(dbgs() << "      getBest\n");
 248
 249   SmallVector<VPValue *, 4> BestCandidates;
 250   LLVM_DEBUG(dbgs() << "        Candidates  for "
 251                     << *cast<VPInstruction>(Last)->getUnderlyingInstr() << " ");
 252   for (auto *Candidate : Candidates) {
 253     auto *LastI = cast<VPInstruction>(Last);
 254     auto *CandidateI = cast<VPInstruction>(Candidate);
 255     if (areConsecutiveOrMatch(LastI, CandidateI, IAI)) {
 256       LLVM_DEBUG(dbgs() << *cast<VPInstruction>(Candidate)->getUnderlyingInstr()
 257                         << " ");
 258       BestCandidates.push_back(Candidate);
 259     }
 260   }
 261   LLVM_DEBUG(dbgs() << "\n");
 262
 263   if (BestCandidates.empty())
 264     return {OpMode::Failed, nullptr};
 265
 266   if (BestCandidates.size() == 1)
 267     return {Mode, BestCandidates[0]};
 268
 269   VPValue *Best = nullptr;
 270   unsigned BestScore = 0;
 271   for (unsigned Depth = 1; Depth < LookaheadMaxDepth; Depth++) {
 272     unsigned PrevScore = ~0u;
 273     bool AllSame = true;
 274
 275     // FIXME: Avoid visiting the same operands multiple times.
 276     for (auto *Candidate : BestCandidates) {
 277       unsigned Score = getLAScore(Last, Candidate, Depth, IAI);
 278       if (PrevScore == ~0u)
 279         PrevScore = Score;
 280       if (PrevScore != Score)
 281         AllSame = false;
 282       PrevScore = Score;
 283
 284       if (Score > BestScore) {
 285         BestScore = Score;
 286         Best = Candidate;
 287       }
 288     }
 289     if (!AllSame)
 290       break;
 291   }
 292   LLVM_DEBUG(dbgs() << "Found best "
 293                     << *cast<VPInstruction>(Best)->getUnderlyingInstr()
 294                     << "\n");
 295   Candidates.erase(Best);
 296
 297   return {Mode, Best};
 298 }
 299
 300 SmallVector<VPlanSlp::MultiNodeOpTy, 4> VPlanSlp::reorderMultiNodeOps() {
 301   SmallVector<MultiNodeOpTy, 4> FinalOrder;
 302   SmallVector<OpMode, 4> Mode;
 303   FinalOrder.reserve(MultiNodeOps.size());
 304   Mode.reserve(MultiNodeOps.size());
 305
 306   LLVM_DEBUG(dbgs() << "Reordering multinode\n");
 307
 308   for (auto &Operands : MultiNodeOps) {
 309     FinalOrder.push_back({Operands.first, {Operands.second[0]}});
 310     if (cast<VPInstruction>(Operands.second[0])->getOpcode() ==
 311         Instruction::Load)
 312       Mode.push_back(OpMode::Load);
 313     else
 314       Mode.push_back(OpMode::Opcode);
 315   }
 316
 317   for (unsigned Lane = 1, E = MultiNodeOps[0].second.size(); Lane < E; ++Lane) {
 318     LLVM_DEBUG(dbgs() << "  Finding best value for lane " << Lane << "\n");
 319     SmallPtrSet<VPValue *, 4> Candidates;
 320     LLVM_DEBUG(dbgs() << "  Candidates  ");
 321     for (auto Ops : MultiNodeOps) {
 322       LLVM_DEBUG(
 323           dbgs() << *cast<VPInstruction>(Ops.second[Lane])->getUnderlyingInstr()
 324                  << " ");
 325       Candidates.insert(Ops.second[Lane]);
 326     }
 327     LLVM_DEBUG(dbgs() << "\n");
 328
 329     for (unsigned Op = 0, E = MultiNodeOps.size(); Op < E; ++Op) {
 330       LLVM_DEBUG(dbgs() << "  Checking " << Op << "\n");
 331       if (Mode[Op] == OpMode::Failed)
 332         continue;
 333
 334       VPValue *Last = FinalOrder[Op].second[Lane - 1];
 335       std::pair<OpMode, VPValue *> Res =
 336           getBest(Mode[Op], Last, Candidates, IAI);
 337       if (Res.second)
 338         FinalOrder[Op].second.push_back(Res.second);
 339       else
 340         // TODO: handle this case
 341         FinalOrder[Op].second.push_back(markFailed());
 342     }
 343   }
 344
 345   return FinalOrder;
 346 }
 347
 348 void VPlanSlp::dumpBundle(ArrayRef<VPValue *> Values) {
 349   dbgs() << " Ops: ";
 350   for (auto Op : Values)
 351     if (auto *Instr = cast_or_null<VPInstruction>(Op)->getUnderlyingInstr())
 352       dbgs() << *Instr << " | ";
 353     else
 354       dbgs() << " nullptr | ";
 355   dbgs() << "\n";
 356 }
 357
 358 VPInstruction *VPlanSlp::buildGraph(ArrayRef<VPValue *> Values) {
 359   assert(!Values.empty() && "Need some operands!");
 360
 361   // If we already visited this instruction bundle, re-use the existing node
 362   auto I = BundleToCombined.find(to_vector<4>(Values));
 363   if (I != BundleToCombined.end()) {
 364 #ifndef NDEBUG
 365     // Check that the resulting graph is a tree. If we re-use a node, this means
 366     // its values have multiple users. We only allow this, if all users of each
 367     // value are the same instruction.
 368     for (auto *V : Values) {
 369       auto UI = V->user_begin();
 370       auto *FirstUser = *UI++;
 371       while (UI != V->user_end()) {
 372         assert(*UI == FirstUser && "Currently we only support SLP trees.");
 373         UI++;
 374       }
 375     }
 376 #endif
 377     return I->second;
 378   }
 379
 380   // Dump inputs
 381   LLVM_DEBUG({
 382     dbgs() << "buildGraph: ";
 383     dumpBundle(Values);
 384   });
 385
 386   if (!areVectorizable(Values))
 387     return markFailed();
 388
 389   assert(getOpcode(Values) && "Opcodes for all values must match");
 390   unsigned ValuesOpcode = getOpcode(Values).getValue();
 391
 392   SmallVector<VPValue *, 4> CombinedOperands;
 393   if (areCommutative(Values)) {
 394     bool MultiNodeRoot = !MultiNodeActive;
 395     MultiNodeActive = true;
 396     for (auto &Operands : getOperands(Values)) {
 397       LLVM_DEBUG({
 398         dbgs() << "  Visiting Commutative";
 399         dumpBundle(Operands);
 400       });
 401
 402       auto OperandsOpcode = getOpcode(Operands);
 403       if (OperandsOpcode && OperandsOpcode == getOpcode(Values)) {
 404         LLVM_DEBUG(dbgs() << "    Same opcode, continue building\n");
 405         CombinedOperands.push_back(buildGraph(Operands));
 406       } else {
 407         LLVM_DEBUG(dbgs() << "    Adding multinode Ops\n");
 408         // Create dummy VPInstruction, which will we replace later by the
 409         // re-ordered operand.
 410         VPInstruction *Op = new VPInstruction(0, {});
 411         CombinedOperands.push_back(Op);
 412         MultiNodeOps.emplace_back(Op, Operands);
 413       }
 414     }
 415
 416     if (MultiNodeRoot) {
 417       LLVM_DEBUG(dbgs() << "Reorder \n");
 418       MultiNodeActive = false;
 419
 420       auto FinalOrder = reorderMultiNodeOps();
 421
 422       MultiNodeOps.clear();
 423       for (auto &Ops : FinalOrder) {
 424         VPInstruction *NewOp = buildGraph(Ops.second);
 425         Ops.first->replaceAllUsesWith(NewOp);
 426         for (unsigned i = 0; i < CombinedOperands.size(); i++)
 427           if (CombinedOperands[i] == Ops.first)
 428             CombinedOperands[i] = NewOp;
 429         delete Ops.first;
 430         Ops.first = NewOp;
 431       }
 432       LLVM_DEBUG(dbgs() << "Found final order\n");
 433     }
 434   } else {
 435     LLVM_DEBUG(dbgs() << "  NonCommuntative\n");
 436     if (ValuesOpcode == Instruction::Load)
 437       for (VPValue *V : Values)
 438         CombinedOperands.push_back(cast<VPInstruction>(V)->getOperand(0));
 439     else
 440       for (auto &Operands : getOperands(Values))
 441         CombinedOperands.push_back(buildGraph(Operands));
 442   }
 443
 444   unsigned Opcode;
 445   switch (ValuesOpcode) {
 446   case Instruction::Load:
 447     Opcode = VPInstruction::SLPLoad;
 448     break;
 449   case Instruction::Store:
 450     Opcode = VPInstruction::SLPStore;
 451     break;
 452   default:
 453     Opcode = ValuesOpcode;
 454     break;
 455   }
 456
 457   if (!CompletelySLP)
 458     return markFailed();
 459
 460   assert(CombinedOperands.size() > 0 && "Need more some operands");
 461   auto *VPI = new VPInstruction(Opcode, CombinedOperands);
 462   VPI->setUnderlyingInstr(cast<VPInstruction>(Values[0])->getUnderlyingInstr());
 463
 464   LLVM_DEBUG(dbgs() << "Create VPInstruction "; VPI->print(dbgs());
 465              cast<VPInstruction>(Values[0])->print(dbgs()); dbgs() << "\n");
 466   addCombined(Values, VPI);
 467   return VPI;
 468 }