1 /*========================== begin_copyright_notice ============================
2 
3 Copyright (C) 2017-2021 Intel Corporation
4 
5 SPDX-License-Identifier: MIT
6 
7 ============================= end_copyright_notice ===========================*/
8 
9 #ifndef _IGA_IR_DUANALYSIS_HPP
10 #define _IGA_IR_DUANALYSIS_HPP
11 
12 #include "../IR/RegSet.hpp"
13 #include "../IR/Kernel.hpp"
14 
15 #include <ostream>
16 #include <string>
17 #include <vector>
18 
19 namespace iga
20 {
21     // A live range is a path from a definition of some register values to
22     // a use.  The use may be a read (typical case) or a write (since we need
23     // to be able to track WAW dependencies).
24     struct Dep
25     {
26         //
27         // The producer instruction;
28         // this can be nullptr if the value is a program input
29         Instruction             *def = nullptr;
30         //
31         // The consumer instruction;
32         // this can be nullptr if the value is a program output
33         Instruction             *use = nullptr;
34         //
35         // The register values that are live in this path
36         RegSet                   values;
37         //
38         // The minimum number of instructions this path covers
39         int                      minInsts = 0;
40         //
41         // The minimum number of instructions this path covers in the same
42         // pipe as the def pipe (or 0 if there is no def).
43         //   int                      minInstsDefPipe = 0;
44         // Need to account syncs in between
45         //
46         // indicates if the dependency crosses a branch (JEU)
47         // N.b. this will false for fallthrough since that isn't a branch
48         //        mov r1 ...
49         // (f0.0) jmpi TARGET
50         //        add ...  r1 // crossesBranch = false here
51         // TARGET:
52         //        mul ...  r1 // crossesBranch = true here
53         bool                     crossesBranch = false;
54         // Similar to the above but includes fallthrough
55         bool                     crossesBlock = false;
56 
57         // Dep(const Model &m) : values(m) { }
58 
Depiga::Dep59         Dep(Instruction *_def, const RegSet &_values, Instruction *_use)
60             : def(_def)
61             , use(_use)
62             , values(_values)
63         {
64         }
65         Dep(const Dep &) = default;
66         Dep &operator=(const Dep &) = default;
67 
68         bool operator==(const Dep &p) const;
operator !=iga::Dep69         bool operator!=(const Dep &p) const { return !(*this == p); }
70 
71         // for debug
72         void str(std::ostream &os) const;
73         std::string str() const;
74     };
75 
76 
77     struct LiveCount {
78         unsigned grfBytes = 0; // r*
79         unsigned flagBytes = 0; // f*
80         unsigned accBytes = 0; // acc*
81         unsigned indexBytes = 0; // a0*
82     };
83 
84     struct DepAnalysis
85     {
86         //
87         // relation of definitions and uses
88         std::vector<Dep>         deps;
89 
90         //
91         // uses without any definition
92         std::vector<Dep>         liveIn;
93 
94         // directly maps instruction ID to the live counts there;
95         // the counts are for the live sets *before* the instruction is
96         // executed
97         std::vector<LiveCount>   sums;
98 
99         // number of iterations until reaching the fixed-point
100         int                      iterations = 0;
101     };
102 
103     // The primary entry point for the live analysis
104     // The counts are counts *going into* this instruction
105     DepAnalysis ComputeDepAnalysis(Kernel *k);
106 } // namespace IGA
107 
108 #endif // _IGA_IR_ANALYSIS_HPP
109