1//===- MatrixUtils.cpp - Utilities to lower matrix intrinsics ---*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Utilities for generating tiled loops for matrix operations.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Transforms/Utils/MatrixUtils.h"
14#include "llvm/Analysis/DomTreeUpdater.h"
15#include "llvm/Analysis/LoopInfo.h"
16#include "llvm/IR/BasicBlock.h"
17#include "llvm/IR/Dominators.h"
18#include "llvm/IR/IRBuilder.h"
19#include "llvm/IR/MDBuilder.h"
20#include "llvm/IR/ProfDataUtils.h"
21#include "llvm/IR/Type.h"
22
23using namespace llvm;
24
25BasicBlock *TileInfo::CreateLoop(BasicBlock *Preheader, BasicBlock *Exit,
26 ConstantInt *Bound, ConstantInt *Step,
27 StringRef Name, IRBuilderBase &B,
28 DomTreeUpdater &DTU, Loop *L, LoopInfo &LI) {
29 LLVMContext &Ctx = Preheader->getContext();
30 BasicBlock *Header = BasicBlock::Create(
31 Context&: Preheader->getContext(), Name: Name + ".header", Parent: Preheader->getParent(), InsertBefore: Exit);
32 BasicBlock *Body = BasicBlock::Create(Context&: Header->getContext(), Name: Name + ".body",
33 Parent: Header->getParent(), InsertBefore: Exit);
34 BasicBlock *Latch = BasicBlock::Create(Context&: Header->getContext(), Name: Name + ".latch",
35 Parent: Header->getParent(), InsertBefore: Exit);
36
37 Type *I32Ty = Type::getInt64Ty(C&: Ctx);
38 UncondBrInst::Create(Target: Body, InsertBefore: Header);
39 UncondBrInst::Create(Target: Latch, InsertBefore: Body);
40 PHINode *IV =
41 PHINode::Create(Ty: I32Ty, NumReservedValues: 2, NameStr: Name + ".iv", InsertBefore: Header->getTerminator()->getIterator());
42 IV->addIncoming(V: ConstantInt::get(Ty: I32Ty, V: 0), BB: Preheader);
43
44 B.SetInsertPoint(Latch);
45 Value *Inc = B.CreateAdd(LHS: IV, RHS: Step, Name: Name + ".step");
46 Value *Cond = B.CreateICmpNE(LHS: Inc, RHS: Bound, Name: Name + ".cond");
47 auto *BR = B.CreateCondBr(Cond, True: Header, False: Exit);
48 assert(Step->getZExtValue() != 0 &&
49 "Expected a non-zero step size. This is chosen by the pass and "
50 "should always be non-zero to imply a finite loop.");
51 MDBuilder MDB(Preheader->getContext());
52 setFittedBranchWeights(I&: *BR, Weights: {Bound->getZExtValue() / Step->getZExtValue(), 1},
53 IsExpected: false);
54 IV->addIncoming(V: Inc, BB: Latch);
55
56 UncondBrInst *PreheaderBr = cast<UncondBrInst>(Val: Preheader->getTerminator());
57 BasicBlock *Tmp = PreheaderBr->getSuccessor();
58 PreheaderBr->setSuccessor(idx: 0, NewSucc: Header);
59 DTU.applyUpdatesPermissive(Updates: {
60 {DominatorTree::Delete, Preheader, Tmp},
61 {DominatorTree::Insert, Header, Body},
62 {DominatorTree::Insert, Body, Latch},
63 {DominatorTree::Insert, Latch, Header},
64 {DominatorTree::Insert, Latch, Exit},
65 {DominatorTree::Insert, Preheader, Header},
66 });
67
68 L->addBasicBlockToLoop(NewBB: Header, LI);
69 L->addBasicBlockToLoop(NewBB: Body, LI);
70 L->addBasicBlockToLoop(NewBB: Latch, LI);
71 return Body;
72}
73
74// Creates the following loop nest skeleton:
75// for C = 0; C < NumColumns; C += TileSize
76// for R = 0; R < NumRows; R += TileSize
77// for K = 0; K < Inner ; K += TileSize
78BasicBlock *TileInfo::CreateTiledLoops(BasicBlock *Start, BasicBlock *End,
79 IRBuilderBase &B, DomTreeUpdater &DTU,
80 LoopInfo &LI) {
81 Loop *ColumnLoopInfo = LI.AllocateLoop();
82 Loop *RowLoopInfo = LI.AllocateLoop();
83 Loop *KLoopInfo = LI.AllocateLoop();
84 RowLoopInfo->addChildLoop(NewChild: KLoopInfo);
85 ColumnLoopInfo->addChildLoop(NewChild: RowLoopInfo);
86 if (Loop *ParentL = LI.getLoopFor(BB: Start))
87 ParentL->addChildLoop(NewChild: ColumnLoopInfo);
88 else
89 LI.addTopLevelLoop(New: ColumnLoopInfo);
90
91 BasicBlock *ColBody =
92 CreateLoop(Preheader: Start, Exit: End, Bound: B.getInt64(C: NumColumns), Step: B.getInt64(C: TileSize),
93 Name: "cols", B, DTU, L: ColumnLoopInfo, LI);
94 ColumnLoop.Latch = ColBody->getSingleSuccessor();
95 BasicBlock *RowBody =
96 CreateLoop(Preheader: ColBody, Exit: ColumnLoop.Latch, Bound: B.getInt64(C: NumRows),
97 Step: B.getInt64(C: TileSize), Name: "rows", B, DTU, L: RowLoopInfo, LI);
98 RowLoop.Latch = RowBody->getSingleSuccessor();
99
100 BasicBlock *InnerBody =
101 CreateLoop(Preheader: RowBody, Exit: RowLoop.Latch, Bound: B.getInt64(C: NumInner),
102 Step: B.getInt64(C: TileSize), Name: "inner", B, DTU, L: KLoopInfo, LI);
103 KLoop.Latch = InnerBody->getSingleSuccessor();
104 ColumnLoop.Header = ColBody->getSinglePredecessor();
105 RowLoop.Header = RowBody->getSinglePredecessor();
106 KLoop.Header = InnerBody->getSinglePredecessor();
107 RowLoop.Index = &*RowLoop.Header->begin();
108 ColumnLoop.Index = &*ColumnLoop.Header->begin();
109 KLoop.Index = &*KLoop.Header->begin();
110
111 return InnerBody;
112}
113