LLVM  13.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 *ColLoop = LI.AllocateLoop();
74  Loop *RowLoop = LI.AllocateLoop();
75  Loop *InnerLoop = LI.AllocateLoop();
76  RowLoop->addChildLoop(InnerLoop);
77  ColLoop->addChildLoop(RowLoop);
78  if (Loop *ParentL = LI.getLoopFor(Start))
79  ParentL->addChildLoop(ColLoop);
80  else
81  LI.addTopLevelLoop(ColLoop);
82 
83  BasicBlock *ColBody =
84  CreateLoop(Start, End, B.getInt64(NumColumns), B.getInt64(TileSize),
85  "cols", B, DTU, ColLoop, LI);
86  BasicBlock *ColLatch = ColBody->getSingleSuccessor();
87  BasicBlock *RowBody =
88  CreateLoop(ColBody, ColLatch, B.getInt64(NumRows), B.getInt64(TileSize),
89  "rows", B, DTU, RowLoop, LI);
90  RowLoopLatch = RowBody->getSingleSuccessor();
91 
92  BasicBlock *InnerBody =
93  CreateLoop(RowBody, RowLoopLatch, B.getInt64(NumInner),
94  B.getInt64(TileSize), "inner", B, DTU, InnerLoop, LI);
95  InnerLoopLatch = InnerBody->getSingleSuccessor();
102 
103  return InnerBody;
104 }
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::TileInfo::RowLoopLatch
BasicBlock * RowLoopLatch
Latch of the second loop iterating from 0..NumRows.
Definition: MatrixUtils.h:60
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
llvm::TileInfo::InnerLoopLatch
BasicBlock * InnerLoopLatch
Latch of the innermost loop iterating from 0..NumInner.
Definition: MatrixUtils.h:64
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
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:294
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:264
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:3130
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
MatrixUtils.h
llvm::LoopBase::addChildLoop
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
Definition: LoopInfo.h:395
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
llvm::LoopInfoBase::addTopLevelLoop
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
Definition: LoopInfo.h:1024
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:899
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:931
llvm::TileInfo::CurrentCol
Value * CurrentCol
Start column of the current tile to compute.
Definition: MatrixUtils.h:49
BasicBlock.h
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2747
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3088
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:967
IRBuilder.h
llvm::TileInfo::InnerLoopHeader
BasicBlock * InnerLoopHeader
Header of the innermost loop iterating from 0..NumInner.
Definition: MatrixUtils.h:62
llvm::TileInfo::RowLoopHeader
BasicBlock * RowLoopHeader
Header of the second loop iterating from 0..NumRows.
Definition: MatrixUtils.h:58
llvm::LoopInfo
Definition: LoopInfo.h:1083
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:167
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
llvm::IRBuilderBase
Common base class shared among various IRBuilders.
Definition: IRBuilder.h:95
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.cpp:148
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
llvm::Type::getInt64Ty
static IntegerType * getInt64Ty(LLVMContext &C)
Definition: Type.cpp:204
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
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:2639
llvm::TileInfo::TileSize
unsigned TileSize
Number of rows/columns in a tile.
Definition: MatrixUtils.h:43
llvm::TileInfo::CurrentRow
Value * CurrentRow
Start row of the current tile to compute.
Definition: MatrixUtils.h:46
llvm::TileInfo::ColumnLoopHeader
BasicBlock * ColumnLoopHeader
Header of the outermost loop iterating from 0..NumColumns.
Definition: MatrixUtils.h:55
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:242
Dominators.h
llvm::PHINode
Definition: Instructions.h:2597
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3032
llvm::TileInfo::CurrentK
Value * CurrentK
Current tile offset during the tile computation.
Definition: MatrixUtils.h:52
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:75
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3125
llvm::DominatorTreeBase< BasicBlock, false >::Delete
static constexpr UpdateKind Delete
Definition: GenericDomTree.h:243