xref: /llvm-project/llvm/lib/Transforms/Vectorize/SandboxVectorizer/DependencyGraph.cpp (revision 267e852109381fe35cff0a92915a0418b872213f)
1 //===- DependencyGraph.cpp ------------------------------------------===//
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 #include "llvm/Transforms/Vectorize/SandboxVectorizer/DependencyGraph.h"
10 #include "llvm/ADT/ArrayRef.h"
11 #include "llvm/SandboxIR/Utils.h"
12 
13 namespace llvm::sandboxir {
14 
15 #ifndef NDEBUG
16 void DGNode::print(raw_ostream &OS, bool PrintDeps) const {
17   I->dumpOS(OS);
18   if (PrintDeps) {
19     OS << "\n";
20     // Print memory preds.
21     static constexpr const unsigned Indent = 4;
22     for (auto *Pred : MemPreds) {
23       OS.indent(Indent) << "<-";
24       Pred->print(OS, false);
25       OS << "\n";
26     }
27   }
28 }
29 void DGNode::dump() const {
30   print(dbgs());
31   dbgs() << "\n";
32 }
33 #endif // NDEBUG
34 
35 Interval<MemDGNode>
36 MemDGNodeIntervalBuilder::make(const Interval<Instruction> &Instrs,
37                                DependencyGraph &DAG) {
38   // If top or bottom instructions are not mem-dep candidate nodes we need to
39   // walk down/up the chain and find the mem-dep ones.
40   Instruction *MemTopI = Instrs.top();
41   Instruction *MemBotI = Instrs.bottom();
42   while (!DGNode::isMemDepNodeCandidate(MemTopI) && MemTopI != MemBotI)
43     MemTopI = MemTopI->getNextNode();
44   while (!DGNode::isMemDepNodeCandidate(MemBotI) && MemBotI != MemTopI)
45     MemBotI = MemBotI->getPrevNode();
46   // If we couldn't find a mem node in range TopN - BotN then it's empty.
47   if (!DGNode::isMemDepNodeCandidate(MemTopI))
48     return {};
49   // Now that we have the mem-dep nodes, create and return the range.
50   return Interval<MemDGNode>(cast<MemDGNode>(DAG.getNode(MemTopI)),
51                              cast<MemDGNode>(DAG.getNode(MemBotI)));
52 }
53 
54 DependencyGraph::DependencyType
55 DependencyGraph::getRoughDepType(Instruction *FromI, Instruction *ToI) {
56   // TODO: Perhaps compile-time improvement by skipping if neither is mem?
57   if (FromI->mayWriteToMemory()) {
58     if (ToI->mayReadFromMemory())
59       return DependencyType::ReadAfterWrite;
60     if (ToI->mayWriteToMemory())
61       return DependencyType::WriteAfterWrite;
62   } else if (FromI->mayReadFromMemory()) {
63     if (ToI->mayWriteToMemory())
64       return DependencyType::WriteAfterRead;
65     if (ToI->mayReadFromMemory())
66       return DependencyType::ReadAfterRead;
67   }
68   if (isa<sandboxir::PHINode>(FromI) || isa<sandboxir::PHINode>(ToI))
69     return DependencyType::Control;
70   if (ToI->isTerminator())
71     return DependencyType::Control;
72   if (DGNode::isStackSaveOrRestoreIntrinsic(FromI) ||
73       DGNode::isStackSaveOrRestoreIntrinsic(ToI))
74     return DependencyType::Other;
75   return DependencyType::None;
76 }
77 
78 static bool isOrdered(Instruction *I) {
79   auto IsOrdered = [](Instruction *I) {
80     if (auto *LI = dyn_cast<LoadInst>(I))
81       return !LI->isUnordered();
82     if (auto *SI = dyn_cast<StoreInst>(I))
83       return !SI->isUnordered();
84     if (DGNode::isFenceLike(I))
85       return true;
86     return false;
87   };
88   bool Is = IsOrdered(I);
89   assert((!Is || DGNode::isMemDepCandidate(I)) &&
90          "An ordered instruction must be a MemDepCandidate!");
91   return Is;
92 }
93 
94 bool DependencyGraph::alias(Instruction *SrcI, Instruction *DstI,
95                             DependencyType DepType) {
96   std::optional<MemoryLocation> DstLocOpt =
97       Utils::memoryLocationGetOrNone(DstI);
98   if (!DstLocOpt)
99     return true;
100   // Check aliasing.
101   assert((SrcI->mayReadFromMemory() || SrcI->mayWriteToMemory()) &&
102          "Expected a mem instr");
103   // TODO: Check AABudget
104   ModRefInfo SrcModRef =
105       isOrdered(SrcI)
106           ? ModRefInfo::Mod
107           : Utils::aliasAnalysisGetModRefInfo(*BatchAA, SrcI, *DstLocOpt);
108   switch (DepType) {
109   case DependencyType::ReadAfterWrite:
110   case DependencyType::WriteAfterWrite:
111     return isModSet(SrcModRef);
112   case DependencyType::WriteAfterRead:
113     return isRefSet(SrcModRef);
114   default:
115     llvm_unreachable("Expected only RAW, WAW and WAR!");
116   }
117 }
118 
119 bool DependencyGraph::hasDep(Instruction *SrcI, Instruction *DstI) {
120   DependencyType RoughDepType = getRoughDepType(SrcI, DstI);
121   switch (RoughDepType) {
122   case DependencyType::ReadAfterRead:
123     return false;
124   case DependencyType::ReadAfterWrite:
125   case DependencyType::WriteAfterWrite:
126   case DependencyType::WriteAfterRead:
127     return alias(SrcI, DstI, RoughDepType);
128   case DependencyType::Control:
129     // Adding actual dep edges from PHIs/to terminator would just create too
130     // many edges, which would be bad for compile-time.
131     // So we ignore them in the DAG formation but handle them in the
132     // scheduler, while sorting the ready list.
133     return false;
134   case DependencyType::Other:
135     return true;
136   case DependencyType::None:
137     return false;
138   }
139 }
140 
141 void DependencyGraph::scanAndAddDeps(DGNode &DstN,
142                                      const Interval<MemDGNode> &SrcScanRange) {
143   assert(isa<MemDGNode>(DstN) &&
144          "DstN is the mem dep destination, so it must be mem");
145   Instruction *DstI = DstN.getInstruction();
146   // Walk up the instruction chain from ScanRange bottom to top, looking for
147   // memory instrs that may alias.
148   for (MemDGNode &SrcN : reverse(SrcScanRange)) {
149     Instruction *SrcI = SrcN.getInstruction();
150     if (hasDep(SrcI, DstI))
151       DstN.addMemPred(&SrcN);
152   }
153 }
154 
155 Interval<Instruction> DependencyGraph::extend(ArrayRef<Instruction *> Instrs) {
156   if (Instrs.empty())
157     return {};
158 
159   Interval<Instruction> InstrInterval(Instrs);
160 
161   DGNode *LastN = getOrCreateNode(InstrInterval.top());
162   // Create DGNodes for all instrs in Interval to avoid future Instruction to
163   // DGNode lookups.
164   MemDGNode *LastMemN = dyn_cast<MemDGNode>(LastN);
165   for (Instruction &I : drop_begin(InstrInterval)) {
166     auto *N = getOrCreateNode(&I);
167     // Build the Mem node chain.
168     if (auto *MemN = dyn_cast<MemDGNode>(N)) {
169       MemN->setPrevNode(LastMemN);
170       if (LastMemN != nullptr)
171         LastMemN->setNextNode(MemN);
172       LastMemN = MemN;
173     }
174   }
175   // Create the dependencies.
176   auto DstRange = MemDGNodeIntervalBuilder::make(InstrInterval, *this);
177   for (MemDGNode &DstN : drop_begin(DstRange)) {
178     auto SrcRange = Interval<MemDGNode>(DstRange.top(), DstN.getPrevNode());
179     scanAndAddDeps(DstN, SrcRange);
180   }
181 
182   return InstrInterval;
183 }
184 
185 #ifndef NDEBUG
186 void DependencyGraph::print(raw_ostream &OS) const {
187   // InstrToNodeMap is unordered so we need to create an ordered vector.
188   SmallVector<DGNode *> Nodes;
189   Nodes.reserve(InstrToNodeMap.size());
190   for (const auto &Pair : InstrToNodeMap)
191     Nodes.push_back(Pair.second.get());
192   // Sort them based on which one comes first in the BB.
193   sort(Nodes, [](DGNode *N1, DGNode *N2) {
194     return N1->getInstruction()->comesBefore(N2->getInstruction());
195   });
196   for (auto *N : Nodes)
197     N->print(OS, /*PrintDeps=*/true);
198 }
199 
200 void DependencyGraph::dump() const {
201   print(dbgs());
202   dbgs() << "\n";
203 }
204 #endif // NDEBUG
205 
206 } // namespace llvm::sandboxir
207