1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
|
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Known Bits Analysis — LLVM 13 documentation</title>
<link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
<link rel="stylesheet" href="../_static/llvm-theme.css" type="text/css" />
<script id="documentation_options" data-url_root="../" src="../_static/documentation_options.js"></script>
<script src="../_static/jquery.js"></script>
<script src="../_static/underscore.js"></script>
<script src="../_static/doctools.js"></script>
<link rel="index" title="Index" href="../genindex.html" />
<link rel="search" title="Search" href="../search.html" />
<link rel="next" title="GWP-ASan" href="../GwpAsan.html" />
<link rel="prev" title="Resources" href="Resources.html" />
<style type="text/css">
table.right { float: right; margin-left: 20px; }
table.right td { border: 1px solid #ccc; }
</style>
</head><body>
<div class="logo">
<a href="../index.html">
<img src="../_static/logo.png"
alt="LLVM Logo" width="250" height="88"/></a>
</div>
<div class="related" role="navigation" aria-label="related navigation">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="../genindex.html" title="General Index"
accesskey="I">index</a></li>
<li class="right" >
<a href="../GwpAsan.html" title="GWP-ASan"
accesskey="N">next</a> |</li>
<li class="right" >
<a href="Resources.html" title="Resources"
accesskey="P">previous</a> |</li>
<li><a href="https://llvm.org/">LLVM Home</a> | </li>
<li><a href="../index.html">Documentation</a>»</li>
<li class="nav-item nav-item-1"><a href="../Reference.html" >Reference</a> »</li>
<li class="nav-item nav-item-2"><a href="index.html" accesskey="U">Global Instruction Selection</a> »</li>
<li class="nav-item nav-item-this"><a href="">Known Bits Analysis</a></li>
</ul>
</div>
<div class="sphinxsidebar" role="navigation" aria-label="main navigation">
<div class="sphinxsidebarwrapper">
<h3>Documentation</h3>
<ul class="want-points">
<li><a href="https://llvm.org/docs/GettingStartedTutorials.html">Getting Started/Tutorials</a></li>
<li><a href="https://llvm.org/docs/UserGuides.html">User Guides</a></li>
<li><a href="https://llvm.org/docs/Reference.html">Reference</a></li>
</ul>
<h3>Getting Involved</h3>
<ul class="want-points">
<li><a href="https://llvm.org/docs/Contributing.html">Contributing to LLVM</a></li>
<li><a href="https://llvm.org/docs/HowToSubmitABug.html">Submitting Bug Reports</a></li>
<li><a href="https://llvm.org/docs/GettingInvolved.html#mailing-lists">Mailing Lists</a></li>
<li><a href="https://llvm.org/docs/GettingInvolved.html#irc">IRC</a></li>
<li><a href="https://llvm.org/docs/GettingInvolved.html#meetups-and-social-events">Meetups and Social Events</a></li>
</ul>
<h3>Additional Links</h3>
<ul class="want-points">
<li><a href="https://llvm.org/docs/FAQ.html">FAQ</a></li>
<li><a href="https://llvm.org/docs/Lexicon.html">Glossary</a></li>
<li><a href="https://llvm.org/pubs">Publications</a></li>
<li><a href="https://github.com/llvm/llvm-project//">Github Repository</a></li>
</ul>
<div role="note" aria-label="source link">
<h3>This Page</h3>
<ul class="this-page-menu">
<li><a href="../_sources/GlobalISel/KnownBits.rst.txt"
rel="nofollow">Show Source</a></li>
</ul>
</div>
<div id="searchbox" style="display: none" role="search">
<h3 id="searchlabel">Quick search</h3>
<div class="searchformwrapper">
<form class="search" action="../search.html" method="get">
<input type="text" name="q" aria-labelledby="searchlabel" />
<input type="submit" value="Go" />
</form>
</div>
</div>
<script>$('#searchbox').show(0);</script>
</div>
</div>
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body" role="main">
<div class="section" id="known-bits-analysis">
<h1>Known Bits Analysis<a class="headerlink" href="#known-bits-analysis" title="Permalink to this headline">¶</a></h1>
<p>The Known Bits Analysis pass makes information about the known values of bits
available to other passes to enable transformations like those in the examples
below. The information is lazily computed so you should only pay for what you
use.</p>
<div class="section" id="examples">
<h2>Examples<a class="headerlink" href="#examples" title="Permalink to this headline">¶</a></h2>
<p>A simple example is that transforming:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">a</span> <span class="o">+</span> <span class="mi">1</span>
</pre></div>
</div>
<p>into:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">a</span> <span class="o">|</span> <span class="mi">1</span>
</pre></div>
</div>
<p>is only valid when the addition doesn’t carry. In other words it’s only valid
if <code class="docutils literal notranslate"><span class="pre">a</span> <span class="pre">&</span> <span class="pre">1</span></code> is zero.</p>
<p>Another example is:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>%1:(s32) = G_CONSTANT i32 0xFF0
%2:(s32) = G_AND %0, %1
%3:(s32) = G_CONSTANT i32 0x0FF
%4:(s32) = G_AND %2, %3
</pre></div>
</div>
<p>We can use the constants and the definition of <code class="docutils literal notranslate"><span class="pre">G_AND</span></code> to determine the known
bits:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span> ; %0 = 0x????????
%1:(s32) = G_CONSTANT i32 0xFF0 ; %1 = 0x00000FF0
%2:(s32) = G_AND %0, %1 ; %2 = 0x00000??0
%3:(s32) = G_CONSTANT i32 0x0FF ; %3 = 0x000000FF
%4:(s32) = G_AND %2, %3 ; %4 = 0x000000?0
</pre></div>
</div>
<p>and then use this to simplify the expression:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span> ; %0 = 0x????????
%5:(s32) = G_CONSTANT i32 0x0F0 ; %5 = 0x00000FF0
%4:(s32) = G_AND %0, %5 ; %4 = 0x000000?0
</pre></div>
</div>
<p>Note that <code class="docutils literal notranslate"><span class="pre">%4</span></code> still has the same known bits as before the transformation.
Many transformations share this property. The main exception being when the
transform causes undefined bits to become defined to either zero, one, or
defined but unknown.</p>
</div>
<div class="section" id="usage">
<h2>Usage<a class="headerlink" href="#usage" title="Permalink to this headline">¶</a></h2>
<p>To use Known Bits Analysis in a pass, first include the header and register the
dependency with <code class="docutils literal notranslate"><span class="pre">INITIALIZE_PASS_DEPENDENCY</span></code>.</p>
<div class="highlight-c++ notranslate"><div class="highlight"><pre><span></span><span class="cp">#include</span> <span class="cpf">"llvm/CodeGen/GlobalISel/GISelKnownBits.h"</span><span class="cp"></span>
<span class="p">...</span>
<span class="n">INITIALIZE_PASS_BEGIN</span><span class="p">(...)</span>
<span class="n">INITIALIZE_PASS_DEPENDENCY</span><span class="p">(</span><span class="n">GISelKnownBitsAnalysis</span><span class="p">)</span>
<span class="n">INITIALIZE_PASS_END</span><span class="p">(...)</span>
</pre></div>
</div>
<p>and require the pass in <code class="docutils literal notranslate"><span class="pre">getAnalysisUsage</span></code>.</p>
<div class="highlight-c++ notranslate"><div class="highlight"><pre><span></span><span class="kt">void</span> <span class="n">MyPass</span><span class="o">::</span><span class="n">getAnalysisUsage</span><span class="p">(</span><span class="n">AnalysisUsage</span> <span class="o">&</span><span class="n">AU</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
<span class="n">AU</span><span class="p">.</span><span class="n">addRequired</span><span class="o"><</span><span class="n">GISelKnownBitsAnalysis</span><span class="o">></span><span class="p">();</span>
<span class="c1">// Optional: If your pass preserves known bits analysis (many do) then</span>
<span class="c1">// indicate that it's preserved for re-use by another pass here.</span>
<span class="n">AU</span><span class="p">.</span><span class="n">addPreserved</span><span class="o"><</span><span class="n">GISelKnownBitsAnalysis</span><span class="o">></span><span class="p">();</span>
<span class="p">}</span>
</pre></div>
</div>
<p>Then it’s just a matter of fetching the analysis and using it:</p>
<div class="highlight-c++ notranslate"><div class="highlight"><pre><span></span><span class="kt">bool</span> <span class="n">MyPass</span><span class="o">::</span><span class="n">runOnMachineFunction</span><span class="p">(</span><span class="n">MachineFunction</span> <span class="o">&</span><span class="n">MF</span><span class="p">)</span> <span class="p">{</span>
<span class="p">...</span>
<span class="n">GISelKnownBits</span> <span class="o">&</span><span class="n">KB</span> <span class="o">=</span> <span class="n">getAnalysis</span><span class="o"><</span><span class="n">GISelKnownBitsAnalysis</span><span class="o">></span><span class="p">().</span><span class="n">get</span><span class="p">(</span><span class="n">MF</span><span class="p">);</span>
<span class="p">...</span>
<span class="n">MachineInstr</span> <span class="o">*</span><span class="n">MI</span> <span class="o">=</span> <span class="p">...;</span>
<span class="n">KnownBits</span> <span class="n">Known</span> <span class="o">=</span> <span class="n">KB</span><span class="o">-></span><span class="n">getKnownBits</span><span class="p">(</span><span class="n">MI</span><span class="o">-></span><span class="n">getOperand</span><span class="p">(</span><span class="mi">0</span><span class="p">).</span><span class="n">getReg</span><span class="p">());</span>
<span class="k">if</span> <span class="p">(</span><span class="n">Known</span><span class="p">.</span><span class="n">Zeros</span> <span class="o">&</span> <span class="mi">1</span><span class="p">)</span> <span class="p">{</span>
<span class="c1">// Bit 0 is known to be zero</span>
<span class="p">}</span>
<span class="p">...</span>
<span class="p">}</span>
</pre></div>
</div>
<p>There are many more API’s beyond <code class="docutils literal notranslate"><span class="pre">getKnownBits()</span></code>. See the <a class="reference external" href="https://llvm.org/doxygen">API reference</a> for more information</p>
</div>
</div>
<div class="clearer"></div>
</div>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="related" role="navigation" aria-label="related navigation">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="../genindex.html" title="General Index"
>index</a></li>
<li class="right" >
<a href="../GwpAsan.html" title="GWP-ASan"
>next</a> |</li>
<li class="right" >
<a href="Resources.html" title="Resources"
>previous</a> |</li>
<li><a href="https://llvm.org/">LLVM Home</a> | </li>
<li><a href="../index.html">Documentation</a>»</li>
<li class="nav-item nav-item-1"><a href="../Reference.html" >Reference</a> »</li>
<li class="nav-item nav-item-2"><a href="index.html" >Global Instruction Selection</a> »</li>
<li class="nav-item nav-item-this"><a href="">Known Bits Analysis</a></li>
</ul>
</div>
<div class="footer" role="contentinfo">
© Copyright 2003-2021, LLVM Project.
Last updated on 2021-09-18.
Created using <a href="https://www.sphinx-doc.org/">Sphinx</a> 3.5.4.
</div>
</body>
</html>
|
