CIRCT 21.0.0git
Loading...
Searching...
No Matches
IMConstProp.cpp
Go to the documentation of this file.
1//===- IMConstProp.cpp - Intermodule ConstProp and DCE ----------*- C++ -*-===//
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//
9// This implements SCCP:
10// https://www.cs.wustl.edu/~cytron/531Pages/f11/Resources/Papers/cprop.pdf
11//
12//===----------------------------------------------------------------------===//
13
20#include "circt/Support/APInt.h"
21#include "mlir/IR/Iterators.h"
22#include "mlir/IR/Threading.h"
23#include "mlir/Pass/Pass.h"
24#include "llvm/ADT/APSInt.h"
25#include "llvm/ADT/TinyPtrVector.h"
26#include "llvm/Support/Debug.h"
27#include "llvm/Support/ScopedPrinter.h"
28
29namespace circt {
30namespace firrtl {
31#define GEN_PASS_DEF_IMCONSTPROP
32#include "circt/Dialect/FIRRTL/Passes.h.inc"
33} // namespace firrtl
34} // namespace circt
35
36using namespace circt;
37using namespace firrtl;
38
39#define DEBUG_TYPE "IMCP"
40
41/// Return true if this is a wire or register.
42static bool isWireOrReg(Operation *op) {
43 return isa<WireOp, RegResetOp, RegOp>(op);
44}
45
46/// Return true if this is an aggregate indexer.
47static bool isAggregate(Operation *op) {
48 return isa<SubindexOp, SubaccessOp, SubfieldOp, OpenSubfieldOp,
49 OpenSubindexOp, RefSubOp>(op);
50}
51
52// Return true if this forwards input to output.
53// Implies has appropriate visit method that propagates changes.
54static bool isNodeLike(Operation *op) {
55 return isa<NodeOp, RefResolveOp, RefSendOp>(op);
56}
57
58/// Return true if this is a wire or register we're allowed to delete.
59static bool isDeletableWireOrRegOrNode(Operation *op) {
60 if (!isWireOrReg(op) && !isa<NodeOp>(op))
61 return false;
62
63 // Always allow deleting wires of probe-type.
64 if (type_isa<RefType>(op->getResult(0).getType()))
65 return true;
66
67 // Otherwise, don't delete if has anything keeping it around or unknown.
68 return AnnotationSet(op).empty() && !hasDontTouch(op) &&
69 hasDroppableName(op) && !cast<Forceable>(op).isForceable();
70}
71
72//===----------------------------------------------------------------------===//
73// Pass Infrastructure
74//===----------------------------------------------------------------------===//
75
76namespace {
77/// This class represents a single lattice value. A lattive value corresponds to
78/// the various different states that a value in the SCCP dataflow analysis can
79/// take. See 'Kind' below for more details on the different states a value can
80/// take.
81class LatticeValue {
82 enum Kind {
83 /// A value with a yet-to-be-determined value. This state may be changed to
84 /// anything, it hasn't been processed by IMConstProp.
85 Unknown,
86
87 /// A value that is known to be a constant. This state may be changed to
88 /// overdefined.
89 Constant,
90
91 /// A value that cannot statically be determined to be a constant. This
92 /// state cannot be changed.
93 Overdefined
94 };
95
96public:
97 /// Initialize a lattice value with "Unknown".
98 /*implicit*/ LatticeValue() : valueAndTag(nullptr, Kind::Unknown) {}
99 /// Initialize a lattice value with a constant.
100 /*implicit*/ LatticeValue(IntegerAttr attr)
101 : valueAndTag(attr, Kind::Constant) {}
102 /*implicit*/ LatticeValue(StringAttr attr)
103 : valueAndTag(attr, Kind::Constant) {}
104
105 static LatticeValue getOverdefined() {
106 LatticeValue result;
107 result.markOverdefined();
108 return result;
109 }
110
111 bool isUnknown() const { return valueAndTag.getInt() == Kind::Unknown; }
112 bool isConstant() const { return valueAndTag.getInt() == Kind::Constant; }
113 bool isOverdefined() const {
114 return valueAndTag.getInt() == Kind::Overdefined;
115 }
116
117 /// Mark the lattice value as overdefined.
118 void markOverdefined() {
119 valueAndTag.setPointerAndInt(nullptr, Kind::Overdefined);
120 }
121
122 /// Mark the lattice value as constant.
123 void markConstant(IntegerAttr value) {
124 valueAndTag.setPointerAndInt(value, Kind::Constant);
125 }
126
127 /// If this lattice is constant or invalid value, return the attribute.
128 /// Returns nullptr otherwise.
129 Attribute getValue() const { return valueAndTag.getPointer(); }
130
131 /// If this is in the constant state, return the attribute.
132 Attribute getConstant() const {
134 return getValue();
135 }
136
137 /// Merge in the value of the 'rhs' lattice into this one. Returns true if the
138 /// lattice value changed.
139 bool mergeIn(LatticeValue rhs) {
140 // If we are already overdefined, or rhs is unknown, there is nothing to do.
141 if (isOverdefined() || rhs.isUnknown())
142 return false;
143
144 // If we are unknown, just take the value of rhs.
145 if (isUnknown()) {
146 valueAndTag = rhs.valueAndTag;
147 return true;
148 }
149
150 // Otherwise, if this value doesn't match rhs go straight to overdefined.
151 // This happens when we merge "3" and "4" from two different instance sites
152 // for example.
153 if (valueAndTag != rhs.valueAndTag) {
154 markOverdefined();
155 return true;
156 }
157 return false;
158 }
159
160 bool operator==(const LatticeValue &other) const {
161 return valueAndTag == other.valueAndTag;
162 }
163 bool operator!=(const LatticeValue &other) const {
164 return valueAndTag != other.valueAndTag;
165 }
166
167private:
168 /// The attribute value if this is a constant and the tag for the element
169 /// kind. The attribute is an IntegerAttr (or BoolAttr) or StringAttr.
170 llvm::PointerIntPair<Attribute, 2, Kind> valueAndTag;
171};
172} // end anonymous namespace
173
174LLVM_ATTRIBUTE_USED
175static llvm::raw_ostream &operator<<(llvm::raw_ostream &os,
176 const LatticeValue &lattice) {
177 if (lattice.isUnknown())
178 return os << "<Unknown>";
179 if (lattice.isOverdefined())
180 return os << "<Overdefined>";
181 return os << "<" << lattice.getConstant() << ">";
182}
183
184namespace {
185struct IMConstPropPass
186 : public circt::firrtl::impl::IMConstPropBase<IMConstPropPass> {
187
188 void runOnOperation() override;
189 void rewriteModuleBody(FModuleOp module);
190
191 /// Returns true if the given block is executable.
192 bool isBlockExecutable(Block *block) const {
193 return executableBlocks.count(block);
194 }
195
196 bool isOverdefined(FieldRef value) const {
197 auto it = latticeValues.find(value);
198 return it != latticeValues.end() && it->second.isOverdefined();
199 }
200
201 // Mark the given value as overdefined. If the value is an aggregate,
202 // we mark all ground elements as overdefined.
203 void markOverdefined(Value value) {
204 FieldRef fieldRef = getOrCacheFieldRefFromValue(value);
205 auto firrtlType = type_dyn_cast<FIRRTLType>(value.getType());
206 if (!firrtlType || type_isa<PropertyType>(firrtlType)) {
207 markOverdefined(fieldRef);
208 return;
209 }
210
211 walkGroundTypes(firrtlType, [&](uint64_t fieldID, auto, auto) {
212 markOverdefined(fieldRef.getSubField(fieldID));
213 });
214 }
215
216 /// Mark the given value as overdefined. This means that we cannot refine a
217 /// specific constant for this value.
218 void markOverdefined(FieldRef value) {
219 auto &entry = latticeValues[value];
220 if (!entry.isOverdefined()) {
221 LLVM_DEBUG({
222 logger.getOStream()
223 << "Setting overdefined : (" << getFieldName(value).first << ")\n";
224 });
225 entry.markOverdefined();
226 changedLatticeValueWorklist.push_back(value);
227 }
228 }
229
230 /// Merge information from the 'from' lattice value into value. If it
231 /// changes, then users of the value are added to the worklist for
232 /// revisitation.
233 void mergeLatticeValue(FieldRef value, LatticeValue &valueEntry,
234 LatticeValue source) {
235 if (valueEntry.mergeIn(source)) {
236 LLVM_DEBUG({
237 logger.getOStream()
238 << "Changed to " << valueEntry << " : (" << value << ")\n";
239 });
240 changedLatticeValueWorklist.push_back(value);
241 }
242 }
243
244 void mergeLatticeValue(FieldRef value, LatticeValue source) {
245 // Don't even do a map lookup if from has no info in it.
246 if (source.isUnknown())
247 return;
248 mergeLatticeValue(value, latticeValues[value], source);
249 }
250
251 void mergeLatticeValue(FieldRef result, FieldRef from) {
252 // If 'from' hasn't been computed yet, then it is unknown, don't do
253 // anything.
254 auto it = latticeValues.find(from);
255 if (it == latticeValues.end())
256 return;
257 mergeLatticeValue(result, it->second);
258 }
259
260 void mergeLatticeValue(Value result, Value from) {
261 FieldRef fieldRefFrom = getOrCacheFieldRefFromValue(from);
262 FieldRef fieldRefResult = getOrCacheFieldRefFromValue(result);
263 if (!type_isa<FIRRTLType>(result.getType()))
264 return mergeLatticeValue(fieldRefResult, fieldRefFrom);
265 // Special-handle PropertyType's, walkGroundType's doesn't support.
266 if (type_isa<PropertyType>(result.getType()))
267 return mergeLatticeValue(fieldRefResult, fieldRefFrom);
268 walkGroundTypes(type_cast<FIRRTLType>(result.getType()),
269 [&](uint64_t fieldID, auto, auto) {
270 mergeLatticeValue(fieldRefResult.getSubField(fieldID),
271 fieldRefFrom.getSubField(fieldID));
272 });
273 }
274
275 /// setLatticeValue - This is used when a new LatticeValue is computed for
276 /// the result of the specified value that replaces any previous knowledge,
277 /// e.g. because a fold() function on an op returned a new thing. This should
278 /// not be used on operations that have multiple contributors to it, e.g.
279 /// wires or ports.
280 void setLatticeValue(FieldRef value, LatticeValue source) {
281 // Don't even do a map lookup if from has no info in it.
282 if (source.isUnknown())
283 return;
284
285 // If we've changed this value then revisit all the users.
286 auto &valueEntry = latticeValues[value];
287 if (valueEntry != source) {
288 changedLatticeValueWorklist.push_back(value);
289 valueEntry = source;
290 }
291 }
292
293 // This function returns a field ref of the given value. This function caches
294 // the result to avoid extra IR traversal if the value is an aggregate
295 // element.
296 FieldRef getOrCacheFieldRefFromValue(Value value) {
297 if (!value.getDefiningOp() || !isAggregate(value.getDefiningOp()))
298 return FieldRef(value, 0);
299 auto &fieldRef = valueToFieldRef[value];
300 if (fieldRef)
301 return fieldRef;
302 return fieldRef = getFieldRefFromValue(value);
303 }
304
305 /// Return the lattice value for the specified SSA value, extended to the
306 /// width of the specified destType. If allowTruncation is true, then this
307 /// allows truncating the lattice value to the specified type.
308 LatticeValue getExtendedLatticeValue(FieldRef value, FIRRTLType destType,
309 bool allowTruncation = false);
310
311 /// Mark the given block as executable.
312 void markBlockExecutable(Block *block);
313 void markWireOp(WireOp wireOrReg);
314 void markMemOp(MemOp mem);
315 void markDPICallIntrinsicOp(DPICallIntrinsicOp dpi);
316
317 void markInvalidValueOp(InvalidValueOp invalid);
318 void markAggregateConstantOp(AggregateConstantOp constant);
319 void markInstanceOp(InstanceOp instance);
320 void markObjectOp(ObjectOp object);
321 template <typename OpTy>
322 void markConstantValueOp(OpTy op);
323
324 void visitConnectLike(FConnectLike connect, FieldRef changedFieldRef);
325 void visitRefSend(RefSendOp send, FieldRef changedFieldRef);
326 void visitRefResolve(RefResolveOp resolve, FieldRef changedFieldRef);
327 void mergeOnlyChangedLatticeValue(Value dest, Value src,
328 FieldRef changedFieldRef);
329 void visitNode(NodeOp node, FieldRef changedFieldRef);
330 void visitOperation(Operation *op, FieldRef changedFieldRef);
331
332private:
333 /// This is the current instance graph for the Circuit.
334 InstanceGraph *instanceGraph = nullptr;
335
336 /// This keeps track of the current state of each tracked value.
337 DenseMap<FieldRef, LatticeValue> latticeValues;
338
339 /// The set of blocks that are known to execute, or are intrinsically live.
340 SmallPtrSet<Block *, 16> executableBlocks;
341
342 /// A worklist of values whose LatticeValue recently changed, indicating the
343 /// users need to be reprocessed.
344 SmallVector<FieldRef, 64> changedLatticeValueWorklist;
345
346 // A map to give operations to be reprocessed.
347 DenseMap<FieldRef, llvm::TinyPtrVector<Operation *>> fieldRefToUsers;
348
349 // A map to cache results of getFieldRefFromValue since it's costly traverse
350 // the IR.
351 llvm::DenseMap<Value, FieldRef> valueToFieldRef;
352
353 /// This keeps track of users the instance results that correspond to output
354 /// ports.
355 DenseMap<BlockArgument, llvm::TinyPtrVector<Value>>
356 resultPortToInstanceResultMapping;
357
358#ifndef NDEBUG
359 /// A logger used to emit information during the application process.
360 llvm::ScopedPrinter logger{llvm::dbgs()};
361#endif
362};
363} // end anonymous namespace
364
365// TODO: handle annotations: [[OptimizableExtModuleAnnotation]]
366void IMConstPropPass::runOnOperation() {
367 auto circuit = getOperation();
368 LLVM_DEBUG(
369 { logger.startLine() << "IMConstProp : " << circuit.getName() << "\n"; });
370
371 instanceGraph = &getAnalysis<InstanceGraph>();
372
373 // Mark input ports as overdefined where appropriate.
374 for (auto &op : circuit.getOps()) {
375 // Inputs of public modules are overdefined.
376 if (auto module = dyn_cast<FModuleOp>(op)) {
377 if (module.isPublic()) {
378 markBlockExecutable(module.getBodyBlock());
379 for (auto port : module.getBodyBlock()->getArguments())
380 markOverdefined(port);
381 }
382 continue;
383 }
384
385 // Otherwise we check whether the top-level operation contains any
386 // references to modules. Symbol uses in NLAs are ignored.
387 if (isa<hw::HierPathOp>(op))
388 continue;
389
390 // Inputs of modules referenced by unknown operations are overdefined, since
391 // we don't know how those operations affect the input port values. This
392 // handles things like `firrtl.formal`, which may may assign symbolic values
393 // to input ports of a private module.
394 auto symbolUses = SymbolTable::getSymbolUses(&op);
395 if (!symbolUses)
396 continue;
397 for (const auto &use : *symbolUses) {
398 if (auto symRef = dyn_cast<FlatSymbolRefAttr>(use.getSymbolRef())) {
399 if (auto *igNode = instanceGraph->lookupOrNull(symRef.getAttr())) {
400 if (auto module = dyn_cast<FModuleOp>(*igNode->getModule())) {
401 LLVM_DEBUG(llvm::dbgs()
402 << "Unknown use of " << module.getModuleNameAttr()
403 << " in " << op.getName()
404 << ", marking inputs as overdefined\n");
405 markBlockExecutable(module.getBodyBlock());
406 for (auto port : module.getBodyBlock()->getArguments())
407 markOverdefined(port);
408 }
409 }
410 }
411 }
412 }
413
414 // If a value changed lattice state then reprocess any of its users.
415 while (!changedLatticeValueWorklist.empty()) {
416 FieldRef changedFieldRef = changedLatticeValueWorklist.pop_back_val();
417 for (Operation *user : fieldRefToUsers[changedFieldRef]) {
418 if (isBlockExecutable(user->getBlock()))
419 visitOperation(user, changedFieldRef);
420 }
421 }
422
423 // Rewrite any constants in the modules.
424 mlir::parallelForEach(circuit.getContext(),
425 circuit.getBodyBlock()->getOps<FModuleOp>(),
426 [&](auto op) { rewriteModuleBody(op); });
427
428 // Clean up our state for next time.
429 instanceGraph = nullptr;
430 latticeValues.clear();
431 executableBlocks.clear();
432 assert(changedLatticeValueWorklist.empty());
433 fieldRefToUsers.clear();
434 valueToFieldRef.clear();
435 resultPortToInstanceResultMapping.clear();
436}
437
438/// Return the lattice value for the specified SSA value, extended to the width
439/// of the specified destType. If allowTruncation is true, then this allows
440/// truncating the lattice value to the specified type.
441LatticeValue IMConstPropPass::getExtendedLatticeValue(FieldRef value,
442 FIRRTLType destType,
443 bool allowTruncation) {
444 // If 'value' hasn't been computed yet, then it is unknown.
445 auto it = latticeValues.find(value);
446 if (it == latticeValues.end())
447 return LatticeValue();
448
449 auto result = it->second;
450 // Unknown/overdefined stay whatever they are.
451 if (result.isUnknown() || result.isOverdefined())
452 return result;
453
454 // No extOrTrunc for property types. Return what we have.
455 if (isa<PropertyType>(destType))
456 return result;
457
458 auto constant = result.getConstant();
459
460 // If not property, only support integers.
461 auto intAttr = dyn_cast<IntegerAttr>(constant);
462 assert(intAttr && "unsupported lattice attribute kind");
463 if (!intAttr)
464 return result;
465
466 // No extOrTrunc necessary for bools.
467 if (auto boolAttr = dyn_cast<BoolAttr>(intAttr))
468 return result;
469
470 // Non-base (or non-ref) types are overdefined.
471 auto baseType = getBaseType(destType);
472 if (!baseType)
473 return LatticeValue::getOverdefined();
474
475 // If destType is wider than the source constant type, extend it.
476 auto resultConstant = intAttr.getAPSInt();
477 auto destWidth = baseType.getBitWidthOrSentinel();
478 if (destWidth == -1) // We don't support unknown width FIRRTL.
479 return LatticeValue::getOverdefined();
480 if (resultConstant.getBitWidth() == (unsigned)destWidth)
481 return result; // Already the right width, we're done.
482
483 // Otherwise, extend the constant using the signedness of the source.
484 resultConstant = extOrTruncZeroWidth(resultConstant, destWidth);
485 return LatticeValue(IntegerAttr::get(destType.getContext(), resultConstant));
486}
487
488// NOLINTBEGIN(misc-no-recursion)
489/// Mark a block executable if it isn't already. This does an initial scan of
490/// the block, processing nullary operations like wires, instances, and
491/// constants that only get processed once.
492void IMConstPropPass::markBlockExecutable(Block *block) {
493 if (!executableBlocks.insert(block).second)
494 return; // Already executable.
495
496 // Mark block arguments, which are module ports, with don't touch as
497 // overdefined.
498 for (auto ba : block->getArguments())
499 if (hasDontTouch(ba))
500 markOverdefined(ba);
501
502 for (auto &op : *block) {
503 // Handle each of the special operations in the firrtl dialect.
504 TypeSwitch<Operation *>(&op)
505 .Case<RegOp, RegResetOp>(
506 [&](auto reg) { markOverdefined(op.getResult(0)); })
507 .Case<WireOp>([&](auto wire) { markWireOp(wire); })
508 .Case<ConstantOp, SpecialConstantOp, StringConstantOp,
509 FIntegerConstantOp, BoolConstantOp>(
510 [&](auto constOp) { markConstantValueOp(constOp); })
511 .Case<AggregateConstantOp>(
512 [&](auto aggConstOp) { markAggregateConstantOp(aggConstOp); })
513 .Case<InvalidValueOp>(
514 [&](auto invalid) { markInvalidValueOp(invalid); })
515 .Case<InstanceOp>([&](auto instance) { markInstanceOp(instance); })
516 .Case<ObjectOp>([&](auto obj) { markObjectOp(obj); })
517 .Case<MemOp>([&](auto mem) { markMemOp(mem); })
518 .Case<LayerBlockOp>(
519 [&](auto layer) { markBlockExecutable(layer.getBody(0)); })
520 .Case<DPICallIntrinsicOp>(
521 [&](auto dpi) { markDPICallIntrinsicOp(dpi); })
522 .Default([&](auto _) {
523 if (isa<mlir::UnrealizedConversionCastOp, VerbatimExprOp,
524 VerbatimWireOp, SubaccessOp>(op) ||
525 op.getNumOperands() == 0) {
526 // Mark operations whose results cannot be tracked as overdefined.
527 // Mark unhandled operations with no operand as well since otherwise
528 // they will remain unknown states until the end.
529 for (auto result : op.getResults())
530 markOverdefined(result);
531 } else if (
532 // Operations that are handled when propagating values, or chasing
533 // indexing.
534 !isAggregate(&op) && !isNodeLike(&op) && op.getNumResults() > 0) {
535 // If an unknown operation has an aggregate operand, mark results as
536 // overdefined since we cannot track the dataflow. Similarly if the
537 // operations create aggregate values, we mark them overdefined.
538
539 // TODO: We should handle aggregate operations such as
540 // vector_create, bundle_create or vector operations.
541
542 bool hasAggregateOperand =
543 llvm::any_of(op.getOperandTypes(), [](Type type) {
544 return type_isa<FVectorType, BundleType>(type);
545 });
546
547 for (auto result : op.getResults())
548 if (hasAggregateOperand ||
549 type_isa<FVectorType, BundleType>(result.getType()))
550 markOverdefined(result);
551 }
552 });
553
554 // This tracks a dependency from field refs to operations which need
555 // to be added to worklist when lattice values change.
556 if (!isAggregate(&op)) {
557 for (auto operand : op.getOperands()) {
558 auto fieldRef = getOrCacheFieldRefFromValue(operand);
559 auto firrtlType = type_dyn_cast<FIRRTLType>(operand.getType());
560 if (!firrtlType)
561 continue;
562 // Special-handle PropertyType's, walkGroundTypes doesn't support.
563 if (type_isa<PropertyType>(firrtlType)) {
564 fieldRefToUsers[fieldRef].push_back(&op);
565 continue;
566 }
567 walkGroundTypes(firrtlType, [&](uint64_t fieldID, auto type, auto) {
568 fieldRefToUsers[fieldRef.getSubField(fieldID)].push_back(&op);
569 });
570 }
571 }
572 }
573}
574// NOLINTEND(misc-no-recursion)
575
576void IMConstPropPass::markWireOp(WireOp wire) {
577 auto type = type_dyn_cast<FIRRTLType>(wire.getResult().getType());
578 if (!type || hasDontTouch(wire.getResult()) || wire.isForceable()) {
579 for (auto result : wire.getResults())
580 markOverdefined(result);
581 return;
582 }
583
584 // Otherwise, this starts out as unknown and is upgraded by connects.
585}
586
587void IMConstPropPass::markMemOp(MemOp mem) {
588 for (auto result : mem.getResults())
589 markOverdefined(result);
590}
591
592void IMConstPropPass::markDPICallIntrinsicOp(DPICallIntrinsicOp dpi) {
593 if (auto result = dpi.getResult())
594 markOverdefined(result);
595}
596
597template <typename OpTy>
598void IMConstPropPass::markConstantValueOp(OpTy op) {
599 mergeLatticeValue(getOrCacheFieldRefFromValue(op),
600 LatticeValue(op.getValueAttr()));
601}
602
603void IMConstPropPass::markAggregateConstantOp(AggregateConstantOp constant) {
604 walkGroundTypes(constant.getType(), [&](uint64_t fieldID, auto, auto) {
605 mergeLatticeValue(FieldRef(constant, fieldID),
606 LatticeValue(cast<IntegerAttr>(
607 constant.getAttributeFromFieldID(fieldID))));
608 });
609}
610
611void IMConstPropPass::markInvalidValueOp(InvalidValueOp invalid) {
612 markOverdefined(invalid.getResult());
613}
614
615/// Instances have no operands, so they are visited exactly once when their
616/// enclosing block is marked live. This sets up the def-use edges for ports.
617void IMConstPropPass::markInstanceOp(InstanceOp instance) {
618 // Get the module being reference or a null pointer if this is an extmodule.
619 Operation *op = instance.getReferencedModule(*instanceGraph);
620
621 // If this is an extmodule, just remember that any results and inouts are
622 // overdefined.
623 if (!isa<FModuleOp>(op)) {
624 auto module = dyn_cast<FModuleLike>(op);
625 for (size_t resultNo = 0, e = instance.getNumResults(); resultNo != e;
626 ++resultNo) {
627 auto portVal = instance.getResult(resultNo);
628 // If this is an input to the extmodule, we can ignore it.
629 if (module.getPortDirection(resultNo) == Direction::In)
630 continue;
631
632 // Otherwise this is a result from it or an inout, mark it as overdefined.
633 markOverdefined(portVal);
634 }
635 return;
636 }
637
638 // Otherwise this is a defined module.
639 auto fModule = cast<FModuleOp>(op);
640 markBlockExecutable(fModule.getBodyBlock());
641
642 // Ok, it is a normal internal module reference. Populate
643 // resultPortToInstanceResultMapping, and forward any already-computed values.
644 for (size_t resultNo = 0, e = instance.getNumResults(); resultNo != e;
645 ++resultNo) {
646 auto instancePortVal = instance.getResult(resultNo);
647 // If this is an input to the instance, it will
648 // get handled when any connects to it are processed.
649 if (fModule.getPortDirection(resultNo) == Direction::In)
650 continue;
651
652 // Otherwise we have a result from the instance. We need to forward results
653 // from the body to this instance result's SSA value, so remember it.
654 BlockArgument modulePortVal = fModule.getArgument(resultNo);
655
656 resultPortToInstanceResultMapping[modulePortVal].push_back(instancePortVal);
657
658 // If there is already a value known for modulePortVal make sure to forward
659 // it here.
660 mergeLatticeValue(instancePortVal, modulePortVal);
661 }
662}
663
664void IMConstPropPass::markObjectOp(ObjectOp obj) {
665 // Mark overdefined for now, not supported.
666 markOverdefined(obj);
667}
668
669static std::optional<uint64_t>
670getFieldIDOffset(FieldRef changedFieldRef, Type connectionType,
671 FieldRef connectedValueFieldRef) {
672 assert(!type_isa<RefType>(connectionType));
673 if (changedFieldRef.getValue() != connectedValueFieldRef.getValue())
674 return {};
675 if (changedFieldRef.getFieldID() >= connectedValueFieldRef.getFieldID() &&
676 changedFieldRef.getFieldID() <=
677 hw::FieldIdImpl::getMaxFieldID(connectionType) +
678 connectedValueFieldRef.getFieldID())
679 return changedFieldRef.getFieldID() - connectedValueFieldRef.getFieldID();
680 return {};
681}
682
683void IMConstPropPass::mergeOnlyChangedLatticeValue(Value dest, Value src,
684 FieldRef changedFieldRef) {
685
686 // Operate on inner type for refs.
687 auto destType = dest.getType();
688 if (auto refType = type_dyn_cast<RefType>(destType))
689 destType = refType.getType();
690
691 if (!isa<FIRRTLType>(destType)) {
692 // If the dest is not FIRRTL type, conservatively mark
693 // all of them overdefined.
694 markOverdefined(src);
695 return markOverdefined(dest);
696 }
697
698 auto fieldRefSrc = getOrCacheFieldRefFromValue(src);
699 auto fieldRefDest = getOrCacheFieldRefFromValue(dest);
700
701 // If a changed field ref is included the source value, find an offset in the
702 // connection.
703 if (auto srcOffset = getFieldIDOffset(changedFieldRef, destType, fieldRefSrc))
704 mergeLatticeValue(fieldRefDest.getSubField(*srcOffset),
705 fieldRefSrc.getSubField(*srcOffset));
706
707 // If a changed field ref is included the dest value, find an offset in the
708 // connection.
709 if (auto destOffset =
710 getFieldIDOffset(changedFieldRef, destType, fieldRefDest))
711 mergeLatticeValue(fieldRefDest.getSubField(*destOffset),
712 fieldRefSrc.getSubField(*destOffset));
713}
714
715void IMConstPropPass::visitConnectLike(FConnectLike connect,
716 FieldRef changedFieldRef) {
717 // Operate on inner type for refs.
718 auto destType = connect.getDest().getType();
719 if (auto refType = type_dyn_cast<RefType>(destType))
720 destType = refType.getType();
721
722 // Mark foreign types as overdefined.
723 if (!isa<FIRRTLType>(destType)) {
724 markOverdefined(connect.getSrc());
725 return markOverdefined(connect.getDest());
726 }
727
728 auto fieldRefSrc = getOrCacheFieldRefFromValue(connect.getSrc());
729 auto fieldRefDest = getOrCacheFieldRefFromValue(connect.getDest());
730 if (auto subaccess = fieldRefDest.getValue().getDefiningOp<SubaccessOp>()) {
731 // If the destination is subaccess, we give up to precisely track
732 // lattice values and mark entire aggregate as overdefined. This code
733 // should be dead unless we stop lowering of subaccess in LowerTypes.
734 Value parent = subaccess.getInput();
735 while (parent.getDefiningOp() &&
736 parent.getDefiningOp()->getNumOperands() > 0)
737 parent = parent.getDefiningOp()->getOperand(0);
738 return markOverdefined(parent);
739 }
740
741 auto propagateElementLattice = [&](uint64_t fieldID, FIRRTLType destType) {
742 auto fieldRefDestConnected = fieldRefDest.getSubField(fieldID);
743 assert(!firrtl::type_isa<FIRRTLBaseType>(destType) ||
744 firrtl::type_cast<FIRRTLBaseType>(destType).isGround());
745
746 // Handle implicit extensions.
747 auto srcValue =
748 getExtendedLatticeValue(fieldRefSrc.getSubField(fieldID), destType);
749 if (srcValue.isUnknown())
750 return;
751
752 // Driving result ports propagates the value to each instance using the
753 // module.
754 if (auto blockArg = dyn_cast<BlockArgument>(fieldRefDest.getValue())) {
755 for (auto userOfResultPort : resultPortToInstanceResultMapping[blockArg])
756 mergeLatticeValue(
757 FieldRef(userOfResultPort, fieldRefDestConnected.getFieldID()),
758 srcValue);
759 // Output ports are wire-like and may have users.
760 return mergeLatticeValue(fieldRefDestConnected, srcValue);
761 }
762
763 auto dest = cast<mlir::OpResult>(fieldRefDest.getValue());
764
765 // For wires and registers, we drive the value of the wire itself, which
766 // automatically propagates to users.
767 if (isWireOrReg(dest.getOwner()))
768 return mergeLatticeValue(fieldRefDestConnected, srcValue);
769
770 // Driving an instance argument port drives the corresponding argument
771 // of the referenced module.
772 if (auto instance = dest.getDefiningOp<InstanceOp>()) {
773 // Update the dest, when its an instance op.
774 mergeLatticeValue(fieldRefDestConnected, srcValue);
775 auto mod = instance.getReferencedModule<FModuleOp>(*instanceGraph);
776 if (!mod)
777 return;
778
779 BlockArgument modulePortVal = mod.getArgument(dest.getResultNumber());
780
781 return mergeLatticeValue(
782 FieldRef(modulePortVal, fieldRefDestConnected.getFieldID()),
783 srcValue);
784 }
785
786 // Driving a memory result is ignored because these are always treated
787 // as overdefined.
788 if (dest.getDefiningOp<MemOp>())
789 return;
790
791 // For now, don't support const prop into object fields.
792 if (isa_and_nonnull<ObjectSubfieldOp>(dest.getDefiningOp()))
793 return;
794
795 connect.emitError("connectlike operation unhandled by IMConstProp")
796 .attachNote(connect.getDest().getLoc())
797 << "connect destination is here";
798 };
799
800 if (auto srcOffset = getFieldIDOffset(changedFieldRef, destType, fieldRefSrc))
801 propagateElementLattice(
802 *srcOffset,
803 firrtl::type_cast<FIRRTLType>(
804 hw::FieldIdImpl::getFinalTypeByFieldID(destType, *srcOffset)));
805
806 if (auto relativeDest =
807 getFieldIDOffset(changedFieldRef, destType, fieldRefDest))
808 propagateElementLattice(
809 *relativeDest,
810 firrtl::type_cast<FIRRTLType>(
811 hw::FieldIdImpl::getFinalTypeByFieldID(destType, *relativeDest)));
812}
813
814void IMConstPropPass::visitRefSend(RefSendOp send, FieldRef changedFieldRef) {
815 // Send connects the base value (source) to the result (dest).
816 return mergeOnlyChangedLatticeValue(send.getResult(), send.getBase(),
817 changedFieldRef);
818}
819
820void IMConstPropPass::visitRefResolve(RefResolveOp resolve,
821 FieldRef changedFieldRef) {
822 // Resolve connects the ref value (source) to result (dest).
823 // If writes are ever supported, this will need to work differently!
824 return mergeOnlyChangedLatticeValue(resolve.getResult(), resolve.getRef(),
825 changedFieldRef);
826}
827
828void IMConstPropPass::visitNode(NodeOp node, FieldRef changedFieldRef) {
829 if (hasDontTouch(node.getResult()) || node.isForceable()) {
830 for (auto result : node.getResults())
831 markOverdefined(result);
832 return;
833 }
834
835 return mergeOnlyChangedLatticeValue(node.getResult(), node.getInput(),
836 changedFieldRef);
837}
838
839/// This method is invoked when an operand of the specified op changes its
840/// lattice value state and when the block containing the operation is first
841/// noticed as being alive.
842///
843/// This should update the lattice value state for any result values.
844///
845void IMConstPropPass::visitOperation(Operation *op, FieldRef changedField) {
846 // If this is a operation with special handling, handle it specially.
847 if (auto connectLikeOp = dyn_cast<FConnectLike>(op))
848 return visitConnectLike(connectLikeOp, changedField);
849 if (auto sendOp = dyn_cast<RefSendOp>(op))
850 return visitRefSend(sendOp, changedField);
851 if (auto resolveOp = dyn_cast<RefResolveOp>(op))
852 return visitRefResolve(resolveOp, changedField);
853 if (auto nodeOp = dyn_cast<NodeOp>(op))
854 return visitNode(nodeOp, changedField);
855
856 // The clock operand of regop changing doesn't change its result value. All
857 // other registers are over-defined. Aggregate operations also doesn't change
858 // its result value.
859 if (isa<RegOp, RegResetOp>(op) || isAggregate(op))
860 return;
861 // TODO: Handle 'when' operations.
862
863 // If all of the results of this operation are already overdefined (or if
864 // there are no results) then bail out early: we've converged.
865 auto isOverdefinedFn = [&](Value value) {
866 return isOverdefined(getOrCacheFieldRefFromValue(value));
867 };
868 if (llvm::all_of(op->getResults(), isOverdefinedFn))
869 return;
870
871 // To prevent regressions, mark values as overdefined when they are defined
872 // by operations with a large number of operands.
873 if (op->getNumOperands() > 128) {
874 for (auto value : op->getResults())
875 markOverdefined(value);
876 return;
877 }
878
879 // Collect all of the constant operands feeding into this operation. If any
880 // are not ready to be resolved, bail out and wait for them to resolve.
881 SmallVector<Attribute, 8> operandConstants;
882 operandConstants.reserve(op->getNumOperands());
883 bool hasUnknown = false;
884 for (Value operand : op->getOperands()) {
885
886 auto &operandLattice = latticeValues[getOrCacheFieldRefFromValue(operand)];
887
888 // If the operand is an unknown value, then we generally don't want to
889 // process it - we want to wait until the value is resolved to by the SCCP
890 // algorithm.
891 if (operandLattice.isUnknown())
892 hasUnknown = true;
893
894 // Otherwise, it must be constant, invalid, or overdefined. Translate them
895 // into attributes that the fold hook can look at.
896 if (operandLattice.isConstant())
897 operandConstants.push_back(operandLattice.getValue());
898 else
899 operandConstants.push_back({});
900 }
901
902 // Simulate the result of folding this operation to a constant. If folding
903 // fails mark the results as overdefined.
904 SmallVector<OpFoldResult, 8> foldResults;
905 foldResults.reserve(op->getNumResults());
906 if (failed(op->fold(operandConstants, foldResults))) {
907 LLVM_DEBUG({
908 logger.startLine() << "Folding Failed operation : '" << op->getName()
909 << "\n";
910 op->dump();
911 });
912 // If we had unknown arguments, hold off on overdefining
913 if (!hasUnknown)
914 for (auto value : op->getResults())
915 markOverdefined(value);
916 return;
917 }
918
919 LLVM_DEBUG({
920 logger.getOStream() << "\n";
921 logger.startLine() << "Folding operation : '" << op->getName() << "\n";
922 op->dump();
923 logger.getOStream() << "( ";
924 for (auto cst : operandConstants)
925 if (!cst)
926 logger.getOStream() << "{} ";
927 else
928 logger.getOStream() << cst << " ";
929 logger.unindent();
930 logger.getOStream() << ") -> { ";
931 logger.indent();
932 for (auto &r : foldResults) {
933 logger.getOStream() << r << " ";
934 }
935 logger.unindent();
936 logger.getOStream() << "}\n";
937 });
938
939 // If the folding was in-place, keep going. This is surprising, but since
940 // only folder that will do in-place updates is the commutative folder, we
941 // aren't going to stop. We don't update the results, since they didn't
942 // change, the op just got shuffled around.
943 if (foldResults.empty())
944 return visitOperation(op, changedField);
945
946 // Merge the fold results into the lattice for this operation.
947 assert(foldResults.size() == op->getNumResults() && "invalid result size");
948 for (unsigned i = 0, e = foldResults.size(); i != e; ++i) {
949 // Merge in the result of the fold, either a constant or a value.
950 LatticeValue resultLattice;
951 OpFoldResult foldResult = foldResults[i];
952 if (Attribute foldAttr = dyn_cast<Attribute>(foldResult)) {
953 if (auto intAttr = dyn_cast<IntegerAttr>(foldAttr))
954 resultLattice = LatticeValue(intAttr);
955 else if (auto strAttr = dyn_cast<StringAttr>(foldAttr))
956 resultLattice = LatticeValue(strAttr);
957 else // Treat unsupported constants as overdefined.
958 resultLattice = LatticeValue::getOverdefined();
959 } else { // Folding to an operand results in its value.
960 resultLattice =
961 latticeValues[getOrCacheFieldRefFromValue(cast<Value>(foldResult))];
962 }
963
964 mergeLatticeValue(getOrCacheFieldRefFromValue(op->getResult(i)),
965 resultLattice);
966 }
967}
968
969void IMConstPropPass::rewriteModuleBody(FModuleOp module) {
970 auto *body = module.getBodyBlock();
971 // If a module is unreachable, just ignore it.
972 if (!executableBlocks.count(body))
973 return;
974
975 auto builder = OpBuilder::atBlockBegin(body);
976
977 // Separate the constants we insert from the instructions we are folding and
978 // processing. Leave these as-is until we're done.
979 auto cursor = builder.create<firrtl::ConstantOp>(module.getLoc(), APSInt(1));
980 builder.setInsertionPoint(cursor);
981
982 // Unique constants per <Const,Type> pair, inserted at entry
983 DenseMap<std::pair<Attribute, Type>, Operation *> constPool;
984
985 std::function<Value(Attribute, Type, Location)> getConst =
986 [&](Attribute constantValue, Type type, Location loc) -> Value {
987 auto constIt = constPool.find({constantValue, type});
988 if (constIt != constPool.end()) {
989 auto *cst = constIt->second;
990 // Add location to the constant
991 cst->setLoc(builder.getFusedLoc({cst->getLoc(), loc}));
992 return cst->getResult(0);
993 }
994 OpBuilder::InsertionGuard x(builder);
995 builder.setInsertionPoint(cursor);
996
997 // Materialize reftype "constants" by materializing the constant
998 // and probing it.
999 Operation *cst;
1000 if (auto refType = type_dyn_cast<RefType>(type)) {
1001 assert(!type_cast<RefType>(type).getForceable() &&
1002 "Attempting to materialize rwprobe of constant, shouldn't happen");
1003 auto inner = getConst(constantValue, refType.getType(), loc);
1004 assert(inner);
1005 cst = builder.create<RefSendOp>(loc, inner);
1006 } else
1007 cst = module->getDialect()->materializeConstant(builder, constantValue,
1008 type, loc);
1009 assert(cst && "all FIRRTL constants can be materialized");
1010 constPool.insert({{constantValue, type}, cst});
1011 return cst->getResult(0);
1012 };
1013
1014 // If the lattice value for the specified value is a constant update it and
1015 // return true. Otherwise return false.
1016 auto replaceValueIfPossible = [&](Value value) -> bool {
1017 // Lambda to replace all uses of this value a replacement, unless this is
1018 // the destination of a connect. We leave connects alone to avoid upsetting
1019 // flow, i.e., to avoid trying to connect to a constant.
1020 auto replaceIfNotConnect = [&value](Value replacement) {
1021 value.replaceUsesWithIf(replacement, [](OpOperand &operand) {
1022 return !isa<FConnectLike>(operand.getOwner()) ||
1023 operand.getOperandNumber() != 0;
1024 });
1025 };
1026
1027 // TODO: Replace entire aggregate.
1028 auto it = latticeValues.find(getFieldRefFromValue(value));
1029 if (it == latticeValues.end() || it->second.isOverdefined() ||
1030 it->second.isUnknown())
1031 return false;
1032
1033 // Cannot materialize constants for certain types.
1034 // TODO: Let materializeConstant tell us what it supports instead of this.
1035 // Presently it asserts on unsupported combinations, so check this here.
1036 if (!type_isa<FIRRTLBaseType, RefType, FIntegerType, StringType, BoolType>(
1037 value.getType()))
1038 return false;
1039
1040 auto cstValue =
1041 getConst(it->second.getValue(), value.getType(), value.getLoc());
1042
1043 replaceIfNotConnect(cstValue);
1044 return true;
1045 };
1046
1047 // Constant propagate any ports that are always constant.
1048 for (auto &port : body->getArguments())
1049 replaceValueIfPossible(port);
1050
1051 // Walk the IR bottom-up when folding. We often fold entire chains of
1052 // operations into constants, which make the intermediate nodes dead. Going
1053 // bottom up eliminates the users of the intermediate ops, allowing us to
1054 // aggressively delete them.
1055 //
1056 // TODO: Handle WhenOps correctly.
1057 bool aboveCursor = false;
1058 module.walk<mlir::WalkOrder::PostOrder, mlir::ReverseIterator>(
1059 [&](Operation *op) {
1060 auto dropIfDead = [&](Operation *op, const Twine &debugPrefix) {
1061 if (op->use_empty() &&
1062 (wouldOpBeTriviallyDead(op) || isDeletableWireOrRegOrNode(op))) {
1063 LLVM_DEBUG(
1064 { logger.getOStream() << debugPrefix << " : " << op << "\n"; });
1065 ++numErasedOp;
1066 op->erase();
1067 return true;
1068 }
1069 return false;
1070 };
1071
1072 if (aboveCursor) {
1073 // Drop dead constants we materialized.
1074 dropIfDead(op, "Trivially dead materialized constant");
1075 return WalkResult::advance();
1076 }
1077 // Stop once hit the generated constants.
1078 if (op == cursor) {
1079 cursor.erase();
1080 aboveCursor = true;
1081 return WalkResult::advance();
1082 }
1083
1084 // Connects to values that we found to be constant can be dropped.
1085 if (auto connect = dyn_cast<FConnectLike>(op)) {
1086 if (auto *destOp = connect.getDest().getDefiningOp()) {
1087 auto fieldRef = getOrCacheFieldRefFromValue(connect.getDest());
1088 // Don't remove a field-level connection even if the src value is
1089 // constant. If other elements of the aggregate value are not
1090 // constant, the aggregate value cannot be replaced. We can forward
1091 // the constant to its users, so IMDCE (or SV/HW canonicalizer)
1092 // should remove the aggregate if entire aggregate is dead.
1093 auto type = type_dyn_cast<FIRRTLType>(connect.getDest().getType());
1094 if (!type)
1095 return WalkResult::advance();
1096 auto baseType = type_dyn_cast<FIRRTLBaseType>(type);
1097 if (baseType && !baseType.isGround())
1098 return WalkResult::advance();
1099 if (isDeletableWireOrRegOrNode(destOp) &&
1100 !isOverdefined(fieldRef)) {
1101 connect.erase();
1102 ++numErasedOp;
1103 }
1104 }
1105 return WalkResult::advance();
1106 }
1107
1108 // We only fold single-result ops and instances in practice, because
1109 // they are the expressions.
1110 if (op->getNumResults() != 1 && !isa<InstanceOp>(op))
1111 return WalkResult::advance();
1112
1113 // If this operation is already dead, then go ahead and remove it.
1114 if (dropIfDead(op, "Trivially dead"))
1115 return WalkResult::advance();
1116
1117 // Don't "fold" constants (into equivalent), also because they
1118 // may have name hints we'd like to preserve.
1119 if (op->hasTrait<mlir::OpTrait::ConstantLike>())
1120 return WalkResult::advance();
1121
1122 // If the op had any constants folded, replace them.
1123 builder.setInsertionPoint(op);
1124 bool foldedAny = false;
1125 for (auto result : op->getResults())
1126 foldedAny |= replaceValueIfPossible(result);
1127
1128 if (foldedAny)
1129 ++numFoldedOp;
1130
1131 // If the operation folded to a constant then we can probably nuke it.
1132 if (foldedAny && dropIfDead(op, "Made dead"))
1133 return WalkResult::advance();
1134
1135 return WalkResult::advance();
1136 });
1137}
1138
1139std::unique_ptr<mlir::Pass> circt::firrtl::createIMConstPropPass() {
1140 return std::make_unique<IMConstPropPass>();
1141}
assert(baseType &&"element must be base type")
static std::optional< APSInt > getConstant(Attribute operand)
Determine the value of a constant operand for the sake of constant folding.
static bool isNodeLike(Operation *op)
static bool isWireOrReg(Operation *op)
Return true if this is a wire or register.
static bool isAggregate(Operation *op)
Return true if this is an aggregate indexer.
static std::optional< uint64_t > getFieldIDOffset(FieldRef changedFieldRef, Type connectionType, FieldRef connectedValueFieldRef)
static bool isDeletableWireOrRegOrNode(Operation *op)
Return true if this is a wire or register we're allowed to delete.
static unsigned getFieldID(BundleType type, unsigned index)
static Block * getBodyBlock(FModuleLike mod)
This class represents a reference to a specific field or element of an aggregate value.
Definition FieldRef.h:28
FieldRef getSubField(unsigned subFieldID) const
Get a reference to a subfield.
Definition FieldRef.h:62
unsigned getFieldID() const
Get the field ID of this FieldRef, which is a unique identifier mapped to a specific field in a bundl...
Definition FieldRef.h:59
Value getValue() const
Get the Value which created this location.
Definition FieldRef.h:37
Location getLoc() const
Get the location associated with the value of this field ref.
Definition FieldRef.h:67
This class provides a read-only projection over the MLIR attributes that represent a set of annotatio...
This graph tracks modules and where they are instantiated.
connect(destination, source)
Definition support.py:39
FIRRTLBaseType getBaseType(Type type)
If it is a base type, return it as is.
FieldRef getFieldRefFromValue(Value value, bool lookThroughCasts=false)
Get the FieldRef from a value.
void walkGroundTypes(FIRRTLType firrtlType, llvm::function_ref< void(uint64_t, FIRRTLBaseType, bool)> fn)
Walk leaf ground types in the firrtlType and apply the function fn.
bool isConstant(Operation *op)
Return true if the specified operation has a constant value.
std::unique_ptr< mlir::Pass > createIMConstPropPass()
bool hasDontTouch(Value value)
Check whether a block argument ("port") or the operation defining a value has a DontTouch annotation,...
llvm::raw_ostream & operator<<(llvm::raw_ostream &os, const InstanceInfo::LatticeValue &value)
bool hasDroppableName(Operation *op)
Return true if the name is droppable.
std::pair< std::string, bool > getFieldName(const FieldRef &fieldRef, bool nameSafe=false)
Get a string identifier representing the FieldRef.
bool type_isa(Type type)
::mlir::Type getFinalTypeByFieldID(Type type, uint64_t fieldID)
static bool operator==(const ModulePort &a, const ModulePort &b)
Definition HWTypes.h:35
The InstanceGraph op interface, see InstanceGraphInterface.td for more details.
APSInt extOrTruncZeroWidth(APSInt value, unsigned width)
A safe version of APSInt::extOrTrunc that will NOT assert on zero-width signed APSInts.
Definition APInt.cpp:22
bool operator!=(uint64_t a, const FVInt &b)
Definition FVInt.h:651
reg(value, clock, reset=None, reset_value=None, name=None, sym_name=None)
Definition seq.py:21