-
Notifications
You must be signed in to change notification settings - Fork 10.8k
/
KnowledgeRetention.h
150 lines (129 loc) · 5.96 KB
/
KnowledgeRetention.h
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
//===- KnowledgeRetention.h - utilities to preserve informations *- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file contain tools to preserve informations. They should be used before
// performing a transformation that may move and delete instructions as those
// transformation may destroy or worsen information that can be derived from the
// IR.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_TRANSFORMS_UTILS_ASSUMEBUILDER_H
#define LLVM_TRANSFORMS_UTILS_ASSUMEBUILDER_H
#include "llvm/IR/Attributes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/PassManager.h"
#include "llvm/ADT/DenseMap.h"
namespace llvm {
class IntrinsicInst;
/// Build a call to llvm.assume to preserve informations that can be derived
/// from the given instruction.
/// If no information derived from \p I, this call returns null.
/// The returned instruction is not inserted anywhere.
IntrinsicInst *buildAssumeFromInst(Instruction *I);
/// Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert
/// if before I. This is usually what need to be done to salvage the knowledge
/// contained in the instruction I.
void salvageKnowledge(Instruction *I);
/// It is possible to have multiple Value for the argument of an attribute in
/// the same llvm.assume on the same llvm::Value. This is rare but need to be
/// dealt with.
enum class AssumeQuery {
Highest, ///< Take the highest value available.
Lowest, ///< Take the lowest value available.
};
/// Query the operand bundle of an llvm.assume to find a single attribute of
/// the specified kind applied on a specified Value.
///
/// This has a non-constant complexity. It should only be used when a single
/// attribute is going to be queried.
///
/// Return true iff the queried attribute was found.
/// If ArgVal is set. the argument will be stored to ArgVal.
bool hasAttributeInAssume(CallInst &AssumeCI, Value *IsOn, StringRef AttrName,
uint64_t *ArgVal = nullptr,
AssumeQuery AQR = AssumeQuery::Highest);
inline bool hasAttributeInAssume(CallInst &AssumeCI, Value *IsOn,
Attribute::AttrKind Kind,
uint64_t *ArgVal = nullptr,
AssumeQuery AQR = AssumeQuery::Highest) {
return hasAttributeInAssume(
AssumeCI, IsOn, Attribute::getNameFromAttrKind(Kind), ArgVal, AQR);
}
template<> struct DenseMapInfo<Attribute::AttrKind> {
static Attribute::AttrKind getEmptyKey() {
return Attribute::EmptyKey;
}
static Attribute::AttrKind getTombstoneKey() {
return Attribute::TombstoneKey;
}
static unsigned getHashValue(Attribute::AttrKind AK) {
return hash_combine(AK);
}
static bool isEqual(Attribute::AttrKind LHS, Attribute::AttrKind RHS) {
return LHS == RHS;
}
};
/// The map Key contains the Value on for which the attribute is valid and
/// the Attribute that is valid for that value.
/// If the Attribute is not on any value, the Value is nullptr.
using RetainedKnowledgeKey = std::pair<Value *, Attribute::AttrKind>;
struct MinMax {
unsigned Min;
unsigned Max;
};
/// A mapping from intrinsics (=`llvm.assume` calls) to a value range
/// (=knowledge) that is encoded in them. How the value range is interpreted
/// depends on the RetainedKnowledgeKey that was used to get this out of the
/// RetainedKnowledgeMap.
using Assume2KnowledgeMap = DenseMap<IntrinsicInst *, MinMax>;
using RetainedKnowledgeMap =
DenseMap<RetainedKnowledgeKey, Assume2KnowledgeMap>;
/// Insert into the map all the informations contained in the operand bundles of
/// the llvm.assume. This should be used instead of hasAttributeInAssume when
/// many queries are going to be made on the same llvm.assume.
/// String attributes are not inserted in the map.
/// If the IR changes the map will be outdated.
void fillMapFromAssume(CallInst &AssumeCI, RetainedKnowledgeMap &Result);
/// Represent one information held inside an operand bundle of an llvm.assume.
/// AttrKind is the property that hold.
/// WasOn if not null is that Value for which AttrKind holds.
/// ArgValue is optionally an argument.
struct RetainedKnowledge {
Attribute::AttrKind AttrKind = Attribute::None;
Value *WasOn = nullptr;
unsigned ArgValue = 0;
};
/// Retreive the information help by Assume on the operand at index Idx.
/// Assume should be an llvm.assume and Idx should be in the operand bundle.
RetainedKnowledge getKnowledgeFromOperandInAssume(CallInst &Assume,
unsigned Idx);
/// Retreive the information help by the Use U of an llvm.assume. the use should
/// be in the operand bundle.
inline RetainedKnowledge getKnowledgeFromUseInAssume(const Use *U) {
return getKnowledgeFromOperandInAssume(*cast<CallInst>(U->getUser()),
U->getOperandNo());
}
/// Return true iff the operand bundles of the provided llvm.assume doesn't
/// contain any valuable information. This is true when:
/// - The operand bundle is empty
/// - The operand bundle only contains information about dropped values or
/// constant folded values.
///
/// the argument to the call of llvm.assume may still be useful even if the
/// function returned true.
bool isAssumeWithEmptyBundle(CallInst &Assume);
//===----------------------------------------------------------------------===//
// Utilities for testing
//===----------------------------------------------------------------------===//
/// This pass will try to build an llvm.assume for every instruction in the
/// function. Its main purpose is testing.
struct AssumeBuilderPass : public PassInfoMixin<AssumeBuilderPass> {
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
};
} // namespace llvm
#endif