LLVM 19.0.0git
MatrixUtils.cpp
Go to the documentation of this file.
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
16#include "llvm/IR/BasicBlock.h"
17#include "llvm/IR/Dominators.h"
18#include "llvm/IR/IRBuilder.h"
19#include "llvm/IR/Type.h"
20
21using namespace llvm;
22
23BasicBlock *TileInfo::CreateLoop(BasicBlock *Preheader, BasicBlock *Exit,
24 Value *Bound, Value *Step, StringRef Name,
26 LoopInfo &LI) {
27 LLVMContext &Ctx = Preheader->getContext();
29 Preheader->getContext(), Name + ".header", Preheader->getParent(), Exit);
30 BasicBlock *Body = BasicBlock::Create(Header->getContext(), Name + ".body",
31 Header->getParent(), Exit);
32 BasicBlock *Latch = BasicBlock::Create(Header->getContext(), Name + ".latch",
33 Header->getParent(), Exit);
34
35 Type *I32Ty = Type::getInt64Ty(Ctx);
36 BranchInst::Create(Body, Header);
37 BranchInst::Create(Latch, Body);
38 PHINode *IV =
39 PHINode::Create(I32Ty, 2, Name + ".iv", Header->getTerminator()->getIterator());
40 IV->addIncoming(ConstantInt::get(I32Ty, 0), Preheader);
41
42 B.SetInsertPoint(Latch);
43 Value *Inc = B.CreateAdd(IV, Step, Name + ".step");
44 Value *Cond = B.CreateICmpNE(Inc, Bound, Name + ".cond");
45 BranchInst::Create(Header, Exit, Cond, Latch);
46 IV->addIncoming(Inc, Latch);
47
48 BranchInst *PreheaderBr = cast<BranchInst>(Preheader->getTerminator());
49 BasicBlock *Tmp = PreheaderBr->getSuccessor(0);
50 PreheaderBr->setSuccessor(0, Header);
52 {DominatorTree::Delete, Preheader, Tmp},
53 {DominatorTree::Insert, Header, Body},
54 {DominatorTree::Insert, Body, Latch},
55 {DominatorTree::Insert, Latch, Header},
57 {DominatorTree::Insert, Preheader, Header},
58 });
59
60 L->addBasicBlockToLoop(Header, LI);
61 L->addBasicBlockToLoop(Body, LI);
62 L->addBasicBlockToLoop(Latch, LI);
63 return Body;
64}
65
66// Creates the following loop nest skeleton:
67// for C = 0; C < NumColumns; C += TileSize
68// for R = 0; R < NumRows; R += TileSize
69// for K = 0; K < Inner ; K += TileSize
72 LoopInfo &LI) {
73 Loop *ColumnLoopInfo = LI.AllocateLoop();
74 Loop *RowLoopInfo = LI.AllocateLoop();
75 Loop *KLoopInfo = LI.AllocateLoop();
76 RowLoopInfo->addChildLoop(KLoopInfo);
77 ColumnLoopInfo->addChildLoop(RowLoopInfo);
78 if (Loop *ParentL = LI.getLoopFor(Start))
79 ParentL->addChildLoop(ColumnLoopInfo);
80 else
81 LI.addTopLevelLoop(ColumnLoopInfo);
82
83 BasicBlock *ColBody =
84 CreateLoop(Start, End, B.getInt64(NumColumns), B.getInt64(TileSize),
85 "cols", B, DTU, ColumnLoopInfo, LI);
87 BasicBlock *RowBody =
88 CreateLoop(ColBody, ColumnLoop.Latch, B.getInt64(NumRows),
89 B.getInt64(TileSize), "rows", B, DTU, RowLoopInfo, LI);
90 RowLoop.Latch = RowBody->getSingleSuccessor();
91
92 BasicBlock *InnerBody =
93 CreateLoop(RowBody, RowLoop.Latch, B.getInt64(NumInner),
94 B.getInt64(TileSize), "inner", B, DTU, KLoopInfo, LI);
95 KLoop.Latch = InnerBody->getSingleSuccessor();
98 KLoop.Header = InnerBody->getSinglePredecessor();
102
103 return InnerBody;
104}
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
std::string Name
bool End
Definition: ELF_riscv.cpp:480
const SmallVectorImpl< MachineOperand > & Cond
static const uint32_t IV[8]
Definition: blake3_impl.h:78
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:429
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:198
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:441
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:471
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:205
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:157
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:220
Conditional or Unconditional Branch instruction.
static BranchInst * Create(BasicBlock *IfTrue, BasicBlock::iterator InsertBefore)
BasicBlock * getSuccessor(unsigned i) const
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Common base class shared among various IRBuilders.
Definition: IRBuilder.h:94
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
LoopT * AllocateLoop(ArgsTy &&...Args)
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr, BasicBlock::iterator InsertBefore)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
static IntegerType * getInt64Ty(LLVMContext &C)
LLVM Value Representation.
Definition: Value.h:74
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
BasicBlock * Header
The header and latch of the loop.
Definition: MatrixUtils.h:50
Value * Index
The index updated on every iteration.
Definition: MatrixUtils.h:48
unsigned NumInner
Number of columns of the first matrix of a multiply / number of rows of the second matrix of a multip...
Definition: MatrixUtils.h:40
MatrixLoop ColumnLoop
The loop iterating on the columns.
Definition: MatrixUtils.h:57
MatrixLoop RowLoop
The loop iterating on the rows.
Definition: MatrixUtils.h:55
unsigned NumRows
Number of rows of the matrix.
Definition: MatrixUtils.h:33
BasicBlock * CreateTiledLoops(BasicBlock *Start, BasicBlock *End, IRBuilderBase &B, DomTreeUpdater &DTU, LoopInfo &LI)
Creates an IR loop nests for tiling of the form below.
Definition: MatrixUtils.cpp:70
unsigned NumColumns
Number of columns of the matrix.
Definition: MatrixUtils.h:36
unsigned TileSize
Number of rows/columns in a tile.
Definition: MatrixUtils.h:43
MatrixLoop KLoop
The loop iterating on k (inner dimension).
Definition: MatrixUtils.h:59