Skip to content
Snippets Groups Projects
  1. Mar 31, 2017
    • Alessandro Di Federico's avatar
      SET: use the appropriate type while materializing · 6d9b0c43
      Alessandro Di Federico authored
      While materializing values in SET through the `OperationStack` we used
      to use as a type the type of the value associate to the currently used
      `BoundedValue`. This was wrong, this patch uses the type on the free
      operand on the top of the `OperationsStack` to perform the required
      computations.
      6d9b0c43
    • Alessandro Di Federico's avatar
      Detect `try`/`catch` landing pads · d8f13c79
      Alessandro Di Federico authored
      Landing pads are basically the `catch` blocks in C++ `try`/`catch`
      statements. So far we were missing them since they are encoded in a
      particular way in a way similar to DWARF debugging information in the
      `.eh_frame` and, more specifically, in the `.gcc_except_table` sections
      of ELF programs.
      
      This commit parses these sections so that the basic blocks associated to
      landing pads are correctly identified. Personality functions are
      detected too. A test is also introduced to assess the effectiveness of
      our code.
      d8f13c79
    • Alessandro Di Federico's avatar
      c81dd323
  2. Mar 29, 2017
  3. Mar 23, 2017
    • Alessandro Di Federico's avatar
      Rewrite `OSRA::handleComparison` · 66ef40f9
      Alessandro Di Federico authored
      `OSRA:handleComparison` was too big and complex, it has been mostly
      rewritten.
      
      * Create `OSRA::identifyComparisonOperands` which expands the argument
        of the comparison in a list of possible values (constants or
        OSRs). The new way in which we handle possible operands also fixes a
        bug showing up in case a constant OSR was being compared with an LLVM
        constant, which was checked for being a tautology/contradiction,
        preventing the reaching definitions of the operand to be considered
        too.
      * Squeeze more information from uge/ugt. Unsigned comparisons lead to
        two pieces information: the result of the comparison itself, and the
        fact the left-hand side is greather than or equal 0. This secondo
        information is precious, but we were not able to exploit it in the
        case the original comparison is already "greater than" or "greater
        than or equal". In fact, `x - 4 > 10` gives us `x >= 4` and `x > 14`,
        which boils down to `x > 14`.  This commit introduces a change that
        handles this case as `NOT x - 4 <= 10` leading to the negation of `x
        >= 4` and `x < 14` which is way more informative.
      * Improve `OSRA::mergePredicate` and `OSRA::applyConstraints`
        interfaces.
      * In case a comparison instructions leads to multiple constraints on the
        same `Value`, these constraints are now first or-merged together and
        then propagated. This change improves the quality of the analysis in
        certain situations.
      66ef40f9
    • Alessandro Di Federico's avatar
      `BoundedValue`: support for multiple ranges · 5b8fb1af
      Alessandro Di Federico authored
      This commit introduces radically changes the implementation of
      `BoundedValue`: it no longer represents a single, contiguous range, but
      an arbitrary number of ranges.
      
      The bounds are now represented through a
      `llvm::SmallVector<std::pair<uint64_t, uint64_t>, 3>`.
      
      * Introduce the `BoundedValue::bounds()` method, which allows to iterate
        over all the ranges that a `BoundedValue` represents. The `bounds`
        method returns a `Bounds` object, which can be used as a range
        composed by `BoundsIterator`.
      * All the methods dealing with the `BoundedValue`'s bounds have been
        rewritten.
      * New debugging information: "bv-merge". Print all the computations
        performed by `BoundedValue::mergeImpl`.
      * Drop dead code: `BoundedValue::setBound` and `isPositive`
      * Introduce `BoundedValue::isRightOpen` and drop
        `BoundedValue::isSingleRange`
      5b8fb1af
    • Alessandro Di Federico's avatar
      Improve `OSRA::pathSensitiveMerge` · 4089c203
      Alessandro Di Federico authored
      Some subtle bugs have been fixed in `OSRA::pathSensitiveMerge`:
      
      * Do not alter the current `BoundedValue` if merging a component would
        lead to bottom.
      * Do not deactivate a reacher in case an incoherent condition is met.
      4089c203
    • Alessandro Di Federico's avatar
      `ReachingDefinitionsPass`: free loads are definers · 1d967349
      Alessandro Di Federico authored
      In our reaching definition analysis we used to consider all the loads
      not reached by any store as definitions. However we forgot to actually
      register them as such, with the result that two consecutive loads from
      the same CSV would end up being two free loads.
      1d967349
    • Alessandro Di Federico's avatar
      `ConditionNumberingPass`: last user, still user · 244f0dc9
      Alessandro Di Federico authored
      In `ConditionNumberingPass` we used to consider as resetting the last
      basic block possibly interested in a certain numbered
      condition. However, what we really meant, was that its successors were
      resetting basic blocks. This commit fixes this issue.
      244f0dc9
    • Alessandro Di Federico's avatar
      `OSR::constant()`: consider `Base` and `Factor` · f409fd65
      Alessandro Di Federico authored
      `OSR::constant()` used to forward the result of
      `BoundedValue::constant()`, but this is wrong, since the factor and the
      base value have to be considered too.
      f409fd65
    • Alessandro Di Federico's avatar
      OSRA: x | bottom = x, not bottom · bddc0d03
      Alessandro Di Federico authored
      or-merging bottom with anything used to produce a bottom value, which is
      wrong. The non-bottom value should be produced instead.
      bddc0d03
    • Alessandro Di Federico's avatar
      Propagated constraints should be and-merged · 0f70a6ef
      Alessandro Di Federico authored
      Constraints associated to a memory instruction are propagated to
      reached loads. However, if a constraint on the same `Value` is already
      present, the new constraint should be and-merged, not or-merged.
      0f70a6ef
    • Alessandro Di Federico's avatar
    • Alessandro Di Federico's avatar
      Minor improvements · 8bb3a382
      Alessandro Di Federico authored
      * Introduce some additional helpers
      * Spread some `const`ness
      * Improve documentation
      * New debugging information: "osr-bv". Prints every update operation
        performed in `BVMap::update`.
      * Remove dead code
      * Whitespace fixes
      * Some new TODOs
      * Fix some typos in comments
      8bb3a382
  4. Mar 10, 2017
    • Alessandro Di Federico's avatar
      Switch `BoundedValue::merge` to `boost:icl` · 850fc09a
      Alessandro Di Federico authored
      This commit drops the original handcrafted implementation of
      `BoundedValue` merging, in favor of an implementation based on Boost
      intervals. The old implementation was the source of intermittend bugs,
      using Boost should be a more reliable solution. Moreover, this commit
      enables moves us towards supporting multiple ranges in `BoundedValues`.
      850fc09a
  5. Mar 09, 2017
  6. Mar 08, 2017
    • Alessandro Di Federico's avatar
      OSRA: track register+constant pointers too · b21f3b18
      Alessandro Di Federico authored
      In OSRA we used to track `GlobalVariable`s and `AllocaInst` only,
      despite the `MemoryAccess` infrastructure supported memory accesses of
      the type register + constant. Enabling this, we're able to handle the
      following x86-64 snippet found in the `omnetpp` SPEC benchmark:
      
          cmp    DWORD PTR [rbx+0x8],0x5
          ja     elsewhere
          mov    eax,DWORD PTR [rbx+0x8]
      b21f3b18
  7. Mar 06, 2017
    • Alessandro Di Federico's avatar
      Improve handling of load insturctions in SET · 14f4cd74
      Alessandro Di Federico authored
      SET, when getting data from OSRA, used to check that the first and last
      materialized address were within a certain range, under the assumption
      that the last value would be greater that the first one. Turns out that
      this is not always the case when in the operation stack we have a load
      instruction. This commit improve the way such a situation is handled.
      14f4cd74
    • Alessandro Di Federico's avatar
      Purge translated code in post-order · d398213a
      Alessandro Di Federico authored
      This commit changes the way instruction and basic block are purged when
      re-translation is necessary. Specifically, the purge is now performed
      through a post-order visit, which should prevent the removal of any
      instructions still holding users.
      
      This commit also introduces the `SubGraph` class, which is useful to be
      able to navigate portions of a graph (e.g., a `Function`) in post-order
      easily.
      d398213a
    • Alessandro Di Federico's avatar
      Reorganize OSRA · 87dc88c2
      Alessandro Di Federico authored
      The main goal of this patch is to reduce the size of
      `OSRAPass::runOnFunction()`. To do this we created the `OSRA` class
      which handles everything `runOnFunction` was taking care of but without
      the ugly lambdas nor being an endless function. Each class of
      instruction is now handled by a dedicated function.
      
      This also has the side effect of heavily reducing the amount of clutter
      exposed by `OSRAPass` to its users.
      87dc88c2
  8. Mar 02, 2017
    • Alessandro Di Federico's avatar
      Anticipate `cpu_loop_exit` removal · 1e9163c7
      Alessandro Di Federico authored
      Fix of another bug showing up only with LLVM in debug mode: splitting a
      malformed basic block is not allowed, and we had a function call after a
      `ret` instruction.
      1e9163c7
    • Alessandro Di Federico's avatar
      When splitting a basic block, retranslate · 04a4591f
      Alessandro Di Federico authored
      This commit should fix some bugs due to the fact that when we're
      splitting a basic block we don't retranslate the basic block at the
      split point but preserve the existing code. This lead to problems, in
      particular in x86-64 where certain QEMU local variables were not
      available. This change should fix it.
      
      Basically, every time we split a basic block in
      `JumpTargetManager::registerJT` we note down that the new basic block
      must be purged, and in `JumpTargetManager::harvest` we perform the
      purge. `harvest` has been chosen since it's a particularly quiet moment,
      i.e., there should be no pending references/iterator to code we have to
      delete.
      04a4591f
    • Alessandro Di Federico's avatar
      Fix deletion order of temporary parts in RDA · 7babafac
      Alessandro Di Federico authored
      This commit fixes a bug that appears only with debug builds of LLVM: in
      RDA we were erasing a temporary common predecessor basic block before
      removing the references to it in a `switch` statement.
      7babafac
    • Alessandro Di Federico's avatar
      Dismiss basic block statistics collection · d6b257dd
      Alessandro Di Federico authored
      If we need this again, we can do it in revamb-dump.
      d6b257dd
    • Alessandro Di Federico's avatar
      OSRA: ignore unknown signedness in comparisons · f8c7ebab
      Alessandro Di Federico authored
      When performing a comparison, we try to attach its signedness to the
      base OSR it's working on. However, this is not always
      effective. Typically, even after this, the OSR remains with an unknown
      signedness due to the fact that we don't have information about its
      bounded value from all the predecessors, and therefore it goes to top.
      f8c7ebab
    • Alessandro Di Federico's avatar
      Reorganize the tracing system · 4789524a
      Alessandro Di Federico authored
      `support.c` used to have a basic tracing system which would print on `stderr`
      all the program counters. This commit reorganizes this system so that it has a
      buffer, whose size can be specified through the `REVAMB_TRACE_BUFFER_SIZE`
      environment variable, and it's possible to specify the output file
      `REVAMB_TRACE_PATH`. The new tracing system also supports flushing the buffers
      in case of clean exit of crash.
      
      We also cleaned up `support.c`.
      4789524a
    • Alessandro Di Federico's avatar
      Compile `support.c` to LLVM IR · dae2f7e6
      Alessandro Di Federico authored
      `support.c` used to be compiled using the system compiler and then
      linked to the module generated by `revamb` as a separate translation
      unit. This commit introduces a change that lets `clang` compile
      `support.c`. This will allow us to make the CSV static, which should
      enable more aggressive optimizations.
      
      * Change the signature of the `root` function so that it accepts an
        argument: the initial value of the stack pointer, which the main is
        supposed to set up. QEMU now provides us with the offset of the stack
        pointer.
      * Let the build system compile `support.c` for each supported
        architecture, both in normal and "tracing" mode.
      * Remove the `--tracing` option, this is now handled by `support.c`, in
        particular depending on which version of `support.c` you link, you can
        have tracing enabled or not.
      * In `support.c` drop global variables representing the stack pointer,
        we no longer need them.
      * In `support.c` fix some warnings while handling the stack on 32-bit
        architectures.
      * Extende the `translate` script to handle the new way we link the final
        binary and the tracing mechanism.
      dae2f7e6
  9. Feb 20, 2017
  10. Jan 23, 2017
    • Alessandro Di Federico's avatar
      Handle calls with multiple successors · 3b89c5f3
      Alessandro Di Federico authored
      This commit handles the situation where we have a function call with
      more than one successor. This might be the case if there's an indirect
      call but we're able to enumerate the possible targets statically.
      
      This commit simply avoids an assertion, in the future we will register
      all the possible destinations in the `function_call` marker.
      3b89c5f3
    • Alessandro Di Federico's avatar
      Function detection: drop normalized address space · c3fbcf31
      Alessandro Di Federico authored
      We used to have a normalized address space formed only functions,
      skipping all the holes. This was employed to identify "skipping
      jumps". However, this method was ineffective, and we changed the
      definition of skipping jump as a jump skipping over CFEPs that are
      highly likely to be actual functions.
      
      This commit removes the leftovers of the normalized address space
      computation, which was also the cause of a bug in function detection.
      c3fbcf31
    • Alessandro Di Federico's avatar
      Register manual entry point as jump target · 6b91aeb9
      Alessandro Di Federico authored
      This commit fixes a bug triggered by specifying the `--entry` switch:
      the entry point would not be registered as a jump target, instead the
      code would try to get the basic block associated to that address,
      resulting in an assertion.
      
      The manually specified entry point is now registered as a jump target
      coming from global data.
      6b91aeb9
  11. Jan 11, 2017
  12. Dec 08, 2016
Loading