{"header":{"message":"Import UnitLoopInfo and UnitLICM","description":null,"timestamp":"2024-05-02T23:15:09.105397052Z","authors":[{}]},"hash":"56LYABQH3HNWTV4MWQ2IWW7LEIYKMOW4ZVTRXKOSQID4JTQ5A35AC","authors":[{"key":"8Cqo1QjSCQ3F66Vh3nan9N8dv1MjQSAEz8RNwt2cTacK"}],"deps":{"hashes":[["56LYABQH3HNWTV4MWQ2IWW7LEIYKMOW4ZVTRXKOSQID4JTQ5A35AC","Import UnitLoopInfo and UnitLICM"],["AA",null],["7OVOGA6QKF5OJXOT6VP4Y6GOFI2ZZSBBK3QNK7CPFGN74F7O6HAAC","Import LLVM @ 15.0.7"]],"deps":["7OVOGA6QKF5OJXOT6VP4Y6GOFI2ZZSBBK3QNK7CPFGN74F7O6HAAC"],"known":[]},"hunks":[{"FileAdd":{"meta":{"basename":"UnitLICM.cpp","metadata":0},"context":[{"change":2,"pos":509877339}],"contents":[{"Add":"#include "},{"Add":"#include "},{"Add":"#include "},{"Add":"#include "},{"Add":"#include "},{"Add":"#include "},{"Add":"#include \"llvm/Support/raw_ostream.h\""},{"Add":"#include \"llvm/Support/Debug.h\""},{"Add":"#include \"llvm/Support/Casting.h\""},{"Add":"#include \"llvm/ADT/SmallVector.h\""},{"Add":"#include \"llvm/ADT/DenseMap.h\""},{"Add":"#include \"llvm/ADT/Statistic.h\""},{"Add":"#include \"llvm/IR/Value.h\""},{"Add":"#include \"llvm/IR/Function.h\""},{"Add":"#include \"llvm/IR/Instruction.h\""},{"Add":"#include \"llvm/IR/Instructions.h\""},{"Add":"#include \"llvm/IR/PatternMatch.h\""},{"Add":"#include \"llvm/IR/Dominators.h\""},{"Add":"#include \"llvm/Analysis/AliasAnalysis.h\""},{"Add":"#include \"llvm/Analysis/AliasSetTracker.h\""},{"Add":"#include \"llvm/Analysis/ValueTracking.h\""},{"Add":""},{"Add":"#include \"llvm/Transforms/UnitLICM.h\""},{"Add":"#include \"llvm/Analysis/UnitLoopInfo.h\""},{"Add":""},{"Add":"#define DEBUG_TYPE \"unit-licm\""},{"Add":"STATISTIC(NumInstsHoisted, \"Number of instructions hoisted\");"},{"Add":"STATISTIC(NumStoresHoisted, \"Number of stores hoisted\");"},{"Add":"STATISTIC(NumLoadsHoisted, \"Number of loads hoisted\");"},{"Add":"STATISTIC(NumComputationalHoisted, \"Number of computational instructions (excluding casts and GEPs) hoisted\");"},{"Add":"STATISTIC(NumVisited, \"Number of instructions considered for hoisting\");"},{"Add":""},{"Add":"using namespace llvm;"},{"Add":"using namespace ece479k;"},{"Add":""},{"Add":"/// Since all symbols are exported from the SO, we try to mark all symbols local"},{"Add":"/// to this translation unit to improve diagnostics and improve performance."},{"Add":"/// Likewise, we try to keep functions pure."},{"Add":"///"},{"Add":"/// To reduce confusion when describing LICM, we classify two types of \"invariants\":"},{"Add":"/// - Invariant: a Value that is already invariant to the loop - it is outside the loop or not an Instruction"},{"Add":"/// - Hoistable: a Value that can be hoisted outside the loop to become an invariant"},{"Add":"///"},{"Add":"/// (Un)Hoistable detection is implemented as DFS on every use-def chain in the loop,"},{"Add":"/// stopping if we end up at an invariant or condition that prevents hoisting,"},{"Add":"/// propagating the result back up the chain to every Value visited."},{"Add":"///"},{"Add":"/// This is implemented as a series of tail-recursive calls to check each"},{"Add":"/// instruction for any disqualifying cases or an invariant and then recursively"},{"Add":"/// on each of its operands (the part that makes it a DFS)."},{"Add":"///"},{"Add":"/// Optimization misses are documented in debug output. For meaningful names,"},{"Add":"/// make sure to run the `instnamer` pass before running `unit-licm`."},{"Add":"/// Example output:"},{"Add":"/// UnitLICM: Can't hoist instruction: Depends on unsupported phi `p.0`: %idxprom = sext i32 %p.0 to i64"},{"Add":"/// UnitLICM: Can't hoist instruction: Depends on not-hoistable sext `idxprom`: %arrayidx18 = getelementptr inbounds [8 x [3 x double]], ptr %position, i64 0, i64 %idxprom"},{"Add":"/// UnitLICM: Can't hoist instruction: Depends on not-hoistable getelementptr `arrayidx18`: %arraydecay19 = getelementptr inbounds [3 x double], ptr %arrayidx18, i64 0, i64 0"},{"Add":""},{"Add":"static bool is_supported(Instruction const&) __attribute((pure));"},{"Add":"static bool is_computational(Instruction const&) __attribute((pure));"},{"Add":""},{"Add":"namespace {"},{"Add":" struct HoistArgs {"},{"Add":" UnitLoopInfo const& loop;"},{"Add":" DenseMap cache;"},{"Add":" DominatorTree const& DT;"},{"Add":" };"},{"Add":"}"},{"Add":""},{"Add":"static bool can_hoist(Instruction const&, HoistArgs &) __attribute((pure));"},{"Add":"static void hoist(Instruction&, HoistArgs &);"},{"Add":""},{"Add":"// ReSharper disable once CppMemberFunctionMayBeStatic"},{"Add":"PreservedAnalyses UnitLICM::run(Function &F, FunctionAnalysisManager &FAM) // NOLINT(*-convert-member-functions-to-static)"},{"Add":"{"},{"Add":" for (auto const& loop: FAM.getResult(F)) {"},{"Add":""},{"Add":" auto hoist_args = HoistArgs{"},{"Add":" loop,"},{"Add":" DenseMap(32),"},{"Add":" FAM.getResult(F)"},{"Add":" };"},{"Add":" hoist_args.cache.clear();"},{"Add":""},{"Add":" auto const is_hoistable = [&loop, &hoist_args](Instruction const& inst) {"},{"Add":" return is_supported(inst) && can_hoist(inst, hoist_args);"},{"Add":" };"},{"Add":""},{"Add":" // Hoist everything we can"},{"Add":" for (auto i: loop.instructions(is_hoistable))"},{"Add":" {"},{"Add":" hoist(*i, hoist_args);"},{"Add":""},{"Add":" if (isa(i))"},{"Add":" ++NumLoadsHoisted;"},{"Add":" else if (isa(i))"},{"Add":" ++NumStoresHoisted;"},{"Add":" else if (is_computational(*i))"},{"Add":" ++NumComputationalHoisted;"},{"Add":""},{"Add":" ++NumInstsHoisted;"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" // Invalidate analyses (we fucked the code up)"},{"Add":" return PreservedAnalyses::none();"},{"Add":"}"},{"Add":""},{"Add":"// This switch is inlined instead of chaining isXXX calls because it's easier to see what's going on"},{"Add":"// and we get slightly better codegen (practically it doesn't matter)"},{"Add":"static bool is_supported(Instruction const& inst)"},{"Add":"{"},{"Add":" switch (inst.getOpcode()) {"},{"Add":" default:"},{"Add":" return false;"},{"Add":" // unary operator"},{"Add":" case Instruction::FNeg:"},{"Add":" // binary operator"},{"Add":" case Instruction::Add:"},{"Add":" case Instruction::FAdd:"},{"Add":" case Instruction::Sub:"},{"Add":" case Instruction::FSub:"},{"Add":" case Instruction::Mul:"},{"Add":" case Instruction::FMul:"},{"Add":" case Instruction::UDiv:"},{"Add":" case Instruction::SDiv:"},{"Add":" case Instruction::FDiv:"},{"Add":" case Instruction::URem:"},{"Add":" case Instruction::SRem:"},{"Add":" case Instruction::FRem:"},{"Add":" // logical operator"},{"Add":" case Instruction::Shl:"},{"Add":" case Instruction::LShr:"},{"Add":" case Instruction::AShr:"},{"Add":" case Instruction::And:"},{"Add":" case Instruction::Or:"},{"Add":" case Instruction::Xor:"},{"Add":" // memory operator"},{"Add":" case Instruction::Load:"},{"Add":" case Instruction::Store:"},{"Add":" case Instruction::GetElementPtr:"},{"Add":" // cast operator"},{"Add":" case Instruction::Trunc:"},{"Add":" case Instruction::ZExt:"},{"Add":" case Instruction::SExt:"},{"Add":" case Instruction::FPToUI:"},{"Add":" case Instruction::FPToSI:"},{"Add":" case Instruction::UIToFP:"},{"Add":" case Instruction::SIToFP:"},{"Add":" case Instruction::FPTrunc:"},{"Add":" case Instruction::FPExt:"},{"Add":" case Instruction::PtrToInt:"},{"Add":" case Instruction::IntToPtr:"},{"Add":" case Instruction::BitCast:"},{"Add":" case Instruction::AddrSpaceCast:"},{"Add":" // misc operator"},{"Add":" case Instruction::Select:"},{"Add":" case Instruction::ICmp:"},{"Add":" case Instruction::FCmp:"},{"Add":" return true;"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":""},{"Add":"static bool is_computational(Instruction const& inst)"},{"Add":"{"},{"Add":" switch (inst.getOpcode()) {"},{"Add":" default:"},{"Add":" return false;"},{"Add":" // unary operator"},{"Add":" case Instruction::FNeg:"},{"Add":" // binary operator"},{"Add":" case Instruction::Add:"},{"Add":" case Instruction::FAdd:"},{"Add":" case Instruction::Sub:"},{"Add":" case Instruction::FSub:"},{"Add":" case Instruction::Mul:"},{"Add":" case Instruction::FMul:"},{"Add":" case Instruction::UDiv:"},{"Add":" case Instruction::SDiv:"},{"Add":" case Instruction::FDiv:"},{"Add":" case Instruction::URem:"},{"Add":" case Instruction::SRem:"},{"Add":" case Instruction::FRem:"},{"Add":" // logical operator"},{"Add":" case Instruction::Shl:"},{"Add":" case Instruction::LShr:"},{"Add":" case Instruction::AShr:"},{"Add":" case Instruction::And:"},{"Add":" case Instruction::Or:"},{"Add":" case Instruction::Xor:"},{"Add":" // misc operator"},{"Add":" case Instruction::Select:"},{"Add":" case Instruction::ICmp:"},{"Add":" case Instruction::FCmp:"},{"Add":" return true;"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"static void hoist(Instruction& inst, HoistArgs &args)"},{"Add":"{"},{"Add":" assert(!args.loop.is_invariant(inst) && \"Cannot hoist variant\");"},{"Add":""},{"Add":" auto* insertion_point = const_cast(args.loop.preheader->getTerminator());"},{"Add":" inst.moveBefore(insertion_point);"},{"Add":""},{"Add":" assert(args.loop.is_invariant(inst) && \"Hoist did not make invariant\");"},{"Add":"}"},{"Add":""},{"Add":"// These are called in a tail-recursive (ish) manner"},{"Add":"static bool can_hoist_impl(Instruction const&, HoistArgs &) __attribute((pure));"},{"Add":"static bool can_hoist(Value const&, HoistArgs &) __attribute((pure));"},{"Add":"static bool can_hoist_udiv(Instruction const&, HoistArgs &) __attribute((pure));"},{"Add":"static bool can_hoist_sdiv(Instruction const&, HoistArgs &) __attribute((pure));"},{"Add":"static bool can_hoist_store(Instruction const&, HoistArgs &) __attribute((pure));"},{"Add":"static bool can_hoist_load(Instruction const&, HoistArgs &) __attribute((pure));"},{"Add":"static bool can_hoist_load_impl(Instruction const&, HoistArgs &) __attribute((pure));"},{"Add":"static bool can_hoist_sidefx(Instruction const&, HoistArgs&) __attribute((pure));"},{"Add":"static bool can_hoist_operands(Instruction const&, HoistArgs &) __attribute((pure));"},{"Add":""},{"Add":""},{"Add":"static bool can_hoist(Instruction const& inst, HoistArgs &args)"},{"Add":"{"},{"Add":" if (args.loop.is_invariant(inst))"},{"Add":" return true;"},{"Add":""},{"Add":" if (!is_supported(inst)) {"},{"Add":" LLVM_DEBUG(dbgs() << \"UnitLICM: Can't hoist instruction: Depends on unsupported \" << inst.getOpcodeName() << \" `\" << inst.getName() << \"`: \");"},{"Add":" return false;"},{"Add":" }"},{"Add":""},{"Add":" auto const it = args.cache.find(&inst);"},{"Add":" if (it != args.cache.end()) {"},{"Add":" LLVM_DEBUG(if (!it->second)"},{"Add":" dbgs() << \"UnitLICM: Can't hoist instruction: Depends on not-hoistable \" << inst.getOpcodeName() << \" `\" << inst.getName() << \"`: \");"},{"Add":""},{"Add":" return it->second;"},{"Add":" }"},{"Add":""},{"Add":" bool const dfs = can_hoist_impl(inst, args);"},{"Add":" args.cache.insert({&inst, dfs});"},{"Add":" return dfs;"},{"Add":"}"},{"Add":""},{"Add":"static bool can_hoist(Value const& val, HoistArgs &args)"},{"Add":"{"},{"Add":" if (auto const* inst = dyn_cast(&val))"},{"Add":" return can_hoist(*inst, args);"},{"Add":" return true;"},{"Add":"}"},{"Add":""},{"Add":"/// This is effectively a specialization of isSafeToSpeculativelyExecute for our case:"},{"Add":"/// - We support stores"},{"Add":"/// - We don't bail directly if an instruction has sidefx - we check if it dominates all exits to try and hoist it anyway"},{"Add":"/// - We don't check for instructions we don't support"},{"Add":"///"},{"Add":"/// This will dispatch to special cases for instructions that can have side effects"},{"Add":"/// or cause the use-def chain to be marked as not-hoistable. Otherwise, this"},{"Add":"/// will directly dispatch to the next step of the DFS"},{"Add":"static bool can_hoist_impl(Instruction const& inst, HoistArgs &args)"},{"Add":"{"},{"Add":" assert(is_supported(inst) && \"Instruction is not supported\");"},{"Add":""},{"Add":" ++NumVisited;"},{"Add":""},{"Add":" switch (inst.getOpcode()) {"},{"Add":" default: // Instruction doesn't have edge cases"},{"Add":" return can_hoist_operands(inst, args);"},{"Add":""},{"Add":" case Instruction::Load: // Need to do alias analysis"},{"Add":" return can_hoist_load(inst, args);"},{"Add":""},{"Add":" case Instruction::Store: // This one always has sidefx, and we need to do alias analysis"},{"Add":" return can_hoist_store(inst, args);"},{"Add":""},{"Add":" case Instruction::UDiv:"},{"Add":" case Instruction::URem: // Division by zero can throw"},{"Add":" return can_hoist_udiv(inst, args);"},{"Add":""},{"Add":" case Instruction::SDiv:"},{"Add":" case Instruction::SRem: // Division by zero or of INT_MIN can throw"},{"Add":" return can_hoist_sdiv(inst, args);"},{"Add":""},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"static bool can_hoist_sdiv(Instruction const& inst, HoistArgs &args)"},{"Add":"{"},{"Add":" // code stolen from isSafeToSpeculativelyExecute"},{"Add":" using namespace llvm::PatternMatch;"},{"Add":" // x / y is undefined if y == 0 or x == INT_MIN and y == -1"},{"Add":" const APInt *Numerator, *Denominator;"},{"Add":" if (!match(inst.getOperand(1), m_APInt(Denominator))) {"},{"Add":" // LLVM_DEBUG(dbgs() << \"UnitLICM: Can't hoist \" << inst.getOpcodeName() << \": Undefined denominator \" << inst.getOperand(1) << \":\" << inst << \"\\n\");"},{"Add":" return can_hoist_sidefx(inst, args);"},{"Add":" }"},{"Add":" // We cannot hoist this division if the denominator is 0."},{"Add":" if (*Denominator == 0) {"},{"Add":" // LLVM_DEBUG(dbgs() << \"UnitLICM: Can't hoist \" << inst.getOpcodeName() << \": Division by zero:\" << inst << \"\\n\");"},{"Add":" return can_hoist_sidefx(inst, args);"},{"Add":" }"},{"Add":" // It's safe to hoist if the denominator is not 0 or -1."},{"Add":" if (!Denominator->isAllOnes()) {"},{"Add":" return can_hoist_operands(inst, args);"},{"Add":" }"},{"Add":" // At this point we know that the denominator is -1. It is safe to hoist as"},{"Add":" // long we know that the numerator is not INT_MIN."},{"Add":" if (match(inst.getOperand(0), m_APInt(Numerator))) {"},{"Add":" if (Numerator->isMinSignedValue()) {"},{"Add":" // LLVM_DEBUG(dbgs() << \"UnitLICM: Can't hoist \" << inst.getOpcodeName() << \": Division of INT_MIN by -1:\" << inst << \"\\n\");"},{"Add":" return can_hoist_sidefx(inst, args);"},{"Add":" }"},{"Add":""},{"Add":" return can_hoist_operands(inst, args);"},{"Add":" }"},{"Add":" // The numerator *might* be MinSignedValue."},{"Add":" // LLVM_DEBUG(dbgs() << \"UnitLICM: Can't hoist \" << inst.getOpcodeName() << \": Division of INT_MIN( \" << Numerator << \" ) by -1:\" << inst << \"\\n\");"},{"Add":" return can_hoist_sidefx(inst, args);"},{"Add":"}"},{"Add":""},{"Add":"static bool can_hoist_udiv(Instruction const& inst, HoistArgs &args)"},{"Add":"{"},{"Add":" // code stolen from isSafeToSpeculativelyExecute"},{"Add":" using namespace llvm::PatternMatch;"},{"Add":" // x / y is undefined if y == 0."},{"Add":" const APInt *V;"},{"Add":" if (match(inst.getOperand(1), m_APInt(V))) {"},{"Add":" if (!*V) {"},{"Add":" // LLVM_DEBUG(dbgs() << \"UnitLICM: Can't hoist \" << inst.getOpcodeName() << \": Division by zero:\" << inst << \"\\n\");"},{"Add":" return can_hoist_sidefx(inst, args);"},{"Add":" }"},{"Add":""},{"Add":" return can_hoist_operands(inst, args);"},{"Add":" }"},{"Add":" return false;"},{"Add":"}"},{"Add":""},{"Add":"static bool can_hoist_load(Instruction const& inst, HoistArgs &args)"},{"Add":"{"},{"Add":" // code stolen from isSafeToSpeculativelyExecute"},{"Add":" const auto *LI = dyn_cast(&inst);"},{"Add":" if (!LI) {"},{"Add":" LLVM_DEBUG(dbgs() << \"UnitLICM: Invalid instruction (expected load): \" << inst << \"\\n\");"},{"Add":" return false;"},{"Add":" }"},{"Add":" if (mustSuppressSpeculation(*LI)) {"},{"Add":" LLVM_DEBUG(dbgs() << \"UnitLICM: Can't hoist load: Suppressed by sanitizer:\" << inst << \"\\n\");"},{"Add":" return false;"},{"Add":" }"},{"Add":""},{"Add":" return can_hoist_load_impl(inst, args);"},{"Add":"}"},{"Add":""},{"Add":"static bool can_hoist_load_impl(Instruction const& inst, HoistArgs &args)"},{"Add":"{"},{"Add":" auto const *LI = dyn_cast(&inst);"},{"Add":" if (!LI) {"},{"Add":" LLVM_DEBUG(dbgs() << \"UnitLICM: Invalid instruction (expected load): \" << inst << \"\\n\");"},{"Add":" return false;"},{"Add":" }"},{"Add":""},{"Add":" auto const& aa = args.loop.alias_for(LI);"},{"Add":""},{"Add":" // If the load always reads the same mem loc, we can hoist it"},{"Add":""},{"Add":" if (aa.isMod()) {"},{"Add":" LLVM_DEBUG(dbgs() << \"UnitLICM: Can't hoist load: Load aliases modified memory:\" << inst << \"\\n\");"},{"Add":" return false;"},{"Add":" }"},{"Add":""},{"Add":" return can_hoist_operands(inst, args);"},{"Add":"}"},{"Add":""},{"Add":"static bool can_hoist_store(Instruction const& inst, HoistArgs &args)"},{"Add":"{"},{"Add":" auto const *SI = dyn_cast(&inst);"},{"Add":" if (!SI) {"},{"Add":" LLVM_DEBUG(dbgs() << \"UnitLICM: Invalid instruction (expected store):\\t\" << inst << \"\\n\");"},{"Add":" return false;"},{"Add":" }"},{"Add":""},{"Add":" // Volatile stores may not return, so we can't hoist them"},{"Add":" if (SI->isVolatile())"},{"Add":" return false;"},{"Add":""},{"Add":" auto const& aa = args.loop.alias_for(SI);"},{"Add":""},{"Add":" // If the store always modifies the same mem loc and it is never read, we can hoist it"},{"Add":""},{"Add":" if (!aa.isMustAlias()) {"},{"Add":" LLVM_DEBUG(dbgs() << \"UnitLICM: Can't hoist store: Store does not always write the same memory:\" << inst << \"\\n\");"},{"Add":" return false;"},{"Add":" }"},{"Add":""},{"Add":" if (aa.isRef()) {"},{"Add":" LLVM_DEBUG(dbgs() << \"UnitLICM: Can't hoist store: Store aliases read memory:\" << inst << \"\\n\");"},{"Add":" return false;"},{"Add":" }"},{"Add":""},{"Add":" // Writing to memory is side-effectful"},{"Add":" return can_hoist_sidefx(inst, args);"},{"Add":"}"},{"Add":""},{"Add":"/// We can only host expressions with side effects if they dominate all exits."},{"Add":"static bool can_hoist_sidefx(Instruction const& inst, HoistArgs& args)"},{"Add":"{"},{"Add":" if (!all_of(args.loop.exits, [&args, &inst](BasicBlock const* exit) {"},{"Add":" return args.DT.dominates(&inst, exit);"},{"Add":" })) {"},{"Add":" LLVM_DEBUG(dbgs() << \"UnitLICM: Can't hoist inst w/ sidefx: Does not dominate all exits:\" << inst << \"\\n\");"},{"Add":" return false;"},{"Add":" }"},{"Add":""},{"Add":" return can_hoist_operands(inst, args);"},{"Add":"}"},{"Add":""},{"Add":"static bool can_hoist_operands(Instruction const& inst, HoistArgs &args)"},{"Add":"{"},{"Add":" return std::ranges::all_of(inst.operands(), [&args, &inst](Use const& V) {"},{"Add":" bool const r = can_hoist(*V.get(), args);"},{"Add":" LLVM_DEBUG(if (!r) dbgs() << inst << \"\\n\");"},{"Add":" return r;"},{"Add":" });"},{"Add":"}"},{"Add":""},{"Add":""}]}},{"Edit":{"inode":{"change":2,"pos":513306586},"path":"llvm/lib/Transforms/Scalar/CMakeLists.txt","line":80,"atom":{"NewVertex":{"up_context":[{"change":2,"pos":513308338}],"down_context":[{"change":2,"pos":513308338}],"flag":"BLOCK","start":77654,"end":77669,"inode":{"change":2,"pos":513306586}}},"contents":[{"Add":" UnitLICM.cpp"}]}},{"FileAdd":{"meta":{"basename":"UnitLoopInfo.cpp","metadata":0},"context":[{"change":2,"pos":602795540}],"contents":[{"Add":"#include "},{"Add":"#include "},{"Add":"#include "},{"Add":"#include "},{"Add":"#include "},{"Add":"#include \"llvm/Support/raw_ostream.h\""},{"Add":"#include \"llvm/Support/Debug.h\""},{"Add":"#include \"llvm/Support/Casting.h\""},{"Add":"#include \"llvm/ADT/Statistic.h\""},{"Add":"#include \"llvm/ADT/SmallVector.h\""},{"Add":"#include \"llvm/IR/Value.h\""},{"Add":"#include \"llvm/IR/User.h\""},{"Add":"#include \"llvm/IR/Function.h\""},{"Add":"#include \"llvm/IR/Instruction.h\""},{"Add":"#include \"llvm/IR/Instructions.h\""},{"Add":"#include \"llvm/IR/Dominators.h\""},{"Add":"#include \"llvm/Analysis/AliasAnalysis.h\""},{"Add":"#include \"llvm/Analysis/AliasSetTracker.h\""},{"Add":""},{"Add":"#include \"llvm/Analysis/UnitLoopInfo.h\""},{"Add":""},{"Add":"#define DEBUG_TYPE \"unit-loop\""},{"Add":"STATISTIC(NumLoopsDetected, \"Number of loops detected\");"},{"Add":""},{"Add":"using namespace llvm;"},{"Add":"using namespace ece479k;"},{"Add":""},{"Add":"// Need to do this conversion because predecessors doesn't satisfy forward-iterator"},{"Add":"// so we can use it in a filter view"},{"Add":"static auto preds(BasicBlock const* block)"},{"Add":"{"},{"Add":" SmallVector r;"},{"Add":""},{"Add":" auto const p = predecessors(block);"},{"Add":" r.append(p.begin(), p.end());"},{"Add":""},{"Add":" return r;"},{"Add":"}"},{"Add":""},{"Add":"#pragma region \"UnitLoopAnalysis\""},{"Add":"/// Main function for running the Loop Identification analysis. This function"},{"Add":"/// returns information about the loops in the function via the UnitLoopInfo"},{"Add":"/// object"},{"Add":"UnitLoopAnalysis::Result UnitLoopAnalysis::run(Function &F, FunctionAnalysisManager &FAM)"},{"Add":"{"},{"Add":" auto &DT = FAM.getResult(F);"},{"Add":" auto &AA = FAM.getResult(F);"},{"Add":""},{"Add":" Result Loops;"},{"Add":" // Need to have this ugliness to support both LLVM 15 and LLVM 16-19"},{"Add":" #if LLVM_VERSION_MAJOR > 15"},{"Add":" UnitLoopInfo::alias_results alias = BatchAAResults(AA);"},{"Add":" #else"},{"Add":" UnitLoopInfo::alias_results alias = AA;"},{"Add":" #endif"},{"Add":""},{"Add":" auto const is_reachable = [&DT](BasicBlock const& bb) {"},{"Add":" return DT.isReachableFromEntry(&bb);"},{"Add":" };"},{"Add":""},{"Add":" // Find all back-edges in F"},{"Add":" for (BasicBlock& BB: F | std::views::filter(is_reachable)) {"},{"Add":""},{"Add":" // ReSharper disable once CppDeclarationHidesLocal"},{"Add":" auto const is_reachable = [&DT](BasicBlock const* bb) {"},{"Add":" return DT.isReachableFromEntry(bb);"},{"Add":" };"},{"Add":""},{"Add":" auto const is_backedge = [&DT, &BB](BasicBlock const* bb) {"},{"Add":" return DT.dominates(&BB, bb);"},{"Add":" };"},{"Add":""},{"Add":" // We need to filter out unreachble blocks twice because it's possible"},{"Add":" // for an unreachble block to be the predecessor of a reachable block."},{"Add":" // See bad_loop1.ll for canonical case of this."},{"Add":""},{"Add":" for (BasicBlock const* P: preds(&BB)"},{"Add":" | std::views::filter(is_reachable)"},{"Add":" | std::views::filter(is_backedge))"},{"Add":" {"},{"Add":" LLVM_DEBUG(dbgs()"},{"Add":" << \"UnitLoopAnalysis: Found loop in \" << F.getName() << \" from `\""},{"Add":" << BB.getName() << \"` to `\" << P->getName() << \"`\");"},{"Add":" Loops.emplace_back(&BB, const_cast(P), alias, DT);"},{"Add":" ++NumLoopsDetected;"},{"Add":" }"},{"Add":" }"},{"Add":" return Loops;"},{"Add":"}"},{"Add":""},{"Add":"AnalysisKey UnitLoopAnalysis::Key;"},{"Add":"#pragma endregion"},{"Add":""},{"Add":"#pragma region \"UnitLoopInfo\""},{"Add":"static BasicBlock* get_preheader(BasicBlock* header, BasicBlock* end)"},{"Add":"{"},{"Add":" BasicBlock* preheader;"},{"Add":" // LoopSimplify guarantees 1 preheader and 1 backedge"},{"Add":" // hence the preds of hedaer are [preheader, end]"},{"Add":" assert(header->hasNPredecessors(2) && \"Loop header preds were not [preheader, backedge]\");"},{"Add":""},{"Add":" for (auto* pred : predecessors(header))"},{"Add":" if (pred != end)"},{"Add":" preheader = pred;"},{"Add":""},{"Add":" assert(preheader && \"Preheader not found\");"},{"Add":" assert(preheader->isLegalToHoistInto() && \"Preheader is not hoistable\");"},{"Add":" assert(preheader->getSingleSuccessor() == header && \"Preheader is invalid\");"},{"Add":""},{"Add":" return preheader;"},{"Add":"}"},{"Add":""},{"Add":"UnitLoopInfo::UnitLoopInfo(BasicBlock* header, BasicBlock* end, alias_results AA, DominatorTree& DT)"},{"Add":" :header(header), preheader(get_preheader(header, end)), alias_sets(std::make_unique(AA))"},{"Add":"{"},{"Add":" assert(header && \"Can't record a loop that starts from a non-existent BasicBlock\");"},{"Add":" assert(end && \"Can't record a loop that ends with a non-existent BasicBlock\");"},{"Add":" assert(preheader && \"Loop does not have a valid preheader\");"},{"Add":""},{"Add":" SmallVector worklist;"},{"Add":" worklist.emplace_back(end);"},{"Add":""},{"Add":" // Populate loop body by walking up from the end to the header"},{"Add":" while (!worklist.empty()) {"},{"Add":" BasicBlock* cur = worklist.back(); worklist.pop_back();"},{"Add":""},{"Add":" // Make sure that we don't add the preds of the header"},{"Add":" if (cur == header) {"},{"Add":" set.insert(header);"},{"Add":" blocks.emplace_back(header);"},{"Add":" break;"},{"Add":" }"},{"Add":""},{"Add":" if (set.insert(cur).second) {"},{"Add":" blocks.emplace_back(cur);"},{"Add":" auto preds = predecessors(cur);"},{"Add":" worklist.append(preds.begin(), preds.end());"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" assert(!set.empty() && \"Loops must contain at least one BasicBlock\");"},{"Add":" assert(blocks.back() == header && \"Loop must start at the header\");"},{"Add":" assert(blocks.front() == end && \"Loop must end at the end\");"},{"Add":""},{"Add":" for (BasicBlock* block: blocks) {"},{"Add":" assert(DT.dominates(preheader, block) && \"All blocks in the loop must be dominated by the preheader\");"},{"Add":" assert(DT.dominates(header, block) && \"All blocks in the loop must be dominated by the header\");"},{"Add":" }"},{"Add":""},{"Add":" // Populate AliasSets for this loop"},{"Add":" for (BasicBlock* block: blocks | std::views::reverse)"},{"Add":" alias_sets->add(*block);"},{"Add":""},{"Add":" // Populate the loop exits"},{"Add":" for (BasicBlock* block : blocks)"},{"Add":" // if any of the successors of a block point outside the loop, it is an exit from the loop"},{"Add":" if (any_of(successors(block), [end, this](BasicBlock const* bb) {"},{"Add":" return !this->contains(bb);"},{"Add":" }))"},{"Add":" exits.insert(block);"},{"Add":""},{"Add":" LLVM_DEBUG("},{"Add":" dbgs() << \" with preheader `\" << preheader->getName()"},{"Add":" << \"`, header `\" << header->getName()"},{"Add":" << \"`, exits [ \";"},{"Add":" for (BasicBlock const* exit: exits)"},{"Add":" dbgs() << \"`\" << exit->getName() << \"` \";"},{"Add":""},{"Add":" dbgs() << \"]\\n\";"},{"Add":" );"},{"Add":"}"},{"Add":""},{"Add":""},{"Add":"bool UnitLoopInfo::contains(BasicBlock const *BB) const"},{"Add":"{"},{"Add":" assert(!set.empty() && \"Can't check an empty loop\");"},{"Add":" // assert(BB && \"Can't look-up a non-existent BasicBlock\");"},{"Add":" return set.contains(BB);"},{"Add":"}"},{"Add":""},{"Add":"bool UnitLoopInfo::contains(Instruction const *I) const"},{"Add":"{"},{"Add":" assert(!set.empty() && \"Can't check an empty loop\");"},{"Add":" // assert(I && \"Can't look-up a non-existent Instruction\");"},{"Add":" return contains(I->getParent());"},{"Add":"}"},{"Add":""},{"Add":"bool UnitLoopInfo::contains(Instruction const& I) const"},{"Add":"{"},{"Add":" assert(!set.empty() && \"Can't check an empty loop\");"},{"Add":" // assert(I && \"Can't look-up a non-existent Instruction\");"},{"Add":" return contains(I.getParent());"},{"Add":"}"},{"Add":""},{"Add":"bool UnitLoopInfo::is_invariant(Value const *V) const"},{"Add":"{"},{"Add":" assert(!set.empty() && \"Can't be invariant to an empty loop\");"},{"Add":" if (auto const* i = dyn_cast(V))"},{"Add":" return !contains(i);"},{"Add":" return true; "},{"Add":"}"},{"Add":""},{"Add":"bool UnitLoopInfo::is_invariant(Instruction const *I) const"},{"Add":"{"},{"Add":" assert(!set.empty() && \"Can't be invariant to an empty loop\");"},{"Add":" return !contains(I);"},{"Add":"}"},{"Add":""},{"Add":"bool UnitLoopInfo::is_invariant(Instruction const& I) const"},{"Add":"{"},{"Add":" assert(!set.empty() && \"Can't be invariant to an empty loop\");"},{"Add":" return !contains(I);"},{"Add":"}"},{"Add":""},{"Add":"bool UnitLoopInfo::has_invariant_operands(Instruction const *I) const"},{"Add":"{"},{"Add":" assert(!set.empty() && \"Can't be invariant to an empty loop\");"},{"Add":" return std::ranges::all_of(I->operands(), [this](Value *v){ return is_invariant(v); });"},{"Add":"}"},{"Add":""},{"Add":"std::vector UnitLoopInfo::instructions() const"},{"Add":"{"},{"Add":" std::vector r;"},{"Add":""},{"Add":" for (BasicBlock* block : blocks | std::views::reverse)"},{"Add":" for (Instruction& inst: *block)"},{"Add":" r.emplace_back(&inst);"},{"Add":""},{"Add":" return r;"},{"Add":"}"},{"Add":""},{"Add":"std::vector UnitLoopInfo::instructions(std::function const& filter) const"},{"Add":"{"},{"Add":" std::vector r;"},{"Add":""},{"Add":" for (BasicBlock* block : blocks | std::views::reverse)"},{"Add":" for (Instruction& inst: *block | std::views::filter(filter))"},{"Add":" r.emplace_back(&inst);"},{"Add":""},{"Add":" return r;"},{"Add":"}"},{"Add":""},{"Add":"AliasSet const& UnitLoopInfo::alias_for(LoadInst const* inst) const"},{"Add":"{"},{"Add":" return alias_sets->getAliasSetFor(MemoryLocation::get(inst));"},{"Add":"}"},{"Add":""},{"Add":"AliasSet const& UnitLoopInfo::alias_for(StoreInst const* inst) const"},{"Add":"{"},{"Add":" return alias_sets->getAliasSetFor(MemoryLocation::get(inst));"},{"Add":"}"},{"Add":"#pragma endregion"}]}},{"Edit":{"inode":{"change":2,"pos":606168938},"path":"llvm/lib/Analysis/CMakeLists.txt","line":138,"atom":{"NewVertex":{"up_context":[{"change":2,"pos":606172191}],"down_context":[{"change":2,"pos":606172191}],"flag":"BLOCK","start":81695,"end":81714,"inode":{"change":2,"pos":606168938}}},"contents":[{"Add":" UnitLoopInfo.cpp"}]}},{"FileAdd":{"meta":{"basename":"UnitLICM.h","metadata":0},"context":[{"change":2,"pos":607628340}],"contents":[{"Add":"#ifndef INCLUDE_UNIT_LICM_H"},{"Add":"#define INCLUDE_UNIT_LICM_H"},{"Add":""},{"Add":"#include \"llvm/IR/PassManager.h\""},{"Add":""},{"Add":"namespace llvm {"},{"Add":" class Function;"},{"Add":"}"},{"Add":""},{"Add":"using namespace llvm;"},{"Add":""},{"Add":"namespace ece479k"},{"Add":"{"},{"Add":"/// Loop Invariant Code Motion Optimization Pass"},{"Add":"///"},{"Add":"/// Implements the relaxed-case:"},{"Add":"/// - We move pure expressions even if they don't dominate all exits"},{"Add":"/// - We move expressions with side effects if they dominate all exits"},{"Add":"struct UnitLICM : PassInfoMixin {"},{"Add":" PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM);"},{"Add":"};"},{"Add":"} // namespace"},{"Add":""},{"Add":"#endif // INCLUDE_UNIT_LICM_H"}]}},{"FileAdd":{"meta":{"basename":"UnitLoopInfo.h","metadata":0},"context":[{"change":2,"pos":622017596}],"contents":[{"Add":"#ifndef INCLUDE_UNIT_LOOP_INFO_H"},{"Add":"#define INCLUDE_UNIT_LOOP_INFO_H"},{"Add":""},{"Add":"#include "},{"Add":"#include "},{"Add":"#include \"llvm/IR/PassManager.h\""},{"Add":"#include \"llvm/ADT/SmallVector.h\""},{"Add":"#include \"llvm/ADT/SmallPtrSet.h\""},{"Add":"#include \"llvm/Analysis/AliasAnalysis.h\""},{"Add":"#include \"llvm/Analysis/AliasSetTracker.h\""},{"Add":""},{"Add":""},{"Add":"namespace llvm {"},{"Add":" class Value;"},{"Add":" class Instruction;"},{"Add":" class BasicBlock;"},{"Add":" class DominatorTree;"},{"Add":" class LoadInst;"},{"Add":" class StoreInst;"},{"Add":"}"},{"Add":""},{"Add":"using namespace llvm;"},{"Add":""},{"Add":"namespace ece479k {"},{"Add":""},{"Add":"struct UnitLoopInfo {"},{"Add":"private:"},{"Add":" // The basic blocks that form this loop"},{"Add":" SmallPtrSet set;"},{"Add":" // The blocks in *reverse* order"},{"Add":" SmallVector blocks;"},{"Add":"public:"},{"Add":" BasicBlock const* header;"},{"Add":" BasicBlock const* preheader;"},{"Add":" SmallPtrSet exits;"},{"Add":"private:"},{"Add":" std::unique_ptr alias_sets;"},{"Add":"public:"},{"Add":" using alias_results = AAResults&;"},{"Add":""},{"Add":" // Record a natural loop given its backedge from end to header"},{"Add":" UnitLoopInfo(BasicBlock* header, BasicBlock* end, alias_results AA, DominatorTree& DT);"},{"Add":""},{"Add":" /*loop properties*/"},{"Add":" [[nodiscard]] bool contains(BasicBlock const*) const;"},{"Add":" [[nodiscard]] bool contains(BasicBlock const&) const;"},{"Add":" [[nodiscard]] bool contains(Instruction const*) const;"},{"Add":" [[nodiscard]] bool contains(Instruction const&) const;"},{"Add":" [[nodiscard]] bool contains(Value const*) const;"},{"Add":" [[nodiscard]] bool contains(Value const&) const;"},{"Add":""},{"Add":" /*loop invariants*/"},{"Add":" [[nodiscard]] bool is_invariant(Value const*) const;"},{"Add":" [[nodiscard]] bool is_invariant(Value const&) const;"},{"Add":" [[nodiscard]] bool is_invariant(Instruction const*) const;"},{"Add":" [[nodiscard]] bool is_invariant(Instruction const&) const;"},{"Add":" [[nodiscard]] bool has_invariant_operands(Instruction const*) const;"},{"Add":" [[nodiscard]] bool has_invariant_operands(Instruction const&) const;"},{"Add":""},{"Add":" /*utility*/"},{"Add":" [[nodiscard]] std::vector instructions() const;"},{"Add":" [[nodiscard]] std::vector instructions(std::function const&) const;"},{"Add":" [[nodiscard]] AliasSet const& alias_for(LoadInst const*) const;"},{"Add":" [[nodiscard]] AliasSet const& alias_for(StoreInst const*) const;"},{"Add":"};"},{"Add":""},{"Add":"/// Loop Identification Analysis Pass. Produces a UnitLoopInfo object which"},{"Add":"/// should contain any information about the loops in the function which is"},{"Add":"/// needed for your implementation of LICM"},{"Add":"class UnitLoopAnalysis : public AnalysisInfoMixin {"},{"Add":" friend AnalysisInfoMixin;"},{"Add":" static AnalysisKey Key;"},{"Add":""},{"Add":"public:"},{"Add":" using Result = std::vector;"},{"Add":""},{"Add":" Result run(Function &F, FunctionAnalysisManager &AM);"},{"Add":"};"},{"Add":""},{"Add":"} // namespace ece479k"},{"Add":"#endif // INCLUDE_UNIT_LOOP_INFO_H"}]}}],"owner":"nuudlman","repo":"llvm","token":"BlnRrjgSyl9mcyZ252LHoJdBAbmShslIG52UQHu6RK4=","login":null}

…

Dependencies

Change contents