| 1 | //===- AssumeBundleBuilder.cpp - tools to preserve informations -*- 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 | #include "llvm/Transforms/Utils/AssumeBundleBuilder.h" |
| 10 | #include "llvm/ADT/DepthFirstIterator.h" |
| 11 | #include "llvm/ADT/MapVector.h" |
| 12 | #include "llvm/ADT/Statistic.h" |
| 13 | #include "llvm/Analysis/AssumeBundleQueries.h" |
| 14 | #include "llvm/Analysis/AssumptionCache.h" |
| 15 | #include "llvm/Analysis/ValueTracking.h" |
| 16 | #include "llvm/IR/Dominators.h" |
| 17 | #include "llvm/IR/Function.h" |
| 18 | #include "llvm/IR/InstIterator.h" |
| 19 | #include "llvm/IR/IntrinsicInst.h" |
| 20 | #include "llvm/IR/Module.h" |
| 21 | #include "llvm/IR/Operator.h" |
| 22 | #include "llvm/Support/CommandLine.h" |
| 23 | #include "llvm/Support/DebugCounter.h" |
| 24 | #include "llvm/Transforms/Utils/Local.h" |
| 25 | |
| 26 | using namespace llvm; |
| 27 | |
| 28 | namespace llvm { |
| 29 | cl::opt<bool> EnableKnowledgeRetention( |
| 30 | "enable-knowledge-retention" , cl::init(Val: false), cl::Hidden, |
| 31 | cl::desc( |
| 32 | "enable preservation of attributes throughout code transformation" )); |
| 33 | } // namespace llvm |
| 34 | |
| 35 | #define DEBUG_TYPE "assume-builder" |
| 36 | |
| 37 | STATISTIC(NumAssumeBuilt, "Number of assume built by the assume builder" ); |
| 38 | STATISTIC(NumBundlesInAssumes, "Total number of Bundles in the assume built" ); |
| 39 | |
| 40 | DEBUG_COUNTER(BuildAssumeCounter, "assume-builder-counter" , |
| 41 | "Controls which assumes gets created" ); |
| 42 | |
| 43 | namespace { |
| 44 | |
| 45 | bool isUsefullToPreserve(Attribute::AttrKind Kind) { |
| 46 | switch (Kind) { |
| 47 | case Attribute::NonNull: |
| 48 | case Attribute::NoUndef: |
| 49 | case Attribute::Alignment: |
| 50 | case Attribute::Dereferenceable: |
| 51 | case Attribute::DereferenceableOrNull: |
| 52 | case Attribute::Cold: |
| 53 | return true; |
| 54 | default: |
| 55 | return false; |
| 56 | } |
| 57 | } |
| 58 | |
| 59 | /// This function will try to transform the given knowledge into a more |
| 60 | /// canonical one. the canonical knowledge maybe the given one. |
| 61 | RetainedKnowledge canonicalizedKnowledge(RetainedKnowledge RK, |
| 62 | const DataLayout &DL) { |
| 63 | switch (RK.AttrKind) { |
| 64 | default: |
| 65 | return RK; |
| 66 | case Attribute::NonNull: |
| 67 | RK.WasOn = RK.WasOn->stripInBoundsOffsets(); |
| 68 | return RK; |
| 69 | case Attribute::Alignment: { |
| 70 | Value *V = RK.WasOn->stripInBoundsOffsets(Func: [&](const Value *Strip) { |
| 71 | if (auto *GEP = dyn_cast<GEPOperator>(Val: Strip)) |
| 72 | RK.ArgValue = |
| 73 | MinAlign(A: RK.ArgValue, B: GEP->getMaxPreservedAlignment(DL).value()); |
| 74 | }); |
| 75 | RK.WasOn = V; |
| 76 | return RK; |
| 77 | } |
| 78 | case Attribute::Dereferenceable: |
| 79 | case Attribute::DereferenceableOrNull: { |
| 80 | int64_t Offset = 0; |
| 81 | Value *V = GetPointerBaseWithConstantOffset(Ptr: RK.WasOn, Offset, DL, |
| 82 | /*AllowNonInBounds*/ AllowNonInbounds: false); |
| 83 | if (Offset < 0) |
| 84 | return RK; |
| 85 | RK.ArgValue = RK.ArgValue + Offset; |
| 86 | RK.WasOn = V; |
| 87 | } |
| 88 | } |
| 89 | return RK; |
| 90 | } |
| 91 | |
| 92 | /// This class contain all knowledge that have been gather while building an |
| 93 | /// llvm.assume and the function to manipulate it. |
| 94 | struct AssumeBuilderState { |
| 95 | Module *M; |
| 96 | |
| 97 | using MapKey = std::pair<Value *, Attribute::AttrKind>; |
| 98 | SmallMapVector<MapKey, uint64_t, 8> AssumedKnowledgeMap; |
| 99 | Instruction *InstBeingModified = nullptr; |
| 100 | AssumptionCache* AC = nullptr; |
| 101 | DominatorTree* DT = nullptr; |
| 102 | |
| 103 | AssumeBuilderState(Module *M, Instruction *I = nullptr, |
| 104 | AssumptionCache *AC = nullptr, DominatorTree *DT = nullptr) |
| 105 | : M(M), InstBeingModified(I), AC(AC), DT(DT) {} |
| 106 | |
| 107 | bool tryToPreserveWithoutAddingAssume(RetainedKnowledge RK) { |
| 108 | if (!InstBeingModified || !RK.WasOn || !AC) |
| 109 | return false; |
| 110 | bool HasBeenPreserved = false; |
| 111 | Use* ToUpdate = nullptr; |
| 112 | getKnowledgeForValue( |
| 113 | V: RK.WasOn, AttrKinds: {RK.AttrKind}, AC&: *AC, |
| 114 | Filter: [&](RetainedKnowledge RKOther, Instruction *Assume, |
| 115 | const CallInst::BundleOpInfo *Bundle) { |
| 116 | if (!isValidAssumeForContext(I: Assume, CtxI: InstBeingModified, DT)) |
| 117 | return false; |
| 118 | if (RKOther.ArgValue >= RK.ArgValue) { |
| 119 | HasBeenPreserved = true; |
| 120 | return true; |
| 121 | } else if (isValidAssumeForContext(I: InstBeingModified, CtxI: Assume, DT)) { |
| 122 | HasBeenPreserved = true; |
| 123 | IntrinsicInst *Intr = cast<IntrinsicInst>(Val: Assume); |
| 124 | ToUpdate = &Intr->op_begin()[Bundle->Begin + ABA_Argument]; |
| 125 | return true; |
| 126 | } |
| 127 | return false; |
| 128 | }); |
| 129 | if (ToUpdate) |
| 130 | ToUpdate->set( |
| 131 | ConstantInt::get(Ty: Type::getInt64Ty(C&: M->getContext()), V: RK.ArgValue)); |
| 132 | return HasBeenPreserved; |
| 133 | } |
| 134 | |
| 135 | bool isKnowledgeWorthPreserving(RetainedKnowledge RK) { |
| 136 | if (!RK) |
| 137 | return false; |
| 138 | if (!RK.WasOn) |
| 139 | return true; |
| 140 | if (RK.WasOn->getType()->isPointerTy()) { |
| 141 | Value *UnderlyingPtr = getUnderlyingObject(V: RK.WasOn); |
| 142 | if (isa<AllocaInst>(Val: UnderlyingPtr) || isa<GlobalValue>(Val: UnderlyingPtr)) |
| 143 | return false; |
| 144 | } |
| 145 | if (auto *Arg = dyn_cast<Argument>(Val: RK.WasOn)) { |
| 146 | if (Arg->hasAttribute(Kind: RK.AttrKind) && |
| 147 | (!Attribute::isIntAttrKind(Kind: RK.AttrKind) || |
| 148 | Arg->getAttribute(Kind: RK.AttrKind).getValueAsInt() >= RK.ArgValue)) |
| 149 | return false; |
| 150 | return true; |
| 151 | } |
| 152 | if (auto *Inst = dyn_cast<Instruction>(Val: RK.WasOn)) |
| 153 | if (wouldInstructionBeTriviallyDead(I: Inst)) { |
| 154 | if (RK.WasOn->use_empty()) |
| 155 | return false; |
| 156 | Use *SingleUse = RK.WasOn->getSingleUndroppableUse(); |
| 157 | if (SingleUse && SingleUse->getUser() == InstBeingModified) |
| 158 | return false; |
| 159 | } |
| 160 | return true; |
| 161 | } |
| 162 | |
| 163 | void addKnowledge(RetainedKnowledge RK) { |
| 164 | RK = canonicalizedKnowledge(RK, DL: M->getDataLayout()); |
| 165 | |
| 166 | if (!isKnowledgeWorthPreserving(RK)) |
| 167 | return; |
| 168 | |
| 169 | if (tryToPreserveWithoutAddingAssume(RK)) |
| 170 | return; |
| 171 | MapKey Key{RK.WasOn, RK.AttrKind}; |
| 172 | auto [Lookup, Inserted] = AssumedKnowledgeMap.try_emplace(Key, Args&: RK.ArgValue); |
| 173 | if (Inserted) |
| 174 | return; |
| 175 | assert(((Lookup->second == 0 && RK.ArgValue == 0) || |
| 176 | (Lookup->second != 0 && RK.ArgValue != 0)) && |
| 177 | "inconsistent argument value" ); |
| 178 | |
| 179 | /// This is only desirable because for all attributes taking an argument |
| 180 | /// higher is better. |
| 181 | Lookup->second = std::max(a: Lookup->second, b: RK.ArgValue); |
| 182 | } |
| 183 | |
| 184 | void addAttribute(Attribute Attr, Value *WasOn) { |
| 185 | if (Attr.isTypeAttribute() || Attr.isStringAttribute() || |
| 186 | !isUsefullToPreserve(Kind: Attr.getKindAsEnum())) |
| 187 | return; |
| 188 | uint64_t AttrArg = 0; |
| 189 | if (Attr.isIntAttribute()) |
| 190 | AttrArg = Attr.getValueAsInt(); |
| 191 | addKnowledge(RK: {Attr.getKindAsEnum(), AttrArg, WasOn}); |
| 192 | } |
| 193 | |
| 194 | void addCall(const CallBase *Call) { |
| 195 | auto addAttrList = [&](AttributeList AttrList, unsigned NumArgs) { |
| 196 | for (unsigned Idx = 0; Idx < NumArgs; Idx++) |
| 197 | for (Attribute Attr : AttrList.getParamAttrs(ArgNo: Idx)) { |
| 198 | bool IsPoisonAttr = Attr.hasAttribute(Val: Attribute::NonNull) || |
| 199 | Attr.hasAttribute(Val: Attribute::Alignment); |
| 200 | if (!IsPoisonAttr || Call->isPassingUndefUB(ArgNo: Idx)) |
| 201 | addAttribute(Attr, WasOn: Call->getArgOperand(i: Idx)); |
| 202 | } |
| 203 | for (Attribute Attr : AttrList.getFnAttrs()) |
| 204 | addAttribute(Attr, WasOn: nullptr); |
| 205 | }; |
| 206 | addAttrList(Call->getAttributes(), Call->arg_size()); |
| 207 | if (Function *Fn = Call->getCalledFunction()) |
| 208 | addAttrList(Fn->getAttributes(), Fn->arg_size()); |
| 209 | } |
| 210 | |
| 211 | AssumeInst *build() { |
| 212 | if (AssumedKnowledgeMap.empty()) |
| 213 | return nullptr; |
| 214 | if (!DebugCounter::shouldExecute(Counter&: BuildAssumeCounter)) |
| 215 | return nullptr; |
| 216 | Function *FnAssume = |
| 217 | Intrinsic::getOrInsertDeclaration(M, id: Intrinsic::assume); |
| 218 | LLVMContext &C = M->getContext(); |
| 219 | SmallVector<OperandBundleDef, 8> OpBundle; |
| 220 | for (auto &MapElem : AssumedKnowledgeMap) { |
| 221 | SmallVector<Value *, 2> Args; |
| 222 | if (MapElem.first.first) |
| 223 | Args.push_back(Elt: MapElem.first.first); |
| 224 | |
| 225 | /// This is only valid because for all attribute that currently exist a |
| 226 | /// value of 0 is useless. and should not be preserved. |
| 227 | if (MapElem.second) |
| 228 | Args.push_back(Elt: ConstantInt::get(Ty: Type::getInt64Ty(C&: M->getContext()), |
| 229 | V: MapElem.second)); |
| 230 | OpBundle.push_back(Elt: OperandBundleDefT<Value *>( |
| 231 | std::string(Attribute::getNameFromAttrKind(AttrKind: MapElem.first.second)), |
| 232 | Args)); |
| 233 | NumBundlesInAssumes++; |
| 234 | } |
| 235 | NumAssumeBuilt++; |
| 236 | return cast<AssumeInst>(Val: CallInst::Create( |
| 237 | Func: FnAssume, Args: ArrayRef<Value *>({ConstantInt::getTrue(Context&: C)}), Bundles: OpBundle)); |
| 238 | } |
| 239 | |
| 240 | void addAccessedPtr(Instruction *MemInst, Value *Pointer, Type *AccType, |
| 241 | MaybeAlign MA) { |
| 242 | unsigned DerefSize = MemInst->getModule() |
| 243 | ->getDataLayout() |
| 244 | .getTypeStoreSize(Ty: AccType) |
| 245 | .getKnownMinValue(); |
| 246 | if (DerefSize != 0) { |
| 247 | addKnowledge(RK: {Attribute::Dereferenceable, DerefSize, Pointer}); |
| 248 | if (!NullPointerIsDefined(F: MemInst->getFunction(), |
| 249 | AS: Pointer->getType()->getPointerAddressSpace())) |
| 250 | addKnowledge(RK: {Attribute::NonNull, 0u, Pointer}); |
| 251 | } |
| 252 | if (MA.valueOrOne() > 1) |
| 253 | addKnowledge(RK: {Attribute::Alignment, MA.valueOrOne().value(), Pointer}); |
| 254 | } |
| 255 | |
| 256 | void addInstruction(Instruction *I) { |
| 257 | if (auto *Call = dyn_cast<CallBase>(Val: I)) |
| 258 | return addCall(Call); |
| 259 | if (auto *Load = dyn_cast<LoadInst>(Val: I)) |
| 260 | return addAccessedPtr(MemInst: I, Pointer: Load->getPointerOperand(), AccType: Load->getType(), |
| 261 | MA: Load->getAlign()); |
| 262 | if (auto *Store = dyn_cast<StoreInst>(Val: I)) |
| 263 | return addAccessedPtr(MemInst: I, Pointer: Store->getPointerOperand(), |
| 264 | AccType: Store->getValueOperand()->getType(), |
| 265 | MA: Store->getAlign()); |
| 266 | if (auto *RMW = dyn_cast<AtomicRMWInst>(Val: I)) |
| 267 | return addAccessedPtr(MemInst: I, Pointer: RMW->getPointerOperand(), |
| 268 | AccType: RMW->getValOperand()->getType(), MA: RMW->getAlign()); |
| 269 | if (auto *CmpXchg = dyn_cast<AtomicCmpXchgInst>(Val: I)) |
| 270 | return addAccessedPtr(MemInst: I, Pointer: CmpXchg->getPointerOperand(), |
| 271 | AccType: CmpXchg->getCompareOperand()->getType(), |
| 272 | MA: CmpXchg->getAlign()); |
| 273 | // TODO: Maybe we should look around and merge with other llvm.assume. |
| 274 | } |
| 275 | }; |
| 276 | |
| 277 | } // namespace |
| 278 | |
| 279 | AssumeInst *llvm::buildAssumeFromInst(Instruction *I) { |
| 280 | if (!EnableKnowledgeRetention) |
| 281 | return nullptr; |
| 282 | AssumeBuilderState Builder(I->getModule()); |
| 283 | Builder.addInstruction(I); |
| 284 | return Builder.build(); |
| 285 | } |
| 286 | |
| 287 | bool llvm::salvageKnowledge(Instruction *I, AssumptionCache *AC, |
| 288 | DominatorTree *DT) { |
| 289 | if (!EnableKnowledgeRetention || I->isTerminator()) |
| 290 | return false; |
| 291 | bool Changed = false; |
| 292 | AssumeBuilderState Builder(I->getModule(), I, AC, DT); |
| 293 | Builder.addInstruction(I); |
| 294 | if (auto *Intr = Builder.build()) { |
| 295 | Intr->insertBefore(InsertPos: I->getIterator()); |
| 296 | Changed = true; |
| 297 | if (AC) |
| 298 | AC->registerAssumption(CI: Intr); |
| 299 | } |
| 300 | return Changed; |
| 301 | } |
| 302 | |
| 303 | PreservedAnalyses AssumeBuilderPass::run(Function &F, |
| 304 | FunctionAnalysisManager &AM) { |
| 305 | AssumptionCache *AC = &AM.getResult<AssumptionAnalysis>(IR&: F); |
| 306 | DominatorTree* DT = AM.getCachedResult<DominatorTreeAnalysis>(IR&: F); |
| 307 | bool Changed = false; |
| 308 | for (Instruction &I : instructions(F)) |
| 309 | Changed |= salvageKnowledge(I: &I, AC, DT); |
| 310 | if (!Changed) |
| 311 | PreservedAnalyses::all(); |
| 312 | PreservedAnalyses PA; |
| 313 | PA.preserveSet<CFGAnalyses>(); |
| 314 | return PA; |
| 315 | } |
| 316 | |