1 | /** |
2 | * Copyright (c) Glow Contributors. See CONTRIBUTORS file. |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | * you may not use this file except in compliance with the License. |
6 | * You may obtain a copy of the License at |
7 | * |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * |
10 | * Unless required by applicable law or agreed to in writing, software |
11 | * distributed under the License is distributed on an "AS IS" BASIS, |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 | * See the License for the specific language governing permissions and |
14 | * limitations under the License. |
15 | */ |
16 | #ifndef GLOW_IR_IR_H |
17 | #define GLOW_IR_IR_H |
18 | |
19 | #include "glow/Base/TaggedList.h" |
20 | #include "glow/Base/Traits.h" |
21 | #include "glow/Base/Type.h" |
22 | #include "glow/Graph/Graph.h" |
23 | #include "glow/Graph/UseDef.h" |
24 | |
25 | #include "llvm/ADT/ArrayRef.h" |
26 | #include "llvm/ADT/MapVector.h" |
27 | #include "llvm/ADT/SmallVector.h" |
28 | #include "llvm/ADT/StringRef.h" |
29 | #include "llvm/ADT/StringSet.h" |
30 | |
31 | #include <list> |
32 | #include <unordered_map> |
33 | #include <vector> |
34 | #if FACEBOOK_INTERNAL |
35 | namespace glow { |
36 | class FXIRWrapper; |
37 | } |
38 | #endif |
39 | |
40 | namespace glow { |
41 | class Instruction; |
42 | class IRFunction; |
43 | class Function; |
44 | class Value; |
45 | class InstructionNumbering; |
46 | |
47 | enum class OperandKind : unsigned char { |
48 | In, |
49 | InOut, |
50 | Out, |
51 | }; |
52 | |
53 | inline const char *getOperandKindStr(OperandKind CC) { |
54 | const char *names[] = {"@in" , "@inout" , "@out" , nullptr}; |
55 | return names[(int)CC]; |
56 | } |
57 | |
58 | using InstructionOperand = std::pair<Value *, OperandKind>; |
59 | using ConstInstructionOperand = const std::pair<const Value *, OperandKind>; |
60 | |
61 | /// A 'Use' is a use-list representation of an instruction operand. It maps to a |
62 | /// specific operand in an instruction. |
63 | struct Use { |
64 | /// The instruction. |
65 | Instruction *use_; |
66 | /// The index of the operand. |
67 | unsigned idx_; |
68 | |
69 | bool operator==(const Use &other) const { |
70 | return idx_ == other.idx_ && use_ == other.use_; |
71 | } |
72 | |
73 | Use(unsigned idx, Instruction *use) : use_(use), idx_(idx) {} |
74 | |
75 | /// \returns the instruction that the use refers to. |
76 | Instruction *get() const { return use_; } |
77 | /// \returns the instruction that the use refers to |
78 | /// (for compatibility with UseDef::hasUser) |
79 | Instruction *getUser() const { return use_; } |
80 | /// \returns true if this Use is for the instruction \p other. |
81 | bool isSame(Instruction *other) const { return use_ == other; } |
82 | /// Sets the operand to a new value. |
83 | void setOperand(Value *other); |
84 | /// \returns the operand of the user instruction. |
85 | InstructionOperand getOperand(); |
86 | ConstInstructionOperand getOperand() const; |
87 | }; |
88 | |
89 | class Value : public Named, |
90 | public UseDef<Instruction, Use>, |
91 | public Typed, |
92 | public Kinded { |
93 | public: |
94 | Value(llvm::StringRef name, TypeRef T, Kinded::Kind k) |
95 | : Named(name), Typed(T), Kinded(k) {} |
96 | |
97 | bool verifyUseList(const InstructionNumbering &InstrNumbering) const; |
98 | |
99 | /// Verify the correctness of the instruction parameters. |
100 | bool verify(const IRFunction &M) const; |
101 | |
102 | /// Dump a textual representation of the Value into provided output stream. |
103 | void dump(llvm::raw_ostream &out) const; |
104 | |
105 | /// Dump a textual representation of the Value into default output stream. |
106 | void dump() const; |
107 | |
108 | /// Dump a textual representation of the Value to std::string. |
109 | std::string toString() const; |
110 | |
111 | /// Print value in context. |
112 | void dumpInContext(llvm::raw_ostream &out) const; |
113 | |
114 | /// Print value in context using a default output stream. |
115 | void dumpInContext() const; |
116 | }; |
117 | |
118 | /// This represents an instruction in our IR. |
119 | class Instruction : public Value, public TaggedListNode<Instruction> { |
120 | public: |
121 | using Operand = InstructionOperand; |
122 | |
123 | private: |
124 | friend struct InstructionTraits; |
125 | friend IRFunction; |
126 | |
127 | /// Parent function. |
128 | IRFunction *F_; |
129 | /// If a predicate is set this index points to the non-zero index of the |
130 | /// predicate in the instruction list. |
131 | unsigned predicateIndex_{0}; |
132 | |
133 | /// A list of operands that the instruction has. This is typically a very |
134 | /// short list. |
135 | llvm::SmallVector<Operand, 6> ops_{}; |
136 | |
137 | // Define/disallow default ctor, copy ctor and assignment operator. |
138 | Instruction(const Instruction &I) = delete; |
139 | Instruction &operator=(const Instruction &I) = delete; |
140 | |
141 | /// Destroy an instruction and deallocate its memory. This function is |
142 | /// automatically invoked when the instruction is being deleted from the list |
143 | /// of instructions. |
144 | static void destroyInstruction(Instruction *I); |
145 | |
146 | public: |
147 | /// Prevent the destruction of a derived object via a base-class pointer. |
148 | /// Use IRFunction::destroyInstruction instead. |
149 | ~Instruction() { |
150 | for (unsigned idx = 0, e = ops_.size(); idx < e; ++idx) { |
151 | setOperand(idx, nullptr); |
152 | } |
153 | } |
154 | |
155 | public: |
156 | /// \returns the nullable predicate of the current node. |
157 | Value *getPredicate() const; |
158 | /// Assigns a nullable predicate to the current node. |
159 | void setPredicate(Value *p); |
160 | /// Checks if a predicate is assigned to the current node. |
161 | bool hasPredicate() const; |
162 | |
163 | /// Adds a new operand \p op at the end of the operand list. |
164 | void pushOperand(Operand op); |
165 | |
166 | Instruction(llvm::StringRef name, Kinded::Kind k, TypeRef Ty) |
167 | : Value(name, Ty, k), F_(nullptr) {} |
168 | |
169 | Instruction(llvm::StringRef name, Kinded::Kind k, TypeRef Ty, |
170 | llvm::ArrayRef<Operand> ops) |
171 | : Value(name, Ty, k), F_(nullptr) { |
172 | for (auto &op : ops) { |
173 | pushOperand(op); |
174 | } |
175 | } |
176 | |
177 | /// Clone the current instruction. |
178 | /// \returns a cloned instruction. |
179 | Instruction *clone() const; |
180 | |
181 | /// \returns True if this instruction may reuse the memory buffer read by |
182 | /// operand \p srcIdx for writing the result of the operand at \p dstIdx. |
183 | bool isInplaceOp(unsigned dstIdx, unsigned srcIdx) const { return false; } |
184 | |
185 | /// \returns True if this instruction is not backend-specific. |
186 | bool isCanonical() const; |
187 | |
188 | /// \returns True if this instruction is data parallel. |
189 | bool isDataParallel() const; |
190 | |
191 | /// Sets the ith operand at index \p idx to the value \p v. |
192 | void setOperand(unsigned idx, Value *v); |
193 | |
194 | /// \returns the ith operand. |
195 | Operand getOperand(unsigned idx) const; |
196 | |
197 | /// \returns the number of operands. |
198 | unsigned getNumOperands() const { return ops_.size(); } |
199 | |
200 | /// \returns the number of input operands (includes In and InOut operands). |
201 | unsigned getNumInputs() const; |
202 | |
203 | /// \returns the number of output operands (includes Out and InOut operands). |
204 | unsigned getNumOutputs() const; |
205 | |
206 | /// \returns the operands of the instruction. |
207 | llvm::ArrayRef<Operand> getOperands() const { return ops_; } |
208 | |
209 | /// \returns the name of the operand. |
210 | llvm::StringRef getOperandName(unsigned idx) const; |
211 | |
212 | /// Check the correctness of the use-list. |
213 | bool verifyUseList(const InstructionNumbering &InstrNumbering) const; |
214 | |
215 | /// Verify the correctness of the instruction parameters. |
216 | bool verify() const; |
217 | |
218 | /// The static dispatch version of isInplaceOp. |
219 | static bool isInplaceOp(const Instruction *I, unsigned dstIdx, |
220 | unsigned srcIdx); |
221 | |
222 | /// \returns parent of current instruction. |
223 | const IRFunction *getParent() const { return F_; } |
224 | IRFunction *getParent() { return F_; } |
225 | |
226 | /// Sets a parent for the current instruction. |
227 | void setParent(IRFunction *Mod) { F_ = Mod; } |
228 | |
229 | /// Erases instruction from its parent and destroy it. |
230 | void eraseFromParent(); |
231 | |
232 | /// Removes instruction from its parent, but does not destroy it. |
233 | /// The instruction can be inserted elsewhere afterwards. |
234 | void removeFromParent(); |
235 | |
236 | static bool classof(const Value *V); |
237 | |
238 | static bool classof(const Instruction *I) { return true; } |
239 | |
240 | protected: |
241 | /// Dump the operands of the instruction into the stream \p os. |
242 | void dumpOperands(llvm::raw_ostream &os) const; |
243 | }; |
244 | |
245 | /// Different stages of processing an IR instruction. Transitions between stages |
246 | /// always happen in the same order as they are defined below, i.e. |
247 | /// PROCESSING -> POSTPROCESSING |
248 | /// In particular, there is no possibility for any transition in the backwards |
249 | /// direction. |
250 | enum class IRInstructionProcessingStage { |
251 | /// Instruction is being processed. |
252 | PROCESSING, |
253 | /// Instruction was just processed. |
254 | POSTPROCESSING, |
255 | }; |
256 | |
257 | /// A function for processing instructions e.g. during a code generation or |
258 | /// during a code execution of instructions by backends. A processing function |
259 | /// takes an instruction \p I, a current instruction execution stage \p |
260 | /// executionStage and current context \p ctx as inputs, processes the |
261 | /// instruction and \returns true if the client should proceed to the next |
262 | /// execution stage or false if the client should proceed with the current |
263 | /// execution stage. The processing of the instruction will continue by the |
264 | /// caller (e.g. by a backend) from this stage. For example, if this processing |
265 | /// function has processed the instruction it may decide to return a stage |
266 | /// indicating that the processing has finished so that the caller does not |
267 | /// process it anymore. The passed \p ctx can be anything, e.g. a backend, an |
268 | /// ExecutionContext, etc. |
269 | using IRInstructionProcessingFn = |
270 | std::function<bool(const Instruction *I, |
271 | IRInstructionProcessingStage executionStage, void *ctx)>; |
272 | |
273 | /// The interface class for IR instruction handlers. Useful for intercepting IR |
274 | /// instructions processing. |
275 | class IRInstructionProcessingHandler { |
276 | public: |
277 | IRInstructionProcessingHandler() = default; |
278 | virtual ~IRInstructionProcessingHandler() = default; |
279 | /// Set the handler to be used for IR instruction processing. |
280 | virtual void |
281 | setIRInstructionProcessingHandler(IRInstructionProcessingFn hook) { |
282 | handler_ = hook; |
283 | } |
284 | /// \returns the handler to be used for IR instructions processing. |
285 | virtual const IRInstructionProcessingFn & |
286 | getIRInstructionProcessingHandler() const { |
287 | return handler_; |
288 | } |
289 | |
290 | protected: |
291 | /// The handler function to be used for instruction processing. |
292 | glow::IRInstructionProcessingFn handler_; |
293 | }; |
294 | |
295 | //===----------------------------------------------------------------------===// |
296 | // TaggedListTraits for glow::Instruction |
297 | //===----------------------------------------------------------------------===// |
298 | |
299 | struct InstructionTraits : public TaggedListTraits<Instruction> { |
300 | static void deleteNode(Instruction *V) { Instruction::destroyInstruction(V); } |
301 | |
302 | void addNodeToList(Instruction *I); |
303 | void removeNodeFromList(Instruction *I); |
304 | |
305 | private: |
306 | IRFunction *getContainingFunction(); |
307 | void createNode(const Instruction &); |
308 | }; |
309 | |
310 | class Backend; |
311 | class WeightVar; |
312 | class Value; |
313 | class Node; |
314 | |
315 | /// A function that represents the compilation unit. |
316 | class IRFunction final : public IRContainer { |
317 | public: |
318 | using VariableMap = llvm::MapVector<const Storage *, Value *>; |
319 | using InstListTy = TaggedList<Instruction, InstructionTraits>; |
320 | using InstrIterator = InstListTy::iterator; |
321 | using InstrConstIterator = InstListTy::const_iterator; |
322 | using WeightVarListTy = std::list<WeightVar *>; |
323 | |
324 | private: |
325 | /// A pointer to the graph structure. The function does not own the graph. |
326 | IRContainer *G_{}; |
327 | |
328 | /// A list of weights. Weights are shared between all execution context. |
329 | WeightVarListTy weights_{}; |
330 | |
331 | /// A list of instruction that represent the network. |
332 | InstListTy instrs_{}; |
333 | |
334 | /// Maps Variable nodes in the original graph to the weight values that |
335 | /// represent them in the lower IR. |
336 | VariableMap variableMap_{}; |
337 | |
338 | /// A list of unique instruction names use by the function. |
339 | llvm::StringSet<> stringTable_; |
340 | |
341 | /// Perform scheduling on the graph. |
342 | /// \returns computed schedule in the \p Schedule parameter. |
343 | void scheduleGraph(NodesPtrList &Schedule); |
344 | |
345 | public: |
346 | /// Add an instruction to the instr stream. |
347 | void pushInstr(Instruction *I) { instrs_.push_back(I); } |
348 | |
349 | explicit IRFunction(IRContainer *G = nullptr); |
350 | |
351 | ~IRFunction(); |
352 | |
353 | IRKind getIRKind() const override { return IRKind::GlowInstructionIRKind; }; |
354 | |
355 | static bool classof(const IRContainer *I) { |
356 | return I->getIRKind() == IRKind::GlowInstructionIRKind; |
357 | } |
358 | |
359 | static bool classof(const IRFunction *I) { return true; } |
360 | |
361 | /// Generate IR from the graph nodes. If the compilation mode is 'training' |
362 | /// then this procedure will also generate the code for the backward pass. |
363 | /// It allows Backend \p B to custom translate from a Node to Instruction IR. |
364 | void generateIR(const Backend &B); |
365 | |
366 | /// Wipe out the content of the function. This allows the function to be used |
367 | /// again for another round of code generation. |
368 | void clear(); |
369 | |
370 | /// Clone the current IR function into a new function with the name \p newName |
371 | /// in the same module. If \p map is non-null then the procedure records the |
372 | /// mapping between the old node to the new node in \p map. If \p currToNewMap |
373 | /// is non-null it is used as the initial state of the currToNew map inside |
374 | /// the cloner. |
375 | /// \returns a new function that is a copy of the current function. |
376 | IRFunction * |
377 | clone(llvm::StringRef newName, |
378 | llvm::DenseMap<const Value *, Value *> *map = nullptr, |
379 | llvm::DenseMap<const Value *, Value *> *currToNewMap = nullptr); |
380 | |
381 | /// Clone the current function into a user-provided function \p newF. The |
382 | /// function \p newF is not automatically added to a module by the clone call. |
383 | /// If \p map is non-null then the procedure records the mapping between the |
384 | /// old node to the new node in \p map. If \p currToNewMap is non-null it is |
385 | /// used as the initial state of the currToNew map inside the cloner. \returns |
386 | /// a user-provided function \p newF that now contains a clone of the current |
387 | /// function. |
388 | IRFunction * |
389 | clone(IRFunction *newF, llvm::DenseMap<const Value *, Value *> *map = nullptr, |
390 | llvm::DenseMap<const Value *, Value *> *currToNewMap = nullptr) const; |
391 | |
392 | /// \returns a reference to the high-level graph without down casting it to |
393 | /// children types like Function or FXIRWrapper. |
394 | IRContainer *getRawGraph() { return G_; } |
395 | |
396 | /// \returns a reference to the high-level graph. |
397 | Function *getGraph() { |
398 | assert(llvm::isa<Function>(G_)); |
399 | return llvm::cast<Function>(G_); |
400 | } |
401 | |
402 | /// \returns a reference to the high-level graph. |
403 | const Function *getGraph() const { |
404 | assert(llvm::isa<Function>(G_)); |
405 | return llvm::cast<Function>(G_); |
406 | } |
407 | |
408 | #if FACEBOOK_INTERNAL |
409 | /// \returns a reference to the glow FX graph. |
410 | FXIRWrapper *getFXGraph(); |
411 | |
412 | /// \returns a reference to the glow FX graph. |
413 | const FXIRWrapper *getFXGraph() const; |
414 | #endif |
415 | |
416 | Module *getParent() override { return G_->getParent(); } |
417 | |
418 | const Module *getParent() const override { return G_->getParent(); } |
419 | |
420 | /// Sets the high-level graph corresponding to this function. |
421 | void setGraph(Function *F) { G_ = F; } |
422 | |
423 | /// \returns a unique legal name that's based on the string \p name. Legal |
424 | /// names are legal C identifiers in the form: "[a-zA-Z_][a-zA-Z0-9_]*". |
425 | llvm::StringRef uniqueName(llvm::StringRef name) { |
426 | return Module::uniqueName(name, stringTable_, stringTable_, |
427 | *getParent()->getOriginalNames()); |
428 | } |
429 | |
430 | /// Verify the correctness of the function. |
431 | bool verify() const; |
432 | |
433 | /// Dump a textual representation of the IRFunction into default output |
434 | /// stream. |
435 | void dump() const; |
436 | |
437 | /// Dump a textual representation of the IRFunction to std::string. |
438 | std::string toString() const; |
439 | |
440 | /// Dump a textual representation of the IRFunction into provided output |
441 | /// stream. |
442 | void dump(llvm::raw_ostream &OS) const; |
443 | |
444 | /// Dump a dotty graph that depicts the function. |
445 | void dumpDAG(llvm::StringRef dotFilename) const; |
446 | |
447 | /// Dump a dotty graph that depicts the function. |
448 | void dumpDAG(const char *dotFilename) const; |
449 | |
450 | /// Dump a dotty graph that depicts the function. |
451 | void dumpDAG() const; |
452 | |
453 | /// \returns the variable map. |
454 | VariableMap &getVariableMap() { return variableMap_; } |
455 | |
456 | /// \returns the variable map. |
457 | const VariableMap &getVariableMap() const { return variableMap_; } |
458 | |
459 | /// Returns a list of constants associated with function. |
460 | std::vector<const Constant *> findConstants() const; |
461 | |
462 | /// Returns a list of placeholders associated with the function. |
463 | std::vector<const Placeholder *> findPlaceholders() const; |
464 | |
465 | /// \returns the weight that the variable \p v is lowered into, or null if the |
466 | /// variable is unknown. |
467 | Value *getWeightForNode(const Storage *V) const; |
468 | |
469 | /// \returns the list of instructions. |
470 | InstListTy &getInstrs() { return instrs_; } |
471 | |
472 | /// \returns the list of instructions. |
473 | const InstListTy &getInstrs() const { return instrs_; } |
474 | |
475 | /// \returns pointer to the class member for the instruction list. |
476 | static InstListTy IRFunction::*getInstrsMemberPtr() { |
477 | return &IRFunction::instrs_; |
478 | } |
479 | |
480 | /// \returns the list of weights. |
481 | WeightVarListTy &getWeights() { return weights_; } |
482 | |
483 | /// \returns the list of weights. |
484 | const WeightVarListTy &getWeights() const { return weights_; } |
485 | |
486 | /// Erase the instruction from the function. |
487 | void eraseInstruction(Instruction *I); |
488 | |
489 | /// Remove the instruction from the function. |
490 | InstrIterator removeInstruction(Instruction *I); |
491 | |
492 | /// Inserts an instruction at the place described by \where. |
493 | InstrIterator insertInstruction(Instruction *where, Instruction *I); |
494 | |
495 | /// Inserts an instruction at the end of the instructions list. |
496 | void insertInstruction(Instruction *I); |
497 | |
498 | /// Moves an instruction belonging to a function before the place described by |
499 | /// \where. |
500 | InstrIterator moveInstruction(Instruction *where, Instruction *I); |
501 | }; |
502 | |
503 | /// Iterator over inteructions. |
504 | using InstrIterator = IRFunction::InstrIterator; |
505 | using InstrConstIterator = IRFunction::InstrConstIterator; |
506 | |
507 | /// A helper class used for instructions numbering. |
508 | class InstructionNumbering { |
509 | using NumberedInstructionMap = std::vector<const Instruction *>; |
510 | using InstructionNumbersMap = std::unordered_map<const Instruction *, size_t>; |
511 | /// Maps the number to an instruction. |
512 | NumberedInstructionMap numToInstr_; |
513 | /// Maps an instruction to its number. |
514 | InstructionNumbersMap instrToNum_; |
515 | |
516 | public: |
517 | InstructionNumbering(const IRFunction &M); |
518 | |
519 | /// Return the instruction with a given number or |
520 | /// M.getInstrs().end() if this instruction is not assigned any number. |
521 | const Instruction *getInstr(size_t InstrNumber) const; |
522 | |
523 | /// Return the number of an instruction or a negative value if no number |
524 | /// was assigned to this instruction. |
525 | int64_t getInstrNumber(const Instruction *I) const; |
526 | }; |
527 | |
528 | llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const Value &V); |
529 | |
530 | llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const Value *V); |
531 | |
532 | llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const IRFunction &irf); |
533 | |
534 | llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const IRFunction *irf); |
535 | |
536 | /// IR instrumentation kind. |
537 | enum class InstrumentKind : unsigned char { |
538 | /// Instrumentation before an instruction is executed. |
539 | Before, |
540 | /// Instrumentation after an instruction is executed. |
541 | After, |
542 | }; |
543 | |
544 | llvm::raw_ostream &operator<<(llvm::raw_ostream &os, InstrumentKind kind); |
545 | |
546 | } // namespace glow |
547 | |
548 | #endif // GLOW_IR_IR_H |
549 | |