Changeset View
Standalone View
llvm/lib/Transforms/IPO/Attributor.cpp
1 | //===- Attributor.cpp - Module-wide attribute deduction -------------------===// | 1 | //===- Attributor.cpp - Module-wide attribute deduction -------------------===// | ||
---|---|---|---|---|---|
2 | // | 2 | // | ||
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | 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. | 4 | // See https://llvm.org/LICENSE.txt for license information. | ||
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | ||
6 | // | 6 | // | ||
7 | //===----------------------------------------------------------------------===// | 7 | //===----------------------------------------------------------------------===// | ||
8 | // | 8 | // | ||
9 | // This file implements an inter procedural pass which walk the call-graph | 9 | // This file implements an inter procedural pass which walk the call-graph | ||
10 | // deducing and/or propagating attributes along the way. This is done in an | 10 | // deducing and/or propagating attributes along the way. This is done in an | ||
11 | // abstract interpretation style fixpoint iteration. See the Attributor.h | 11 | // abstract interpretation style fixpoint iteration. See the Attributor.h | ||
12 | // file comment and the class descriptions in that file for more information. | 12 | // file comment and the class descriptions in that file for more information. | ||
13 | // | 13 | // | ||
14 | //===----------------------------------------------------------------------===// | 14 | //===----------------------------------------------------------------------===// | ||
15 | 15 | | |||
16 | #include "llvm/Transforms/IPO/Attributor.h" | 16 | #include "llvm/Transforms/IPO/Attributor.h" | ||
17 | #include "llvm/ADT/DepthFirstIterator.h" | ||||
17 | #include "llvm/ADT/SetVector.h" | 18 | #include "llvm/ADT/SetVector.h" | ||
18 | #include "llvm/ADT/SmallPtrSet.h" | 19 | #include "llvm/ADT/SmallPtrSet.h" | ||
19 | #include "llvm/ADT/SmallVector.h" | 20 | #include "llvm/ADT/SmallVector.h" | ||
20 | #include "llvm/ADT/Statistic.h" | 21 | #include "llvm/ADT/Statistic.h" | ||
21 | #include "llvm/Analysis/CallGraph.h" | 22 | #include "llvm/Analysis/CallGraph.h" | ||
22 | #include "llvm/Analysis/CallGraphSCCPass.h" | 23 | #include "llvm/Analysis/CallGraphSCCPass.h" | ||
23 | #include "llvm/Analysis/GlobalsModRef.h" | 24 | #include "llvm/Analysis/GlobalsModRef.h" | ||
24 | #include "llvm/IR/Argument.h" | 25 | #include "llvm/IR/Argument.h" | ||
▲ Show 20 Lines • Show All 458 Lines • ▼ Show 20 Line(s) | 483 | collectValuesRecursively(cast<ReturnInst>(RI)->getReturnValue(), RISet, | |||
483 | ReturnedValues); | 484 | ReturnedValues); | ||
484 | } | 485 | } | ||
485 | } | 486 | } | ||
486 | 487 | | |||
487 | /// See AbstractAttribute::manifest(...). | 488 | /// See AbstractAttribute::manifest(...). | ||
488 | virtual ChangeStatus manifest(Attributor &A) override; | 489 | virtual ChangeStatus manifest(Attributor &A) override; | ||
489 | 490 | | |||
490 | /// See AbstractAttribute::getState(...). | 491 | /// See AbstractAttribute::getState(...). | ||
491 | virtual AbstractState &getState() override { return *this; } | 492 | virtual AbstractState &getState() override { return *this; } | ||
jdoerfert: I think we should be cautious and not mark intrinsics as `willreturn` in the update method but… | |||||
492 | 493 | | |||
493 | /// See AbstractAttribute::getState(...). | 494 | /// See AbstractAttribute::getState(...). | ||
494 | virtual const AbstractState &getState() const override { return *this; } | 495 | virtual const AbstractState &getState() const override { return *this; } | ||
495 | 496 | | |||
496 | /// See AbstractAttribute::getManifestPosition(). | 497 | /// See AbstractAttribute::getManifestPosition(). | ||
497 | virtual ManifestPosition getManifestPosition() const override { | 498 | virtual ManifestPosition getManifestPosition() const override { | ||
498 | return MP_ARGUMENT; | 499 | return MP_ARGUMENT; | ||
499 | } | 500 | } | ||
▲ Show 20 Lines • Show All 526 Lines • ▼ Show 20 Line(s) | 1017 | } else { | |||
1026 | } | 1027 | } | ||
1027 | } | 1028 | } | ||
1028 | 1029 | | |||
1029 | // Fallthrough if we failed to keep the no-capture state. | 1030 | // Fallthrough if we failed to keep the no-capture state. | ||
1030 | indicatePessimisticFixpoint(); | 1031 | indicatePessimisticFixpoint(); | ||
1031 | return ChangeStatus::CHANGED; | 1032 | return ChangeStatus::CHANGED; | ||
1032 | } | 1033 | } | ||
1033 | 1034 | | |||
1035 | /// ------------------------ Will-Return Attributes ---------------------------- | ||||
1036 | | ||||
1037 | struct AAWillReturn : public AbstractAttribute { | ||||
Done ReplyPlease create an AAWillReturn interface in the header so it is easier to query the attribute. jdoerfert: Please create an AAWillReturn interface in the header so it is easier to query the attribute. | |||||
Done ReplyNow I would split this again into: jdoerfert: Now I would split this again into:
`struct AAWillReturn : public AbstractAttribute ` that… | |||||
Done ReplyCould you move this struct to the header file please? jdoerfert: Could you move this struct to the header file please? | |||||
1038 | | ||||
1039 | /// See AbstractAttribute::AbstractAttribute(...). | ||||
1040 | AAWillReturn(Function &F, InformationCache &InfoCache) | ||||
1041 | : AbstractAttribute(F, InfoCache) {} | ||||
1042 | | ||||
1043 | /// Return the deduced attributes in \p Attrs. | ||||
1044 | virtual void | ||||
1045 | getDeducedAttributes(SmallVectorImpl<Attribute> &Attrs) const override { | ||||
Done Replyassumed and known mixed up in the comments. jdoerfert: assumed and known mixed up in the comments. | |||||
1046 | LLVMContext &Ctx = AnchoredVal.getContext(); | ||||
1047 | Attrs.emplace_back(Attribute::get(Ctx, "willreturn")); | ||||
1048 | } | ||||
1049 | | ||||
1050 | /// See AbstractAttribute::getAttrKind() | ||||
1051 | virtual Attribute::AttrKind getAttrKind() const override { | ||||
1052 | return Attribute::None; | ||||
1053 | } | ||||
1054 | | ||||
1055 | /// Return true if "willreturn" is known. | ||||
1056 | bool isKnownWillReturn() const; | ||||
Done ReplyI think it might make sense to use the same spelling in the assumed case as we use for the attr. jdoerfert: I think it might make sense to use the same spelling in the assumed case as we use for the attr. | |||||
1057 | | ||||
1058 | /// Return true if "willreturn" is assumed. | ||||
1059 | bool isAssumedWillReturn() const; | ||||
1060 | | ||||
1061 | /// The identifier used by the Attributor for this class of attributes. | ||||
1062 | /// FIXME: I use Attribute::None + 2 for now. | ||||
1063 | static constexpr Attribute::AttrKind ID = | ||||
1064 | Attribute::AttrKind(Attribute::None + 2); | ||||
1065 | }; | ||||
1066 | | ||||
1067 | struct AAWillReturnImpl : public AAWillReturn, BooleanState { | ||||
1068 | | ||||
1069 | /// See AbstractAttribute::AbstractAttribute(...). | ||||
1070 | AAWillReturnImpl(Function &F, InformationCache &InfoCache) | ||||
1071 | : AAWillReturn(F, InfoCache) {} | ||||
1072 | | ||||
1073 | /// See AAWillReturn::isKnownWillReturn(). | ||||
1074 | bool isKnownWillReturn() const { return getKnown(); } | ||||
1075 | | ||||
1076 | /// See AAWillReturn::isAssumedWillReturn(). | ||||
1077 | bool isAssumedWillReturn() const { return getAssumed(); } | ||||
1078 | | ||||
1079 | /// See AbstractAttribute::getState(...). | ||||
1080 | virtual AbstractState &getState() override { return *this; } | ||||
1081 | | ||||
1082 | /// See AbstractAttribute::getState(...). | ||||
1083 | virtual const AbstractState &getState() const override { return *this; } | ||||
1084 | | ||||
1085 | /// See AbstractAttribute::getAsStr() | ||||
1086 | virtual const std::string getAsStr() const override { | ||||
1087 | return getAssumed() ? "willreturn" : "may-noreturn"; | ||||
1088 | } | ||||
1089 | }; | ||||
1090 | | ||||
1091 | struct AAWillReturnFunction final : AAWillReturnImpl { | ||||
1092 | | ||||
1093 | /// See AbstractAttribute::AbstractAttribute(...). | ||||
1094 | AAWillReturnFunction(Function &F, InformationCache &InfoCache) | ||||
1095 | : AAWillReturnImpl(F, InfoCache) {} | ||||
Done Replyfor (BasicBlock *SuccBB : successors(BB)) { jdoerfert: `for (BasicBlock *SuccBB : successors(BB)) {` | |||||
1096 | | ||||
1097 | /// See AbstractAttribute::getManifestPosition(). | ||||
1098 | virtual ManifestPosition getManifestPosition() const override { | ||||
Done ReplyNo braces around return jdoerfert: No braces around `return` | |||||
1099 | return MP_FUNCTION; | ||||
1100 | } | ||||
1101 | | ||||
1102 | /// See AbstractAttribute::initialize(...). | ||||
1103 | virtual void initialize(Attributor &A) override; | ||||
1104 | | ||||
1105 | /// See AbstractAttribute::updateImpl(...). | ||||
1106 | virtual ChangeStatus updateImpl(Attributor &A) override; | ||||
1107 | }; | ||||
1108 | | ||||
1109 | // Helper function that checks whether a function has any cycle. | ||||
Not Done ReplyLoop is commonly assumed to mean "natural loop", where there is one block (the header) which dominates the other blocks in the loop (the loop body). What you're looking for here is a more general thing called a cycle (equivalent to looking for a backedge). That also explains why you need your own function and can't reuse LoopInfo. nicholas: Loop is commonly assumed to mean "natural loop", where there is one block (the header) which… | |||||
Not Done Reply
OK, I rename it.
LoopInfo doesn't contain an irreducible loop (maybe endless loop) so I check the cycle manually for now. uenoku: > Loop is commonly assumed to mean "natural loop", where there is one block (the header) which… | |||||
Not Done Reply
Keep it this way for now, LoopInfo will currently not simplify things jdoerfert: > I'm going to use LoopInfo to check (i) whether a function has an irreducible loop and (ii)… | |||||
1110 | bool containsCycle(Function &F) { | ||||
1111 | SmallPtrSet<BasicBlock *, 32> Visited; | ||||
1112 | | ||||
1113 | // Traverse BB by dfs and check whether successor is already visited. | ||||
1114 | for (BasicBlock *BB : depth_first(&F)) { | ||||
1115 | Visited.insert(BB); | ||||
1116 | for (auto *SuccBB : successors(BB)) { | ||||
1117 | if (Visited.count(SuccBB)) | ||||
1118 | return true; | ||||
1119 | } | ||||
1120 | } | ||||
Not Done ReplyFYI, with effort, this could be pushed to be more efficient. df_iterator maintains its own copy of Visited, and it does its own scan over the successors of the block, neither of which need to be done twice. Unfortunately the fix is not entirely simple. nicholas: FYI, with effort, this could be pushed to be more efficient. df_iterator maintains its own copy… | |||||
Not Done ReplyLet's not optimize it preemptively. I'll run it through LLVM-TS and SPEC2006 before I commit it anyway, if there is a change in compile or runtime I'll report it back. jdoerfert: Let's not optimize it preemptively. I'll run it through LLVM-TS and SPEC2006 before I commit it… | |||||
Not Done ReplyI doubt human-written code will trigger slow compile times in this path, but I bet it could happen with machine generated code. Just leave a TODO noting how it could be more efficient. nicholas: I doubt human-written code will trigger slow compile times in this path, but I bet it could… | |||||
Not Done ReplyAgreed, to all of it. We will most likely see various "compile time problems" once we add more and more functionality (and actually turn it on), so keeping a record of fixes is very useful. @uenoku Can you add such a comment. jdoerfert: Agreed, to all of it. We will most likely see various "compile time problems" once we add more… | |||||
1121 | return false; | ||||
1122 | } | ||||
1123 | | ||||
1124 | // Helper function that checks the function have a loop which might become an | ||||
1125 | // endless loop | ||||
1126 | // FIXME: Any cycle is regarded as endless loop for now. | ||||
1127 | // We have to allow some patterns. | ||||
1128 | bool containsPossiblyEndlessLoop(Function &F) { return containsCycle(F); } | ||||
1129 | | ||||
1130 | void AAWillReturnFunction::initialize(Attributor &A) { | ||||
1131 | Function &F = getAnchorScope(); | ||||
1132 | | ||||
1133 | if (containsPossiblyEndlessLoop(F)) | ||||
1134 | indicatePessimisticFixpoint(); | ||||
1135 | } | ||||
1136 | | ||||
1137 | ChangeStatus AAWillReturnFunction::updateImpl(Attributor &A) { | ||||
1138 | Function &F = getAnchorScope(); | ||||
1139 | | ||||
1140 | // The map from instruction opcodes to those instructions in the function. | ||||
1141 | auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F); | ||||
1142 | | ||||
1143 | for (unsigned Opcode : | ||||
1144 | {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr, | ||||
1145 | (unsigned)Instruction::Call}) { | ||||
1146 | for (Instruction *I : OpcodeInstMap[Opcode]) { | ||||
1147 | auto ICS = ImmutableCallSite(I); | ||||
1148 | | ||||
1149 | // Assume that all intrinsic without noreturn are willreturn | ||||
1150 | if (isa<IntrinsicInst>(I) && !ICS.hasFnAttr(Attribute::NoReturn)) { | ||||
1151 | continue; | ||||
1152 | } | ||||
1153 | | ||||
1154 | auto *WillReturnAA = A.getAAFor<AAWillReturnFunction>(*this, *I); | ||||
1155 | if ((!WillReturnAA || !WillReturnAA->isValidState() || | ||||
1156 | !WillReturnAA->isAssumedWillReturn()) && | ||||
1157 | !ICS.hasFnAttr("willreturn")) { | ||||
1158 | indicatePessimisticFixpoint(); | ||||
1159 | return ChangeStatus::CHANGED; | ||||
1160 | } | ||||
1161 | | ||||
1162 | // FIXME: Prohibit any recursion for now | ||||
1163 | auto *NoRecurseAA = A.getAAFor<AANoRecurseFunction>(*this, *I); | ||||
1164 | if ((!NoRecurseAA || !NoRecurseAA->isValidState() || | ||||
1165 | !NoRecurseAA->isAssumedNoRecurse()) && | ||||
1166 | !ICS.hasFnAttr(Attribute::NoRecurse)) { | ||||
1167 | indicatePessimisticFixpoint(); | ||||
1168 | return ChangeStatus::CHANGED; | ||||
1169 | } | ||||
1170 | | ||||
1171 | auto *NoReturnAA = A.getAAFor<AANoReturnFunction>(*this, *I); | ||||
1172 | // If callee is known to be noreturn, a function is not willreturn. | ||||
1173 | if ((NoReturnAA && NoRecurseAA->isValidState() && | ||||
1174 | NoRecurseAA->isKnownNoReturn()) || | ||||
1175 | ICS.hasFnAttr(Attribute::NoReturn)) { | ||||
1176 | indicatePessimisticFixpoint(); | ||||
1177 | return ChangeStatus::CHANGED; | ||||
Not Done ReplyI'd argue: Either do not check for noreturn at all, which I would have initially thought we do, or do it explicitly for this function but not the callees. That way, the function which is noreturn is not willreturn and callers will no be able to get willreturn. However, once willreturn is deduced, noreturn should be irrelevant (IMHO), maybe contradicting. jdoerfert: I'd argue: Either do not check for noreturn at all, which I would have initially thought we do… | |||||
Done ReplyI agree with you. uenoku: I agree with you. | |||||
1178 | } | ||||
1179 | } | ||||
1180 | } | ||||
1181 | | ||||
1182 | return ChangeStatus::UNCHANGED; | ||||
1183 | } | ||||
1034 | 1184 | | |||
1035 | /// ---------------------------------------------------------------------------- | 1185 | /// ---------------------------------------------------------------------------- | ||
1036 | /// Attributor | 1186 | /// Attributor | ||
1037 | /// ---------------------------------------------------------------------------- | 1187 | /// ---------------------------------------------------------------------------- | ||
1038 | 1188 | | |||
1039 | ChangeStatus Attributor::run() { | 1189 | ChangeStatus Attributor::run() { | ||
1040 | // Initialize all abstract attributes. | 1190 | // Initialize all abstract attributes. | ||
1041 | for (AbstractAttribute *AA : AllAbstractAttributes) | 1191 | for (AbstractAttribute *AA : AllAbstractAttributes) | ||
▲ Show 20 Lines • Show All 143 Lines • ▼ Show 20 Line(s) | 1321 | void Attributor::identifyDefaultAbstractAttributes( | |||
1185 | registerAA(*new AANoRecurseFunction(F, InfoCache)); | 1335 | registerAA(*new AANoRecurseFunction(F, InfoCache)); | ||
1186 | 1336 | | |||
1187 | // Every function might be "no-free". | 1337 | // Every function might be "no-free". | ||
1188 | registerAA(*new AANoFreeFunction(F, InfoCache)); | 1338 | registerAA(*new AANoFreeFunction(F, InfoCache)); | ||
1189 | 1339 | | |||
1190 | // Every function might be "no-return". | 1340 | // Every function might be "no-return". | ||
1191 | registerAA(*new AANoReturnFunction(F, InfoCache)); | 1341 | registerAA(*new AANoReturnFunction(F, InfoCache)); | ||
1192 | 1342 | | |||
1343 | // Every function might be "will-return". | ||||
1344 | registerAA(*new AAWillReturnFunction(F, InfoCache)); | ||||
1345 | | ||||
1193 | // Walk all instructions to find more attribute opportunities and also | 1346 | // Walk all instructions to find more attribute opportunities and also | ||
1194 | // interesting instructions that might be queried by abstract attributes | 1347 | // interesting instructions that might be queried by abstract attributes | ||
1195 | // during their initialization or update. | 1348 | // during their initialization or update. | ||
1196 | auto &ReadOrWriteInsts = InfoCache.FuncRWInstsMap[&F]; | 1349 | auto &ReadOrWriteInsts = InfoCache.FuncRWInstsMap[&F]; | ||
1197 | auto &InstOpcodeMap = InfoCache.FuncInstOpcodeMap[&F]; | 1350 | auto &InstOpcodeMap = InfoCache.FuncInstOpcodeMap[&F]; | ||
1198 | 1351 | | |||
1199 | for (Instruction &I : instructions(&F)) { | 1352 | for (Instruction &I : instructions(&F)) { | ||
1200 | bool IsInterestingOpcode = false; | 1353 | bool IsInterestingOpcode = false; | ||
▲ Show 20 Lines • Show All 159 Lines • Show Last 20 Lines |
I think we should be cautious and not mark intrinsics as willreturn in the update method but instead do it explicitly as such in the Intrinsics.td file.
Also, drop the braces around single statements.