CIRCT  20.0.0git
CombAnalysis.cpp
Go to the documentation of this file.
1 //===- CombAnalysis.cpp - Analysis Helpers for Comb+HW operations ---------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
10 #include "circt/Dialect/HW/HWOps.h"
11 #include "llvm/Support/KnownBits.h"
12 
13 using namespace circt;
14 using namespace comb;
15 
16 /// Given an integer SSA value, check to see if we know anything about the
17 /// result of the computation. For example, we know that "and with a constant"
18 /// always returns zeros for the zero bits in a constant.
19 ///
20 /// Expression trees can be very large, so we need ot make sure to cap our
21 /// recursion, this is controlled by `depth`.
22 static KnownBits computeKnownBits(Value v, unsigned depth) {
23  Operation *op = v.getDefiningOp();
24  if (!op || depth == 5)
25  return KnownBits(v.getType().getIntOrFloatBitWidth());
26 
27  // A constant has all bits known!
28  if (auto constant = dyn_cast<hw::ConstantOp>(op))
29  return KnownBits::makeConstant(constant.getValue());
30 
31  // `concat(x, y, z)` has whatever is known about the operands concat'd.
32  if (auto concatOp = dyn_cast<ConcatOp>(op)) {
33  auto result = computeKnownBits(concatOp.getOperand(0), depth + 1);
34  for (size_t i = 1, e = concatOp.getNumOperands(); i != e; ++i) {
35  auto otherBits = computeKnownBits(concatOp.getOperand(i), depth + 1);
36  unsigned width = otherBits.getBitWidth();
37  unsigned newWidth = result.getBitWidth() + width;
38  result.Zero =
39  (result.Zero.zext(newWidth) << width) | otherBits.Zero.zext(newWidth);
40  result.One =
41  (result.One.zext(newWidth) << width) | otherBits.One.zext(newWidth);
42  }
43  return result;
44  }
45 
46  // `and(x, y, z)` has whatever is known about the operands intersected.
47  if (auto andOp = dyn_cast<AndOp>(op)) {
48  auto result = computeKnownBits(andOp.getOperand(0), depth + 1);
49  for (size_t i = 1, e = andOp.getNumOperands(); i != e; ++i)
50  result &= computeKnownBits(andOp.getOperand(i), depth + 1);
51  return result;
52  }
53 
54  // `or(x, y, z)` has whatever is known about the operands unioned.
55  if (auto orOp = dyn_cast<OrOp>(op)) {
56  auto result = computeKnownBits(orOp.getOperand(0), depth + 1);
57  for (size_t i = 1, e = orOp.getNumOperands(); i != e; ++i)
58  result |= computeKnownBits(orOp.getOperand(i), depth + 1);
59  return result;
60  }
61 
62  // `xor(x, cst)` inverts known bits and passes through unmodified ones.
63  if (auto xorOp = dyn_cast<XorOp>(op)) {
64  auto result = computeKnownBits(xorOp.getOperand(0), depth + 1);
65  for (size_t i = 1, e = xorOp.getNumOperands(); i != e; ++i) {
66  // If we don't know anything, we don't need to evaluate more subexprs.
67  if (result.isUnknown())
68  return result;
69  result ^= computeKnownBits(xorOp.getOperand(i), depth + 1);
70  }
71  return result;
72  }
73 
74  // `mux(cond, x, y)` is the intersection of the known bits of `x` and `y`.
75  if (auto muxOp = dyn_cast<MuxOp>(op)) {
76  auto lhs = computeKnownBits(muxOp.getTrueValue(), depth + 1);
77  auto rhs = computeKnownBits(muxOp.getFalseValue(), depth + 1);
78  return lhs.intersectWith(rhs);
79  }
80 
81  return KnownBits(v.getType().getIntOrFloatBitWidth());
82 }
83 
84 /// Given an integer SSA value, check to see if we know anything about the
85 /// result of the computation. For example, we know that "and with a
86 /// constant" always returns zeros for the zero bits in a constant.
87 KnownBits comb::computeKnownBits(Value value) {
88  return ::computeKnownBits(value, 0);
89 }
static KnownBits computeKnownBits(Value v, unsigned depth)
Given an integer SSA value, check to see if we know anything about the result of the computation.
int32_t width
Definition: FIRRTL.cpp:36
KnownBits computeKnownBits(Value value)
Compute "known bits" information about the specified value - the set of bits that are guaranteed to a...
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
Definition: DebugAnalysis.h:21
Definition: comb.py:1