LLVM  16.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 
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/Type.h"
20 
21 using namespace llvm;
22 
23 BasicBlock *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());
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},
56  {DominatorTree::Insert, Latch, Exit},
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);
86  ColumnLoop.Latch = ColBody->getSingleSuccessor();
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();
97  RowLoop.Header = RowBody->getSinglePredecessor();
98  KLoop.Header = InnerBody->getSinglePredecessor();
101  KLoop.Index = &*KLoop.Header->begin();
102 
103  return InnerBody;
104 }
llvm::TileInfo::ColumnLoop
MatrixLoop ColumnLoop
The loop iterating on the columns.
Definition: MatrixUtils.h:57
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::TileInfo::MatrixLoop::Latch
BasicBlock * Latch
Definition: MatrixUtils.h:51
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
DomTreeUpdater.h
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::BasicBlock::getSingleSuccessor
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:315
llvm::DominatorTreeBase< BasicBlock, false >::Insert
static constexpr UpdateKind Insert
Definition: GenericDomTree.h:242
llvm::TileInfo::NumColumns
unsigned NumColumns
Number of columns of the matrix.
Definition: MatrixUtils.h:36
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:285
llvm::TileInfo::NumInner
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
llvm::BranchInst::setSuccessor
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
Definition: Instructions.h:3232
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
MatrixUtils.h
llvm::TileInfo::MatrixLoop::Index
Value * Index
The index updated on every iteration.
Definition: MatrixUtils.h:48
llvm::LoopBase::addChildLoop
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
Definition: LoopInfo.h:412
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:306
llvm::LoopInfoBase::addTopLevelLoop
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
Definition: LoopInfo.h:1049
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:879
llvm::TileInfo::NumRows
unsigned NumRows
Number of rows of the matrix.
Definition: MatrixUtils.h:33
Type.h
LoopInfo.h
llvm::LoopInfoBase::AllocateLoop
LoopT * AllocateLoop(ArgsTy &&... Args)
Definition: LoopInfo.h:956
BasicBlock.h
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3190
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:992
IRBuilder.h
llvm::TileInfo::MatrixLoop::Header
BasicBlock * Header
The header and latch of the loop.
Definition: MatrixUtils.h:50
llvm::TileInfo::KLoop
MatrixLoop KLoop
The loop iterating on k (inner dimension).
Definition: MatrixUtils.h:59
llvm::TileInfo::RowLoop
MatrixLoop RowLoop
The loop iterating on the rows.
Definition: MatrixUtils.h:55
llvm::LoopInfo
Definition: LoopInfo.h:1108
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:138
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:97
llvm::IRBuilderBase
Common base class shared among various IRBuilders.
Definition: IRBuilder.h:93
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:35
llvm::Type::getInt64Ty
static IntegerType * getInt64Ty(LLVMContext &C)
Definition: Type.cpp:240
llvm::PHINode::Create
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
Definition: Instructions.h:2741
llvm::TileInfo::TileSize
unsigned TileSize
Number of rows/columns in a tile.
Definition: MatrixUtils.h:43
llvm::TileInfo::CreateTiledLoops
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
llvm::LoopBase::addBasicBlockToLoop
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:258
Dominators.h
llvm::PHINode
Definition: Instructions.h:2699
llvm::BasicBlock::getTerminator
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:119
IV
static const uint32_t IV[8]
Definition: blake3_impl.h:85
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3134
llvm::DomTreeUpdater::applyUpdatesPermissive
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:249
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3227
llvm::DominatorTreeBase< BasicBlock, false >::Delete
static constexpr UpdateKind Delete
Definition: GenericDomTree.h:243