Absolutely! You can absolutely pull off random traversal of llvm::Instructions in an LLVM function—including picking random execution paths through branches. Let’s break down how to do this, depending on exactly what you need:

Option 1: Random Execution Path Traversal (Following Control Flow) #

If you want to simulate random execution paths (i.e., follow branch decisions randomly, just like a program might take different paths at runtime), you’ll work with LLVM’s Control Flow Graph (CFG) and basic blocks. Here’s a step-by-step implementation:

Step 1: Set Up Random Number Generation #

Use a reliable random number generator—either the standard library’s or LLVM’s utilities. We’ll use std::mt19937 for this example:

Step 2: Traverse the CFG with Random Branch Choices #

Start at the function’s entry block, traverse all instructions in the block (in execution order), then randomly pick a successor block when hitting a branch or switch. We’ll also add a guard against infinite loops in cyclic functions.

#include <llvm/IR/Function.h>
#include <llvm/IR/BasicBlock.h>
#include <llvm/IR/Instruction.h>
#include <llvm/IR/TerminatorInst.h>
#include <llvm/IR/BranchInst.h>
#include <llvm/IR/SwitchInst.h>
#include <random>
#include <unordered_set>
#include <vector>

void randomPathTraverse(llvm::Function* func) {
    if (!func || func->empty()) return;

    // Initialize RNG (use a fixed seed if you need reproducible paths)
    std::random_device rd;
    std::mt19937 rng(rd());

    llvm::BasicBlock* currentBlock = &func->getEntryBlock();
    std::unordered_set<llvm::BasicBlock*> visitedBlocks; // Prevent infinite loops

    while (currentBlock && visitedBlocks.find(currentBlock) == visitedBlocks.end()) {
        visitedBlocks.insert(currentBlock);

        // Traverse all instructions in the current block (execution order)
        for (llvm::Instruction& inst : *currentBlock) {
            // Replace this with your logic for handling the instruction
            llvm::errs() << "Visited instruction: " << inst << "\n";
        }

        // Handle the block's terminator (branch/switch/return etc.)
        llvm::TerminatorInst* terminator = currentBlock->getTerminator();
        if (!terminator) break;

        if (llvm::BranchInst* branch = llvm::dyn_cast<llvm::BranchInst>(terminator)) {
            if (branch->isUnconditional()) {
                // Only one path to take
                currentBlock = branch->getSuccessor(0);
            } else {
                // Randomly choose between the two conditional successors
                std::uniform_int_distribution<> branchDist(0, 1);
                currentBlock = branch->getSuccessor(branchDist(rng));
            }
        } else if (llvm::SwitchInst* switchInst = llvm::dyn_cast<llvm::SwitchInst>(terminator)) {
            // Collect all switch destinations (default + cases)
            std::vector<llvm::BasicBlock*> switchDestinations;
            switchDestinations.push_back(switchInst->getDefaultDest());
            for (auto& caseEntry : switchInst->cases()) {
                switchDestinations.push_back(caseEntry.getCaseSuccessor());
            }

            // Pick a random destination
            std::uniform_int_distribution<> switchDist(0, switchDestinations.size() - 1);
            currentBlock = switchDestinations[switchDist(rng)];
        } else {
            // Handle other terminators (return, invoke, etc.) by ending traversal
            break;
        }
    }
}

Note: This follows the natural execution order within each basic block—since that's how instructions would run in a real execution path. If you want to randomize even the order within a block, you could collect the block's instructions into a vector, shuffle it, then traverse.

Option 2: Fully Random Instruction Traversal (Ignoring Control Flow) #

If you don’t care about simulating execution paths and just want to visit all instructions in a random order, the approach is simpler: collect all instructions into a list, shuffle it, then iterate.

#include <llvm/IR/Function.h>
#include <llvm/IR/Instruction.h>
#include <random>
#include <vector>
#include <algorithm>

void randomInstTraverse(llvm::Function* func) {
    if (!func || func->empty()) return;

    // Collect all instructions in the function
    std::vector<llvm::Instruction*> allInstructions;
    for (llvm::BasicBlock& block : *func) {
        for (llvm::Instruction& inst : block) {
            allInstructions.push_back(&inst);
        }
    }

    // Shuffle the list
    std::random_device rd;
    std::mt19937 rng(rd());
    std::shuffle(allInstructions.begin(), allInstructions.end(), rng);

    // Traverse the shuffled instructions
    for (llvm::Instruction* inst : allInstructions) {
        // Your logic here
        llvm::errs() << "Randomly visited instruction: " << *inst << "\n";
    }
}

Key Notes & Edge Cases #

• Reproducibility: If you need the same random path/instruction order every time, replace std::random_device with a fixed seed (e.g., rng.seed(42)).
• Loop Handling: The visitedBlocks set in Option 1 prevents infinite loops in cyclic functions. If you want to allow limited loop iterations, replace it with a std::unordered_map<llvm::BasicBlock*, int> to track visit counts and stop after a threshold.
• Other Terminators: For terminators like InvokeInst (used for exception handling), you can extend the logic to randomly choose between the normal and exception successors, similar to how we handled branches.

内容的提问来源于stack exchange，提问作者Chris Smyth