← Back to branch summary

~mmach/netext73/mesa-haswell

« back to all changes in this revision

Viewing changes to src/compiler/nir/nir_worklist.c

  • Committer: mmach
  • Date: 2022-09-22 19:56:13 UTC
  • Revision ID: netbit73@gmail.com-20220922195613-wtik9mmy20tmor0i
2022-09-22 21:17:09

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/compiler/nir/nir_worklist.c
1
 
/*
2
 
 * Copyright © 2014 Intel Corporation
3
 
 *
4
 
 * Permission is hereby granted, free of charge, to any person obtaining a
5
 
 * copy of this software and associated documentation files (the "Software"),
6
 
 * to deal in the Software without restriction, including without limitation
7
 
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8
 
 * and/or sell copies of the Software, and to permit persons to whom the
9
 
 * Software is furnished to do so, subject to the following conditions:
10
 
 *
11
 
 * The above copyright notice and this permission notice (including the next
12
 
 * paragraph) shall be included in all copies or substantial portions of the
13
 
 * Software.
14
 
 *
15
 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16
 
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17
 
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
18
 
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19
 
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20
 
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
21
 
 * IN THE SOFTWARE.
22
 
 *
23
 
 * Authors:
24
 
 *    Jason Ekstrand (jason@jlekstrand.net)
25
 
 *
26
 
 */
27
 
 
28
 
#include "nir_worklist.h"
29
 
 
30
 
void
31
 
nir_block_worklist_init(nir_block_worklist *w, unsigned num_blocks,
32
 
                        void *mem_ctx)
33
 
{
34
 
   w->size = num_blocks;
35
 
   w->count = 0;
36
 
   w->start = 0;
37
 
 
38
 
   w->blocks_present = rzalloc_array(mem_ctx, BITSET_WORD,
39
 
                                     BITSET_WORDS(num_blocks));
40
 
   w->blocks = rzalloc_array(mem_ctx, nir_block *, num_blocks);
41
 
}
42
 
 
43
 
void
44
 
nir_block_worklist_fini(nir_block_worklist *w)
45
 
{
46
 
   ralloc_free(w->blocks_present);
47
 
   ralloc_free(w->blocks);
48
 
}
49
 
 
50
 
void
51
 
nir_block_worklist_add_all(nir_block_worklist *w, nir_function_impl *impl)
52
 
{
53
 
   nir_foreach_block(block, impl) {
54
 
      nir_block_worklist_push_tail(w, block);
55
 
   }
56
 
}
57
 
 
58
 
void
59
 
nir_block_worklist_push_head(nir_block_worklist *w, nir_block *block)
60
 
{
61
 
   /* Pushing a block we already have is a no-op */
62
 
   if (BITSET_TEST(w->blocks_present, block->index))
63
 
      return;
64
 
 
65
 
   assert(w->count < w->size);
66
 
 
67
 
   if (w->start == 0)
68
 
      w->start = w->size - 1;
69
 
   else
70
 
      w->start--;
71
 
 
72
 
   w->count++;
73
 
 
74
 
   w->blocks[w->start] = block;
75
 
   BITSET_SET(w->blocks_present, block->index);
76
 
}
77
 
 
78
 
nir_block *
79
 
nir_block_worklist_peek_head(const nir_block_worklist *w)
80
 
{
81
 
   assert(w->count > 0);
82
 
 
83
 
   return w->blocks[w->start];
84
 
}
85
 
 
86
 
nir_block *
87
 
nir_block_worklist_pop_head(nir_block_worklist *w)
88
 
{
89
 
   assert(w->count > 0);
90
 
 
91
 
   unsigned head = w->start;
92
 
 
93
 
   w->start = (w->start + 1) % w->size;
94
 
   w->count--;
95
 
 
96
 
   BITSET_CLEAR(w->blocks_present, w->blocks[head]->index);
97
 
   return w->blocks[head];
98
 
}
99
 
 
100
 
void
101
 
nir_block_worklist_push_tail(nir_block_worklist *w, nir_block *block)
102
 
{
103
 
   /* Pushing a block we already have is a no-op */
104
 
   if (BITSET_TEST(w->blocks_present, block->index))
105
 
      return;
106
 
 
107
 
   assert(w->count < w->size);
108
 
 
109
 
   w->count++;
110
 
 
111
 
   unsigned tail = (w->start + w->count - 1) % w->size;
112
 
 
113
 
   w->blocks[tail] = block;
114
 
   BITSET_SET(w->blocks_present, block->index);
115
 
}
116
 
 
117
 
nir_block *
118
 
nir_block_worklist_peek_tail(const nir_block_worklist *w)
119
 
{
120
 
   assert(w->count > 0);
121
 
 
122
 
   unsigned tail = (w->start + w->count - 1) % w->size;
123
 
 
124
 
   return w->blocks[tail];
125
 
}
126
 
 
127
 
nir_block *
128
 
nir_block_worklist_pop_tail(nir_block_worklist *w)
129
 
{
130
 
   assert(w->count > 0);
131
 
 
132
 
   unsigned tail = (w->start + w->count - 1) % w->size;
133
 
 
134
 
   w->count--;
135
 
 
136
 
   BITSET_CLEAR(w->blocks_present, w->blocks[tail]->index);
137
 
   return w->blocks[tail];
138
 
}
139
 
 
140
 
static bool
141
 
nir_instr_worklist_add_srcs_cb(nir_src *src, void *state)
142
 
{
143
 
   nir_instr_worklist *wl = state;
144
 
 
145
 
   if (src->is_ssa)
146
 
      nir_instr_worklist_push_tail(wl, src->ssa->parent_instr);
147
 
 
148
 
   return true;
149
 
}
150
 
 
151
 
void
152
 
nir_instr_worklist_add_ssa_srcs(nir_instr_worklist *wl, nir_instr *instr)
153
 
{
154
 
   nir_foreach_src(instr, nir_instr_worklist_add_srcs_cb, wl);
155
 
}