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
35namespace glow {
36class FXIRWrapper;
37}
38#endif
39
40namespace glow {
41class Instruction;
42class IRFunction;
43class Function;
44class Value;
45class InstructionNumbering;
46
47enum class OperandKind : unsigned char {
48 In,
49 InOut,
50 Out,
51};
52
53inline const char *getOperandKindStr(OperandKind CC) {
54 const char *names[] = {"@in", "@inout", "@out", nullptr};
55 return names[(int)CC];
56}
57
58using InstructionOperand = std::pair<Value *, OperandKind>;
59using 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.
63struct 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
89class Value : public Named,
90 public UseDef<Instruction, Use>,
91 public Typed,
92 public Kinded {
93public:
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.
119class Instruction : public Value, public TaggedListNode<Instruction> {
120public:
121 using Operand = InstructionOperand;
122
123private:
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
146public:
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
155public:
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
240protected:
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.
250enum 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.
269using 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.
275class IRInstructionProcessingHandler {
276public:
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
290protected:
291 /// The handler function to be used for instruction processing.
292 glow::IRInstructionProcessingFn handler_;
293};
294
295//===----------------------------------------------------------------------===//
296// TaggedListTraits for glow::Instruction
297//===----------------------------------------------------------------------===//
298
299struct 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
305private:
306 IRFunction *getContainingFunction();
307 void createNode(const Instruction &);
308};
309
310class Backend;
311class WeightVar;
312class Value;
313class Node;
314
315/// A function that represents the compilation unit.
316class IRFunction final : public IRContainer {
317public:
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
324private:
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
345public:
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.
504using InstrIterator = IRFunction::InstrIterator;
505using InstrConstIterator = IRFunction::InstrConstIterator;
506
507/// A helper class used for instructions numbering.
508class 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
516public:
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
528llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const Value &V);
529
530llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const Value *V);
531
532llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const IRFunction &irf);
533
534llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const IRFunction *irf);
535
536/// IR instrumentation kind.
537enum class InstrumentKind : unsigned char {
538 /// Instrumentation before an instruction is executed.
539 Before,
540 /// Instrumentation after an instruction is executed.
541 After,
542};
543
544llvm::raw_ostream &operator<<(llvm::raw_ostream &os, InstrumentKind kind);
545
546} // namespace glow
547
548#endif // GLOW_IR_IR_H
549