| 1 | //===- AliasAnalysisEvaluator.cpp - Alias Analysis Accuracy Evaluator -----===// |
| 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/Analysis/AliasAnalysisEvaluator.h" |
| 10 | #include "AnalysisOptions.h" |
| 11 | #include "llvm/ADT/SetVector.h" |
| 12 | #include "llvm/Analysis/AliasAnalysis.h" |
| 13 | #include "llvm/IR/DataLayout.h" |
| 14 | #include "llvm/IR/Function.h" |
| 15 | #include "llvm/IR/InstIterator.h" |
| 16 | #include "llvm/IR/Instructions.h" |
| 17 | #include "llvm/IR/Module.h" |
| 18 | #include "llvm/Support/raw_ostream.h" |
| 19 | using namespace llvm; |
| 20 | |
| 21 | static void printResults(const AnalysisOptions &Opts, AliasResult AR, bool P, |
| 22 | std::pair<const Value *, Type *> Loc1, |
| 23 | std::pair<const Value *, Type *> Loc2, |
| 24 | const Module *M) { |
| 25 | if (Opts.print_all_alias_modref_info || P) { |
| 26 | Type *Ty1 = Loc1.second, *Ty2 = Loc2.second; |
| 27 | unsigned AS1 = Loc1.first->getType()->getPointerAddressSpace(); |
| 28 | unsigned AS2 = Loc2.first->getType()->getPointerAddressSpace(); |
| 29 | std::string o1, o2; |
| 30 | { |
| 31 | raw_string_ostream os1(o1), os2(o2); |
| 32 | Loc1.first->printAsOperand(O&: os1, PrintType: false, M); |
| 33 | Loc2.first->printAsOperand(O&: os2, PrintType: false, M); |
| 34 | } |
| 35 | |
| 36 | if (o2 < o1) { |
| 37 | std::swap(lhs&: o1, rhs&: o2); |
| 38 | std::swap(a&: Ty1, b&: Ty2); |
| 39 | std::swap(a&: AS1, b&: AS2); |
| 40 | // Change offset sign for the local AR, for printing only. |
| 41 | AR.swap(); |
| 42 | } |
| 43 | errs() << " " << AR << ":\t" ; |
| 44 | Ty1->print(O&: errs(), IsForDebug: false, /* NoDetails */ true); |
| 45 | if (AS1 != 0) |
| 46 | errs() << " addrspace(" << AS1 << ")" ; |
| 47 | errs() << "* " << o1 << ", " ; |
| 48 | Ty2->print(O&: errs(), IsForDebug: false, /* NoDetails */ true); |
| 49 | if (AS2 != 0) |
| 50 | errs() << " addrspace(" << AS2 << ")" ; |
| 51 | errs() << "* " << o2 << "\n" ; |
| 52 | } |
| 53 | } |
| 54 | |
| 55 | static inline void printModRefResults(const AnalysisOptions &Opts, |
| 56 | const char *Msg, bool P, Instruction *I, |
| 57 | std::pair<const Value *, Type *> Loc, |
| 58 | Module *M) { |
| 59 | if (Opts.print_all_alias_modref_info || P) { |
| 60 | errs() << " " << Msg << ": Ptr: " ; |
| 61 | Loc.second->print(O&: errs(), IsForDebug: false, /* NoDetails */ true); |
| 62 | errs() << "* " ; |
| 63 | Loc.first->printAsOperand(O&: errs(), PrintType: false, M); |
| 64 | errs() << "\t<->" << *I << '\n'; |
| 65 | } |
| 66 | } |
| 67 | |
| 68 | static inline void printModRefResults(const AnalysisOptions &Opts, |
| 69 | const char *Msg, bool P, |
| 70 | Instruction *MemOpA, Instruction *MemOpB, |
| 71 | Module *M) { |
| 72 | if (Opts.print_all_alias_modref_info || P) { |
| 73 | errs() << " " << Msg << ": " << *MemOpA << " <-> " << *MemOpB << '\n'; |
| 74 | } |
| 75 | } |
| 76 | |
| 77 | static inline void printLoadStoreResults(const AnalysisOptions &Opts, |
| 78 | AliasResult AR, bool P, |
| 79 | const Value *V1, const Value *V2, |
| 80 | const Module *M) { |
| 81 | if (Opts.print_all_alias_modref_info || P) { |
| 82 | errs() << " " << AR << ": " << *V1 << " <-> " << *V2 << '\n'; |
| 83 | } |
| 84 | } |
| 85 | |
| 86 | PreservedAnalyses AAEvaluator::run(Function &F, FunctionAnalysisManager &AM) { |
| 87 | runInternal(F, AA&: AM.getResult<AAManager>(IR&: F)); |
| 88 | return PreservedAnalyses::all(); |
| 89 | } |
| 90 | |
| 91 | void AAEvaluator::runInternal(Function &F, AAResults &AA) { |
| 92 | const AnalysisOptions &Opts = getAnalysisOptions(F); |
| 93 | const DataLayout &DL = F.getDataLayout(); |
| 94 | |
| 95 | ++FunctionCount; |
| 96 | |
| 97 | SetVector<std::pair<const Value *, Type *>> Pointers; |
| 98 | SmallSetVector<Instruction *, 16> OtherMemOps; |
| 99 | SetVector<Value *> Loads; |
| 100 | SetVector<Value *> Stores; |
| 101 | |
| 102 | for (Instruction &Inst : instructions(F)) { |
| 103 | if (auto *LI = dyn_cast<LoadInst>(Val: &Inst)) { |
| 104 | Pointers.insert(X: {LI->getPointerOperand(), LI->getType()}); |
| 105 | Loads.insert(X: LI); |
| 106 | } else if (auto *SI = dyn_cast<StoreInst>(Val: &Inst)) { |
| 107 | Pointers.insert(X: {SI->getPointerOperand(), |
| 108 | SI->getValueOperand()->getType()}); |
| 109 | Stores.insert(X: SI); |
| 110 | } |
| 111 | |
| 112 | if (isa<CallBase>(Val: Inst) || Inst.isAtomic()) |
| 113 | OtherMemOps.insert(X: &Inst); |
| 114 | } |
| 115 | |
| 116 | if (Opts.print_all_alias_modref_info || Opts.print_no_aliases || |
| 117 | Opts.print_may_aliases || Opts.print_partial_aliases || |
| 118 | Opts.print_must_aliases || Opts.print_no_modref || Opts.print_mod || |
| 119 | Opts.print_ref || Opts.print_modref) |
| 120 | errs() << "Function: " << F.getName() << ": " << Pointers.size() |
| 121 | << " pointers, " << OtherMemOps.size() << " call sites\n" ; |
| 122 | |
| 123 | // iterate over the worklist, and run the full (n^2)/2 disambiguations |
| 124 | for (auto I1 = Pointers.begin(), E = Pointers.end(); I1 != E; ++I1) { |
| 125 | LocationSize Size1 = LocationSize::precise(Value: DL.getTypeStoreSize(Ty: I1->second)); |
| 126 | for (auto I2 = Pointers.begin(); I2 != I1; ++I2) { |
| 127 | LocationSize Size2 = |
| 128 | LocationSize::precise(Value: DL.getTypeStoreSize(Ty: I2->second)); |
| 129 | AliasResult AR = AA.alias(V1: I1->first, V1Size: Size1, V2: I2->first, V2Size: Size2); |
| 130 | switch (AR) { |
| 131 | case AliasResult::NoAlias: |
| 132 | printResults(Opts, AR, P: Opts.print_no_aliases, Loc1: *I1, Loc2: *I2, M: F.getParent()); |
| 133 | ++NoAliasCount; |
| 134 | break; |
| 135 | case AliasResult::MayAlias: |
| 136 | printResults(Opts, AR, P: Opts.print_may_aliases, Loc1: *I1, Loc2: *I2, M: F.getParent()); |
| 137 | ++MayAliasCount; |
| 138 | break; |
| 139 | case AliasResult::PartialAlias: |
| 140 | printResults(Opts, AR, P: Opts.print_partial_aliases, Loc1: *I1, Loc2: *I2, |
| 141 | M: F.getParent()); |
| 142 | ++PartialAliasCount; |
| 143 | break; |
| 144 | case AliasResult::MustAlias: |
| 145 | printResults(Opts, AR, P: Opts.print_must_aliases, Loc1: *I1, Loc2: *I2, |
| 146 | M: F.getParent()); |
| 147 | ++MustAliasCount; |
| 148 | break; |
| 149 | } |
| 150 | } |
| 151 | } |
| 152 | |
| 153 | if (Opts.evaluate_aa_metadata) { |
| 154 | // iterate over all pairs of load, store |
| 155 | for (Value *Load : Loads) { |
| 156 | for (Value *Store : Stores) { |
| 157 | AliasResult AR = AA.alias(LocA: MemoryLocation::get(LI: cast<LoadInst>(Val: Load)), |
| 158 | LocB: MemoryLocation::get(SI: cast<StoreInst>(Val: Store))); |
| 159 | switch (AR) { |
| 160 | case AliasResult::NoAlias: |
| 161 | printLoadStoreResults(Opts, AR, P: Opts.print_no_aliases, V1: Load, V2: Store, |
| 162 | M: F.getParent()); |
| 163 | ++NoAliasCount; |
| 164 | break; |
| 165 | case AliasResult::MayAlias: |
| 166 | printLoadStoreResults(Opts, AR, P: Opts.print_may_aliases, V1: Load, V2: Store, |
| 167 | M: F.getParent()); |
| 168 | ++MayAliasCount; |
| 169 | break; |
| 170 | case AliasResult::PartialAlias: |
| 171 | printLoadStoreResults(Opts, AR, P: Opts.print_partial_aliases, V1: Load, |
| 172 | V2: Store, M: F.getParent()); |
| 173 | ++PartialAliasCount; |
| 174 | break; |
| 175 | case AliasResult::MustAlias: |
| 176 | printLoadStoreResults(Opts, AR, P: Opts.print_must_aliases, V1: Load, V2: Store, |
| 177 | M: F.getParent()); |
| 178 | ++MustAliasCount; |
| 179 | break; |
| 180 | } |
| 181 | } |
| 182 | } |
| 183 | |
| 184 | // iterate over all pairs of store, store |
| 185 | for (SetVector<Value *>::iterator I1 = Stores.begin(), E = Stores.end(); |
| 186 | I1 != E; ++I1) { |
| 187 | for (SetVector<Value *>::iterator I2 = Stores.begin(); I2 != I1; ++I2) { |
| 188 | AliasResult AR = AA.alias(LocA: MemoryLocation::get(SI: cast<StoreInst>(Val: *I1)), |
| 189 | LocB: MemoryLocation::get(SI: cast<StoreInst>(Val: *I2))); |
| 190 | switch (AR) { |
| 191 | case AliasResult::NoAlias: |
| 192 | printLoadStoreResults(Opts, AR, P: Opts.print_no_aliases, V1: *I1, V2: *I2, |
| 193 | M: F.getParent()); |
| 194 | ++NoAliasCount; |
| 195 | break; |
| 196 | case AliasResult::MayAlias: |
| 197 | printLoadStoreResults(Opts, AR, P: Opts.print_may_aliases, V1: *I1, V2: *I2, |
| 198 | M: F.getParent()); |
| 199 | ++MayAliasCount; |
| 200 | break; |
| 201 | case AliasResult::PartialAlias: |
| 202 | printLoadStoreResults(Opts, AR, P: Opts.print_partial_aliases, V1: *I1, V2: *I2, |
| 203 | M: F.getParent()); |
| 204 | ++PartialAliasCount; |
| 205 | break; |
| 206 | case AliasResult::MustAlias: |
| 207 | printLoadStoreResults(Opts, AR, P: Opts.print_must_aliases, V1: *I1, V2: *I2, |
| 208 | M: F.getParent()); |
| 209 | ++MustAliasCount; |
| 210 | break; |
| 211 | } |
| 212 | } |
| 213 | } |
| 214 | } |
| 215 | |
| 216 | // Mod/ref alias analysis: compare all pairs of mem ops and values |
| 217 | for (Instruction *MemOp : OtherMemOps) { |
| 218 | for (const auto &Pointer : Pointers) { |
| 219 | LocationSize Size = |
| 220 | LocationSize::precise(Value: DL.getTypeStoreSize(Ty: Pointer.second)); |
| 221 | switch (AA.getModRefInfo(I: MemOp, P: Pointer.first, Size)) { |
| 222 | case ModRefInfo::NoModRef: |
| 223 | printModRefResults(Opts, Msg: "NoModRef" , P: Opts.print_no_modref, I: MemOp, |
| 224 | Loc: Pointer, M: F.getParent()); |
| 225 | ++NoModRefCount; |
| 226 | break; |
| 227 | case ModRefInfo::Mod: |
| 228 | printModRefResults(Opts, Msg: "Just Mod" , P: Opts.print_mod, I: MemOp, Loc: Pointer, |
| 229 | M: F.getParent()); |
| 230 | ++ModCount; |
| 231 | break; |
| 232 | case ModRefInfo::Ref: |
| 233 | printModRefResults(Opts, Msg: "Just Ref" , P: Opts.print_ref, I: MemOp, Loc: Pointer, |
| 234 | M: F.getParent()); |
| 235 | ++RefCount; |
| 236 | break; |
| 237 | case ModRefInfo::ModRef: |
| 238 | printModRefResults(Opts, Msg: "Both ModRef" , P: Opts.print_modref, I: MemOp, |
| 239 | Loc: Pointer, M: F.getParent()); |
| 240 | ++ModRefCount; |
| 241 | break; |
| 242 | } |
| 243 | } |
| 244 | } |
| 245 | |
| 246 | // Mod/ref alias analysis: compare all pairs of mem ops |
| 247 | for (Instruction *MemOpA : OtherMemOps) { |
| 248 | for (Instruction *MemOpB : OtherMemOps) { |
| 249 | if (MemOpA == MemOpB) |
| 250 | continue; |
| 251 | switch (AA.getModRefInfo(I1: MemOpA, I2: MemOpB)) { |
| 252 | case ModRefInfo::NoModRef: |
| 253 | printModRefResults(Opts, Msg: "NoModRef" , P: Opts.print_no_modref, MemOpA, |
| 254 | MemOpB, M: F.getParent()); |
| 255 | ++NoModRefCount; |
| 256 | break; |
| 257 | case ModRefInfo::Mod: |
| 258 | printModRefResults(Opts, Msg: "Just Mod" , P: Opts.print_mod, MemOpA, MemOpB, |
| 259 | M: F.getParent()); |
| 260 | ++ModCount; |
| 261 | break; |
| 262 | case ModRefInfo::Ref: |
| 263 | printModRefResults(Opts, Msg: "Just Ref" , P: Opts.print_ref, MemOpA, MemOpB, |
| 264 | M: F.getParent()); |
| 265 | ++RefCount; |
| 266 | break; |
| 267 | case ModRefInfo::ModRef: |
| 268 | printModRefResults(Opts, Msg: "Both ModRef" , P: Opts.print_modref, MemOpA, |
| 269 | MemOpB, M: F.getParent()); |
| 270 | ++ModRefCount; |
| 271 | break; |
| 272 | } |
| 273 | } |
| 274 | } |
| 275 | } |
| 276 | |
| 277 | static void PrintPercent(int64_t Num, int64_t Sum) { |
| 278 | errs() << "(" << Num * 100LL / Sum << "." << ((Num * 1000LL / Sum) % 10) |
| 279 | << "%)\n" ; |
| 280 | } |
| 281 | |
| 282 | AAEvaluator::~AAEvaluator() { |
| 283 | if (FunctionCount == 0) |
| 284 | return; |
| 285 | |
| 286 | int64_t AliasSum = |
| 287 | NoAliasCount + MayAliasCount + PartialAliasCount + MustAliasCount; |
| 288 | errs() << "===== Alias Analysis Evaluator Report =====\n" ; |
| 289 | if (AliasSum == 0) { |
| 290 | errs() << " Alias Analysis Evaluator Summary: No pointers!\n" ; |
| 291 | } else { |
| 292 | errs() << " " << AliasSum << " Total Alias Queries Performed\n" ; |
| 293 | errs() << " " << NoAliasCount << " no alias responses " ; |
| 294 | PrintPercent(Num: NoAliasCount, Sum: AliasSum); |
| 295 | errs() << " " << MayAliasCount << " may alias responses " ; |
| 296 | PrintPercent(Num: MayAliasCount, Sum: AliasSum); |
| 297 | errs() << " " << PartialAliasCount << " partial alias responses " ; |
| 298 | PrintPercent(Num: PartialAliasCount, Sum: AliasSum); |
| 299 | errs() << " " << MustAliasCount << " must alias responses " ; |
| 300 | PrintPercent(Num: MustAliasCount, Sum: AliasSum); |
| 301 | errs() << " Alias Analysis Evaluator Pointer Alias Summary: " |
| 302 | << NoAliasCount * 100 / AliasSum << "%/" |
| 303 | << MayAliasCount * 100 / AliasSum << "%/" |
| 304 | << PartialAliasCount * 100 / AliasSum << "%/" |
| 305 | << MustAliasCount * 100 / AliasSum << "%\n" ; |
| 306 | } |
| 307 | |
| 308 | // Display the summary for mod/ref analysis |
| 309 | int64_t ModRefSum = NoModRefCount + RefCount + ModCount + ModRefCount; |
| 310 | if (ModRefSum == 0) { |
| 311 | errs() << " Alias Analysis Mod/Ref Evaluator Summary: no " |
| 312 | "mod/ref!\n" ; |
| 313 | } else { |
| 314 | errs() << " " << ModRefSum << " Total ModRef Queries Performed\n" ; |
| 315 | errs() << " " << NoModRefCount << " no mod/ref responses " ; |
| 316 | PrintPercent(Num: NoModRefCount, Sum: ModRefSum); |
| 317 | errs() << " " << ModCount << " mod responses " ; |
| 318 | PrintPercent(Num: ModCount, Sum: ModRefSum); |
| 319 | errs() << " " << RefCount << " ref responses " ; |
| 320 | PrintPercent(Num: RefCount, Sum: ModRefSum); |
| 321 | errs() << " " << ModRefCount << " mod & ref responses " ; |
| 322 | PrintPercent(Num: ModRefCount, Sum: ModRefSum); |
| 323 | errs() << " Alias Analysis Evaluator Mod/Ref Summary: " |
| 324 | << NoModRefCount * 100 / ModRefSum << "%/" |
| 325 | << ModCount * 100 / ModRefSum << "%/" << RefCount * 100 / ModRefSum |
| 326 | << "%/" << ModRefCount * 100 / ModRefSum << "%\n" ; |
| 327 | } |
| 328 | } |
| 329 | |